Page 45 - 《软件学报》2021年第9期

姜佳君 等:软件缺陷自动修复技术综述 2669

补丁语法等价)、Top-N(正确补丁排在候选补丁中的前 N 位置)召回率等.

2 程序缺陷自动修复技术综述
本节基于第 1 节中介绍的缺陷自动修复研究框架,根据补丁生成阶段所采用的技术,对已有的修复方法进
行分类.本文将已有的自动修复技术分为以下 4 大类:基于启发式搜索(例如 GenProg [26−28] 和 SimFix [29] )、基于
人工修复模板(例如 PAR [30] 和 SketchFix [31] )、基于语义约束(例如 Nopol [32] 和 Angelix [33] )以及基于统计分析(例
[9]
[8]
如 DeepFix 和 SequenceR )的自动修复技术.需要说明的是,单一的缺陷修复方法可能同时应用多种技术.比
如,SimFix 在项目中搜索相似代码的同时也利用了从历史修复补丁中提取的常用修改操作对补丁进行过滤.在
这种情况下,我们将根据方法的主要创新对其进行分类.
2.1 基于启发式搜索
(1) 利用变异算子
基于启发式搜索的自动修复技术通过人工定义启发式规则,指导修复补丁的生成过程.2009 年被提出来的
缺陷自动修复技术 GenProg [26−28] 是典型的基于启发式搜索的技术,其基本思想是代码具有重复性,因此通过复
用项目中的代码,有希望产生正确的修复补丁.在搜索过程中,GenProg 采用遗传算法,通过定义代码片段的交叉
和变异操作实现已有代码片段的重新组合,增大补丁的搜索空间.该方法将生成补丁所通过的测试数量作为优
化目标,对候选补丁迭代应用交叉和变异操作,直至产生可以通过所有测试的补丁.通过实验证明,该方法可以
修复程序中的缺陷.该工作使得自动修复技术进入了一个新的时期,吸引了大量的科研人员开始对自动修复技
术进行探索.
Qi 等人 [34] 在 2014 年提出了 RSRepair,该方法采用与 GenProg 方法相同的修复框架,只是将其中的遗传算
法替换成了随机搜索.实验对比分析表明:GenProg 中的遗传算法并没有发挥较大的作用,使用随机搜索算法不
仅可以正确修复同样的缺陷,且在 23 个缺陷上,随机搜索相比遗传算法实现了更高的效率.
在此之后,先后有一系列针对 GenProg 进一步优化的方法被提出.
2018 年,Oliveira 等人 [35] 提出了一种新的代码修改表示方法来对遗传算法进一步优化.原始的 GenProg 方
法中所采用的代码修改表示将代码与修改作为两个独立的部分,互不干扰.GenProg 每次首先从所有定义的变
异算子中选择一个,例如交叉或变异,然后根据此再去选择候选的修复补丁或代码片段,最后应用对应的变异算
子产生新的候选补丁.Oloveira 等人提出的代码表示方法将变异算子和算子对应的代码元素编码在同一条“染
色体”上.该表示方法的好处在于,变异阶段可以复用之前的代码操作.此外,通过变异“染色体”上的变异算子部
分,该方法可以实现对同一段代码的不同变异操作.因此,相比于传统的遗传算法,其灵活性更强,可以提升修复
工具的补丁生成能力.
2018 年,Yuan 等人 [36] 提出了基于多目标遗传算法的自动修复方法 ARJA,该方法同样是对遗传算法中的表
示方法进行了优化.ARJA 将代码补丁表示为三元组〈b,u,v〉,分别用来编码代码上的修改位置、修改操作类型和
复用的代码元素.该方法由于记录了代码的修改过程,因此具有更强的表达能力,通过变异操作可以获得更大的
补丁空间.除此之外,ARJA 将补丁生成过程转化为多目标优化问题,其两个优化目标分别是补丁对代码改动的
大小以及应用补丁后程序通过测试的数量.因此,该方法倾向于修改较小的修复补丁.最后,ARJA 在补丁验证阶
段通过移除与当前补丁无关的测试以及通过编译器分析提前排除不合法的补丁等方式提升补丁验证的效率.
最终实验结果表明,ARJA 正确修复缺陷的数量接近 GenProg 的 4 倍.
与 ARJA 类似,2018 年,Mehne 等人 [37] 同样通过筛选程序中的测试样例对修复的过程进行加速.其具体方法
为:对于给定的修复补丁,如果一个测试在运行的过程中没有覆盖补丁所修改的代码位置,那么该测试在验证该
补丁时可以被过滤,即节省了部分测试运行的时间开销.除此之外,Mehne 等人还通过过滤候选出错位置实现修
复加速.在程序运行时,分别搜集通过测试和未通过测试在候选出错位置处的变量取值情况:如果变量在未通过
测试运行中的取值是其在通过测试运行中取值的子集,则对应代码位置出错的概率会比较小,在修复的时候可
以被过滤掉.其依据为,同样的变量取值有很大的概率触发相同的程序错误.