ABSTRACT
Effective program repair techniques, which modify faulty programs to fix them with respect to given test suites, can substantially reduce the cost of manual debugging. A common repair approach is to iteratively first generate candidate programs with possible bug fixes and then validate them against the given tests until a candidate that passes all the tests is found. While this approach is conceptually simple, due to the potentially high number of candidates that need to first be generated and then be compiled and tested, existing repair techniques that embody this approach have relatively low effectiveness, especially for faults at a fine granularity.
To tackle this limitation, we introduce a novel repair technique, SketchFix, which generates candidate fixes on demand (as needed) during the test execution. Instead of iteratively re-compiling and re-executing each actual candidate program, SketchFix translates faulty programs to sketches, i.e., partial programs with "holes", and compiles each sketch once which may represent thousands of concrete candidates. With the insight that the space of candidates can be reduced substantially by utilizing the runtime behaviors of the tests, SketchFix lazily initializes the candidates of the sketches while validating them against the test execution.
We experimentally evaluate SketchFix on the Defects4J benchmark and the experimental results show that SketchFix works particularly well in repairing bugs with expression manipulation at the AST node-level granularity compared to other program repair techniques. Specifically, SketchFix correctly fixes 19 out of 357 defects in 23 minutes on average using the default setting. In addition, SketchFix finds the first repair with 1.6% of re-compilations (#compiled sketches/#candidates) and 3.0% of re-executions out of all repair candidates.
- Rui Abreu, Peter Zoeteweij, and Arjan J. C. van Gemund. On the accuracy of spectrum-based fault localization. In Testing - Practice and Research Techniques, 5th International Academic and Industrial Conference, TAIC PART 2007. Google ScholarDigital Library
- Christoffer Quist Adamsen, Anders Møller, Rezwana Karim, Manu Sridharan, Frank Tip, and Koushik Sen. 2017. Repairing event race errors by controlling nondeterminism. In Proceedings of the 39th International Conference on Software Engineering, ICSE 2017, Buenos Aires, Argentina, May 20--28, 2017. 289--299. Google ScholarDigital Library
- ASM Java bytecode manipulation and analysis framework 2017. (2017). http://asm.ow2.org/ Accessed: 07-30-2017.Google Scholar
- Closure Compiler 2017. https://github.com/google/closure-compiler. (2017). Accessed: 2018-02-10.Google Scholar
- Loris D'Antoni, Roopsha Samanta, and Rishabh Singh. 2016. Qlose: Program Repair with Quantitative Objectives. In Computer Aided Verification - 28th International Conference, CAV 2016, Toronto, ON, Canada, July 17--23, 2016, Proceedings, Part II. 383--401.Google Scholar
- Vidroha Debroy and W. Eric Wong. 2010. Using Mutation to Automatically Suggest Fixes for Faulty Programs. In 3rd IEEE International Conference on Software Testing, Verification and Validation, ICST 2010. 65--74. Google ScholarDigital Library
- Favio Demarco, Jifeng Xuan, Daniel Le Berre, and Martin Monperrus. 2014. Automatic repair of buggy if conditions and missing preconditions with SMT. In 6th International Workshop on Constraints in Software Testing, Verification, and Analysis, CSTVA 2014. Google ScholarDigital Library
- Brian Demsky, Michael D. Ernst, Philip J. Guo, Stephen McCamant, Jeff H. Perkins, and Martin C. Rinard. 2006. Inference and enforcement of data structure consistency specifications. In International Symposium on Software Testing and Analysis, ISSTA 2006. 233--244. Google ScholarDigital Library
- Edit Distance 2017. (2017). https://en.wikipedia.org/wiki/Edit_distance Accessed: 07-30-2017.Google Scholar
- Joel Galenson, Philip Reames, Rastislav Bodík, Björn Hartmann, and Koushik Sen. 2014. CodeHint: dynamic and interactive synthesis of code snippets. In 36th International Conference on Software Engineering, ICSE 2014. 653--663. Google ScholarDigital Library
- Divya Gopinath, Muhammad Zubair Malik, and Sarfraz Khurshid. 2011. Specification-Based Program Repair Using SAT. In Tools and Algorithms for the Construction and Analysis of Systems - 17th International Conference, TACAS 2011. 173--188. Google ScholarDigital Library
- Jinru Hua and Sarfraz Khurshid. 2016. A Sketching-Based Approach for Debugging Using Test Cases. In Automated Technology for Verification and Analysis -14th International Symposium, ATVA 2016. 463--478.Google Scholar
- Jinru Hua and Sarfraz Khurshid. 2017. EdSketch: execution-driven sketching for Java. In Proceedings of the 24th ACM SIGSOFT International SPIN Symposium on Model Checking of Software, Santa Barbara, CA, USA, July 10--14, 2017. 162--171. Google ScholarDigital Library
- Java programming language agents 2017. (2017). https://docs.oracle.com/javase/7/docs/api/java/lang/instrument/package-summary.html Accessed: 07-30-2017.Google Scholar
- JavaParser Transformation Tool 2017. http://javaparser.org. (2017). Accessed: 2017-07-30.Google Scholar
- Jinseong Jeon, Xiaokang Qiu, Jeffrey S. Foster, and Armando Solar-Lezama. 2015. JSketch: sketching for Java. In 23th ACM SIGSOFT International Symposium on Foundations of Software Engineering, ESEC/FSE 2015. 934--937. Google ScholarDigital Library
- JFreeChart Project 2017. (2017). http://www.jfree.org/jfreechart/ Accessed: 07-30-2017.Google Scholar
- Susmit Jha, Sumit Gulwani, Sanjit A. Seshia, and Ashish Tiwari. 2010. Oracle-guided component-based program synthesis. In 32th International Conference on Software Engineering, ICSE 2010. 215--224. Google ScholarDigital Library
- Frolin S. Ocariza Jr., Karthik Pattabiraman, and Ali Mesbah. 2014. Vejovis: suggesting fixes for JavaScript faults. In 36th International Conference on Software Engineering, ICSE '14, Hyderabad, India - May 31 - June 07, 2014. 837--847. Google ScholarDigital Library
- René Just, Darioush Jalali, and Michael D. Ernst. 2014. Defects4J: a database of existing faults toenable controlled testing studies for Java programs. In International Symposium on Software Testing and Analysis, ISSTA 2014. 437--440. Google ScholarDigital Library
- Yalin Ke, Kathryn T. Stolee, Claire Le Goues, and Yuriy Brun. 2015. Repairing Programs with Semantic Code Search. In 30th IEEE/ACM International Conference on Automated Software Engineering, ASE 2015, Lincoln, NE, USA, November 9--13, 2015. 295--306.Google Scholar
- Dongsun Kim, Jaechang Nam, Jaewoo Song, and Sunghun Kim. 2013. Automatic patch generation learned from human-written patches. In 35th International Conference on Software Engineering, ICSE 2013. 802--811. Google ScholarDigital Library
- Etienne Kneuss, Manos Koukoutos, and Viktor Kuncak. 2015. Deductive Program Repair. In Computer Aided Verification - 25th International Conference, CAV.Google Scholar
- Xuan-Bach D. Le, Duc-Hiep Chu, David Lo, Claire Le Goues, and Willem Visser. 2017. S3: syntax- and semantic-guided repair synthesis via programming by examples. In Proceedings of the 2017 11th Joint Meeting on Foundations of Software Engineering, ESEC/FSE 2017, Paderborn, Germany, September 4--8, 2017. 593--604. Google ScholarDigital Library
- Xuan-Bach D. Le, David Lo, and Claire Le Goues. 2016. History Driven Program Repair. In IEEE 23rd International Conference on Software Analysis, Evolution, and Reengineering, SANER 2016, Suita, Osaka, Japan, March 14--18, 2016 - Volume 1. 213--224.Google Scholar
- Claire Le Goues, Stephanie Forrest, and Westley Weimer. 2013. Current challenges in automatic software repair. Software Quality Journal 21, 3 (2013), 421--443. Google ScholarDigital Library
- Chen Liu, Jinqiu Yang, Lin Tan, and Munawar Hafiz. 2013. R2Fix: Automatically Generating Bug Fixes from Bug Reports. In Sixth IEEE International Conference on Software Testing, Verification and Validation, ICST 2013, Luxembourg, Luxembourg, March 18--22, 2013. 282--291. Google ScholarDigital Library
- Fan Long, Peter Amidon, and Martin Rinard. 2017. Automatic inference of code transforms for patch generation. In Proceedings of the 2017 11th Joint Meeting on Foundations of Software Engineering, ESEC/FSE 2017, Paderborn, Germany, September 4--8, 2017. 727--739. Google ScholarDigital Library
- Fan Long and Martin Rinard. 2015. Staged program repair with condition synthesis. In Proceedings of the 23th ACM SIGSOFT International Symposium on Foundations of Software Engineering, ESEC/FSE 2015. 166--178. Google ScholarDigital Library
- Fan Long and Martin Rinard. 2016. Automatic patch generation by learning correct code. In 43rd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2016. 298--312. Google ScholarDigital Library
- Fan Long and Martin C. Rinard. 2016. An analysis of the search spaces for generate and validate patch generation systems. In Proceedings of the 38th International Conference on Software Engineering, ICSE 2016, Austin, TX, USA, May 14--22, 2016. 702--713. Google ScholarDigital Library
- Sonal Mahajan, Abdulmajeed Alameer, Phil McMinn, and William G. J. Halfond. 2017. Automated repair of layout cross browser issues using search-based techniques. In Proceedings of the 26th ACM SIGSOFT International Symposium on Software Testing and Analysis, Santa Barbara, CA, USA, July 10- 14,2017. 249--260. Google ScholarDigital Library
- Matias Martinez, Thomas Durieux, Romain Sommerard, Jifeng Xuan, and Martin Monperrus. 2017. Automatic repair of real bugs in java: a large-scale experiment on the defects4j dataset. Empirical Software Engineering 22, 4 (2017), 1936--1964. 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
- Matias Martinez and Martin Monperrus. 2016. ASTOR: a program repair library for Java (demo). In International Symposium on Software Testing and Analysis, ISSTA 2016. 441--444. Google ScholarDigital Library
- Sergey Mechtaev, Jooyong Yi, and Abhik Roychoudhury. 2015. DirectFix: Looking for Simple Program Repairs. In 37th International Conference on Software Engineering, ICSE 2015. 448--458. Google ScholarDigital Library
- Sergey Mechtaev, Jooyong Yi, and Abhik Roychoudhury. 2016. Angelix: Scalable Multiline Program Patch Synthesis via Symbolic Analysis. In 38th International Conference on Software Engineering, ICSE 2016. Google ScholarDigital Library
- Benjamin Mehne, Hiroaki Yoshida, Mukul Prasad, Koushik Sen, Divya Gopinath, and Sarfraz Khurshid. 2018. Accelerating Search-based Program Repair. In 11th IEEE Conference on Software Testing, Validation and Verification (ICST). To appear.Google Scholar
- Martin Monperrus. 2014. A critical review of "automatic patch generation learned from human-written patches": essay on the problem statement and the evaluation of automatic software repair. In 36th International Conference on Software Engineering, ICSE 2014. 234--242. Google ScholarDigital Library
- Hoang Duong Thien Nguyen, Dawei Qi, Abhik Roychoudhury, and Satish Chandra. 2013. SemFix: program repair via semantic analysis. In 35th International Conference on Software Engineering, ICSE 2013. 772--781. Google ScholarDigital Library
- Daniel Perelman, Sumit Gulwani, Dan Grossman, and Peter Provost. 2014. Test-driven synthesis. In ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2014. 43. Google ScholarDigital Library
- Jeff H. Perkins, Sunghun Kim, Samuel Larsen, Saman P. Amarasinghe, Jonathan Bachrach, Michael Carbin, Carlos Pacheco, Frank Sherwood, Stelios Sidiroglou, Greg Sullivan, Weng-Fai Wong, Yoav Zibin, Michael D. Ernst, and Martin C. Rinard. 2009. Automatically patching errors in deployed software. In Proceedings of the 22nd ACM Symposium on Operating Systems Principles 2009, SOSP 2009, Big Sky, Montana, USA, October 11--14, 2009. 87--102. 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 36th International Conference on Software Engineering, ICSE '14. 254--265. Google ScholarDigital Library
- Zichao Qi, Fan Long, Sara Achour, and Martin C. Rinard. 2015. An analysis of patch plausibility and correctness for generate-and-validate patch generation systems. In International Symposium on Software Testing and Analysis, ISSTA 2015. 24--36. Google ScholarDigital Library
- Hesam Samimi, Max Schäfer, Shay Artzi, Todd D. Millstein, Frank Tip, and Laurie J. Hendren. 2012. Automated repair of HTML generation errors in PHP applications using string constraint solving. In 34th International Conference on Software Engineering, ICSE 2012, June 2--9, 2012, Zurich, Switzerland. 277--287. 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 Proceedings of the 36th ACM SIGPLAN Conference on Programming Language Design and Implementation, Portland, OR, USA, June 15--17, 2015. 43--54. Google ScholarDigital Library
- Rishabh Singh, Sumit Gulwani, and Armando Solar-Lezama. 2013. Automated feedback generation for introductory programming assignments. In ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2013. 15--26. Google ScholarDigital Library
- Rishabh Singh and Armando Solar-Lezama. 2011. Synthesizing data structure manipulations from storyboards. In 19th ACM SIGSOFT International Symposium on Foundations of Software Engineering, FSE 2011. 289--299. Google ScholarDigital Library
- Edward K. Smith, Earl T. Barr, Claire Le Goues, and Yuriy Brun. 2015. Is the cure worse than the disease? overfitting in automated program repair. In 23th ACM SIGSOFT International Symposium on Foundations of Software Engineering, ESEC/FSE 2015. 532--543. Google ScholarDigital Library
- Armando Solar-Lezama. 2013. Program sketching. STTT 15, 5--6 (2013), 475--495. Google ScholarDigital Library
- Saurabh Srivastava, Sumit Gulwani, and Jeffrey S. Foster. 2010. From program verification to program synthesis. In 37th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2010. 313--326. Google ScholarDigital Library
- Friedrich Steimann, Marcus Frenkel, and Rui Abreu. 2013. Threats to the validity and value of empirical assessments of the accuracy of coverage-based fault locators. In International Symposium on Software Testing and Analysis, ISSTA 2013. 314--324. Google ScholarDigital Library
- Shin Hwei Tan, Hiroaki Yoshida, Mukul R. Prasad, and Abhik Roychoudhury. 2016. Anti-patterns in search-based program repair. In Proceedings of the 24th ACM SIGSOFT International Symposium on Foundations of Software Engineering, FSE 2016, Seattle, WA, USA, November 13--18, 2016. 727--738. Google ScholarDigital Library
- Yi Wei, Yu Pei, Carlo A. Furia, Lucas Serpa Silva, Stefan Buchholz, Bertrand Meyer, and Andreas Zeller. 2010. Automated fixing of programs with contracts. In International Symposium on Software Testing and Analysis, ISSTA 2010. 61--72. Google ScholarDigital Library
- Westley Weimer, Zachary P. Fry, and Stephanie Forrest. 2013. Leveraging program equivalence for adaptive program repair: Models and first results. In 28th IEEE/ACM International Conference on Automated Software Engineering, ASE 2013. 356--366. Google ScholarDigital Library
- Westley Weimer, ThanhVu Nguyen, Claire Le Goues, and Stephanie Forrest. 2009. Automatically finding patches using genetic programming. In 31st International Conference on Software Engineering, ICSE 2009, May 16--24, 2009, Vancouver, Canada, Proceedings. 364--374. Google ScholarDigital Library
- Qi Xin and Steven P. Reiss. 2017. Identifying test-suite-overfitted patches through test case generation. In Proceedings of the 26th ACM SIGSOFT International Symposium on Software Testing and Analysis, Santa Barbara, CA, USA, July 10 - 14, 2017. 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 Proceedings of the 39th International Conference on Software Engineering, ICSE 2017, Buenos Aires, Argentina, May 20--28, 2017. 416--426. Google ScholarDigital Library
- Jifeng Xuan and Martin Monperrus. 2014. Learning to Combine Multiple Ranking Metrics for Fault Localization. In IEEE International Conference on Software Maintenance and Evolution, ICSME 2014. 191--200. Google ScholarDigital Library
- Zijiang Yang, Jinru Hua, Kaiyuan Wang, and Sarfraz Khurshid. 2018. Test-Execution-Driven Sketching for Complex APIs. In 11th IEEE Conference on Software Testing, Validation and Verification (ICST). To appear.Google Scholar
- Jooyong Yi, Umair Z. Ahmed, Amey Karkare, Shin Hwei Tan, and Abhik Roychoudhury. 2017. A feasibility study of using automated program repair for introductory programming assignments. In Proceedings of the 2017 11th Joint Meeting on Foundations of Software Engineering, ESEC/FSE 2017, Paderborn, Germany, September 4--8, 2017. 740--751. Google ScholarDigital Library
Index Terms
- Towards practical program repair with on-demand candidate generation
Recommendations
SketchFix: a tool for automated program repair approach using lazy candidate generation
ESEC/FSE 2018: Proceedings of the 2018 26th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software EngineeringManually locating and removing bugs in faulty program is often tedious and error-prone. A common automated program repair approach called generate-and-validate (G&V) iteratively creates candidate fixes, compiles them, and runs these candidates against ...
An effective candidate generation method for improving performance of edit similarity query processing
In this paper, we study edit similarity query processing to find strings similar to a query string from a collection of strings. To solve the problem, many algorithms have been proposed under a filter-and-verification framework, where candidate strings ...
Leveraging program equivalence for adaptive program repair: models and first results
ASE '13: Proceedings of the 28th IEEE/ACM International Conference on Automated Software EngineeringSoftware bugs remain a compelling problem. Automated program repair is a promising approach for reducing cost, and many methods have recently demonstrated positive results. However, success on any particular bug is variable, as is the cost to find a ...
Comments