跟踪机制引导的C程序内存错误自动修复

董玉坤，位欣欣，孙玉雪，唐道龙

中国石油大学（华东）计算机科学与技术学院，山东 青岛 266580

程序缺陷是软件开发及维护工作中难以避免的副产品，可引起软件故障甚至是系统崩溃[1]。如何尽早的检测并修复程序缺陷一直是研究人员关注的重点。学术界已就缺陷定位、缺陷检测进行了大量工作[2-6]，但对检测出的缺陷进行人工修复依然耗费大量人力物力[7]。程序自动修复[8-12]基于给定的错误程序自动生成修复补丁，进而修复程序缺陷。其修复过程中产生的补丁可以直接用于修复程序，也能够帮助开发人员改进代码，在一定程度上为开发人员缩短修复时间。然而不同类型程序缺陷的产生原因及引发后果不尽相同，利用统一的自动修复框架或方法进行缺陷修复，每类缺陷修复成功率低，同时容易引入新的错误。因此研究针对特定类型缺陷的程序自动修复方法尤为重要。

C 程序中的内存错误，如内存泄漏（memory leak，ML）、释放后使用（use-after-free，UAF）和双重释放（double-free，DF），在C 程序中非常普遍，但很难修正。例如内存泄漏便是C 程序动态内存分配及释放方面常见的程序缺陷[13-14]。通常情况下，内存泄漏不会产生可直接观察的错误状态，而是逐渐积累，造成系统内存的浪费并可能引发系统安全威胁，持续运行下可造成软件崩溃[15]。尽管研究人员已提出多种方法进行程序中内存错误修复，但存在着明显的缺点。首先，有些方法将缺陷检测与缺陷修复分为两个割裂的过程，缺陷检测的过程信息与结果信息在缺陷修复时未被充分利用，导致缺陷修复时敏感路径分析精度降低，耗费时间长或者可扩展性低。其次，有些方法可以保证扩展性，应用到大型项目，但是可能在修复的过程中引入新的错误[16]。最后，有些工具为了保证安全修复缺陷，选择性的执行路径敏感分析，虽然可以保证可扩展性，但造成缺陷报告中的缺陷被遗漏。

本文提出了一种内存错误自动修复方法，结合已被过滤的缺陷报告信息，不管缺陷报告中的内存错误是真正的错误还是误报（false positive，FP），在保证安全的前提下，对缺陷报告中的错误进行全部、尽早的修复。为了实现安全修复，本文提出了一种基于全局指针的跟踪机制，跟踪与动态内存分配过程和函数调用有关的分配表达式，确保正确释放分配内存；同时利用构造的作用域树，提出一种新的故障定位技术，只有在确信缺陷得到修复而不违反其他安全条件时才插入补丁。该方法在保证可扩展性的同时，实现对报告中的全部错误的修复；对于某些未释放的内存，在其作用结束点及时释放，实现尽早修复，避免内存空间的浪费。

结合内存错误的检测与修复，在DTSC[17]的基础上实现了原型工具DTSFix，DTSC（deefect testing system for C）是面向缺陷软件测试系统——DTS 的重要组成部分之一，主要用于针对C 程序的面向缺陷测试。DTSFix是DTSC在检测缺陷的基础上，研究缺陷自动修复的拓展功能，处理过程如图1 所示。在DTSC 中加入作用域树，然后对源程序进行第一次缺陷检测，输出缺陷报告（defect report，DR）。DR 包括缺陷发生文件、分配位置、分配表达式和可能发生内存错误的行，从而指导缺陷检测以及后续的缺陷修复[18]。依赖缺陷报告以及检测过程中的函数摘要（function summary，FS）[17]信息，试图插入一个全局指针作为探针，以追踪缺陷报告中发生错误的分配内存，即本文提出的跟踪机制。跟踪机制完成后，着重对DR中的缺陷进行第二次检测，过滤DR中的部分误报，为后续自动修复减少干扰，并再次输出缺陷报告DR′。基于缺陷报告DR′，针对不同的内存错误，依赖全局指针生成相应的补丁；作用域树中的每个树结点存储变量属性信息，通过遍历指向分配内存区域的变量的作用分布，计算分配内存最后的作用结点，定位故障的修复位置。

图1 DTSFix工作框架Fig.1 Working framework of DTSFix

本文做出了以下贡献：

