我想从C源代码生成程序依赖图(PDG)。我找到了说明其操作方法的论文,但都使用了商业化的CodeSurfer工具。

是否有任何免费工具或开源项目可以做到这一点?

最佳答案

Frama-C是一个基于a slicer for C programs的开源静态分析平台,基于程序依赖图的计算。

请注意,对用诸如C之类的真实编程语言编写的实际程序进行切片会涉及许多特殊情况和概念,这些情况和概念已在科学出版物中有所介绍。不过,我有信心,您不会找到比Frama-C的PDG计算更简单的东西,首先是因为它是唯一可用的(我知道)开放源代码,其次是因为任何其他处理C程序的PDG计算都将拥有解决相同的问题并引入相同的概念。

这是一个例子:

int a, b, d, *p;

int f (int x) {
  return a + x;
}

int main (int c, char **v) {
  p = &b;
  a = 1;
  *p = 2;
  d = 3;
  c = f(b);
}

命令frama-c -pdg -pdg-dot graph -pdg-print t.c生成点文件graph.main.dotgraph.f.dot,分别包含main()f()的PDG。

您可以使用dot程序通过以下方式漂亮地打印其中之一:dot -Tpdf graph.main.dot > graph.pdf
结果如下:

注意从节点c = f(b);到节点*p = 2;的边缘。声称对C程序有用的PDG计算必须处理别名。

另一方面,使用此PDG在标准“语句c = f(b);的输入”上进行切片的切片器将能够删除d = 3;,即使通过指针访问*p也不会影响函数调用。
Frama-C的切片器使用PDG指示的依赖性仅保留对用户指定的切片条件有用的语句。例如,命令frama-c -slice-wr c t.c -then-on 'Slicing export' -print会在下面生成精简程序,其中对d的分配已删除:
/* Generated by Frama-C */
int a;
int b;
int *p;
int f_slice_1(int x)
{
  int __retres;
  __retres = a + x;
  return (__retres);
}

void main(int c)
{
  p = & b;
  a = 1;
  *p = 2;
  c = f_slice_1(b);
  return;
}

09-04 09:51