基于抽象内存模型的内存相关漏洞检测方法

许 健，陈平华，熊建斌

1.广东工业大学 计算机学院，广州 510006

2.广东技术师范大学 自动化学院，广州 510665

与内存相关的漏洞包括Memory Leak（内存泄露）[1]、Double Free（重复释放内存）[2]和Use After Free（读写释放后的内存）[3]，这三种漏洞都与动态内存的使用息息相关。内存泄漏是程序运行过程中资源泄漏的一种形式，指的是分配给程序的一部分堆内存直到程序结束才释放，通常发生在程序执行不适当的内存分配、操作和释放时。内存泄漏会导致内存耗尽[4]、程序崩溃[5]、系统故障、信息泄漏[6]等严重问题。指针使得程序员能够灵活操作内存，是C语言强大的一个重要特征，但这也使得程序员在使用C语言编写程序时，很容易错误地将内存安全缺陷引入到C程序中，而且这些缺陷很难发现、定位和修复[7]。重复释放内存指在程序运行过程中，某一块已分配的动态内存被释放两次，这会造成内存管理中数据结构的错误，从而导致系统出现未知的风险[8]。读写释放后的内存指的是释放非空指针指向的动态内存后，但没有把指针置为空，在后续代码中又使用该指针读写其指向的内存，这将会导致指针访问或修改未知的数据，有可能影响程序的运行和导致不可预测的结果。

目前对于内存相关漏洞检测的研究大多专注于指针的数据流分析和内存相关漏洞特征的形式化描述，而忽略了运行时内存的状态变化和特征。而在对于运行时内存状态的研究中，则存在着缺乏内存相关漏洞特征的形式化描述以及内存相关漏洞特征描述不全面的问题，例如，对漏洞特征没有形式化定义或只描述了内存泄露的运行时内存状态特征。

文献[9-11]认为造成重复释放内存和读写释放后的内存两种内存漏洞的主要原因是悬浮指针的使用。Caballero等[2]指出，重复释放内存和读写释放后的内存漏洞产生的一个重要特征是，此类漏洞的发生是由于创建和使用了悬浮指针；因此，该研究的认为根源是悬浮指针的创建而不是悬浮指针的使用，但是并没有考虑内存状态等任何信息，检测误报率普遍较高。Yamaguchi等[12]研究内存泄漏的特点，结合抽象语法树、控制流图以及程序流程图，基于图遍历，利用漏洞特征进行漏洞检测，该方法也只考虑了指针的创建和指针的使用，分析指针的数据流。王涛等[13]定义软件漏洞的特征，包括初始漏洞节点集、状态空间、漏洞语法规则集、判定前后条件，设计了一个基于漏洞可执行路径集的软件漏洞静态检测框架，利用定义的漏洞语法规则求解漏洞可执行路径集上的漏洞相关节点集，但是文中可执行路径集是与指针的声明和定义息息相关的，并未考虑内存的运行时状态，会存在一定的漏洞漏报。Liu等[7]为内存泄漏漏洞的语义特征定义形式化描述方法，并基于形式化特征定义语法检测规则，但他们的方法只能形式化地描述内存泄漏特征。Han等[14]研究释放后访问内存漏洞的特性是程序中分配内存、释放内存和使用释放的内存，这三种操作依次出现，然后选择关键路径，检查关键路径上是否存在释放后访问内存的漏洞特征。然而，他们的研究中所描述的漏洞特征和对关键路径的选择算法并没有深入形式化和讲述，没有考虑运行时内存的状态，从而导致关键路径的选择存在一定的错误以及漏洞的误报和漏报。Hu等[8]提出MRVDAVF模型，将有关于内存的漏洞具体形式化，同时构建指针相关的控制流图，重点对指针的声明和指针的操作进行分析，文中提到的可执行路径重点关心指针的数据流信息，并没有考虑运行时内存状态且分析程序所有执行路径，也会产生漏洞的误报和漏报。Zhang[15]提出一种阵列模型，可以直观地将内存看作一个大阵列。在这个模型中，数组元素的索引表示变量的内存地址。该方法简单直观，但不涉及复杂数据结构的描述，如指针和结构体。Dong[16]提出一个完善的抽象内存模型，基于区域的符号三元组模型，它可以描述内存中数据结构的形态信息和C程序中内存对象的存储状态，但并没有对内存相关的漏洞特征进行形式化表示以及忽略内存的偏移量信息。Dong等[17]在文献[16]的基础上提出一个改进的抽象内存模型，加入内存的偏移量信息，并基于改进的抽象内存模型，对内存泄露漏洞进行检测，但他们的方法只能形式化描述内存泄漏漏洞的特征。

