research-article

Harnessing evolution for multi-hunk program repair

Authors:

Mukul R. PrasadAuthors Info & Claims

ICSE '19: Proceedings of the 41st International Conference on Software Engineering

Pages 13 - 24

https://doi.org/10.1109/ICSE.2019.00020

Published: 25 May 2019 Publication History

Abstract

Despite significant advances in automatic program repair (APR) techniques over the past decade, practical deployment remains an elusive goal. One of the important challenges in this regard is the general inability of current APR techniques to produce patches that require edits in multiple locations, i.e., multi-hunk patches. In this work, we present a novel APR technique that generalizes single-hunk repair techniques to include an important class of multi-hunk bugs, namely bugs that may require applying a substantially similar patch at a number of locations. We term such sets of repair locations as evolutionary siblings - similar looking code, instantiated in similar contexts, that are expected to undergo similar changes. At the heart of our proposed method is an analysis to accurately identify a set of evolutionary siblings, for a given bug. This analysis leverages three distinct sources of information, namely the test-suite spectrum, a novel code similarity analysis, and the revision history of the project. The discovered siblings are then simultaneously repaired in a similar fashion. We instantiate this technique in a tool called Hercules and demonstrate that it is able to correctly fix 46 bugs in the Defects4J dataset, the highest of any individual APR technique to date. This includes 15 multi-hunk bugs and overall 11 bugs which have not been fixed by any other technique so far.

References

[1]

L. Gazzola, D. Micucci, and L. Mariani, "Automatic software repair: A survey," IEEE Transactions on Software Engineering, pp. 1--1, 2018.

Digital Library

[2]

M. Monperrus, "Automatic software repair: A bibliography," ACM Computing Surveys, vol. 51, no. 1, pp. 17:1--17:24, Jan. 2018.

Digital Library

[3]

C. Le Goues, S. Forrest, and W. Weimer, "Current challenges in automatic software repair," Software quality journal, vol. 21, no. 3, pp. 421--443, 2013.

Digital Library

[4]

H. Zhong and Z. Su, "An empirical study on real bug fixes," in Proceedings of the 37th International Conference on Software Engineering-Volume 1. IEEE Press, 2015, pp. 913--923.

Digital Library

[5]

S. Mechtaev, J. Yi, and A. Roychoudhury, "Angelix: Scalable Multiline Program Patch Synthesis via Symbolic Analysis," in Proceedings of the 38th International Conference on Software Engineering, ser. ICSE '16. New York, NY, USA: ACM, 2016, pp. 691--701.

Digital Library

[6]

R. Just, D. Jalali, and 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. ACM, 2014, pp. 437--440.

Digital Library

[7]

R. K. Saha, Y. Lyu, W. Lam, H. Yoshida, and M. R. Prasad, "Bugs. jar: a large-scale, diverse dataset of real-world java bugs," in Proceedings of the 15th International Conference on Mining Software Repositories. ACM, 2018, pp. 10--13.

Digital Library

[8]

M. Kim and D. Notkin, "Using a clone genealogy extractor for understanding and supporting evolution of code clones," in ACM SIGSOFT Software Engineering Notes, vol. 30, no. 4. ACM, 2005, pp. 1--5.

Digital Library

[9]

C. K. Roy and J. R. Cordy, "An empirical study of function clones in open source software," in 2008 15th Working Conference on Reverse Engineering. IEEE, 2008, pp. 81--90.

Digital Library

[10]

E. Duala-Ekoko and M. P. Robillard, "Tracking code clones in evolving software," in Software Engineering, 2007. ICSE 2007. 29th International Conference on. IEEE, 2007, pp. 158--167.

Digital Library

[11]

E. Juergens, F. Deissenboeck, B. Hummel, and S. Wagner, "Do code clones matter?" in Software Engineering, 2009. ICSE 2009. IEEE 31st International Conference on. IEEE, 2009, pp. 485--495.

Digital Library

[12]

T. Kamiya, S. Kusumoto, and K. Inoue, "Ccfinder: A multilinguistic token-based code clone detection system for large scale source code," IEEE Trans. Softw. Eng., vol. 28, no. 7, pp. 654--670, Jul. 2002.

Digital Library

