C程序中的内存泄漏机制分析与检测方法设计*

张 静，黄志球,2，沈国华,2，喻垚慎，艾 磊

(1.南京航空航天大学计算机科学与技术学院， 江苏 南京 211106; 2.南京航空航天大学高安全系统的软件开发与验证技术工业和信息化部重点实验室,江苏 南京 211106)

1 引言

内存泄漏[1]是程序运行时资源泄漏的一种形式，通常在程序执行不适当的内存分配和释放操作时发生，是指由于疏忽或错误造成程序未能释放已经不再使用的内存，导致潜在的安全隐患。每个物理系统都有一个较大的内存量，如果内存泄漏没有被及时终止，会造成难以估计的损失，如内存耗尽[2]、程序崩溃[3]、系统故障、信息泄漏[4]等。例如，2017年的Cloudflare解析器bug导致内存泄漏事件中，泄漏的内存包含了隐私信息，其中很明显有一个是用于在Cloudflare机器之间进行安全连接的私钥，且这些隐私信息还会被搜索引擎缓存。2月13日到2月18日期间，通过Cloudflare的每3 300 000个HTTP请求中约有1个可能导致内存泄漏(约为请求的0.000 03%)。因此，针对内存泄漏检测的研究一直是一个热门的课题[5,6]。

C语言常用于编写安全关键软件，然而其中存在的内存泄漏缺陷一直难以被检测。在支持自动垃圾回收的语言(如Java)中，程序显式地申请内存，但不需要显式地释放。但是，C语言由于缺乏垃圾自动回收机制，导致发生内存泄漏的概率要比Java、C#等大得多，一旦发生问题，后果也更为严重，一般的软件测试方法无法及时发现程序中可能存在的内存泄漏。堆[7]是操作系统所维护的一块特殊内存，用于程序的内存动态分配。C语言使用malloc从堆上分配内存，使用free释放已分配的对应内存。通过分析程序源码可知，程序员经常使用指针变量直接或者间接地对内存单元进行操作，使得这些动态内存单元之间存在着复杂的指向关系，例如，某个内存单元可能被多个指针变量或其他内存单元引用[8]。随着软件规模的增加，指向关系更为复杂，申请和释放操作可能不在一个函数内，所以检测C程序中已经申请的内存单元最终是否被释放非常复杂。目前检测内存泄漏的方法主要分为动态测试和静态分析。

动态测试是在程序执行的过程中，根据内存的实际变化来判断是否发生泄漏，实时动态检测，记录程序动态分配的内存资源和释放信息，检测的泄漏点精确，不存在太多误报的情况。现有的动态测试工具例如Purify[9]和Valgrind[10]，自动化程度高且定位准确。但是，动态测试存在局限性，首先是难以保证代码覆盖的全面性，有的内存泄漏不易触发，容易发生漏报的情况，因此需要依赖高质量的测试用例[8]；其次动态测试的代价比较大，对硬件的要求高；最后，由于动态测试发生在软件开发后期，此时发现缺陷和修改缺陷的成本更高。

静态分析技术是软件开发中十分有效的质量控制方式之一，其分析工具具有灵活的使用方法，根据检测技术原理，用户可以定制最佳的检测方案。作为一种检测效率高、安全性高的软件程序检测方法，静态分析技术受到越来越多的软件开发人员的重视。静态分析的主要对象是源程序，其中含有大量设计信息、逻辑信息，同时也含有程序异常的信息。通过扫描源程序，可以从中提取方法调用关系、各模块间数据交互关系等设计信息，检测程序的控制流和数据流结构，从逻辑的角度对程序进行分析，更全面地检测出程序中存在的内存泄漏，因此静态分析是检测内存泄漏必不可少的一种检测方式。

