research-article

Anti-patterns in search-based program repair

Authors:

Hiroaki Yoshida,

Mukul R. Prasad,

Abhik RoychoudhuryAuthors Info & Claims

FSE 2016: Proceedings of the 2016 24th ACM SIGSOFT International Symposium on Foundations of Software Engineering

Pages 727 - 738

https://doi.org/10.1145/2950290.2950295

Published: 01 November 2016 Publication History

Abstract

Search-based program repair automatically searches for a program fix within a given repair space. This may be accomplished by retrofitting a generic search algorithm for program repair as evidenced by the GenProg tool, or by building a customized search algorithm for program repair as in SPR. Unfortunately, automated program repair approaches may produce patches that may be rejected by programmers, because of which past works have suggested using human-written patches to produce templates to guide program repair. In this work, we take the position that we will not provide templates to guide the repair search because that may unduly restrict the repair space and attempt to overfit the repairs into one of the provided templates. Instead, we suggest the use of a set of anti-patterns --- a set of generic forbidden transformations that can be enforced on top of any search-based repair tool. We show that by enforcing our anti-patterns, we obtain repairs that localize the correct lines or functions, involve less deletion of program functionality, and are mostly obtained more efficiently. Since our set of anti-patterns are generic, we have integrated them into existing search based repair tools, including GenProg and SPR, thereby allowing us to obtain higher quality program patches with minimal effort.

References

[1]

M. Böhme and A. Roychoudhury. CoREBench: Studying complexity of regression errors. In Proceedings of the 2014 International Symposium on Software Testing and Analysis, ISSTA 2014, pages 105–115, New York, NY, USA, 2014. ACM.

Digital Library

[2]

W. H. Brown, R. C. Malveau, and T. J. Mowbray. AntiPatterns: refactoring software, architectures, and projects in crisis. Wiley, 1998.

Digital Library

[3]

F. DeMarco, J. Xuan, D. Le Berre, and M. Monperrus. Automatic repair of buggy if conditions and missing preconditions with SMT. In Proceedings of the 6th International Workshop on Constraints in Software Testing, Verification, and Analysis, CSTVA 2014, pages 30–39, New York, NY, USA, 2014. ACM.

Digital Library

[4]

B. Demsky, M. D. Ernst, P. J. Guo, S. McCamant, J. H. Perkins, and M. Rinard. Inference and enforcement of data structure consistency specifications. In Proceedings of the 2006 International Symposium on Software Testing and Analysis, ISSTA ’06, pages 233–244, New York, NY, USA, 2006. ACM.

Digital Library

[5]

D. Gopinath, M. Z. Malik, and S. Khurshid. Specification-based program repair using sat. In Tools and Algorithms for the Construction and Analysis of Systems, pages 173–188. Springer, 2011.

Digital Library

[6]

S. Kaleeswaran, V. Tulsian, A. Kanade, and A. Orso. Minthint: Automated synthesis of repair hints. In Proceedings of the 36th International Conference on Software Engineering, ICSE 2014, pages 266–276, New York, NY, USA, 2014. ACM.

Digital Library

[7]

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, ICSE ’13, pages 802–811, Piscataway, NJ, USA, 2013. IEEE Press.

Digital Library

[8]

A. Koenig. Patterns and antipatterns. Journal of Object Oriented Programming, 8(1), 1995.

[9]

J. R. Koza. Genetic Programming: On the Programming of computers by Means of Natural Selection. MIT Press, 1992.

Digital Library

[10]

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 Software Engineering (ICSE), 2012 34th International Conference on, pages 3–13. IEEE, 2012.

Digital Library

[11]

F. Long and M. Rinard. Staged program repair with condition synthesis. In Proceedings of the 2015 10th Joint Meeting on Foundations of Software Engineering, ESEC/FSE 2015, pages 166–178, New York, NY, USA, 2015. ACM.

Digital Library

[12]

F. Long and M. Rinard. An analysis of the search spaces for generate and validate patch generation systems. In Proceedings of the 38th International Conference on Software Engineering, ICSE ’16, pages 702–713, New York, NY, USA, 2016. ACM.

Digital Library

[13]

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, POPL ’16, pages 298–312, New York, NY, USA, 2016. ACM.

Digital Library

[14]

S. Mechtaev, J. Yi, and A. Roychoudhury. DirectFix: Looking for simple program repairs. In Proceedings of the 37th International Conference on Software Engineering, ICSE 2015, pages 448–458. ACM, 2015.

Digital Library

