2016年自动修复综述——自动程序修复方法研究进展 [软件学报 Journal of Software 2016]

前言

本文旨在介绍2016年软件学报文章——自动程序修复方法研究进展。

1 作者

中文引用格式: 玄跻峰,任志磊,王子元,谢晓园,江贺.自动程序修复方法研究进展.软件学报,2016,27(4):771?784. http://www.
jos.org.cn/1000-9825/4972.htm
英文引用格式: Xuan JF, Ren ZL, Wang ZY, Xie XY, Jiang H. Progress on approaches to automatic program repair. Ruan Jian
Xue Bao/Journal of Software, 2016,27(4):771?784 (in Chinese). http://www.jos.org.cn/1000-9825/4972.htm

2 摘要内容

回顾了基于测试集的程序修复的现有文献,按照自动修复方法和实证基础两个方面陈述了研究进展.

首先,将已有的自动修复方法划分为 3类, 分别是基于搜索的、基于代码穷举的和基于约束求解的补丁生成方法;

其次,细致地描述了程序修复的实证研究基础以及该研究领域中的争议;

然后,简要介绍了程序修复的相关技术作为修复方法的补充;最后做出总结,描述了面临的机遇和挑战.

3 introduction

1） 历史数据表明,超过45%的现代软件开发成本消耗于定位和修复 bug 过程中。
[1] Pressman RS. Software Engineering: A Practitioner’s Approach. 7th ed., New York: McGraw-Hill, 2010. 437?443.

文献引用的好棒

2）随着软件测试和调试技术的提高,自动化的程序 bug 定位技术已经得到了一定的
研究和发展[2,3],然而自动化的程序 bug 修复方法仍处在初级阶段.随着程序 bug 数量的日益积累,自动修复技术
的深入研究及应用已迫在眉睫.

**就是说现在缺陷定位发展的比APR成熟一点。
好像确实是这样**

[2] Xie X, Chen TY, Kuo FC, Xu B. A theoretical analysis of the risk evaluation formulas for spectrum-based fault localization. ACM
Trans. on Software Engineering and Methodology, 2013,22(4):31:1?31:40. [doi: 10.1145/2522920.2522924]
[3] Wen WZ, Li BX, Sun XB, Liu CC. Technique of software fault localization based on hierarchical slicing spectrum. Ruan Jian Xue
Bao/Journal of Software, 2013,24(5):977?992 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/4342.htm [doi:
10.3724/SP.J.1001.2013.04342]

疑问：为什么要引用文献[3]呢，是因为同样来自journal of software吗

3）自动生成程序补丁(patch),进而修复程序中的错误.修复中产生的程序补丁既可以自动添加
到程序中,也可以用于指导开发者继续改进代码.与现代软件工业中广泛出现的敏捷开发(agile development)和
持续集成(continuous integration)相结合,自动程序修复方法将有效地降低程序修复的成本.从技术角度来看,研
究者将程序修复看作从潜在的搜索空间(search space)中搜索补丁的过程,而优秀的修复技术可以大幅度提高补
丁搜索的准确率,并减少用于搜索的时间消耗[5,6].该研究思路与基于搜索的软件工程契合[7].例如,自动程序修
复中的先驱方法 GenProg 就是一种基于遗传规划(genetic programming)的 C 程序修复算法[8]

这里讲了：自动生成的补丁的用处 + 工业化潜力 + 基于搜索的软件工程 + 补丁搜索、搜索空间（search space）

4 自动修复面临什么挑战

• 一方面,研究者尝试设计算法为程序自动生成补丁,而所生成的补丁与真实人工添加的补丁尚存较大
  差别;
• 另一方面,研究者正在探索自动修复的实证基础(empirical foundation),然而该研究并非一帆风顺,曾在
  2014 年[9]和 2015 年[10,11]掀起了两次领域内的学术争论

第一个，经常会得到可行但非正确补丁；
第二个，我感觉和第一个一样的。

[9] Monperrus M. A critical review of automatic patch generation learned from human-written patches: Essay on the problem statement
and the evaluation of automatic software repair. In: Proc. of the 36th Int’l Conf. on Software Engineering (ICSE). 2014. 234?242.
[doi: 10.1145/2568225.2568324]
[10] Qi Z, Long F, Achour S, Rinard M. An analysis of patch plausibility and correctness for generate-and-validate patch generation
systems. In: Proc. of the Int’l Symp. on Software Testing and Analysis (ISSTA). 2015. 24?36. [doi: 10.1145/2771783.2771791]
[11] Smith EK, Barr E, Le Goues C, Brun Y. Is the cure worse than the diseaseOverfitting in automated program repair. In: Proc. of
the European Software Engineering Conf. and ACM SIGSOFT Int’l Symp. on Foundations of Software Engineering (ESEC/FSE).
2015. 532?543. [doi: 10.1145/2786805.2786825]

