杀毒引擎如何高效地搜索已知签名的文件？

Question

随着新的病毒变种不断发布，以搜索字符串形式呈现的数据也在不断增长，这引发了我的疑问 - 杀毒引擎如何如此高效地搜索已知签名的文件？如果我下载一个新文件，我的杀毒扫描器可以快速识别该文件是否是威胁，这是基于它的签名，但是它是如何如此迅速地完成这个过程的？我相信到这个时候已经有成千上万的签名了。

- Charles Saag

Answer 1

更新: 正如 tripleee 指出的那样，Aho-Corasick算法 对于病毒扫描程序非常相关。以下是一些相关资料供您参考：

http://www.dais.unive.it/~calpar/AA07-08/aho-corasick.pdf

http://www.researchgate.net/publication/4276168_Generalized_Aho-Corasick_Algorithm_for_Signature_Based_Anti-Virus_Applications/file/d912f50bd440de76b0.pdf

http://jason.spashett.com/av/index.htm

Aho-Corasick类似算法用于反恶意软件代码中

以下是我的旧回答。它仍然适用于轻松检测像蠕虫一样简单地制作副本的恶意软件：

我将写下一些关于防病毒软件可能如何工作的想法。我不确定。如果有人认为信息错误，请通知我。

AVs检测潜在威胁的方法有很多种。其中之一是基于签名的检测。

签名只是文件的唯一指纹（它只是一系列字节）。从计算机科学的角度看，它可以被称为哈希。一个哈希值可能需要大约4/8/16个字节。假设哈希大小为4个字节（例如，CRC32），则约可以存储6700万个哈希值在256MB中。

所有这些哈希值都可以存储在签名数据库中。可以使用平衡树结构实现此数据库，以便可以进行O(logn)时间的插入、删除和搜索操作，即使对于大的n值也非常快。或者，如果有大量内存可用，则可以使用哈希表，它提供O(1)的插入、删除和搜索。随着n的增长和使用良好的哈希技术，这可以更快地进行。

所以，一个杀毒软件大致上的工作原理是，计算文件的哈希值或仅计算其关键部分（可以进行恶意注入），并在其签名数据库中进行搜索。正如上面所解释的，这种搜索非常快速，可以在短时间内扫描大量文件。如果找到，则将该文件归类为恶意文件。

同样，数据库也可以快速更新，因为插入和删除也很快。

您可以阅读以下页面以获得更多见解。 哈希查找和二分查找哪个更快？ 什么是彩虹表以及它们如何被使用

- max

---

有趣的帖子。我的初步想法是，AV引擎不会想要在每个文件中检查相同的位置/偏移量以获取签名。换句话说，我想象一些偏移量由于高碰撞发生率而比其他偏移量更好。 - Charles Saag

Answer 2

许多签名都锚定在特定的偏移量或文件的二进制结构中的特定部分。您可以跳过包含数据部分、内部结构的初始化数据等的二进制部分。

许多现代蠕虫是独立的文件，对于这些文件，整个文件的签名（SHA1哈希或类似）就足够了。

如何在文件中扫描大量模式的一般问题最好回答指向Aho-Corasick算法。

- tripleee

Answer 3

我不知道一个实际的音视频是如何工作的，但我认为这个问题与在给定字典中查找长文本中的单词有关。

对于上述问题，像TRIE这样的数据结构将使其非常快速。处理一个长度为N的文本字典，包含K个单词，只需要O(N)的时间。

- richselian