在两个二进制文件中查找匹配序列

Question

让我从一些背景开始。

今天早上，我们的一位用户报告说，Testuff 的安装文件被 CA 防病毒软件报告为感染了病毒。确信这是误报，我在网上查看，发现另一个程序 (SpyBot) 的用户报告了同样的问题。

现在，对于实际问题。

假设防病毒软件正在文件中寻找特定的二进制签名，我想在两个文件中找到匹配的序列，并希望找到一种方法来调整安装脚本以防止出现该序列。

我在 Python 中尝试了以下方法，但它已经运行了很长时间，我想知道是否有更好或更快的方法。

from difflib import SequenceMatcher

spybot = open("spybotsd160.exe", "rb").read()
testuff = open("TestuffSetup.exe", "rb").read()

s = SequenceMatcher(None, spybot, testuff)
print s.find_longest_match(0, len(spybot), 0, len(testuff))

有没有更好的 Python 或其他语言的库可以做到这一点？也欢迎采用完全不同的方法来解决这个问题。

Answer 1

参见最长公共子串问题。我猜 difflib 使用 DP 解决方案，这对于比较可执行文件来说肯定太慢了。使用后缀树/数组可以做得更好。

使用 perl Tree::Suffix可能是最简单的解决方案。显然它给出了指定长度范围内的所有常见子字符串：

@lcs = $tree->lcs;
@lcs = $tree->lcs($min_len, $max_len);
@lcs = $tree->longest_common_substrings;