与动态检测相比，静态分析能够遍历程序中的每个分支，覆盖到程序源码中所有可能路径，从而找出潜在的缺陷。Maxwell等[11]提出了基于图的内存泄漏检测方法，用图对动态内存建模，将堆内存进行图化，然后挖掘图中的信息，针对C/C++程序中基于指针和动态内存的数据结构进行有效的缺陷检测。斯坦福大学的Heine等[12]介绍了基于流敏感和上下文敏感检测算法的静态分析工具，每个对象有且只有一个所有权指针，对所有权约束进行求解并将其不一致性判定为潜在的内存泄漏，Xie等[13]提出了一种上下文敏感和路径敏感的算法，通过显式内存管理来检测程序中的内存泄漏，使用布尔约束表达分析。Fastcheck[14]是一个常用静态分析工具，其检测思想是基于保护值流分析，通过跟踪内存空间分配点到释放点的流向，判断所有的路径是否有且只有一个源-聚对。该方法是基于统一的指向别名分析，使用等价类方法将内存划分成不相交的区域。

基于上述分析，C程序的内存泄漏静态分析研究是具有重要现实意义的。尽管静态分析已经取得了一定的研究进展，但现有的检测方法仍存在不足的地方。随着代码规模的增长，实用的内存检测方法需要可扩展性，在保证检测效率的同时也需要保证检测的准确性。然而现有的方法大都受限于准确性和可扩展性，例如稀疏值流分析SVFA(Sparse Value-Flow Analysis)[15]是目前内存泄漏检测相对准确且高效的技术，但是，由于缺乏路径敏感性，还是不可避免地会引入误报。但是，通过遍历控制流图同时使用路径敏感分析来实现高精度检测的方法，其可扩展性容易受限，尤其是分析代码规模大的程序时代价太高。

为了在查找精度和效率上达到平衡，本文针对广泛应用于内存泄漏的SVFA技术缺乏路径敏感的问题，通过结合控制流信息引入路径敏感性，来提高检测准确性。本文提出了一种基于指针分析构建路径敏感的值流约束检测内存泄漏的方法，简称PACV(Pointer Analysis and Control-flow Value Guard)研究方法。

2 内存泄漏机制分析

从动态内存管理的角度，可将一个C程序内存空间抽象为2个空间：工作空间和自由空间。程序运行过程中,自由空间中有可供申请的动态内存，工作空间可以申请其中的内存块，通过全局数据区、栈区和常量区的指针变量进行索引。这2个空间之间有2种内存迁移的方向：(1)自由空间到工作空间：通过内存分配函数将内存块从自由空间迁移到工作空间中；(2)工作空间到自由空间：通过内存释放函数将内存块释放到自由空间中。在动态空间中，若存在己分配的内存块没有释放却失去了访问路径，则无法再去访问它们，这些内存块就是被泄漏的。如图1所示，m5释放回到自由空间中，m1和m8为泄漏内存。

从程序执行的角度，在任何程序执行路径中，在分配点(source)创建的每个对象最终必须至少到达一个释放点(sink)。

2.1 场景分析

通过分析2018年1月至今CVE(Common Vulnerabilities and Exposure)[16]中公布的63条内存泄漏相关漏洞信息，可将其分为5种常见场景。

场景1内存管理关键字或函数使用不当。

从2018年1月至2019年4月，CVE中就有3条相关漏洞信息，由于程序结构复杂、人员疏忽导致使用了错误的释放方法。内存分配和释放是相互匹配出现的，成对使用这些关键字或函数是内存动态分配使用的基本原则，调用了内存分配函数却没有调用释放函数会导致泄漏。此场景属于最基本的场景，针对这种类型的内存泄漏检测也相对简单，通常是在函数入口处初始化指针内存的分配情况，在函数出口处对比函数内的分配和释放操作来判定是否存在已经分配内存的指针没有被释放的情况[17]。

场景2程序逻辑缺陷。

虽然程序中分配和释放函数成对出现，并未出现错配或者漏配的情况，但由于程序本来的一些缺陷，仍会导致内存泄漏。函数在程序入口处分配了内存，但在最后释放之前，分支语句内的代码提前返回发生异常，那么就引发了内存泄漏。若函数里的逻辑非常复杂，或者异常情况不是必现，那么查找内存泄漏点则更加困难。

场景3指针重新赋值。

