程序缺陷是软件开发及维护工作中难以避免的问题, 可引起软件故障甚至是系统崩溃. 而修复缺陷是软件开发中最耗费人力的任务之一. 因此人们致力于研究自动程序修复(automatic program repair, APR), 旨在自动生成补丁来减少手动修复错误的工作量^[1].

近几年, 业界提出了许多自动程序修复技术^[2–6]. 这些技术都将测试套件作为补丁验证的标准, 旨在生成一个通过所有测试用例的补丁. 然而实践中的测试套件往往不充分, 通过所有测试用例的补丁可能仍然没有修复缺陷, 甚至引入新的缺陷并产生波及效应. 因此, 人们将通过测试套件的补丁表示为合理的补丁. 同时, 若该补丁正确修复错误且未对程序产生副作用,则为正确的补丁, 否则为过拟合补丁. 如Long等人^[7]研究所示, 现有的程序修复系统生成的合理的补丁大部分是过拟合补丁, 一项现有研究^[8]还表明, 当开发人员获得不正确补丁时, 修复中产生的波及效应会降低软件的性能, 从而导致用户对修复结果不认可, 制约着APR工具的推广应用.

我们的目标是分析补丁修改的波及效应, 避免修复副作用的影响, 从而识别更多的过拟合补丁. 目前APR工具采用变异测试的思想, 对程序语句、表达式进行细粒度的修改, 导致程序状态与数据流信息发生改变, 并因为波及效应导致程序产生多粒度成分的变更. 因此, 我们将程序的修改分解为对变量的操作(添加、修改、删除), 基于数据流分析方法为不同变量(局部变量、常量、全局变量)制定相应的分析机制, 充分利用变量间的关联关系, 结合过程内分析与过程间分析, 确定补丁程序中与修改变量有关联关系的节点, 将其加入补丁影响域中, 作为分析结果的集合. 然后根据补丁影响域选择针对性覆盖准则来识别目标覆盖元素, 最后选取路径并生成测试用例实现对程序的充分测试. 我们的方法能有效提高程序修复系统的精度, 降低开发人员手动验证补丁的代价.

本文第1节详细介绍补丁影响域的识别过程. 第2节解释如何匹配针对性覆盖准则以提取目标覆盖元素. 第3节阐述如何通过覆盖元素选取测试路径并生成测试用例. 第4节展开了一系列的实验对比讨论, 评估本文方法的有效性. 第5节对本文工作进行总结, 同时展望下一步的研究工作.

1 补丁影响域识别

补丁中的代码修改是识别补丁影响域的前提. 虽然补丁程序中语句、表达式的修改相对复杂, 但它们包含的变量类型(局部变量、常量、全局变量)及其更改类型(添加、修改、删除)是有限的, 因此我们只需为这些有限类型的变量制定分析机制, 最终的修改影响是它们分析结果的集合. 语句、表达式中包含的变量及其更改类型如表1所示.

下面显示了3个补丁修改示例, 包括对条件语句、表达式操作符以及赋值语句的修改. 如示例3, 工具修改了变量index的赋值表达式. 因此在影响分析中, 我们首先将该补丁修改分解为对index变量的操作, 基于数据流分析方法识别变量index的修改影响.

示例1. Nopol修复FirstZero-bug9生成的补丁

– if (x.length == 0)

+ if (x.length == 1)

示例2. jMutRepair修复Bank-bug6生成的补丁

– int mid = start + (end – start)/2

+ int mid = start + (end + start)/2

示例3. Cardumen修复Inverse-bug2生成的补丁

– index = index + 1

+ index = x[index]

此外, 有些修改产生方法内影响的同时还会产生跨方法的影响. 因此生成CFG时还要分析程序的调用关系, 从而进行过程间分析. 示例4是工具ArjaE生成的一个修复补丁, 该修复产生了跨方法的影响.

示例4. Combination-bug3修复补丁