指针数据流分析的方法重点关注程序中指针的数据流向。在检测内存相关漏洞中，指针数据流分析主要包括分析指针的声明和定义、申请内存、释放内存、使用指针访问内存这几种情况，重点关注指针变量本身的信息。但忽略了程序中分配和释放的内存块大小、指针指向的内存块信息以及动态分配的连续内存块和数组这一类顺序存储结构（一组地址连续的存储单元组成的存储数据的结构）的重要属性——偏移量（即指针指向顺序存储结构的位置与顺序存储结构基址的距离）。因此指针数据流分析不能全面且正确地分析程序运行时内存状态，这将会导致较高的误报率和漏报率。

为解决指针数据流分析检测内存相关漏洞所存在的问题，本文提出抽象内存模型，将程序运行过程中变量所操作的内存映射为抽象内存区域。抽象内存模型有效地将各种类型变量的信息以及所对应内存区域的信息结合起来，同时关注变量的信息以及内存区域的属性特征并且将偏移量信息融合进来。然后基于抽象内存模型形式化内存相关漏洞特征，最后基于内存相关漏洞的特征提出内存相关漏洞检测框架。

本文工作的主要贡献有以下三个方面：

（1）结合代码中数据与运行时内存状态之间的关系，提出抽象内存模型，从对指针数据流的关心转化到数据以及运行时内存状态的关心，该模型将不同类型的变量映射到抽象内存模型五元组，五元组不仅关注各种类型变量的信息和变量所对应内存区域的信息，而且包含内存区域的偏移量信息。同时很方便地分析代码控制流图中的可行路径，从而使得基于抽象内存模型的内存相关漏洞检测框架更准确地检测出与内存相关的漏洞，降低漏洞检测的误报率和漏报率。

（2）目前内存相关漏洞静态检测的方法缺乏漏洞特征的形式化描述以及漏洞特征描述不全面，本文基于抽象内存模型对与内存相关的三种漏洞类型进行分析，对内存相关漏洞的特征进行形式化表示。

（3）基于抽象内存模型和内存相关漏洞的特征，提出内存相关漏洞检测框架，其中包括可行路径求解算法以及检测内存相关漏洞的算法。

1 相关定义

内存相关漏洞产生的主要原因是在程序执行过程中内存状态的变化，因此只关注指针数据流的方法不能很好并且直观地分析程序中是否存在内存相关漏洞。另一方面，内存状态变化的原因可能是由指针或者其他变量引起的，为了建立变量与所操作内存区域之间的关系，同时关注变量的信息和所操作内存区域的信息并且引入内存区域的偏移量信息，本文提出抽象内存模型，将变量在程序运行过程中所操作的内存区域映射为抽象内存区域，用五元组定义抽象内存模型。

定义1（抽象内存模型五元组）抽象内存模型描述不同类型的变量和抽象内存区域之间的关系以及变量和抽象内存区域的信息。定义五元组q=＜Var,Type,Region,Domain,LineNum＞，Var指的是变量的名称，Type表示变量的类型，Region是与变量相关的抽象内存区域，每一块不同的抽象内存区域以唯一编号表示，按照r1,r2,…,r k顺序编号。Domain表示值域，该值在不同类型变量中所表示的含义有所区别，LineNum表示代码行号。变量与其对应抽象内存模型五元组之间的对应关系为q=map(Var)，表示将变量Var映射至抽象内存模型五元组q。

考虑C程序中的一个变量Var，根据变量Var的类型不同，其对应的五元组定义有所不同，r x表示某抽象内存区域。

（1）若Var是基本类型，如果Var的值是未知的，则其对应的五元组表示为＜Var,ptv,r x,[-inf,inf],LineNum＞；如果Var的值域是已知的，则表示为：

＜Var,ptv,r x,[y1,y2]⋃[y3,y4]⋃…⋃[yk,yk+1],LineNum＞(k≥1)

ptv表示“基本类型”（primitive type variable）。

（2）若Var是数组类型，则其对应的五元组表示为A=＜Var,array,r x,Domain,LineNum＞，对于每个d i∈Domain，d i=＜index,qi＞，index表示数组的索引，是抽象内存区域的偏移量信息，qi表示数组中元素的五元组信息，其中(d i.qi.r i)⊆(A.r x)表示Var数组中元素的抽象内存区域在Var数组的抽象内存区域内。

（3）若Var是结构体类型，则其对应的五元组表示S=＜Var,struct,r x,Domain,LineNum＞，对于每个d i∈Domain，d i=＜index,qi＞，index表示结构体中成员变量的位置，是抽象内存区域的偏移量信息，qi表示结构体中成员变量对应的五元组信息，其中(d i.qi.r i)⊆(S.r x)表示结构体S中成员变量的抽象内存区域在结构体S的抽象内存区域内。

