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

2670 Journal of Software 软件学报 Vol.32, No.9, September 2021

2018 年,Sun 等人 [38] 通过对遗传算法的种群初始化以及变异过程进行优化来改善原有的 GenProg 修复方
法.GenProg 方法在初始化最初的种群时,根据缺陷定位的结果从高到低采用贪心策略逐一尝试.然而,由于实际
中缺陷定位的结果并不一定准确,真正出错的代码可能排在比较靠后的位置或者是候选位置相关的代码.在真
实的工业场景下,定位的不准确会导致修复工具生成更多不正确的修复补丁,从而降低修复工具的实用性.针对
上述问题,Sun 等人提出弱化定位结果的影响,在初始化种群时,同时考虑多处候选出错位置,并同时生成候选补
丁,以此来缓解定位不准确带来的影响.除此之外,为了更高效地探索补丁空间,该文中方法采用了两种交叉操
作,将候选补丁根据适应度分数分为高、低适应度两个集合,然后对其分别进行交叉操作,在提升高质量补丁收
敛速度的同时,可以有效探索更大的补丁空间.类似方法还有 Dantas 等人 [39] 在 2019 年提出的使用语言模型中的
Doc2Vec 和 LSTM 模型优化 GenProg 的适应度函数,以及 2020 年 Villanueva 等人 [40] 提出的使用新颖性搜索
(novelty search)算法对 GenProg 的搜索进行优化,以避免陷入局部最优解.本文不再逐一详细介绍.
上述方法主要针对 GenProg 方法在算法上的一些优化,实际上对其补丁生成空间影响不大,依然是复用项
目中已有代码片段.2019 年,Yuan 等人 [41,42] 针对 GenProg 的补丁空间进行了扩充,将 GenProg 和 PAR [30] (基于人
工模板的补丁生成方法,将在第 2.2 节详细介绍)方法结合提出了 ARJA-e.根据上面的介绍我们知道,GenProg 是
直接复用项目中已有的代码来生成补丁.在此基础之上,ARJA-e借用 PAR方法的修复补丁模板再额外产生一些
新的代码片段加入到遗传算法的候选补丁集合中,与其原有的补丁一起进行变异和遗传.除此之外,ARJA-e 对
GenProg 的适应度函数(fitness function)进行了优化.根据上面的介绍,GenProg 将通过测试的个数作为补丁的适
应度值.然而实际上,单个测试函数中可能存在多条断言(assertion),任何一条断言的失败都会导致整个测试函
数的失败.ARJA-e 针对该情况进行了细化处理,将以测试为单位修改为以断言为单位,根据补丁通过断言的数
量评价补丁的适应度.在 Defects4J 数据集 [43] 上的实验验证表明:ARJA-e 相比 GenProg 正确修复数量有了明显
提升,大概是后者的 4 倍.
2019 年,Ghanbari 等人 [44] 提出了基于 JVM 字节码(bytecode)的缺陷修复技术 PraPR.在此之前的自动修复技
术主要针对源代码.上述所介绍的基于变异的技术均通过定义源码上的变异算子生成修复补丁.与字节码相比,
源码级别的修复存在结构复杂、反复编译耗时等缺点.字节码级别的修复可以有效克服上述缺点.类似遗传算
法,PraPR 根据预先定义好的字节码上的遗传算子对缺陷代码进行修改.由于字节码中的结构种类有限且简单,
因此变异算子所能覆盖到的补丁空间会更大.但是由于对字节码修改不需要二次编译,可以直接在 JVM 上运
行,所以其效率会比较高.实际验证效果也表明,该方法相比已有的技术具有更高的效率.该方法因为不涉及到
源代码的结构,也因此具有更强的通用性,可以修复任何中间代码为 JVM 字节码的编程语言程序,例如 Java,
Kotlin,Scala 等.然而 PraPR 也存在其固有的缺点,字节码简单的同时也伴随着部分程序语义信息的丢失,例如变
量名称等,使得基于源码字面语义的启发式方法不适用于对 PraPR 的进一步优化.
(2) 利用历史修复补丁
与上述基于遗传算法的缺陷修复不同,Le 等人 [45] 认为:在不同的应用软件中,软件缺陷会重复出现,之前的
缺陷修复历史可以为修复补丁提供有效的指导.因此,引入了第三方数据源(即历史修复)对 GenProg 进行优化.
基于该思想,作者在 2016 年提出一个新的缺陷修复技术 HistoricalFix.该方法同样采用了遗传算法来生成修复
补丁,不同的是,HistoricalFix 仅仅采用变异(mutation)而不使用交叉(crossover)操作.在每次变异之后,计算候选
补丁所涉及的修改操作,根据其他项目历史修复中常用的代码修改对补丁进行筛选.该方法相比之前的遗传算
法引入了第三方的缺陷修复历史数据,对补丁的生成起到了更好的指导作用.最终的实验证明,该方法相比原始
的 GenProg 方法有了非常大的效果提升.在 Defects4J 数据集中的 90 个缺陷上进行验证,GenProg 只能正确修复
1 个缺陷,而 HistoricalFix 可以正确修复 23 个.该实验表明,历史修复数据可以为补丁生成提供有效指导.
与 HistoricalFix 类似,2018 年,Wen 等人 [46] 同样应用从历史修复中挖掘的代码修改操作指导补丁生成,其不
同点在于考虑了代码修改的上下文信息,从而可以提供更加准确的指导,有效约束补丁的搜索空间.基于该方
法,作者实现了一个自动修复工具 CapGen.在历史修复提取阶段,Wen 等人通过记录被修改代码节点的父节点
类型信息作为修改应用的前置条件,例如:“insert EXPR_STMT under METH_DECL”表明,插入的“EXPR_