指针变量p和np分别被分配了5字节的内存。如果程序需要执行赋值语句p=np，指针变量p被np指针重新赋值，导致p之前所指向的内存位置变成了孤立的内存。因为没有指向该内存的引用，它无法进行释放，从而导致5字节的内存泄漏。

场景4错误的内存释放。

假设有一个指针变量p，它指向一个5字节的内存位置。该内存位置的第2字节又指向某个新的动态分配的5字节的内存位置。如果通过调用free来释放了最初的内存块，则新分配的内存变成了孤立的内存，导致了内存泄漏。

场景5返回值的错误处理。

某些函数会返回对动态分配的内存的引用，主函数中调用f函数，但未处理该内存位置的返回地址导致f函数所分配的5字节的内存块丢失，造成内存泄漏。

2.2 原因分析

根据上述场景分析可知，内存泄漏与指针及其关联内存操作相关，因此根本原因分析应从内存块与指针的生命周期展开。内存块的生命周期可用3种方式表示：

(1)引用：当没有对内存块的引用时，堆内存块的生命周期结束。

(2)可达性：无法再从程序变量进行访问，堆内存块的生命周期结束。

(3)活跃度：在最后一次访问该内存块之后，堆内存块的生命周期结束。

其中，可达性在控制流分析中更为直观，若内存块的生命周期结束而指针不可达，则程序中发生内存泄漏。除了内存块生命周期外，还需分析指针的生命周期。图2表示C程序中指向堆内存的指针p的生命周期，显示了指针p从被声明到被释放的全部过程。实线箭头表示程序中正确执行的顺序，虚线箭头表示可能导致指针p引用的内存块上发生泄漏的所有情况。例如，虚线箭头5表示指针p在分配内存块前未被初始化，虚线箭头6表示指针p在被访问之前未被分配内存块，虚线箭头7表示指针p释放内存块之前未被分配内存块。由此可见，若程序或运行时系统在堆内存块的生命周期结束时没有指针回收其内存，会造成内存泄漏。

Figure 2 Pointer liveness图2 指针生命周期

因此，检测内存泄漏本质上是分析相应内存块的生命周期在控制流图的每个分支中结束时是否释放了内存指针。

3 PACV检测分析

本节提出PACV用于检测C程序的内存泄漏，工作流程分为2个阶段：路径敏感的值流信息构建与基于值流约束的泄漏检测。首先基于指向信息构建值流，然后利用值流约束检测内存泄漏，最后通过程序中分配位置和释放位置的指针以及内存块的生命周期信息对泄漏对象进行验证。

3.1 基于指针分析的值流构建

指针分析[18]通过解析变量的读写信息，分析出变量在程序运行时可能指向的对象集合，得到被分析程序在运行时指针的指向信息[19]。

本小节将程序抽象为一组函数Fun、一组变量V和一组语句S，据此对C程序进行抽象模型描述，如下所示：

s∷u=v|u=malloc(n)|u=*v|*u=v|

free(u)|s;s|if(Cond) thenselses′

该模型代表了C语言中内存操作的最简语句，其中语句s包含了赋值语句(u=v,u=*v,*u=v)、内存分配语句(u=mallco(n))、内存释放语句(free(u))，其中内存分配语句malloc(n)表示一般情况。

通常，指针分析描述以下4个集合中的元素之间的关系：

(1)语句集合S，主要包含指针变量的集合。其中Snull表示指针变量为NULL，该指针变量指向未被分配的内存块。

(2)内存位置集合M，它代表了由赋值语句生成的对象。

(3)指针映射集合T，在分析程序语句的过程中动态生成，反映了程序中的指针和内存地址之间的映射关系[20]。

(4)指针域的集合F。变量v通过指针域构成指向关系，表现为被指向的内存结点的地址存储在指向的内存结点中[8]。

根据集合元素之间的分析结果，描述程序中赋值语句产生的变量和对象之间的指向关系，如图3所示。

(1)图中结点包括指针结点x和y，内存对象结点o1和o2，以对象生成语句所在行号命名。

