CPR: A new automated program repair technique based on concolic execution which works on patch abstraction with the sub-optimal goal of refining the patch to less over-fit the initial test cases.
Automated program repair reduces the manual effort in fixing program errors. However, existing repair techniques modify a buggy program such that it passes given tests. Such repair techniques do not discriminate between correct patches and patches that overfit the available tests and break untested but desired functionality. We attempt to solve this problem with a novel solution that make use of the duality of space exploration in Input Space and Program Space. We implemented our technique in the form of a tool called CPR and evaluated its efficacy in reducing the patch space by discarding overfitting patches from a pool of plausible patches. Similar to Cardio-Pulmonary Resuscitation (CPR) does to a patient, our tool CPR resuscitate or recover programs via appropriate fixes.
In this work, we therefore propose and implement an integrated approach for detecting and discarding overfitting patches by exploiting the relationship between the patch space and input space. We leverage concolic path exploration to systematically traverse the input space (and generate inputs), while systematically ruling out significant parts of the patch space. Given a long enough time budget, this approach allows a significant reduction in the pool of patch candidates, as shown by our experiments.
CPR is a reconfigurable APR tool for C source-codes. CPR is:
- Extensible: CPR is designed so that it can be easily extended to plug in any component to replace existing
- Efficient: CPR utilize parallel computing to improve performance
We provide a ready-made container which includes all necessary envrionment set-up to deploy and run our tool. Dependencies include:
- LLVM 3.4
- KLEE 1.4
- Python 3.7
- Z3 SMT Solver
- MathSAT Solver
- Docker
Build and run a container:
docker build -t cpr .
docker run --rm -ti cpr /bin/bash
We provide several examples you can run to test our tool, all test cases are included in the 'tests' directory.
Run examples:
pypy3 CPR.py --conf=tests/bug-types/div-zero/div-zero-1/repair.conf
pypy3 CPR.py --conf=tests/bug-types/div-zero/div-zero-2/repair.conf
CPR should be considered alpha-quality software. Bugs can be reported here:
https://github.com/rshariffdeen/CPR/issues
We welcome contributions to improve this work, see details
- Ridwan Shariffdeen
- Yannic Noller
- Sergey Mechtaev
Concolic Program Repair
Ridwan Shariffdeen, Yannic Noller, Lars Grunske, Abhik Roychoudhury
42nd ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), 2021
This work was partially supported by the National Satellite of Excellence in Trustworthy Software Systems, funded by National Research Foundation (NRF) Singapore.
This project is licensed under the MIT License - see the LICENSE file for details