Please wait a minute...
Frontiers of Computer Science

ISSN 2095-2228

ISSN 2095-2236(Online)

CN 10-1014/TP

Postal Subscription Code 80-970

2018 Impact Factor: 1.129

Front. Comput. Sci.    2021, Vol. 15 Issue (1) : 151202    https://doi.org/10.1007/s11704-020-9263-1
RESEARCH ARTICLE
Evaluating the usage of fault localization in automated program repair: an empirical study
Deheng YANG1,2, Yuhua QI3(), Xiaoguang MAO1,2, Yan LEI4()
1. College of Computer, National University of Defense Technology, Changsha 410073, China
2. Laboratory of Software Engineering for Complex Systems, Changsha 410073, China
3. Beijing Institute of Tracking and Communication Technology, Beijing 100094, China
4. School of Big Data & Software Engineering, Chongqing University, Chongqing 400044, China
 Download: PDF(985 KB)  
 Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks
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     
Corresponding Author(s): Yuhua QI,Yan LEI   
Just Accepted Date: 04 March 2020   Issue Date: 24 September 2020
 Cite this article:   
Deheng YANG,Yuhua QI,Xiaoguang MAO, et al. Evaluating the usage of fault localization in automated program repair: an empirical study[J]. Front. Comput. Sci., 2021, 15(1): 151202.
 URL:  
