Software defects can impair functionality, open up security vulnerabilities, and consume a significant amount of developer time and effort. Motivated by these issues, we have developed multiple systems that automatically generate patches for software defects. These systems target real-world defects in large, production software systems (up to a million lines of code or more) and have demonstrated the ability to successfully patch a significant proportion of the defects in the benchmarks we use to evaluate our systems. Specifically, our systems have demonstrated the ability to generate correct patches for between 20% and 40% of these benchmark defects, depending on the system and the target defect class.

Our systems use a generate and validate approach. They generate candidate patches, then validate the patches against a test suite of inputs to find patches that validate. Because the test suites do not fully characterize desired application behavior, we have developed techniques that 1) deliver focused search spaces with many correct patches and 2) learn from previous successful human patches to recognize correct patches. The following papers present systems that we have developed:

• Automatic Inference of Code Transforms for Patch Generation
  Fan Long, Peter Amidon, and Martin Rinard
  Proceedings of 2017 11th Joint Meeting of the European Software Engineering Conference and the ACM SIGSOFT Symposium on the Foundations of Software Engineering
  Paderborn, Germany, September 2017

  Generate and validate systems work with a set of code transforms that, operating on the defective part of the program, generate candidate patches for the defect. Previous systems used manually developed sets of code transforms. The Genesis system presented in this paper is the first system to automatically infer sets of code transforms for automatic patch generation.

  Manually generated code transform systems typically contain around ten transforms. In contrast, working with over 1000 patches from over 350 applications, Genesis infers a transform system with over 100 transforms. Deploying this many transforms enables Genesis to capture a broad range of patch patterns, with the transforms selected to ensure the overall tractability and coverage of the resulting patch search space. On a set of 49 benchmark null pointer, out of bounds, and class cast defects drawn from 41 open source applications, Genesis generates correct patches for 21 of the 49 defects.

• Automatic Patch Generation by Learning Correct Code
  Fan Long and Martin Rinard
  Proceedings of the 43rd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL 2016)
  St. Petersburg, Florida, January 2016

  Because of weak test suites, generate and validate systems can often generate many more incorrect patches that validate than correct patches (see our ISSTA 2015 paper). The challenge is then to distinguish the few correct patches from the many incorrect patches that validate. This paper presents a technique that processes previous successful patches to learn universal correctness properties that characterize correct patches. It then uses these learned properties to prioritize correct patches. The results show that the resulting Prophet system generates correct patches for 18 of 69 defects, with 15 of these 18 correct patches ranked first by the learned universal correctness properties. This paper highlights the significant benefits that machine learning over large software repositories can deliver to automatic patch generation.

• An Analysis of the Search Spaces for Generate and Validate Patch Generation Systems
  The full version of this paper is available.
  Fan Long and Martin Rinard
  Proceedings of the ACM/IEEE 38th International Conference on Software Engineering (ICSE 2016)
  Austin, Texas May 2016

  Analyzes the search spaces of generate and validate patch generation systems and identifies a tradeoff between the number of correct patches in the search space, the amount of time required to search the space, and the number of incorrect patches that validate.

• Staged Program Repair with Condition Synthesis
  Fan Long and Martin Rinard
  10th Joint Meeting of the European Software Engineering Conference and the ACM SIGSOFT Symposium on the Foundations of Software Engineering (ESEC/FSE 2015)
  Bergamo, Italy, August 2015

  Presents a program repair system, SPR, that uses condition synthesis to automatically generate patches for real-world defects in large applications.

• An Analysis of Patch Plausibility and Correctness for Generate-And-Validate Patch Generation Systems
  The full version of this paper is available.
  Zichao Qi, Fan Long, Sara Achour, and Martin Rinard
  Proceedings of the 2015 International Conference on Software Testing and Analysis (ISSTA 2015)
  Baltimore, Maryland, July 2015

  Presents results that show that, because of weak test suites, many incorrect patches can nevertheless validate, that these incorrect validated patches are often equivalent to simply deleting code, and that these incorrect validated patches can have significant negative impacts such as the introduction of new security vulnerabilities.

• Automatically Patching Errors in Deployed Software
  Jeff H. Perkins, Sunghun Kim, Sam Larsen, Saman Amarasinghe, Jonathan Bachrach, Michael Carbin, Carlos Pacheco, Frank Sherwood, Stelios Sidiroglou, Greg Sullivan, Weng-Fai Wong, Yoav Zibin, Michael D. Ernst, and Martin C. Rinard
  22nd ACM Symposium on Operating Systems Principles (SOSP 2009)
  Big Sky, Montana, October 2009

  ClearView automatically patches defects in stripped x86 binaries, with no access to source code or debugging information. ClearView applies patches to running programs without requiring the application to restart. It can therefore be used in contexts where restarting the program is not an option.

  ClearView observes normal, error-free executions of the program to derive a model (in the form of invariants observed to be true in all observed executions) of the normal behavior of the program. It responds to errors that cause the program to crash by finding observed invariants that are violated when the program crashes, developing patches that change the state of the system (typically by changing the values in memory locations or registers) to enforce violated invariants, then observing executions of the system to find patches that successfully eliminate the effect of the error to enable the program to continue to execute. This technique can be especially effective in the context of a community of machines running similar software, since it can enable ClearView to obtain patches that make all machines invulnerable to an attack even though only a few have actually observed the attack.