随着新的病毒变种不断发布,以搜索字符串形式呈现的数据也在不断增长,这引发了我的疑问 - 杀毒引擎如何如此高效地搜索已知签名的文件?如果我下载一个新文件,我的杀毒扫描器可以快速识别该文件是否是威胁,这是基于它的签名,但是它是如何如此迅速地完成这个过程的?我相信到这个时候已经有成千上万的签名了。
更新: 正如 tripleee 指出的那样,Aho-Corasick算法 对于病毒扫描程序非常相关。以下是一些相关资料供您参考:
http://www.dais.unive.it/~calpar/AA07-08/aho-corasick.pdf
http://jason.spashett.com/av/index.htm
以下是我的旧回答。它仍然适用于轻松检测像蠕虫一样简单地制作副本的恶意软件:
我将写下一些关于防病毒软件可能如何工作的想法。我不确定。如果有人认为信息错误,请通知我。
AVs检测潜在威胁的方法有很多种。其中之一是基于签名的检测。
签名只是文件的唯一指纹(它只是一系列字节)。从计算机科学的角度看,它可以被称为哈希。一个哈希值可能需要大约4/8/16个字节。假设哈希大小为4个字节(例如,CRC32),则约可以存储6700万个哈希值在256MB中。
所有这些哈希值都可以存储在签名数据库中。可以使用平衡树结构实现此数据库,以便可以进行O(logn)
时间的插入、删除和搜索操作,即使对于大的n
值也非常快。或者,如果有大量内存可用,则可以使用哈希表,它提供O(1)
的插入、删除和搜索。随着n
的增长和使用良好的哈希技术,这可以更快地进行。
我不知道一个实际的音视频是如何工作的,但我认为这个问题与在给定字典中查找长文本中的单词有关。
对于上述问题,像TRIE这样的数据结构将使其非常快速。处理一个长度为N的文本字典,包含K个单词,只需要O(N)的时间。