[13]

L. Jiang, G. Misherghi, Z. Su, and S. Glondu, "Deckard: Scalable and accurate tree-based detection of code clones," in Proceedings of the 29th international conference on Software Engineering. IEEE Computer Society, 2007, pp. 96--105.

Digital Library

[14]

J. R. Cordy and C. K. Roy, "The nicad clone detector," in Proceedings of the 2011 IEEE 19th International Conference on Program Comprehension, ser. ICPC '11. Washington, DC, USA: IEEE Computer Society, 2011, pp. 219--220.

Digital Library

[15]

N. Meng, M. Kim, and K. S. McKinley, "Systematic editing: Generating program transformations from an example," in Proceedings of the 32Nd ACM SIGPLAN Conference on Programming Language Design and Implementation, ser. PLDI '11. New York, NY, USA: ACM, 2011, pp. 329--342.

Digital Library

[16]

N. Meng, M. Kim, and K. S. McKinley, "Lase: Locating and applying systematic edits by learning from examples," in Proceedings of the 2013 International Conference on Software Engineering, ser. ICSE '13. Piscataway, NJ, USA: IEEE Press, 2013, pp. 502--511.

Digital Library

[17]

N. Meng, L. Hua, M. Kim, and K. S. McKinley, "Does automated refactoring obviate systematic editing?" in Proceedings of the 37th International Conference on Software Engineering - Volume 1, ser. ICSE '15. Piscataway, NJ, USA: IEEE Press, 2015, pp. 392--402.

Digital Library

[18]

C. K. Roy and J. R. Cordy, "A survey on software clone detection research," Queen?s School of Computing TR, vol. 541, no. 115, pp. 64--68, 2007.

[19]

M. Rieger, S. Ducasse, and M. Lanza, "Insights into system-wide code duplication," in Reverse Engineering, 2004. Proceedings. 11th Working Conference on. IEEE, 2004, pp. 100--109.

Digital Library

[20]

J. F. Islam, M. Mondal, and C. K. Roy, "Bug replication in code clones: An empirical study," in Software Analysis, Evolution, and Reengineering (SANER), 2016 IEEE 23rd International Conference on, vol. 1. IEEE, 2016, pp. 68--78.

[21]

E. T. Barr, Y. Brun, P. Devanbu, M. Harman, and F. Sarro, "The plastic surgery hypothesis," in Proceedings of the 22nd ACM SIGSOFT International Symposium on Foundations of Software Engineering. ACM, 2014, pp. 306--317.

Digital Library

[22]

D. Kim, J. Nam, J. Song, and S. Kim, "Automatic patch generation learned from human-written patches," in Proceedings of the 2013 International Conference on Software Engineering, ser. ICSE '13. Piscataway, NJ, USA: IEEE Press, 2013, pp. 802--811.

Digital Library

[23]

S. H. Tan and A. Roychoudhury, "Relifix: Automated repair of software regressions," in Proceedings of the 37th International Conference on Software Engineering - Volume 1, ser. ICSE '15. Piscataway, NJ, USA: IEEE Press, 2015, pp. 471--482.

Digital Library

[24]

S. H. Tan, H. Yoshida, M. R. Prasad, and A. Roychoudhury, "Anti-patterns in search-based program repair," in Proceedings of the 2016 24th ACM SIGSOFT International Symposium on Foundations of Software Engineering, ser. FSE 2016. New York, NY, USA: ACM, 2016, pp. 727--738.

Digital Library

[25]

F. Long, P. Amidon, and M. Rinard, "Automatic inference of code transforms for patch generation," in Proceedings of the 2017 11th Joint Meeting on Foundations of Software Engineering, ser. ESEC/FSE 2017. New York, NY, USA: ACM, 2017, pp. 727--739.

Digital Library

[26]

M. Wen, J. Chen, R. Wu, D. Hao, and S.-C. Cheung, "Context-aware patch generation for better automated program repair," in Proceedings of the 40th International Conference on Software Engineering, ser. ICSE '18. New York, NY, USA: ACM, 2018, pp. 1--11.

Digital Library

[27]

J. Jiang, Y. Xiong, H. Zhang, Q. Gao, and 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, ser. ISSTA 2018. New York, NY, USA: ACM, 2018, pp. 298--309.