这三篇文献都值得认真一读，无一不是顶会

5 截至本文成文之际(2015 年 8 月 31 日),自动程序修复方法尚未有工业应用.

说明，工业级应用确实难度太大。

6 APR的修复框架，我觉得很有用

7 震惊，kali竟然没有做缺陷定位，而且SemFix竟然没有补丁验证。

需要注意的是:其一,基于代码穷举的方法和基于约束求解的方法也可以看作某种程度的搜索,但本文遵从
基于搜索的软件工程领域的约定,只将第 1 类方法称为基于搜索的补丁生成方法;其二,图 1 的流程是经过总结
已有方法而得到的大概流程 [24,26].在一些修复算法中,某些步骤可能被简化.例如:在基于代码穷举的方法
Kali[10]中,所有的程序语句没有经过故障定位,而按照自然顺序直接排列;而在基于约束求解的方法 SemFix[22]
中,在补丁生成后无需进行补丁的验证.第 3 节详细介绍修复方法

我感觉这句话对我很有用

8 想问下基于约束求解的方法到底咋实现的，还不用补丁验证

基于搜索的方法是程序
修复中的主要部分,尤其在领域创始之初更占有重要地位,代表算法包括基于遗传规划的抽象语法树修复算法
GenProg[5]、基于程序等价性的遗传修复算法 AE[20]、基于随机搜索的修复算法 RSRepair[16]等.基于代码穷举
的方法无差别地变异全部可疑语句,同时,有策略地穷举可能出现的代码修改,追求补丁的有效性而忽略算法效
率.这类算法不多,代表算法包括程序变异算法[21]、代码消除算法 Kali[10].基于约束求解的方法,顾名思义,将补
丁生成转换为约束求解问题,应用求解器直接计算可行解(feasible solution),进而转换为最终补丁,代表算法包
括程序语义修复 SemFix[22]、补丁简化算法 DirectFix[23]、条件 bug 修复 Nopol[24,25]等.

9 文章已经意识到了补丁正确性的问题，看来补丁正确性早有关注

能够通过测试集的补丁并不一定正确.正确性(correctness)指的是修复后的程序达到了预期的行为,即,程序
的输出能够满足潜在的测试预言(test oracle).例如,一个修复划分三角形类别程序的补丁正确,指的是程序可以
无误地划分任何潜在的三角形类别,而不是仅仅满足有限数量的测试用例的通过.正确性目前还不能通过自动
技术完成,只能手动验证.近期的一些工作采用了正确性作为评价标准[10,25,26].

[10] Qi Z, Long F, Achour S, Rinard M. An analysis of patch plausibility and correctness for generate-and-validate patch generation
systems. In: Proc. of the Int’l Symp. on Software Testing and Analysis (ISSTA). 2015. 24?36. [doi: 10.1145/2771783.2771791]
[25] Xuan JF, Martinez M, DeMarco F, Clément M, Lamelas-Marcote S, Durieux T, Le Berre D, Monperrus M. Nopol: Automatic repair
of conditional statement bugs in Java programs. Technical Report, INRIA, 2015. 1?22.
[26] Martinez T, Durieux T, Xuan JF, Monperrus M. Automatic repair of real bugs in Java: A large-scale experiment on the Defects4J
dataset. Technical Report, arXiv:1505.07002, ArXiv, 2015. 1?11.

10 这些文章都值得一看

2012 年,Qi 等人[12,13]提出通过弱重编译(weak recompilation)的方法优化 GenProg 的修复效率,能够较早地
找到补丁.其后的 2013 年,他们[14]应用故障记录的测试用例排序(fault-recorded test prioritization)方法进一步提
高了修复效率.此外,他们[15]还通过程序修复的结果来评估故障定位方法.