（1）构建了一个描述变量作用范围信息的作用域树。首先将输入的源程序解析为抽象语法树（abstract syntax tree，AST），之后基于AST 构造了一个记录变量在可达语句片段的活性信息的作用域树，树结点存储在此程序片段可能出现的变量集合，研究人员可以利用树的结点信息搜索分析变量的可达树结点，并将其应用于定位缺陷修复位置，保证修复缺陷又不会产生副作用。

（2）提出基于全局指针的跟踪机制。基于缺陷报告分析结果，插入全局指针跟踪发生错误的分配内存，跟踪分配内存的访问偏移信息。然后基于全局指针生成补丁，避免分配内存被错误或部分释放。

（3）构建了基于跟踪机制的内存错误自动修复工具DTSFix。增加作用域树以及跟踪机制后，提高对内存缺陷的检测精度，降低缺陷误报率，完成对内存错误的自动修复，实现对大型开源C 程序项目的内存错误修复。

1 相关工作

近些年，研究人员已对多种缺陷类型进行通用的自动修复框架及方法设计，主要可归结为基于搜索的程序修复、基于人工模板的程序修复与基于语义的程序修复。这些方法多基于缺陷定位方法对源代码语句按照可疑值进行排序，将疑似缺陷的位置依次传输给补丁生成算法[19-20]以完成程序修复。基于搜索的修复方法[21-24]利用元启发式方法、演化算法等优化算法在庞大的搜索空间中反复寻找补丁程序，并通过配套的测试用例集进行补丁正确性验证。基于语义的程序修复方法[25-28]利用符号执行推导出正确补丁的约束条件，并使用程序合成或约束求解来合成补丁。基于人工模板的程序修复[29-31]，根据开发者或研究人员的经验预定义一些补丁模板或者补丁生成策略来生成补丁，用于指导修复特定类型的缺陷。此外，除上述方式外，研究人员还关注了其他形式的程序修复方法。文献[32]提出了CodePhage 算法，该算法可以在被修复应用中定位缺陷，同时从其他应用迁移代码来消除缺陷。该算法可修复指定缺陷，如整数溢出、缓冲区溢出及零除数等。文献[33]提出了基于机器学习的Getafix，它可以从以往提交的代码中找到缺陷修复模式，然后对所有候选补丁进行排序，并推荐最合适的修复补丁。而且，最近几年由于人工智能领域的迅速发展，一些智能化的新技术也被应用到程序修复领域中[34-36]。

在内存错误自动修复方面，文献[37]基于可靠的静态分析提出了MemFix，为分配内存未释放、多次释放、释放后再使用3 种内存错误类型提供了统一的解决方案，但它的可扩展性低，无法生成条件补丁，不足以分析基准程序。文献[38]利用指针分析与数据流分析实现了针对C 程序内存泄漏自动修复工具leakFix。该工具可求解释放操作的安全插入位置，保证修复后程序的正确性，但是可以修复的内存泄漏的类型种类比较少，只能修复一小部分的内存泄漏。文献[39]针对资源泄漏、内存泄漏和空指针引用3 种类型缺陷实现了FootPatch方法，该方法利用静态方法检测和修复指针安全属性违反问题，通过分离逻辑生成补丁，并对输出的补丁程序进行形式验证，但是，FootPatch仅根据给定的错误报告检查补丁的正确性，并不能确保安全，并且可能会引入新的错误。文献[40]针对内存错误提出新的技术SAVER，它对主要敏感路径创建对象流图，依据对象流图中各个对象的路径判断是否有泄漏，并提出相应模式的补丁。SAVER 对真正的缺陷执行修复，且插入的补丁不会对源程序产生副作用，但是它需要定义程序和错误报告作为输入，选择性的构建对象流图，当缺陷涉及自定义分配函数或释放函数时，SAVER便无法修复错误。

2 作用域树

为获取变量在生命周期内的作用范围，或者分析某位置使用的变量应该匹配哪层作用域内的变量声明，以分析该变量的可能取值，通过构建作用域树来表示变量在程序中的逻辑关系，描述变量的作用分布。

