程序缺陷自动修复研究进展及关键问题

曹鹤玲，刘 昱，赵晨阳，王玉华

1(河南工业大学 信息科学与工程学院，郑州 450001) 2(河南工业大学 粮食信息处理与控制教育部重点实验室，郑州 450001)

1 引 言

在软件开发过程中，不可避免地会产生缺陷，且随着软件规模和复杂度的不断增长，缺陷的数量也逐年增加[1]，有相当一部分人力和物力资源用于缺陷的定位与修复[2，3].如何能够有效降低软件维护成本，减少软件维护时间已经成为了一个亟待解决的问题.程序缺陷自动修复方法应运而生，其能节省大量的时间、人力和物力，具有极高的科研价值.该方法首先定位到可能含有缺陷的程序语句，并依据存在缺陷可能性的大小对可疑程序语句进行排序；然后利用各种补丁生成方式自动地生成对应的补丁；最后使用某种策略对补丁进行验证，并输出正确的补丁.通过该方法产生的补丁既可以自动添加到程序中，也可以为人工改进代码提供有用的指导[4].

早期的程序缺陷主要通过手工修复，然而程序缺陷数量的激增使得这项工作日渐繁重，手工修复的能力已逐渐不能满足需求.近年来，程序缺陷自动修复获得了广泛的关注，其已成为软件工程领域的研究热点，学术界也涌现出了大批的研究成果，产生了许多颇具影响力的贡献.尽管如此，程序缺陷自动修复仍处于初级阶段，只能修复部分缺陷，并且在工业界成功应用的案例少之又少，其进一步的发展还面临着许多的问题和挑战.

目前已有一些文献对程序缺陷自动修复问题进行了调研.在早期的工作中，Le Goues等人[5]对其团队核心研究工作的创新和不足之处以及当时程序缺陷自动修复方法面临的挑战进行了剖析，为以后的研究工作打下了良好的基础.玄跻峰等人[4]将基于测试集的程序缺陷自动修复方法划分为基于搜索、基于代码穷举以及基于约束求解的方法，并对上述3类方法进行了详细的论述.Monperrus[6]主要整理和总结了行为型修复(behavioral repair)方法和状态型修复(state repair)方法的重要研究成果.王赞等人[7]总结了缺陷定位阶段、补丁生成阶段和补丁验证阶段的研究进展，并梳理了程序缺陷自动修复领域的缺陷库和研究团队.李斌[8]等人从程序规约的角度对程序缺陷自动修复问题与技术进行了梳理和分析.Gazzola等人[9]结合108篇相关文献对程序缺陷自动修复领域的研究成果进行了回顾，对自动修复方法的能力进行了批判性的分析，并从3个方面分析了当时程序缺陷自动修复方法面临的关键挑战.此外，还有一些相关的研究工作，但经调研发现他们仅对以往传统的程序缺陷自动修复方法进行了详细综述，针对最新涌现出的如基于机器学习的程序缺陷自动修复方法等未有全面的研究综述.

基于此，为了便于研究者在现有研究工作的基础上取得更好的进展，非常有必要对目前程序缺陷自动修复方法的最新研究成果进行全面分析和总结.因此，我们首先在谷歌学术、IEEE、Web of Science、Springer、ACM和DBLP等搜索引擎和文献数据库中对2001年～2021年的相关文献进行检索，检索时采用的主要关键词包括“bug/defect/program/software/fault repair/fix”、“缺陷修复”、“程序修复”和“缺陷库”等，随后我们进一步筛选了检索出的论文，最终确定了与本文综述问题直接相关的高质量论文共79篇，其中包含发表于权威期刊(TSE(7篇)、TOSEM(3篇)、软件学报(4篇)、计算机学报(1篇))的论文共15篇，以及发表于权威会议(ICSE(15篇)、ICSME(1篇)、PLDI(1篇)、POPL(1篇)、ESEC/FSE(1篇)、ASE(5篇)、ISSTA(4篇)、AAAI(1篇))的论文共29篇.本文不仅吸纳了关于基于搜索和基于语义的程序缺陷自动修复方法的最新研究成果，还首次系统总结了基于机器学习的和基于错误报告驱动的程序缺陷自动修复方法.除此之外，将程序缺陷自动修复领域常用的缺陷库划分为了C/C++、Java和多种语言的缺陷库，并进行了系统地总结，特别梳理了缺陷库的适用场景以及对程序缺陷自动修复工作的贡献.最后，分析了程序缺陷自动修复在工业界的应用现状并总结了该领域面临的关键问题及未来研究的方向.

2 研究框架

程序缺陷自动修复方法针对各种不同的缺陷修复场景，将整个修复过程自动化[8]，实质上就是自动地定位程序缺陷、生成程序补丁并进行补丁验证.图1给出了程序缺陷自动修复的研究框架.