（4）若Var是指针类型，表示为＜Var,pointer,r x,iBytes,LineNum＞，iBytes表示偏移量，单位为字节，r x表示Var指向的抽象内存区域，则五元组表示Var指向抽象内存区域r x中的第iBytes个字节。指针类型的五元组信息中存在指针与其操作内存区域的偏移量信息。指针可能指向空地址，用“null”表示空地址对应的抽象内存区域；也可能指向野地址，用“wild”表示野地址对应的抽象内存区域。指针数据流信息只包含指针类型变量的信息，而抽象内存模型中指针类型所对应的五元组包含了指针和指向内存状态信息，以及它们之间的关系和偏移量信息。

指针变量可以指向顺序存储结构的某个偏移位置，指针数据流分析不能确定指针变量相对于顺序存储结构基址的具体偏移量。在抽象内存模型中，增加指针运算以更好地支持顺序存储结构。指针算术操作可以统一为地址表达式操作，地址表达式操作的形式多种多样，这些变体可以分为以下几类（offset是表示偏移量的整数类型，p表示指针类型变量）：

基于上述三类指针运算，本文定义指针运算，每一类指针运算可能会改变左值指针指向的抽象内存区域，也可能导致该左值指针变量所对应的五元组状态发生转移。

定义2（指针运算）设offset为偏移量，iBytes为offset对应偏移的字节数，p为指针变量名称，a为指针变量名称，Array为数组名称，Array.length为数组的长度，指针运算的转移规则如表1所示。每一类指针运算都会产生两种结果，一种结果为发生指针越界错误，即指针经过运算后不再指向原先的抽象内存区域，而是指向未知区域；另一种结果为得到正确的指针运算后的结果，即指针指向已知的抽象内存区域，且指向该抽象内存区域的偏移范围内。

表1 指针类型变量运算五元组状态转移规则Table 1 Quintuple state transition rules of arithmetic operations on pointer type variables

对于抽象内存区域Region，当程序中申请的内存为堆内存时，其对应的抽象内存区域用三元组r=＜Size,FreeTimes,PointCnt＞表示，Size表示申请的堆内存的大小，单位为字节，FreeTime表示该堆内存被释放的次数，PointCnt表示指向该堆内存的指针数量。对于所有动态申请的堆内存，形成一个集合RegionList存放所有动态申请的堆内存对应的抽象内存区域，当程序中申请的内存为非堆内存时，用一元组r=＜Size＞表示。

以图1代码为例，在第3行，用抽象内存模型五元组＜data,pointer,wild,[0,0],3＞表示指针data，因为声明的指针变量data没有定义指向内存中的某个地址，是一个野指针，所以将抽象内存区域设置为“wild”。在第4行，用抽象内存模型五元组＜data,pointer,null,[0,0],4＞表示指针data，null表示指针data指向空。在第5行，用抽象内存模型五元组＜a,ptv,r1,[0,0],5＞表示基本变量a，其中r1=＜4＞。第6行用五元组＜b,ptv,r2,[1,1],6＞表示基本变量b，其中r2=＜4＞。第9行用抽象内存模型五元组＜data,pointer,r3,[0,0],9＞表示指针data指向抽象内存区域r3且偏移量为0字节，其中r3=＜32,0,1＞表示指针data指向的抽象内存区域r3此刻的状态，RegionList={r3}。第10行用五元组＜p,pointer,r3,[24,24],10＞表示指针p指向抽象内存区域r3且偏移量为24字节，其中r3=＜32,0,2＞表示此刻r3的状态，抽象内存区域r3状态如图2所示。

图1 代码片段例子Fig.1 Code snippet example

图2 抽象内存区域r 3Fig.2 Abstract memory region r 3

指针数据流分析只关注指针的数据流向，而内存相关漏洞产生的主要原因是程序执行过程中内存状态发生了改变，因此本文提出的内存相关漏洞检测框架对程序执行路径过程中的内存状态进行分析，因此定义控制流图表示程序的执行路径。

定义3（控制流图）对于代码的控制流图CFG=(N,E,Entry,Exit)[18-19]，N是节点n的集合，节点即为源代码中的语句，E是控制流边e的集合，控制流边即为控制流信息表示节点ni经过控制流边ei到达节点nj,ni为nj的直接前驱，记为ni=Prev(nj),nj为ni的直接后继，记为nj=Succ(ni)。

对于代码所对应的控制流图，由于条件选择语句的存在，控制流程图中并不是每一条路径都是可行的，因此，定义不可行路径，并且在分析运行时内存状态时忽略不可行路径，降低漏洞的误报率。

2 内存相关漏洞特征形式化

2.1 内存泄露相关定义

内存泄漏（CWE-401）[1]指的是分配给程序的一部分堆内存直到程序结束才释放，从而导致程序的内存占用随着运行时间的增加而减少。内存泄漏可能最终导致程序运行缓慢，甚至导致计算机系统崩溃。内存泄露有以下三种情况。

