数据流分析(data flow analysis)一直是程序分析、缺陷检测、测试用例生成等方面关注的重要问题, 它是静态分析中的关键技术, 通过分析程序状态信息在控制流图中的传播来计算每个静态程序点(语句)在运行时可能出现的状态.通过数据流分析, 测试人员能够在未实际执行程序的情况下发现程序运行时的行为与相关信息.

数组、malloc(·)动态分配后的连续内存等顺序存储结构在C程序中被大量使用, 其结构的复杂性使得无法利用传统的数据流分析方法对其进行准确分析.传统的数据流分析方法基于分析和效率折中的考虑, 较少对顺序存储结构进行建模; 其次, 在程序利用指针访问顺序存储结构时, 大多数现有的数据流分析方法基本只关注了指针的指向信息, 并未考虑指针在连续内存中可能发生偏移的数值性质, 更未考虑发生偏移时可能存在越界的不安全问题.因此, 对C语言中的顺序存储结构进行有效刻画与分析, 是数据流分析领域的难点.

为了说明本文对顺序存储结构的分析, 首先定义本文研究的顺序存储结构, 如图 1所示.在图 1中, m₁为物理内存, 其中, 矩形框表示部分内存块, 斜线标注部分为数组或malloc(·)动态分配成功的连续内存; m₂为对m₁处斜线标注内存内部结构的细致描述, 假设此连续内存已存储了int型数据, 其中每一个int型数据在内存中占据4个字节, 图中每一最小矩形块代表一个字节; m₃为本文定义的顺序存储结构.本文研究的顺序存储结构不考虑具体内存存储数据的类型, 即不考虑存储数据在内存中所占字节数.同时, 将存储一个数据的内存大小记为一个单元(斜线标注部分为其中一个单元), 并按照每个单元与首单元的相对位置, 从0开始依次对内存单元进行编号.

基于定义的顺序存储结构, 本文提出了一种用于C语言顺序存储结构的数据流分析方法.首先, 本文以基于区域的符号化三值逻辑(RSTVL)^[1]模型为基础, 从顺序存储结构的整体与单个元素两层面实现对顺序存储结构的完整建模, 提出了描述顺序存储结构的抽象内存模型SeqMM; 之后, 本文将C程序中顺序存储结构与指针结合使用时的操作进行归纳, 利用指针指向关系分析和数值性质分析相结合的方法对顺序存储结构的访问过程进行细致的分析与总结; 其次, 本文对形参指针引用顺序存储结构元素与实参的映射进行了推导规则设计, 实现了过程间分析; 最后, 基于上述分析, 本文实现了C程序的内存泄漏缺陷检测算法, 并在5个开源C工程及植入的内存泄漏缺陷中验证了该算法的有效性.同时, 实验结果表明:SeqMM模型可有效表示C程序中的顺序存储结构, 准确刻画了连续内存上的指针访问顺序存储结构时的相关操作, 其分析结果能够用于内存泄漏的检测工作, 同时, 在效率和精度之间取得合理的权衡.

本文第1节对现有抽象内存模型、数据流分析方法进行总结.第2节定义一种简化的C语言, 确定本文研究范围, 并提出描述顺序存储结构的抽象内存模型SeqMM.同时, 在第3节归纳C程序中指针访问顺序存储结构相关操作并依次进行分析.第4节对本文提出的方法在内存泄漏的缺陷检测应用中进行细致的讨论.同时, 在第5节展开一系列的统计与实验对比讨论, 在精度和效率上验证本方法的有效性.第6节对本文工作进行总结, 同时展望下一步的研究工作.

1 相关工作 1.1 现有的抽象内存模型

对程序进行数据流分析, 首先应该确定程序中的变量在不同程序点处的存储状态, 即构建描述变量的存储模型.目前, 基于不同的精度、效率及应用的考虑, 研究者们已提出了多种刻画变量存储信息的抽象内存模型.

最初被提出的抽象内存模型是名-值对^[2], 其简单、直观, 但无法直接对指针、数组、结构体等复杂结构进行有效的描述.为此, Xu等人^[3]引入了区域层次结构, 它在内存对象的识别、跟踪及内存对象间的关系推理方面具有重要作用, 未考虑多路径的分析.Zhang等人^[4]提出了一种直观的数组模型, 可处理指针与结构体, 未能表示内存单元之间的层次关系.Hackett等人^[5]提出了一种用局部堆位置推理代替全局堆抽象推理的内存抽象模型, 将形状抽象分解为一组独立的地址集合, 每个地址描述一个堆位置, 但该模型不支持数据流分析.董龙明等人^[6]提出了一种堆操作程序中的内存安全性域敏感的k-limit抽象存储模型, 能够描述指针之间的别名与局部可达关系.STVL^[7]可统一抽象运行时的数据流信息, 能表示变量之间的逻辑关系, 却不能表示层次关系, 而RSTVL恰恰解决了这一问题.

以上大部分对变量的存储状态研究基本上都只关注了指针的指向信息, 却未处理指针可能发生偏移后的数值性质.

文献[8]在考虑指针指向关系与偏移量的基础上提出了一种指针内存模型, 并基于该模型设计了一个可以描述指针指向关系与偏移信息的抽象域, 但在刻画指针偏移量时, 使用大范围区间来表示偏移数值范围, 导致指针偏移量分析结果误差较大.

1.2 数据流分析方法

为了提高数据流分析的精度, 研究人员通常采用敏感的分析方法, 主要包括流敏感、上下文敏感、路径敏感、域敏感.

近些年, 研究人员在流敏感、上下文敏感两方面针对Steensgaard^[9]或Andersen^[10]算法的改进与扩展进行了大量的研究工作, 并主要集中于指针分析^[11-15].文献[16]引入了一种需求驱动的强更新指针分析方法SUPA, 它可以计算C程序数据流的指向信息, 并能在一定分析预算的约束下对预先计算不精确的数值流进行精化, 从而实现上下文敏感.