(2)t1表示从指针变量结点到内存对象结点o1的映射，表示在运行时可能访问内存对象结点o1。

(3)由x=y的赋值语句，从内存对象结点o1到o2的边，表示o1的指针域可能指向o2[21]。

Figure 3 Point-to graph图3 指向图

若存在指针变量z指向内存对象结点o，且有赋值语句t=z，则z与内存对象结点o存在间接指向访问关系。直接指向关系和间接指向关系共同组成程序中完整的指向关系。通过计算指向集合的传递闭包，可以获得完整的指向关系集合。

对于间接指向关系的处理，PACV使用可扩展的全局指针别名分析来确定哪些指针变量可能彼此别名，别名信息用抽象内存位置的命名空间表示。为获得更高的精度，根据其访问路径确定位置。根据指针分析可以获得每个变量v的指向集ps(v)，每个指向目标都是抽象栈位置(本地或全局变量)或抽象堆对象。

由于内存泄漏检测与指针分析密切相关，因此，现有的许多内存泄漏研究将其检测方法构造为特殊的指针分析。本文将指针分析作为独立的一部分，以便以后可以重用不同的指针分析算法，提高分析效率。

Table 1 Variables Def-Use information

定义1过程内Def-Use关系：RIntra(l,l′,v),表示过程内控制流路径P上v从l到l′的Def-Use关系，其中v是程序中的变量，在这之间没有进行重新定义，即:

∃/l″∈P:l″∈Defv

定义2过程间Def-Use关系：RIntra(l,l′,func(v)),表示过程间控制流路径P上v从l到l′的Def-Use关系,其中l与l′在2个不同方法内，在这之间没有进行重新定义，即:

∃/l″∈P:l″∈Deffunc(v)

根据上文C程序的抽象模型描述，表1列出从语句中提取的变量Def-Use信息。对于NULL、COPY语句，可以直接读取其Def-Use信息。对于LOAD或STORE语句，必须考虑间接访问对象的Def-Use信息。其中，ps(v)表示从需求驱动的上下文相关指针分析获得的变量v的指向集；对于方法调用CALL、METHOD和RET，可以直接获得变量v的Def-Use信息。

基于指针分析中的指向信息构建值流信息，捕获程序间引用和程序变量的修改副作用，使用别名集合对每个LOAD、STORE、CALL语句的间接Def-Use进行注释，每个别名集合代表一组可以间接访问的抽象内存对象。

SVFA是一种广泛用于内存泄漏检测的值流分析方法，它沿数据依赖关系跟踪VFG而不是CFG，可以跳过无关的程序语句以实现可扩展性。但是，由于缺少必要的控制流信息，SVFA方法缺乏路径敏感性，导致检测结果误报率高，不够准确。本文在VFG上结合必要的控制流信息，不仅对变量的Def进行编码，还对相关的堆对象的Use进行编码，同一个内存对象的Use位置根据控制流进行排序，从而检查内存泄漏。同时，通过创建终结结点模拟对象的生命周期，表明不再引用p指向的堆对象。其中数据依赖关系记为：p@lm→p@ln，表示p指向的内存分配对象可以在语句ln处释放(li表示第i行的语句)，也可以理解为值流边。最终达到对程序变量的整个生命周期进行建模的效果，将扩展之后的SVFA(Sparse Value Flow)对应值流图记为扩展值流图E-SVFG(Extend SVFG)，仍然沿用稀疏值流图SVFG的稀疏性质，跳过不相关语句。

定义3程序的E-SVFG使用有向图G=(N,E)表示，其中N是结点集合，E是边集合：

(1)o@p∈N表示程序点p处的对象为o。

(2)当o1和o2表示同一对象且存在从p1到p2的控制流路径时，有向边(o1@p1,o2@p2)∈E。

3.2 基于路径敏感的值流分析的内存泄漏检测