如图1所示，定位阶段通过缺陷定位策略找出可能导致程序错误的可疑位置，缺陷定位结果的精度直接关系到补丁的生成效率.缺陷定位方法可分为动态缺陷定位方法与静态缺陷定位方法[10].动态缺陷定位方法通过对测试用例的执行行为与运行结果进行分析，并基于特定模型来定位缺陷语句的可能位置，具有较高的定位准确性，当前此类方法中的主流是基于频谱的缺陷定位方法[7]，其通过执行测试用例获取程序频谱，而后分析频谱来定位程序缺陷[11].静态缺陷定位方法通过分析缺陷报告和程序模块的文本内容并提取特征，基于特定模型确定可疑的程序语句，其不需要执行测试用例，不会受到程序规模和编程语言等因素的影响，基于信息检索的缺陷定位(Information Retrieval-Based Bug Localization，IRBL)是目前静态缺陷定位研究中的热点[12]，其广泛应用于基于错误报告驱动的程序缺陷自动修复方法中.补丁生成阶段按照一定的修复规则逐个对可疑缺陷代码进行相应的处理，生成缺陷代码的补丁.本文根据补丁生成方式的不同，将程序缺陷自动修复方法划分为4类，分别为基于搜索的、基于语义的、基于机器学习的和基于错误报告驱动的程序缺陷自动修复方法.补丁排序及验证阶段对补丁生成阶段产生的候选补丁进行排序和正确性验证.在验证时，一方面要检验补丁是否成功修复原有的缺陷，另一方面要检验原有的程序功能是否被破坏.对补丁进行验证的开销往往较大，利用候选补丁排序技术有助于提高修复效率和缩减验证成本.

图1 程序缺陷自动修复研究框架Fig.1 Research framework of automatic program repair

3 基于搜索的程序缺陷自动修复方法

基于搜索的程序缺陷自动修复方法利用了基于搜索的软件工程[13-15](Search Based Software Engineering，SBSE)中的蚁群算法、粒子群优化、遗传算法以及模拟退火等算法.其核心思想是将修复问题看成是组合优化问题，为了修复程序，将程序中若干位置的代码更新(修改、删除、添加代码)视为个体，即把更新的内容当作潜在的程序补丁，并把所有通过更新得到的程序补丁作为一个庞大的搜索空间，在这个补丁搜索空间中寻找最优可行解，搜索空间的大小取决于代码修改操作的大小.图2展示了基于搜索的程序缺陷自动修复方法的总体流程，可以看出寻找正确补丁的过程是一个迭代的过程.

图2 基于搜索的程序缺陷自动修复方法流程Fig.2 Flow of search-based automatic program repair methods

3.1 基于搜索的程序缺陷自动修复方法研究进展

最早在2008年，Arcuri等人[16]提出了一种协同进化的方法ABF(Automatic Bug Fixing)来自动修复程序中的缺陷.该方法将缺陷程序与测试用例进行协同进化，在多次进化后，筛选出检测缺陷能力较强的测试用例以及正确性较高的程序补丁.该方法对于缺陷的类型没有限制，可以轻易修复难以识别的微小缺陷，但是该方法存在搜索空间过大的问题.

Weimer和Le Goues等人[17-20]于2009年提出了开创性的基于搜索的程序缺陷自动修复方法GenProg.该方法工作在抽象语法树(Abstract Syntax Tree，AST)级别，其将源程序转化为AST，通过更新(删除，插入，替换)AST的节点获得新的AST，最后将AST转化为程序补丁.相比于ABF[16]，该方法设计了限制搜索空间的策略.在2012年，Le Goues等人[21]对GenProg进行了如下优化：对GenProg提出新的算法改进，使其能够扩展到大型程序并且能够修复更多的缺陷；利用GenProg固有的并行性，使用云计算资源提供可靠的成本估算.在2013年，Weimer等人[22]提出了程序缺陷自动修复方法AE，AE利用近似语义等价关系识别出语义等价的候选补丁，可显著减少补丁评估数.在2015年，Le Goues等人[23]为程序缺陷自动修复领域贡献了两个经典的缺陷库MangBugs和IntroClass.

在2010年，Debroy等人[24]提出了一种通过使用变异测试中的变异算子来生成程序补丁的缺陷自动修复方法.该方法按照包含缺陷可能性的大小对程序语句进行排序，并以相同的顺序对程序语句进行变异，以为含有缺陷的程序提供尽可能的修复.Fast等人[25]则在2010年对进化算法进行了优化，研究了两种增强程序修复适应度函数的方法：对测试集进行选择来提高效率；形式化规范以提高精度.Schulte等人[26]在同年尝试了利用进化算法在汇编代码级别的修复，其修复效率与在源代码级别的修复方法不相上下.

在大型程序中通过修改源代码来自动修复缺陷通常是一个非常耗时的过程，重新编译和重新安装打过补丁的程序需要大量的时间.于是，Qi等人[27，28]在2012年提出了一种弱重新编译技术.在弱重新编译技术中，假设一个程序是由多个组件构成的，对于每个候选补丁，仅将一个组件中更改的代码片段重新编译为共享库.弱重新编译的优点是可以大幅降低重新编译和重新安装的成本.他们还构建了WAutoRepair，这是一个具有可伸缩性的系统，可以高效地修复大型C程序中的缺陷.在2013年，Qi等人[29]将回归测试优先级排序应用于程序缺陷自动修复领域，并提出了一种新的优先级排序技术FRTP，可以减少测试用例的执行次数.他们还开发了一个名为TrpAutoRepair的工具来实现FRTP技术.同年，Kim等人[30]从开发人员手工编写的修复程序中总结出了10种常用的代码修改模板，由此提出了程序缺陷自动修复方法PAR(Pattern-based Automatic program Repair).该方法解决了GenProg[17-20]因突变操作的随机性而产生无效补丁的问题.在2014年，Qi等人[31]提出了一种基于随机搜索的程序缺陷自动修复方法RSRepair，并实现了其原型工具.相比于GenProg[17-20]，RSRepair需要的测试用例更少且补丁搜索空间更小，这也证明了随机搜索相对于遗传编程具有更强的优势.

