Connecting Program Synthesis and Reachability: Automatic Program Repair using Test-Input Generation
Preprint
Abstract
We prove that certain formulations of program synthesis and reachability are equivalent. Specifically, our constructive proof shows the reductions between the template-based synthesis problem, which generates a program in a pre-specified form, and the reachability problem, which decides the reachability of a program location. This establishes a link between the two research fields and allows for the transfer of techniques and results between them. To demonstrate the equivalence, we develop a program repair prototype using reachability tools. We transform a buggy program and its required specification into a specific program containing a location reachable only when the original program can be repaired, and then apply an off-the-shelf test-input generation tool on the transformed program to find test values to reach the desired location. Those test values correspond to repairs for the original programm. Preliminary results suggest that our approach compares favorably to other repair methods.Keywords
All Related Versions
This publication has 23 references indexed in Scilit:
- Connecting Program Synthesis and Reachability: Automatic Program Repair Using Test-Input Generation2017
- Alchemist: Learning Guarded Affine Functions2015
- Repair with On-The-Fly Program AnalysisLecture Notes in Computer Science, 2013
- Template-based program verification and program synthesisInternational Journal on Software Tools for Technology Transfer, 2012
- KLOVER: A Symbolic Execution and Automatic Test Generation Tool for C++ ProgramsLecture Notes in Computer Science, 2011
- Specification-Based Program Repair Using SAT2011
- The software model checker BlastInternational Journal on Software Tools for Technology Transfer, 2007
- JPF–SE: A Symbolic Execution Extension to Java PathFinder2007
- Supporting Controlled Experimentation with Testing Techniques: An Infrastructure and its Potential ImpactEmpirical Software Engineering, 2005
- Program Repair as a Game2005