将程序的内存空间划分为一组抽象内存位置M。抽象内存函数mem:S→M，实现给定语句到抽象内存位置的映射。通过将所有访问映射到它们的抽象内存位置，可以通过直接访问处理间接访问。此外，由于抽象内存位置可以表示多个物理位置，存储新值不会覆盖旧值，因此对抽象内存位置的新定义被称为弱更新，添加新值而不破坏旧值。用ζ函数来表示弱更新。

定义4ζ函数形式如下所示：

d=ζ(d1,d2)

ζ函数有2个操作数，第1个操作数d1表示分配的新值，第2个操作数d2表示保留的旧值。由于d2本身可以被赋予ζ函数，所以可以将所有操作数向前传递追溯，直到ζ函数找到分配给抽象内存位置定义的所有值。

为了对控制流信息进行更具体的描述，给出定义5。

定义5θ函数形式如下所示：

d=θ(〈p1,d1〉,〈p2,d2〉,…,〈pn,dn〉)

其中,d为变量的定义；pi(i≤i≤n)为谓词，在多条控制流路径汇合处，若新的谓词p成立，则新定义d成立。通过构造控制流的程序表达，可经一处Def达到某个变量的多处Use。θ函数的定义操作数本身可以是θ。函数的定义，可以通过计算操作数的传递闭包来找到由θ函数定义的变量的所有可能值。

为减少误报，增加路径敏感性尤为重要。如表2所示，路径不敏感分析会推断出x可能指向a或者NULL，导致第13行上的*x会因解引用NULL而发生ERROR。然而分析程序路径显示，只有当Cond在第13行成立时才会解引用，也就是x只能指向a。

Table 2 Path-sensitive analysis

访问路径是指解引用和字段访问操作的组合，若访问路径不包含迭代的解引用或字段访问操作，则简单很多。函数的局部变量、参数、全局变量作为函数访问位置。访问位置的内容以路径敏感形式进行跟踪。用直接访问替代间接访问，每个变量的定义或使用全部用θ函数表达，通过将其映射到抽象内存位置来分析其他所有访问。

根据表2分析可知，第11行if语句末尾的θ函数表明：当Cond为真，变量x表达为x0；当Cond为假，则为x1。着重分析第13行的间接访问*x，x的有效定义是x2。当Cond为真，x2与x0相同，其值为&a，因此*x的有效定义是a,a1；当Cond为假，x2由x1给出，其值为NULL，解引用NULL产生错误。*x的这2个可能值由2个新定义t1、t2的θ函数表示。由此说明如何表示间接访问的Def-Use关系。

给定程序，构建其过程间控制流图即ICFG(Interprocedural Control Flow Graph)。函数中的节点分为调用节点和返回节点，边分为从调用节点到函数入口节点的调用边以及从函数的出口节点到返回节点的返回边。为执行上下文敏感分析，变量v的pt({ci},v)(其中ci表示变量v的调用位置)返回结果为包含ci的函数调用序列的变量v的指向集。因此，pt({},vl)给出在所有调用上下文中第l行的v的指向集。

为执行路径敏感分析，通过调用上下文c和路径保护ρ来表示抽象路径，c指定其调用序列，ρ收集其分支条件。定义pt({c,ρ},v)，给出在{c,ρ}下的第l行的v的指向集。在函数f中，每个分支条件被看作一个布尔表达式。对于一条控制流边e，ControlGuard(e)是执行e的分支条件；对于一组控制流边e组成的控制流路径cp，cp的条件是每条e的分支条件的逻辑合取:

ControlGuard(cp)=

{∧ControlGuard(e)|e∈cp}

从语句l到语句l′的路径保护Guard(l,l′)是由所有控制流路径的路径条件的逻辑析取：

Guard(l,l′)={∨

ControlGuard(cp)|cp∈Path(l,l′)}

其中Path(l,l′)表示从l到l′的控制流路径集。

由此，根据上述定义收集从入口main()到某条语句的路径保护Guard(l,l′)。由于路径条件可能出现矛盾的情况，用true与false表示可行与不可行路径。

根据计算值流边上的保护信息，以捕获程序中值流发生的路径条件，用于推断所有路径上的释放点的可达性。设定在内存分配结点创建的对象为src，在内存释放结点创建的对象为sink，编码路径之后，开始分析可达性。