Long等人[32]于2016年提出了Prophet，Prophet从现有的补丁数据库中学习一个用于补丁排序的最大似然概率模型.对于一个新的缺陷，Prophet会生成一个包含许多候选补丁的搜索空间，然后应用所学习的模型计算每个补丁可能是正确补丁的概率，接着根据概率进行补丁排序，最后使用给定的测试套件对候选补丁进行验证.实验结果显示，在一组含有69个真实缺陷的集合中，Prophet成功修复了其中的15个，具有一定的准确度.同年，Le等人[33]提出了一种可以利用软件开发历史中大量的修复程序来有效地指导和推动程序缺陷修复的方法.他们认为重复出现的错误修复在现实程序中很常见，以前出现的修复模式可以为自动修复方法提供有用的指导.基于此，该方法首先从许多项目的提交历史中挖掘错误修复模式，然后再使用变异操作符来为含有缺陷的程序生成候选补丁.

在实际项目中，测试套件通常是不够全面的，因此通过测试套件的补丁并不一定是正确的补丁，该问题即过拟合问题.Xiong等人[34]于2017年提出了一种新颖的程序修复方法ACS，ACS可产生精确的补丁和缓解过拟合问题.相比于同时期的其他方法，ACS在修复数量和精确度上都处于领先地位.同年，Saha等人[35]提出了ELIXIR用于自动修复C++程序中的缺陷，尤其是修复表达式与函数调用错误.ELIXIR使用方法调用来构建更有表现力的修复表达式以合成程序补丁.Qi等人[36]也于2017年提出了一种程序缺陷自动修复方法ssFix.该方法假设用于合成补丁的代码可以在现有的代码库中找到，因此其利用现有代码来生成修补程序的补丁.

基于搜索的程序缺陷自动修复方法由于搜索空间可能不包含正确补丁和搜索空间巨大这两个问题，其性能受到了限制.于是，Wen等人[37]于2018年提出了一种上下文感知的程序缺陷自动修复方法CapGen.CapGen增加了搜索空间中正确补丁的数量，同时也解决了由于使用更精细的粒度而导致进一步扩大搜索空间，增加搜索难度的问题.在Defects4J[38]上的实验结果显示，CapGen达到了84%的精度，并且可在绝大多数不正确的补丁之前优先处理正确补丁，其修复能力优于同时期的其它方法.常见的修复方法是迭代生成可疑程序的候选补丁，然后利用给定的测试用例对其进行验证，直到找到通过所有测试用例的候选补丁为止.尽管此类方法在概念上较为简单，但是由于可能需要生成、编译和测试大量的候选补丁，其修复效率相对较低，尤其是对于细粒度的缺陷而言.因此，Hua等人[39]在2018年提出了SketchFix，该方法可在测试执行期间按需生成候选补丁.在Defects4J[38]上对SketchFix的实验结果表明，与其他程序修复方法相比，SketchFix在AST节点级粒度下通过表达式操作修复错误的效果更好.同年，Yuan等人[40]提出了一种基于遗传编程的Java程序自动修复方法ARJA.ARJA使用一种低粒度的补丁表示，它可以适当地解耦可能有bug的位置、操作类型和潜在修复成分的搜索子空间，使其能够更有效地探索搜索空间.基于这种低粒度的表示，该方法将程序缺陷自动修复表述为一个多目标搜索问题，引入了一个测试过滤过程来减小计算工作量和搜索空间，并且还提出了一种类型匹配策略，通过利用现有语句的语法模式来创建新的潜在的修复成分.在对ARJA大规模的实证研究中，实验结果充分显示了多目标搜索和类型匹配策略的有效性，ARJA修复了比jGenProg[41]和Nopol[42]更多的缺陷，其中包含几个公认的难以修复的多位置缺陷.随后，为扩充补丁生成空间，Yuan等人[43，44]结合GenProg[17-20]和PAR[30]提出了ARJA-e.ARJA-e利用冗余假设和修复模板来创建候选补丁的搜索空间.ARJA-e 还使用了更细粒度的适应度函数，可以充分利用测试套件中包含的语义信息，有望更好地指导整个搜索过程.除此之外，ARJA-e 还包含一个后期处理工具，可以用于过拟合检测和补丁排序.在Defects4J[38]上的实验研究表明，相比于GenProg，ARJA-e生成的正确补丁数量有了明显的增加，实现了实质性的性能提升.

在2019年，Hu等人[45]提出了一种全自动的程序修复方法用以根据正确的程序来修复学生提交的作业程序，并实现了修复工具Refactory.该方法首先通过将所有可能的正确程序根据给定的变换规则重构为具有新控制流结构且语义等价的程序，然后根据控制流结构，将学生提交的不正确的程序与正确的重构程序进行匹配，进而根据执行这些正确程序基本块(basic blocks)的运行结果来推断出错误程序基本块的输入/输出规范，最后根据这些规范产生修复代码.同年，Ghanbari等人[46]提出了首个实用的字节码级程序缺陷自动修复方法PraPR，并首次对基于字节码突变的修复方法进行了实证研究.与源代码级别的修复方法相比，由于字节码具有结构简单且种类有限的特点，因此PraPR具有更高的修复效率.在Defects4J[38]上的实验结果显示，其修复效果显著优于当时最先进的程序缺陷自动修复方法.

