函数调用图的静态构造
这是一个研究性项目。 以往的研究生已经基于LLVM开发有跨文件的C函数调用图构造器。进一步的研究点包括:
- 扩展已经有的跨文件的C函数调用图构造器,支持对C++程序的函数调用图构造
- 基于SOOT,构造Java或Android应用的方法调用图
动机与难点
在开发软件理解、软件测试相关的工具时,函数指针、C++/Java等的继承和反射等机制的使用提高了开发的难度:
- 函数指针机制允许通过指针来完成过程调用, 这种机制导致静态分析时无法唯一确定函数指针所指向的函数对象
- C++/Java等面向对象语言的继承会引起各种多态,这导致静态分析时难以唯一确定实例方法
o.m(...)调用在运行时实际调用的是哪个方法 - Java的反射机制允许将一个类、类的成员当成对象操作,这导致静态分析时难以确定对象实际代表的类或成员是什么
CallGraph是理解软件、构造多种软件分析和测试工具的基础。 利用CallGraph还可以用于按需定制大型代码,将相关的模块剥离出来进行打包发行。
已有的原型系统
最初的版本是由张维(2012级硕士研究生)在LLVM 3.3上,基于Clang 和LLVM 研发的跨文件的C 函数调用图构造器。
目前,正由2016级硕士研究生宁宇将其移植到在LLVM 3.9版本上可以编译、运行的版本。
依赖的软件包
功能
它能由用户指定的根函数出发,分析跨多个文件的C 源程序, 构造对应的函数调用图并以dot 文件格式输出。 所输出的dot 文件可以用Graphviz 工具转换成图形,以pdf、jpg 等文件形式保存。 函数调用图中的结点代表函数,其中包含该函数所在的源程序文件名及在文件中的行信息,边刻画了被调用函数 在调用者的程序文本中出现的次数。 能较精确地解析函数指针的轻量级函数指针分析算法。
研究核心
本项目的核心是在LLVM 中间表示(IR) 上,结合传统的不精确的快速指针分析方法,提出了一种轻量级的精确解析函数指针的函数指针分析算法。
适用范围
由于LLVM 中间表示层相对独立,理论上该工作可以扩展用于任何可以生成LLVM 中间代码的语言的程序的函数调用图构建,不过目前我们只测试了C 程序。