Digital Library

[28]

C. Le Goues, M. Dewey-Vogt, S. Forrest, and W. Weimer, "A systematic study of automated program repair: Fixing 55 out of 105 bugs for $8 each," in Proceedings of the 34th International Conference on Software Engineering, ser. ICSE '12. Piscataway, NJ, USA: IEEE Press, 2012, pp. 3--13.

Digital Library

[29]

Y. Xiong, J. Wang, R. Yan, J. Zhang, S. Han, G. Huang, and L. Zhang, "Precise condition synthesis for program repair," in Proceedings of the 39th International Conference on Software Engineering, ser. ICSE '17. Piscataway, NJ, USA: IEEE Press, 2017, pp. 416--426.

Digital Library

[30]

Q. Xin and S. P. Reiss, "Leveraging syntax-related code for automated program repair," in Proceedings of the 32Nd IEEE/ACM International Conference on Automated Software Engineering, ser. ASE 2017. Piscataway, NJ, USA: IEEE Press, 2017, pp. 660--670.

Digital Library

[31]

Z. Qi, F. Long, S. Achour, and 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, ser. ISSTA 2015. New York, NY, USA: ACM, 2015, pp. 24--36.

Digital Library

[32]

F. Long and M. Rinard, "Staged program repair with condition synthesis," in Proceedings of the 2015 10th Joint Meeting on Foundations of Software Engineering, ser. ESEC/FSE 2015. New York, NY, USA: ACM, 2015, pp. 166--178.

Digital Library

[33]

T. Durieux, M. Martinez, M. Monperrus, R. Sommerard, and J. Xuan, "Automatic repair of real bugs: An experience report on the defects4j dataset," CoRR, vol. abs/1505.07002, 2015. {Online}. Available: http://arxiv.org/abs/1505.07002

[34]

F. Long and M. Rinard, "Automatic patch generation by learning correct code," in Proceedings of the 43rd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, ser. POPL '16. New York, NY, USA: ACM, 2016, pp. 298--312.

Digital Library

[35]

J. A. Jones, M. J. Harrold, and J. Stasko, "Visualization of test information to assist fault localization," in Proceedings of the 24th International Conference on Software Engineering, ser. ICSE '02. New York, NY, USA: ACM, 2002, pp. 467--477.

Digital Library

[36]

T. Janssen, R. Abreu, and A. J. van Gemund, "Zoltar: a spectrum-based fault localization tool," in SINTER '09: Proceedings of the 2009 ESEC/FSE workshop on Software integration and evolution @ runtime. New York, NY, USA: ACM, 2009, pp. 23--30.

Digital Library

[37]

R. Abreu, P. Zoeteweij, R. Golsteijn, and A. J. C. van Gemund, "A practical evaluation of spectrum-based fault localization," Journal of Systems and Software, vol. 82, no. 11, pp. 1780--1792, Nov. 2009.

Digital Library

[38]

Y. Qi, X. Mao, Y. Lei, Z. Dai, and C. Wang, "The strength of random search on automated program repair," in Proceedings of the 36th International Conference on Software Engineering, ser. ICSE 2014. New York, NY, USA: ACM, 2014, pp. 254--265.

Digital Library

[39]

W. Weimer, Z. P. Fry, and S. Forrest, "Leveraging program equivalence for adaptive program repair: Models and first results," in Automated Software Engineering (ASE), 2013 IEEE/ACM 28th International Conference on. Piscataway, NJ, USA: IEEE Press, Nov 2013, pp. 356--366.

Digital Library

[40]

R. K. Saha, Y. Lyu, H. Yoshida, and M. R. Prasad, "Elixir: Effective object oriented program repair," in Proceedings of the 32Nd IEEE/ACM International Conference on Automated Software Engineering, ser. ASE 2017. Piscataway, NJ, USA: IEEE Press, 2017, pp. 648--659.

Digital Library

[41]

K. Zhang and D. Shasha, "Simple fast algorithms for the editing distance between trees and related problems," SIAM journal on computing, vol. 18, no. 6, pp. 1245--1262, 1989.

Digital Library

[42]

