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

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

2016 年,D’Antoni 等人 [71] 认为,已有方法仅仅通过代码的语法变化来衡量补丁的复杂度来对补丁进行排序
并不是有效的手段,进而提出一种基于代码结构和语义特征的补丁排序方法 Qlose.与 DirectFix 类似,在语法层
面,Qlose 通过对比修改前后代码的语法结构差异作为补丁的语法复杂度,例如修改表达式的个数等.修改数量
越少,表示补丁越简单.在语义层面,Qlose 针对给定的测试集计算语义差异.其具体做法是:对比通过的测试在修
复前后程序上执行的路径,并计算路径的汉明距离(Hamming distance)来衡量补丁的复杂度.汉明距离越小,表示
补丁越简单.最后,将上述两方面约束作为约束求解器的软约束求解可行修复补丁.该方法在一定程度上提升了
补丁的质量.
Mechtaev 等人 [33] 在 2016 年提出了针对 SemFix 和 DirectFix 的优化方法 Angelix,该方法同样采用基于组
件的程序合成方法,通过使用受控的符号执行技术使其具有更好的延展性(scalability),可以用于修复较大规模
项目中的缺陷.此外,Angelix 采用增量的方式生成补丁,即首先根据部分测试生成修复补丁,然后做回归测试,将
不能通过的测试再添加到用于生成补丁的测试集中,如此递归生成补丁.这样的方法可以有效简化程序的约束,
将约束求解器的部分负担转移到运行测试验证,在一定程度上可以提升修复效率.Angelix 相比之前的工作可以
修复程序中的多处错误.
2016 年,Rothenberg 等人 [72] 针对符号执行难以处理程序中的循环问题(搜索空间爆炸),提出了 AllRepair 方
法.该方法通过指定循环展开次数和递归深度将代码转换为无循环代码,这样可以将代码转换为静态单赋值
(static single assignment)形式,进而可以直接转换为 SMT 的约束.AllRepair 为了产生简单的修复补丁,当发现一
个修改序列可以通过测试,会将其所有的超集排除.该方法相比之前的方法主要的贡献是使用循环展开近似原
程序,其优点是可以处理循环,缺点是得到的修复补丁并不能保证通过测试,需要执行测试进一步验证.
2016 年,Xuan 等人 [32] 提出一种针对 Java 程序中条件语句错误的修复技术 Nopol,该技术针对出错语句的类
型定义了不同修复策略:如果定位出错的代码位置是条件语句,则 Nopol 通常生成的修复补丁为修改原始的条
件语句;如果定位出错的代码位置是非条件语句,则通过添加一个新的条件跳过当前语句的执行实现修复.在针
对特定类型的缺陷生成修复补丁时,Nopol 首先在出错的代码位置搜集所有变量的取值情况,然后根据期望的
条件语句取值情况(true 或 false),将程序语义编码成为 Z3 [73] 约束求解器的约束进行求解.在 Nopol 方法中,除了
程序中的变量可以用于生成修复补丁,同时编码了一些常量(例如 0,−1 等)以及常用函数调用(如 size(⋅),length(⋅)
等)用于支持补丁生成.该方法相比上述基于约束求解器的方法,由于仅针对条件语句(只有 true 和 false 两种取
值)错误,不需要依赖符号执行搜集程序的约束信息,因此其在大项目上的可延展性会更好.缺点是只修复条件
语句缺陷.
2017 年,Chen 等人 [74,75] 提出一种基于程序契约(contract-based)的缺陷修复技术 JAID.该方法基于程序状态
抽象技术,通过监视并记录测试运行过程中不同程序位置的可使用表达式取值情况,同时结合测试执行的结果
定位程序中的可疑缺陷位置,最后通过预定义模板生成修复的补丁.在修复过程中,JAID 同时结合了函数的纯
度分析(purity analysis)等软件分析技术指导补丁生成.该方法中的核心是,根据程序运行过程中的表达式取值
来推断程序的规约以确定出错位置.因此,本文将其归为基于语义约束的修复技术.
实际上,上述介绍的使用约束求解器的方法辅助生成修复补丁的核心是搜集程序中的约束并转化为约束
求解问题.2017 年,Nguyen 等人 [76] 将缺陷修复转换为程序的可达性问题进行求解,其本质和上述技术类似,只是
将测试执行的约束映射为程序中的未知条件语句,然后可以使用可达性问题的求解方法进行计算.该方法被证
明得到的结果一定是正确的(sound),但不能保证完备性(completeness).
2017 年,Le 等人 [77] 提出了缺陷自动修复技术 S3,同时考虑程序的语法和语义特征指导补丁的生成过程.与
之前介绍的基于约束求解的方法类似,S3 通过符号执行搜集测试的约束信息作为约束求解器的输入;不同的是,
S3 为不同的代码修改操作预定义了优先次序,在约束求解的过程中,会根据该排序优化补丁的生成过程.类似
地,最后,S3 通过对比修改之后的代码与修改之前代码的语法以及语义的相似程度对补丁进行排序,例如代码修
改的大小、修改前后同一表达式的取值情况等,相似程度高的补丁排序优先.
2018 年,Mechtaev 等人 [78] 在 Angelix 的基础之上进一步优化并提出了 SemGraft 修复工具.SemGraft 在以下