1. public class CombinationPermutation {

2. 　public long combination(int n, int r) {

3. 　　　Factorial fac = new Factorial();

4. 　　　long combin;

5.　　　 – combin = fac.factorial(n)*(fac.factorial(r)*fac.factorial(n–r));

　　　　+ combin = fac.factorial(n)/(fac.factorial(r)*fac.factorial(n–r));

6.　 return combin;

7.　 }

8.　 public long permutation(int n, int r) {

9–12. ···

13. 　}

14.　　 public long select(int n, int r, boolean flag) {

15. 　return flag ? combination(n, r) : permutation(n, r);

16. 　}

17. }

图1是该程序带有调用关系的CFG. 其中, V₁节点为ArjaE的修改节点, V₂, V₃, V₅节点为受修复影响的节点, 两种节点共同构成Combination-bug3的补丁影响域. 接下来将详细介绍补丁影响域的识别过程.

1.1 过程内影响域识别

过程内影响域识别采用数据流迭代算法^[9], 基于控制流图(control flow graph, CFG)^[10]进行流敏感的分析. 对CFG上的每个节点n, 数据流计算方程如下:

$ in(n) = \left\{ {\begin{array}{*{20}{l}} {init(n), \qquad\qquad\quad\; n = {\rm{entry}}} \\ {\bigcup\nolimits_{p \in pred(n)} {out(p),\quad {\rm{otherwise}}} } \end{array}} \right. $

(1)

$ out(n) = gen(n) \cup (in(n) - kill(n)) $

(2)

其中, n为控制流图当前节点, p为n前驱节点. 式(1)中in(n)计算n的汇入信息; init(n)初始化方法入口处的全局变量与参数; 式(2)中out(n)计算n的出口信息; gen(n)表示n中新产生的数据流信息; kill(n)表示n中注销或改变的数据流信息; pred(n)表示n的所有前驱节点集合.

基于计算的数据流信息, 我们将根据算法1查找过程内路径来获取与修改变量相关的数据流状态发生改变的节点. 第1步获取该点的所有出边并存储在etable中; 第2步对etable进行迭代, 每次获取一条边及该边的endNode. 如果该endNode未被访问, 则添加到节点列表. 如果所有的endNode都已加入路径集或者在第1步中该节点不存在出边, 则将此类节点当作程序终点, 并将它所在的节点序列添加至路径集.

算法1. 查找过程内分析路径算法

输入: 控制流图CFG, 图上节点v, 节点列表NList.

输出: 一组用于过程内分析的路径paths.

说明: getOutedges()为获取一个节点的所有出边

getEndNode()为获取一条边的尾节点

BEGIN

1. Hashtable<String, Edge>etable=v.getOutedges()

2. if (etable is empty) then

3.　 paths.add(NList);

4. else

5. 　 foreach item in etable do

6. 　　edge←etable.get(item);

7.　　 endNode←edge.getEndNode();

8. 　　 if (endNode not in NList) then:

9.　　　　 NList.add(endNode);

10. 　　　findPath(NList, endNode, paths);

11.　　　 newNode– –;

12.　 if (newNode == 0) then

13.　　 paths.add(NList);

END

基于过程内路径, 我们将变量的修改点(change point, cp)分为定义点和使用点, 并使用影响域(influence domain, ID)存储与修改点有关联关系的节点, 由于修改影响会迭代产生, 因此我们基于以下公式获取这些节点.

$ I{D_0} = F(cp) $

(3)

$ I{D_1} = F(I{D_0} - cp) $

(4)

$ I{D_n} = F(I{D_{n - 1}} - \bigcup\limits_{i = 0}^{n - 2} {I{D_i}} )\;(n \geqslant 2) $

(5)

$ ID = \bigcup\limits_{i = 0}^n {I{D_i}} $

(6)

接下来, 我们将详细介绍识别补丁影响域的方法, 即上述公式中的F. 我们将影响域ID分为两类:ID_define和ID_use, 其中, ID_use={ID_c-use, ID_p-use}.ID_c-use中的元素对修改点进行计算使用, ID_p-use中的元素对修改点进行谓词使用. 算法2显示了根据不同类型的修改点获得分类的补丁影响域的过程.

算法2. 识别补丁影响域算法

输入: 控制流图CFG, 修改点cp, 过程内路径paths.

输出: 补丁影响域ID_type, type={define, c-use, p-use}.

说明: getCanculateUse()为获取计算使用cp变量的节点

getPredicateUse()为获取谓词使用cp变量的节点

BEGIN

1. if (cp.type is use) then

2. 　vex←getCanculateUse();

3. 　 ID_c-use.add(vex);

4. 　vex←getPredicateUse();

5. 　 ID_p-use.add(vex);

6. else if (cp.type is definition) then

7. 　 ID_define.add(cp);

8. 　 foreach path in paths do

9.　　 if ( $\scriptstyle \exists $ vex in path usescp) then

10.　　 vex←getCanculateUse();

11. 　　 ID_c-use.add(vex);

12. 　　vex←getPredicateUse();

13.　　 ID_p-use.add(vex);

END

1.2 过程间影响域识别

过程间影响域识别的目标是识别补丁修改的跨方法影响, 因此它分析的目标点(target point, tp)是变更的方法参数、返回值和全局变量所在的节点, 分析的结果是程序中受影响的方法集. 此时目标点有3种类型: {call, return, global}. 其中, call表示目标点上方法参数更改, return表示目标点上返回值更改, global表示目标点上全局变量更改. 分析结束后将继续进行过程内影响域识别.

我们根据算法3查找受影响的方法集. 对于方法返回值的变更, 首先根据方法之间的关系找到调用它的方法, 然后将该方法添加到过程间影响域IMD中; 当分析方法调用时, 我们需要获取它调用的方法或者根据SEA关系^[11]获得受影响的方法, 并将其添加到IMD中; 对于全局变量, 使用数据流分析确定它的使用点, 这些使用点所在的新方法也将添加到IMD中.

算法3. 识别过程间影响域算法

输入: 控制流图CFG, 目标点 tp.

输出: 过程间影响域IMD (受影响的方法集).

说明: getReturn(tp)为获取使用tp返回值的方法

getCall(tp)为获取tp调用的方法

getExecute(tp)获取与tp具有SEA关系的方法

getGlobal(tp)为获取使用tp全局变量的方法

BEGIN

1. if (tp.type==“return”) then

2. 　new_method←getReturn(tp);

3.　 IMD.add (new_method);

4. else if (tp.type==“call”) then

5. 　new_method←getCall(tp) or getExecute(tp);

6. 　IMD.add (new_method);

7. else if (tp.type==“global”) then:

8. 　new_method←getGlobal(tp);

9. 　IMD.add (new_method);

END

2 覆盖元素提取

覆盖元素提取是基于覆盖准则实现的, 目的是确定测试用例必须覆盖的程序元素. 上面我们提到, 补丁影响域识别是基于数据流分析方法通过分析变量的定义与使用来实现的. 因此我们主要关注与修改变量相关的def-use对.

我们在数据流分析中区分了两种类型的变量使用: 计算使用(即c-use), def-use对表示为dcu(V_d, V_u, x); 谓词使用(即p-use). 此时, 出现两个def-use对, 分别表示为dpu(V_d, (V_u, V_t), x)和dpu(V_d, (V_u, V_f), x), 其中x在V_u处有两个不同的分支(V_u, V_t)和(V_u, V_f): 前者表示使用x的条件语句的真分支, 后者是假分支. 因此, 覆盖元素提取将基于c-use覆盖、p-use覆盖提取目标覆盖元素, 增强程序测试的充分性.

3 测试路径选取

提取覆盖元素之后, 需要选择一条或多条包含覆盖元素的测试路径. 基于待覆盖节点, 根据补丁程序中节点的控制关系和蕴含关系找出从控制流图入口到目标节点以及从该节点到控制流图出口的必经节点, 基于这些节点选取测试路径. 假设V_a, V_b为必经节点序列中的两个节点, 我们首先从节点V_a的子节点中找出一个能到达V_b的节点V_c, 然后填充V_c到V_b之间的路径. 由此可见, 节点V_c的选取是填充V_a和V_b间路径的关键. 因此, 我们基于以下原则选择节点V_c.

(1)若节点V_a, V_b间不存在覆盖元素, 则遵循最短路径选择.

(2)若存在待覆盖节点V_g, 且该节点可到达V_a的另一个子节点, 则选取V_g作为节点V_c.

(3)若节点V_a不存在满足(2)的子节点, 则选取V_a的一个待覆盖子节点作为节点V_c.

(4)若V_c为循环判定节点, 则该节点最多在路径上出现2次, 否则为1次(该原则可有效解决实际执行时的无限循环问题).

此外, 将选取的路径用于生成测试用例之前还需进行不可达路径检测, 以降低测试用例生成的代价. 我们基于数据流分析, 通过区间运算计算路径上的变量和表达式的取值范围, 从而确定待测路径是否为不可达路径. 如果路径path的一个节点上变量a的取值为空, 则说明该节点与之前某节点矛盾, 从而判定path为不可达路径.

4 实验分析 4.1 数据集

我们基于两个数据集QuixBugs^[12]和BuggyJavaJML^[13], 包括jGenprog^[6], RSRepair^[14], Nopol^[3], DynaMoth^[15], JMutRepair^[16], SimFix^[2]生成的165个补丁上评估了我们的方法. 表2、表3展示了数据集的评估结果. 其中, jGenprog和RSRepair采用遗传算法, 通过定义代码片段的交叉和变异操作生成修复补丁; Nopol将程序中的变量用于生成补丁的同时还编码了一些常量(如0、1等)来支持补丁生成; DynaMoth针对方法调用进行约束求解来修复程序; JMutRepair通过改变条件语句中的表达式来生成补丁; SimFix替换相似语句中的变量来生成补丁. 这些工具覆盖了两种通用性较强的补丁生成方法: 基于启发式搜索(jGenprog, RSRepair, SimFix, JMutRepair)^[17]和基于语义约束(Nopol, DynaMoth). 并且由于大多数动态APR工具只能修复带有一个缺陷的程序, 因此这两个数据集中每个程序都只有一个缺陷, 且每个程序都最大程度地保留了原始程序的特性. 与GT_Invariants^[18]、RGT_{InputSampling}^[19]以及OpenJML^[13]在上述两个数据集上对比识别过拟合补丁的效果, 同时计算每种技术的准确率, 以充分例证本文方法的有效性.

4.2 实验设计与实现

对于避免修复副作用影响的问题, 我们需要根据测试路径生成测试用例, 覆盖受补丁修改影响的程序元素. 我们使用测试用例生成工具Randoop4.3.1^[20]生成测试输入, 将运行时间设置为3 min.

我们在人类编写的正确补丁上运行新的测试输入, 并将测试输出作为测试预言. 我们总是删除该过程中运行失败的测试用例(失败的测试包括运行过程报错、运行超时以及输出错误等), 之后用符号执行技术^[21]对测试用例进行筛选, 删除重复项以得到最小的测试用例集.

我们在修复工具生成的补丁上执行这些测试用例. 如果补丁使任何测试用例失败, 则将其评估为过拟合. 对于第2个数据集, 我们收集原始正确程序来筛选测试用例集并运行测试套件以生成测试预言, 从而达到人类编写的正确的补丁的测试效果. 并且, 我们根据QuixBugs数据集中的纯随机测试方法对BuggyJavaJML中的补丁程序进行同样的纯随机测试, 以进行对比实验.

4.3 实验结果与分析

本节将分析我们的方法评估过拟合补丁的结果. 我们将其与手动评估以及其他3种技术的结果进行比较. 最后, 我们讨论了漏报和误报的案例.

表2、表3第1行列出了由至少一个修复工具修复的错误程序的名称(表格中为程序名称的字母缩写). 第2行显示所有工具生成的补丁程序总数. 中间部分分别显示了每种自动评估技术识别的过拟合补丁数量、错误地将正确补丁识别为过拟合补丁的误报数量、识别的正确补丁数量以及未将过拟合补丁识别出来的漏报数量. 我们在最后一行显示了手动评估的结果, 并基于该结果检测自动评估技术的准确性. 最后, 使用式(7)计算评估技术的准确性(见表2、表3最后一列).

$ 准确率=\frac{过拟合+正确}{过拟合+误报+正确+漏报} $

(7)

观察表2、表3, 我们可以发现Our method评估过拟合补丁的准确率高于RGT_{InputSampling}. 这表明Our method的性能优于纯随机测试生成. 此外, Our method比GT_Invariants和OpenJML具有更高的准确性, 这是因为Our method比两者产生更少的误报(QuixBugs: 0:12; BuggyJavaJML: 0:27).

虽然Our Method和RGT_{InputSampling}在两个基准集上都不存在误报, 但是在两个数据集中Our method比RGT_{InputSampling}分别多分类25个和15个过拟合补丁. 相反, GT_Invariants和OpenJML分别有12个和27个误报.

上述数字之间的差异可以通过他们收集的信息种类来解释, 并且受到异常值的影响. 比如, GT_Invariants可以捕获测试用例特定的值而不是取值范围. 例如可以捕获x=0而不是x≤0, 这一现象背后的原因是因为测试用例只有x=0的情况, 此时GT_Invariants捕获的不变量本身就是过拟合的, 因此GT_Invariants虽然可以识别更多的过拟合补丁, 但是准确率不高.

在BuggyJavaJML数据集上, OpenJML对过拟合补丁的分类比其他两种更多. 这主要是因为它将27个正确补丁分类为过拟合补丁. 如示例5, ArjaE在修复缺陷时会对程序进行不必要的修改. 我们观察到, 该补丁除了修复原始缺陷之外, 还增加了一句不必要的赋值语句“fact=fact*c”, 该语句因为插入在JML指定为纯的方法中造成了副作用, 因此从模块化验证的角度来看程序不正确, OpenJML因此产生误报.

示例5. ArjaE为Factorial-bug2生成的补丁

for (c = 1; c < n; c++)

　 fact=fact*c;

　+ fact=fact*c;

returnfact;

通过分析表2、表3, 我们发现RGT_{InputSampling}的漏报最多(QuixBugs: 26; BuggyJavaJML: 20). 这表明随机生成测试输入进行补丁评估的有效性较弱.

我们讨论了一个只被Our method正确识别为过拟合补丁的案例. 如示例6, 该修复位置位于for循环中, 生成的修复程序使用“(n % n) == 0”代替“i < max”. 手动评估显示, 此修补程序过拟合: 如果n=0, 则Cardumen生成的修复程序和标准补丁的行为不同, 程序产生的输出也不同. 修复后的程序在n取特定值0时会抛出java.lang.ArithmeticException异常. 由于RGT_{InputSampling}无法生成此特定输入, 因此无法正确识别该补丁是否为过拟合补丁.

示例6. Cardumen为GET_FACTORS生成的补丁

@@ –16, 7 +16, 7 @@

return new ArrayList<Integer>();

int max = (int)(Math.sqrt(n) + 1.0);

– for (int i=2; i < max; i++)

+ for (int i = 2; (n % n) == 0; i++)

if (n %i == 0)

ArrayList<Integer> prepend = new ArrayList<Integer>(0);

5 结论

本文研究了因测试套件不充分而引发的过拟合问题, 提出了一种基于数据流分析的过拟合补丁识别方法. 本文方法在两个数据集上进行了评估, 可以过滤97.2%和94.6%的过拟合补丁. 实验结果表明, 所提出的过拟合补丁识别方法可以有效避免修复副作用的影响, 进而识别更多的过拟合补丁. 在未来的工作中, 我们将考虑回归测试最小化和选择排序技术, 对测试用例进行优先级排序, 从而加快补丁正确性评估.