路径敏感分析增加了对代码中路径条件的考虑.一些缺陷检测工具如Prefix^[17]在某些选定的路径中寻找bug, 或使用量化的递归公式对许多程序属性敏感的路径和上下文条件进行精确地表示^[18]; Gutzmann等人^[19]讨论了在数据流中插入特定于路径的过滤器操作来保留控制流信息, 但没有考虑捕获路径相关性, 也没有排除不可行的路径.Sui等人^[20]提出一种可伸缩路径敏感框架SPAS, 可获得程序中所有指向集合, 但同时增大了空间开销.文献[21]通过识别最小不可行路径段的簇来区分沿着可行和不可行控制流路径流动的数据, 引入了对MFP解的部分路径敏感性, 实现了变量的定义分析和值范围分析.

域敏感分析通过考虑结构体等复合数据类型与成员之间的关系, 保证对复合类型变量分析的准确性. Litvak等人^[22]专注处理大型复合结构变量的程序, 并为这类程序计算域敏感程序依赖关系的问题提供了一个有效和精确的解决方案.

针对现有工作对抽象内存模型以及数据流分析研究的不足, 本文提出了SeqMM模型, 从顺序存储结构的整体与单元素两个层面实现对顺序存储结构的完整建模.本文通过归纳分析访问顺序存储结构的操作与过程间分析实现流敏感、上下文敏感、域敏感的数据流分析, 同时将分析结果应用于内存泄漏的检测工作.

2 面向顺序存储结构的抽象内存模型 2.1 一种简化的C语言

指针记录了程序执行过程中内存中的某个地址, 同时在指针指向的地址上存储了某种类型的数据^[8].通过对源代码进行分析可得, C语言中的指针可以被赋值为某个变量的地址、数组变量及某个数组元素的地址等.

定义1(地址表达式).  基于源代码级指针指向地址的考虑, 将指针变量、取地址表达式、数组变量及三者分别与整型表达式进行加减操作后的表达式及null统称为地址表达式.

下面给出由真实代码改编的一段示例代码, 如图 2所示.代码中的ptr, buf, line, more, & buf[x.data+2], ++line, more-x.data+4, x.result等均属于地址表达式.

为了形式化描述本文提出的模型, 定义本文所支持的C语言文法, 如图 3所示.程序P是变量V与语句S的集合, 地址表达式集合为AER, 可寻址表达式^[1]集合为AE.

2.2 面向顺序存储结构的抽象内存模型

在之前的工作中, 我们已提出了RSTVL模型^[1], 用来描述可寻址表达式间的指向关系、层次关系与取值逻辑关系, 但未涉及对偏移的处理, 导致对顺序存储结构相关的缺陷, 如数组越界、内存泄漏、缓冲区溢出等检测不精确.因此, 本文改进了RSTVL模型, 使其可以有效刻画顺序存储结构, 并精确描述指针访问顺序存储结构操作中的偏移性质.

在图 2所示代码中, L8行的指针ptr及L9行的指针buf, line, more均为野指针, 不确定其指向; 在L12行指针line指向buf[x.data+2], 其指向基址为malloc(·)动态分配成功后顺序存储结构的首地址即buf[0], 偏移量为x.data+2;在L13行more指向基址为buf[0], 其指向buf[x.data+2]单元, 偏移量为x.data+2.指针buf初始指向malloc(·)动态分配成功后顺序存储结构的首地址, L16行执行成功后, 其指向内存单元more^[1], 偏移量为7.