Villanueva等人[47]于2020年将新颖性搜索(Novelty Search，NS)算法应用于GenProg[17-20]中，提出了程序缺陷自动修复方法NS-GenProg，这是NS在程序缺陷自动修复领域的首次应用.NS-GenProg使用NS适应度函数替代了GenProg中的适应度函数，NS-GenProg解决了GenProg陷入局部最优解的问题.经实验研究表明，NS-GenProg在修复了与GenProg相似数量缺陷的同时，还修复了GenProg无法修复的缺陷.

3.2 小 结

目前，基于搜索的程序缺陷自动修复方法还存在如下尚需解决的关键问题：

1)基于搜索的程序缺陷自动修复是一个在搜索空间内寻找补丁并进行正确性验证的过程.但是，若搜索空间设置得过大，会致使效率低下，且会产生大量疑似正确的补丁.若搜索空间设置得过小，可能会导致搜索空间中不存在正确的补丁.因此，如何设置合适的搜索空间是基于搜索的程序缺陷自动修复方法面临的一个关键问题.

2)生成的补丁有可能能够通过全部测试用例但是它违背了程序语义，如何剔除这类补丁是基于搜索的程序缺陷自动修复方法面临的一个关键问题.

3)测试用例在缺陷定位和补丁评价阶段都起到了关键的作用，测试用例的质量决定了定位缺陷的准确性以及验证补丁的准确性.因此，如何生成高质量的测试用例也是基于搜索的程序缺陷自动修复方法面临的一个关键问题.

4 基于语义的程序缺陷自动修复方法

基于语义的程序缺陷自动修复方法的正确性通常高于基于搜索的程序缺陷自动修复方法.该类方法首先定位到可疑的缺陷实体，并对可疑的缺陷实体进行排序；其次生成含有缺陷的实体的输入以及输出预期值；然后收集程序运行时的信息，提取补丁需要满足的约束；最后将修复约束作为合成补丁的规约，并用约束求解器生成补丁[7].该类方法将测试用例作为输入，且转化为解输出.与基于搜索的修复方法相比，其生成的补丁基本都能通过验证.图3展示了基于语义的程序缺陷自动修复方法的总体流程.

图3 基于语义的程序缺陷自动修复方法流程Fig.3 Flow of semantic-based automatic program repair methods

4.1 基于语义的程序缺陷自动修复方法研究进展

Nguyen等人[48]于2013年提出了一种基于符号执行、约束求解和程序综合的缺陷自动修复方法SemFix.SemFix从测试用例中得出修复约束，并求解该修复约束以生成有效的补丁，其优势是可以在不存在修复材料的情况下合成修复程序，且在特定类型的缺陷修复上，SemFix相比于基于搜索的程序缺陷自动修复方法具有更高的修复效率与修复成功率.

Mechtaev等人[49]着眼于最大限度地保留缺陷程序的程序结构，于2015年提出了DirectFix.DirectFix将故障定位和补丁生成融合到一个步骤中，利用部分Max SAT约束求解和基于组件的程序合成来实现.相比于SemFix[48]，DirectFix实现缺陷修复的难度更低.由于DirectFix和SemFix都是测试驱动的修复工具，它们都会进行回归测试，与SemFix相比，DirectFix引入的回归错误要少得多.同在2015年，Marcote等人[50]针对无限循环的缺陷提出了一种自动修复方法Infinitel.该方法首先检测到无限循环缺陷发生的位置，然后收集有关其预期行为的执行信息，最后通过基于程序合成的方法生成新的循环条件.

基于语义的程序缺陷自动修复方法最大的挑战在于如何提高方法的可伸缩性.为此，Mechtaev 等人[51]于2016年提出了Angelix，它可以扩展到与GenProg[17-20]等基于搜索的修复方法处理的大小相似的程序.Angelix比基于语义的其他修复方法如SemFix[48]和DirectFix[49]更具伸缩性，而且该方法可以修复相互依赖的多个位置的缺陷.在2018年，Mechtaev等人[52]在Angelix的基础之上提出了修复工具SemGraft.针对由于Angelix依赖于测试用例作为补丁正确性标准而产生的过拟合问题，SemGraft将程序的规约作为补丁正确性判断的辅助标准，在一定程度上缓解了过拟合问题，提升了生成的补丁质量.

Xuan等人[42]于2017年提出了Nopol，其早期版本[53]于2014年提出，Nopol是一种自动修复条件语句缺陷(即错误的IF条件和缺失的前提条件)的方法.该方法利用天使修复定位(Angelic Fix Localization)来确定缺陷位置，然后利用基于组件的程序合成方法合成条件补丁.虽然该方法存在一定的局限性，但是由于该方法是针对有缺陷的条件语句设计的，所以具有成本低、空间小和可以应用于大规模的程序修复等优势.

针对程序缺陷自动修复方法经常产生低质量补丁且引入新缺陷的问题，Afzal等人[54]于2019年提出了一种基于语义代码搜索的程序缺陷自动修复方法SOSRepair.该方法用人工编写的语义相似但不相同的代码替换可疑位置的代码.除此之外，该方法采用了一种新颖、高效、通用的机制，用于编码程序修复的语义搜索查询，这种编码方式可以有效地将候选修复代码映射到有缺陷的上下文中，显著加快了代码的搜索过程.