DTSFix以.c文件为单位进行分析，定义3种作用域以标识变量的作用分布。分别为源文件作用域（source file scope，SFS）、函数作用域（method scope，MS）、局部作用域（local scope，LS）。一个文件只有一个SFS，MS对应着定义的函数，LS 对应着函数体内的一个块。其中块有3 种属性，分别是简单语句块LS～、判断分支块LS^、循环块LS*。作用域之间具有包含关系，每个作用域看作一个树结点，形成一个树状数据结构。各作用域的封装信息以及之间的包含关系为：

对于SFS，封装外部声明的变量集合Evar，外部声明的函数集合Func，.c 文件中的函数集合M，文件名sfs以及文件存储位置file；一个.c文件中有且仅有一个SFS结点，在SFS结点下含有0个或多个MS孩子结点。其中，Evar 中的每个Evari，封装此变量的名称var，定义行Linedef，一个或多个使用行Lineuse；Func中的每个funci，封装此外部声明的函数的名称func，声明行Linedec；M中的每个mi，封装此函数的函数名称func，函数开始行LSstart，函数结束行LSend。

对于MS，封装形式化参数变量集合Fvar，函数中的语句块集合Ls，函数的名称func以及函数开始行LSstart，函数结束行LSend；每个MS 结点下含有1 个或多个LS孩子结点。其中，LS 中的每个Fvari，封装的此变量的定义行Linedef，也即是函数开始行LSstart；Ls中的每个ls i，封装此语句块的类型style，语句块开始行LSstart，语句块结束行LSend。

对于LS，封装局部变量集合Var，语句块的类型style，语句块开始行LSstart，语句块结束行LSend；每个LS结点下含有0个或多个LS孩子结点。若语句块中存在中断语句return、break、continue，且中断语句所在行与语句块结束行不同时，那么中断语句所在行也是语句块结束行，另外，对带有return 语句的LS 结点做标记。其中，style有3种类型，简单语句块LS～是连续的基本语句，循环块LS*是while或者for循环体，判断分支块LS^，是if或者switch…case分支语句。其中LS^具有一些特殊性，每个分支便看作一个作用域，如果存在if，else if，…，else连续分支，第一个分支看作，剩余的看作。

作用域树各个结点之间的关系利用结点开始行以及结束行来寻找，从而构建一个.c 文件的作用域树，其中树结点的孩子结点有左右顺序。各个结点连接规则如下所示。

连接SFS类型结点s与MS类型结点：

ms是MS类型结点，schild是s的孩子结点集合，若ms与m的开始行信息一样，则ms属于s孩子结点，连接ms与s结点。其中s孩子结点的左右顺序由其孩子linestart决定，若∃m,m′∈MS,m.linestart＜m′.linestart，则结点m在结点m′左侧。

图2 作用域树示例Fig.2 Anexample of scope tree

3 内存错误检测

内存错误是程序开发人员在编码时，由于设计疏忽或考虑不全面导致的。程序调用malloc 等函数动态分配内存空间，调用free等函数释放分配的内存空间。如果程序开发人员没有在合适的位置释放内存或者没有正确的进行释放操作，比如在程序执行不了的分支路径上进行释放操作，或者在程序执行路径上遗漏了free操作，将导致内存泄漏。同样的，如果程序开发人员多次释放内存对象或者引用已经释放的内存对象，将会导致DF或者UAF[41]。

一般有两种检测内存错误的方法，分别是静态和动态检测技术。由于内存错误的隐蔽性，静态检测技术优先于成本较高的动态检测技术[42]。源程序的静态缺陷检测产生了大量的缺陷信息，可以帮助自动程序修复产生补丁，以提高程序修复的准确性[18，43]。

如图3是一个缺陷程序示例。在程序中，f1 是一个内存分配函数，m、p、q均为局部指针变量，图3（a）中，在第8 行，f1 函数的返回值赋值给指针变量p，在第9行，当a＞0 时，q=p，然后在第15行释放内存。但是在第11 行至14 行，当执行else 分支时，再次调用f1函数，返回值赋值给指针变量q，释放p，这时在第15行，第8 行分配的内存可能发生DF，而在第16 行，在函数结束时，第12行分配的内存可能发生ML。

图3 缺陷程序示例Fig.3 Example of defect program

3.1 基于全局指针跟踪分配内存

C 程序中对某一内存的分配与释放往往存在于不同函数中，同时，函数返回值及受副作用影响的表达式均可对动态分配内存进行操作。本文利用函数摘要的思想对指向分配内存的函数返回值及受副作用影响的表达式进行表示与确定，以保证全局指针可正确跟踪可能发生错误的分配内存。