定义2(面向顺序存储结构的抽象内存模型(abstract memory model oriented to sequential storage structure, 简称SeqMM). SeqMM被定义为四元组:SepMM=$\langle$Var, Region, S_Exp, Domain$\rangle$.其中, Var表示内存对象, Region表示内存对象分配的内存块; 对每一个描述区域Region用唯一的区域编号进行标识, 区域编号对应区域Region的左值, 符号表达式S_Exp表示区域Region的右值, Domain表示取值区间.内存对象、符号表达式等概念参见文献[1].

对于C程序中的一个变量p, p的类型不同, SeqMM有不同的表示.

(1)   当p为数组变量时, 其模型表示为$\langle$Var, Region, Domain$\rangle$, 此时取值区间Domain={r₁, r₂, …, r_n}为各数组元素区域信息, 其中, r_i=$\langle$elementIndex, elementRegion$\rangle$由某个数组元素索引与其对应区域构成.

(2)   当p为指针变量时, SepMM=$\langle$Var, Region, S_Exp, Domain$\rangle$, Domain={d₁, d₂, …, d_n}为p指向区域与对应偏移的集合, 其中, d_i=$\langle$PtRegion, Offset$\rangle$, PtRegion为指针p指向的内存对象Var对应区域, 且Offset是一个整型表达式, 表示偏离指向基址的偏移量对应的整型区间(不考虑指针的指向内存对象所占内存字节数大小).

(3)   当p为结构体变量时, SepMM=$\langle$Var, Region, S_Exp, Domain$\rangle$, 此时取值区间Domain={r₁, r₂, …, r_n}为结构体各成员的区域信息, 其中, r_i=$\langle$member, memberRegion$\rangle$由结构体某成员及其对应区域构成.

(4)   当p为基本类型变量时, 若p的取值value未知, 其模型表示为四元组$\langle$Var, Region, S_Exp, Domain$\rangle$, 此时Domain=[-inf, inf]; 若p的取值已知, 其模型则为三元组$\langle$Var, Region, S_Exp$\rangle$, 此时将其具体取值记为p的符号表达式.

对不同类型的内存对象Var, SeqMM用不同类型的区域对其存储状态进行抽象刻画.PrimitiveRegion刻画基本数据类型的内存对象, PointerRegion, ArrayRegion, StructRegion分别用来刻画指针、数组或malloc(·)动态分配的内存区域、结构体.每一个描述区域仅有唯一的区域编号, 上述区域的编号形式依次为“bm_i”, “pm_i”, “am_i”, “sm_i”(i∈N, 从0开始递增).对malloc(·)动态分配的无名内存, 用“mxm_i_n”(“x”表示上述区域类型, 取值可为“b”, “p”, “a”, “s”)进行区域的抽象描述, 其中, “n”为该无名内存的字节数.对于空指针, 其对应地址的区域编号为“null”, 野指针为“wild”, 同时, 对于函数参数和全局变量的区域编号分别额外增加首字母“u”与“g”.

用本文所提出的SeqMM模型对图 2代码中的部分变量进行建模, 分析得出L6行结构体x的模型表示为$\langle$x, usm_0, {·}$\rangle$; L7行变量i用本模型表示为$\langle$i, bm_1, i_01, [-inf, inf]$\rangle$, [-inf, inf]用来标识函数内数值型变量取值区间未知, 同时变量value可表示为$\langle$value, bm_2, 1$\rangle$(“1”为value的符号表达式); L8行指针fmt指向整型变量i, 其模型表示为$\langle$fmt, pm_3, fmt_45, {$\langle$bm_1, [0, 0]$\rangle$}$\rangle$, 其中, 指针指向基本类型变量时, 其偏移区间固定为[0, 0], 其次, 无法确定指针ptr的指向, 故其模型表示为$\langle$ptr, pm_7, ptr_1011, {$\langle$wild, [0, 0]$\rangle$}$\rangle$, 其中, 野指针指向地址的区域编号为“wild”, Offset初始区间为[0, 0];同样地, L9行指针buf, line, more可分别表示为$\langle$buf, pm_8, buf_1213, {$\langle$wild, [0, 0]$\rangle$}$\rangle$, $\langle$line, pm_9, line_1415, {$\langle$wild, [0, 0]$\rangle$}$\rangle$, $\langle$more, pm_10, more_1617, {$\langle$wild, [0, 0]$\rangle$}$\rangle$; L10行在为结构体x的成员data赋值后, x.data用模型表示为$\langle$x.data, ubm_11, 3.0$\rangle$(“3.0”为x.data的符号表达式), 同时, 变量x模型更新为$\langle$x, usm_0, {data: 3.0}$\rangle$; L11行执行结束后, 变量buf的模型表示为$\langle$buf, pm_8, buf_1819, {$\langle$mbm_12_8, [0, 0]$\rangle$}$\rangle$.

3 面向顺序存储结构的数据流分析

C程序中主要通过指针访问顺序存储结构, 本节将针对指针的迁移操作、谓词操作、遍历顺序存储结构循环操作、形参指针引用顺序存储结构时与实参的对应进行分析.

3.1 指针相关迁移操作分析

在C程序中, 指针主要通过值、地址访问顺序存储结构实现对其他变量的赋值, 下面本节将就两种方式分别进行细致的讨论.

假定在程序点l处, R^l$\left[\kern-0.15em\left[ {Var} \right]\kern-0.15em\right]$表示内存对象var对应区域r; P^l$\left[\kern-0.15em\left[ {p} \right]\kern-0.15em\right]$={PtRegion₁, PtRegion₂, …, PtRegion_n}为指针p指向区域的集合; B^l$\left[\kern-0.15em\left[ {r} \right]\kern-0.15em\right]$表示区域r对应的基址区域, length为该区域单元个数即长度; O^l$\left[\kern-0.15em\left[ {r} \right]\kern-0.15em\right]$表示区域r偏离基址区域的偏移区间Offset; E^l$\left[\kern-0.15em\left[ {r} \right]\kern-0.15em\right]$表示区域r对应的符号表达式; $D_{se}^l [\kern-0.15em[ {S_{Exp}} ]\kern-0.15em] $表示符号表达式S_Exp对应的抽象取值区间Domain.

3.1.1 地址访问迁移操作分析

从源代码级看, C程序中通过地址访问顺序存储结构可统一归结为地址表达式addrexp_i的操作, 其在程序中表示多样, 本节归纳为如下7类.

●  p=q+iexp;    //q为指针变量

●  p=A+iexp;    //A为数组变量

●  p= & A[j]+iexp;

●  p++;

●  ++p;      //操作与p++类似, 不再单独讨论

●  p——;

●  ——p;      //操作与p——类似, 不再单独讨论

本文根据上述常见的地址访问操作对指针的赋值总结如下的迁移操作, 见表 1, 其中, newS_Exp表示产生的新符号表达式, nR为区域r偏移某个长度后的区域, out of Bounds表示索引越界警告.

以p=q+iexp为例, 对于右端q的每一个指向区域r, 若为数组元素区域, 则执行下面的操作.

(1)   获取区域r的偏移O^l$\left[\kern-0.15em\left[ {r} \right]\kern-0.15em\right]$, 当O^l$\left[\kern-0.15em\left[ {r} \right]\kern-0.15em\right]$+iexp在0与基址区域长度length之间, 才能执行迁移操作; 否则, 提示out of Bounds警告.

(2)   在执行迁移操作时, 生成区域r偏移iexp后的新区域nR, 该区域偏移区间为O^l$\left[\kern-0.15em\left[ {r} \right]\kern-0.15em\right]$+iexp, 同时为p生成新的符号表达式与nR对应.

由表 1可以看出, 本文在更新左端指针指向区域的同时, 对偏移区间、基址区域、符号表达式执行相应的更新操作.

利用本文归纳的迁移操作, 对图 2中的代码进行分析验证.代码L12行执行完成后, 指针line指向发生变化, 指向元素buf^[5], 其模型表示为$\langle$line, pm_9, line_2021, {$\langle$bm_15, ^{[5, 5]}$\rangle$}$\rangle$, 其中, “bm_15”为buf^[5]的区域编号.在代码L13行, 指针line先执行自加操作, 其模型表示为$\langle$line, pm_9, line_2425, {$\langle$bm_16, ^{[6, 6]}$\rangle$}$\rangle$, 指向区域及偏移区间均发生变化.同样地, 在执行对指针more的赋值操作后, more的模型表示为$\langle$more, pm_10, more_2829, {$\langle$bm_16, ^{[6, 6]}$\rangle$}$\rangle$.因此, L13行部分指针的指向关系如图 4所示.若满足if条件, 则在L15行执行时, line应指向buf^[9], 超过连续内存索引上界, 提示out of Bounds警告.

3.1.2 值访问迁移操作分析

利用指针可方便、灵活、随机访问顺序存储结构中元素的值, 设p为指针, 则归纳其值访问操作如下.

●  a=^*p;

●  a=p[iexp].  //iexp为整型表达式

根据两种常见值访问操作, 可总结如下对应的迁移操作, 见表 2.

●  对于a=^*p, 本文根据指针p的每一个指向区域对应符号表达式获得相应的取值区间, 并对所有取值区间执行区间并运算, 再赋值给左端变量a的取值区间Domain, 同时生成新的符号表达式与之对应.

●  对于a=p[iexp], 指针p应指向数组或malloc(·)动态分配成功的连续内存, 且存在指向区域对应的偏移在0与基址区域长度length之间, 才可执行迁移操作; 否则提示out of Bounds警告.a=p[iexp]执行迁移操作的过程与a=^*p类似.

在图 2代码中, 在L23行语句执行前, 指针ptr指向两个内存对象x.result[0]与x.result^[5], 故其模型表示为$\langle$ptr, pm_7, ptr_4445, {$\langle$ubm_19, [0, 0]$\rangle$, $\langle$ubm_20, ^{[5, 5]}$\rangle$}$\rangle$, 同时, x.result的模型表示更新为$\langle$x.result, uam_18, {$\langle$0, ubm_ 19$\rangle$, $\langle$5, ubm_20$\rangle$}$\rangle$; 当执行L22行时, 通过指向区域获得对应区域的符号表达式x.result[0]_3637, x.result^[5]_4041, 并依据符号表达式获取当前x.result[0]与x.result^[5]的取值均为[-inf, inf], 同时取并集为[-inf, inf], 其次生成新的符号表达式并与[-inf, inf]之间建立映射关系.在L24行执行时, 因区域{“ubm_20”}对应偏移为^{[5, 5]}, ^{[5, 5]}+value+2后将超出x.result的索引上界, 提示out of Bounds警告, 因此, 该行只根据区域{“ubm_19”}进行计算, 与L23行过程类似.

因此, 由表 1、表 2及示例可得, 指针访问顺序存储结构与索引安全性密切相关.本节通过对索引的预先计算检查, 对可能超过索引下界或上界的操作进行越界警告, 减少之后不必要的分析工作, 并有效提高分析精度与效率.

3.2 指针相关谓词操作分析

当分支语句中条件形如$\left[\kern-0.15em\left[ {{{addrex}}{{{p}}_1}\Re\; {{ addrex}}{{{p}}_2}} \right]\kern-0.15em\right]$时, 涉及指针对顺序存储结构的访问操作.其中, addrexp_i为地址表达式, $\Re $∈{ > , < , > =, < =, !=, ==}.

由地址表达式在C代码中的不同形式, 可总结为如下4类(以$\Re $为“ > =”时为例).

●  p+iexp₁ > =q+iexp₂;

●  p+iexp₁ > =A+iexp₂;

●  p+iexp₁ > = & A[j]+iexp₂;

●  p > = & a.

其中, p, q均为指针, iexp_i为整型表达式, a为基本类型变量.

本文在实现地址表达式的比较时, 作如下规定:

(1)   若addrexp₁与addrexp₂存在共同基地址且两者偏移区间满足$\Re $, 则谓词一定为真;

(2)   若addrexp₁与addrexp₂存在共同基地址且两者偏移区间不满足$\Re $, 则谓词一定为假;

(3)   否则, 本文方法无法对地址表达式进行比较.

在归纳地址表达式比较的谓词操作时, 本文假定flag标记条件的布尔值, True表示条件为真, False表示条件为假, True or False表示无法判断, 见表 3.对于其他关系符号的地址表达式比较, 可以定义类似形式的谓词操作.

以p+iexp₁ > =q+iexp₂为例.

(1)   若存在r₁∈P^l $\left[\kern-0.15em\left[ p \right]\kern-0.15em\right]$, r₂∈P^l$\left[\kern-0.15em\left[ q \right]\kern-0.15em\right]$, 其基址区域相同, 且偏移区间满足O^l$\left[\kern-0.15em\left[ r_1 \right]\kern-0.15em\right]$+iexp₁≥O^l$\left[\kern-0.15em\left[ r_2 \right]\kern-0.15em\right]$+iexp₂, 则本文方法

判定谓词为True;

(2)   若对于任意的r₁∈P^l$\left[\kern-0.15em\left[ p \right]\kern-0.15em\right]$, r₂∈P^l$\left[\kern-0.15em\left[ q \right]\kern-0.15em\right]$, 其基址区域相同, 且偏移区间无法满足O^l$\left[\kern-0.15em\left[ r_1 \right]\kern-0.15em\right]$+iexp₁≥O^l$\left[\kern-0.15em\left[ r_2 \right]\kern-0.15em\right]$+iexp₂,

则本文方法判定谓词为False;

(3)   若对于任意的r₁∈P^l$\left[\kern-0.15em\left[ p \right]\kern-0.15em\right]$, r₂∈P^l$\left[\kern-0.15em\left[ q \right]\kern-0.15em\right]$, 其基址区域不相同, 则本文方法无法进行判定.

由上文对图 2的L14行代码分析可得, 指针line的模型表示为$\langle$line, pm_9, line_2425, {$\langle$bm_16, ^{[6, 6]}$\rangle$}$\rangle$, 其中, “bm_16”为内存对象buf^[6]对应区域的区域编号, 右端指针buf经过运算, 其指向内存对象buf^[6], 两者存在共同的基址; 同时, 左端偏移区间^{[6, 6]}与右端偏移区间^{[6, 6]}满足小于等于关系, 故该条件为真, 一定会执行if语句块内代码.

此外, 在分支语句执行完成后, 本文分析方法会对各分支数据流事实进行合并操作, 以L19行分支语句块为例, 其控制流图如图 5所示.在该控制流图中, 只给出了与if语句块相关的变量存储状态.在执行if语句前, x, i, ptr的模型表示在上述工作中已确定.在L20行, i的取值范围变为[1, inf], 并为新出现的x.result[0]分配抽象区域, 生成新的符号表达式, 其取值为[-inf, inf].因此, x的模型表示更新为$\langle$x.usm_0, {data:3.0, result:{$\langle$0, ubm_19$\rangle$}}$\rangle$, 其中, “ubm_19”为x.result[0]对应的区域编号.L20执行完成后, ptr指向x.result[0], 其模型表示为$\langle$ptr, pm_7, ptr_1011, $\langle${$\langle$ubm_19, [0, 0]$\rangle$} $\rangle \rangle $.同样地, L22行语句也执行类似分析.在if语句块执行结束后, 需对各汇入结束节点的边上的数据流事实进行合并.因此, x的模型表示更新为$\langle$x.usm_0, {data:3.0, result:{$\langle$0, ubm_19$\rangle$, $\langle$5, ubm_20$\rangle$}}$\rangle$, ptr模型表示更新为$\langle$ptr, pm_7, ptr_4445, $\langle${$\langle$ubm_19, [0, 0]$\rangle$, $\langle$ubm_20, ^{[5, 5]}$\rangle$} $\rangle \rangle $, 其中, Domain已经发生变化, 需要生成新的符号表达式与之对应, 即“ptr_4445”.

3.3 循环语句分析

C程序中循环语句一般为3类:for语句、while语句、do-wihile语句.循环语句分析复杂且do-wihile语句在实际工程中出现次数较前两者少, 因此本文将只对for语句与while语句中对顺序存储结构遍历的操作进行细致讨论, 以while语句为例, for语句分析与while语句等价.

本文利用加宽/收窄算子^[23]对循环语句的抽象存储迭代求精, 直至达到循环内外的抽象存储的不动点.通过加宽算子使程序不动点语义的计算过程收敛或加速使其收敛, 收窄算子对程序不动点语义计算结果进行精化.在对某个顺序存储结构进行遍历时, 指针对应偏移区间可唯一确定顺序存储结构的各个元素, 因此, 本文在对循环语句分析时, 只关注当前指针取值Domain中的偏移区间, 其指向区域固定为NotNull.表 4为本文偏移区间的加宽/收窄算子运算规则, 其中, “-1”表示指针指向顺序存储结构0号单元的前一个单元.

遍历顺序存储结构的循环语句的控制流图结构如图 6所示.循环语句块的直接前驱节点为n₁, 包含循环条件的循环开始节点为n₂, 循环语句块内循环变量变化的语句对应节点为n₃, 循环结束节点为n₄.

本文利用加宽/收窄算子对循环语句进行分析的算法如下所示.

算法1.遍历顺序存储结构的循环语句分析算法.

Begin

1:   let ${{O}^{\centerdot {{n}_{2}}}}={{O}^{{{n}_{1}}\centerdot }}$, var as cyclic variable

2:   $O_{temp}^{{{n}_{1}}\centerdot }={{O}^{{{n}_{1}}\centerdot }}-{{O}^{{{n}_{1}}\centerdot }}[\![{{R}^{{{n}_{1}}\centerdot }}[\![var]\!]]\!]$;

3:   ${{O}^{\centerdot {{n}_{3}}}}={{O}^{{{n}_{2}}\centerdot \mapsto T}}$;

4:  $O_{temp}^{\centerdot {{n}_{2}}}={{O}^{{{n}_{3}}\centerdot }}\cup {{O}^{{{n}_{1}}\centerdot }}[\![{{R}^{{{n}_{1}}\centerdot }}[\![var]\!]]\!]$;

5:  ${O}'=O_{temp}^{\centerdot {{n}_{2}}}$;

6:  while true

7:     ${{O}^{\centerdot {{n}_{3}}}}={{O}^{{{n}_{2}}\centerdot \mapsto T}}$;

8:     $O_{temp}^{\centerdot {{n}_{2}}}={{O}^{{{n}_{3}}\centerdot }}\cup {{O}^{{{n}_{1}}\centerdot }}[\![{{R}^{{{n}_{1}}\centerdot }}[\![var]\!]]\!]$;

9:    $O_{temp}^{\centerdot {{n}_{2}}}={O}'\nabla O_{temp}^{\centerdot {{n}_{2}}}$;

10:      if $O^{\prime} \neq O_{t e m p}^{n_{2}} \quad O^{\prime}=O_{t e m p}^{\cdot n_{2}}$;

11:      else break;

12:    let ${O}'=O_{temp}^{\centerdot {{n}_{2}}}$;

13:    while true

14:      ${{O}^{\centerdot {{n}_{3}}}}={{O}^{{{n}_{2}}\centerdot \mapsto T}}$;

15:      $O_{temp}^{\centerdot {{n}_{2}}}={{O}^{{{n}_{3}}\centerdot }}\cup {{O}^{{{n}_{1}}\centerdot }}[\![{{R}^{{{n}_{1}}\centerdot }}[\![var]\!]]\!]$;

16:      $O_{t e m p}^{n_{2}}=O^{\prime} \Delta O_{t e m p}^{\cdot n_{2}}$;

17:      if ${O}'\ne O_{temp}^{\centerdot {{n}_{2}}}\ \ {O}'=O_{temp}^{\centerdot {{n}_{2}}}$;

18:      else break;

19:    ${{O}^{{{n}_{4}}\centerdot }}=O_{temp}^{\centerdot {{n}_{2}}}\cup O_{temp}^{{{n}_{1}}\centerdot }$

图 7中, p在L3行指向数组A, 其指向基址等于A的基址; 同时, 偏移区间与[50, 50]满足小于关系, 故可执行循环体.在分析循环时, 本文方法只对偏移区间进行加宽/收窄, 最终p的偏移区间为[50, 50].

3.4 过程间分析

过程间分析是静态分析的重要组成部分.同一函数在不同的调用点被调用, 因为上下文环境的不同可能造成实参与全局变量存储状态的不同.近些年, 研究者们已对函数调用中指针别名的指向映射进行了大量工作, 但对被调函数内形参指针引用顺序存储结构元素与实参的映射研究相对较少.本节针对这一问题开展研究, 提出了一种映射推导规则.

本文采用符号化函数摘要^[1]的思想, 解决偏移相关下实参与形参指针引用时的映射问题.假定acPara, foPara分别表示指向顺序存储结构的实参指针与形参指针, foPara[iexp]表示通过指针foPara引用顺序存储结构元素. $P_{o}^{l}[\![p]\!]=\{\langle PtRegio{{n}_{1}}, offse{{t}_{1}}\rangle , \langle PtRegio{{n}_{2}}, offse{{t}_{2}}\rangle , ..., \langle PtRegio{{n}_{n}}, offse{{t}_{n}}\rangle \}$表示指针p的指向区域与对应偏移的集合, V^l$\left[\kern-0.15em\left[ r_1 \right]\kern-0.15em\right]$表示区域r偏移iexp之后的新区域.本文提出的推导规则如下所示.

$ \frac{foPara:P_{o}^{l}[\![foPara]\!]=P_{o}^{l}[\![acPara]\!]}{foPara[iexp]:{{V}^{l}}[\![nR_{iexp}^{r}]\!]\wedge {{B}^{l}}[\![nR_{iexp}^{r}]\!]={{B}^{l}}[\![r]\!]}(\forall r\in {{P}^{l}}[\![acPara]\!]). $

对于形参foPara, 其指向区域、偏移及基址区域与实参acPara相同; 对于foPara[iexp], 获得foPara的指向

区域P^l$\left[\kern-0.15em\left[ foPara \right]\kern-0.15em\right]$, 对于每一个区域r, 其偏移为O^l$\left[\kern-0.15em\left[ r \right]\kern-0.15em\right]$, 基地址区域为B^l$\left[\kern-0.15em\left[ r \right]\kern-0.15em\right]$, foPara[iexp]的基地址区域与foPara完全相同, 其指向区域在区域r基础上向左或向右偏移iexp个单位, 对应内存对象为${{V}^{l}}[\![nR_{iexp}^{r}]\!]$.

对于图 2中的代码, ean_make函数在L25行被调用, 传递指针ptr.ptr指向区域与对应偏移的集合$P_{o}^{l}[\![ptr]\!]=$ {$\langle$ubm_19, [0, 0]$\rangle$, $\langle$ubm_20, ^{[5, 5]}$\rangle$}, 则形参指针spc的指向区域与对应偏移集合$P_{o}^{l}[\![spc]\!]=P_{o}^{l}[\![ptr]\!]$.对于ean_make函数内的spc^[2], 首先获得spc的指向区域P^l$\left[\kern-0.15em\left[ spc \right]\kern-0.15em\right]$:对于spc的指向区域{“ubm_19”}, 其偏移为[0, 0], 则spc^[2]指向区域的偏移为^{[2, 2]}, 指向区域为{“ubm_23”}, 指向内存对象为x.result^[2]; 对于spc的指向区域{“ubm_20”}, 其偏移为^{[5, 5]}, 则spc^[2]指向区域的偏移为^{[7, 7]}, 指向区域为{“ubm_24”}, 指向内存对象为x.result^[7].同时, x.result^[2], x.result^[7]的值修改为31, x.result的模型表示更新为

$ \left\langle \left. x.\text{result, ua}{{\text{m}}_{-}}18, \left\{ \left\langle 0, ub{{m}_{-}}19 \right\rangle , \left\langle 2, ub{{m}_{-}}23 \right\rangle , \left\langle 5, ub{{m}_{-}}20 \right\rangle , \left\langle 7, ub{{m}_{-}}24 \right\rangle \right\} \right\rangle \right.. $

4 内存泄漏检测算法

内存泄漏是程序动态内存分配及释放方面常见的软件漏洞.通常情况下, 内存泄漏不会产生可直接观察的错误状态, 而是逐渐积累, 造成系统内存的浪费, 严重情况下可能造成软件崩溃.

近年来, 研究人员已从多个方面开展对内存泄漏的研究工作.Šor在他的博士论文^[24]中提出基于GenCount概念的增长分析方法来检测Java内存泄漏, 该方法可识别重复创建新对象的代码位置, 但不处理先前创建的对象.在作者另外两篇文献[25, 26]中, 该方法得到进一步增强.同时, Andrzejak等人^[27]将文献[24, 25]的方法转移到C/C++中, 通过对SPEC CPU2006中14个程序的评估, 展示了他们的可行性和准确性.文献[28]提出了一种C语言内存泄漏的智能化检测算法, 通过使用机器学习算法学习程序与内存泄漏之间的相关性.文献[29]提出了一种基于混合执行测试的静态内存泄漏警报的自动化确认方法, 并对内存泄漏警报进行分类, 降低人工确认的工作量.

静态分析中, 数据流分析是检测多种缺陷的必要工作.本节利用第2节提出的SeqMM模型, 对动态分配内存进行描述, 同时利用第3节对访问顺序存储结构迁移操作、谓词操作的数据流分析对各程序点处指向动态内存的指针进行刻画, 从而实现内存泄漏缺陷检测算法的设计.

本文根据常见的内存泄漏缺陷, 将C程序中可能发生的内存泄漏缺陷总结为如下两类.

(1)   已成功动态分配的内存未释放.主要是指在程序中对分配的内存没有对应的释放操作或未在全部可能执行路径下释放内存导致无法正确释放内存.

(2)   分配与释放不匹配.主要是指释放的内存空间与分配的内存空间大小不符, 如图 2示例代码1, 在L16行执行对指针buf的赋值操作后, buf指向连续内存的7号单元, 而在执行L18行free(buf)操作后, 造成内存泄漏, 未将内存0单元~6单元成功释放.

针对上述情况, 本文以函数为单位, 提出一种内存泄漏检测算法, 用于有效检测C代码中出现的上述内存泄漏缺陷.本文假定在程序点l处, MePtr^l={$\langle$Memory₁, Pointer₁$\rangle$, $\langle$Memory₂, Pointer₂$\rangle$, …, $\langle$Memory_n, Pointer_n$\rangle$}, 其中, Memory_i为动态分配后连续内存的对应区域或连续内存的某个单元对应区域, Pointer_i={p₁, p₂, …, p_n}为指向Memory_i的指针变量集合.在进行内存泄漏缺陷检测时, 首先对控制流图节点上与动态分配内存相关的指针进行识别, 并根据归纳的迁移操作计算其存储状态信息, 同时更新MePtr^l.

对于一个控制流图G, 假定程序动态分配连续内存对应区域为r, 由指针p指向, 则在不同的控制流图节点, 对MePtr^l执行不同的更新操作.

(1)   在内存分配节点, 将分配的区域r与指针p添加至MePtr^l.

(2)   在执行指针相关迁移操作的控制流图节点上, p可能指向其他区域或有新指针q指向区域r或r的某个单元r[i], 此时对MePtr^l执行相应的更新操作.若更新之后, MePtr^l中某区域r对应的指针变量集合Pointer为空并且MePtr^l中没有其余与区域r基址相同的区域(或存在基址相同的区域r₁, 但r₁对应指针变量集合均为空), 则发生内存泄漏, 并将区域r及其指针变量集合从MePtr^l删除.

(3)   在释放内存节点, MePtr^l对释放的区域r, r[i]及对应的指针集合执行删除操作.对于p指向的每一个区域r不为wild, 若O^l$\left[\kern-0.15em\left[ r \right]\kern-0.15em\right]$不为[0, 0], 则释放内存大小与分配大小不一致; 否则, 将区域r及其对应的指针变量集合从MePtr^l中删除.

(4)   在语句块结束节点或程序退出节点, MePtr^l将根据指针变量的作用域进行更新, 将该语句块包含的指针变量在MePtr^l中删除.若删除后MePtr^l中某区域r对应的指针变量集合Pointer为空并且MePtr^l中没有其余与区域r基址相同的区域(或存在基址相同的区域r₁, 但r₁对应指针变量集合均为空), 则发生内存泄漏, 并将区域r及其指针变量集合从MePtr^l中删除.

下面是本文提出的内存泄漏缺陷检测算法.

算法2.内存泄漏缺陷检测算法.

输入:控制流图G.

输出:缺陷检测表mdb=$\langle$line, variable, type$\rangle$, 包括发生内存泄漏缺陷的语句行数、指针变量及内存泄漏类型, type=0表示未释放内存, type=1表示释放内存大小与分配大小不符.

说明:

●  getPointer(r)为获得区域r在MePtr中对应的指针变量集合;

●  getRegion(·)为获得MePtr中所有的区域;

●  delete(r)为从MePtr中删除区域r及其对应的指针变量集合;

●  delete(r, p)为从MePtr中区域r对应的指针变量集合中删除变量p;

●  node.getTreeNode(·)为获得控制流图节点对应的抽象语法树节点ASTtreenode;

●  ASTtreenode.getScope(·)为获得抽象语法树节点上对应作用域中的变量集合.

Begin

1:    let MePtr=Ø

2:    for each node in G

3:      if node is mallocNode

4:        add Region and PointerSet to MePtr;

5:      if node is migrationNode

6:        for each pointer p in node

7:          compute data flow value of p by migration operation rules;

8:          update Region and PointerSet in MePtr;

9:          for each r₁ in MePtr.getRegion(·)

10:            if MePtr.getPointer(r₁)==Ø

11:          let r₂ as other Region in MePtr.getRegion(·);

12:            if B^l$\left[\kern-0.15em\left[ r_2 \right]\kern-0.15em\right]$ orB^l$\left[\kern-0.15em\left[ r_1 \right]\kern-0.15em\right]$ or B^l$\left[\kern-0.15em\left[ r_2 \right]\kern-0.15em\right]$==B^l$\left[\kern-0.15em\left[ r_1 \right]\kern-0.15em\right]$ and MePtr.getPointer(r₂)==Ø

13:                type=0; add line, MePtr.getPointer(r₁) and type to mdb;

14:                MePtr.delete(r₁);

15:      if node is freeNode

16:        if P^l$\left[\kern-0.15em\left[ p \right]\kern-0.15em\right]$!=wild

17:          for r in P^l$\left[\kern-0.15em\left[ p \right]\kern-0.15em\right]$

18:              if O^l$\left[\kern-0.15em\left[ r \right]\kern-0.15em\right]$!=[0, 0] type=1; add line, p and type to mdb;

19:             else MePtr.delete(r);

20:        if node is exitNode

21:          let ASTtreenode=node.getTreeNode(·);

22:          let scope=ASTtreenode.getScope(·);

23:          for r in MePtr.getRegion(·)

24:            for p in MePtr.getPointer(r)

25:            if p in scope MePtr.delete(r, p);

26:          for r1 in MePtr.getRegion(·)

27:            if MePtr.getPointer(r₁)==Ø

28:            let r₂ as other Region in MePtr.getRegion(·)

29:            if B^l$\left[\kern-0.15em\left[ r_2 \right]\kern-0.15em\right]$orB^l$\left[\kern-0.15em\left[ r_1 \right]\kern-0.15em\right]$ or B^l$\left[\kern-0.15em\left[ r_2 \right]\kern-0.15em\right]$ ==B^l$\left[\kern-0.15em\left[ r_1 \right]\kern-0.15em\right]$ and MePtr.getPointer(r₂)==Ø

30:              type=0; add line, MePtr.getPointer(r₁) and type to mdb;

31:             MePtr.delete(r₁);

End

对于图 2的代码片段, MePtr^l的变化过程如图 8所示.

5 实验

本文的实验是在DTSC^[30]缺陷检测系统基础上做进一步的研究.DTSC是一款静态缺陷检测工具, 它通过分析程序源代码识别并得出代码中可能存在的缺陷, 其缺陷检测流程如图 9所示.在DTSC检测缺陷过程中, 源程序依次转换为抽象语法树、符号表、控制流图等结构, 同时利用函数调用关系、定义-使用链及数据流分析实现缺陷检测.为了验证本文所提方法的有效性, 在DTSC系统中实现了本文提出的SeqMM模型及分析方法, 通过对5个开源工程进行迁移操作、谓词操作的统计验证本文研究的必要性, 并对本文提出的内存泄漏缺陷检测算法的精度与效率进行对比分析.

5.1 访问顺序存储结构迁移、谓词操作统计

本文对5个开源工程中上述指针访问顺序存储结构的迁移操作、谓词操作统计结果如表 5所示.本文按照操作的出现顺序依次对每个操作进行编号, o₁代表p=q+expr, o₁₁代表p > = & a.

由表 5可以看出, 迁移操作在C程序中出现频率较高, 地址访问迁移操作大约为8个/KLOC, 值访问迁移操作大约为11个/KLOC.在地址访问迁移操作中, 超过50%为指针的自加操作, 超过41%为指针变量与整型表达式组成的地址表达式之间的赋值操作, 最少的是指针的对数组元素取地址与整型表达式组成的地址表达式的赋值.在值访问操作中, 通过对指针变量直接取值或利用指针变量引用顺序存储结构均在C程序中被大量使用, 其中通过指针引用顺序存储结构元素约占53.8%.

此外, 由表 5可以看出, 指针相关谓词操作在C程序中较少出现, 其中, 使用最高为指针与整型表达式组成的地址表达式的比较; 同时, 指针与取地址表达式的比较在5个开源工程中未出现.

综上所述, 顺序存储结构及其上的操作在C程序中被广泛使用.本文的工作聚焦这一方面, 具有针对性, 能够有效提高数据流分析的准确性, 为检测C程序中顺序存储结构相关的缺陷奠定基础.

5.2 内存泄漏缺陷检测对比实验

本文提出的内存泄漏缺陷检测算法已在DTSC中实现.本文在上述开源工程中手工植入第4节提出的两类内存泄漏缺陷, 并使用DTSC_SeqMM, Klocwork12, DTSC_RSTVL对工程分别进行内存泄漏的缺陷检测, 以此验证DTSC_SeqMM及提出的内存泄漏检测算法的有效性, 实验结果见表 6.表 6中列出了被测项目的分析时间、不同工具测试输出的检查点(IP)、缺陷数(RD)及相对漏报(RFN).相对漏报数指的是不同工具间的相对于缺陷总数的漏报数量, 缺陷总数(FB)为3个工具测出的缺陷总计.

衡量检测精度的误报率(FPR)与相对漏报率(FNR)分别为:

$ \begin{align} & FPR=\frac{IP-RD}{IP}\text{, } \\ & FNR=\frac{FB-RD}{FB}\text{.} \\ \end{align} $

经过人工确认并对检测结果进行对比分析可得, DTSC_SeqMM检测出的缺陷包含Klocwork12与DTSC_ RSTVL检测出的所有缺陷, 对于所有实验用例, DTSC_SeqMM, Klocwork12, DTSC_RSTVL的误报率分别为27.9%, 14.4%, 35.8%, 相对漏报率分别为0, 10.7%, 7.5%.说明本文实现的DTSC_SeqMM与内存泄漏缺陷检测算法能够有效分析C程序, 并降低漏报.

图 10为本文手工植入的释放空间与分配空间不符的内存泄漏缺陷.

Klockwork12与DTSC_SeqMM均能检测出因654行test2_implanted的释放而造成的内存泄漏, 而DTSC_RSTVL却漏报了该缺陷.在653行指针test2_implanted执行的自加操作导致其偏移一个单元, 因此在654行对其释放, 则使得在651行分配成功的内存未完全得到释放, 发生内存泄漏.因为DTSC_RSTVL缺少对指针偏移的刻画, 故无法对指针访问顺序存储结构的迁移操作与谓词操作进行识别, 导致了此内存泄漏缺陷的漏报.

同时, 从表 6中也可以清晰地看出, DTSC_SeqMM较其余两种检测工具时间开销增加明显.因为DTSC_ SeqMM比DTSC_RSTVL能够描述更多的变量与操作信息, 同时在检测内存泄露时, 需要对MePtr^l频繁地进行查询与修改操作, 故在检测过程中效率有所降低.

综上所述, 本文的实验结果表明, 本文提出的数据流分析方法能够对带顺序存储结构的C程序进行有效的描述.同时, 本文的内存泄漏缺陷算法对本文提出的两种类型缺陷具有准确的检测效果.

6 结束语

本文通过对顺序存储结构的刻画与描述进行研究, 提出了用于顺序存储结构数据流分析的抽象内存模型SeqMM, 总结指针相关的迁移与谓词操作, 并对遍历顺序存储结构的循环操作、函数调用时形参指针引用顺序存储结构元素进行分析.该模型将指针的指向关系与数值性质进行有效结合, 对访问顺序存储结构的操作进行分析, 解决了现有数据流方法未能对顺序存储结构进行精确分析等问题.同时, 将上述分析结果应用于内存泄漏的缺陷检测.实验结果表明, 本文提出的内存泄漏缺陷检测算法在效率降低的可接受范围内, 实现对工程的有效检测.在下一步的工作中, 我们将着重提高设计模型的分析能力, 降低数据流分析结果的误报率, 在本文工作的基础上进行完善提高.