（1）申请的堆内存没有被释放。基于抽象内存模型，特征形式化定义为：

若存在一条可行路径path，当代码沿着path执行完毕，在RegionList集合中存在一块抽象内存区域r i的释放次数为0，即说明在程序结束之前，存在申请的堆内存没有被释放的情况，此时判定代码存在内存泄露漏洞。

（2）指针的重定义。基于抽象内存模型，特征形式化定义为：

若存在一条可行路径path，在程序沿着path执行过程中，当控制流到达某节点nk时，所有指向某抽象内存区域r i的指针都已被重定义，不再指向该抽象内存区域r i，说明r i所代表的某块初始分配的堆内存没办法被释放，从而将会产生内存泄露的问题。

（3）堆内存的申请和释放大小不匹配。基于抽象内存模型，特征形式化定义为：

若存在一条可行路径path，在程序沿着path执行过程中，控制流到达某节点nk时，指针Var虽然指向抽象内存区域r i，但不是指向该抽象内存区域r i的首地址，此时若执行free(Var)对Var指向的堆内存进行释放操作，由于Var不是指向对应堆内存的首地址，会出现堆内存的申请和释放大小不匹配的问题，从而导致内存泄露漏洞。

2.2 重复释放内存相关定义

重复释放内存（CWE-415）[2]是指在运行程序的过程中，某块堆内存在被释放一次之后，但是在之后再次被释放，这会造成堆内存管理中数据结构的错误，从而给系统和程序带来未知的错误，基于抽象内存模型，特征形式化定义为：

在可执行路径path中，在程序沿着path执行过程中，控制流到达某节点nk时，发现在RegionList中存在一块抽象内存区域r i的释放内存次数大于1，此时判定代码存在重复释放内存的漏洞。

2.3 读写释放后的内存相关定义

读写释放后的内存（CWE-416）[3]是指一个指针在释放了它指向的堆内存后，指针并没有被赋为null，如果在程序运行结束之前，再次通过该指针访问它指向的堆内存，对指向的内容进行读或写操作时，将会读取到未知的值或者修改未知区域的内容，这都将会导致不可预计的严重后果，基于抽象内存模型，特征形式化定义为：

某指针类型变量p在节点ni处声明，其所对应的抽象内存模型五元组为＜p,pointer,r i,[0,0],LineNum＞，在可执行路径path中的节点nj执行free(p)释放了p指向的堆内存区域r i后，并没有把指针p置为null，在节点nk仍然对p指向的这块堆内存进行读写操作，而这块堆内存是未知的情况，此时判定代码存在读写释放后的内存的漏洞。

3 内存相关漏洞检测框架

3.1 整体架构

图3为本文内存相关漏洞检测框架图，首先，对目标源代码进行词法分析和语法分析生成对应的抽象语法树AST；然后构造对应的控制流图CFG，定义控制流图CFG的节点信息CFGNode，如图4所示；其次，基于抽象内存模型，定义内存相关漏洞特征，根据内存泄露漏洞、重复释放内存漏洞以及读写释放后的内存漏洞的特征相关定义，检测路径上的指针状态以及运行时内存状态判断代码是否存在某种内存相关漏洞；最后生成漏洞报告。

图3 整体架构Fig.3 Overall framework

图4 控制流图CFG节点信息Fig.4 Node information of control flow graph（CFG）

3.2 得到所有可行路径

控制流图CFG中的所有路径由可行路径以及不可行路径组成，条件选择语句是造成不可行路径的主要原因。如果在控制流图中某个节点存在条件选择语句，此时会产生两条控制流边，分别表示条件选择表达式为true或者false的流向情况，但是当该条件选择表达式的结果能被判定为永远为false或者永远为true，那么其中的一条边必然不可行，而另一条边是可行的。不可行路径的存在是误报和漏报的一个重要原因，因为不可行路径是永远不可能被执行的，所以应该忽略对不可行路径的分析。在控制流图中加入变量的数值区间域可以有效地检测出不可达路径。

3.2.1数值区间域检测不可行路径

数值的区间域信息也即为数值的取值范围，抽象内存模型中基本变量类型所对应五元组中的值域即为该变量的取值范围。若变量v是基本类型且v的值是未知的，则其对应的五元组＜v,ptv,r x,[-inf,inf],LineNum＞表示变量v的取值范围为负无穷到正无穷；若变量v是基本类型且取值范围是已知的，则其对应的五元组＜v,ptv,r x,[y1,y2]⋃[y3,y4]⋃…⋃[yk,yk+1],LineNum＞(k≥1)表示变量v的取值范围为多个区间的并集。特别地，常数C的取值范围表示为[C,C]。

