|
|
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 |
|
|
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
|
|
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
|
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
|
Shared |
|
|
|
|
|
Discussed |
|
|
|
|