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

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

匹配部分语法子树,输出修改之后的语法子树.比如替换一个变量为函数调用,其输入是变量对应的子树(根节
点是叶子节点),输出则是函数调用对应的子树(根节点是内部节点).Refazer 在提取模板时(重写规则序列),采用
了基于演绎的程序综合方法(deductive program systhesis)生成重写规则.最后,基于人工定义的启发式规则对其
生成的模板进行排序.其基本思想是倾向于尽可能复用已有的代码,且被修改的代码不要包含过多的上下文信
息,目的是使得到的模板具有更强的鲁棒性.文中通过修复学生作业程序验证 Refazer 的修复效果,实验结果表
明,Refazer 可以帮助 87%的学生修复缺陷代码.
2018 年,Zhong 和 Mei [87] 提出了一个针对异常(exception)相关缺陷的修复技术 MiMo.与之前介绍的自动修
复方法不同的是,MiMo 针对给定的程序缺陷推荐对应的修改操作(repair shape).本文的主要出发点是之前的实
证研究关注于挖掘通用类型的代码修改操作,期望为自动化的修复工具提供指导.论文作者认为:当划定缺陷的
范围,代码修改推荐效果将有希望进一步提升.为此,作者首先开发了一个根据程序的异常信息对缺陷类型进行
自动分类的工具 ExFi,并构建了一个数据集.其中,数据集里的每个修复都被标记为特定类型的缺陷.MiMo 应用
ChangeDistiller,在该数据集中提取缺陷修复的修改操作.对于新的缺陷,MiMo 通过搜索缺陷报告或相关的 Issue
报告中的异常信息来匹配需要使用的代码修改操作.该方法目前只能针对异常相关的缺陷推荐代码修改操作,
尚不能直接生成修复补丁.但该论文为以后的研究提供了一个新的思路,即:通过将缺陷分类提取补丁模板,有
希望提升现有自动修复方法的准确率.
2018 年,Gulwani 等人 [88] 提出了 Clara,用于修复学生的作业程序.与 Refazer 不同的是,Clara 不依赖历史修
复样例,而是直接聚类相同功能的正确代码.在该过程中,Clara 根据程序的控制流以及变量的使用情况映射功
能相同的两段代码.此外,Clara 会考虑程序执行过程中变量的取值情况映射不同变量.最后,被归为一类的代码
随机选择一个作为该类的代表.在修复阶段,通过匹配缺陷程序与正确程序中的变量和结构生成对应的修改.
[7]
2019 年,Bader 等人 提出了自动修复技术 GetaFix.其基本方法与 Genesis 类似,在代码的语法树级别提取
代码修改操作以及代码修改所涉及到的上下文信息.在应用其修复新的缺陷时,首先将缺陷代码与模板进行匹
配,匹配成功,则可以应用对应的修改操作生成补丁.由于不同的代码修改操作涉及的上下文特征不同,为了保
证提取到的模板具有一定的通用性(在相似但不相同的上下文中可以应用),GetaFix 使用层次聚类(hierarchical
clustering)算法对提取的模板进行归类合并,其目的是抽象掉同一类别模板中的不相同特征,例如使用不同的变
量名等.但是,如果对模板中的代码特征过度抽象,会导致模板不能准确地描述其所修改代码的特征,模板的准
确性将降低.为了平衡模板的通用性与准确性,GetaFix 在聚类过程中使用 Anti-Unification 算法避免过度抽象.
由于该方法依赖相似的代码修改作代码抽象,因此对缺陷的重复性有一定要求,目前仅针对比较常见的一些静
态工具检测出的缺陷类型,如空指针异常(NullPointerException)、缺少指定编码(DefaultCharSet)等.
类似的,2019 年,Bavishi 等人 [89] 同样针对静态分析工具检测出的缺陷进行修复,并实现了修复推荐工具
Phoenix.它同样依赖于聚类算法对从历史中提取的补丁模板进行抽象.为此,作者提出了一个领域特定语言
(DSL),用来描述代码的修改模板.Phoenix 同样在代码的抽象语法树上提取修改模板.具体讲,根据静态分析工具
报告的缺陷代码位置,Phoenix 从对应的语法树节点出发,使用 DSL 描述代码修改的上下文信息,实际上可以表
示为有限状态自动机(finite state automata),自动机中的每个节点对应语法树中的节点,节点间的连边代表节点
之间的关系,比如变量声明(decl).在模板的聚类阶段,Phoenix 采用贪心策略将所有兼容(compatible)的模板进行
合并,在合并的过程中,会匹配不同模板所对应的自动机并求交集.此处的兼容性根据修改模板中所包含的字符
串和涉及到的节点类型等因素决定,最终的目标是聚类之后的模板之间彼此不兼容.在应用其修复缺陷阶段,首
先是匹配模板的上下文信息,匹配成功即可应用对应修改.
2020 年,Koyuncu 等人 [90] 提出了 FixMiner,通过迭代式聚类算法,从相似的代码修改中挖掘可以复用的代码
修改模板.本文定义了抽象语法树上的代码编辑脚本语言,用来描述代码修改操作.在迭代式聚类过程中,
FixMiner 将编辑脚本拆分成 3 个子部分进行索引,分别是代码结构(shape)、代码修改(action)以及代码文本
(token).通过上述拆分,可以实现对代码修改聚类的有效加速.在实验验证部分,作者将 FixMiner 挖掘的修复模板
用于修复工具 PAR 中,结果表明,其挖掘得到的模板可以用于修复真实缺陷.与此类似,Liu 等人 [91] 提出的修复工