程序执行过程中，数值的区间域可能会经过运算而发生改变，本文基于抽象内存模型引入数值区间域运算对程序控制流图中的变量及表达式的取值范围进行跟踪，下面定义基本的区间域运算。给定两个区间域X=[x s,x e]和Y=[ys,ye]，区间域四则运算定义为：

在控制流图中，当遇到条件选择语句时，对条件选择语句中的条件表达式进行分析，根据条件表达式相关变量所对应的五元组中的值域信息分析条件表达式的返回值是否一直是false或者true，排除不可行路径。另一方面，相关变量的五元组信息在程序执行过程中随时会发生变化，此时必须获得条件表达式相关变量所对应的最新五元组信息。对每个变量使用一个该变量专属的栈结构来保存该变量所对应的最新五元组信息，栈中有且只有一个元素，该元素表示变量最新的五元组信息，随着程序的执行，在控制流图某一节点，若变量的五元组信息与该变量专属栈栈顶的五元组信息不同，则把栈中旧的五元组信息弹出，然后把新的变量对应五元组信息压入该变量的专属栈中。

在图5代码第4行（图6控制流图的节点n2）变量a的数值区间域为[0，0]，其所对应的五元组为＜a,ptv,r1,[0,0],4＞，变量a专属栈中的内容如图7所示。

图5 代码片段例子Fig.5 Code snippet example

图6 图5代码对应的控制流图Fig.6 Control flow diagram corresponding to code in Fig.5

图7 到达图6控制流图节点n2时的变量a专属栈内容Fig.7 Exclusive stack content of variable a when reaching node n2 of control flow graph in Fig.6

在图5代码的第5行（图6控制流图的节点n3）变量b的数值区间域为[0，0]，其所对应的五元组为＜b,ptv,r2,[0,0],5＞，变量b的专属栈中的内容如图8所示。

图8 到达图6控制流图节点n3时的变量b专属栈内容Fig.8 Exclusive stack content of variable b when reaching node n3 of control flow graph in Fig.6

在图5代码的第6行（图6控制流图的节点n4），变量b专属栈栈顶五元组＜b,ptv,r2,[0,0],6＞的值域[0，0]和[1，1]区间域进行加法运算，得到区间域结果为[1，1]，所以此时变量b所对应的五元组为＜b,ptv,r2,[1,1],6＞，与变量b的专属栈栈顶五元组信息不同，因此先从变量b的专属栈中弹出旧的五元组信息，然后将变量b新的五元组信息压入变量b的专属栈中，变量b的专属栈中的内容变为如图9所示。

图9 到达图6控制流图节点n4时的变量b专属栈内容Fig.9 Exclusive stack content of variable b when reaching node n4 of control flow graph in Fig.6

本文主要针对条件表达式中只存在关系运算符的情况进行分析研究，关系运算符主要有以下六种：==（等于）、!=（不等于）、＞（大于）、＜（小于）、≥（大于或等于）和≤（小于或等于）。假设有两个基本类型变量a和b，当控制流图到达某一选择语句时，获取a和b各自的专属栈栈顶的最新五元组信息，变量a所对应的最新五元组为aq=＜a,ptv,r i,Domain,LineNum＞，变量b所对应的最新五元组为bq=＜b,ptv,r j,Domain,LineNum＞。表2为a和b通过六种比较运算符的运算结果一直是false或true的情况分析。

表2 六种比较运算符运算结果一直是false或true的情况Table 2 Result of six comparison operators is always false or true

当图5代码执行到第7行（图6控制流图的节点n5），分别取得此时变量a的专属栈和变量b的专属栈，并得到各自栈顶的五元组信息＜a,ptv,r1,[0,0],4＞（图7）以及＜b,ptv,r2,[1,1],6＞（图9）。由表2可知，b的区间域总是大于a的区间域。所以第7行的条件表达式结果必为true，而第11行的条件表达式结果必为false。所以，在控制流图中，n5→e6n7是不可行子路径，n7→e7n8也为不可行子路径。

图10为基于抽象内存模型，利用数值区间域以及表2规则对控制流图中的不可行路径进行分析。

图10 不可行路径分析Fig.10 Analysis of infeasible path

3.2.2所有可行路径求解算法

在代码控制流图CFG上，按照算法1，从CFG根节点开始，采用深度优先遍历，基于抽象内存模型，利用数值区间域及表2规则，排除不可行路径，得到所有可行路径。

算法1根据数值区间域检测得到所有可行路径

输入：CFG

输出：所有可行的路径

说明：isReach(node,nextNode)：当节点node是条件选择语句，利用数值区间域检测节点node是否可达节点nextNode，其中nextNode=Succ(node)，true表示可达，false表示不可达。