[15]

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, ICSE ’16, pages 691–701, New York, NY, USA, 2016. ACM.

Digital Library

[16]

M. Monperrus. A critical review of ”automatic patch generation learned from human-written patches”: Essay on the problem statement and the evaluation of automatic software repair. In Proceedings of the 36th International Conference on Software Engineering, ICSE 2014, 2014.

Digital Library

[17]

H. D. T. Nguyen, D. Qi, A. Roychoudhury, and S. Chandra. Semfix: Program repair via semantic analysis. In Proceedings of the 2013 International Conference on Software Engineering, pages 772–781. IEEE Press, 2013.

Digital Library

[18]

F. S. Ocariza, Jr., K. Pattabiraman, and A. Mesbah. Vejovis: Suggesting fixes for javascript faults. In Proceedings of the 36th International Conference on Software Engineering, ICSE 2014, pages 837–847, New York, NY, USA, 2014. ACM.

Digital Library

[19]

Y. Pei, C. Furia, M. Nordio, Y. Wei, B. Meyer, and A. Zeller. Automated fixing of programs with contracts. Software Engineering, IEEE Transactions on, 40(5):427–449, May 2014.

Digital Library

[20]

J. H. Perkins, S. Kim, S. Larsen, S. Amarasinghe, J. Bachrach, M. Carbin, C. Pacheco, F. Sherwood, S. Sidiroglou, G. Sullivan, W.-F. Wong, Y. Zibin, M. D. Ernst, and M. Rinard. Automatically patching errors in deployed software. In Proceedings of the ACM SIGOPS 22Nd Symposium on Operating Systems Principles, SOSP ’09, pages 87–102, New York, NY, USA, 2009. ACM.

Digital Library

[21]

R. Purushothaman and D. E. Perry. Towards understanding the rhetoric of small changes-extended abstract. In International Workshop on Mining Software Repositories (MSR 2004), International Conference on Software Engineering, pages 90–94, 2004.

[22]

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, ICSE 2014, New York, NY, USA, 2014.

Digital Library

[23]

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, ISSTA 2015, pages 24–36, New York, NY, USA, 2015. ACM.

Digital Library

[24]

R. Samanta, O. Olivo, and E. Emerson. Cost-aware automatic program repair. In M. Müller-Olm and H. Seidl, editors, Static Analysis Symposium, volume 8723 of Lecture Notes in Computer Science, pages 268–284. Springer International Publishing, 2014.

[25]

J. Śliwerski, T. Zimmermann, and A. Zeller. When do changes induce fixes? In Proceedings of the 2005 International Workshop on Mining Software Repositories, MSR ’05, pages 1–5, New York, NY, USA, 2005. ACM.

Digital Library

[26]

E. K. Smith, E. T. Barr, C. Le Goues, and Y. Brun. Is the cure worse than the disease? overfitting in automated program repair. In Proceedings of the 10th Joint Meeting of the European Software Engineering Conference and ACM SIGSOFT Symposium on the Foundations of Software Engineering (ESEC/FSE), Bergamo, Italy, 2015.

Digital Library

[27]

S. H. Tan and A. Roychoudhury. Relifix: Automated repair of software regressions. In Proceedings of the 37th International Conference on Software Engineering, ICSE 2015, pages 471–482. ACM, 2015.

Digital Library

[28]

W. Weimer, Z. 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, Nov 2013.

Digital Library

[29]

Z. Yin, D. Yuan, Y. Zhou, S. Pasupathy, and L. Bairavasundaram. How do fixes become bugs? In Proceedings of the 19th ACM SIGSOFT Symposium and the 13th European Conference on Foundations of Software Engineering, ESEC/FSE ’11, pages 26–36, New York, NY, USA, 2011. ACM.

Digital Library

Cited By

Fei ZGe JLi CWang TLi YZhang HHuang LLuo B(2024)Patch Correctness Assessment: A SurveyACM Transactions on Software Engineering and Methodology10.1145/370297234:2(1-50)Online publication date: 8-Nov-2024
https://dl.acm.org/doi/10.1145/3702972
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
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
Show More Cited By

Index Terms

Anti-patterns in search-based program repair
1. Computing methodologies
  1. Machine learning
    1. Machine learning approaches
      1. Bio-inspired approaches
        Genetic programming
2. Software and its engineering
  1. Software creation and management
    1. Search-based software engineering
    2. Software verification and validation
      1. Software defect analysis
        Software testing and debugging

Recommendations

Large Language Models for Automated Program Repair
SPLASH 2023: Companion Proceedings of the 2023 ACM SIGPLAN International Conference on Systems, Programming, Languages, and Applications: Software for Humanity

