ABSTRACT
Automated program repair has been studied via the use of techniques involving search, semantic analysis and artificial intelligence. Most of these techniques rely on tests as the correctness criteria, which causes the test overfitting problem. Although various approaches such as learning from code corpus have been proposed to address this problem, they are unable to guarantee that the generated patches generalize beyond the given tests. This work studies automated repair of errors using a reference implementation. The reference implementation is symbolically analyzed to automatically infer a specification of the intended behavior. This specification is then used to synthesize a patch that enforces conditional equivalence of the patched and the reference programs. The use of the reference implementation as an implicit correctness criterion alleviates overfitting in test-based repair. Besides, since we generate patches by semantic analysis, the reference program may have a substantially different implementation from the patched program, which distinguishes our approach from existing techniques for regression repair like Relifix. Our experiments in repairing the embedded Linux Busybox with GNU Coreutils as reference (and vice-versa) revealed that the proposed approach scales to real-world programs and enables the generation of more correct patches.
- Rajeev Alur, Rastislav Bodik, Eric Dallal, Dana Fisman, Pranav Garg, Garvit Juniwal, Hadas Kress-Gazit, P. Madhusudan, Milo M. K. Martin, Mukund Raghothaman, Shambwaditya Saha, Sanjit A. Seshia, Rishabh Singh, Armando Solar-Lezama, Emina Torlak, and Abhishek Udupa. 2015. Syntax-Guided Synthesis. In Dependable Software Systems Engineering. 1--25.Google Scholar
- Earl T. Barr, Yuriy Brun, Premkumar T. Devanbu, Mark Harman, and Federica Sarro. 2014. The plastic surgery hypothesis. In FSE. ACM, 306--317. Google ScholarDigital Library
- Earl T. Barr, Mark Harman, Yue Jia, Alexandru Marginean, and Justyna Petke. 2015. Automated Software Transplantation. In ISSTA. ACM, New York, NY, USA, 257--269. Google ScholarDigital Library
- Cristian Cadar, Daniel Dunbar, Dawson R Engler, et al. 2008. KLEE: Unassisted and Automatic Generation of High-Coverage Tests for Complex Systems Programs.. In OSDI, Vol. 8. 209--224. Google ScholarDigital Library
- Satish Chandra, Emina Torlak, Shaon Barman, and Rastislav Bodík. 2011. Angelic debugging. In ICSE. 121--130. Google ScholarDigital Library
- Leonardo De Moura and Nikolaj Bjørner. 2008. Z3: An Efficient SMT Solver. In TACAS. Springer-Verlag, Berlin, Heidelberg, 337--340. Google ScholarDigital Library
- Thomas Durieux, Matias Martinez, Martin Monperrus, Romain Sommerard, and Jifeng Xuan. 2015. Automatic Repair of Real Bugs: An Experience Report on the Defects4J Dataset. CoRR abs/1505.07002 (2015).Google Scholar
- Mark Harman, Yue Jia, and William B. Langdon. 2014. Babel Pidgin: SBSE Can Grow and Graft Entirely New Functionality into a Real World System. In SSBSE, Vol. 8636. Springer, 247--252.Google Scholar
- James A Jones, Mary Jean Harrold, and John Stasko. 2002. Visualization of test information to assist fault localization. In ICSE. ACM, 467--477. Google ScholarDigital Library
- Ming Kawaguchi, Shuvendu Lahiri, and Henrique Rebelo. 2010. Conditional equivalence. Technical Report.Google Scholar
- Yalin Ke, Kathryn T. Stolee, Claire Le Goues,and Yuriy Brun. 2015. Repairing Programs with Semantic Code Search. In ASE. IEEE Computer Society, 295--306.Google Scholar
- James C. King. 1976. Symbolic Execution and Program Testing. Commun. ACM 19, 7 (1976), 385--394. Google ScholarDigital Library
- Shuvendu K. Lahiri, Chris Hawblitzel, Ming Kawaguchi, and Henrique Rebêlo. 2012. SYMDIFF: A Language-Agnostic Semantic Diff Tool for Imperative Programs. In CAV. 712--717. Google ScholarDigital Library
- Shuvendu K. Lahiri, Rohit Sinha, and Chris Hawblitzel. 2015. Automatic Rootcausing for Program Equivalence Failures in Binaries. In CAV. 362--379.Google Scholar
- Xuan-Bach D. Le, Duc-Hiep Chu, David Lo, Claire Le Goues, and Willem Visser. 2017. JFIX: semantics-based repair of Java programs via symbolic PathFinder. In ISSTA. ACM, 376--379. Google ScholarDigital Library
- Claire Le Goues, Michael Dewey-Vogt, Stephanie Forrest, and WestleyWeimer. 2012. A Systematic Study ofAutomated Program Repair: Fixing 55 out of 105 Bugs for $8 Each. In ICSE. IEEE Press, 3--13. Google ScholarDigital Library
- Claire Le Goues, Neal Holtschulte, Edward K Smith, Yuriy Brun, Premkumar Devanbu, Stephanie Forrest, and Westley Weimer. 2015. The ManyBugs and IntroClass benchmarks for automated repair of C programs. TSE 41, 12 (2015), 1236--1256.Google ScholarDigital Library
- Claire Le Goues, ThanhVu Nguyen, Stephanie Forrest, and Westley Weimer. 2012. GenProg: A generic method for automatic software repair. IEEE TSE 38, 1 (2012), 54--72. Google ScholarDigital Library
- Rainer Leupers. 2013. Code optimization techniques for embedded processors: Methods, algorithms, and tools. Springer Science & Business Media. Google ScholarDigital Library
- Qing Li, Tatuya Jinmei, and Keiichi Shima. 2010. IPv6 Core Protocols Implementation. Morgan Kaufmann. Google ScholarDigital Library
- Fan Long and Martin Rinard. {n. d.}. Staged program repair with condition synthesis. In ESEC/FSE. ACM, 166--178. Google ScholarDigital Library
- Fan Long and Martin Rinard. 2016. Automatic patch generation by learning correct code. In POPL. ACM, 298--312. Google ScholarDigital Library
- Paul Dan Marinescu and Cristian Cadar. 2012. Make test-zesti: A symbolic execution solution for improving regression testing. In ICSE. IEEE Press, 716--726. Google ScholarDigital Library
- Matias Martinez and Martin Monperrus. 2015. Mining software repair models for reasoning on the search space of automated program fixing. Empirical Software Engineering 20, 1 (2015), 176--205. Google ScholarDigital Library
- Sergey Mechtaev, Jooyong Yi, and Abhik Roychoudhury. 2015. Directfix: Looking for simple program repairs. In ICSE. IEEE Press, 448--458. Google ScholarDigital Library
- Sergey Mechtaev, Jooyong Yi, and Abhik Roychoudhury. 2016. Angelix: Scalable Multiline Program Patch Synthesis via Symbolic Analysis. In ICSE. 691--701. Google ScholarDigital Library
- Hoang Duong Thien Nguyen, Dawei Qi, Abhik Roychoudhury, and Satish Chandra. 2013. SemFix: Program Repair via Semantic Analysis. In ICSE. IEEE Press, Piscataway, NJ, USA, 772--781. Google ScholarDigital Library
- Suzette Person, Matthew B. Dwyer, Sebastian G. Elbaum, and Corina S. Pasareanu. 2008. Differential symbolic execution. In FSE. 226--237. Google ScholarDigital Library
- Justyna Petke, Mark Harman, William B. Langdon, and Westley Weimer. 2014. Using Genetic Improvement and Code Transplants to Specialise a C+ + Program to a Problem Class. In EuroGP, Vol. 8599. Springer, 137--149. Google ScholarDigital Library
- Yuhua Qi, Xiaoguang Mao, Yan Lei, Ziying Dai, and Chengsong Wang. 2014. The strength of random search on automated program repair. In ICSE. ACM, 254--265. Google ScholarDigital Library
- Stelios Sidiroglou-Douskos, Eric Lahtinen, Anthony Eden, Fan Long, and Martin Rinard. 2017. CodeCarbonCopy. In ESEC/FSE. ACM, 95--105. Google ScholarDigital Library
- Stelios Sidiroglou-Douskos, Eric Lahtinen, Fan Long, and Martin Rinard. 2015. Automatic Error Elimination by Horizontal Code Transfer Across Multiple Applications. In PLDI. ACM, New York, NY, USA, 43--54. Google ScholarDigital Library
- Kathryn T. Stolee, Sebastian G. Elbaum, and Daniel Dobos. 2014. Solving the Search for Source Code. ACM Trans. Softw. Eng. Methodol. 23,3 (2014), 26:1--26:45. Google ScholarDigital Library
- Kathryn T. Stolee, Sebastian G. Elbaum, and Matthew B. Dwyer. 2016. Code search with input/output queries: Generalizing, ranking, and assessment. Journal of Systems and Software 116 (2016), 35--48. Google ScholarDigital Library
- Shin Hwei Tan and Abhik Roychoudhury. 2015. relifix: Automated repair of software regressions. In ICSE. IEEE Press, 471--482. Google ScholarDigital Library
- Shin Hwei Tan, Jooyong Yi, Sergey Mechtaev, Abhik Roychoudhury, et al. 2017. Codeflaws: a programming competition benchmark for evaluating automated program repair tools. In ICSE Companion. 180--182. Google ScholarDigital Library
- Shin Hwei Tan, Hiroaki Yoshida, Mukul R Prasad, and Abhik Roychoudhury. 2016. Anti-patterns in search-based program repair. In FSE. ACM, 727--738. Google ScholarDigital Library
- Nikolai Tillmann and Wolfram Schulte. 2005. Parameterized unit tests. In ACM SIGSOFT Software Engineering Notes, Vol. 30. ACM, 253--262. Google ScholarDigital Library
- Busybox Website. 2017. Busybox. https://busybox.net/. (2017).Google Scholar
- GNU Coreutils Website. 2017. GNU Coreutils. https://www.gnu.org/software/coreutils/coreutils.html. (2017).Google Scholar
- Westley Weimer, Zachary P. Fry, and Stephanie Forrest. 2013. Leveraging program equivalence for adaptive program repair: Models and first results. In ASE. IEEE, 356--366. Google ScholarDigital Library
- Westley Weimer, ThanhVu Nguyen, Claire Le Goues, and Stephanie Forrest. 2009. Automatically Finding Patches Using Genetic Programming. In ICSE. IEEE Computer Society, 364--374. Google ScholarDigital Library
- Qi Xin and Steven P Reiss. 2017. Identifying test-suite-overfitted patches through test case generation. In ISSTA. ACM, 226--236. Google ScholarDigital Library
- Yingfei Xiong, Jie Wang, Runfa Yan, Jiachen Zhang, Shi Han, Gang Huang, and Lu Zhang. 2017. Precise condition synthesis for program repair. In ICSE. IEEE / ACM, 416--426. Google ScholarDigital Library
- Jifeng Xuan, Matias Martinez, Favio Demarco, Maxime Clement, Sebastian R. Lamelas Marcote, Thomas Durieux, Daniel Le Berre, and Martin Monperrus. 2017. Nopol: Automatic Repair of Conditional Statement Bugs in Java Programs. IEEE TSE 43, 1 (2017), 34--55. Google ScholarDigital Library
- Jinqiu Yang, Alexey Zhikhartsev, Yuefei Liu, and Lin Tan. 2017. Better test cases for better automated program repair. In ESEC/FSE. ACM, 831--841. Google ScholarDigital Library
- Jooyong Yi, Shin Hwei Tan, Sergey Mechtaev, Marcel Boehme, and Abhik Roychoudhury. 2018. Correlation of Test-suite Metrics with Patch Quality in Program Repair. Empirical Software Engineering To appear (2018).Google Scholar
- Andreas Zeller. 1999. Yesterday, My Program Worked. Today, It Does Not. Why?. In FSE. Springer-Verlag, London, UK, UK, 253--267. Google ScholarDigital Library
- Tianyi Zhang and Miryung Kim. 2017. Automated transplantation and differential testing for clones. In ICSE. IEEE / ACM, 665--676. Google ScholarDigital Library
Index Terms
- Semantic program repair using a reference implementation
Recommendations
Angelix: scalable multiline program patch synthesis via symbolic analysis
ICSE '16: Proceedings of the 38th International Conference on Software EngineeringSince debugging is a time-consuming activity, automated program repair tools such as GenProg have garnered interest. A recent study revealed that the majority of GenProg repairs avoid bugs simply by deleting functionality. We found that SPR, a state-of-...
Model and Program Repair via SAT Solving
Special Issue on MEMCODE 2015 and Regular Papers (Diamonds)We consider the subtractive model repair problem: given a finite Kripke structure M and a CTL formula η, determine if M contains a substructure M′ that satisfies η. Thus, M can be “repaired” to satisfy eta by deleting some transitions and states. We map ...
Repair with on-the-fly program analysis
HVC'12: Proceedings of the 8th international conference on Hardware and Software: verification and testingThis paper presents a novel automatic repair approach for incorrect programs. It applies formal methods and analyzes program behavior only on demand. We argue that this is beneficial, especially if exhaustive program analysis is infeasible. Our approach ...
Comments