OVER-FITTING IN PROGRAM REPAIR AND SYNTHESIS

Abstract

Programming-by-example (PbE) is one of the well-studied auto-programming techniques. PbE systems attempt to inductively construct programs according to the specification demonstrated using 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. If the given examples are incomplete, the auto-generated program can easily overfit the given examples. This thesis introduces a series of approaches to advance PbE 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. The experiments showed that the proposed techniques advance the state of the art repair/synthesis systems by discarding overfitted patches/programs and increasing the quality of automatically generated patches/programs. We think this is an important step forward to apply automated program repair in real world and help end-users via program synthesis.