L. Chen, Y. Pei, and C. A. Furia, "Contract-based program repair without the contracts," in Automated Software Engineering (ASE), 2017 32nd IEEE/ACM International Conference on. IEEE, 2017, pp. 637--647.

Digital Library

[43]

E. T. Barr, M. Harman, Y. Jia, A. Marginean, and J. Petke, "Automated software transplantation," in Proceedings of the 2015 International Symposium on Software Testing and Analysis, ser. ISSTA 2015. New York, NY, USA: ACM, 2015, pp. 257--269.

Digital Library

[44]

S. Sidiroglou-Douskos, E. Lahtinen, F. Long, and M. Rinard, "Automatic error elimination by horizontal code transfer across multiple applications," in Proceedings of the 36th ACM SIGPLAN Conference on Programming Language Design and Implementation, ser. PLDI '15. New York, NY, USA: ACM, 2015, pp. 43--54.

Digital Library

[45]

Y. Ke, K. T. Stolee, C. Le Goues, and Y. Brun, "Repairing programs with semantic code search," in 2015 30th IEEE/ACM International Conference on Automated Software Engineering (ASE), Nov 2015, pp. 295--306.

Digital Library

[46]

X. B. D. Le, D. Lo, and C. Le Goues, "History Driven Program Repair," in 2016 IEEE 23rd International Conference on Software Analysis, Evolution, and Reengineering (SANER), vol. 1. Piscataway, NJ, USA: IEEE Press, March 2016, pp. 213--224.

[47]

M. Kim and D. Notkin, "Discovering and representing systematic code changes," in Proceedings of the 31st International Conference on Software Engineering, ser. ICSE '09. Washington, DC, USA: IEEE Computer Society, 2009, pp. 309--319.

Digital Library

Cited By

Huang KXu ZYang SSun HLi XYan ZZhang Y(2024)Evolving Paradigms in Automated Program Repair: Taxonomy, Challenges, and OpportunitiesACM Computing Surveys10.1145/369645057:2(1-43)Online publication date: 10-Oct-2024
https://dl.acm.org/doi/10.1145/3696450
Kim YPark YHan SYi JFilkov VRay BZhou M(2024)Enhancing the Efficiency of Automated Program Repair via Greybox AnalysisProceedings of the 39th IEEE/ACM International Conference on Automated Software Engineering10.1145/3691620.3695602(1719-1731)Online publication date: 27-Oct-2024
https://dl.acm.org/doi/10.1145/3691620.3695602
Zhong WLi CLiu KGe JLuo BBissyandé TNg V(2024)Benchmarking and Categorizing the Performance of Neural Program Repair Systems for JavaACM Transactions on Software Engineering and Methodology10.1145/368883434:1(1-35)Online publication date: 19-Aug-2024
https://dl.acm.org/doi/10.1145/3688834
Show More Cited By

Recommendations

Towards API-specific automatic program repair
ASE '17: Proceedings of the 32nd IEEE/ACM International Conference on Automated Software Engineering

The domain of Automatic Program Repair (APR) had many research contributions in recent years. So far, most approaches target fixing generic bugs in programs (e.g., off-by-one errors). Nevertheless, recent studies reveal that about 50% of real bugs ...
ELIXIR: effective object oriented program repair
ASE '17: Proceedings of the 32nd IEEE/ACM International Conference on Automated Software Engineering

This work is motivated by the pervasive use of method invocations in object-oriented (OO) programs, and indeed their prevalence in patches of OO-program bugs. We propose a generate-and-validate repair technique, called ELIXIR designed to be able to ...
CRSearcher: Searching Code Database for Repairing Bugs
Internetware '17: Proceedings of the 9th Asia-Pacific Symposium on Internetware

With the exponentially rising of software development in the past decades, millions of software products have been created. Existing empirical studies show that many code snippets are similar. Although there exist many difficulties in maintaining these ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ICSE '19: Proceedings of the 41st International Conference on Software Engineering

May 2019

1318 pages

General Chair:
Joanne M. Atlee
University of Waterloo, Canada
,
Program Chairs:
Tevfik Bultan
University of California, Santa Barbara
,
Jon Whittle
Monash University, Australia

Sponsors

