comparison - 计算二进制数据相似度

Question

我在这里看到了一些与确定文件相似性有关的问题，但它们都与特定域（图像、声音、文本等）相关联。作为解决方案提供的技术需要了解被比较文件的基础文件格式。我正在寻找的是一种没有此要求的方法，可以比较任意二进制文件而无需了解它们包含什么类型的数据。也就是说，我正在寻找确定两个文件的二进制数据的相似性百分比。

为了提供更多细节供您使用，尽管这可能适用于许多事情，但我确实有一个正在处理的特定问题。我目前也有一个可行的解决方案，但我认为它并不理想。在比较方法和存储结果方面可能有很多优化。希望这里的一些人能够给我一些新的想法。几天后我可能会编辑一些关于我当前方法的信息，但我不想通过告诉你我已经在做什么来偏见人们对这个问题的看法。

我正在处理的问题是视频游戏 ROM 映像的克隆检测。对于那些没有仿真经验的人来说，ROM 是游戏卡带上数据的转储。ROM“克隆”通常是同一游戏的修改版本，最常见的类型是翻译版本。例如，NES原版《最终幻想》的日文版和英文版都是克隆版。游戏共享几乎所有的资产（精灵、音乐等），但文本已被翻译。

目前有几个小组致力于维护各种系统的克隆列表，但据我所知，这一切都是手动完成的。我正在尝试做的是找到一种方法来自动和客观地检测相似的 ROM 映像，基于数据相似性而不是“这些看起来像同一个游戏”。检测克隆有几个原因，但主要动机之一是与Solid 压缩一起使用。这允许将所有游戏克隆一起压缩到同一个存档中，整个压缩克隆集通常只占用比单个 ROM 稍多的空间。

在提出潜在方法时需要考虑的一些问题：

• ROM 的大小差异很大，具体取决于系统。有些很小，但现代系统可能有较大的系统，256MB 或更多。一些（全部？）系统只有 2 作为可能大小的幂，其中一个系统上的 130MB 游戏将有 256MB ROM，大部分是空的。请注意，因此，如果游戏版本超过阈值并且必须使用两倍大小的卡带，某些克隆的大小可能会有很大差异。
• 目前，许多系统上有数千个已知的 ROM，大多数系统仍在不断发布新的 ROM。即使对于旧系统，也有一个主要的 ROM 黑客社区经常生产修改后的 ROM。
• 为每对可能的 ROM 存储相似性数据将为任何更流行的系统产生数百万行数据。一个有 5000 个 ROM 的系统需要 2500 万行相似性数据，而一个新游戏又增加了 5000 行。
• 处理的状态必须是可恢复的，这样如果它被中断，它可以从中断的地方继续。使用任何方法都需要进行大量处理，并且假设整个事情将在一批中运行是不安全的。
• 可以随时添加新的 ROM，因此该方法不应假定它已经具有“完整”集。也就是说，即使您已经确定了所有现有 ROM 的相似性，如果添加了一个新 ROM（这也可能在之前的处理完全完成之前发生），必须有一种方法将其与所有之前的 ROM 进行比较，以确定哪个（如果有的话）是它的克隆。
• 更高的处理速度应该优先于准确性（到一个点）。知道两个 ROM 是 94% 还是 96% 相似并不是特别重要，但如果需要一天的时间来比较一个新的 ROM 和以前的所有 ROM，那么程序可能永远不会真正完成。

这是一个有趣的问题，我期待看到其他人能想出什么。如果您需要更多详细信息，请在评论中告诉我，我会尽力提供。

Answer 1

听起来您想要一个二进制增量，或者可能是一个从二进制增量应用程序派生的索引（就像它的大小一样）。然后，您可以将此索引与您通过实验确定的某个基线进行比较，以确定它是否是“克隆”。

压缩和增量创建之间有很多相似之处，所以我想说您与当前的实现相距不远。

话虽如此，数据库中每个二进制文件的成对比较可能非常昂贵（我认为 O(n ² )）。我会尝试找到一个简单的哈希来识别可能的候选者进行比较。在概念上类似于 spdenne 和 Eduard 的建议。也就是说，找到一个可以应用于每个项目一次的散列，对该列表进行排序，然后对列表中散列靠近的项目使用更细粒度的比较。

