CoChat
Sign Up
Cited by 167Software Testing and Debugging TechniquesSoftware Engineering ResearchEvolutionary Algorithms and Applications

An Analysis of the Search Spaces for Generate and Validate Patch Generation Systems

Open access
Long, Fan, Rinard, Martin·2016·Proceedings of the 38th International Conference on Software Engineering
DOI 10.1145/2884781.2884872
Open this paper in CoChat — free accountOpen PDF

Abstract

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 generation systems. The analysis shows that 1) correct patches are sparse in the search spaces (typically at most one correct patch per search space per defect), 2) incorrect patches that nevertheless pass all of the test cases in the validation test suite are typically orders of magnitude more abundant, and 3) leveraging information other than the test suite is therefore critical for enabling the system to successfully isolate correct patches.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1145/2884781.2884872

Cites

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

The citation lists haven’t been fetched yet

References 46 · Cited by 167

Research works printed but not linked: 35

  1. [1][1] E. T. Barr, Y. Brun, P. Devanbu, M. Harman, and F. Sarro. The Plastic Surgery Hypothesis. In Proceedings of the 22nd ACM SIGSOFT Symposium on the Foundations of Software Engineering (FSE), pages 306–317, Hong Kong, China, November 2014.
  2. [2][2] C. Cadar, D. Dunbar, and D. Engler. Klee: Unassisted and automatic generation of high-coverage tests for complex systems programs. In Proceedings of the 8th USENIX Conference on Operating Systems Design and Implementation, OSDI'08, pages 209–224, Berkeley, CA, USA, 2008. USENIX Association.
  3. [3][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.
  4. [4][4] 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.
  5. [5][5] B. Demsky and M. C. Rinard. Automatic detection and repair of errors in data structures. In OOPSLA, pages 78–95, 2003.
  6. [6][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.
  7. [7][7] 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. · arXiv
  8. [8][8] Y. H. Eom and B. Demsky. Self-stabilizing java. In ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI '12, Beijing, China - June 11 - 16, 2012, pages 287–298, 2012.
  9. [9][9] 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.
  10. [10][10] D. Gopinath, S. Khurshid, D. Saha, and S. Chandra. Data-guided repair of selection statements. In Proceedings of the 36th International Conference on Software Engineering, ICSE 2014, pages 243–253, New York, NY, USA, 2014. ACM.
  11. [12][12] 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.
  12. [13][13] 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.
  13. [14][14] 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.
  14. [15][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.
  15. [16][16] F. Long and M. Rinard. Staged program repair with condition synthesis. In Proceedings of 10th Joint Meeting of the European Software Engineering Conference and the ACM SIGSOFT Symposium on the Foundations of Software Engineering (ESEC/FSE 2015) Proceedings of ESEC/FSE, 2015.
  16. [17][17] 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 2016, pages 298–312, New York, NY, USA, 2016. ACM.
  17. [18][18] 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.
  18. [19][19] 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.
  19. [20][20] M. Martinez, W. Weimer, and M. Monperrus. Do the fix ingredients already exist? an empirical inquiry into the redundancy assumptions of program repair approaches. In Companion Proceedings of the 36th International Conference on Software Engineering, ICSE Companion 2014, pages 492–495, New York, NY, USA, 2014. ACM.
  20. [21][21] 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.
  21. [22][22] 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.
  22. [23][23] H. H. Nguyen and M. C. Rinard. Detecting and eliminating memory leaks using cyclic memory allocation. In Proceedings of the 6th International Symposium on Memory Management, ISMM 2007, Montreal, Quebec, Canada, October 21-22, 2007, pages 15–30, 2007.
  23. [24][24] 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.
  24. [25][25] Y. Pei, C. A. Furia, M. Nordio, Y. Wei, B. Meyer, and A. Zeller. Automated fixing of programs with contracts. IEEE Trans. Software Eng., 40(5):427–449, 2014.
  25. [26][26] 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.
  26. [27][27] 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.
  27. [28][28] 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 ACM/SIGSOFT International Symposium on Software Testing and Analysis, ISSTA 2015, 2015.
  28. [29][29] M. Rinard, C. Cadar, D. Dumitran, D. M. Roy, T. Leu, and W. S. Beebee. Enhancing server availability and security through failure-oblivious computing. In OSDI, pages 303–316, 2004.
  29. [30][30] M. C. Rinard. Probabilistic accuracy bounds for fault-tolerant computations that discard tasks. In ICS, pages 324–334, 2006.
  30. [31][31] M. C. Rinard. Using early phase termination to eliminate load imbalances at barrier synchronization points. In OOPSLA, pages 369–386, 2007.
  31. [33][33] 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, Portland, OR, USA, June 15-17, 2015, pages 43–54, 2015.
  32. [35][35] S. Son, K. S. McKinley, and V. Shmatikov. Fix me up: Repairing access-control bugs in web applications. In NDSS, 2013.
  33. [36][36] Y. Wei, Y. Pei, C. A. Furia, L. S. Silva, S. Buchholz, B. Meyer, and A. Zeller. Automated fixing of programs with contracts. In Proceedings of the 19th International Symposium on Software Testing and Analysis, ISSTA '10', pages 61–72, New York, NY, USA, 2010. ACM.
  34. [37][37] 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.
  35. [38][38] H. Zhong and Z. Su. An empirical study on real bug fixes. In 37th IEEE/ACM International Conference on Software Engineering, ICSE 2015, Florence, Italy, May 16-24, 2015, Volume 1, pages 913–923, 2015.

Authors
Long, F., & Rinard, M.
Affiliations
MIT Computer Science and Artificial Intelligence Laboratory (US)
ORCID
Venue
Proceedings of the 38th International Conference on Software Engineering
Publisher
ACM
Published
2016-05-14
Pages
702-713
ISSN
0270-5257 (ISSN-L)
DOI
10.1145/2884781.2884872
OpenAlex
W2288083000
Cited by
167
References
46
Citations by year
2026: 8 · 2025: 10 · 2024: 8 · 2023: 7 · 2022: 15 · 2021: 23 · 2020: 17 · 2019: 22 · 2018: 25 · 2017: 23 · 2016: 9
FWCI
19.44
Type
conference paper
Language
en
Open access
Licence
www.acm.org/publications/policies/copyright_policy#Background (vor)
Locations
  • ACM/IEEE International Conference on Software Engineering: Companion Proceedings (ICSE-Companion) (publishedVersion)
  • arXiv (Cornell University) (submittedVersion)
  • DSpace@MIT (Massachusetts Institute of Technology) (submittedVersion, cc-by-nc)
  • DSpace@MIT (Massachusetts Institute of Technology) (submittedVersion, cc-by-nc-sa)
  • arXiv (Cornell University)
Funders
Defense Advanced Research Projects Agency (FA8750-14-2-0242, FA8750, FA8650- 11-C-7192)
Topics
  • Physical Sciences › Computer Science › Software › Software Testing and Debugging Techniques
  • Physical Sciences › Computer Science › Information Systems › Software Engineering Research
  • Physical Sciences › Computer Science › Artificial Intelligence › Evolutionary Algorithms and Applications
Keywords
SPR, prophets, software defect repair

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review