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

Question

随着新病毒变种的发布,搜索字符串形式的数据会继续增长,这提示了我的问题 - AV引擎如何有效地搜索文件以查找已知签名？如果我下载一个新文件,我的AV扫描仪会根据其签名快速识别该文件是否为威胁,但它如何能够如此快速地执行此操作？到目前为止,我确信有数十万个签名.

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 算法

以下是我的旧答案。它仍然与轻松检测恶意软件（例如蠕虫）相关，这些恶意软件只是简单地复制自身：

我只会写一些我对自动驾驶汽车如何运作的想法。我不确定。如果有人认为该信息不正确，请通知我。

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

签名只是文件的唯一指纹（只是字节序列）。用计算机科学来说，可以称为哈希。单个哈希可能需要大约 4/8/16 字节。假设大小为 4 字节（例如CRC32），则256MB中可以存储大约6700 万个签名。

所有这些哈希值都可以存储在签名数据库中。该数据库可以用平衡树结构来实现，以便可以及时完成插入、删除和搜索操作，即使对于较大的值（n是条目数），O(logn)这也相当快。n或者，如果有大量可用内存，则可以使用哈希表O(1)，它可以进行插入、删除和搜索。n随着规模的增大和使用良好的散列技术，速度会更快。

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

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

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

哈希查找和二分查找哪个更快？

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