GAO等人[55]于2021年提出了一种基于约束驱动的程序缺陷自动修复方法并实现了修复工具ExtractFix.为应对高质量的测试用例并不总是存在的问题，ExtractFix使用了一种基于约束/依赖的定位技术而不是广泛应用的统计故障定位技术.针对程序崩溃位置可能与修复位置不同的问题，ExtractFix可对提取的约束进行传播和转换，以指导在修复位置生成补丁.此外，ExtractFix还扩展了现有的二阶程序合成方法以生成具有最小句法/语义变化的补丁.经在MangBugs[23]等数据集上的实验研究表明，ExtractFix产生的正确补丁数多于同时期较为先进的程序缺陷自动修复工具.

4.2 小 结

基于语义的程序缺陷自动修复方法目前还存在如下尚需解决的关键问题：

1)基于语义的程序缺陷自动修复方法通过约束生成补丁，生成正确补丁的概率往往更高.但是此类方法需要更多的程序信息，且面临算法执行时间较长、部署和实施困难的问题.

2)基于语义的程序缺陷自动修复方法建立在“若补丁通过全部的测试用例，则为正确补丁”的假设之上，因此不可避免地会产生过拟合问题.如何更好的缓解过拟合问题是基于语义的程序缺陷自动修复方法面临的一个关键问题.

3)基于语义的程序缺陷自动修复方法在小规模的程序上展现出了良好的修复效果，然而由于此类方法大多使用了符号执行以及约束求解等技术，使得其难以应用在较为复杂的程序上.如何解决上述局限性是基于语义的程序缺陷自动修复方法面临的一个关键问题.

5 基于机器学习的程序缺陷自动修复方法

目前，以GenProg[17-20]为代表的基于搜索的程序自动修复方法和以SemFix[48]为代表的基于语义的程序自动修复方法已展现出良好的修复效果.但是这些方法都有自身的局限性，将机器学习应用于程序缺陷自动修复可以有效解决这些局限.基于机器学习的缺陷自动修复主要步骤为：首先，获取数据集，进行数据预处理并将数据送与修复模型；其次，结合机器学习的技术对修复模型进行训练；然后，用训练好的模型为待修复程序生成候选补丁；最后，对候选补丁进行排序和正确性验证.图4展示了基于机器学习的程序缺陷自动修复方法的总体流程.

5.1 基于机器学习的程序缺陷自动修复方法研究进展

最早在2009年，Jeffrey等人[56]提出了一种称为BugFix的程序缺陷自动修复方法.BugFix会在程序语句中自动分析调试情况，并得出相关缺陷的修复程序排序列表以指导开发人员对该缺陷进行适当的修复.BugFix融合了机器学习的思想，可以不断地自动学习新的调试情况和缺陷修复.当遇到新的缺陷时，可以有效的预测最准确的缺陷修复程序.

图4 基于机器学习的程序缺陷自动修复方法流程Fig.4 Flow of machine learning-based automatic program repair methods

对于执行复杂操作的代码，修复其中的错误仍然是昂贵且困难的.于是在2016年，Gopinath等人[57]提出了MLR用以修复复杂代码中的错误，他们认为基于机器学习和系统路径探索的集成方法可以提供有效的修复.MLR首先挖掘执行条件分支成功和执行失败的数据以生成程序频谱，然后生成补丁搜索空间，最后生成在现有测试套件之下的补丁.Gopinath等人[57]将MLR应用于修复小型但数据结构复杂的程序中的缺陷以证明其修复效果.实验结果表明，与2016年同时期的其它修复工具相比，MLR能更有效地修复此类缺陷.

由于一些程序员缺乏编程的经验以及对细节的关注，会产生许多错误，通常称这些错误为编程错误.编译器会检测到此类错误，但编译器提供的错误报告通常不准确.针对此类错误，在2017年，Gupta等人[58]提出了一种称为DeepFix的程序缺陷自动修复方法，其核心是一个序列到序列神经网络，该神经网络具有多层次的结构.在训练后DeepFix可以预测缺陷位置以及正确的修复语句.在一组由学生编写的6971个含有错误的C程序集合中，DeepFix完整修复的程序数量达到了1881(27%)个，部分修复的程序数量达到了1338(19%)个.

在2019年，Vasic等人[59]提出了一种联合学习定位和修复的方法，该方法主要针对变量滥用而引起的程序缺陷.方法中设计了一个基于程序标记序列顺序编码的多头指针网络模型，每个头指针网络模型用于定位和修复一个错误，该模型的性能明显优于使用枚举方法的模型.在将来，他们还将探索使用其他模型(如图模型、指针和图模型的组合)的联合定位和修复，并将考虑使用更多的程序语义信息.White等人[60]于2019年提出了一种通过深度学习来推理代码相似性的程序缺陷自动修复方法DeepRepair.该方法可以根据与可疑元素(即包含可疑语句的代码元素)的相似性来对代码片段进行排序，并且可以通过将范围外的标识符映射到范围内的相似标识符来转换语句.该方法的特点是找到了当时基于冗余的修复方法无法找到的补丁.Tufano等人[61]于2019年对使用神经机器翻译(NMT)技术进行程序修复的可行性进行了广泛的实证研究，其设计并详细阐述了挖掘、提取以及抽象缺陷程序和修复程序的过程.在此基础之上建立了基于循环神经网络(RNN)的NMT模型用于将缺陷程序转换为修复程序.Tufano等人[61]提出的NMT模型作为较为先进的修复工具，其能修复多种类型的缺陷，且能在9%-50%的情况下预测补丁程序.该NMT模型中解码器输出的是方法级别的补丁程序，但由于NMT模型难以处理过长的方法序列，使得其修复范围仅限于中小型方法中.Chen[62]等人于2019年提出了一种使用序列到序列模型进行端到端程序修复的方法SEQUENCER.该方法通过构建抽象的上下文来模拟开发人员分析和推理bug的过程，通过复制机制克服大代码中出现的词汇量巨大的问题.相比于Tufano等人[61]提出的方法，SEQUENCER没有修复方法大小的限制，且其考虑的上下文范围由方法扩展到了类，使模型在修复缺陷时可以访问更多的程序信息.

