基于随机搜索和代码相似性的程序自动修复

doi:10.1007/s12204-022-2514-6

摘要/Abstract

摘要： 近年来，自动程序修复方法在软件工程领域发展迅速。然而，现有基于遗传编程的程序修复技术需要验证大量候选补丁，这会消耗大量的计算资源。本文提出了一种基于随机搜索和代码相似性的自动程序修复方法（RSCSRepair）。首先，为了减少候选补丁的验证计算工作量，引入测试过滤来减少测试用例的数量，并使用测试用例优先级排序技术来重组新的测试用例。其次，结合代码相似性和随机搜索来生成补丁。最后，使用补丁过拟合检测方法来提高补丁的质量。为了验证该方法的性能，在 Defects4J 基准评测库上进行了实验。实验结果表明：RSCSRepair 正确修复了54个错误，与 jKali、Nopol、CapGen和SimFix相比，该方法分别提高了14.3%、8.5%、14.3%、10.3%的正确率。

关键词: 程序修复，随机搜索，测试用例优先级，过拟合检测

Abstract: In recent years, automatic program repair approaches have developed rapidly in the field of software engineering. However, the existing program repair techniques based on genetic programming suffer from requiring verification of a large number of candidate patches, which consume a lot of computational resources. In this paper, we propose a random search and code similarity based automatic program repair (RSCSRepair). First, to reduce the verification computation effort for candidate patches, we introduce test filtering to reduce the number of test cases and use test case prioritization techniques to reconstruct a new set of test cases. Second, we use a combination of code similarity and random search for patch generation. Finally, we use a patch overfitting detection method to improve the quality of patches. In order to verify the performance of our approach, we conducted the experiments on the Defects4J benchmark. The experimental results show that RSCSRepair correctly repairs up to 54 bugs, with improvements of 14.3%, 8.5%, 14.3% and 10.3% for our approach compared with jKali, Nopol, CapGen and SimFix, respectively

Key words: program repair, random search, test case prioritization, overfitting detection

中图分类号:

TP311.5

曹鹤玲a,b，刘方正a，石建树a，楚永贺a，邓淼磊a. 基于随机搜索和代码相似性的程序自动修复[J]. J Shanghai Jiaotong Univ Sci, 2023, 28(6): 738-752.

CAO Heling,a,b (曹鹤玲),LIU Fangzhenga (刘方正)，SHI Jianshua (石建树),CHU Yonghea (楚永贺)，DENG Miaoleia*. (邓淼磊). Random Search and Code Similarity-Based Automatic Program Repair[J]. J Shanghai Jiaotong Univ Sci, 2023, 28(6): 738-752.

参考文献 27