本文获取的部分摘要信息如下：

其中，EV为一个二元组集合，封装的是受副作用影响的外部表达式（可计算为全局指针或实参指针的表达式）及其抽象取值。RE为一个二元组集合，封装的是函数返回表达式及其抽象取值，若外部变量及函数返回值均指向动态分配内存时，则Domain 为指向内存单元的抽象地址。

定义1（分配表达式（allocation expression，AExp））分配表达式为在程序分配行获取动态分配内存首地址的表达式，其最终取值为指针。在程序分配行的语法可归纳为：

其中exp是整型参数，FunMalloc()指代自定义内存分配函数。

对于图3（a）的程序例子，变量p、q均为分配表达式，从函数摘要中得到的函数返回的内存信息[17]如下：

在DTSFix 基于跟踪机制检测内存错误之前，它事先进行静态分析，然后输出一份缺陷报告DR。对于缺陷报告中的每个错误，DTSFix 声明全局指针去跟踪报告中的分配内存。

void*Probe_FileName_Number

声明的指针为void*类型，任何类型的指针都可以直接赋值给void指针，而无需进行其他相关的强制类型转换。请注意，void 指针不指向具体的数据类型，只表示用来指向一个抽象的类型的数据，即近提供一个纯地址，而不能指向任何具体的对象，因此，需要避免对void指针进行算术操作。

算法1描述的是跟踪发生错误的分配内存的过程，对于报告中的每条缺陷，首先声明全局指针，从源程序的AST中检索出第一个外部声明结点，映射获得这个结点对应的代码段的开始行，即全局指针的插入位置，在全局指针插入之前，获得源程序P 的符号表，以避免全局指针的命名与程序中的变量之间的冲突；然后进行令全局指针跟踪这个缺陷的分配内存。依据函数摘要以及作用域树的分布位置，帮助全局指针精准跟踪DR中发生错误的分配内存，监督分配内存的生命周期。

在动态分配内存语句之后都插入跟踪语句，避免调用分配函数后，内存返回值没有指向，导致地址丢失。如果分配内存在当前分配函数中没有使用，且存在返回值或受副作用影响的外部表达式在另一个函数，则声明新的全局指针跟踪返回值或受副作用影响的外部表达式。在图3（b）中，DTSFix 首先依次分析缺陷报告中的每个缺陷信息，例如针对在第15行的缺陷，p可能发生DF，声明相应的全局指针Probe_f2_1。然后找到错误内存的分配行L8，全局指针指向分配行的分配表达式p，以便跟踪其生命周期。

3.2 缺陷过滤

插入全局指针，实现对缺陷报告中全部错误内存的跟踪。然后，DTSFix 利用函数调用关系和数据流分析来确定程序中全局指针的抽象存储状态。最后，对全局指针的状态分析，检测是否存在缺陷。当缺陷检测完成后，可能发生内存错误的分配内存的相关信息将被记录，输出过滤的缺陷检测报告DR′。

4 基于跟踪机制的内存泄漏自动修复

4.1 缺陷报告

DTSFix第二次对源程序执行缺陷检测并输出DR′，报告包括可能发生内存泄漏的程序文件、内存分配行、分配表达式，以及泄漏发生行等，与DR相比，添加了全局指针列。DR′如表1所示。

表1 缺陷报告Table 1 Defect report

4.2 跟踪机制

C 程序中往往通过分配表达式灵活访问动态分配的连续内存，其中涉及的访问操作、指针偏移、函数调用等可能导致动态分配内存的地址信息丢失，引起内存泄漏。全局指针在指向未发生变化的情况下，可在整个源程序内跟踪动态分配内存，对可能丢失的动态分配内存地址进行记录，以弥补指向丢失。

如图4 为包含全局指针的程序实例及其简化的控制流图。其中图4（a）是一个代码片段，存在一个全局指针指向动态分配内存。图4（b）中m为L3 行分配内存的地址，m+1 表示动态分配内存地址m后的单元，可以看出在函数f未对全局指针p进行偏移、赋值等操作的情况下，全局指针p可跟踪m直至作用域结束。正是全局指针的可跟踪机制使得只需在程序合适位置执行释放操作，避免内存部分释放。

图4 程序实例及其简化的控制流图Fig.4 Example of program and its corresponding simplified control flow graph

