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

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

最好不要去想这些算法需要多复杂和多长时间。

如果你对此感兴趣，可以在这里找到一个很好的介绍，链接是这个.ps文档。

至于这些算法是否有好的实现，我就不太清楚了。

Answer 2

请注意，即使你是通过这种方式找到的，也不能保证你找到的最长匹配就是你真正想要的。相反，你可能会发现一些常见的初始化代码或者同一个编译器添加的字符串表之类的东西。

Answer 3

可以看看最长公共子串问题。我猜difflib使用的是动态规划的方法，但这个方法在比较可执行文件时肯定太慢了。用后缀树或后缀数组会更有效。

使用perl的Tree::Suffix可能是最简单的解决方案。显然，它可以提供指定长度范围内的所有公共子串：

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