可行路径求解算法的输入是代码的控制流图CFG，输出的结果是所有的可行路径。算法1的1～3行分别定义临时的路径变量path、存放所有可行路径的变量feasiblePath以及CFG的根节点root；7～11行是深度优先遍历的递归出口，当遍历到CFG的出口节点时，一条可行路径生成并加入到feasiblePath中；13行表示临时存储到达控制流图当前节点node时的所有专属栈，以便递归返回时供isReach(node,nextNode)判断节点可达性使用。14～22行是对每个节点的后继节点集循环一遍，如果当前节点可达某后继节点，则把该节点信息加入到path中，然后继续以后继节点进行深度优先遍历。

isReach(node,nextNode)利用数值区间域分析控制流图中当节点node是条件选择语句时是否可达节点nextNode（节点nextNode是节点node的直接后继节点）。此时只要得到与节点node相关的变量以及它们各自专属栈中的栈顶五元组信息，利用表2规则，若节点node的条件表达式的结果一直是false或者一直是true，则根据node到nextNode的边信息是true或者false判断是否可达；相反，则肯定可达。该算法的时间复杂度为O(1)。

可行路径求解算法对控制流图的每个节点和边只遍历一次，且isReach(node,nextNode)时间复杂度为O(1)，因此总时间复杂度为O(n+e)，其中n为控制流图中的节点数，e代表控制流图中的边数。

3.3 检测内存相关漏洞算法

算法2为检测内存相关漏洞的算法，主要任务是在所有可行路径上，依照基于抽象内存模型中提出的内存泄露漏洞、重复释放内存漏洞以及读写释放后的内存漏洞相关特征形式化定义，分析路径上的节点的指针状态以及运行时内存状态，以检测出相应的内存相关的漏洞。

算法2得到可能存在的与内存相关的漏洞

算法2的输入是所有可行路径，输出是可能存在的与内存相关的漏洞。算法2中第1行的errors集合是存放检测出来的内存相关漏洞。第6～8行表示如果当前节点是分配动态内存的节点，则生成对应的抽象内存区域r加入到RegionList集合中。第9～23行表示如果当前节点是涉及到指针运算的节点，遍历每一个相关指针p，11行表示先根据指针p对应的专属栈得到离当前节点最近的关于指针p对应的五元组信息old Q，然后按照抽象内存模型中的指针运算规则运算，如果运算结果存在指针越界的情况，则把“指针越界错误”加入到errors集合中；如果指针p没有越界，则根据五元组old Q得到其之前指向的抽象内存区域，如果指向该内存区域的指针的数量减少了，则说明当前节点的指针运算使得指针p不再指向该内存区域，当指向该内存区域的指针的数量为0时，则把“指针重定义所导致的内存泄露”加入到errors集合中。第24～37行表示如果当前节点是涉及指针p释放动态内存的节点，则根据指针p对应的专属栈得到离当前节点最近的关于指针p对应的五元组信息old Q，如果指针p不是指向动态内存首地址，则把“堆内存的申请和释放大小不匹配导致的内存泄露”加入到errors集合中；否则，判断p指向的抽象内存区域的释放次数是否为1，如果为1，则把“重复释放内存”加入到errors集合中。第38～44行表示如果当前节点是使用指针p读写指向内存的节点，则根据指针p对应的专属栈得到离当前节点最近的关于指针p对应的五元组信息old Q，如果p指向的抽象内存已经在之前被释放过了，则把“读写释放后的内存”加入到errors中。第45～52行表示如果当前节点是CFG的出口节点时，此时遍历RegionList集合中的抽象内存区域，如果发现某一抽象内存区域的释放次数为0，则把“申请的堆内存没有被释放”加入到errors中。

检测内存相关漏洞算法通过遍历每一条可行路径上的节点信息，平均时间复杂度为O(m×n)，其中m表示可行路径的条数，n表示平均每条可行路径上的节点数。

4 实验

本文从C/CPP的Juliet Test Suite[20]中选取CWE-401 Memory Leak、CWE-415 Double Free和CWE-416 Use After Free三种与内存相关的漏洞类型的测试数据集，将本文提出的内存相关漏洞检测框架与另外四种漏洞检测工具/框架（Flawfinder[21]、Cppcheck[22]、Splint[23]和MRVDAVF[8]）在该数据集进行实验。表3为三种类型数据集经预处理之后的具体信息。

表3 测试数据集具体信息Table 3 Specific information of test data set

设测试数据集的总漏洞数为TVN，模型（工具）检测出来的漏洞数为TRN，检测出来属于测试数据集的漏洞类型的漏洞数量为TTP，检测出来不属于测试数据集的漏洞类型的漏洞数量为TFN，则有TRN=TTP+TNF。公式（1）为漏报率FNR，公式（2）为漏洞误报率FPR。