[12] Qi Y, Mao X, Lei Y. Making automatic repair for large-scale programs more efficient using weak recompilation. In: Proc. of the
IEEE Int’l Conf. on Software Maintenance (ICSM). 2012. 254?263. [doi: 10.1109/ICSM.2012.6405280]
[13] Qi Y, Mao X, Wen Y, Dai Z, Gu B. More efficient automatic repair of large-scale programs using weak recompilation. Science
China Information Sciences, 2012,55(12):2785?2799. [doi: 10.1007/s11432-012-4741-1]
[14] Qi Y, Mao X, Lei Y. Efficient automated program repair through fault-recorded testing prioritization. In: Proc. of the IEEE Int’l
Conf. on Software Maintenance (ICSM). 2013. 180?189. [doi: 10.1109/ICSM.2013.29]
[15] Qi Y, Mao X, Lei Y, Wang C. Using automated program repair for evaluating the effectiveness of fault localization techniques. In:
Proc. of the Int’l Symp. on Software Testing and Analysis (ISSTA). 2013. 191?201. [doi: 10.1145/2483760.2483785]
[16] Qi Y, Mao X, Lei Y, Dai Z, Wang C. The strength of random search on automated program repair. In: Proc. of the 36th Int’l Conf.
on Software Engineering (ICSE). 2014. 254?265. [doi: 10.1145/2568225.2568254]

11 APR的发展

2013 年,Kim 等人[6]从人工书写的补丁中学习代码模式,并将模式与 GenProg 相融合生成补丁.该方法生成
的补丁可以避免出现通过优化算法而得到的无意义的补丁.Weimer 等人[20]考虑增强发现潜在补丁的能力,提出
了基于程序等价性(program equivalence)的遗传修复算法 AE.
2014 年,Qi 等人[16]通过研究发现,GenProg 算法中的遗传规划算法对于高效生成补丁并不奏效.他们用随机
搜索(random search)替换了遗传算法,并设计了 RSRepair 用于程序修复.实验结果表明:相对于 GenProg 方法,
RSRepair 能够减少生成补丁的时间消耗.
2015 年,Martinez 和 Monperrus[33]通过挖掘程序修复的历史数据,建立了概率模型预测新 bug 的修复.超过 6
万个 Java 语言的代码变更提交(code commit)被转换为抽象语法树,用于修复概率模型的建立.同是 2015 年,
Long 和 Rinard[34]提出了 Prophet,一种学习现有补丁以指导未来补丁排序的算法.它通过最大似然(maximum
likelihood)模型识别最可能成功的补丁的概率,其算法本质是补丁排序的过程.该方法可以修复 69 个真实 bug
中的 15 个,具有一定的准确度

我感觉这些都可以看一看。

12 基于约束求解的方法——原理

2012 年,该类算法的先驱,Nguyen 等人提出 SemFix[22],一种 C 程序的基于约束的语义修复算法.该算法将测
试用例转换为约束,并应用 SMT(satisfiability modulo theories)求解器求解,最终转换为补丁并输出.生成补丁的
过程源自基于组件的程序合成算法(component based program synthesis)[37],该算法将备选语句作为组件,提取预
期的输入输出,并建立约束求解模型.另外,SemFix 采用 Tarantula 算法[38]定位潜在的 bug 位置.与基于搜索的方
法,如 GenProg 不同,SemFix 不需要为生成的补丁调用测试用例验证修复性;约束机制已将测试用例作为输入,
并进而转化为解输出.
2014 年,DeMarco 和 Xuan 等人[24,25]设计了 Nopol,一种面向 Java 条件语句 bug 的基于约束求解的方法.该
方法针对错误条件或条件语句缺失这两种常见 bug 进行修复.过程中,采用天使定位(angelic fix localization)算
法[39]确定潜在修复的位置.与 SemFix 不同,Nopol 中的天使定位算法只针对条件值(即布尔值),其搜索空间小,
计算成本低,可以应用于大规模程序.该算法中采用利于面向对象故障定位的 Ochiai 算法[40]获取被修复语句的
排序.实验中,Nopol 可以修复 22 个大规模 Java 程序的真实 bug 中的 17 个,具有较高的准确率.

2015 年,Mechtaev 等人提出了补丁简化算法 DirectFix[23].该方法将补丁中潜在的程序组件转换为最大可满足性问题(maximum satisfiability,即 MaxSat),求解后转换为具体的简化后的补丁.

Ke 等人[41]设计了 SearchRepair,一种基于语义代码搜索(semantic code search)的修复方法.该方法通过将数
据库中的代码段编码为基于输入输出的 SMT 模型中的约束,进而求解补丁.相对于已有算法 GenProg、 AE 和
RSRepair,算法 SearchRepair 可以获得更多的补丁,且补丁质量较高

13 震惊，原来Nopol如12 中所说： 采用天使定位算法只针对条件值，使得搜索空间变小，计算成本低。。。确实创新了

从这里面我学到了：
1）因为约束求解，如果不只针对条件值的话，会导致搜索空间特别大，这样的话确实不适用于大规模缺陷程序修复

2）原来idea可以这样出来，看来平时得多思考，多读书、论文。

原来原理就是：（参考SemFix的描述）通过将测试用例转化成约束。。。进行求解。

来源：宇内虹游