程序自动修复技术是保证软件质量、提高开发效率的有效手段. 目前, 大多数自动修复工具使用测试用例作为补丁正确性验证的最终方法, 有限的测试用例难以对程序进行充分的测试, 因此自动修复工具生成的补丁集合包含大量的不正确补丁. 为了识别不正确补丁, 我们采用对比缺陷修复前后成功测试的执行路径以及生成测试用例的方法来识别修复补丁的有效性, 以解决自动修复工具精度低的问题. 我们的方法评估了来自6个经典的自动修复工具生成的132个补丁, 并成功地排除了80个不正确的补丁并且没有排除正确的补丁, 这表明我们的方法可以有效地排除不正确补丁, 并且提高自动修复工具的精度.
Automatic program repair is an effective technology for ensuring software quality and improving development efficiency. At present, most automatic repair tools use test cases as the final method of patch correctness verification. However, program can barely be fully tested by limited test cases. Consequently, patch sets generated by automatic repair tools contain a large number of incorrect patches. To identify such patches, this study identifies the effectiveness of repair patches by comparing the execution paths of successful tests before and after defect repair and the methods of test case generation to solve the low accuracy problem of automatic repair tools. When the proposed method is applied to evaluate 132 patches generated by six classic repair tools, it successfully excludes 80 incorrect patches, without excluding correct ones. This result shows that the proposed method can effectively exclude incorrect patches and improve the accuracy of automatic repair tools.
现代软件应用程序的复杂性和规模在不断增加, 导致软件中的缺陷难以检测、定位、修复, 自动化的缺陷检测与程序自动修复得到了越来越多的关注. 特别是近几年, 相关研究人员从不同视角提出了多种程序自动修复方法并研制了相关原型工具[
程序自动修复工具产生的补丁质量决定了该修复工具的修复精度, 然而现有的自动修复工具的修复精度很低[
为了识别不正确补丁, 我们采用对比程序修复前后成功测试的执行路径以及生成测试用例的方法来识别不正确补丁, 以解决自动修复工具精度低的问题. 我们的方法可以有效地提高修复工具的修复精度, 并且减少开发者手动排除不正确补丁的时间.
自动程序修复工具产生大量不正确补丁的主要原因是测试用例的不充分, 这将导致难以测试程序的所有预期功能, 即弱测试问题. 弱测试问题可以分为两类: 测试的弱断言问题和测试的弱输入问题. 测试的弱断言问题是测试用例仅关注程序是否抛出异常或者仅关注程序的部分预期功能, 而不关心程序完整的预期功能. 测试的弱输入问题是在缺陷路径上, 程序没有充分的测试用例. 在缺陷路径上, 自动工具对已有的少部分测试用例采用不修改路径功能的策略, 对失败的测试用例采用修改路径的功能策略来生成补丁, 这种修改操作可能会影响已有测试用例之外的测试用例的功能. 在测试套件中, 测试用例的弱输入或弱断言问题都可能导致不正确补丁的产生. 为了简化讨论, 我们假设缺陷程序只包含一个缺陷. 为了使补丁通过所有的测试, 自动修复工具修改或删除程序的原始功能或路径, 由于测试的弱断言和弱输入的问题, 自动修复工具没有充分的测试用例来检测修复后的补丁, 所以自动修复工具就产生了不正确补丁.
测试的弱断言问题可以使得不正确补丁通过所有测试. 示例1展示了一个由自动修复工具jKali[
示例1. jKali为Chart-15缺陷生成的不正确补丁
public void draw(…){+ if(true) return ;…
示例2. Chart-15缺陷的测试程序
public void testDrawWithNullDataset(){… JFreeChart chart = ChartFactory.createPieChart3D(“Test”, null, …); try{ chart.draw(…); success = true; }catch(Exception e){ success = false; } assertTrue(success);}
测试的弱输入问题可以使得不正确补丁非常容易地通过所有测试. 示例3展示了一个由自动程序修复工具Nopol[
示例3. Nopol为Lang-39缺陷生成的不正确补丁
…+ if(
示例4. Lang-39缺陷的正确补丁
…for(int
缺陷程序所有的测试用例仅关注缺陷程序是否抛出异常, 而且没有测试缺陷程序预期功能的测试用例, 对于这种缺陷程序, 自动修复工具采取跳过整个方法的策略, 就能生成通过所有测试的补丁. 这种补丁删除所有预期的功能, 这种补丁没有任何功能和意义, 这种补丁毫无疑问就是不正确补丁. 因此缺陷程序所有测试用例仅关注是否抛出异常并且修复工具采取跳过缺陷代码的修复策略, 这种补丁就是不正确补丁.
当缺陷程序的测试用例仅测试程序的部分预期功能并且没有测试缺陷程序全部预期功能时, 自动修复工具为了使得生成的补丁能够通过所有测试用例, 自动修复工具通过修改了缺陷程序的正确功能来生成补丁, 这种修改是不正确的. 因此, 我们提出一种基于路径功能的评估方法, 如果补丁修改了缺陷程序的正确功能, 则这个补丁就是不正确补丁; 如果补丁没有修改缺陷程序的正确功能, 这个补丁是正确的补丁. 现在的问题是如何判断缺陷程序中的每条路径的功能是正确的或者是符合开发者意图的. 在实践中, 我们发现, 当越多的成功测试用例经过的路径时, 它的功能越有可能是正确的. 在现实中, 测试用例的数目是有限的, 因此我们采取了一种折中的方法, 即少数服从多数的原则来判断路径功能的正确性, 成功测试用例数量多于失败测试用例数量的路径是功能正确的路径. 我们使用路径的序列来表示路径的功能. 通过对比成功测试用例在修复缺陷前后的执行路径的差异, 我们可以判断补丁是否修改缺陷程序的正确功能. 如果成功测试在修复前后程序上的执行路径是相同的, 这意味着补丁没有修改缺陷程序的正确功能; 如果成功测试在修复前后程序上的执行路径是不相同的, 这意味着补丁修改了缺陷程序的正确功能; 失败测试用例的执行路径被改变, 并得到正确的输出, 这表明缺陷程序错误路径已经修复, 程序功能恢复[
示例5展示了修复工具jKali[
示例5. jKali生成的不正确补丁
…
1
if(index>=0&&! allowDuplicateXValues){
…
2
}else{ -if(autoSort){ +if (false) {
this.data.add(-index-1,
3
}else{
this.data.add(
4
}
…
5
在
Chart-5缺陷路径上已存在的测试
序号 |
测试 | 执行结果 | |||
1 | (1, 2) | 1, 3, 5 | 1, 4, 5 | 成功执行 | 0 |
2 | (2, 3) | 1, 3, 5 | 1, 4, 5 | 成功执行 | 0 |
3 | (1, 1) | 1, 3, 5 | 1, 4, 5 | 成功执行 | 0 |
4 | (1, 4) | 1, 3 | 1, 4, 5 | 抛出异常 | — |
弱输入的用例本身不能够识别出测试弱输入问题造成的不正确补丁, 为了能够识别由弱测试输入问题产生的不正确补丁, 直观的想法是增强测试用例. 有很多研究[
其中,
对于被分类为成功的测试输入, 我们利用缺陷程序为成功测试输入生成测试预言, 将测试输入和测试预言作为补丁的测试用例, 补丁无法通过新增的测试用例, 我们认为这是不正确补丁. 对于分类为失败的测试输入, 收集失败的测试输入在缺陷程序中的执行路径和在补丁程序中的路径, 我们对比失败测试用例在缺陷程序和补丁的执行路径的差异, 如果两者执行路径相同, 说明补丁程序没有完全修复缺陷程序, 这说明这个补丁是不正确; 如果路径不同, 我们无法给出判断.
我们选择6个经典修复工具生成的补丁作为数据集,
6个修复工具的补丁统计
工程 | jGenProg | jKali | Nopol2015 | Nopol2017 | DynaMoth | ACS | Total | ||||||||||||||||||||
P | C | O | P | C | O | P | C | O | P | C | O | P | C | O | P | C | O | P | C | O | |||||||
注: P表示可疑补丁的数量, C表示正确补丁的数量, O表示不正确补丁的数量. | |||||||||||||||||||||||||||
Chart | 6 | 0 | 6 | 6 | 0 | 6 | 6 | 1 | 5 | 6 | 0 | 6 | 8 | 0 | 8 | 2 | 2 | 0 | 34 | 3 | 31 | ||||||
Lang | 0 | 0 | 0 | 0 | 0 | 0 | 7 | 3 | 4 | 4 | 0 | 4 | 1 | 0 | 1 | 3 | 1 | 2 | 15 | 4 | 11 | ||||||
Math | 14 | 5 | 9 | 10 | 1 | 9 | 15 | 1 | 14 | 22 | 0 | 22 | 16 | 0 | 16 | 15 | 11 | 4 | 92 | 18 | 74 | ||||||
Time | 2 | 0 | 2 | 2 | 0 | 2 | 1 | 0 | 1 | 8 | 0 | 8 | 3 | 0 | 3 | 1 | 1 | 0 | 17 | 1 | 16 | ||||||
Total | 22 | 5 | 17 | 18 | 1 | 17 | 29 | 5 | 24 | 40 | 0 | 40 | 28 | 0 | 28 | 21 | 15 | 6 | 158 | 26 | 132 |
对于弱测试断言问题, 我们通过补丁和缺陷修复报告获取缺陷程序的缺陷路径, 在缺陷路径中插入打印调用栈的代码, 将所有调用修改后的方法的测试用例和调用栈信息输出到指定文件中, 在Defects4j中, 我们使用编译和测试命令, 对修改后的程序进行编译和测试, 我们可以获得经过缺陷路径的所有测试用例和调用栈信息, 这些测试用例包括失败的测试用例和成功的测试用例. 我们使用符号执行技术[
多种工具补丁的评估结果
工具 | 不正确补丁 | 正确补丁 | 排除的不正确补丁 | 排除的正确补丁 |
jGenProg | 17 | 5 | 13 (76.5%) | 0 |
jKali | 17 | 1 | 10 (58.8%) | 0 |
Nopol2015 | 24 | 5 | 16 (66.7%) | 0 |
Nopol2017 | 40 | 0 | 20 (50.0%) | 0 |
ACS | 6 | 15 | 4 (66.7%) | 0 |
DynaMoth | 28 | 0 | 17 (60.7%) | 0 |
总计 | 132 | 26 | 80 (43.2%) | 0 |
为了说明我们方法的有效性, 我们的方法与另外4种程序补丁评估方法进行对比. 反模式[
在本文中, 我们采用对比程序修复前后成功测试的执行路径以及生成测试用例的方法来识别不正确补丁的方法, 正如实验结果所示, 我们的方法可以有效地过滤掉43.2%的不正确补丁, 因此提高自动修复工具的修复准确率, 并且没有过滤掉任何正确的补丁. 结果表示通过对比修改前后成功测试的执行路径和生成测试用例是一个很有效的方法. 我们希望能找到更多的方法来识别不正确补丁, 解决自动修复工具精度率低的问题.
et al. Context-aware patch generation for better automated program repair. Proceedings of the 2018 IEEE/ACM 40th International Conference on Software Engineering. Gothenburg: IEEE, 2018. 1–11.]]>
et al. Shaping program repair space with existing patches and similar code. Proceedings of the 27th ACM SIGSOFT International Symposium on Software Testing and Analysis. Amsterdam: ACM, 2018. 298–309.]]>
et al. SemFix: Program repair via semantic analysis. Proceedings of the 2013 35th International Conference on Software Engineering. San Francisco: IEEE, 2013. 772–781.]]>
et al. Elixir: Effective object-oriented program repair. Proceedings of the 2017 32nd IEEE/ACM International Conference on Automated Software Engineering. Urbana: IEEE, 2017. 648–659.]]>
Gazzola L, Micucci D, Mariani L. Automatic software repair: A survey. IEEE Transactions on Software Engineering, 2019, 45(1): 34–67, doi: 10.1109/TSE.2017.2755013.
Le Goues C, Nguyen TV, Forrest S,
et al. A systematic study of automated program repair: Fixing 55 out of 105 bugs for $8 each. Proceedings of the 2012 34th International Conference on Software Engineering. Zurich: IEEE, 2012. 3–13.]]>
et al. An analysis of patch plausibility and correctness for generate-and-validate patch generation systems. Proceedings of the 2015 International Symposium on Software Testing and Analysis. Baltimore: ACM, 2015. 24–36.]]>
et al. Is the cure worse than the disease? Overfitting in automated program repair. Proceedings of the 2015 10th Joint Meeting on Foundations of Software Engineering. Bergamo: ACM, 2015. 532–543.]]>
Dong YK, Zhang L, Pang SC,
Xuan JF, Martinez M, DeMarco F,
Dong YK, Wu M, Zhang L,
et al. Automatically generated patches as debugging aids: A human study. Proceedings of the 22nd ACM SIGSOFT International Symposium on Foundations of Software Engineering. Hong Kong: ACM, 2014. 64–74.]]>
et al. Better test cases for better automated program repair. Proceedings of the 2017 11th Joint Meeting on Foundations of Software Engineering. Paderborn: ACM, 2017. 831–841.]]>
Barr ET, Harman M, McMinn P,
et al. Identifying patch correctness in test-based program repair. Proceedings of the 2018 IEEE/ACM 40th International Conference on Software Engineering. Gothenburg: IEEE, 2018. 789–799.]]>
Martinez M, Durieux T, Sommerard R,
et al. Precise condition synthesis for program repair. Proceedings of the 2017 IEEE/ACM 39th International Conference on Software Engineering. Buenos Aires: IEEE, 2017. 416–426.]]>
赵跃华, 阚俊杰. 基于符号执行的测试数据生成方法的研究与设计. 计算机应用与软件, 2014, 31(2): 303–306, doi: 10.3969/j.issn.1000-386x.2014.02.081..
et al. Anti-patterns in search-based program repair. Proceedings of the 2016 24th ACM SIGSOFT International Symposium on Foundations of Software Engineering. Seattle: ACM, 2016. 727–738.]]>
et al. S3: Syntax-and semantic-guided repair synthesis via programming by examples. Proceedings of the 2017 11th Joint Meeting on Foundations of Software Engineering. Paderborn: ACM, 2017. 593–604.]]>