SIGSOFT: ACM Special Interest Group on Software Engineering
IEEE-CS: Computer Society

Publisher

IEEE Press

Publication History

Published: 25 May 2019

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ICSE '19

Sponsor:

SIGSOFT
IEEE-CS

ICSE '19: 41st International Conference on Software Engineering

May 25 - 31, 2019

Quebec, Montreal, Canada

Acceptance Rates

Overall Acceptance Rate 276 of 1,856 submissions, 15%

Upcoming Conference

ICSE 2025

2025 IEEE/ACM 46th International Conference on Software Engineering

April 26 - May 3, 2025

Ottawa , ON , Canada

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

37
Total Citations
View Citations
450
Total Downloads

Downloads (Last 12 months)31
Downloads (Last 6 weeks)6

Reflects downloads up to 17 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Huang KXu ZYang SSun HLi XYan ZZhang Y(2024)Evolving Paradigms in Automated Program Repair: Taxonomy, Challenges, and OpportunitiesACM Computing Surveys10.1145/369645057:2(1-43)Online publication date: 10-Oct-2024
https://dl.acm.org/doi/10.1145/3696450
Kim YPark YHan SYi JFilkov VRay BZhou M(2024)Enhancing the Efficiency of Automated Program Repair via Greybox AnalysisProceedings of the 39th IEEE/ACM International Conference on Automated Software Engineering10.1145/3691620.3695602(1719-1731)Online publication date: 27-Oct-2024
https://dl.acm.org/doi/10.1145/3691620.3695602
Zhong WLi CLiu KGe JLuo BBissyandé TNg V(2024)Benchmarking and Categorizing the Performance of Neural Program Repair Systems for JavaACM Transactions on Software Engineering and Methodology10.1145/368883434:1(1-35)Online publication date: 19-Aug-2024
https://dl.acm.org/doi/10.1145/3688834
Lou YYang JBenton SHao DTan LChen ZZhang LZhang L(2024)When Automated Program Repair Meets Regression Testing—An Extensive Study on Two Million PatchesACM Transactions on Software Engineering and Methodology10.1145/367245033:7(1-23)Online publication date: 13-Jun-2024
https://dl.acm.org/doi/10.1145/3672450
Ságodi ZAntal GBogenfürst BIsztin MHegedűs PFerenc R(2024)Reality Check: Assessing GPT-4 in Fixing Real-World Software VulnerabilitiesProceedings of the 28th International Conference on Evaluation and Assessment in Software Engineering10.1145/3661167.3661207(252-261)Online publication date: 18-Jun-2024
https://dl.acm.org/doi/10.1145/3661167.3661207
Xin QWu HTang JLiu XReiss SXuan J(2024)Detecting, Creating, Repairing, and Understanding Indivisible Multi-Hunk BugsProceedings of the ACM on Software Engineering10.1145/36608281:FSE(2747-2770)Online publication date: 12-Jul-2024
https://dl.acm.org/doi/10.1145/3660828
Ye HMonperrus MRoychoudhury APaiva AAbreu RStorey M(2024)ITER: Iterative Neural Repair for Multi-Location PatchesProceedings of the IEEE/ACM 46th International Conference on Software Engineering10.1145/3597503.3623337(1-13)Online publication date: 20-May-2024
https://dl.acm.org/doi/10.1145/3597503.3623337
Xie HLei YYan MLi SMao XYu YLo D(2024)Towards More Precise Coincidental Correctness Detection With Deep Semantic LearningIEEE Transactions on Software Engineering10.1109/TSE.2024.348189350:12(3265-3289)Online publication date: 1-Dec-2024
https://dl.acm.org/doi/10.1109/TSE.2024.3481893
Gharibi RSadreddini MFakhrahmad S(2024)T5APRJournal of Systems and Software10.1016/j.jss.2024.112083214:COnline publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1016/j.jss.2024.112083
Sharma TKechagia MGeorgiou STiwari RVats IMoazen HSarro F(2024)A survey on machine learning techniques applied to source codeJournal of Systems and Software10.1016/j.jss.2023.111934209:COnline publication date: 14-Mar-2024
https://dl.acm.org/doi/10.1016/j.jss.2023.111934
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten