LLVM中静态程序信息的过程间分析方法
2018-06-19莫培弘衷璐洁
莫培弘，衷璐洁
(首都师范大学 信息工程学院，北京 100048)
0 引 言
现代软件系统的复杂性越来越突出，程序的规模也越来越大，难以直观地了解程序的编码逻辑结构。过程间信息以及过程内信息能够反映软件系统中的程序编码逻辑，在对程序的理解和分析、软件的测试、调试和维护、编译优化、错误定位、bug查找、过程间数据流分析、回溯测试等软件工程领域中都有应用[1-3]，完整的过程间信息和过程内信息更好地辅助程序验证和程序调试[4,5]，提高程序分析的质量，增强对程序的理解。
程序分析方法分为动态分析方法和静态分析方法。其中，静态分析方法不需要运行待分析的程序就能获取程序可能执行的状态，有利于对程序进行自动化和快速分析。在大型项目中存在大量的过程间信息和复杂的过程内信息，通过静态分析可以快速地获取过程间信息和过程内信息。精确的过程内信息更好地提高静态分析的精度[6,7]。函数指针指向信息的准确获取对过程间信息分析的精度有着重要的作用[8,9]。完整的过程内信息和精确的过程间信息有助于代码阅读和分析人员在阅读和分析大工程或者开源代码时快速地了解程序的过程内结构和过程间的层次结构。
1 相关工作
1.1 有关研究
目前，对程序静态分析工作的研究比较活跃。针对过程间信息提取的问题，牟等[10]在函数调用路径的基础上获取测试用例优先级排序的问题，通过获取函数调用的路径，并利用调整算法实现动态调整测试用例的优先级排序。孙等[11]针对操作系统内核等大型软件的函数调用问题，通过RTL工具对源码生成的中间信息提取函数调用信息，生成函数调用图。王等[12]针对多语言函数调用图的构建工具重用率低和实现复杂的问题，通过GNU编译器集合(GCC)的插件在GCC中间表示层上提取函数调用关系并转化成图形描述语言，获取函数调用图。
1.2 现有工具
现有的过程间分析工具存在函数调用信息提取不够准确和处理库函数调用信息不够完善的问题。
Source Insight[13]是一个项目向导的程序编辑器和代码浏览器，具有对引用树(reference tree)，类继承图(class inheritance diagram)和调用树(call trees)等程序分析信息的可视化支持，并可以生成函数调用图。
CodeViz[14]是一个C源码静态分析工具，针对C程序生成可视化的函数调用图，通过给GCC打补丁，在编译源文件时dump出函数调用信息，再通过Perl脚本提取函数调用信息。
Cflow[15]是一个C源码程序静态分析工具，它可以产生前向和反向的两种函数调用图，直接对源码进行分析，生成一个C程序的函数调用信息的外部引用集合。
CallTree[16]是一个C源码静态调用树生成器，通过分析C源码，提取函数调用信息。
但是上述文献[10-12]中均不能获取函数指针指向的信息，存在函数调用信息获取不够完善的问题；Source Insight和CodeViz不能获取函数指针指向的信息；CallTree不能获取函数指针指向的真实信息；CodeViz、CallTree以及Cflow不能完善地处理库函数调用信息。综上，在现有过程间信息获取的工作中存在的主要问题有以下两点：
(1)存在不能获取函数指针指向的真实信息；
(2)存在不能完善地处理库函数的调用信息。
2 LLVM编译框架
2.1 LLVM
LLVM(low level virtual machine)是一个被广泛使用的开源编译器框架，它基于静态单赋值(static single assignment，SSA)的编译策略，能同时支持静态和动态的任意编程语言的编译目标。LLVM有着丰富的工具链和用户可自由定义的LLVM Pass等，是一个模块化、可重复使用的编译器和工具技术的集合。它由不同的子项目组成，许多项目已经在各种商业和开源项目中得到广泛应用，并被应用于学术研究[17,18]。
2.2 LLVM IR
IR是LLVM的中间表示(intermediate representation，IR)，是LLVM编译框架的一个重要组成部分。IR中包含丰富的程序分析信息[19]，由模块、全局变量、函数以及连接类型等信息组成。其中，这些程序信息中包含过程内信息和过程间信息。
LLVM自定义了一组独特的指令模式，并为用户提供了大量的API接口和可复用的库，通过编写LLVM Pass可以为用户从IR中获取程序分析信息带来方便。针对上述函数指针指向信息获取不够准确和库函数调用信息处理不完善的问题，提出一种LLVM中静态程序信息的过程间分析方法(control-flow inter-procedural call-graph，CFICG)。
LLVM IR文件由LLVM指令组成，本文获取过程内信息和过程间信息，需要对ret、br、switch，call，store以及load等LLVM指令等进行解析，进而提取本文需要的静态程序分析信息。表1是代表性的LLVM指令，如终结指令：通过获取br指令，可以获取当前基本块的后继信息；通过switch指令获取基本块的分支信息，解决控制流的分支问题。
表1 代表性LLVM指令
3 以过程内信息和过程间信息的提取为分析示例
LLVM IR文件中包含指针、数据流、过程内以及过程间等的信息。通过提取本文需要的过程内和过程间的信息，获取CFICG信息。CFICG表示为
CFICG=
其中，cf
3.1 过程内信息提取的分析
关于过程内信息的提取，每一个函数都由一个或若干个基本块组成，一个基本块又由一条或者若干条语句组成，在LLVM IR中以switch、ret、br等终结指令区分过程内基本块的信息，如图1所示。
图1 过程内信息分析
以上述图1(a)中的main函数为例进行说明(Li中，L表示行，i表示第几行)。main函数有4个基本块，分别如图1(a)中4个实线方框所示；main函数中有两条过程内路径，分别是L7->L9->L14和L7->L11,L12->L14。
图1(b)为图1(a)对应的LLVM IR，源码中的基本块语句转化成LLVM中的指令，如图1中虚线箭头对应的方框，在图1(b)中实线方框前的虚线方框即为当前基本块的名称，图1(b)中main函数分别有entry，if.then，if.else和if.end这4个基本块，其过程内的路径分别为entry->if.else->if.end和entry ->if.then ->if.end。
每一个基本块由多条LLVM指令组成，并以br，ret等终结指令划分基本块。如图1(b)中main的entry由{L9，L10，L11，L12}组成，L12中实线箭头表示为图2，entry以br指令结束一个基本块并由label指令指明当前基本块的后继基本块的个数和名称，一个label指令对应一个后继基本块，entry基本块的br指令中存在两个label指令，即存在两个后继的基本块。通过准确地获取过程内信息并组成与源码对应的过程内信息，解决过程内信息的复杂性与多样性地问题。
图2 基本块信息获取
3.2 过程间信息提取的分析
函数调用是一个有向图，这里先将其表示为CallGraph(V,E)，V表示函数调用中所有函数节点的集合，E表示节点之间的边，并满足E⊆V×V。
表示如下：
其中，VE表示函数调用之间的关系集合；functionSet表示函数的集合；F(a,b)表示函数a到函数b之间有一条路径。
过程间信息提取需要区分直接函数调用信息和函数指针指向信息，在LLVM 的指令中直接函数调用与函数指针都以call指令的形式表示[19]，如图3所示。为区分直接函数调用和函数指针，需要做进一步的分析，即通过函数所在的文件、函数名、参数类型和参数个数并结合定值-引用(def-use)方法和指针分析方法(load和store指令)来确定函数指针指向的信息。
图3 过程间信息分析
图3(a)中假设EditFunc函数与FileFunc函数已事先定义好，由函数指针*funcptr1，*funcptr2和4个非函数指针的函数FileFunc，EditFunc，foo和main组成，图中实线箭头表示函数调用的过程，虚线箭头表示函数指针指向的真实函数，main函数的调用路径，分别是main->foo->funcptr1和main->funcptr2，这两条调用路径上都有函数指针。
获取函数指针指向的真实信息需要获取函数指针指向的真实函数，即funcptr1指向的真实函数是FileFunc，funcptr2指向的真实函数是EditFunc, 得出main中的两条真实函数调用路径，分别为main-> foo->FileFunc和main->EditFunc。
图3(a)源码转化成图3(b)的LLVM 指令，对图3(b)中main的过程间信息分析，存在两条调用路径，即图中细虚线箭头表示的调用路径和细实线箭头表示的调用路径。细虚线箭头调用信息表示为图4(a)所示，main通过call指令调用foo函数，foo通过call调用 FileFunc函数。
图4 main调用信息的路径
第二条函数调用信息的路径，即图中细实线箭头所示，表示为图4(b)，main函数通过call指令调用“%1”，“%1”的形成过程，首先，store指令将EditFunc函数存储到函数指针funcptr2中，然后load指令将funcptr2加载到“%1”，最后main函数通过call指令调用“%1”，最终获取函数指针指向的真实函数EditFunc。
上述的两条函数调用路径中都存在函数指针信息，获取准确的过程间信息需要做以下分析：
(1)区分直接函数调用信息与函数指针指向信息；
(2)分析函数指针指向的信息存在的两种情况：①只存在call指令形式的函数指针信息；②存在store、load和call指令的函数指针信息。
直接函数调用和函数指针都以call指令表示，通过对函数所在的文件、函数名、参数类型和参数个数等进行分析获取函数指针指向的信息。针对函数指针的第二种情况，需要对store和load进行指针分析，再对call进行指向分析获取函数指针指向的信息。
最后，结合获取的过程内信息和过程间信息，组成CFICG信息，如图5所示。
图5 main的CFICG信息
4 过程间分析方法(CFICG)
针对上述过程间存在不能获取函数指针指向的真实信息和不能完善地处理库函数调用信息的问题，提出一种在LLVM 中提取静态程序信息的过程间分析方法(CFICG)，其结构框架如图6所示。首先输入LLVM IR文件，通过上述过程间信息提取的分析方式，编写LLVM Pass提取过程内信息和过程间信息，形成程序执行的所有可能过程，并解析过程内信息和过程间信息，最后生成过程内信息和过程间信息的文本。解决过程间的函数指针指向信息不够准确和库函数调用信息处理不完善的问题以及过程内信息的复杂性与多样性的问题。
图6 CFICG框架
4.1 算法描述
为了获取过程内信息和过程间信息，提出在LLVM中静态程序信息的过程间分析方法(CFICG)，CFICG算法表示为getProInfo()，其由3部分组成，分别是过程内信息提取算法(getIntra())，直接函数调用信息提取算法(getCusCall())和函数指针指向信息提取算法(getPtrCall())，它们的具体算法描述分别如下所示。
CFICG的算法描述如下：
CFICG的算法描述
输入：IR
输出：过程内信息、过程间信息
getProInfo(IR)
(1)getIntra(IR)//提取过程内信息算法
(2)getCusCall(IR)//提取直接函数调用信息算法
(3)getPtrCall(IR)//提取函数指针指向信息算法
CFICG算法包括3部分：过程内信息提取算法、直接函数调用信息提取算法和函数指针指向信息提取算法，分别是算法1、算法2和算法3，算法1、算法2和算法3的输入都是LLVM的IR，输出分别是过程内信息、直接函数调用信息和函数指针指向信息。
4.2 过程内信息提取的算法描述
首先获取每一个函数的每一个基本块，然后获取每一个基本块的终结指令，再根据终结指令确定基本块的后继，重复上述步骤，依次获取，直到每一个函数执行完毕。其算法如下：
算法1：过程内信息提取的算法描述
输入：IR
输出：过程内信息
getIntra(IR)
(1)forbbin func do //遍历函数获取基本块
(2)br←branch(bb); //获取br指令
(3) if unconditional_branch(br) then
(4)sets←successors(bb);//无后继的基本块
(5) else
(6)sets_n←successor(bb);//有后继的基本块
(7) end if
(8)end for
4.3 过程间信息提取的算法描述
本文的过程间信息分为直接函数调用信息和函数指针指向信息，其中直接函数调用信息包括库函数调用信息和非库函数调用信息。
4.3.1 直接函数调用信息提取的算法描述
从LLVM指令中获取call指令，并通过call指令获取直接函数调用信息，对获取的函数进行库函数和非库函数的区分，最后得到直接函数调用信息。其算法如下：
算法2：直接函数调用信息提取的算法描述
输入：IR
输出：直接函数调用信息
getCusCall(IR)
(1)forfuncin mod do //遍历模块获取函数
(2) forbbin func do //遍历函数获取基本块
(3) foriin basicbk do //遍历基本块获取指令
(4)setinstrc←i;
(5) if(call←instrc) //获取call指令
(6)setfunct←call; //获取函数调用信息
(7)setfunct←funct; //获取非库函数调用信息
(8) end if
(9) end for
(10) end for
(11) end for
4.3.2 函数指针指向信息提取的算法描述
通过解析call指令和call的函数，若不是函数指针则不做进一步分析，直接获取调用的函数信息；若是函数指针则进一步分析，通过函数参数传递的个数和函数传递的实参获取函数指针指向的信息；若是存在store和load指令则进行指针分析，获取调用的函数信息，然后通过对函数的形参和实参分析，获取函数指针指向的真实信息；当一个函数调用分析完后定值-引用(def-use)分析下一个被调用的函数，再继续重复上述的执行过程，直到所有的函数都分析完毕为止。其算法描述如下：
算法3：函数指针信息提取的算法描述
输入：IR
输出：函数指针的指向信息
getPtrCall(IR)
(1)forbbin func do
(2) foriin basicbk do
(3)cur_inst=i;
(4) if(!call←cur_inst)
(5)setfunc←call;//获取函数调用信息
(6) else
(7)setnum←getNumArg;//参数个数
(8)setAgrOperand←num;//实参
(9) end if
(11)setfunc←store;//获取函数调用信息
(12)setfunc←load;//获取函数调用信息
(13) end if
(14) forargin func do //遍历函数获取参数
(15) if(arg==ArgOperand)//获取形参
(16)setfunct←call;//函数指针信息
(17) end if
(18) end for
(19) getFuncChain();//函数调用链信息获取
(20) end for
(21)end for
算法3的重要部分在对函数指针指向信息的分析和对过程间信息的def-use分析[20,21]上。在分析函数指针调用信息的部分，通过分析确定函数指针，再通过函数指针传递的实参与形参确定函数调用信息指向的真实函数；def-use分析，通过函数的定值，再由函数调用来确定哪个函数被哪个函数引用。其表示形式如下：
(1)def(func2)={func1|函数func1定值了函数func2}
表示函数func2的定值函数集def(func2)由定值函数func2的所有函数组成。
(2)use(func2)={func1|函数func1引用了函数func2}
函数func2的引用函数集use(func2)由引用函数func2的所有函数组成。
(3)use(func2)={func1|函数func1引用了函数func2}
函数func2的定值-引用函数集def-use(func2)由定值函数func2的所有引用的函数组成。
如：main=foo1->foo2->foo3->foo4；
则：def-use(main)={foo1，foo2，foo3，foo4}。
针对过程间信息的处理，首先根据函数的定值，然后通过确定main函数调用时引用了哪个函数，再判断引用的函数是否为函数指针；如果是，则获取函数指针变量的信息，通过分析函数指针的实参(称为定值)被哪个函数指针指向的函数引用了，最终获取函数指针指向的真实函数信息。即获取函数调用的定值-引用算法表示为getFuncChain()。
getFuncChain()算法描述的流程具体如下：
算法4：函数调用链算法的描述
输入：IR中的函数
输出：函数调用链
getFuncChain(func1,func2){
(1)从main函数的func1函数开始分析.
(2)分析函数列表中的每一个函数fun;
(3) if(fun是函数变量)
(4) 则def(fun),use(fun)中的函数,def(func)|函数变量func∈use(fun)中的函数是func2中函数.
(5) else if((f为函数自变量|f∈def(fun)或f∈(def(def(fun)…)或f∈use(fun))
(6) 则def(fun),use(fun)中的函数是func2中的函数.
(7) getFuncChain(func11,func22)递归获取下一个引用的函数.
(8) 生成函数调用链.
(9) }
5 实验结果与分析
本文在LLVM下静态分析提取C/C++程序的过程内信息和过程间信息，首先通过与现有工具Source Insight、CallTree以及Cflow的对比来验证本方法过程间信息的提取精度；再通过开源码进行实验验证本方法的实用性。
5.1 实验环境
本文的实验环境为，硬件环境：Intel(R) Core(TM) i7-4790 CPU @ 3.60GHz，3GB内存；软件环境：Ubuntu 15.04，LLVM 3.7.0；开发工具：Sublime Text 3，vim；编程语言：C/C++，python。
5.2 实验验证
本文的实验验证主要从两方面进行验证：
(1)验证本文提出的过程间分析方法对过程间信息提取的精度;
(2)验证本文提出的过程间分析方法的实用性。
5.2.1 验证CFICG提取过程间信息的精度
图7(a)中函数add_ptr、mul_ptr以及test1_all为函数指针，本文利用graphviz[22]工具绘制函数调用图，图7(b)是过程间分析方法(CFICG)与现有分析工具的对比结果。根据图7的实验结果可知，Source Insight可以获取直接函数调用信息，不能获取函数指针指向的信息；CallTree可以获取函数调用信息，无法获取函数指针指向的真实信息；Cflow可以获取函数指针指向的真实信息，不能解析、区分非库函数调用与库函数调用的信息(如scanf函数)；本文提出的过程间分析方法获取了函数指针指向的真实信息以及识别和区分非库函数和库函数调用的信息并可以直观地观察在哪个基本块内发生了函数调用，如图7(b)的实验结果对比。
图7(b)中CFICG的函数add、mul、test1和test2都只有1个基本块entry；all有4个基本块分别是entry、if_then、if_else以及if_end，在if_then内调用了test1(函数指针test1_all指向test1)，在if_else内调用了test2；函数main有5个基本块分别为entry、sw_bb、sw_bb2、sw_bb3以及sw_epilog，即sw_bb对应源程序的第1个case，并调用add(函数指针add_ptr指向add)，sw_bb2对应源程序的第2个case，并调用mul(函数指针mul_ptr指向mul)，sw_bb3对应源程序的第3个case，并调用了all，再以一个sw_epilog作为最后1个基本块结束整个函数。
图7 CFICG与现有工具实验结果
表2用于统计过程间分析方法(CFICG)和现有工具对图7的C源码获取程序中实际被调用函数与实验获取被调用函数的个数进行对比，统计出图8的函数调用信息提取的覆盖率((覆盖率=(实验获取被调用函数个数/程序中实际被调用函数个数)×100%))，表2中reCal表示程序中实际被调用函数个数，ExO表示实验获取被调用函数个数，IdCo表示函数调用提取的覆盖率，统计结果见表2。
表2 图7中示例代码函数调用信息的统计结果
图8 函数调用信息获取的覆盖率
5.2.2 验证CFICG的实用性
通过测试开源码，来验证本文提出的过程间分析方法(CFICG)的实用性。实验结果见表3。
由于处理源码的规模较大，为了体现过程间分析方法(CFICG)的检测速度，进行了时间开销的统计。如图9所示。
同时，以aget开源码为示例给出实验结果的图示，并放大一小部分以便了解，如图10所示。
实验结果表明，本文提出的过程间分析方法(CFICG)提取了过程内信息的路径流向，在过程间信息提取中函数指针指向信息提取更为精确和库函数调用信息处理更为完善，并且能结合过程内信息分析出函数调用信息发生在哪个基本块内，比上述工具更准确地体现出函数调用发生的位置。更精确地获取函数指针指向的真实信息和更完善地处理库函数调用的信息，提高了静态程序分析过程间的精度；对开源码进行了实验，验证本文提出的方法的实用性并且在时间开销上也不是很大；同时，有助于代码阅读和程序分析人员更清晰、更好地理解程序结构以及程序的设计流程。
表3 源码实验结果
图9 开源码获取函数信息的时间开销
6 结束语
本文针对C/C++静态程序分析，提出一种在LLVM平台下静态程序信息的过程间分析方法(CFICG)，通过对过程内信息和过程间信息的提取，解决了过程间信息获取中函数指针指向信息不够准确的问题以及库函数调用信息处理不完善的问题。实验结果表明，本文提出的静态程序分析方法(CFICG)支持C/C++程序过程内和过程间的信息提取，更好地处理库函数调用信息并更为准确地获取函数指针指向的真实信息，并且具有实用性。
图10 aget实验结果
参考文献：
[1]Ohmann P,Liblit B.Lightweight control-flow instrumentation and postmortem analysis in support of debugging[C]//IEEE/ACM 28th International Conference on Automated Software Engineering,2013:378-388.
[2]ZONG Fangfang,HUANG Hongyun,DING Zuohua.Software fault location based on double-times-locating strategy[J].Journal of Software,2016,27(8):1993-2007(in Chinese).[宗芳芳,黄鸿云,丁佐华.基于二次定位策略的软件故障定位[J].软件学报,2016,27(8):1993-2007.]
[3]LI Zhoujun,ZHANG Junxian,LIAO Xiangke,et al.Survey of software vulnerability detection techniques[J].Chinese Journal of Computers,2015,38(4):717-732(in Chinese).[李舟军,张俊贤,廖湘科,等.软件安全漏洞检测技术[J].计算机学报,2015,38(4):717-732.]
[4]Fittkau F,Finke S,Hasselbring W,et al.Comparing trace visualizations for program comprehension through controlled experiments[C]//IEEE 23rd International Conference on Program Comprehension,2015:266-276.
[5]Sui Y,Xue J.SVF:Interprocedural static value-flow analysis in LLVM[C]//Proceedings of the 25th International Confe-rence on Compiler Construction.New York:ACM,2016:265-266.
[6]Tice C,Roeder T,Collingbourne P,et al.Enforcing forwar-dedge control-flow integrity in GCC & LLVM[C]//23rd USENIX Security Symposium,2014:941-955.
[7]Niu B,Tan G.Modular control-flow integrity[J].ACM SIGPLAN Notices,2014,49(6):577-587.
[8]Wang P,Yang J,Tan L,et al.Generating precise dependencies for large software[C]//4th International Workshop on Managing Technical Debt.IEEE,2013:47-50.
[9]Padhye R,Khedker U P.Interprocedural data flow analysis in soot using value contexts[C]//Proceedings of the 2nd ACM SIGPLAN International Workshop on State of the Art in Java Program Analysis,2013:31-36.
[10]MOU Yongmin,LI Huili.Test case prioritization based on function calling paths[J].Computer Engineering,2014,40(7):242-246(in Chinese).[牟永敏,李慧丽.基于函数调用路径的测试用例优先级排序[J].计算机工程,2014,40(7):242-246.]
[11]SUN Weizhen,DU Xiangyan,XIANG Yong,et al.CG-RTL:A RTL-based function call graph generator[J].Journal of Chinese Computer Systems,2014,35(3):555-559(in Chinese).[孙卫真,杜香燕,向勇,等.基于RTL的函数调用图生成工具CG-RTL[J].小型微型计算机系统,2014,35(3):555-559.]
[12]WANG Yagang,XU Chenghua.Construction of function calls relationship graph for multi-language source code[J].Journal of Xi’an University of Posts and Telecommunications,2013,18(6):75-79(in Chinese).[王亚刚,徐成华.多语言源程序函数调用关系图的生成方法[J].西安邮电大学学报,2013,18(6):75-79.]
[13]Source Dynamics Inc:Source insight version 3.5[EB/OL].[2016-06-07].https://www.sourceinsight.com/doc/v3/ManualTOC.htm.
[14]Petersenna:CodeViz:A CallGraph visualiser [EB/OL].[2015-07-23].https://github.com/petersenna/codeviz.
[15]Ruda:GNU cflow[EB/OL].[2015-10-23].http://rudix.org/packages/cflow.html.
[16]Czaber:callTree[EB/OL].[2016-07-26].https://sourceforge.net/projects/calltree/.
[17]LLVM Team.The LLVM compiler infrastructure[EB/OL].[2017-03-13].http://llvm.org/.
[18]Lopes B C,Auler R.Getting started with LLVM core libra-ries[M].Birmingham:Packt Publishing Ltd,2014:219-284.
[19]LLVM Team.LLVM language reference manual[EB/OL].[2015-09-01].http://releases.llvm.org/3.7.0/docs/LangRef.html.
[20]Wei F,Roy S,Ou X.Amandroid:A precise and general inter-component data flow analysis framework for security vetting of android apps[C]//Proceedings of the ACM SIGSAC Conference on Computer and Communications Security.New York:ACM,2014:1329-1341.
[21]Jin W,Cohen C,Gennari J,et al.Recovering c++ objects from binaries using inter-procedural data-flow analysis[C]//Proceedings of ACM SIGPLAN on Program Protection and Reverse Engineering Workshop.New York:ACM,2014:1.
[22]John Ellson:Graph visualization tools[EB/OL].[2017-01-04].https://github.com/ellson/graphviz/releases.