4.3 修复位置定位

在以M0为根结点的子树中，若O分布在多个return结点lsreturn，则l可能会有多个，l定位在各个没有释放语句的lsreturn出口前。

在以M0为根结点的子树中，若存在1 个或0 个return结点，O作用分布的LS结点的最低层，统称C层，C层结点的父结点所在层，即P层，P层结点的父亲结点所在层为2P层，依次类推。

其中，(m-1)PLi是O在(m-1)P层作用分布的LS结点或者低一层O作用分布的LS 结点的父结点，k是与r没有关系，可能是1或者大于1。

修复位置已经定位到F层，然后定位修复位置所在结点：

在函数结点M是递归的情况下，如果O出现过的LS 结点只有一个MS 类型父结点M，则O可以在M中定位修复位置;否则，对O的修复必须定位在M及其子结点之外的其他结点，以确保安全修复。

图5 图3示例程序对应的作用域树Fig.5 Scope tree corresponding to sample program in Fig.3

4.4 内存错误自动修复

本文中DTSFix通过对C程序执行添加语句的操作以生成补丁代码段。该过程可归结为函数F={FML,FDF,FUAF}的求解过程，分别表示为未释放、多次释放、释放后使用。

其中，FML=fix(p,lML)，lML是计算得到的泄漏内存的修复位置，表示在lML处分配内存作用域将结束的释放操作，该操作使得根据全局指针p正确释放分配内存；FDF=fix(p,lDF)，lDF是DR′中的DF发生行之前，表示在lDF处对全局指针p取值判断是否非空，然后插入操作以修复双重释放泄漏；FUAF与FML类似，删除错误发生行的free语句，通过计算分配内存最后的作用分布位置lUAF。通过对函数P的正确求解即获得错误程序的修复补丁。基于跟踪机制生成补丁和修复缺陷的过程如算法2所示。

如图6显示了图3的内存错误的自动修复情况。在图6中，根据表2的信息，由p指向的分配内存可能在第15 行发生DF。因此，修复补丁被插入到第15 行之前。此外，q可能出现ML，通过分析文件作用域树之后，发现泄漏的内存的最外层作用点是L16前，所以在此处插入补丁释放分配内存。

表2 图3实例的检测结果Table 2 Detection results of example in Fig.3

图6 图3示例程序的修复结果Fig.6 Repair results of Fig.3 sample program

同时，在对跨文件的内存的动态分配存在类似处理方法，即在调用内存分配函数文件中确定动态分配内存的分配行，并利用全局指针进行状态跟踪，直至作用域结束完成释放。

5 实验设计与结果分析

本章对DTSFix 进行了实验评估，主要目的是：（1）评估DTSFix在第二次缺陷检测之后，过滤报告中误报的效果；（2）评估它在实践中修复内存错误的有效性，主要观察它对ML、DF、UAF 缺陷类型的修复效果，以及针对误报，插入补丁后对源程序的影响。本文还将DTSFix 与现有的修复内存错误技术MemFix、Saver进行比较。所有的实验都是在一台装有Intel Core i5-8500和16 GB内存的主机上进行的。

5.1 数据集基准

本文用两个基准集评估了DTSFix：一组是从流行的开源C语言库中抽象出来的模型程序[37]和一组开源C程序[40]。第一个基准集是由MemFix 创建的，从5 个开源存储库构建的总共100个模型程序，平均每个程序代码行大概有200行，最大的代码行是440行。其中，一个程序只包含一个错误，每个程序都尽量保留了程序的原始特性，以便在模型程序中与错误相关的部分保持完整，虽然模型程序与原始程序相比较小，但修正其中的错误并不容易。表3横轴和表4第一列显示了从开源存储库构建的模型程序的结果，目的是评估修复工具针对内存释放错误的修复效果。第二个基准集是开源的C程序，由从GitHub 收集的5 个基准构成，分别是flex、WavPack、Swoole、Snort和p11-kit，如表4、表5第一列所示。这5个程序也被Saver工具应用，用于评估Saver关于内存错误的修复效果。DTSFix 与Saver 利用此数据集对比修复内存泄漏的效果，同时列出并分析DTSFix对此数据集中内存泄露的修复效果和时间，以充分例证本文方法的有效性。

表3 DTSFix和MemFix修复内存错误的对比结果Table 3 Comparison results of DTSFix and MemFix fixing memory error