表4为Flawfinder、Cppcheck、Splint、MRVDAVF和本文模型在三个数据集上的检测结果对比。Flawfinder、Cppcheck和Splint是三款开源的代码静态检测分析工具，MRVDAVF是针对内存相关漏洞提出的检测模型，这些检测工具或者方法都重点关注指针的数据流并分析程序中所有执行路径。与Flawfinder、Cppcheck、Splint和MRVDAVF相比，本文检测方法在Memory Leak和User After Free在Double Free这三种与内存相关的漏洞检测中具有更低的误报率和漏报率，说明本文提出的基于抽象内存模型的检测框架的有效性和可行性。因为本文的检测方法完全模拟了运行时内存的状态，并描述了涉及指针运算的操作，同时包含变量的信息、内存区域的信息以及忽略程序中不可行路径，确保更加精确的内存相关漏洞的检测。其中存在一定的误报率和漏报率的原因是缺乏对代码中循环结构的分析以及条件选择语句中其他未知复杂表达式的处理。

表4 五种检测工具（模型）对三个测试数据集的检测结果Table 4 Test results of five test tools（models）on three test data sets

图11为不含有漏洞的代码片段，图12、图13和图14代码片段均含有内存泄漏的漏洞，图15代码片段含有重复释放内存的漏洞，图16代码片段含有读写释放后的内存的漏洞。通过实验发现，分析程序中所有路径的检测模型或工具对图11的代码进行静态检测时会误报内存泄露漏洞；重点关注指针数据流的模型或工具能够正确检测出图12和图13代码含有内存泄漏的漏洞，但不能检测出图14代码含有内存泄漏的漏洞；同时也不能检测出图15代码含有重复释放内存的漏洞；以及不能检测出图16代码含有读写释放后的内存的漏洞。而本文提出的方法能够正确检测图11～图16的代码。

图12 内存泄漏例子（没释放动态内存）Fig.12 Memory leak example（dynamic memory is not freed）

图13 内存泄漏例子（指针重定向）Fig.13 Memory leak example（pointer redirection）

图14 内存泄漏例子（动态内存释放不全）Fig.14 Memory leak example（dynamic memory is not fully freed）

图15 代码片段例子（重复释放内存）Fig.15 Code snippet example（double free）

图16 代码片段例子（读写释放后的内存）Fig.16 Code snippet example（use after free）

图11代码是一个无漏洞的例子，但当使用Flawfinder、Cppcheck、Splint、MRVDAVF这类关注指针数据流并分析程序中所有执行路径的检测工具或方法检测图11代码时，会得到内存泄露的检测结果。因为若关注指针data的数据流并分析程序中所有执行路径时，指针data在第9行申请了一块堆内存，但是并没有在11～14行的if语句块中执行free(data)操作释放data指向的堆内存，从而报告程序存在内存泄露的漏洞。但实际上11～14行的if语句块中的代码是永远都执行不到，只会执行15～18行else语句块中的代码，else语句块中有free(data)语句，所以实际上该段代码是不存在内存泄露漏洞的。本文基于抽象内存模型提出使用数值区间域解决该类问题，根据控制流图的节点遍历，当遍历到控制流图的控制语句节点时，得到a和b两个变量各自对应的专属栈，根据专属栈可得到a和b两个变量的最新五元组信息，也即得到a和b的数值区间域，以分析路径的可达性与不可达性，忽略不可行路径，避免漏洞误报。

图12代码是一个由于申请的堆内存没有被释放而导致内存泄漏的例子，当使用Flawfinder、Cppcheck、Splint、MRVDAVF这类关注指针数据流的检测工具或方法检测图12代码时，能够报告存在内存泄漏的检测结果，因为若关心指针data的数据流，发现到程序结束之前都没有执行free(data)释放指针data所指向的堆内存，此时可判定代码存在由申请的堆内存没有被释放导致的内存泄露漏洞。本文提出的基于抽象内存模型的检测方法重点关注已分配堆内存的状态，同样也能报告存在内存泄漏的检测结果，因为在程序结束之前，通过遍历程序执行过程中分配的所有堆内存对应的抽象内存区域，发现存在某抽象内存区域中释放次数FreeTimes的值为0，此时同样可判定代码存在由申请的堆内存没有被释放导致的内存泄露漏洞。

图13代码是一个由于指针的重定义而导致内存泄漏的例子，当使用Flawfinder、Cppcheck、Splint、MRVDAVF这类关注指针数据流的检测工具或方法检测图13代码时，能够报告存在内存泄漏的检测结果，因为若关心指针data的数据流，代码中第3行声明指针data指向某块堆内存，而在第5行对指针进行了重定义，指向另一块堆内存，导致之前指向的堆内存没法被释放。本文提出的基于抽象内存模型的检测方法重点关注运行时堆内存状态，记录代码中第3行以及第5行中申请的两块堆内存的具体信息，在执行代码第5行之后发现第3行申请的堆内存所对应的抽象内存区域中指针指向数PointCnt的值为0，证明此时没有指针指向代码第3行申请的堆内存，此时同样可判定代码存在由指针重定义导致的内存泄露漏洞。

