An analysis of patch plausibility and correctness for generate-and-validate patch generation systems
By Zichao Qi, Fan Long, Sara Achour, Martin C. Rinard. 2015
488 citations recorded by the source corpus.
We analyze reported patches for three existing generate-and- validate patch generation systems (GenProg, RSRepair, and AE). The basic principle behind generate-and-validate systems is to accept only plausible patches that produce correct outputs for all inputs in the validation test suite. Because of errors in the patch evaluation infrastructure, the majority of the reported patches are not plausible — they do not produce correct outputs even for the inputs in the validation test suite. The overwhelming majority of the reported patches are not correct and are equivalent to a single modification that simply deletes functionality. Observed negative effects include the introduction of security vulnerabilities and the elimination of desirable functionality. We also present Kali, a generate-and-validate patch generation system that only deletes functionality. Working with a simpler and more effectively focused search space, Kali generates at least as many correct patches as prior GenProg, RSRepair, and AE systems. Kali also generates at least as many patches that produce correct outputs for the inputs in the validation test suite as the three prior systems. We also discuss the patches produced by ClearView, a generate-and-validate binary hot patching system that lever- ages learned invariants to produce patches that enable systems to survive otherwise fatal defects and security attacks. Our analysis indicates that ClearView successfully patches 9 of the 10 security vulnerabilities used to evaluate the system. At least 4 of these patches are correct.
Subfields: Software, Program Analysis & Verification, Signal Processing
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Software
- Lingming Zhang
- Chun Xia
- Charles Sutton
- Michele Tufano
- Miltiadis Allamanis
- Baishakhi Ray
- Vincent J. Hellendoorn
- Gabriele Bavota
In Program Analysis & Verification
- Miltiadis Allamanis
- Charles Sutton
- Prem Devanbu
- Chun Xia
- Lingming Zhang
- Kensen Shi
- Earl T. Barr
- Baishakhi Ray
In Signal Processing
- Prem Devanbu
- Baishakhi Ray
- Miltiadis Allamanis
- Saikat Chakraborty
- Charles Sutton
- Vincent J. Hellendoorn
- Abhik Roychoudhury
- Yangruibo Ding
Citations in the corpus
- PaLM: Scaling Language Modeling with Pathways (2022, background): “In the program repair literature, this problem has been particularly acute; in part due to limitations in test suites, the overwhelming majority of patches generated by systems at that time were not correct (Qi et al., 2015).”
- Evaluating Large Language Models Trained on Code (2021, neutral): “However, these works used an exact match against a reference instead of functional correctness, citing Qi et al. (2015)’s finding that most of the proposed solutions by genetic search in (Goues et al., 2012) passed through weak test suites by deleting functionality that failed.”
- SequenceR: Sequence-to-Sequence Learning for End-to-End Program Repair (2018, methodology): “We do not consider line deletion because: 1) it does not require a method for token generation (and is thus less interesting to our research) and 2) if desired, SEQUENCER could be combined with the lightweight Kali [11] to include line deletion.”
- An Empirical Study on Learning Bug-Fixing Patches in the Wild via Neural Machine Translation (2018, methodology): “wo major problems automated repair approaches have, are producing patches acceptable for programmers and especially for generate-and-validate techniques, over-fitting patches to test cases. Qi et al. [67] found that the majority of the reported patches generated by several generate-andvalidate techn”
- Patching as Translation: the Data and the Metaphor (2020, methodology): “Classic APR techniques can be categorized into 1) generate-andvalidate (G&V) [9, 17, 24, 25] or 2) synthesis-based approaches [20].”
- A syntax-guided edit decoder for neural program repair (2021, methodology): “For QuixBugs and IntroClassJava, we directly choosed the APR tools used in RepairThemAll [10] and DL-based APR tools which have experimented on these two benchmarks as baselines: jGenProg [35], RSRepair [55], Nopol [73], and CoCoNuT [44].”
- Nopol: Automatic Repair of Conditional Statement Bugs in Java Programs (2018, methodology): “actively explored research area [5], [6], [12], [13], [14].”
- Is the cure worse than the disease? overfitting in automated program repair (2015, background): “INTRODUCTION Automated program repair [4,13,17,18,26,28,29,32,36,37,39,39, 43,46,47,50,55,58,60,61] holds great potential to reduce debugging costs and improve software quality.”
- Baldur: Whole-Proof Generation and Repair with Large Language Models (2023, background): “It is possible to learn how to repair errors together by learning how to create errors, which can increase the amount of available training data, but poses an additional challenge of learning to approximate making human-like errors [107].”
- Staged program repair with condition synthesis (2015, methodology): “We modified the test scripts and test harnesses to eliminate various errors [32].”
- Less training, more repairing please: revisiting automated program repair via zero-shot learning (2022, methodology): “A popular approach for APR is Generate and Validate (G&V) [25, 29, 35, 38, 39, 44, 45, 49, 53, 61, 74].”
- Examining Zero-Shot Vulnerability Repair with Large Language Models (2021, background): “[41] found that although GenProg [42] claimed to fix 55 bugs, with stricter testing only two of the patches were correct.”
- Shaping program repair space with existing patches and similar code (2018, background): “As argued by existing studies [50, 57], deleting code often leads to incorrect patches, so we do not consider deletion in our search space.”
- History Driven Program Repair (2016, background): “Even merely plausible patches—those that lead the buggy program to pass the provide test cases, but that are not necessarily globally correct as judged by an informed programmer—may take more than 10 hours to generate, and the resulting patches may still be incorrect [25], [43].”
- CoCoNuT: combining context-aware neural translation models using ensemble for program repair (2020, unknown): “Pfect 15 SOSRepair [2] 16/23 16 Nopol [88] 2/9 1/4 17 (j)Kali [58, 68] 2/8 1/2 3/27 18 (j)GenProg [38, 58] 6/16 0/2 [255-369]/1423 2/18 19 RSRepair [67] 10/24 2/4 2/10 20 ARJA [91] 12/36 21 SequenceR [13] 12/19 22 ACS [87] 16/21 23 SimFix* [29] 27/50 24 kPAR* [46] 29/56 25 AVATAR* [48] 29/50 26 FixM”
- Generating bug-fixes using pretrained transformers (2021, background): “However, a followup paper (Qi et al., 2015) found that 53 out of the 55 claimed fixes were merely test-suite adequate, and that most of them were generated simply using the deletion operator.”
- Context-Aware Patch Generation for Better Automated Program Repair (2018, methodology): “Previous techniques [16, 19, 20, 29, 36, 46] use random techniques to search among these generated patches, and therefore, they are more likely to produce the incorrect plausible patches [38].”