Java中用于文件比较的程序化方法

Question

将两个十六进制文件签名相互比较以获得相似性的最佳方法是什么.

更具体地说,我想要做的是采用.exe文件的十六进制表示形式,并将其与一系列病毒签名进行比较.对于这种方法,我计划将文件(exe)十六进制表示分成N个字符的单独组(即10个十六进制字符),并对病毒签名执行相同操作.我的目标是执行某种启发式方法,因此统计检查此exe文件是否与已知病毒签名具有X%的相似性.

我想到的最简单也可能非常错误的方法是将exe [n,n-1]与病毒[n,n-1]进行比较,其中数组中的每个元素都是一个子数组,因此exe1 [0, 9]针对病毒1 [0,9].每个子集将进行统计分级.

你可以意识到会有大量的比较,因此非常慢.所以我想问一下你们是否可以想出一个更好的方法来进行这样的比较,例如一起实现不同的数据结构.

这是我正在为我的BSc做的一个项目,我正在尝试开发一种算法来检测多态恶意软件,这只是整个系统的一部分,另一部分是基于遗传算法来发展静态病毒签名.任何建议,意见或资源等一般信息都是非常受欢迎的.

---

定义:多态恶意软件(病毒,蠕虫,......)与"原始"版本保持相同的功能和有效负载,同时具有明显不同的结构(变体).他们通过代码混淆实现了这一点,从而改变了他们的十六进制签名.用于多态的一些技术是; 格式更改(插入删除空格),变量重命名,语句重新排列,垃圾代码添加,语句替换(x = 1更改为x = y/5,其中y = 5),交换控制语句.非常像流感病毒变异,因此疫苗接种无效,多态恶意软件会发生变异以避免检测.

---

更新:建议你们给我关于阅读的内容; 我做到了,但它让我更加困惑.我找到了几种可以应用于我的问题的距离算法,例如;

• 最常见的子序列
• Levenshtein算法
• Needleman-Wunsch算法
• Smith-Waterman算法
• Boyer Moore算法
• Aho Corasick算法

但现在我不知道使用哪个,他们似乎都以不同的方式做同样的事情.我将继续做研究,以便我能更好地理解每一个; 但同时你可以给我你的意见,which might be more suitable这样我就可以在研究过程中优先考虑并深入研究.

---

更新2:我最终使用了LCSubsequence,LCSubstring和Levenshtein Distance的合并.谢谢大家的建议.

在GitHub上有一份完成的纸张

Answer 1

对于这样的算法，我建议您研究一下生物信息学领域。那里有一个类似的问题设置，因为您有大文件（基因组序列），您正在其中寻找某些签名（基因、特殊的众所周知的短碱基序列等）。

另外，考虑到多态恶意软件，该领域应该为您提供很多帮助，因为在生物学中似乎同样难以获得精确匹配。（不幸的是，我不知道合适的近似搜索/匹配算法可以为您指出。）

这个方向的一个例子是采用Aho Corasick算法之类的算法，以便同时搜索多个恶意软件签名。

类似地，像Boyer Moore算法这样的算法可以为您提供出色的搜索运行时间，特别是对于较长的序列（对于大小为 N 的文本，您在其中查找大小为 M 的模式，平均情况为 O(N/M)，即次线性搜索时间）。