This paper introduces two methods for automated program repair (APR) utilizing pre-trained language models. The first method demonstrates program repair as a code completion task and is validated on a dataset of Java programs. The second method, ...
Constraint-Based Program Debugging Using Data Structure Repair
ICST '11: Proceedings of the 2011 Fourth IEEE International Conference on Software Testing, Verification and Validation

Developers have used data structure repair over the last few decades as an effective means to recover on-the-fly from errors in program state. Traditional repair techniques were based on dedicated repair routines, whereas more recent techniques have ...
Anti-patterns for Java automated program repair tools
ASE '20: Proceedings of the 35th IEEE/ACM International Conference on Automated Software Engineering

Prior study has identified common anti-patterns in automated repair for C programs. In this work, we study if the same problems exist in Java programs. We performed a manual inspection on the plausible patches generated by Java automated repair tools. We ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

FSE 2016: Proceedings of the 2016 24th ACM SIGSOFT International Symposium on Foundations of Software Engineering

November 2016

1156 pages

ISBN:9781450342186

DOI:10.1145/2950290

General Chair:
Thomas Zimmermann
Microsoft Research, USA
,
Program Chairs:
Jane Cleland-Huang
University of Notre Dame, USA
,
Zhendong Su
University of California at Davis, USA

Copyright © 2016 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGSOFT: ACM Special Interest Group on Software Engineering

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 November 2016

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

FSE'16

Sponsor:

SIGSOFT

FSE'16: 24nd ACM SIGSOFT International Symposium on the Foundations of Software Engineering

November 13 - 18, 2016

WA, Seattle, USA

Acceptance Rates

Overall Acceptance Rate 17 of 128 submissions, 13%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

102
Total Citations
View Citations
720
Total Downloads

Downloads (Last 12 months)67
Downloads (Last 6 weeks)9

Reflects downloads up to 18 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Fei ZGe JLi CWang TLi YZhang HHuang LLuo B(2024)Patch Correctness Assessment: A SurveyACM Transactions on Software Engineering and Methodology10.1145/370297234:2(1-50)Online publication date: 8-Nov-2024
https://dl.acm.org/doi/10.1145/3702972
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
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
Yuan YHuyen PTan SMechtaev SKhurshid S(2024)ARJA-e for the First International Competition on Automated Program RepairProceedings of the 5th ACM/IEEE International Workshop on Automated Program Repair10.1145/3643788.3648019(50-52)Online publication date: 20-Apr-2024
https://dl.acm.org/doi/10.1145/3643788.3648019
Zhou XXu BKim KHan DNguyen HLe-Cong THe JLe BLo D(2024)Leveraging Large Language Model for Automatic Patch Correctness AssessmentIEEE Transactions on Software Engineering10.1109/TSE.2024.345225250:11(2865-2883)Online publication date: Nov-2024
https://doi.org/10.1109/TSE.2024.3452252
Zhang QFang CSun WLiu YHe THao XChen Z(2024)APPT: Boosting Automated Patch Correctness Prediction via Fine-Tuning Pre-Trained ModelsIEEE Transactions on Software Engineering10.1109/TSE.2024.335496950:3(474-494)Online publication date: Mar-2024
https://doi.org/10.1109/TSE.2024.3354969
Molina FCopia JGorla A(2024)Improving Patch Correctness Analysis via Random Testing and Large Language Models2024 IEEE Conference on Software Testing, Verification and Validation (ICST)10.1109/ICST60714.2024.00036(317-328)Online publication date: 27-May-2024
https://doi.org/10.1109/ICST60714.2024.00036
Dong YCheng XYang YZhang LWang SKong L(2024)A Method to Identify Overfitting Program Repair Patches Based on Expression TreeScience of Computer Programming10.1016/j.scico.2024.103105(103105)Online publication date: Mar-2024
https://doi.org/10.1016/j.scico.2024.103105
Zheng ZWang RTao ZLi HChen CLi TGuo S(2024)Automated patch correctness predicting to fix software defectExpert Systems with Applications: An International Journal10.1016/j.eswa.2024.124877256:COnline publication date: 5-Dec-2024
https://dl.acm.org/doi/10.1016/j.eswa.2024.124877
Song YXie XXu B(2024)When debugging encounters artificial intelligence: state of the art and open challengesScience China Information Sciences10.1007/s11432-022-3803-967:4Online publication date: 21-Feb-2024
https://doi.org/10.1007/s11432-022-3803-9
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