使用较旧调试版本中的符号来标记剥离的二进制文件(不精确的图形匹配)

Question

我有二进制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的观众都知道我应该从哪里开始？

Answer 1

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

对齐可执行代码

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

1. 将整个指令视为字符（这需要构建一个基本的反汇编器）
2. 完全忽略指令的地址部分
3. 减少删除（假设“第一个”文件是调试版本，我们预计该文件会更大）
4. 增加指令匹配的权重CALL，以及可能的其他“可靠”指令序列的权重。

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

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

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

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

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

使用完整的调用树

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

1. 提取给定函数调用的不同函数的列表
2. 将第一个被调用的函数标记为 1，将第二个被调用的不同函数标记为 2，等等。
3. 签名就是按照函数中调用顺序排列的函数标签序列。

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