计算二进制数据相似度

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

为了给你提供更多的细节,即使这可能适用于很多事情,我确实有一个特定的问题,我正在努力.我目前也有一个有效的解决方案,但我不认为它是理想的.在比较方法方面可能存在许多优化,并存储结果.希望这里的一些人能够给我一些新的想法.我可能会在几天之后编辑一些关于我当前方法的信息,但我不想通过告诉你我是如何做的来偏见人们对这个问题的想法.

我正在研究的问题是视频游戏ROM映像的克隆检测.对于那些没有仿真经验的人来说,ROM是游戏卡带上的数据转储.ROM"克隆"通常是同一游戏的修改版本,最常见的类型是翻译版本.例如,NES 的原始最终幻想的日语和英语版本是克隆.游戏几乎分享了他们所有的资产(精灵,音乐等),但文本已被翻译.

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

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

ROM的大小各不相同,具体取决于系统.有些很小,但现代系统可能有大型,256MB或更多.一些(所有？)系统只有2个可能的大小的功能,其中一个系统上的130MB游戏将具有256MB的rom,基本上是空的.请注意,因此,如果游戏版本超过阈值并且必须使用两倍大小的盒式磁带,则某些克隆可能具有完全不同的大小.

目前在许多系统上有数千种已知的ROM,大多数系统仍然不断发布新的系统.即使对于较旧的系统,也有一个主要的ROM黑客社区经常生产修改后的ROM.

为每个可能的ROM对存储相似性数据将导致数百万行数据用于任何更流行的系统.具有5000个ROM的系统将需要2500万行相似性数据,其中一个新游戏添加另外5000行.

处理状态必须是可恢复的,因此如果它被中断,它可以从中断的地方继续.使用任何方法,将需要大量处理,并假设整个事件将在一个批次中运行是不安全的.

可以随时添加新的ROM,因此该方法不应该假设它已经具有"完整"集.也就是说,即使您已经找出所有现有ROM的相似性,如果添加了一个新的(并且这也可能在之前的处理完全完成之前发生),必须有一种方法将其与之前的所有ROM进行比较,以确定哪个(如果有的话)它是克隆的.

较高的处理速度应优先于准确性(至某一点).知道两个ROM是94%还是96%相似并不是特别重要,但如果需要一天的处理时间来比较新的ROM与之前的所有ROM,那么该程序可能永远不会真正完成.

这是一个有趣的问题,我期待看到其他人能想到的东西.如果您想了解更多细节,请在评论中告诉我,我会尽力提供.

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

压缩和增量创建之间有很多相似之处,所以我说你对当前的实现并不遥远.

话虽这么说,数据库中每个二进制文件的成对比较可能非常昂贵(O(n ²),我认为).我会尝试找到一个简单的哈希来识别可能的候选对象.概念上类似于斯普登和爱德华所暗示的东西.也就是说,找到一个可以应用于每个项目的哈希值,对该列表进行排序,然后对列表中哈希值接近的项目使用更细粒度的比较.

几年来,构建对一般案例有用的哈希一直是CS积极追求的研究课题.该LSHKit软件库实现这种一些算法.可访问互联网的论文在大型文件系统中查找类似文件似乎可能更多地用于比较文本文件,但可能对您有用.最近的论文多分辨率相似性散列描述了一种更强大的算法.但是,如果没有订阅,它似乎无法访问.您可能希望保留关于Locality Sensitive Hashing的维基百科文章在浏览其他资源时很方便.它们都具有很强的技术性,维基百科条目本身就非常重要.作为一种更加用户友好的替代方案,您可以应用声学指纹识别领域的一些想法(甚至可执行文件).

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

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

你可能想看看bsdiff,它是一个二进制的差异/修补系统.还有一篇论文涉及很多理论.

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

我的想法:

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

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

如果你使用了一个简单的散列函数,比如每个8位字节的xor,那么你就可以通过xor计算下一个窗口位置的散列值,当前散列值为8位,x或者输入8位.另一种替代散列函数可以简单地使用指令代码字长.这可能足以为代表机器指令的代码创建静态模式.重要的是你需要一个哈希函数,它会导致指令代码中的公共短序列产生相同的哈希值.

您可能希望更少的哈希值具有更高的频率,但不要太远,否则您的图形将太平,导致难以比较它们.同样不要太宽,或者你会有很多非常小的频率,再次比较难.

每个ROM存储此图表.通过计算每个散列值的频率差的平方和来比较两个不同ROM的频率图.如果总和为零,那么ROM可能是相同的.它越远离零,ROM就越不相似.

虽然它比"几天"要多得多,但我想我应该在这里添加我当前的解决方案.

Nils Pipenbrinck与我目前的方法走的方向相同.由于找到克隆的主要结果之一是实体存档的巨大节省,我想我可以尝试将任意两个ROM压缩在一起并查看节省了多少空间.我在7zip中使用LZMA算法.

第一步是单独压缩每个ROM并记下压缩大小,然后尝试将任意两个ROM存档在一起,并查看最终大小与其各自压缩大小的差异.如果组合尺寸与各个尺寸的总和相同,则它们相似0%,如果尺寸与其中一个(最大尺寸)相同,则它们是相同的.

现在,这需要大量的压缩尝试,所以到目前为止我有几个优化(并想了解更多):

根据压缩大小的相似程度对比较进行优先级排序.如果ROM A的压缩大小为10MB,而ROM B的压缩大小为2MB,则它们不可能超过20%,因此比较它们以获得实际结果可以保留到以后.在高度相似的文件上运行相同的压缩算法往往会产生类似大小的结果,因此可以非常快速地找到很多克隆.

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