7

我有二进制A，这是一个带有随附符号的调试版本——多年前构建的。我也有二进制B ，一个没有附带符号的发布版本，并且是更新的。我正在寻找将二进制 A 中的符号与二进制 B 中的潜在候选匹配的最有效方法。

鉴于调试版本要大得多（进行更多的输入验证，打印更多的东西stderr等）并且函数总是随着时间而变化，我认为尝试对各个函数进行指纹识别将浪费时间。

因此，我已经决定 - 完全凭空，所以我可能会叫错树 - 指纹函数的最佳方法是创建两个二进制文件的调用图并尝试匹配顶点（即职能）。

我已经做了一些预处理，所以我有以下数据结构：

# binary A
[[60, 60, 8734], # function 0 is called by functions 60 (twice) and 8734
 [193, 441, 505], # function 1 is called by functions 193, 441 and 505
 [193, 742],
 [23],  
 [21],  
 [21],  
 [26],  
 [26, 1508, 1509, 1573],  
 [24],  
 [25],
 ...] # (~10k functions)

# binary B
[[8999], # function 0 is called by function 8999
 [9016], # function 1 is called by function 9016
 [1126], 
 [7904, 7904, 7913], 
 [182, 336, 396, 396], 
 [9010], 
 [407], 
 [182, 632], 
 [20], 
 [24],
 ...] # (~10k functions)

需要注意的重要一点是，二进制A中的函数“0”和二进制B中的函数“0”之间没有对应关系。这些是我为每个二进制文件中的每个函数分配的任意 ID。

下一步是让我感到困惑的。我的算法很弱，我想不出一个聪明的方法来继续。我（非常有限）的理解是，为了解决这个问题，我想采用某种形式的不精确图形匹配。换句话说，哪一组映射 Ai -> Bi 将使两个调用图的相似性最大化？

鉴于二进制A中有额外的调试功能，并且程序随着时间的推移而发展的明显事实，可能没有完全匹配。理想情况下，我想要以下形式的输出：

[[(37, 0.998), (8432, 0.912), (442, 0.75)], # matching-ness of function "0" in binary A with function "37" in binary B is 0.998, second most likely candidate is function "8432" in binary B with score 0.912, etc.
 [(42, 0.973), (7751, 0.788)], # matching-ness of function "1" in binary A with function "42" in binary B is 0.973, second most likely candidate is function "7751" in binary B with score 0.788, etc.
 [(4579, 0.996), (123, 0.934)], 
 ...] # around ~10k mappings

实际上，如果我只需要一名候选人并且没有提供排名，我会很高兴，但可以梦想。

任何 SO-goers 都知道我应该从哪里开始？

4

2 回答 2

5

当然是一个有趣的问题，尽管我怀疑它很难解决。它似乎是有向图上近似图同构的一个实例。我没有找到太多的谷歌搜索，但这里有一些解决无向一般图的软件，这是一个更一般的情况，是 NP 难的。

对齐可执行代码

我认为您可以做的最实际的事情是忘记运行时信息，只需获取每个版本的可执行代码部分并使用全局对齐算法（例如Needleman-Wunsch，虽然确实存在更快但不太准确算法）在他们身上：

  1. 将整个指令视为字符（这将需要构建一个基本的反汇编程序）
  2. 完全忽略指令的地址组件
  3. 减重删除（假设“第一个”文件是调试版本，我们希望它更大）
  4. 提升指令匹配CALL，以及可能的其他“可靠”指令序列。

假设函数出现在可执行文件中的顺序没有太大变化（它不会有太大变化，除非优化版本使用了一些优化，使链接器将相互调用的函数放置在彼此附近），这应该给你一个很好的第一个近似值。

分配问题（二部最大匹配）

或者，如果你能找到一种方法（我的直觉表明它需要是一种迭代方法，类似于 PageRank 如何决定网页的价值）来“评分”f调试版本中的函数对应于的可能性优化版本中的函数g，那么是的，您可以使用图形匹配技术。在这种情况下，图的顶点将是两个版本中的所有函数，并且在调试版本的每个函数和优化版本的每个函数之间都会有一个加权边，权重由您的评分系统确定。

该图将是二分图，因为同一版本中的两个函数之间永远不会有边。这意味着它是Assignment Problem的一个实例，存在相当好的（而且不太复杂）算法。

但是，这里缺少的部分是确定每个配对权重的方法。一种近似的方法是构建一个向量，计算每个函数的直系子女、孙子女、曾孙子女等的数量。然后，您可以使用您喜欢的任何距离度量来比较这些向量。但我预计在这里这样做不会很好，因为我们已经预计调试版本包含比优化版本更多的函数调用。

使用完整的调用树

如果您可以访问两者的整个调用树，这将为您提供更多信息：在函数中进行的调用顺序，以及调用的确切层次结构的知识。然后，您可以通过仅使用后者来为每个函数构建一个“签名”：

  1. 提取给定函数调用的不同函数的列表
  2. 标记第一个调用的函数 1，第二个调用的不同函数 2，等等。
  3. 签名就是这个函数标签的序列，它们在函数中被调用的顺序。

现在，Levenshtein 距离可用于比较 2 个签名。为了以更多计算为代价获得更高的准确性，您可以使用一种变体，其中允许删除调试版本中最多 k 个不同的函数，对于一些小的 k（例如 k = 3），并采用最佳 Levenshtein 距离在所有此类“精简”版本中，附加了与删除的功能数量成正比的小惩罚。

于 2010-12-07T07:21:33.923 回答
1

如果你负担得起，IDA Pro + BinDiff。

于 2010-12-07T10:40:22.910 回答