Evaluating the usage of fault localization in automated program repair: an empirical study

Abstract

Fault localization techniques are originally proposed to assist in manual debugging by generally producing a rank list of suspicious locations.With the increasing popularity of automated program repair, the fault localization techniques have been introduced to effectively reduce the search space of automated program repair. Unlike developers who mainly focus on the rank information, current automated program repair has two strategies to use the fault localization information: suspiciousness-first algorithm (SFA) based on the suspiciousness accuracy and rank-first algorithm (RFA) relying on the rank accuracy. However, despite the fact that the two different usages are widely adopted by current automated program repair and may result in different repair results, little is known about the impacts of the two strategies on automated program repair. In this paper we empirically compare the performance of SFA and RFA in the context of automated program repair. Specifically, we implement the two strategies and six well-studied fault localization techniques into four state-of-the-art automated program repair tools, and then use these tools to perform repair experiments on 60 real-world bugs from Defects4J. Our study presents a number of interesting findings: RFA outperforms SFA in 70.02% of cases when measured by the number of candidate patches generated before a valid patch is found (NCP), while SFA performs better in parallel repair and patch diversity; the performance of SFA can be improved by increasing the suspiciousness accuracy of fault localization techniques; finally, we use SimFix that deploys SFA to successfully repair four extra Defects4J bugs which cannot be repaired by SimFix originally using RFA. These observations provide a new perspective for future research on the usage and improvement of fault localization in automated program repair.

Keywords

automated program repair / fault localization / empirical study

References

[1] Pearson S, Campos J, Just R, Fraser G, Abreu R, Ernst M D, Pang D, Keller B. Evaluating and improving fault localization. In: Proceedings of the 39th International Conference on Software Engineering. 2017, 609–620

[2] Wong W E, Gao R, Li Y, Abreu R, Wotawa F. A survey on software fault localization. IEEE Transactions on Software Engineering, 2016, 42(8): 707–740

[3] Parnin C, Orso A. Are automated debugging techniques actually helping programmers? In: Proceedings of the 2011 International Symposium on Software Testing and Analysis. 2011, 199–209

[4] Kochhar P S, Xia X, Lo D, Li S. Practitioner’s expectations on automated fault localization. In: Proceedings of the 25th International Symposium on Software Testing and Analysis. 2016, 165–176

[5] Gazzola L, Micucci D, Mariani L. Automatic software repair: a survey. IEEE Transactions on Software Engineering, 2017, 45(1): 34–67

[6] Jiang J, Xiong Y, Zhang H, Gao Q, Chen X. Shaping program repair space with existing patches and similar code. In: Proceedings of the 27th ACM SIGSOFT International Symposium on Software Testing and Analysis. 2018, 298–309

[7] Le Goues C, Nguyen T, Forrest S, Weimer W. Genprog: a generic method for automatic software repair. IEEE Transactions on Software Engineering, 2011, 38(1): 54–72

[8] Mechtaev S, Nguyen M D, Noller Y, Grunske L, Roychoudhury A. Semantic program repair using a reference implementation. In: Proceedings of the 40th International Conference on Software Engineering. 2018, 129–139

[9] Nguyen H D T, Qi D, Roychoudhury A, Chandra S. Semfix: program repair via semantic analysis. In: Proceedings of the 35th International Conference on Software Engineering. 2013, 772–781

[10] Xuan J, Martinez M, Demarco F, et al. Nopol: automatic repair of conditional statement bugs in java programs. IEEE Transactions on Software Engineering, 2016, 43(1): 34–55

[11] Qi Y, Mao X, Lei Y, Wang C. Using automated program repair for evaluating the effectiveness of fault localization techniques. In: Proceedings of the 2013 International Symposium on Software Testing and Analysis. 2013, 191–201

[12] Qi Y, Mao X, Lei Y, Dai Z, Wang C. The strength of random search on automated program repair. In: Proceedings of the 36th International Conference on Software Engineering. 2014, 254–265

[13] Le X B D, Lo D, Le Goues C. History driven program repair. In: Proceedings of the 23rd IEEE International Conference on Software Analysis, Evolution, and Reengineering. 2016, 213–224

[14] Kim D, Nam J, Song J, Kim S. Automatic patch generation learned from human-written patches. In: Proceedings of the 2013 International Conference on Software Engineering. 2013, 802–811

[15] Martinez M, Durieux T, Sommerard R, Xuan J, Monperrus M. Automatic repair of real bugs in java: a large-scale experiment on the defects4j dataset. Empirical Software Engineering, 2017, 22(4): 1936–1964

[16] Chen L, Pei Y, Furia C A. Contract-based program repair without the contracts. In: Proceedings of the 32nd IEEE/ACM International Conference on Automated Software Engineering. 2017, 637–647

[17] Xiong Y, Wang J, Yan R, Zhang J, Han S, Huang G, Zhang L. Precise condition synthesis for program repair. In: Proceedings of the 39th IEEE/ACM International Conference on Software Engineering. 2017, 416–426

[18] Martinez M, Monperrus M. Astor: a program repair library for java. In: Proceedings of the 25th International Symposium on Software Testing and Analysis. 2016, 441–444

[19] Yang D, Qi Y, Mao X. Evaluating the strategies of statement selection in automated program repair. In: Proceedings of the International Conference on Software Analysis, Testing, and Evolution. 2018, 33–48

[20] Monperrus M. Automatic software repair: a bibliography. ACM Computing Surveys (CSUR), 2018, 51(1): 17

[21] Jia Y, Mao K, Harman M. Finding and Fixing Software Bugs Automatically with SapFix and Sapienz. 2018

