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

Question

随着新病毒变种的发布，搜索字符串形式的数据继续增长，这引发了我的问题 - AV 引擎如何如此有效地搜索文件以查找已知签名？如果我下载了一个新文件，我的 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 如何 的看法可能工作。我不确定。如果有人认为信息不正确，请通知我。

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

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

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

因此，防病毒软件的大致工作是计算文件的哈希值或仅计算其关键部分(可能存在恶意注入(inject))，并在其签名数据库中搜索它。如上所述，搜索速度非常快，可以在短时间内扫描大量文件。如果找到，则该文件被归类为恶意文件。

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

您可以阅读这些页面以获得更多见解。

Which is faster, Hash lookup or Binary search?

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