表4 DTSFix和Saver基于开源C程序的内存泄漏修复效果Table 4 Repair effects of DTSFix and Saver on memory leak based on open-source C programs

表5 DTSFix对开源C程序的内存泄露的完整修复结果Table 5 DTSFix complete repair results of memory leakage of open-source C programs

5.2 实验设计实现

本文的实验验证是基于DTSC 检测系统的进一步研究，并实现了原型工具DTSFix，重点是真正地实现修复内存错误的目标，而不是优化其检测功能。本文对基准进行缺陷检测，获得含有错误内存信息的DR。然后在源程序中插入全局指针来追踪报告的分配内存，执行缺陷过滤。最后，基于缺陷类别来确定修复补丁模式。利用作用域树计算修复位置，插入合适的修复补丁。在这个过程中，DTSFix检测和修复是一体化的，可以直接在修复过程中使用缺陷检测的过程信息和结果信息。DR 中的缺陷信息帮助在原程序中插入全局指针，而在检测过程构建的作用域树用于寻找补丁插入位置，对源程序插入的全局指针用于缺陷检测和补丁生成。

DTSFix 的修复原则上是安全的。第2 章实现的作用域树和第3.1 节实现的基于全局指针跟踪分配内存，目的便是找到安全释放位置以及将动态分配的内存地址正确释放。请注意，DTSFix 不准确（不完整）的静态分析或预分析可能会导致较低的修复率，但不会损害程序的安全性。在故障定位时，搜索的补丁插入位置是发生错误的分配内存最末尾的活性位置，且在此位置之后，没有对此内存区域的引用，保证插入补丁后不会对源程序产生威胁。另外，基于全局指针生成的补丁包含断言，因此避免补丁插入程序后部分修复缺陷或者引入新的错误。

5.3 实验结果与结果分析

如图7 显示了DTSFi 两次检测抽象模型程序的结果。其中柱状图的横轴是基准集的5 个项目（Binutils、Git、OpenSSH、OpenSSL 和Tmux），每个项目分别含有20个程序；纵轴是工具报告的缺陷检测数量；FP表示第一次检测项目中报告的误报数量，FP′表示第二次检测报告的误报数量；ML、DF、UAF分别表示第一次缺陷检测报告的各种缺陷数量，ML′、DF′、UAF′分别表示第二次缺陷检测报告的各种缺陷数量。

如图7 所示，5 个程序上第一次执行缺陷检测后，DR总共报告了155个缺陷，为了评估DTSFix，手动分类检测结果，将缺陷分为49 个缺陷和106 个误报。工具（自动地）对第一次缺陷检测过程信息处理，在待测程序中插入全局指针跟踪DR中指出的分配内存，然后第二次执行缺陷检测，DR′总共报告了90个缺陷。手动分类后发现，其中各个项目的减少的误报个数分别是Binutils（9 个）、Git（13 个）、OpenSSH（8 个）、OpenSSL（12 个）和Tmux（23 个）。程序中插入的全局指针跟踪内存对象的访问操作、指针偏移、函数调用等，记录内存对象的动态变化信息，帮助缺陷检测更准确地分析错误分配内存在程序点的状态，从而减少误报。同时也发现两次检测结果中，报告中的真实缺陷数量没有改变，在两次检测结果中，对各个项目检测到的真实缺陷数分别是Binutils（9个）、Git（7个）、OpenSSH（13个）、OpenSSL（11个）和Tmux（9个）。

表3 显示了DTSFix 和MemFix 修复模型程序的结果。#Pgm 表示缺陷数，表格第2、3、4 列表示DTSFix 与MemFix 相比，分别修复内存错误的数量。与MemFix相比，DTSFix能够修复其中的49%（49/100）。对于内存泄漏（ML），DTSFix平均成功修复了56%（28/50）。对于双重释放（DF）和释放后使用（UAF），DTSFix 能够修复54.2%（13/24）和30.8%（8/26）。对于Tmux程序中的DF和UAF，MemFix 未能修复它们，而本工具对此突破了零修复率。这是因为当代码中隐含地存在隐式释放语句时，MemFix不能修复在这些程序中发现的错误（例如UAF）。DTSFix 修复缺陷的数量与其缺陷检测的结果有直接关系，它可以保证DR′报告的真实缺陷全部安全修复。