[22] Wen M, Chen J, Wu R, Hao D, Cheung S C. Context-aware patch generation for better automated program repair. In: Proceedings of the 40th International Conference on Software Engineering. 2018, 1–11

[23] Qi Z, Long F, Achour S, Rinard M. An analysis of patch plausibility and correctness for generate-and-validate patch generation systems. In: Proceedings of the 2015 International Symposium on Software Testing and Analysis. 2015, 24–36

[24] Smith E K, Barr E T, Le Goues C, Brun Y. Is the cure worse than the disease? overfitting in automated program repair. In: Proceedings of the 10th Joint Meeting on Foundations of Software Engineering. 2015, 532–543

[25] Keller F, Grunske L, Heiden S, Filieri A, van Hoorn A, Lo D. A critical evaluation of spectrum-based fault localization techniques on a largescale software system. In: Proceedings of IEEE International Conference on Software Quality, Reliability and Security. 2017, 114–125

[26] Xie X, Chen T Y, Kuo F C, Xu B. A theoretical analysis of the risk evaluation formulas for spectrum-based fault localization. ACM Transactions on Software Engineering and Methodology, 2013, 22(4): 31

[27] Saha R K, Lyu Y, Yoshida H, Prasad M R. ELIXIR: effective object oriented program repair. In: Proceedings of the 32nd IEEE/ACM International Conference on Automated Software Engineering. 2017, 648–659

[28] Mechtaev S, Yi J, Roychoudhury A. Angelix: scalable multiline program patch synthesis via symbolic analysis. In: Proceedings of the 38th International Conference on Software Engineering. 2016, 691–701

[29] Xin Q, Reiss S P. Leveraging syntax-related code for automated program repair. In: Proceedings of the 32nd IEEE/ACM International Conference on Automated Software Engineering. 2017, 660–670

[30] Durieux T, Danglot B, Yu Z, Martinez M, Urli S, Monperrus M. The patches of the Nopol automatic repair system on the bugs of Defects4J version 1.1. 0. Research Report, 2017

[31] Hua J, Zhang M, Wang K, Khurshid S. Sketchfix: a tool for automated program repair approach using lazy candidate generation. In: Proceedings of the 26th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering. 2018, 888–891

[32] Xiong Y, Liu X, Zeng M, Zhang L, Huang G. Identifying patch correctness in test-based program repair. In: Proceedings of the 40th International Conference on Software Engineering. 2018, 789–799

[33] Debroy V, Wong W E. Using mutation to automatically suggest fixes for faulty programs. In: Proceedings of the 3rd International Conference on Software Testing, Verification and Validation. 2010, 65–74

[34] Just R, Parnin C, Drosos I, Ernst M D. Comparing developer-provided to user-provided tests for fault localization and automated program repair. In: Proceedings of the 27th ACM SIGSOFT International Symposium on Software Testing and Analysis. 2018, 287–297

[35] Just R, Jalali D, Ernst M D. Defects4J: a database of existing faults to enable controlled testing studies for Java programs. In: Proceedings of the 2014 International Symposium on Software Testing and Analysis. 2014, 437–440

[36] Durieux T, Madeiral F, Martinez M, Abreu R. Empirical review of java program repair tools: a large-scale experiment on 2,141 bugs and 23,551 repair attempts. 2019, arXiv preprint arXiv:1905.11973

[37] Moon S, Kim Y, Kim M, Yoo S. Ask the mutants: mutating faulty programs for fault localization. In: Proceedings of the IEEE International Conference on Software Testing, Verification and Validation. 2014, 153–162

[38] Tao Y, Kim J, Kim S, Xu C. Automatically generated patches as debugging aids: a human study. In: Proceedings of the 22nd ACM SIGSOFT International Symposium on Foundations of Software Engineering. 2014, 64–74

[39] Arcuri A, Briand L. A practical guide for using statistical tests to assess randomized algorithms in software engineering. In: Proceedings of the 33rd International Conference on Software Engineering. 2011, 1–10

[40] Le X B D, Bao L, Lo D, Xia X, Li S, Pasareanu C. On reliability of patch correctness assessment. In: Proceedings of the 41st International Conference on Software Engineering. 2019, 524–535

[41] Kong X, Zhang L, Wong W E, Li B. The impacts of techniques, programs and tests on automated program repair: an empirical study. Journal of Systems and Software, 2018, 137: 480–496

[42] Zou D, Liang J, Xiong Y, Ernst M D, Zhang L. An empirical study of fault localization families and their combinations. IEEE Transactions on Software Engineering, 2019

[43] Yi J, Ahmed U Z, Karkare A, Tan S H, Roychoudhury A. A feasibility study of using automated program repair for introductory programming assignments. In: Proceedings of the 11th Joint Meeting on Foundations of Software Engineering. 2017, 740–751

[44] Assiri F Y, Bieman J M. Fault localization for automated program repair: effectiveness, performance, repair correctness. Software Quality Journal, 2017, 25(1): 171–199

[45] Choi K, Sohn J, Yoo S. Learning fault localisation for both humans and machines using multi-objective GP. In: Proceedings of International Symposium on Search Based Software Engineering. 2018, 349–355

[46] Abreu R, Zoeteweij P, Van Gemund A J. On the accuracy of spectrumbased fault localization. In: Proceedings of the Testing: Academic and Industrial Conference Practice and Research Techniques-MUTATION. 2007, 89–98

[47] Harman M. The current state and future of search based software engineering. In: Proceedings of Future of Software Engineering. 2007, 342–357

[48] Wong W E, Debroy V, Gao R, Li Y. The DStar method for effective software fault localization. IEEE Transactions on Reliability, 2013, 63(1): 290–308

RIGHTS & PERMISSIONS

2020 Higher Education Press