代码之家 › 专栏 › 技术社区 › Chad Birch

计算二进制数据相似度

similarity binary-data comparison

Chad Birch · 技术社区 · 17 年前

我在这里看到了一些与确定文件相似性有关的问题,但它们都链接到一个特定的域(图像、声音、文本等)。作为解决方案提供的技术需要了解所比较文件的底层文件格式。我正在寻找一种没有此要求的方法,可以比较任意二进制文件,而不需要了解它们包含的数据类型。也就是说,我希望确定 两个文件二进制数据的相似性百分比 .

为了给你提供更多细节,尽管这可能适用于许多事情,但我确实有一个正在解决的具体问题。我目前也有一个可行的解决方案,但我认为它并不理想。在比较方法和存储结果方面可能有很多优化。希望这里的一些人能给我一些新的想法。几天后,我可能会编辑一些关于我目前方法的信息,但我不想告诉你我是怎么做的,从而影响人们对这个问题的看法。

视频游戏ROM图像的克隆检测 最终幻想 因为NES是克隆体。游戏几乎共享了所有的资产(精灵、音乐等),但文本已被翻译。

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

为每对可能的ROM存储相似性数据将导致任何更流行的系统产生数百万行数据。一个拥有5000个ROM的系统需要2500万行相似性数据,而一个新游戏又需要增加5000行。
新的ROM可以随时添加,因此该方法不应假设它已经有一个“完整”的集合。也就是说,即使在你已经计算出所有现有ROM的相似性之后,如果添加了一个新的ROM(这也可能发生在之前的处理完全完成之前),也必须有一种方法将其与所有之前的ROM进行比较,以确定它是哪一个(如果有的话)的克隆。
在一定程度上,更高的处理速度应优先于精度。知道两个ROM是94%还是96%相似并不是特别重要,但如果需要一天的处理时间来比较新ROM和之前的所有ROM,程序可能永远不会真正完成。

10 回复 | 直到 17 年前

Waylon Flinn 12 年前

^2. ),我想)。我会尝试找到一个简单的哈希值来识别可能的候选者进行比较。这在概念上与spdenne和Eduard的建议相似。也就是说,找到一个可以应用于每个项目一次的哈希值,对列表进行排序,然后对列表中哈希值接近的项目进行更细粒度的比较。

LSHKit 软件库实现了这类算法 FINDING SIMILAR FILES IN A LARGE FILE SYSTEM Multi-resolution similarity hashing 描述了一种更强大的算法。不过,如果没有订阅,它似乎无法访问。你可能想保留维基百科上的文章 Locality Sensitive Hashing 方便您浏览其他资源。它们都非常技术化,维基百科条目本身也非常数学化。作为一种更用户友好的替代方案,您可能能够应用以下领域的一些想法(甚至是可执行文件) Acoustic Fingerprinting .

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

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

jpalecek 17 年前

bsdiff

Stephen Denne 17 年前

使用以下的一些想法 Plagiarism Detection 算法。

为了为每个ROM创建一个可比较的“签名”,随着小部分的变化而略有变化,生成类似于单词频率图的东西,但你可以对ROM的很短部分进行哈希运算,并记录哈希值的频率,而不是记录单词的频率。

不要只对一个部分进行哈希运算,然后从第一部分的末尾开始对下一部分进行哈希,而是使用滑动窗口,对从字节1开始的部分进行哈希计算,然后对从字节2开始、从字节3开始的相同大小的部分进行哈希计算,以此类推。这将抵消ROM中可变大小变化部分的影响。

如果你使用一个简单的哈希函数,比如每个8位字节的异或,这样你就可以很容易地计算下一个窗口位置的哈希,方法是用输出的8位对当前哈希进行异或运算,用输入的8位进行异或运算。另一种可选的哈希函数可能只是使用指令码字长度。这可能足以为表示机器指令的代码创建静态模式。重要的是,你需要一个哈希函数,在指令代码中产生常见的短序列,从而产生相同的哈希值。

你可能想要更少的哈希值,每个哈希值的频率更高,但不要走得太远,否则你的图会太平坦,导致比较困难。同样,不要走得太宽,否则你会有很多非常小的频率,使比较再次变得困难。

Chad Birch 17 年前

虽然这已经超过了“几天”,但我想我可能应该在这里添加我目前的解决方案。

7zip

第一步是单独压缩每个ROM并记录压缩后的大小,然后尝试将任意两个ROM归档在一起,看看结果大小与它们各自的压缩大小有多大不同。如果组合大小与单个大小的总和相同,则它们0%相似,如果大小与其中一个(最大的一个)相同,则完全相同。

结合上述内容,保持任何一对ROM之间可能相似性的上限和下限。这允许进一步确定优先级。如果ROM A和B有95%相似,而ROM B和C只有2%相似,那么你已经知道A和C在0%到7%之间。这太低了,不能被复制,所以这种比较可以安全地推迟甚至完全忽略,除非我真的想知道一切的确切相似之处。

Nils Pipenbrinck 17 年前

我认为从数据压缩中借鉴的一些技术可能会很有趣:

大小的差异将给你一个粗略的估计,这些文件有多相似。

Rik Hemsley 17 年前

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

Eduard - Gabriel Munteanu 17 年前

您可以从存储以下内容开始 hash trees 只需要为每个ROM存储一组这样的哈希值,并且假设块大小恒定,所需的存储空间仅与ROM的大小成比例(但远低于ROM的大小)。所选块大小必须提供足够的粒度以确保准确性,例如:对于最小大小为128MiB的块,精度限制为1%,以及 Tiger-128 hash (类似于他们用来检查通过DirectConnect传输的文件的方法),1MiB的块大小是可以的,你可以将所有哈希存储在128*128/8=2048字节中!因此,使用10000个ROM只需要大约20MiB的空间。此外,您可以选择一个不太安全但更快和/或更小的哈希。添加/检查新ROM的相似性将需要以下内容:

对于数据库中已有的每个ROM,将其哈希值与新ROM的哈希值进行比较(见下文)。

正如你所看到的,这个问题在性能方面被简化为一个更简单的问题:检查更小的数据集的相似性。

Liudvikas Bukys 17 年前

考虑将文件组织为数据流图,并对该表示进行规范化。既然你知道指令集,这可能是可行的,也许只需要捆绑一个反汇编程序并进行一些文本处理。
CRM114

Yuval F 17 年前

正如Waylon Flinn所说,你可能需要一个二进制增量算法。这 rsync algorithm utility's documentation .

HUAGHAGUAH 17 年前

这里的困难在于,由于您正在处理可执行代码,简单的更改可以在整个ROM中传播。所有值的地址和偏移量都可以通过添加单个变量或不添加操作指令来更改。这将使基于块的哈希变得毫无价值。

一个快速而肮脏的解决方案是用 difflib (或等效的w/你最喜欢的语言),因为它为你提供了一个滑动比较,可以处理数据的添加或删除。将ROM拆分为可执行文件和数据部分(如果可能的话)。数据部分可以直接与 similarity ratio calculated

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