https://academic.hep.com.cn/fcs/EN/10.1007/s11704-020-9263-1
https://academic.hep.com.cn/fcs/EN/Y2021/V15/I1/151202
1 S Pearson, J Campos, R Just, G Fraser, R Abreu, M D Ernst, D Pang, B Keller. Evaluating and improving fault localization. In: Proceedings of the 39th International Conference on Software Engineering. 2017, 609–620
https://doi.org/10.1109/ICSE.2017.62
2 W E Wong, R Gao, Y Li, R Abreu, F Wotawa. A survey on software fault localization. IEEE Transactions on Software Engineering, 2016, 42(8): 707–740
https://doi.org/10.1109/TSE.2016.2521368
3 C Parnin, A Orso. Are automated debugging techniques actually helping programmers? In: Proceedings of the 2011 International Symposium on Software Testing and Analysis. 2011, 199–209
https://doi.org/10.1145/2001420.2001445
4 P S Kochhar, X Xia, D Lo, S Li. Practitioner’s expectations on automated fault localization. In: Proceedings of the 25th International Symposium on Software Testing and Analysis. 2016, 165–176
https://doi.org/10.1145/2931037.2931051
5 L Gazzola, D Micucci, L Mariani. Automatic software repair: a survey. IEEE Transactions on Software Engineering, 2017, 45(1): 34–67
https://doi.org/10.1109/TSE.2017.2755013
6 J Jiang, Y Xiong, H Zhang, Q Gao, X Chen. 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
https://doi.org/10.1145/3213846.3213871
7 C Le Goues, T Nguyen, S Forrest, W Weimer. Genprog: a generic method for automatic software repair. IEEE Transactions on Software Engineering, 2011, 38(1): 54–72
https://doi.org/10.1109/TSE.2011.104
8 S Mechtaev, M D Nguyen, Y Noller, L Grunske, A Roychoudhury. Semantic program repair using a reference implementation. In: Proceedings of the 40th International Conference on Software Engineering. 2018, 129–139
https://doi.org/10.1145/3180155.3180247
9 H D T Nguyen, D Qi, A Roychoudhury, S Chandra. Semfix: program repair via semantic analysis. In: Proceedings of the 35th International Conference on Software Engineering. 2013, 772–781
https://doi.org/10.1109/ICSE.2013.6606623
10 J Xuan, M Martinez, F Demarco, et al. Nopol: automatic repair of conditional statement bugs in java programs. IEEE Transactions on Software Engineering, 2016, 43(1): 34–55
https://doi.org/10.1109/TSE.2016.2560811
11 Y Qi, X Mao, Y Lei, C Wang. 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
https://doi.org/10.1145/2483760.2483785
12 Y Qi, X Mao, Y Lei, Z Dai, C Wang. The strength of random search on automated program repair. In: Proceedings of the 36th International Conference on Software Engineering. 2014, 254–265
https://doi.org/10.1145/2568225.2568254
13 X B D Le, D Lo, C Le Goues. History driven program repair. In: Proceedings of the 23rd IEEE International Conference on Software Analysis, Evolution, and Reengineering. 2016, 213–224
https://doi.org/10.1109/SANER.2016.76
14 D Kim, J Nam, J Song, S Kim. Automatic patch generation learned from human-written patches. In: Proceedings of the 2013 International Conference on Software Engineering. 2013, 802–811
https://doi.org/10.1109/ICSE.2013.6606626
15 M Martinez, T Durieux, R Sommerard, J Xuan, M Monperrus. Automatic repair of real bugs in java: a large-scale experiment on the defects4j dataset. Empirical Software Engineering, 2017, 22(4): 1936–1964
https://doi.org/10.1007/s10664-016-9470-4
16 L Chen, Y Pei, C A Furia. Contract-based program repair without the contracts. In: Proceedings of the 32nd IEEE/ACM International Conference on Automated Software Engineering. 2017, 637–647
https://doi.org/10.1109/ASE.2017.8115674
17 Y Xiong, J Wang, R Yan, J Zhang, S Han, G Huang, L Zhang. Precise condition synthesis for program repair. In: Proceedings of the 39th IEEE/ACM International Conference on Software Engineering. 2017, 416–426
https://doi.org/10.1109/ICSE.2017.45
18 M Martinez, M Monperrus. Astor: a program repair library for java. In: Proceedings of the 25th International Symposium on Software Testing and Analysis. 2016, 441–444
https://doi.org/10.1145/2931037.2948705
19 D Yang, Y Qi, X Mao. 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
https://doi.org/10.1007/978-3-030-04272-1_3
20 M Monperrus. Automatic software repair: a bibliography. ACM Computing Surveys (CSUR), 2018, 51(1): 17
https://doi.org/10.1145/3105906
21 Y Jia, K Mao, M Harman. Finding and Fixing Software Bugs Automatically with SapFix and Sapienz. 2018
22 M Wen, J Chen, R Wu, D Hao, S C Cheung. Context-aware patch generation for better automated program repair. In: Proceedings of the 40th International Conference on Software Engineering. 2018, 1–11
https://doi.org/10.1145/3180155.3180233
23 Z Qi, F Long, S Achour, M Rinard. 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
https://doi.org/10.1145/2771783.2771791
24 E K Smith, E T Barr, C Le Goues, Y Brun. 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
https://doi.org/10.1145/2786805.2786825
25 F Keller, L Grunske, S Heiden, A Filieri, A van Hoorn, D Lo. 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
https://doi.org/10.1109/QRS.2017.22
26 X Xie, T Y Chen, F C Kuo, B Xu. A theoretical analysis of the risk evaluation formulas for spectrum-based fault localization. ACM Transactions on Software Engineering and Methodology, 2013, 22(4): 31
https://doi.org/10.1145/2522920.2522924
27 R K Saha, Y Lyu, H Yoshida, M R Prasad. ELIXIR: effective object oriented program repair. In: Proceedings of the 32nd IEEE/ACM International Conference on Automated Software Engineering. 2017, 648–659
https://doi.org/10.1109/ASE.2017.8115675
28 S Mechtaev, J Yi, A Roychoudhury. Angelix: scalable multiline program patch synthesis via symbolic analysis. In: Proceedings of the 38th International Conference on Software Engineering. 2016, 691–701
https://doi.org/10.1145/2884781.2884807
29 Q Xin, S P Reiss. Leveraging syntax-related code for automated program repair. In: Proceedings of the 32nd IEEE/ACM International Conference on Automated Software Engineering. 2017, 660–670
https://doi.org/10.1109/ASE.2017.8115676
30 T Durieux, B Danglot, Z Yu, M Martinez, S Urli, M Monperrus. The patches of the Nopol automatic repair system on the bugs of Defects4J version 1.1. 0. Research Report, 2017
31 J Hua, M Zhang, K Wang, S Khurshid. 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
https://doi.org/10.1145/3236024.3264600
32 Y Xiong, X Liu, M Zeng, L Zhang, G Huang. Identifying patch correctness in test-based program repair. In: Proceedings of the 40th International Conference on Software Engineering. 2018, 789–799
https://doi.org/10.1145/3180155.3180182
33 V Debroy, W E Wong. 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
https://doi.org/10.1109/ICST.2010.66
34 R Just, C Parnin, I Drosos, M D Ernst. 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
https://doi.org/10.1145/3213846.3213870
35 R Just, D Jalali, M D Ernst. 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
https://doi.org/10.1145/2610384.2628055
36 T Durieux, F Madeiral, M Martinez, R Abreu. 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
https://doi.org/10.1145/3338906.3338911
37 S Moon, Y Kim, M Kim, S Yoo. 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
https://doi.org/10.1109/ICST.2014.28
38 Y Tao, J Kim, S Kim, C Xu. 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
https://doi.org/10.1145/2635868.2635873
39 A Arcuri, L Briand. 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
https://doi.org/10.1145/1985793.1985795
40 X B D Le, L Bao, D Lo, X Xia, S Li, C Pasareanu. On reliability of patch correctness assessment. In: Proceedings of the 41st International Conference on Software Engineering. 2019, 524–535
https://doi.org/10.1109/ICSE.2019.00064
41 X Kong, L Zhang, W E Wong, B Li. The impacts of techniques, programs and tests on automated program repair: an empirical study. Journal of Systems and Software, 2018, 137: 480–496
https://doi.org/10.1016/j.jss.2017.06.039
42 D Zou, J Liang, Y Xiong, M D Ernst, L Zhang. An empirical study of fault localization families and their combinations. IEEE Transactions on Software Engineering, 2019
https://doi.org/10.1109/TSE.2019.2892102
43 J Yi, U Z Ahmed, A Karkare, S H Tan, A Roychoudhury. 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
https://doi.org/10.1145/3106237.3106262
44 F Y Assiri, J M Bieman. Fault localization for automated program repair: effectiveness, performance, repair correctness. Software Quality Journal, 2017, 25(1): 171–199
https://doi.org/10.1007/s11219-016-9312-z
45 K Choi, J Sohn, S Yoo. 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
https://doi.org/10.1007/978-3-319-99241-9_20
46 R Abreu, P Zoeteweij, A J Van Gemund. On the accuracy of spectrumbased fault localization. In: Proceedings of the Testing: Academic and Industrial Conference Practice and Research Techniques-MUTATION. 2007, 89–98
https://doi.org/10.1109/TAIC.PART.2007.13
47 M Harman. The current state and future of search based software engineering. In: Proceedings of Future of Software Engineering. 2007, 342–357
https://doi.org/10.1109/FOSE.2007.29
48 W E Wong, V Debroy, R Gao, Y Li. The DStar method for effective software fault localization. IEEE Transactions on Reliability, 2013, 63(1): 290–308
https://doi.org/10.1109/TR.2013.2285319
[1] Article highlights Download
[1] Farid FEYZI, Saeed PARSA. Inforence: effective fault localization based on information-theoretic analysis and statistical causal inference[J]. Front. Comput. Sci., 2019, 13(4): 735-759.
[2] Xiaobing SUN, Hui YANG, Hareton LEUNG, Bin LI, Hanchao (Jerry) LI, Lingzhi LIAO. Effectiveness of exploring historical commits for developer recommendation: an empirical study[J]. Front. Comput. Sci., 2018, 12(3): 528-544.
[3] Xiaobing SUN,Xin PENG,Bin LI,Bixin LI,Wanzhi WEN. IPSETFUL: an iterative process of selecting test cases for effective fault localization by exploring concept lattice of program spectra[J]. Front. Comput. Sci., 2016, 10(5): 812-831.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed