AV引擎如何如此高效地搜索文件中的已知签名？

Question

随着新的病毒变体的发布，搜索字符串形式的数据继续增长，这引发了我的问题- AV引擎如何如此高效地搜索文件中的已知特征码？如果我下载一个新文件，我的反病毒扫描程序会根据文件的签名快速识别该文件是否构成威胁，但它怎么能这么快做到这一点？我相信到目前为止，已经有成千上万的签名了。

Answer 1

更新：正如tripleee指出的那样，Aho-Corasick algorithm似乎与病毒扫描程序非常相关。下面是一些值得阅读的内容：

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-like algorithm for use in anti-malware code

下面是我以前的答案。它仍然适用于简单地检测像蠕虫这样的恶意软件，这些恶意软件只是简单地复制自己：

我只想写一些关于如何工作的想法。我不确定。如果有人认为信息不正确，请通知我。

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

签名只是文件的唯一指纹(它只是一个字节序列)。在计算机科学方面，它可以被称为散列。单个散列可能需要大约4/8/16字节。假设大小为4字节(例如，CRC32)，则大约6700万个签名可以存储在256MB中。

所有这些散列都可以存储在签名数据库中。这个数据库可以用平衡的树结构实现，这样插入、删除和搜索操作就可以在O(logn)时间内完成，即使对于n (n是条目的数量)的大值来说，这也是相当快的。或者，如果有大量内存可用，则可以使用哈希表，它提供O(1)插入、删除和搜索。随着n变得越来越大，并且使用了一种很好的散列技术，这样做会更快。

因此，杀毒软件所做的大致就是计算文件的哈希值或仅计算其临界区(可能存在恶意注入的地方)，并搜索其签名数据库。如上所述，搜索速度非常快，可以在短时间内扫描大量文件。如果找到该文件，则将其归类为恶意文件。

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

你可以阅读这些页面来获得更多的洞察力。

Which is faster, Hash lookup or Binary search?

https://security.stackexchange.com/questions/379/what-are-rainbow-tables-and-how-are-they-used

Answer 2

许多签名被锚定到文件的二进制结构中的特定偏移量或特定部分。您可以跳过二进制文件中包含带有显示字符串的数据部分、内部结构的初始化数据等的部分。

许多现在的蠕虫都是独立的文件，对于整个文件签名(SHA1散列或类似的)就足够了。

关于如何扫描文件中的大量模式这一一般性问题，最好用指向Aho-Corasick algorithm的指针来回答。

Answer 3

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

对于上面的问题，像TRIE这样的数据结构会让它变得非常快。处理一个包含K个单词的Length=N文本字典只需要O(N)时间。