部分路径分析：Fsrc为前向切片，由VFG中src可以到达的结点组成，Ssrc为Fsrc到达的释放结点集合，若Ssrc为空，则src肯定发生泄漏，因为此种情况下，不会沿某些控制流路径到达sink(释放结点)。如果src沿着一些控制流路径到达全局变量，则泄漏检测终止，认为src没有泄漏。

路径分析：Bsrc为一个后向切片，包含src到Ssrc中的sink的路径上的节点。然后执行全路径分析来检查一个src在每条控制流上至少可达Ssrc中的一个sink，如果src在某些控制流路径上无法到达Ssrc中的sink，则发出泄漏警告，这是一种条件性泄漏，只有在某些路径条件下才会触发。

根据控制流路径保护信息，解决全路径可达性问题，vfPath(src,sink)是VFG中从src到sink的所有值流路径集，对于每条值流路径VP∈vfPath(src,sink)，Guard(VP)编码在程序中从src到sink的控制流路径集。此外，为降低分析难度，递归与循环均展开一次。因此，有以下定义：

HasFree(src)={∨Guard(VP)|

VP∈vfPath(src,sink),sink∈Ssrc}

如果HasFree(src)≠true，则发出泄漏警告，表示src沿着HasFree中的控制流路径发生泄漏。此外，在分配点之后插入对Add()的调用，以跟踪内存中的所有已分配对象。在从相应的分配结点可到达的每个释放结点之后插入对Delete()的调用，以删除释放的对象。首先，程序的VFG非常逼近变量的Def-Use关系，路径分析可靠性大大提高；其次，Add()和Delete()维护有效的内存地址，记录其生命期，对于产生的内存泄漏进行验证，剔除部分误报。鉴于以上2个原因，得出的分析结果更为准确。

根据上文所提方法设计的算法主要包括wlMod和Check_MemeoryLeak 2个算法，如算法1和算法2所示。

算法1wlMod算法

input：the C program。

output：Wstore Def-Use chain in statements。

1 whilef∈FCGis not empty

2W=∅;

3 foreachs∈Succ(n) inCFGf

4switch(s){

5 case assignment statements:e0=e1:

6Mods=ζ(e0,graph(s));

7 case call statements:e=p():

8Mods=ζ(e,graph(s));

9 }

10 foreach producrepr

11Mod(pr)=∪s∈stm(pr)Mod(s);

12W=W∪{pr};

13 endfor

14 endwhile

算法1首先通过worklist设计迭代算法wlMod，进行后向分析。从程序CFG入口处的第1个变量定义处，即第1个指针赋值语句处生成初始化信息，将信息向后传播。其中，FCG表示程序过程调用图，f为程序过程调用图中的函数，CFGf表示为每个函数生成的CFG，Succ(n)表示 CFG上语句n的所有后继语句。从FCG中自顶向下选择函数，为CFGf中每个程序点生成初始内存信息。

算法2Check_MemoryLeak算法

input： statementS,HasFree(src)。

output：reportMemoryLeak。

1 begin

2 foreachs∈S

3switch(s){

4 cases:e0=e1:

5 for(go throughdleft)

6 if(dleft→mem)

7DeleteTA(dleft→mem);

8 if(dright→mem)

9 for(go throughdleft)

10 AddTA(dleft→mem),TB(dleft);

11 if(malloc(n)):

12 for(go throughdleft)

13 AddTA(dleft→mem),TB(dleft);

14 cases:free(u):

15 for(go throughdleft)

16 DeleteTA(dleft→mem),TB(dleft);}

17 end for

18 if(TAdidn′t includesrc(dleft→mem)&&

19TBincludesrc(dleft))

20 reportMemoryLeak_Error;

21 end

