More Web Proxy on the site http://driver.im/

research-article

Public Access

Automatic patch generation by learning correct code

Authors:

Martin RinardAuthors Info & Claims

POPL '16: Proceedings of the 43rd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages

Pages 298 - 312

https://doi.org/10.1145/2837614.2837617

Published: 11 January 2016 Publication History

Abstract

We present Prophet, a novel patch generation system that works with a set of successful human patches obtained from open- source software repositories to learn a probabilistic, application-independent model of correct code. It generates a space of candidate patches, uses the model to rank the candidate patches in order of likely correctness, and validates the ranked patches against a suite of test cases to find correct patches. Experimental results show that, on a benchmark set of 69 real-world defects drawn from eight open-source projects, Prophet significantly outperforms the previous state-of-the-art patch generation system.

References

[1]

GitHub. https://github.com/.

[2]

E. D. Berger and B. G. Zorn. Diehard: Probabilistic memory safety for unsafe languages. In Proceedings of the 2006 ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI ’06’, pages 158–168. ACM, 2006.

Digital Library

[3]

S. Chandra, E. Torlak, S. Barman, and R. Bodik. Angelic debugging. In Proceedings of the 33rd International Conference on Software Engineering, ICSE ’11’, pages 121–130, New York, NY, USA, 2011. ACM.

Digital Library

[4]

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

[5]

B. Demsky, M. D. Ernst, P. J. Guo, S. McCamant, J. H. Perkins, and M. C. Rinard. Inference and enforcement of data structure consistency specifications. In Proceedings of the ACM/SIGSOFT International Symposium on Software Testing and Analysis, ISSTA 2006, Portland, Maine, USA, July 17-20, 2006, pages 233–244, 2006.

Digital Library

[6]

B. Demsky and M. C. Rinard. Goal-directed reasoning for specification-based data structure repair. IEEE Trans. Software Eng., 32(12):931–951, 2006.

Digital Library

[7]

K. Dobolyi and W. Weimer. Changing java’s semantics for handling null pointer exceptions. In 19th International Symposium on Software Reliability Engineering (ISSRE 2008), 11-14 November 2008, Seattle/Redmond, WA, USA, pages 47–56, 2008.

Digital Library

[8]

T. Durieux, M. Martinez, M. Monperrus, R. Sommerard, and J. Xuan. Automatic repair of real bugs: An experience report on the defects4j dataset. CoRR, abs/1505.07002, 2015.

[9]

Q. Gao, Y. Xiong, Y. Mi, L. Zhang, W. Yang, Z. Zhou, B. Xie, and H. Mei. Safe memory-leak fixing for c programs. In Proceedings of the 37th International Conference on Software Engineering - Volume 1, ICSE ’15’, pages 459–470, Piscataway, NJ, USA, 2015. IEEE Press.

Digital Library

[10]

Q. Gao, H. Zhang, J. Wang, Y. Xiong, L. Zhang, and H. Mei. Fixing recurring crash bugs via analyzing Q&A sites. In Proc. of ASE, 2015.

Digital Library

[11]

M. Jose and R. Majumdar. Cause clue clauses: Error localization using maximum satisfiability. In Proceedings of the 32Nd ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI ’11’, pages 437–446, New York, NY, USA, 2011. ACM.

Digital Library

[12]

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. IEEE Press, 2013.

Digital Library

[13]

M. Kling, S. Misailovic, M. Carbin, and M. Rinard. Bolt: on-demand infinite loop escape in unmodified binaries. In Proceedings of the ACM international conference on Object oriented programming systems languages and applications, OOPSLA ’12’, pages 431–450. ACM, 2012.

Digital Library

[14]

E. Kneuss, M. Koukoutos, and V. Kuncak. Deductive program repair. In Computer-Aided Verification (CAV), 2015.

[15]

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

Digital Library

[16]

F. Long, V. Ganesh, M. Carbin, S. Sidiroglou, and M. Rinard. Automatic input rectification. ICSE ’12, 2012.

Digital Library

[17]

F. Long and M. Rinard. Staged Program Repair in SPR. Technical Report MIT-CSAIL-TR-2015-008, 2015.

[18]

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

[19]

F. Long, S. Sidiroglou-Douskos, D. Kim, and M. Rinard. Sound input filter generation for integer overflow errors. In Proceedings of the 41st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL ’14’, pages 439–452, New York, NY, USA, 2014. ACM.

Digital Library

[20]

F. Long, S. Sidiroglou-Douskos, and M. Rinard. Automatic runtime error repair and containment via recovery shepherding. In Proceedings of the 35th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI ’14’, pages 227–238, New York, NY, USA, 2014. ACM.