“生成—验证(G&V)”的程序缺陷自动修复方法常依赖于硬编码规则，发现这些规则需要大量的人工努力，而且难以使这些规则适应于不同的程序语言，因此只能按照特定的修复模式修复缺陷.为了解决这些问题，在2020年，Lutellier等人[63]提出了一种G&V方法CoCoNuT.CoCoNuT利用卷积神经网络(CNN)和神经机器翻译技术来自动修复多种程序语言的缺陷.Lutellier等人[63]在4种编程语言(Java，C，Python，JavaScript)的6个缺陷库上测试了CoCoNuT的修复效果.实验结果表明，在其中的4个缺陷库上，CoCoNuT修复了数量最多的缺陷，也是唯一一个修复Python和JavaScript缺陷的方法.Li等人[64]于2020年提出了一个两层的深度学习模型DLFix用于自动修复程序缺陷.DLFix的第1层是基于树的RNN模型，用于学习缺陷修复的上下文，第2层用于学习缺陷程序到修复程序的转换.

近些年，神经机器翻译技术(NMT)被广泛用于自动修复程序缺陷.该类方法展现出了良好的发展前景，但是目前存在着两个主要的局限性：该类方法的搜索空间中包含的正确补丁较少；其搜索策略忽略了如代码语法等软件知识.针对上述局限性，Jiang等人[65]于2021年提出了一种新的基于NMT的程序缺陷自动修复方法CURE.CURE 在大型软件代码库上预训练编程语言(PL)模型，以在自动修复程序之前预先对源代码进行学习.CURE 还设计了一种新的代码感知搜索策略，该策略侧重于关注可编译的补丁和与错误代码长度相近的补丁以找到更多正确的修复.此外，CURE 使用了子词标记化技术来生成包含更多正确修复的较小搜索空间.PL模型、代码感知搜索策略和子词标记化技术的使用使得CURE的修复效率及效果优于同时期的程序缺陷自动修复方法.

5.2 小 结

目前，基于机器学习的程序缺陷自动修复方法还存在如下尚需解决的关键问题：

1)源代码不同于自然语言，其原始数据相当嘈杂，会对训练产生极大程度的噪音.因此，如何过滤原始数据是基于机器学习的程序缺陷自动修复方法面临的一个关键问题.

2)在自然语言中，类似于标点符号的错误是可以接受的，且依赖关系通常在同一个句子中或者几个句子中.但在编程语言中，标识符、数字等的误用会导致编译器产生错误的结果，依赖关系的范围也更长(可以使用一个在几十行前已经声明的变量).因此，如何使通过机器学习产生的修复程序的精度达到标识符、数字级别和处理好长依赖关系是基于机器学习的程序缺陷自动修复方法面临的关键问题.

3)使用机器学习自动修复程序缺陷时，需要处理的词汇数量巨大，这是由于变量、常量等定义的任意性，且字母的大小写在编程语言中代表着不同的含义.因此，如何减小需要处理的词汇数量是基于机器学习的程序缺陷自动修复方法面临的一个关键问题.

6 基于错误报告驱动的程序缺陷自动修复方法

目前程序缺陷自动修复主要集中在基于测试集的修复方法，其中错误定位和补丁生成由明确定义的测试套件驱动.但是在大多数实际情况中，有关测试用例的通用假设并不存在，即许多的错误并不能通过测试套件挖掘到.基于错误报告驱动的程序缺陷自动修复方法可以应对上述问题，因为错误报告中含有丰富的关于程序执行以及用户反馈的错误信息.

6.1 基于错误报告驱动的程序缺陷自动修复方法研究进展

2011年，Jin等人[66]提出了AFIX，该方法用于自动修复单变量原子性违背的并发错误.其使用现有的错误检验工具得到错误报告，通过静态分析和静态代码转换来自动设计和生成程序补丁.它还利用交叉测试技术来引导其修复过程.此外，AFIX进一步结合了运行时动态代码监测，以帮助开发人员验证和评估它生成的每个补丁.

2013年，Liu等人[67]提出了一种基于错误报告驱动的程序缺陷自动修复方法R2Fix，该方法可以通过无格式要求的错误报告生成补丁.收到错误报告后，R2Fix会先分析该错误报告，然后确定错误类型，最后生成候选补丁来修复该错误.具体的，R2Fix包含3个步骤：1)错误分类器(简称为分类器)分类，分类器对错误报告进行分析和归类，并且仅保留归类为目标错误类型的错误报告(候选错误报告)用于接下来的两个步骤;2)模式参数提取器(简称模式提取器)从源代码和候选错误报告中提取缓冲区长度、指针名称等模式参数;3)补丁生成器(或简称生成器)使用目标错误类型的修复模式、模式参数以及源代码存储库来自动生成补丁.研究人员在3个大型的项目(即Linux内核，Mozilla和Apache)上评估了R2Fix对3类重要错误(缓冲区溢出，空指针错误和内存泄漏)的修复效果.实验结果表明，R2Fix可以生成60个正确补丁，其中5个是针对尚未被开发人员修复的错误的新补丁，且5个中的4个补丁被开发人员认可接受.R2Fix生成的60个正确的补丁程序可以节省68天的错误诊断和补丁程序生成时间.

在2019年，Koyuncu等人[68]提出了一种基于错误报告驱动的程序缺陷自动修复方法iFixR，这是一种程序自动修复的管道变体，适用于测试用例不可用的情况.该方法的修复流程为：将错误报告和错误程序送到基于IR的定位器，定位器会定位到可疑代码的位置；筛选出合适的修复模式，由修复模式生成补丁；通过回归测试进行补丁验证.在重组的Defects4J上的实验结果表明，iFixR可以针对各种错误报告生成更合理的补丁，且其修复性能与Defects4J上绝大多数基于测试集的程序缺陷自动修复方法不相上下.

6.2 小 结

在修复实际项目中的错误时，测试用例的假设通常是无法成立的.相比于基于测试集的程序缺陷自动修复方法，基于错误报告驱动的修复方法最大的优势是不需要对测试用例进行任何的假设，这也在一定程度上增加了此类方法的实际可用性.目前，基于错误报告驱动的程序缺陷自动修复方法还存在如下尚需解决的关键问题：

1)基于错误报告驱动的程序缺陷自动修复方法修复错误的第一阶段是对错误报告进行解析、筛选和分类，然而错误报告的数量通常较多，需要耗费大量的资源.因此，设计更加合理高效的解析、筛选和分类算法是基于错误报告驱动的程序缺陷自动修复方法面临的一个关键问题.

2)为了从错误报告中自动生成补丁，需要从错误报告中提取关于错误的详细信息，然而现有的许多错误报告提取技术只能从错误报告中获取到简单的错误描述.因此，如何改进现有的技术以获取全面的错误描述进而得到错误产生的根本原因是基于错误报告驱动的程序缺陷自动修复方法面临的一个关键问题.

7 缺陷库

程序缺陷自动修复方法及工具修复效果的检验离不开高质量的缺陷库.高质量的缺陷库需要具有完备的测试集，且要求缺陷的来源必须是真实的项目.本节总结了目前程序缺陷自动修复领域常用的C/C++、Java和多种语言的缺陷库，特别梳理了缺陷库的适用场景以及对程序缺陷自动修复工作的贡献.表1给出了每个缺陷库对应的编程语言、缺陷总数、参考文献、缺陷来源、适用场景和下载地址.

表1 程序缺陷自动修复评测缺陷库Table 1 Defect libraries for automatic program repair evaluation

7.1 C/C++缺陷库

Le Goues等人[23]于2015年提出了两个缺陷库ManyBugs和IntroClass.ManyBugs由9个大型开源项目的185个缺陷组成，共含有代码590万行和测试用例1万多个.IntroClass由本科生编写的程序中的共998个缺陷组成.ManyBugs和IntroClass包含黑盒测试和白盒测试，黑盒测试由人工方式依据等价类划分执行，白盒测试实现测试预言的分支覆盖.Tan等人[69]于2017年提出了缺陷库Codeflaws，Codeflaws缺陷库来自于Codeforces在线数据库中的7436个程序.它是3902个缺陷的集合，共有39种缺陷类别.Codeflaws用于研究不同修复工具可修复的缺陷类别.Böhme等人[70]基于CoREBench(CoREBench是4个开源项目(coreutils，findutils，grep和make)中70个实际回归错误的集合)于2017年发布了DBGBENCH论文，提出了DBGBENCH缺陷库.

7.2 Java缺陷库

Just等人[38]于2014年提出了Defects4J，这是一个可扩展的缺陷库，提供了真实项目中的缺陷.Defects4J的初始版本包含5个真实的开源项目中的357个程序缺陷，每个缺陷都附带一个全面的测试套件.Defects4J是可扩展的，将Defects4J配置好之后，可以轻松地将新的缺陷添加到缺陷库中.Defects4J具有一个框架，该框架提供了高级界面，可访问错误程序和修复程序以及相应的测试套件.Saha等人[71]于2018年提出了Bugs.jar，这是一个大规模的缺陷库，用于研究Java语言的程序缺陷自动修复方法.Bugs.jar由1，158个错误和补丁组成，这些错误和补丁来自8个大型流行的开源Java项目.Bugs.jar比Defects4J[38]大一个数量级.Madeiral等人[72]于2019年提出了缺陷库Bears，Bears是用于程序缺陷自动修复研究的可扩展Java缺陷库.Madeiral等人[72]提供了Bears的1.0版本，Bears1.0版本中包含从72个项目中收集的251个可复制的缺陷.

7.3 多种语言的缺陷库

Lin等人[73]于2017年提出了QuixBugs缺陷库.QuixBugs中的40个Python缺陷程序来自于Quixey公司测试题目，这些程序均由人工转换为Java程序，每个程序都包含一个单行缺陷，以及通过和失败测试用例.Quixbugs旨在用于检验修复方法跨语言的修复性能.Tomassi等人[74]于2019年提出了BugSwarm.BugSwarm是同类中最大的缺陷库，其有成千上万个可复制的错误程序及相应的修复程序对，具有很强的可扩展性.目前，BugSwarm已经收集了3，091个Java和Python的错误程序及相应的修复程序对.

7.4 缺陷库对程序缺陷自动修复工作的贡献

