linux - 我们如何比较两个程序的依赖关系图？

Question

这是一个示例程序依赖图。**

这是生成上图的代码。我想比较这些类型的两个图，有没有什么方法可以比较这些图的相似度百分比。我也在考虑比较图的图像以获得相似度百分比，请建议我该怎么做。

digraph cfg {
subgraph cluster_sum {
graph [label="sum"];
s1[label="i = 0;"];
s1 -> s2;
s2[label="sum_0 = 0;"];
s2 -> s3;
s3[label="i = x;"];
s3 -> s4;
s4[label="<loop>"];
s4 -> s6;
s6[label="if i <= y"];
s6 -> s8;
s6 -> s7;
s7[label="<break>"];
s7 -> s11;
s8[label="<enter block>"];
s8 -> s9;
s9[label="sum_0 -= i;"];
s9 -> s10;
s10[label="i ++;"];
s10 -> s4;
s11[label="<return>"];
}
subgraph cluster_main {
  graph [label="main"];
  s13[label="res = 0;"];
  s13 -> s14;
  s14[label="a = 2;"];
  s14 -> s15;
  s15[label="b = 5;"];
  s15 -> s16;
  s16[label="res = sum(a,b);"];
  s16 -> s17;
  s17[label="printf(\"%d\",res);"];
  s17 -> s18;
  s18[label="__retres = 0;"];
  s18 -> s21;
  s21[label="<return>"];
  }
  }

Answer 1

嗯，总的来说它是一个开放无解的？问题。您可以使用抽象解释评估这两个程序并比较结果。但我不认为你期待这个答案。

最简单的方法是将图形(可以使用 ocamlgraph 库在 OCaml 中读取)转换为规范化形式，其中删除所有句法差异(例如，所有变量都使用重命名通用命名方案或替换为正则表达式)，然后您可以根据您的比较函数比较结果图。

但这当然只是一个 hack。为了更复杂，你应该学习几门程序分析类(class)，写一篇论文，然后自己回答，一般来说它是无法解决的......但最终，你会写出类似BinDiff的东西。 .

什么比较两张图，那我觉得是更粗暴的hack。但通常的方法是进行 2D 卷积，这将返回平等的衡量标准。 OCaml fftw 库拥有您需要的一切。