Digital Library

[21]

M. Martinez and M. Monperrus. Mining software repair models for reasoning on the search space of automated program fixing. Empirical Software Engineering, 20(1):176–205, 2015.

Digital Library

[22]

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, pages 234–242, New York, NY, USA, 2014. ACM.

Digital Library

[23]

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

Digital Library

[24]

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

Digital Library

[25]

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. ACM, 2009.

Digital Library

[26]

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, pages 254–265, New York, NY, USA, 2014. ACM.

Digital Library

[27]

Z. Qi, F. Long, S. Achour, and M. Rinard. An anlysis of patch plausibility and correctness for generate-and-validate patch generation systems. In Proceedings of the ACM/SIGSOFT International Symposium on Software Testing and Analysis, ISSTA 2015, 2015.

Digital Library

[28]

V. Raychev, M. Vechev, and A. Krause. Predicting program properties from "big code". In Proceedings of the 42Nd Annual ACM SIGPLANSIGACT Symposium on Principles of Programming Languages, POPL ’15’, pages 111–124, New York, NY, USA, 2015. ACM.

Digital Library

[29]

M. Rinard, C. Cadar, D. Dumitran, D. M. Roy, T. Leu, and W. S. Beebee. Enhancing server availability and security through failureoblivious computing. In OSDI, pages 303–316, 2004.

Digital Library

[30]

R. Samanta, O. Olivo, and E. A. Emerson. Cost-aware automatic program repair. In Static Analysis - 21st International Symposium, SAS 2014, Munich, Germany, September 11-13, 2014. Proceedings, pages 268–284, 2014.

[31]

H. Samimi, M. Schäfer, S. Artzi, T. D. Millstein, F. Tip, and L. J. Hendren. Automated repair of HTML generation errors in PHP applications using string constraint solving. In ICSE 2012, June 2-9, 2012, Zurich, Switzerland, pages 277–287, 2012.

Digital Library

[32]

J. Shen. RIFL: A Language with Filtered Iterators. Master’s thesis, Massachusetts Institute of Technology, 2015.

[33]

S. Sidiroglou, E. Lahtinen, F. Long, and M. Rinard. Automatic error elimination by multi-application code transfer. In Proceedings of the 36th ACM SIGPLAN Conference on Programming Language Design and Implementation. ACM, 2015.

Digital Library

[34]

S. Son, K. S. McKinley, and V. Shmatikov. Fix me up: Repairing access-control bugs in web applications. In NDSS, 2013.

[35]

W. Weimer, Z. P. Fry, and S. Forrest. Leveraging program equivalence for adaptive program repair: Models and first results. In ASE’13, pages 356–366, 2013.

Digital Library

[36]

W. Weimer, T. Nguyen, C. Le Goues, and S. Forrest. Automatically finding patches using genetic programming. In Proceedings of the 31st International Conference on Software Engineering, ICSE ’09’, pages 364–374. IEEE Computer Society, 2009.

Digital Library

[37]

A. Zeller and R. Hildebrandt. Simplifying and isolating failureinducing input. IEEE Trans. Softw. Eng., 28(2):183–200, Feb. 2002.

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
Li YPei HHuang LYin BCai K(2024)Automatic Repair of Quantum Programs via Unitary OperationACM Transactions on Software Engineering and Methodology10.1145/366460433:6(1-43)Online publication date: 28-Jun-2024
https://dl.acm.org/doi/10.1145/3664604
Show More Cited By

Index Terms

Automatic patch generation by learning correct code
1. Software and its engineering
  1. Software creation and management
    1. Software verification and validation
      1. Software defect analysis
        Software testing and debugging
2. Theory of computation
  1. Semantics and reasoning
    1. Program semantics

Recommendations

Automatic inference of code transforms for patch generation
ESEC/FSE 2017: Proceedings of the 2017 11th Joint Meeting on Foundations of Software Engineering

We present a new system, Genesis, that processes human patches to automatically infer code transforms for automatic patch generation. We present results that characterize the effectiveness of the Genesis inference algorithms and the complete Genesis ...
Automatic patch generation by learning correct code
POPL '16

We present Prophet, a novel patch generation system that works with a set of successful human patches obtained from open- source software repositories to learn a probabilistic, application-independent model of correct code. It generates a space of ...
An analysis of the search spaces for generate and validate patch generation systems
ICSE '16: Proceedings of the 38th International Conference on Software Engineering

We present the first systematic analysis of key characteristics of patch search spaces for automatic patch generation systems. We analyze sixteen different configurations of the patch search spaces of SPR and Prophet, two current state-of-the-art patch ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

