10

比较两个十六进制文件签名的相似性的最佳方法是什么。

更具体地说，我想做的是采用 .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）、交换控制语句。就像流感病毒发生变异并因此疫苗接种无效一样，多态恶意软件也会发生变异以避免被发现。

更新：在你们给我关于阅读内容的建议之后；我这样做了，但这让我更加困惑。我发现了几种适用于我的问题的距离算法，例如；

  • 最长公共子序列
  • 文斯坦算法
  • Needleman-Wunsch 算法
  • 史密斯-沃特曼算法
  • 博耶摩尔算法
  • Aho Corasick 算法

但现在我不知道该使用哪个，他们似乎都以不同的方式做同样的事情。我会继续做研究，以便更好地理解每一个；但与此同时，您能否给我您的意见，which might be more suitable以便我在研究期间优先考虑它并深入研究它。

更新 2：我最终使用了 LCSubsequence、LCSubstring 和 Levenshtein Distance 的合并。谢谢大家的建议。

GitHub上有一份完成的论文

4

4 回答 4

4

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

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

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

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

于 2010-11-02T14:15:25.777 回答
2

已经发表了许多关于在网络搜索的背景下在大量文档中查找近乎重复的文档的论文。我想你会发现它们很有用。例如，请参阅此演示文稿。

于 2010-11-02T13:49:34.273 回答
1

正如有人指出的那样，与已知字符串和生物信息学问题的相似性可能会有所帮助。最长公共子串非常脆弱，这意味着一个差异可以将这样一个字符串的长度减半。您需要一种字符串对齐方式，但比 Smith-Waterman 更有效。我会尝试查看 BLAST、BLAT 或 MUMMER3 等程序，看看它们是否能满足您的需求。请记住，这些程序的默认参数是基于生物学应用程序（例如，对插入或替换的惩罚是多少），因此您可能应该根据您的应用程序域来重新估计参数，可能基于训练集。这是一个已知问题，因为即使在生物学中，不同的应用也需要不同的参数（例如，基于要比较的两个基因组的进化距离）。但是，即使在默认情况下，这些算法之一也可能会产生可用的结果。最好的办法是拥有一个病毒如何变化的生成模型，这可以指导您选择距离和比较算法的最佳选择。

于 2010-11-03T21:11:53.013 回答
1

最近有大量关于自动检测错误存储库中重复错误报告的研究。这基本上与您面临的问题相同。不同之处在于您使用的是二进制数据。它们是类似的问题，因为您将寻找具有相同基本模式的字符串，即使这些模式可能有一些细微的差异。直线距离算法在这里可能无法很好地为您服务。

这篇论文很好地总结了这个问题以及在其引文中已经尝试过的一些方法。

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

于 2010-11-03T14:59:14.857 回答