Overfitting in Program Repair and Program Synthesis

Abstract:

Programming-by-example (PbE) is a technique for automatically teaching a computer new behavior via examples. PbE system attempts to inductively infer a program according to the specification demonstrated using concrete examples. However, the examples, which are usually represented in a form of (input, output) pairs, can only specify part of the behaviors of the expected program. The auto-generated program can easily overfit the given examples. Because of the overfitting problem, early test-driven program repair and program synthesis can produce low-quality patches or programs. Specifically, test-driven program repair seeks to rectify program bugs by automatically generating patches according to a correctness criterion in the form of a test suite. Test-based repair may produce overfitting patches, where the patched programs still fail on tests outside the test-suite driving the repair. Similarly, program synthesis, the technique that automatically generates programs according to given input-output examples, is also prone to synthesize overfitting programs.

I will present a series of approaches to advance programming-by-example techniques by alleviating the overfitting issues in program repair and synthesis. Our approaches are united by the idea of using program analysis to strengthen the specifications demonstrated via examples. We think this is a step forward to apply program repair in the real world and help programmers/end-users via program synthesis.