程序缺陷自动修复工作与缺陷库密不可分，本小节将系统地分析和总结缺陷库对于程序缺陷自动修复工作的主要贡献.

1)程序缺陷自动修复方法能够降低维护软件可靠性和保证软件质量所需的成本.为了使程序缺陷自动修复方法走向实际运用，需要建立高质量的缺陷库以对其修复能力进行测试评估.高质量的缺陷库需要具有一定的规模、复杂度和多样性，除此之外还要求缺陷来自于真实项目.近些年，不断有高质量的缺陷库被设计与运用，如用于评估C/C++程序缺陷自动修复方法的ManyBugs[23]、IntroClass[23]和DBGBENCH[70]等，用于评估Java程序缺陷自动修复方法的Defects4J[38]、Bugs.jar[71]和Bears[72]等，这些缺陷库为推进程序缺陷自动修复方法的工业应用作出了重要贡献.

2)通常情况下，一种程序缺陷自动修复方法可以修复多种类型的缺陷.但在修复某种特定类型的缺陷时，为取得良好的修复效果，需针对性地选择修复性能最佳的方法.为此，近些年来研究者们设计和建立了如Codeflaws[69]等缺陷库，这类缺陷库为研究不同的程序缺陷自动修复方法对某种特定类型缺陷的修复效果作出了较为重要的贡献.

3)近年来，程序缺陷自动修复领域涌现出了许多研究成果.虽然以前的工作只关注某一种语言的缺陷修复，但是由于最近语言转换工作的不断进展，当下在该领域也提出了许多可以修复多种语言缺陷的程序自动修复方法.为了对这类方法进行实证研究，一些多语言并行的缺陷库被设计和建立，如Lin等人[73]建立的QuixBugs和Tomassi等人[74]建立的BugSwarm等，这些缺陷库为评估程序自动修复方法跨语言修复缺陷的能力作出了重要贡献.

8 总结与展望

随着软件规模和复杂度的提高，程序缺陷自动修复近几年来获得了持续且广泛的关注.虽然程序缺陷自动修复研究时间较短，但取得了大量的研究成果.尤其在国内，随着研究的深入，产生了许多具有影响力的贡献.本文根据补丁生成方式的不同，将程序缺陷自动修复方法划分为4类，分别为基于搜索的、基于语义的、基于机器学习的和基于错误报告驱动的程序缺陷自动修复方法，并对每类方法进行了详细阐述.其次，总结了检验程序缺陷自动修复方法及工具修复效果所用到的缺陷库，特别梳理了缺陷库的适用场景以及对程序缺陷自动修复工作的贡献.

虽然目前程序缺陷自动修复领域开发出了数以百计的自动修复工具，且在由开源项目组成的真实缺陷库上展现出了一定的修复效果，但程序缺陷自动修复研究成功应用于工业软件的案例少之又少.目前成功应用的案例是Facebook[75]，两个程序缺陷自动修复工具SapFix[76]和Getafix[77]被集成到他们的开发工作流中，其修复了超过40%～50%的与空值相关的缺陷和警告.如ELIXIR[35]、Nopol[42]和Astor[78]等常用的程序缺陷自动修复工具的工业应用并未取得显著的效果.Noda[75]等人将较为先进的程序缺陷自动修复工具ELIXIR[35]应用于大型工业软件中，在20个真实的单语句缺陷的修复中，仅取得了10%的成功率.Naitou等人[79]对Nopol[42]和Astor[78]进行了工业应用的研究，在9个待修复的缺陷中，它们仅正确修复了其中的一个.鉴于此，我们分析总结了该领域面临的关键问题及未来研究的方向：

1)许多程序缺陷自动修复工具在如 Defects4J[38]等缺陷库上展现出了良好的修复效果，然而在工业软件上的实际性能却相当低，这表明修复工具过度拟合缺陷库，这是程序缺陷自动修复应用于工业界尚需解决的一个关键问题.

2)许多程序缺陷自动修复方法都是建立在缺陷只存在于单条语句之上的，修复的缺陷类型较为简单.然而在现实中，程序中的缺陷很可能在多条语句之上.因此，如何修复存在于多条语句之上的缺陷是程序自动修复方法面临的一个关键问题.

3)缺陷定位方法发展相对较早，且取得了较多的研究成果.但是，很多缺陷定位方法是用来辅助开发人员进行人工的缺陷修复的，其精度往往达不到程序缺陷自动修复的要求.因此，开发精度更高的缺陷定位方法是一个值得深入研究的方向.

4)基于生成-验证的程序缺陷自动修复方法在缺陷定位和补丁评估阶段需要消耗相当长一段时间来多次运行测试用例.企业级应用程序的测试时间往往更长，如果执行整个测试用例，则很容易超过时间预算，这是由于企业级应用程序经常需要与数据库等外部环境进行交互，访问数据库等外部环境的时间开销十分沉重，过长的时间开销阻碍了程序缺陷自动修复方法的工业应用.因此，如何选择检测能力较强的测试用例子集并确定其执行顺序以减少时间开销是一个值得进一步研究的问题.

5)在实际应用中，通过程序自动修复方法产生的补丁不仅需要能够修复缺陷，还要具有安全性、清晰的结构和较高的效率等特性，但是这些特性通常难以通过测试套件评估.因此，如何产生和筛选出正确且具有安全性、清晰的结构和较高效率的补丁是程序缺陷自动修复方法面临的一个关键问题.