算法2从程序入口处开始，处理变量的Def-Use关系，为编码路径做基础，分析布尔表达式的正确性，识别可能存在泄漏的路径。为提高检测的准确性，对内存块进行生命周期监测。上文定义的指针映射集T，是在分析程序语句的过程中动态生成的，它反映了程序中的指针和内存地址之间的映射关系。为了对分配的动态内存块以及其与指针的关系进行跟踪，算法2将指针映射集分为2个部分：(1)指针与分配的动态内存块的映射TA，多个指针可指向同一块动态内存。(2)分配的动态内存块与指针集合的映射TB，存放所有指向动态内存块的指针[23]；同时也分为2个操作：Add()和Delete()，分别对应内存块和指针的插入和删除，其中dleft,dright是语句的左操作数和右操作数。遍历程序CFG的每条路径进行检测，针对不同的结点进行不同的处理。主要分为2种语句处理：(1)赋值语句：如p1=p2=p，可能有多个左操作数，那么，算法进行遍历，查找其在TA中是否有记录，若有则删除。然后判断dright的类型：①指针：查找dleft在TA中是否有记录，若没有则处理结束；若有根据对应的内存块M，在TA中添加dleft→M，在TB中的M对应的指针集合中添加dleft。②内存分配函数：生成内存块M，在TA中添加dleft→M，在TB中添加M。(2)处理内存释放函数：根据dleft删除TA和TB中有关M的所有记录。最后根据检测出的警报信息，验证TA和TB是否为内存泄漏错误。

Figure 4 Class diagram of implementation图4 实现类图

4 实验分析

本节根据PACV研究框架以及实现算法，对实际程序中出现的内存泄漏进行分析。原型工具的设计思想如下：首先将源程序通过抽象语法树AST(Abstract Syntax Tree)转化为中间语言程序，在中间语言程序上提取指针别名信息和控制流信息，在此基础上构建路径敏感的值流信息，利用值流约束检测内存泄漏。

为了满足检测需求和具体方法实现设计的目标和原则，从功能和执行逻辑上，将原型工具分为2个模块：代码预处理模块和内存泄漏检测模块。应用SVFG、CFG分析技术定制的算法。源程序经过编译前端处理后获得AST，然后生成中间语言程序，获取变量的Def-Use链，结合必要控制流信息进行内存泄漏路径约束检测。图4是原型工具实现类图。

程序的源文件首先由CLANG前端使用 “-O0”编译，然后使用LLVM Gold链接，以生成整个程序bc文件。基于开源工具SVF[24]计算Def-Use链，增加路径敏感性分析；路径保护使用二进制决策图编码；路径可行性由Z3求解器检查。实验结果通过2个问题来证明PACV在检测实际程序中的内存泄漏时是有效且精确的：

问题1在检测现有的内存泄漏错误时是否有效？

问题2PACV在大型程序中不增加时耗的情况下是否仍能有效查找漏洞？

4.1 案例分析

本小节使用基于路径敏感的值流分析的内存泄漏检测方法检测图5中案例程序中存在2处泄漏的原因。此案例程序改编自发生在wine中的真实场景(wine是实验中用到的一个应用程序)。在图5a中，main函数中的for循环中调用了allocM，每次调用都会创建1个由2个对象组成的单字符缓冲区：L13的o，L14的o′。存在2种情况：如果缓冲区包含的字符是‘noleak’，则打印该字符，然后释放o和o′；如果缓冲区包含的字符不是‘noleak’，则o和o′都会泄漏。

(1)指针分析。获得指针别名信息：

ps(o)={o′}

ps(input)=ps(q)=ps(q)={o}

(2)值流构建。引入R表示{o}，其中o是在L13创建的抽象堆对象。根据指针分析结果，R与*input，*p和*q彼此之间别名。对程序中LOAD、STORE、CALL和RETURN语句进行分析，获取程序变量之间的Def-Use关系。例如，根据表1定义，l13属于STORE语句,描述为定义R，l4和l19的LOAD语句使用R(对其读取)，l3的CALL语句在allocM中重定义R(对其修改)，l9的CALL语句在freeM中使用R(对其读取)，最后R被隐式返回给main函数，在l16添加返回信息。如图5b所示，该图通过分配o和o′捕获Def-Use信息和值流。