图14代码是一个由于堆内存的申请和释放大小不匹配而导致内存泄露的例子，但当使用Flawfinder、Cppcheck、Splint、MRVDAVF这类关注指针数据流的检测工具或方法检测图14代码时，会得到不存在内存泄漏漏洞的检测结果。因为若只关心指针data的数据流，忽略指针运算以及指针对指向堆内存的偏移量信息，程序中会在第5行执行free(data)语句释放指针data指向的堆内存，所以报告不存在内存泄露漏洞。而本文提出的基于抽象内存模型的检测方法关注指针对于顺序存储结构的偏移量信息，根据指针对该堆内存的偏移量信息和堆内存的释放信息，在代码第5行执行free(data)时发现指针data并非指向堆内存的首地址，因此在代码第3行成功分配的内存块没有被完全释放，此时判定代码存在由堆内存的申请和释放大小不匹配导致的内存泄露漏洞，避免了内存泄漏漏洞的漏报。

图15代码是一个存在重复释放内存的例子，但当使用Flawfinder、Cppcheck、Splint、MRVDAVF这类关注指针数据流的检测工具检测图15代码时，会得到不存在重复释放内存漏洞的检测结果。因为若只关心指针data的数据流，程序中会执行free(data)语句释放指针data指向的内存，同理，若关心指针p的数据流，程序中也会执行free(p)语句释放指针p指向的内存，完全没有考虑指针指向内存的状态信息。而本文提出的基于抽象内存模型的检测方法重点关注运行时堆内存状态以及指针状态，发现指针data和指针p都指向同一块堆内存，在执行代码第5行free(data)时，将指针data指向的堆内存所对应的抽象内存区域中释放次数FreeTimes的值置为1，而在执行代码第6行free(p)时，指针p指向的堆内存所对应的抽象内存区域中释放次数FreeTimes的值为1，此时判定代码存在重复释放内存的漏洞，避免了漏洞漏报。

图16代码是一个存在读写释放后的内存的例子，但当使用Flawfinder、Cppcheck、Splint、MRVDAVF这类关注指针数据流的检测工具检测图16代码时，检测不出代码中含有读写释放后的内存的漏洞。因为若只关心指针data的数据流，在代码中第7行指针data仍然指向一片有效合法的内存，并没有考虑所指向内存的状态信息，所以可以通过*data访问该合法内存的内容，导致读写释放后的内存的漏洞漏报。而本文提出的基于抽象内存模型的检测方法重点关注运行时堆内存状态以及指针状态，代码中第3行声明指针data指向一块堆内存，在执行代码第7行free(data)时，将指针data指向的堆内存所对应的抽象内存区域中释放次数FreeTimes的值置为1，在代码第8行使用*data访问指针data指向的堆内存，发现指针data指向的堆内存所对应的抽象内存区域中释放次数FreeTimes的值为1，此时判定代码存在读写释放后的内存的漏洞，避免了漏洞误报。

上述的实验结果表明，在代码中存在不可行路径、指针偏移、动态内存状态变更这几种情况，基于指针数据流和分析程序所有路径的检测方法会出现误报和漏报的问题。而本文提出的基于抽象模型的检测方法关注变量的信息、所操作内存区域的信息、两者之间的关系以及内存区域的偏移量信息，可以在上述的几种情况下得到正确的检测结果，大大降低与内存相关漏洞检测的误报率和漏报率。

5 结束语

内存泄露、重复释放内存和读写释放后的内存这三种漏洞都具有某些特征，对漏洞特征的研究将促进对漏洞预防和检测的研究。本文提出的基于抽象内存模型的内存相关漏洞检测框架重点关注运行时内存状态与指针的状态，对内存相关漏洞进行检测。首先，本文对抽象内存模型进行形式化定义，并形式化描述内存相关漏洞特征；然后，基于抽象内存模型以及内存相关漏洞特征，提出内存相关漏洞检测框架，包含可行路径求解算法以及检测内存相关漏洞算法；最后，为了检验本文提出的检测框架的有效性和可行性，与其他四种漏洞检测工具或模型（Flawfinder、Cppcheck、Splint和MRVDAVF）进行了对比实验。与Flawfinder、Cppcheck、Splint和MRVDAVF相比，本文提出的框架对于内存泄露、重复释放内存和读写释放后的内存的检测能力更强，漏洞漏报率和误报率均降低。实验结果表明，本文提出的检测方法是可行和有效的。

基于该研究的后续工作主要分为两个方面：

（1）研究条件选择语句中更加复杂的表达式和未知情况下的处理，如其他类型变量以及地址比较等。

（2）研究循环语句以及多线程情况下的可行路径求解过程。