示例演化驱动的学生程序自动修复
|
摘要
已有的程序自动化调试研究大多面向工业软件,而学生程序调试具有缺陷数多、类型复杂等特有难点问题,因此,针对学生程序设计应用背景,研究程序自动修复方法,利用模板示例程序指导补丁的演化.改进了遗传编程算法,包括适应度的计算、变异体的生成方式和变异位置及操作的选择方式,使其更加适合修复学生程序.提出了基于示例的静态错误定位方法,能够识别缺陷程序和参考程序差异和可能的变异操作,有效地缩小补丁的搜索空间以提高修复的准确性.提出了基于执行值序列的变量映射方法,以降低变异体的编译错误,提高修复的准确性.在此基础上,设计并实现了示例演化驱动的Java学生程序自动修复系统.实验结果表明,该方法可以修复含有多缺陷学生程序,对于所用的测试集,当学生程序只有1个～2个错误时,修复率将近100%;当含有3个缺陷时,修复率约为70%;当含有4个及以上缺陷时,修复率约为50%.
Most existing program repair researches are oriented to industrial software. Student program debugging has many unique problems, such as multiple bugs and complex bug types. Therefore, according to the application background of student programming, the automatic repair method is studied, and template programs are used to guide the evolution of patches. Genetic programming algorithm has been improved, such as fitness calculation, mutants generation, and mutation position and operator selection, to make it more suitable for repairing student programs. A static fault location method based on sample programs is proposed, which identifies the difference between the defect program and the sample program and recognizes the possible mutation operators. It can effectively reduce the search space of the patch and improves the accuracy of the program repair. A variable mapping method based on execution value sequence is proposed to reduce compilation errors of mutants and improve the accuracy of program repair. On this basis, an example-evolution-driven system for repairing students' Java programs was designed and implemented. The experimental results show that the method can repair student programs with multiple bugs. For the test set, the repair rate is nearly 100% when the student programs have only 1～2 bugs. When there are 3 bugs, the repair rate is about 70%. When there are 4 or more bugs in the student programs, the repair rate is about 50%.
Most existing program repair researches are oriented to industrial software. Student program debugging has many unique problems, such as multiple bugs and complex bug types. Therefore, according to the application background of student programming, the automatic repair method is studied, and template programs are used to guide the evolution of patches. Genetic programming algorithm has been improved, such as fitness calculation, mutants generation, and mutation position and operator selection, to make it more suitable for repairing student programs. A static fault location method based on sample programs is proposed, which identifies the difference between the defect program and the sample program and recognizes the possible mutation operators. It can effectively reduce the search space of the patch and improves the accuracy of the program repair. A variable mapping method based on execution value sequence is proposed to reduce compilation errors of mutants and improve the accuracy of program repair. On this basis, an example-evolution-driven system for repairing students' Java programs was designed and implemented. The experimental results show that the method can repair student programs with multiple bugs. For the test set, the repair rate is nearly 100% when the student programs have only 1～2 bugs. When there are 3 bugs, the repair rate is about 70%. When there are 4 or more bugs in the student programs, the repair rate is about 50%.
引文
[1]Wong WE,Gao R,Li Y,Rui A,Wotawa F.A survey on software fault localization.IEEE Trans.on Software Engineering,2016,42(8):707-740.
[2]Wang KC,Wang TT,Su XH,Ma PJ.Key scientific issues and state-art of automatic software fault localization.Chinese Journal of Computers,2015,38(11):2262-2278(in Chinese with English abstract).[2]王克朝,王甜甜,苏小红,马培军.软件错误自动定位关键科学问题及研究进展.计算机学报,2015,38(11):2262-2278.
[3]Zhong H,Su Z.An empirical study on real bug fixes.In:Proc.of the IEEE/ACM Int’l Conf.on Software Engineering.Firenze:IEEE,2015.913-923.
[4]Xuan JF,Ren ZL,Wang ZY,Xie XY,Jiang H.Progress on approaches to automatic program repair.Ruan Jian Xue Bao/Journal of Software,2016,27(4):771-784(in Chinese with English abstract).http://www.jos.org.cn/1000-9825/4972.htm[doi:10.13328/j.cnki.jos.004972][4]玄跻峰,任志磊,王子元,谢晓园,江贺.自动程序修复方法研究进展.软件学报,2016,27(4):771-784.http://www.jos.org.cn/1000-9825/4972.htm[doi:10.13328/j.cnki.jos.004972]
[5]Gazzola L,Micucci D,Mariani L.Automatic software repair:A survey.IEEE Trans.on Software Engineering,2019,45(1):34-67.
[6]Goues CL,Nguyen TV,Forrest S,Weimer W.GenProg:A generic method for automatic software repair.IEEE Trans.on Software Engineering,2012,38(1):54-72.
[7]Singh R,Gulwani S,Solar-Lezama A.Automated feedback generation for introductory programming assignments.In:Proc.of the ACM SIGPLAN Symp.on Principles of Programming Languages.Seattle:ACM Press,2013.15-26.
[8]Kim D,Kwon Y,Liu P,Kim IL,Perry DM,Zhang X.Apex:Automatic programming assignment error explanation.In:Proc.of the2016 ACM SIGPLAN Int’l Conf.on Object-oriented Programming,Systems,Languages,and Applications.Amsterdam:ACMPress,2016.311-327
[9]Yi J,Ahmed UZ,Karkare A,Tan SH,Roychoudhury A.A feasibility study of using automated program repair for introductory programming assignments.In:Proc.of the 2017 11th Joint Meeting on Foundations of Software Engineering.Paderborn:IEEE,2017.740-751.
[10]Weimer W,Fry ZP,Forrest S.Leveraging program equivalence for adaptive program repair:Models and first results.In:Proc.of the IEEE/ACM Int’l Conf.on Automated Software Engineering.Palo Alto:IEEE,2013.356-366.
[11]Long F,Rinard M.Automatic patch generation by learning correct code.In:Proc.of the ACM SIGPLAN Symp.on Principles of Programming Languages.Santa Barbara:ACM Press,2016.298-312.
[12]Mechtaev S,Yi J,Roychoudhury A.Angelix:Scalable multiline program patch synthesis via symbolic analysis.In:Proc.of the IEEE/ACM Int’l Conf.on Software Engineering.Austin:IEEE,2016.691-701.
[13]Wang T,Su X,Wang Y,et al.Semantic similarity-based grading of student programs.Information and Software Technology,2007,49(2):99-107.
[14]Kou,R,Higo Y,Kusumoto S.A capable crossover technique on automatic program repair.In:Proc.of the Int’l Workshop on Empirical Software Engineering in Practice.YamadaokaSuita:IEEE,2016.45-50.
[2]Wang KC,Wang TT,Su XH,Ma PJ.Key scientific issues and state-art of automatic software fault localization.Chinese Journal of Computers,2015,38(11):2262-2278(in Chinese with English abstract).[2]王克朝,王甜甜,苏小红,马培军.软件错误自动定位关键科学问题及研究进展.计算机学报,2015,38(11):2262-2278.
[3]Zhong H,Su Z.An empirical study on real bug fixes.In:Proc.of the IEEE/ACM Int’l Conf.on Software Engineering.Firenze:IEEE,2015.913-923.
[4]Xuan JF,Ren ZL,Wang ZY,Xie XY,Jiang H.Progress on approaches to automatic program repair.Ruan Jian Xue Bao/Journal of Software,2016,27(4):771-784(in Chinese with English abstract).http://www.jos.org.cn/1000-9825/4972.htm[doi:10.13328/j.cnki.jos.004972][4]玄跻峰,任志磊,王子元,谢晓园,江贺.自动程序修复方法研究进展.软件学报,2016,27(4):771-784.http://www.jos.org.cn/1000-9825/4972.htm[doi:10.13328/j.cnki.jos.004972]
[5]Gazzola L,Micucci D,Mariani L.Automatic software repair:A survey.IEEE Trans.on Software Engineering,2019,45(1):34-67.
[6]Goues CL,Nguyen TV,Forrest S,Weimer W.GenProg:A generic method for automatic software repair.IEEE Trans.on Software Engineering,2012,38(1):54-72.
[7]Singh R,Gulwani S,Solar-Lezama A.Automated feedback generation for introductory programming assignments.In:Proc.of the ACM SIGPLAN Symp.on Principles of Programming Languages.Seattle:ACM Press,2013.15-26.
[8]Kim D,Kwon Y,Liu P,Kim IL,Perry DM,Zhang X.Apex:Automatic programming assignment error explanation.In:Proc.of the2016 ACM SIGPLAN Int’l Conf.on Object-oriented Programming,Systems,Languages,and Applications.Amsterdam:ACMPress,2016.311-327
[9]Yi J,Ahmed UZ,Karkare A,Tan SH,Roychoudhury A.A feasibility study of using automated program repair for introductory programming assignments.In:Proc.of the 2017 11th Joint Meeting on Foundations of Software Engineering.Paderborn:IEEE,2017.740-751.
[10]Weimer W,Fry ZP,Forrest S.Leveraging program equivalence for adaptive program repair:Models and first results.In:Proc.of the IEEE/ACM Int’l Conf.on Automated Software Engineering.Palo Alto:IEEE,2013.356-366.
[11]Long F,Rinard M.Automatic patch generation by learning correct code.In:Proc.of the ACM SIGPLAN Symp.on Principles of Programming Languages.Santa Barbara:ACM Press,2016.298-312.
[12]Mechtaev S,Yi J,Roychoudhury A.Angelix:Scalable multiline program patch synthesis via symbolic analysis.In:Proc.of the IEEE/ACM Int’l Conf.on Software Engineering.Austin:IEEE,2016.691-701.
[13]Wang T,Su X,Wang Y,et al.Semantic similarity-based grading of student programs.Information and Software Technology,2007,49(2):99-107.
[14]Kou,R,Higo Y,Kusumoto S.A capable crossover technique on automatic program repair.In:Proc.of the Int’l Workshop on Empirical Software Engineering in Practice.YamadaokaSuita:IEEE,2016.45-50.