algorithm - 使用旧调试版本的符号来符号化剥离的二进制文件(不精确的图形匹配)

Question

我有二进制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。

下一步让我感到困惑。我的算法很弱，我想不出一个聪明的方法来进行。我(非常有限)的理解是，为了解决这个问题，我想使用某种形式的 inexact graph matching .换句话说，哪一组映射 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 都知道我应该从哪里开始？

Answer 1

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

对齐可执行代码

我认为你能做的最实际的事情就是忘记运行时信息，简单地获取每个版本的可执行代码部分并使用全局对齐算法(例如 Needleman-Wunsch ，尽管确实存在更快但不太准确的算法)在他们身上:

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

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

分配问题(二分最大匹配)

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

此图将是二分图，因为同一版本中的 2 个函数之间永远不会有边。这意味着它是 Assignment Problem 的一个实例，为此存在非常好的(并且不太复杂)算法。

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

使用完整的调用树

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

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

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