skip to main content
10.1145/3180155.3180247acmconferencesArticle/Chapter ViewAbstractPublication PagesicseConference Proceedingsconference-collections
research-article

Semantic program repair using a reference implementation

Published:27 May 2018Publication History

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.

References

  1. 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 ScholarGoogle Scholar
  2. Earl T. Barr, Yuriy Brun, Premkumar T. Devanbu, Mark Harman, and Federica Sarro. 2014. The plastic surgery hypothesis. In FSE. ACM, 306--317. Google ScholarGoogle ScholarDigital LibraryDigital Library
  3. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  4. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  5. Satish Chandra, Emina Torlak, Shaon Barman, and Rastislav Bodík. 2011. Angelic debugging. In ICSE. 121--130. Google ScholarGoogle ScholarDigital LibraryDigital Library
  6. Leonardo De Moura and Nikolaj Bjørner. 2008. Z3: An Efficient SMT Solver. In TACAS. Springer-Verlag, Berlin, Heidelberg, 337--340. Google ScholarGoogle ScholarDigital LibraryDigital Library
  7. 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 ScholarGoogle Scholar
  8. 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 ScholarGoogle Scholar
  9. James A Jones, Mary Jean Harrold, and John Stasko. 2002. Visualization of test information to assist fault localization. In ICSE. ACM, 467--477. Google ScholarGoogle ScholarDigital LibraryDigital Library
  10. Ming Kawaguchi, Shuvendu Lahiri, and Henrique Rebelo. 2010. Conditional equivalence. Technical Report.Google ScholarGoogle Scholar
  11. 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 ScholarGoogle Scholar
  12. James C. King. 1976. Symbolic Execution and Program Testing. Commun. ACM 19, 7 (1976), 385--394. Google ScholarGoogle ScholarDigital LibraryDigital Library
  13. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  14. Shuvendu K. Lahiri, Rohit Sinha, and Chris Hawblitzel. 2015. Automatic Rootcausing for Program Equivalence Failures in Binaries. In CAV. 362--379.Google ScholarGoogle Scholar
  15. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  16. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  17. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  18. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  19. Rainer Leupers. 2013. Code optimization techniques for embedded processors: Methods, algorithms, and tools. Springer Science & Business Media. Google ScholarGoogle ScholarDigital LibraryDigital Library
  20. Qing Li, Tatuya Jinmei, and Keiichi Shima. 2010. IPv6 Core Protocols Implementation. Morgan Kaufmann. Google ScholarGoogle ScholarDigital LibraryDigital Library
  21. Fan Long and Martin Rinard. {n. d.}. Staged program repair with condition synthesis. In ESEC/FSE. ACM, 166--178. Google ScholarGoogle ScholarDigital LibraryDigital Library
  22. Fan Long and Martin Rinard. 2016. Automatic patch generation by learning correct code. In POPL. ACM, 298--312. Google ScholarGoogle ScholarDigital LibraryDigital Library
  23. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  24. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  25. Sergey Mechtaev, Jooyong Yi, and Abhik Roychoudhury. 2015. Directfix: Looking for simple program repairs. In ICSE. IEEE Press, 448--458. Google ScholarGoogle ScholarDigital LibraryDigital Library
  26. Sergey Mechtaev, Jooyong Yi, and Abhik Roychoudhury. 2016. Angelix: Scalable Multiline Program Patch Synthesis via Symbolic Analysis. In ICSE. 691--701. Google ScholarGoogle ScholarDigital LibraryDigital Library
  27. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  28. Suzette Person, Matthew B. Dwyer, Sebastian G. Elbaum, and Corina S. Pasareanu. 2008. Differential symbolic execution. In FSE. 226--237. Google ScholarGoogle ScholarDigital LibraryDigital Library
  29. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  30. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  31. Stelios Sidiroglou-Douskos, Eric Lahtinen, Anthony Eden, Fan Long, and Martin Rinard. 2017. CodeCarbonCopy. In ESEC/FSE. ACM, 95--105. Google ScholarGoogle ScholarDigital LibraryDigital Library
  32. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  33. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  34. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  35. Shin Hwei Tan and Abhik Roychoudhury. 2015. relifix: Automated repair of software regressions. In ICSE. IEEE Press, 471--482. Google ScholarGoogle ScholarDigital LibraryDigital Library
  36. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  37. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  38. Nikolai Tillmann and Wolfram Schulte. 2005. Parameterized unit tests. In ACM SIGSOFT Software Engineering Notes, Vol. 30. ACM, 253--262. Google ScholarGoogle ScholarDigital LibraryDigital Library
  39. Busybox Website. 2017. Busybox. https://busybox.net/. (2017).Google ScholarGoogle Scholar
  40. GNU Coreutils Website. 2017. GNU Coreutils. https://www.gnu.org/software/coreutils/coreutils.html. (2017).Google ScholarGoogle Scholar
  41. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  42. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  43. Qi Xin and Steven P Reiss. 2017. Identifying test-suite-overfitted patches through test case generation. In ISSTA. ACM, 226--236. Google ScholarGoogle ScholarDigital LibraryDigital Library
  44. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  45. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  46. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  47. 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 ScholarGoogle Scholar
  48. Andreas Zeller. 1999. Yesterday, My Program Worked. Today, It Does Not. Why?. In FSE. Springer-Verlag, London, UK, UK, 253--267. Google ScholarGoogle ScholarDigital LibraryDigital Library
  49. Tianyi Zhang and Miryung Kim. 2017. Automated transplantation and differential testing for clones. In ICSE. IEEE / ACM, 665--676. Google ScholarGoogle ScholarDigital LibraryDigital Library

Index Terms

  1. Semantic program repair using a reference implementation

      Recommendations

      Comments

      Login options

      Check if you have access through your login credentials or your institution to get full access on this article.

      Sign in
      • Published in

        cover image ACM Conferences
        ICSE '18: Proceedings of the 40th International Conference on Software Engineering
        May 2018
        1307 pages
        ISBN:9781450356381
        DOI:10.1145/3180155
        • Conference Chair:
        • Michel Chaudron,
        • General Chair:
        • Ivica Crnkovic,
        • Program Chairs:
        • Marsha Chechik,
        • Mark Harman

        Copyright © 2018 ACM

        Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

        Publisher

        Association for Computing Machinery

        New York, NY, United States

        Publication History

        • Published: 27 May 2018

        Permissions

        Request permissions about this article.

        Request Permissions

        Check for updates

        Qualifiers

        • research-article

        Acceptance Rates

        Overall Acceptance Rate276of1,856submissions,15%

        Upcoming Conference

        ICSE 2024

      PDF Format

      View or Download as a PDF file.

      PDF

      eReader

      View online with eReader.

      eReader