基于变异和约束求解的程序缺陷自动修复方法
2024-01-22董兰，洪玫，伍佳
董 兰，洪 玫，伍 佳
(四川大学 计算机学院(软件学院)，四川 成都 610065)
0 引 言
目前软件缺陷自动修复技术[1]主要有基于启发式搜索、语义约束、人工修复模板、统计分析等方法，其中大部分方法都通用的，缺陷修复的召回率和准确率不高[2]。对于基于人工修复模板的方法具有针对性，只能针对常见、特征明确的缺陷类型。而基于测试的缺陷修复方法则依赖于通过的测试数据，而在Defects4 J库中有95%以上的程序缺陷在被修复之前没有相应的未通过测试，而测试覆盖率与补丁质量成正相关，挖掘到的程序规约信息有限，约束求解效果不好[2]。
本文针对Java程序中出现频率较高的条件语句的相关缺陷修复问题，将启发式搜索方法与语义约束求解方法相结合，提出一个更高效的解决方案。针对条件语句缺失错误，基于约束求解，通过收集程序语义信息，采用基于组件的程序合成技术，生成候选条件表达式。同时，针对条件语句逻辑表达式错误，首先采用变异技术，生成候选补丁；其次，对于条件语句逻辑表达式错误中不能利用变异技术修复的缺陷，再使用约束求解方法生成补丁。最后验证补丁的有效性。该方案解决了Java程序自动修复中的重要问题，并在修复效率上有所提高，值得借鉴和参考。
1 相关工作
在自动软件缺陷修复技术中，常用的修复方法是基于启发式搜索的技术，该方法通过改变原始缺陷程序生成新程序作为候选补丁。代表性研究有GenProg、RSRepair、Kail等方法。GenProg[3]采用抽象语法树、遗传算法，运用交叉、变异算子等生成程序候选补丁。RSRepair[4]选择随机搜索来指导生成-验证过程，而Kail[5]是一种试图通过删除潜在的不必要但有害的功能来修复程序的技术。
基于语义约束的缺陷修复方法，其综合应用缺陷定位、天使调试、约束求解、程序合成等多种技术[6]来修复补丁，代表性研究有SemFix、Angelix和Nopol等方法。SemFix[7-9]综合使用天使调试和基于组件的程序合成算法，约束求解器求解获得程序补丁。Angelix[10]旨在保持可伸缩性的同时综合多行修复。而Nopol[11，12]合成了在条件或循环语句中发生的一条更改条件组成的修复，利用天使修复定位获得天使值，通过合成条件表达式修复缺陷。
针对Java程序缺陷的修复方法，除了Nopol方法之外，还有针对修复Java语言的内存溢出、资源泄露、空指针引用、内存溢出等缺陷的FootPatch方法[13]，以及高精度的条件语句综合技ACS[14]，针对空指针、数据越界以及类型强转缺陷的Genesis自动修复技术[15]。
由于单一的自动缺陷修复方法不能保证任何类型的缺陷都可以成功修复[16]，因此，针对特定缺陷类型，考虑综合的自动化修复方法就有一定的研究价值。本文针对Java程序中条件语句逻辑错误和条件语句缺失错误两类缺陷，借鉴启发式搜索中的变异方法和语义驱动的约束求解、组件合成等方法，并对这些方法进行综合运用，以提高缺陷修复率和补丁精度。
2 问题描述和基本思路
研究者通过挖掘和分析7个大型开源Java项目的历史缺陷修复记录，总结了9大类、27个缺陷修复模式。其中，最常见的是IF条件相关(IF)，占19.7%～33.9%[17]。而IF-CC和 IF-APC所对应的条件语句错误和条件语句缺失两类缺陷在实际缺陷中占据较大比例，见表1。
表1 Java程序中的缺陷修复模式
因此针对Java程序中的条件语句逻辑错误和条件语句缺失错误的常见缺陷，探索缺陷自动修复方法。条件语句逻辑表达式错误是指条件表达式存在逻辑错误，导致程序无法执行到期望的分支；条件语句缺失错误是指在执行某些操作之前，缺少前置条件的检查，比如检测空指针。
针对上述两类条件语句相关的缺陷，本文采用收集测试信息(G1)，使用本文提出的方法生成满足的候选补丁(G2)，最后通过测试套件验证候选补丁(G3)这3个阶段过程，实现缺陷的自动修复。首先通过执行相关的测试用例，收集程序执行时待修复程序位置处可访问的数据变量和对应的值，形成待求解的修复方程式；其次，确定可修复程序位置的语句类型以采用不同的补丁生成方案进行缺陷修复。如果待修复位置是条件语句表达式缺陷，先采用变异技术产生候选补丁，如果没有相符合的补丁，再使用基于约束求解方法，合成条件表达式；如果是条件语句缺失缺陷，直接应用基于约束求解方法生成表达式，并将生成的表达式作为前置条件添加在源程序中。最后，运行测试用例，再次进行补丁验证。整体方案流程如图1所示。
图1 方案流程
3 基于测试数据形成缺陷修复方程式
根据测试用例的执行，收集与待修复缺陷相关的测试用例执行过程中的上下文信息。
3.1 条件表达式实际输入数据收集
在程序执行过程中，收集执行到待修复条件语句exp-patch之前所有可访问的变量以及变量值，包括基本类型数据和面对对象程序的特定数据，主要包括局部变量、成员变量、方法参数以及它们对应的值。将收集到的数据称为输入数据，用Il，m，n，其中，l表示待修复条件表达式exp-patch所在位置，n和m分别表示第n个测试用例的第m次执行。除此之外，还增加3个基准常数{-1，0，1}来丰富Il，m，n， 其它的数据都可以基于这3个基准常数构建。假设l位置在可修复的程序位置范围内有a个基本变量和一组对象集合O(共O个对象)，则Il，m，n包含的数据如下：
a个基本变量以及变量对应的变量值。如：a→10；
w个boolean值，分别表示O个对象是否为空。如：obj1=null→false；
object中对象各自对应类的状态查询方法及其输出，如obj2.size()→5；
常数，如0，1，-1。
3.2 条件表达式期望输出结果收集
当执行完待修复的条件表达式exp-patch时，能使所有测试用例能执行通过的值称为条件表达式的期望输出。取值范围为{true，false}，用Ol，m，n来表示期望输出。如果l位置为条件语句，对于测试用例执行是失败的，天使值即为exp-patch期望输出，天使值(angelicValue)指可以让失败的测试用例执行成功的值，取值范围为{true，false}；如果是成功的测试用例，条件表达式exp-patch的实际输出即为期望输出。如果l位置为非条件语句，针对失败的测试用例，Ol，m，n其对应值均为false，对于成功的测试用例，Ol，m，n均为true。
3.3 缺陷修复方程式形成
根据上述实际输入的数据Il，m，n和期望的输出结果Ol，m，n， 可以形成式(1)的待求解的修复方程式F，定义为
(1)
所有的
4 基于变异分析技术的程序候选补丁生成
变异分析一般用于检测测试套件对程序缺陷的发现能力[18]，其思路主要是对原程序P中引入小的代码修改，形成缺陷的变体P′， 然后运行测试套件TS，观察测试套件在原程序P和程序变体P′中的执行情况，查看测试套件是否能够检测到引入的缺陷。其中，引起代码修改的操作被定义为变异算子。
基于文献的研究[19]，对于条件语句缺陷自动修复，将变异技术应用其中。如果待修复的表达式exp-patch为if条件语句时，使用预先设计的变异算子，在该条件表达式中植入小的代码变更，产生所有可能的一阶程序变体P′bug， 作为候选补丁。本文依据修复错误的条件三要素：条件子句、变量和操作符，设计了如下变异算子。
变异算子1：否定条件表达式，如if(a>0‖b<0) 变异成if(！a>0‖b<0)；
变异算子2：替换同类运算符，包括运算符、关系运算符和逻辑运算符，如if(a>0‖b<0) 变异成if(a>0‖b>0)；
变异算子3：移除条件表达式中的一个条件子句，如if(a<0‖b<0) 变异成if(a<0)；
在应用变异算子3时，还可以考虑失败的测试用例所对应的天使值，如果所有失败测试用例的天使值都为true，则表示失败测试用例执行完条件表达式的输出应该由false转变为true；如果都为false，则表示失败测试用例执行完条件表达式的输出应该由true转变为false。通过移除一个条件子句来收缩、扩张条件表达式的判定范围，具体的移除方式为：收缩判定范围：if(clause‖clause1)>=if(clause)。 扩张判定范围：if(clause&&clause1)>=if(clause)。
本文只使用Pbug的一阶变体作为候选补丁，比如，对条件表达式if(x>0‖y<0) 进行变异，所有可能的候选补丁见表2。
表2 基于变异算子生成补丁
由于利用变异技术产生条件表达式的候选补丁时，可能会生成大量无效的程序变体。为了避免这种情况，此时，3.3节得到的修复方程式可用于初步筛选变异生成的程序变体，使满足程序语义约束的变体作为候选补丁，以减少待验证补丁的数量。
5 基于约束求解的程序补丁合成方法
对于上述候选补丁不能修复缺陷的情况，作为补充本文还提供一种语义驱动的补丁生成方法。利用自动化程序合成技术，将补丁生成问题转化为约束求解的问题，将求得解转化为程序补丁。通过运行测试用例，获取一系列的<输入，期望输出>对，作为I/O的Oracle；定义一组用于合成程序的基础组件，如操作符、常数值、函数方法等；合成过程以一系列<输入，期望输出>对和基础组件作为输入，输出一段满足所有<输入，期望输出>对的程序[9]。
假设待修复的条件表达式exp-patch的实际输入数据包含两个变量x和y以及常数0，获取的I/OOracle为 <{x=1，y=2，0}，true>、 <{x=2，y=1，0}，false>， 可用基础组件C={+、-、>、<}。 一种有效的合成过程如图2所示，用矩形表示组件，并用位置号标识(标签“loc”)，边表示如何将在给定位置生成的值用作在另一位置的输入(与每个位置关联的标签“input”)，式(1)生成约束表达式之后，SMT求解器为与每个位置关联的变量输入找到适当的值。
图2 基于约束求解的程序补丁合成示例
假设合成条件表达式exp-patch使用一组基础组件 {f1，f2，…，fn}，fi表示第i个组件，Ii表示组件的输入，ri表示组件的输出。所有组件的输入集合和输出集合分别为下述I和R
待求解条件表达式的一组实际输入为I0(即Il，m，n)， 对应期望输出为r(即Ol，m，n)， 所有的输入输出集合为
IO={I∪R∪I0{r}}
定义位置变量
LOC={locx|x∈IO}
locx表示IO中的每个元素x的索引位置；取值变量
V={vx|x∈IO}
vx表示IO中的每个元素x的取值。对于每个测试用例的每次执行，位置变量代表了补丁的组成结构，应该保持一致。取值变量则被SMT求解器使用，用于保证合成的程序符合I/Ooracle。
LOC应该保证语法约束和语义约束[7]。语法约束规定了在程序语法结构上待求解的条件表达式exp-patch应该满足的要求，其定义如式(2)所示
(2)
式中：φfixed该约束表示对于待求解条件表达式的实际输入I0中的第i个元素，其位置变量loc的值为i； 对于待求解条件表达式的期望输出r中的元素，其位置变量loc的值M。φoutput(R)该约束限制一个基础组件fi所定义的中间变量r；其位置变量loc，应该在 |I0|+1 到M之间。φinput(I) 表示不同的基础组件能够处理不同类型的数据，该约束对每个基础组件所使用的数据x的数据类型进行限制。定义type(x) 方法可以返回与x具有相同数据类型的数据，基础组件的输入数据x只能取自于这些数据，即LOCx=LOCy。φcons(LOC，R) 该约束表示每个基础组件所定义的变量都应该有不同的位置变量，以便在其中使用该变量时，可以索引到。φacyc(LOC，I，R) 该约束则限制了在同一个位置的元素应该具有相同的数据值。
除了语法约束之外，LOC还应满足一定的语义约束。其定义如式(3)所示
(3)
式中：φlib(I，R) 该约束表示任意一个基础组件的输入vIi经过基础组件所定义的计算fi后，输出值为vri，φconn(LOC，I0，r，I，R) 该约束限制了在同一个位置的元素应该具有相同的数据值。
结合语法约束和语义约束，对于I/Ooracle中所有的<输入，期望输出>对，LOC需要满足的完整约束如式(4)所示
(4)
利用SMT求解器对约束θ求解，若LOC为该约束的解，则根据LOC和定义的基本组件，可以构造出满足程序约束的条件表达式exp-patch。
如果可修复程序位置为if条件语句，则直接使用表达式exp-patch对原始表达式进行替换，形成候选的程序补丁；如果为非if条件语句，则将表达式exp-patch作为前置条件添加，形成候选补丁。
6 实验验证
实验基于上述问题设计实现了一个条件语句缺陷自动修复工具原型MSFix，进行方案的可行性和有效性验证。
实验对象选择Defects4 J[20]数据集中的14个Java项目的62个条件语句缺陷，其中条件语句错误缺陷41个，条件语句缺失缺陷21个，见表3。
表3 实验对象信息
实验采用召回率和准确率来评价缺陷修复效果。在修复一个缺陷的过程中，如果能够找到一个有效补丁能通过所有的测试，则认为该缺陷被成功修复，召回率计算方式如式(5)所示
(5)
在修复缺陷的过程中，如果一个有效补丁正确修复了缺陷，则认为该补丁是正确的补丁，补丁准确率计算方式如式(6)所示
(6)
6.1 可行性实验——Java程序中条件语句缺陷的修复
通过运行MSFix，对上述的缺陷进行修复，返回MSFix的修复结果。如果缺陷修复成功，将MSFix修复的补丁与Defects4 J提供的补丁进行比较，验证补丁的有效性。由表4的实验结果可知，在上面提供的项目中69个条件语句缺陷来说，MSFix能够修复39个缺陷，并且整体的召回率为62.90%。
表4 MSFix的整体实验结果
在62个条件语句缺陷中，也有23个缺陷没有修复成功。分析其修复失败的原因主要是：
(1)由于本文方案输入的可疑语句是通过可疑分数进行定位的，可疑语句定位时会计算可疑分数阈值，并舍弃可疑分数低于阈值的程序方法，只对剩余方法中的程序语句进行分析。由于部分缺陷(如 Math-26)的测试用例不够充足，缺少失败测试用例对错误语句的覆盖，导致错误语句所在的程序方法的可疑分数较低。在进行可疑语句定位时，含有错误语句的程序方法被舍弃，最终可疑语句列表中没有真正错误的语句。
(2)由于本文方案输入的可疑语句是通过缺陷定位得到的。在定位可修复程序位置过程中，期望每个失败的测试用例都存在一个使其能够执行通过的天使值。由于部分缺陷(如Lang-16)的一个失败测试用例中存在多个assert断言，这些assert断言覆盖了if结构的then分支和else分支。在使用true/false替换if条件表达式后，重新运行这个失败的测试用例，没有办法同时满足多个assert断言。因此，无法找到这个失败测试用例的天使值，导致可修复程序位置定位失败。通过以上分析可知，测试用例的质量不高是导致缺陷修复失败的重要原因。针对情况(1)，可以通过额外增加失败的测试用例来提高错误语句的覆盖率，使其能够出现在可疑语句列表中，或者排名更靠前。针对情况(2)，可以通过拆分失败的测试用例，使每个测试用例中只有一个assert断言，在可修复程序位置定位中，更可能找到使失败测试用例都通过天使值。
6.2 有效性实验——缺陷修复效果与其它方法的对比
目前针对修复Java程序缺陷的方案中，Nopol[11，12]、jGenProg[3]和jKali[5]这3种工具比较有代表性，在比较多的相关研究中引用。因此，在方案有效性实验中，选择这3种工具作为比较对象。对上述选择的62个条件语句缺陷，分别应用上述的3个工具和MSFix进行自动修复，记录并分析每个工具的修复效果，计算每个工具的缺陷召回率和准确率，并进行分析。表5展示了4种方法的整体修复结果。可以看出MSFix和上面3种修复工具相比，其修复的正确补丁数量是最多的，一共修复了21个，而其它3个工具却修复没有超过有效补丁数量的一半。并且MSFix的召回率和准确率都分别达到了62.90%和53.85%。其它3种工具的召回率和准确率都比较偏低。
表5 4种工具对比的整体实验结果
使用Venn图来展示这4个工具所修复缺陷之间的交叉重叠情况。由表5和图3可知，jGenProg和jKal的召回率相对较低，并且被jGenProg和jKal这两个工具修复的缺陷都能够被Nopel和MSFix修复。MSFix和与Nopel相比，MSFix能够修复17个Nopel无法修复的缺陷，召回率提高了22.58%。
图3 4个工具修复缺陷韦恩
由于jGenProg和jKali在基于各自定义的操作修改缺陷程序形成候选补丁时，对所有类型的缺陷都执行相同的修复操作。虽然能够修复条件语句缺陷，但相比于MSFix和Nopol，jGenProg和jKali，缺少更有针对性的分析。因此，在修复条件语句缺陷时，jGenProg和jKali生成的有效补丁相对较少，缺陷修复较低。另外，Nopol在生成候选补丁时，只使用了基于约束求解的补丁生成方法。本文方案则在此基础之上，增加、并且优先使用变异技术生成程序补丁，综合使用两种补丁生成方法，使得对条件语句缺陷具有更高的修复率。
在补丁准确率方面，4个工具都基于测试套件进行修复，但本文方法在生成程序补丁时，优先考虑使用变异技术对原始表达式进行变异，基于真实的缺陷修复记录，为条件语句定义合适的变异算子，该方法更可能产生符合开发人员预期的程序补丁。因此，MSFix能够优先输出正确的程序补丁，补丁准确率相对其它3种方法都有所提高。
7 结束语
缺陷自动修复方法是帮助开发人员减少调试成本的有效技术，为了修复Java程序中常见的条件语句缺失缺陷和条件语句逻辑错误缺陷，本文提出了基于变异分析和约束求解的程序补丁合成技术，实验结果表明本文方案能够修复真实的条件语句缺陷，并且相比于现有修复方法，本文方案具有更好的修复效果。在相当程度上解决了Java程序中条件语句缺陷的自动修复问题。但本文的研究基于Java程序，对其它语言的适应性还有待进一步的实验验证。在变异分析中，只采取了3种变异算子，在未来工作中，可以考虑增加更多的变异算子，以提高缺陷修复的能力；此外实验结果表明本方法修复的补丁和现有的工具相比，修复的补丁既有重叠的又有独有的，为了提高缺陷自动修复的可靠性和完备性，在未来工作中，可以考虑综合使用补丁修复的工具，对本文方法做出进一步的改进，以提高补丁修复率。