[8]	JI T, CHEN L Q, MAO X G, et al. Automated program repair by using similar code containing fix ingredients [C]//2016 IEEE 40th Annual Computer Software and Applications Conference. Atlanta: IEEE, 2016: 197-202.
[1]	WEIMER W, FORREST S, LE GOUES C, et al. Automatic program repair with evolutionary computation [J]. Communications of the ACM, 2010, 53(5): 109- 116.
[9]	KE Y L, STOLEE K T, LE GOUES C L, et al. Repairing programs with semantic code search (T) [C]//2015 30th IEEE/ACM International Conference on Automated Software Engineering. Lincoln: IEEE, 2015: 295-306.
[2]	MONPERRUS M. Automatic software repair: A bibliography [J]. ACM Computing Surveys, 2019, 51(1): 1-24.
[10]	YOO S, HARMAN M. Regression testing minimization, selection and prioritization: A survey[J]. Software Testing, Verification and Reliability, 2012, 22(2): 67-120.
[3]	GAZZOLA L, MICUCCI D, MARIANI L. Automatic software repair: A survey [J]. IEEE Transactions on Software Engineering, 2019, 45(1): 34-67.
[11]	CAO H L, LIU F Z, SHI J S, et al. Automated repair of Java programs with random search via codesimilarity [C]//2021 IEEE 21st International Conference on Software Quality, Reliability and Security Companion. Hainan: IEEE, 2021: 1-8.
[4]	LE GOUES C, NGUYEN T V, FORREST S, et al. GenProg: A generic method for automatic software repair [J]. IEEE Transactions on Software Engineering, 2012, 38(1): 54-72.
[12]	BIAN P, LIANG B, SHI W C, et al. NAR-miner: Discovering negative association rules from code for bug detection [C]//2018 26th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering. Lake Buena Vista: ACM, 2018: 411-422.
[5]	QI Y H, MAO X G, LEI Y, et al. The strength of random search on automated program repair [C]// 36th International Conference on Software Engineering. Hyderabad: IEEE, 2014: 254-265.
[13]	LIANG B, BIAN P, ZHANG Y, et al. AntMiner: Mining more bugs by reducing noise interference [C]//38th International Conference on Software Engineering. Austin: ACM, 2016: 333-344.
[6]	YUAN Y, BANZHAF W. ARJA: Automated repair of Java programs via multi-objective genetic programming [J]. IEEE Transactions on Software Engineering, 2020, 46(10): 1040-1067.
[7]	YUAN Y, BANZHAF W. Toward better evolutionary program repair: An integrated approach [J]. ACM Transactions on Software Engineering and Methodology, 2020, 29(1): 1-53.
[14]	WANG Q Q, PARNIN C, ORSO A. Evaluating the usefulness of IR-based fault localization techniques [C]//2015 International Symposium on Software Testing and Analysis. Baltimore: ACM, 2015: 1-11.
[15]	CAMPOS J, RIBOIRA A, PEREZ A, et al. GZoltar: An eclipse plug-in for testing and debugging [C]//27th IEEE/ACM International Conference on Automated Software Engineering. Esseny: ACM, 2012: 378-381.
[8]	JI T, CHEN L Q, MAO X G, et al. Automated program repair by using similar code containing fix ingredients [C]//2016 IEEE 40th Annual Computer Software and Applications Conference. Atlanta: IEEE, 2016: 197-202.
[9]	KE Y L, STOLEE K T, LE GOUES C L, et al. Repairing programs with semantic code search (T) [C]//2015 30th IEEE/ACM International Conference on Automated Software Engineering. Lincoln: IEEE, 2015: 295-306.
[16]	ABREU R, ZOETEWEIJ P, VAN GEMUND A J C. An evaluation of similarity coefficients for software fault localization [C]//2006 12th Pacific Rim International Symposium on Dependable Computing. Riverside: IEEE, 2006: 39-46.
[17]	JUST R, JALALI D, ERNST M D. Defects4J: A database of existing faults to enable controlled testing studies for Java programs [C]//2014 International Symposium on Software Testing and Analysis. San Jose: ACM, 2014: 437-440.
[10]	YOO S, HARMAN M. Regression testing minimization, selection and prioritization: A survey[J]. Software Testing, Verification and Reliability, 2012, 22(2): 67-120.
[18]	MARTINEZ M, DURIEUX T, SOMMERARD R, et al. Automatic repair of real bugs in Java: A largescale experiment on the defects4j dataset [J]. Empirical Software Engineering, 2017, 22(4): 1936-1964.
[11]	CAO H L, LIU F Z, SHI J S, et al. Automated repair of Java programs with random search via codesimilarity [C]//2021 IEEE 21st International Conference on Software Quality, Reliability and Security Companion. Hainan: IEEE, 2021: 1-8.
[19]	XUAN J F, MARTINEZ M, DEMARCO F, et al. Nopol: Automatic repair of conditional statement bugs in Java programs [J]. IEEE Transactions on Software Engineering, 2017, 43(1): 34-55.
[12]	BIAN P, LIANG B, SHI W C, et al. NAR-miner: Discovering negative association rules from code for bug detection [C]//2018 26th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering. Lake Buena Vista: ACM, 2018: 411-422.
[20]	WEN M, CHEN J J, WU R X, et al. Context-aware patch generation for better automated program repair [C]//40th International Conference on Software Engineering. Gothenburg: ACM, 2018: 1-11.
[13]	LIANG B, BIAN P, ZHANG Y, et al. AntMiner: Mining more bugs by reducing noise interference [C]//38th International Conference on Software Engineering. Austin: ACM, 2016: 333-344.
[21]	JIANG J J, XIONG Y F, ZHANG H Y, et al. Shaping program repair space with existing patches and similar code [C]//27th ACM SIGSOFT International Symposium on Software Testing and Analysis. Amsterdam: ACM, 2018: 298-309.
[14]	WANG Q Q, PARNIN C, ORSO A. Evaluating the usefulness of IR-based fault localization techniques [C]//2015 International Symposium on Software Testing and Analysis. Baltimore: ACM, 2015: 1-11.
[22]	SUN S Y, GUO J X, ZHAO R L, et al. Search-based efficient automated program repair using mutation and fault localization [C]//2018 IEEE 42nd Annual Computer Software and Applications Conference. Tokyo: IEEE, 2018: 174-183.
[15]	CAMPOS J, RIBOIRA A, PEREZ A, et al. GZoltar: An eclipse plug-in for testing and debugging [C]//27th IEEE/ACM International Conference on Automated Software Engineering. Esseny: ACM, 2012: 378-381.
[23]	GHANBARI A, ZHANG L M. PraPR: Practical program repair via bytecode mutation [C]//2019 34th IEEE/ACM International Conference on Automated Software Engineering. San Diego: IEEE, 2019: 1118- 1121.
[16]	ABREU R, ZOETEWEIJ P, VAN GEMUND A J C. An evaluation of similarity coefficients for software fault localization [C]//2006 12th Pacific Rim International Symposium on Dependable Computing. Riverside: IEEE, 2006: 39-46.
[24]	KIM J, KIM S. Automatic patch generation with context-based change application [J]. Empirical Software Engineering, 2019, 24(6): 4071-4106.
[17]	JUST R, JALALI D, ERNST M D. Defects4J: A database of existing faults to enable controlled testing studies for Java programs [C]//2014 International Symposium on Software Testing and Analysis. San Jose: ACM, 2014: 437-440.
[25]	MOTWANI M. High-quality automated program repair [C]//2021 IEEE/ACM 43rd International Conference on Software Engineering: Companion Proceedings. Madrid: IEEE, 2021: 309-314.
[18]	MARTINEZ M, DURIEUX T, SOMMERARD R, et al. Automatic repair of real bugs in Java: A largescale experiment on the defects4j dataset [J]. Empirical Software Engineering, 2017, 22(4): 1936-1964.
[26]	XIN Q, REISS S P. Leveraging syntax-related code for automated program repair [C]//2017 32nd IEEE/ACM International Conference on Automated Software Engineering. Urbana: IEEE, 2017: 660-670.
[19]	XUAN J F, MARTINEZ M, DEMARCO F, et al. Nopol: Automatic repair of conditional statement bugs in Java programs [J]. IEEE Transactions on Software Engineering, 2017, 43(1): 34-55.
[27]	HU Y, AHMED U Z, MECHTAEV S, et al. Refactoring based program repair applied to programming assignments [C]//2019 34th IEEE/ACM International Conference on Automated Software Engineering. San Diego: IEEE, 2019: 388-398.
[20]	WEN M, CHEN J J, WU R X, et al. Context-aware patch generation for better automated program repair [C]//40th International Conference on Software Engineering. Gothenburg: ACM, 2018: 1-11.
[21]	JIANG J J, XIONG Y F, ZHANG H Y, et al. Shaping program repair space with existing patches and similar code [C]//27th ACM SIGSOFT International Symposium on Software Testing and Analysis. Amsterdam: ACM, 2018: 298-309.
[22]	SUN S Y, GUO J X, ZHAO R L, et al. Search-based efficient automated program repair using mutation and fault localization [C]//2018 IEEE 42nd Annual Computer Software and Applications Conference. Tokyo: IEEE, 2018: 174-183.
[23]	GHANBARI A, ZHANG L M. PraPR: Practical program repair via bytecode mutation [C]//2019 34th IEEE/ACM International Conference on Automated Software Engineering. San Diego: IEEE, 2019: 1118- 1121.
[24]	KIM J, KIM S. Automatic patch generation with context-based change application [J]. Empirical Software Engineering, 2019, 24(6): 4071-4106.
[25]	MOTWANI M. High-quality automated program repair [C]//2021 IEEE/ACM 43rd International Conference on Software Engineering: Companion Proceedings. Madrid: IEEE, 2021: 309-314.
[26]	XIN Q, REISS S P. Leveraging syntax-related code for automated program repair [C]//2017 32nd IEEE/ACM International Conference on Automated Software Engineering. Urbana: IEEE, 2017: 660-670.
[27]	HU Y, AHMED U Z, MECHTAEV S, et al. Refactoring based program repair applied to programming assignments [C]//2019 34th IEEE/ACM International Conference on Automated Software Engineering. San Diego: IEEE, 2019: 388-398.