编程方法实现在Java文件比较

Question

什么是最好的方法来比较两个进制文件的签名反对彼此的相似之处。

更具体地说，我想要做的是采取进制表示的。执行文件，并比较它对一系列的病毒的签名。这种办法我的计划，以打破文件(exe)hex表示成各个组的N字符的(ie。10hex chars)做同样的带有病毒的签名。我的目标，以执行某些种类的启发，因此统计检查是否该文件已X%的相似性对已知的病毒的签名。

最简单和有可能非常错误的方式我认为这样做是比较exe[n,n-1]对病毒[n,n-1]其中的每一个元件阵列是分列的，因此exe1[现0.9]对virus1[现0.9].每个子集将分等级统计。

你能意识到会有一个巨大的数字的比较，因此非常非常缓慢。所以我想问是否你们可以想到一个更好的方法做这样的比较，例如实施不同的数据结构连接在一起。

这是对一个项目，我在做我的BSc在我试图开发一个算法检测多态的恶意软件，这仅仅是其中一部分的整个系统，另一个是基于遗传算法发展的静态病毒的签名。任何建议、评论或一般信息，例如资源是非常值得欢迎的。

---

定义:多晶型的恶意软件(病毒、蠕虫...)保持相同的功能和有效载荷为自己的"原始"的版本，同时具有明显的不同结构(变体)。他们的实现是通过代码混淆，从而改变他们的hex签名。一些技术用于多态性；格式的修改(插入清除毛坯)，变更名，声明重排，垃圾码外，声明更换(x=1改x=y/5，其中y=5)，交换控制的发言。所以就像流感病毒变异和因此接种疫苗是不是有效的，多晶型的恶意软件的改变，以避免检测。

---

更新： 后劝你们给我在关于什么阅读；我做的，但它有点困惑，我更多。我发现了几个远距离的算法，可以应用到我的问题，例如;

• 最常见的子序列
• Levenshtein算法
• 裁缝–Wunsch算法
• 史密斯–沃特曼算法
• Boyer Moore算法
• Aho Corasick算法

但现在我不知道它的使用，他们似乎都对他做同样的事情在不同的方式。我将继续做的研究，所以，我可以理解的每一个更好；但在平均时间你能给我您的意见 which might be more suitable 因此，我可以给它的优先权在我的研究和以研究得更深。

---

更新2： 我结束了使用合并的LCSubsequence,LCSubstring和编辑的距离。感谢您所有的建议。

有一个复制成纸上 想

Answer 1

对于这样的算法我建议你看看生物信息学领域。有一个类似的问题设定在那你有大量的文件(基因组序列)中，你正在寻找某个签名(基因、特别众所周知的短基序列，等等)。

还考虑多态的恶意软件，这个部门应该提供你一个很大的，因为在生物看来同样难以得到确切匹配。(不幸的是，我不知道还有适当的近似的搜索/匹配的算法来点你.)

一个实例，从这个方向将是适应的东西喜欢的 Aho Corasick 算法，以便寻找几个恶意软件的签字在同一时间。

同样，算法喜欢的 Boyer Moore 算法得到你的梦幻般的检索运行时，尤其是对于较长的序列(平均情况O(N/M)为文本的大小N在哪你看起来一模式的大米，即次线性的搜索倍)。

Answer 2

一些论文已经出版，在附近找到复制文件，在一个大集的文件中的上下文的网页.我想你会发现它们很有用。例如，请参阅 此 演示.

Answer 3

已经有一个严重量的研究的最近进入自动化检测的重复的错误报告，在错误的储存库。这基本上是同样的问题。不同的是，你正在使用的二进制数据。他们是类似的问题，因为你将会找串，同样的基本模式，即使该模式可能会有一些细微的差别。一直距离算法可能不会为您好在这里。

本文件提供了一个很好的摘要的问题，以及一些办法在其引文已经试过了。

ftp://ftp.computer.org/press/outgoing/proceedings/Patrick/apsec10/data/4266a366.pdf

Answer 4

正如有人已经指出，相似性与已知的串和生物信息学问题可能会有帮助。最常见的substring是非常脆弱，这意味着一个区别可以减少一半的长度这样的一串。你需要的一种形式的串准，但更有效率的比*史密斯-沃特曼。我会试试看的节目，例如爆炸，BLAT或MUMMER3，看看他们是否可以适合你的需要。记住，缺省参数，对于这些方案，都是基于生物学应用程序(多少以惩罚插入或替代实例)，所以你也许应该看着重新估算参数的基础上你的应用领域，可能基于一个培训组。这是一个已知的问题，因为甚至在生物学上的不同应用需要不同的参数(基础，例如，在进化距离的两个基因组的对比).这也是可能的，但是，即使以默认的一些算法可能会产生有用的结果。所有最好的就是有一个生成模型的病毒变化，可以指导你的最佳选择一个距离和比较法。