POPL '16: Proceedings of the 43rd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages

January 2016

815 pages

ISBN:9781450335492

DOI:10.1145/2837614

General Chair:
Rastislav Bodik
UC Berkeley, USA
,
Program Chair:
Rupak Majumdar
MPI-SWS, Germany

ACM SIGPLAN Notices Volume 51, Issue 1
POPL '16
January 2016
815 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/2914770
Editor:
Andy Gill
University of Kansas, Lawrence, KS
Issue’s Table of Contents

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

SIGPLAN: ACM Special Interest Group on Programming Languages

In-Cooperation

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 January 2016

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Defense Advanced Research Projects Agency

Conference

POPL '16

Sponsor:

SIGPLAN

POPL '16: The 43rd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages

January 20 - 22, 2016

FL, St. Petersburg, USA

Acceptance Rates

Overall Acceptance Rate 824 of 4,130 submissions, 20%

Upcoming Conference

POPL '25

Sponsor:
sigplan

The 52nd Annual ACM SIGPLAN Symposium on Principles of Programming Languages

January 19 - 25, 2025

Denver , CO , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

398
Total Citations
View Citations
5,212
Total Downloads

Downloads (Last 12 months)643
Downloads (Last 6 weeks)73

Reflects downloads up to 18 Dec 2024

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
Li YPei HHuang LYin BCai K(2024)Automatic Repair of Quantum Programs via Unitary OperationACM Transactions on Software Engineering and Methodology10.1145/366460433:6(1-43)Online publication date: 28-Jun-2024
https://dl.acm.org/doi/10.1145/3664604
Raj AGibbs WDong FVadayath JTompkins MWirsz SLiu YHu ZZhu CMenon GDolan-Gavitt BDoupé AWang RShoshitaishvili YBao TLuo BLiao XXu JKirda ELie D(2024)Fuzz to the Future: Uncovering Occluded Future Vulnerabilities via Robust FuzzingProceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security10.1145/3658644.3690278(3719-3733)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1145/3658644.3690278
Ouyang YYang JZhang LChristakis MPradel M(2024)Benchmarking Automated Program Repair: An Extensive Study on Both Real-World and Artificial BugsProceedings of the 33rd ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3650212.3652140(440-452)Online publication date: 11-Sep-2024
https://dl.acm.org/doi/10.1145/3650212.3652140
Zhang JCambronero JGulwani SLe VPiskac RSoares GVerbruggen G(2024)PyDex: Repairing Bugs in Introductory Python Assignments using LLMsProceedings of the ACM on Programming Languages10.1145/36498508:OOPSLA1(1100-1124)Online publication date: 29-Apr-2024
https://dl.acm.org/doi/10.1145/3649850
Lajko MCsuvik VGyimothy TVidacs LHuyen PTan SMechtaev SKhurshid S(2024)Automated Program Repair with the GPT Family, including GPT-2, GPT-3 and CodeXProceedings of the 5th ACM/IEEE International Workshop on Automated Program Repair10.1145/3643788.3648021(34-41)Online publication date: 20-Apr-2024
https://dl.acm.org/doi/10.1145/3643788.3648021
Xie LLi CPei YZhang TPan MHuyen PTan SMechtaev SKhurshid S(2024)Automated Program Repair for Introductory Programming Assignments via Bidirectional RefactoringProceedings of the 5th ACM/IEEE International Workshop on Automated Program Repair10.1145/3643788.3648017(53-55)Online publication date: 20-Apr-2024
https://dl.acm.org/doi/10.1145/3643788.3648017
Wu GSullivan AEgyed AWimmer MChechik MCombemale B(2024)AlloyASG: Alloy Predicate Code Representation as a Compact Structurally Balanced GraphProceedings of the ACM/IEEE 27th International Conference on Model Driven Engineering Languages and Systems10.1145/3640310.3674088(57-68)Online publication date: 22-Sep-2024
https://dl.acm.org/doi/10.1145/3640310.3674088
Williams DCallan JKirbas SMechtaev SPetke JPrideaux-Ghee TSarro FRoychoudhury APaiva AAbreu RStorey MAniche MNagappan N(2024)User-Centric Deployment of Automated Program Repair at BloombergProceedings of the 46th International Conference on Software Engineering: Software Engineering in Practice10.1145/3639477.3639756(81-91)Online publication date: 14-Apr-2024
https://dl.acm.org/doi/10.1145/3639477.3639756
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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

Media

Figures

Other

Tables

View Table of Contents