多年来，构建对一般情况有用的哈希一直是 CS 中积极追求的研究课题。LSHKit软件库实现了一些此类算法。互联网可访问的论文FINDING SIMILAR FILES IN A LARGE FILE SYSTEM似乎更多地针对比较文本文件，但可能对您有用。最近的论文多分辨率相似性哈希描述了一种更强大的算法。不过，如果没有订阅，它似乎无法访问。您可能希望保留有关Locality Sensitive Hashing的维基百科文章方便您浏览其他资源。他们都获得了相当的技术性，维基百科条目本身的数学很重。作为一种更加用户友好的替代方案，您可以应用声学指纹领域的一些想法（甚至可执行文件） 。

如果您愿意放弃一般情况，您可能会找到一个更简单（更快）的特定于域的哈希函数，它只适用于您的 ROM。可能涉及标准或通用字节序列的放置以及它们附近的选择位的值。我对你的二进制格式不太了解，但我在想象文件中部分开始的信号，比如声音、图像或文本的区域。二进制格式经常将这类部分的地址存储在文件开头附近。有些还使用链接机制，将第一部分的地址及其大小存储在已知位置。这使您可以移动到下一个部分，该部分还包含大小等。稍作调查可能会让您发现任何相关的格式，

如果散列函数不能完全满足您的要求（或者它们需要某种类型的输入来定义度量/距离），那么网络上有几种二进制增量算法和实现。我最熟悉的是subversion版本控制系统。它使用称为 xdelta 的二进制增量算法来有效地存储二进制文件修订。这是直接指向其存储库中实现它的文件的链接：xdelta.c。网络上可能有一个工具也可以使这更容易访问。

Answer 2

您可能想查看bsdiff，它是一个二进制差异/修补系统。还有一篇论文有很多理论。

Answer 3

使用抄袭检测算法中的一些想法。

我的点子：

为了为每个 ROM 创建一个可比较的“签名”，随着小部分的变化而略有不同，产生类似于词频图的东西，但不是记录词的频率，您可以散列 ROM 的非常短的部分，并记录哈希值的频率。

不要只散列一个部分，然后从第一部分的末尾开始下一部分，而是使用滑动窗口，从字节 1 开始散列部分，然后从字节 2 开始散列相同大小的部分，然后从字节3等。这将抵消ROM中可变大小的变化部分的影响。

如果您使用简单的哈希函数，例如每个 8 位字节的 xor，那么您可以通过 xor 与传出的 8 位和 xor 传入的 8 位轻松计算下一个窗口位置的哈希。另一种替代散列函数可能只是使用指令码字长。这可能足以为表示机器指令的代码创建静态模式。重要的是，您需要一个哈希函数，它会在指令代码中产生常见的短序列，从而产生相同的哈希值。

您可能需要较少的散列值和较高的频率，但不要走得太远，否则您的图表将太平，导致难以比较它们。同样不要太宽，否则你会有很多非常小的频率，再次难以比较。

每个 ROM 存储此图。通过计算每个哈希值的频率差的平方和来比较两个不同 ROM 的频率图。如果总和为零，则 ROM 很可能是相同的。离零越远，ROM 就越不相似。

Answer 4

虽然这不仅仅是“几天”，但我想我应该在这里添加我当前的解决方案。

Nils Pipenbrinck 的方向与我目前的方法相同。由于找到克隆的主要结果之一是从固态存档中节省了大量资金，我想我可以尝试将任意两个 ROM 压缩在一起，看看节省了多少空间。为此，我正在使用7zip中的 LZMA 算法。

第一步是单独压缩每个 ROM 并记下压缩后的大小，然后尝试将任意两个 ROM 归档在一起，看看生成的大小与它们各自的压缩大小有多大不同。如果组合大小与单个大小的总和相同，则它们的相似度为 0%，如果大小与其中之一（最大的）相同，则它们是相同的。

现在，这需要大量的压缩尝试，所以到目前为止我有一些优化（并且想了解更多）：