(3)泄漏检测。基于路径敏感的值流，每个分配位置根据VFG的可达性判断o和o′是否泄漏。每条Def-Use边都含有其路径保护信息，在程序ICFG上捕获Def-Use之间的分支条件，所有路径保护信息按需生成，如图5c所示。当o和o′沿if分支,则到达释放点，当o和o′沿else分支,则2个对象发生泄漏，如图5d所示。

a 程序案例

b 值流构建

c值流信息约束

d 泄漏路径识别

4.2 程序集分析

为回答针对实验评估提出的2个问题，被测程序的选取分为2个部分：第1部分是对经典的堆操作程序进行分析，包括链表和树操作程序，覆盖了第2节所列举的全部内存泄漏场景，如表3所示。表3中的前5个程序来自文献[25]的不同类型的链表程序，分别是创建一定长度的链表、在链表中有序地插入一个元素、删除元素、判断链表中是否含有某个元素和链表逆置，后2个程序是文献[26]中的树操作程序。第2部分是选取表4中列出的14个SPEC2000C程序，将实验效果与CLANG中一个静态分析器(符号执行)和FASTCHECK(SVFA)进行比较，选取这2个工具是因为它们公开可用，使用率高且趋于成熟。评估时考虑2个标准：(1)效率，即分析时间；(2)准确率，即低误报检测内存泄漏的能力。

Table 3 Typical program analysis

由表3和表4的分析结果可知，PACV实现了之前所述的设计目标。表3显示在链表插入程序中，含有1个误报，说明PACV在检测现有的典型错误案例时还是非常有效的。表4显示 PACV在119个泄漏警告中检测到85个故障，FASTCHECK在165个警告中检测到90个故障，CLANG在47个泄漏警告中检测到40个故障，相比其他2个工具要少得多。总的来说，PACV速度比FASTCHECK慢，但误报率低约28%，更加精确；CLANG的误报率低，但CLANG是过程内的这一局限性，即单独分析函数而不考虑其调用函数和被调用函数，外部信息被假设为未知信息，无法分析在被调用函数中创建的对象，从而导致CLANG漏掉许多错误。对比其他2个工具可知，PACV在保证一定速度的同时仍能保证一定的精确性。

作为静态分析方法，PACV仍然受限于误报和漏报2大固有缺陷。误报的发生有以下原因：某些不可行的路径无法识别，分析时限制循环迭代次数以及保守分析内存块的别名信息存在不准确性。漏报的发生有以下原因：对数组别名访问的不健全建模，分析循环或递归的前n项有限次展开和对堆建模不精确性。此外，和许多方法一样，PACV处理指针别名分析时不完全准确。

5 结束语

C语言作为安全关键软件的主要实现语言，执行效率高，使用范围广，然而在广泛应用的同时，存在的安全问题也不容忽视。通过大量实际项目分析得知，C程序出现最多的安全问题就是与内存相关的缺陷问题，其中内存泄漏就是一种常见的缺陷形式。内存泄漏缺陷具有很高的隐蔽性和危害性，会造成难以估计的损失。

针对广泛应用于内存泄漏的SVFA分析技术缺乏路径敏感的问题，本文提出基于路径敏感的值流分析的内存泄漏检测方法PACV。在中间代码上提取指针别名信息与控制流信息，基于指针别名信息构建值流信息，由于SVFA技术缺乏路径敏感性，因此在值流信息上结合控制流信息引入路径敏感性。最后根据路径敏感的值流约束检测程序是否含有内存泄漏，在程序分配结点和释放结点增加Add()和Delete()2个函数维护有效的内存地址，记录其生命期，对产生的内存泄漏进行验证。本文方法与现有的研究工作相比，提高了内存泄漏检测结果的准确性，具有一定的意义。

Table 4 Comparision with other tools(T:True Alarms;F:False Positves)

基于本文现有工作，今后在以下方面进行进一步的研究，包括：结合更加完备的指针别名算法，提升路径分析的计算精度，加强误报情况的约减计算。