同时，在修复工作进行前，对DR′的准确性没有进行人工判断。换句话说，在不清除误报的情况下，对错误报告中的所有内存错误记录进行统一的缺陷修复处理。对误报的修复并不影响程序的执行路径，仍然可以保证其正确性。如图8 所示，图（a）是没有缺陷的一个程序实例（即误报），图（b）是对图（a）的修复。经过人工判定，插入的修复补丁对源程序没有任何副作用。

图8 修复误报对程序的影响Fig.8 Impact of fixing false positives on program

对于Saver和DTSFix生成的每个补丁，手动检查补丁是否正确修复了目标缺陷。对于修复真实缺陷的补丁，如果它完整地修复内存泄漏（例如，在缺陷的所有执行路径上都保证释放了内存），并且没有引入新的错误，将定义这个补丁是正确的（√T）。如果生成的补丁引入了一个新的错误，将其视为不安全的（×T，×F）。工具的修复率计算公式为：

缺陷修复率=修复缺陷数量/缺陷待修复数量

实验结果如表4 所示。缺陷检测阶段已经实现作用域树的构建以及对泄露内存的跟踪，因此修复阶段执行故障定位和补丁生成并不会耗费太多时间。Infer∩DR′报告有69 个缺陷待修复，对于其中的49 个真正缺陷，DTSFix为其生成了补丁，这些缺陷被完全正确地修复，修复率为71%（49/69）。Infer报告有107个缺陷待修复，其中有68 个真正缺陷，Saver 只完全正确地修复45个缺陷，修复率为42%（45/107）。DTSFix这种高修复率的一个关键因素是基于插入的全局指针生成补丁，对泄漏内存进行全程的跟踪。

为了确保补丁的安全性，修复工具Saver 对误报没有进行修复，因为在不引入错误的情况下修改已经正确的程序，这比将不正确的程序转换为正确的程序更具挑战性。值得注意的是，DTSFix为误报生成补丁，经过人工验证，插入的补丁没有引入新的错误。这是因为在故障定位时，确保插入位置之后不存在对泄漏内存的数据关系依赖，生成的补丁含有条件判断，不会引入DF。

表5 显示了DTSFix 检测以及修复5 个开源程序内存泄露的结果。#√表示工具在分析缺陷报告DR′的基础上，对缺陷的修复数量。#ALoc表示修复过程中插入补丁后，源程序新增的代码行。分析DR′发现，工具在检测开源程序中的DF和UAF结果很少，几乎没有检测到错误，而只是为基准测试产生误报。人工检查DR′后，只在P11-kit 程序中检测到1 个UAF，其余开源程序中并没有检测到，因此，表5 只展示了工具对开源程序中内存泄漏的检测与修复结果。

从表5可以看出，工具在检测阶段花费时间占整个过程的58%～84%（TDefect/（TDefect+TFix），TDefect是检测阶段花费的时间，TFix是修复阶段花费的时间），主要是因为构建作用域树以及实现跟踪机制都是在检测阶段实现的，生成补丁以及定位修复位置依赖前期工作，所以花费时间占比少。工具在没有引入新错误的情况下，总共正确修正了58个错误（修复率为59.8%）。而且，从表4和表5可以发现，工具修复缺陷的数量与其检测到的真实缺陷数量相同，工具可以修复全部DR′中的真实内存错误，同时不会给原程序引入新的错误。

在实验评估中，本文使用了两个开源数据集，但它们可能不具有代表性，或者不足以客观地评估错误修复工具的性能。本文的评估重点是DTSFix修复内存错误的情况，然而，修复只是原型检测工具的扩展应用，依赖检测过程产生的信息，目前还没有应用到其他工具上，对于修复方法的复用性未来还有很多工作要做。

6 总结

本文研究了由动态分配内存错误释放或未释放而引起的内存错误，提出了跟踪机制的自动修复方法，并实现了修复工具DTSFix。该工具实现检测与修复过程一体化，不必借助额外工具进行检测或者中间语言转换，保留处理过程细节，更大化地利用处理过程的反馈信息。实验结果表明，所提出的修复算法可以有效地修复C程序中的内存错误；另外，由DTSFix生成的补丁能够消除目标错误而不引入新的错误。在未来的工作中，将努力降低静态分析结果的误报率，提高修复位置的准确性。