1. 根据压缩大小的相似程度对比较进行优先级排序。如果 ROM A 的压缩大小为 10MB，而 ROM B 的压缩大小为 2MB，它们的相似度不可能超过 20%，因此比较它们以获得真正的结果可以留到以后。对高度相似的文件运行相同的压缩算法往往会产生相似大小的结果，因此可以很快找到很多克隆。

2. 结合上述内容，保持任何一对 ROM 之间可能的相似性的上限和下限。这允许进一步确定优先级。如果 ROM A 和 B 的相似度为 95%，而 ROM B 和 C 的相似度仅为 2%，那么您已经知道 A 和 C 在 0% 到 7% 之间。这对于克隆来说太低了，因此可以安全地推迟甚至完全忽略这种比较，除非我真的想知道所有事物的确切相似之处。

Answer 5

我认为从数据压缩中借来的一些技术在这里可能很有趣：

假设您有两个文件，A 和 B。

单独压缩每个文件并将压缩后的大小加在一起。然后将这两个文件连接成一个大文件并压缩它。

大小的差异将使您粗略估计文件的相似程度。

我建议您尝试使用 Burrow Wheeler Transformation (bzip2) 进行压缩。大多数其他压缩算法只有有限的历史。BWT 算法otoh 可以处理非常大的数据块。该算法同时“看到”两个文件，任何相似性都会导致更高的压缩率。

Answer 6

XDelta 对于获得体面的二进制差异非常有用：http: //xdelta.org

Answer 7

您可以从存储哈希树之类的东西开始。只需要为每个 ROM 存储一组这样的哈希，并且所需的存储空间仅与 ROM 的大小成比例（但远低于），假设块大小恒定。选择的块大小必须提供足够的粒度以确保准确性，例如：对于 128MiB 的最小大小，1% 的准确性约束和Tiger-128 哈希（类似于他们用来检查通过 DirectConnect 传输的文件），块大小为 1MiB没问题，您可以将所有哈希值存储在 128 * 128 / 8 = 2048 字节中！因此，为 10,000 个 ROM 执行此操作只需要大约 20MiB 的空间。此外，您可以选择不太安全但更快和/或更小的散列。添加/检查新 ROM 的相似性将需要以下内容：

1. 将新的 ROM 分成块并散列每个块。
2. 对于数据库中已经存在的每个 ROM，将其哈希值与新 ROM 的哈希值进行比较（见下文）。

比较函数应该检查相似性。但它应该将每个散列视为一个不可分割的值，即不要费心试图找到两个散列之间的逻辑显着差异函数。只要块大小足够小并且哈希冲突足够少，通过简单的等值比较就可以保证准确性。

如您所见，问题在性能方面被简化为一个更简单的问题：检查小得多的数据集的相似性。

Answer 8

两个想法：

• 考虑将文件组织为数据流图并对该表示进行一些规范化。既然你知道指令集，这可能是可行的，也许只是捆绑一个反汇编程序并进行一些文本处理。
• 诸如CRM114 之类的可训练分类器可能会派上用场，为您提供紧凑的表示，让您了解二进制文件是否有很多共同点。

Answer 9

正如 Waylon Flinn 所说，您可能需要二进制增量算法。rsync 算法是一个很好的算法。它快速可靠。另请参阅实用程序的文档。

Answer 10

这里的困难在于，由于您正在处理可执行代码，因此简单的更改可以传播到整个 ROM。ALL 值的地址和偏移量可以随着添加单个变量或无操作指令而改变。这将使基于块的散列变得毫无价值。

一个快速而肮脏的解决方案是使用difflib（或具有您喜欢的语言的等效语言）破解一个解决方案，因为它可以为您提供可以处理数据添加或删除的滑动比较。将 ROM 拆分为可执行和数据部分（如果可能）。可以直接比较数据部分并计算相似率，尽管您仍然会遇到地址或偏移量的问题。

可执行部分更有趣。阅读机器的 asm 格式，获取可执行文件并将其拆分为一系列操作码。保留操作码和寄存器部分，但屏蔽“有效负载”/“立即”部分（它加载变量地址的位置）。将得到的信息也交给相似率计算器。

不幸的是，这仍然是对您跟踪的 ROM 数量的 O(n^2) 操作，但这可以通过（增量）聚类或基于频率的比较顺序来减轻，以减少所需的比较量。