skip to main content
10.1145/3453483.3454051acmconferencesArticle/Chapter ViewAbstractPublication PagespldiConference Proceedingsconference-collections
research-article
Open access

Concolic program repair

Published: 18 June 2021 Publication History

Abstract

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 (breaking untested but desired functionality). We propose an integrated approach for detecting and discarding overfitting patches via systematic co-exploration of the patch space and input space. We leverage concolic path exploration to systematically traverse the input space (and generate inputs), while 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. 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. We evaluated our approach for fixing real-world software vulnerabilities and defects, for fixing functionality errors in programs drawn from SV-COMP benchmarks used in software verification, as well as for test-suite guided repair. In our experiments, we observed a patch space reduction due to our concolic exploration of up to 74% for fixing software vulnerabilities and up to 63% for SV-COMP programs. Our technique presents the viewpoint of gradual correctness - repair run over longer time leads to less overfitting fixes.

References

[1]
Rajeev Alur, Rishabh Singh, Dana Fisman, and Armando Solar-Lezama. 2018. Search-Based Program Synthesis. Commun. ACM, 61, 12 (2018), Nov., 84–93. issn:0001-0782 https://doi.org/10.1145/3208071
[2]
Johannes Bader, Andrew Scott, Michael Pradel, and Satish Chandra. 2019. Getafix: learning to fix bugs automatically. Proc. ACM Program. Lang., 3, OOPSLA (2019), 159:1–159:27. https://doi.org/10.1145/3360585
[3]
Marcel Böhme, Van-Thuan Pham, Manh-Dung Nguyen, and Abhik Roychoudhury. 2017. Directed Greybox Fuzzing. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security (CCS ’17). Association for Computing Machinery, New York, NY, USA. 2329–2344. isbn:9781450349468 https://doi.org/10.1145/3133956.3134020
[4]
Cristian Cadar, Daniel Dunbar, and Dawson Engler. 2008. KLEE: Unassisted and Automatic Generation of High-Coverage Tests for Complex Systems Programs. In Proceedings of the 8th USENIX Conference on Operating Systems Design and Implementation (OSDI’08). USENIX Association, USA. 209–224.
[5]
Supratik Chakraborty, Kuldeep S. Meel, and Moshe Y. Vardi. 2013. A Scalable Approximate Model Counter. In Principles and Practice of Constraint Programming - 19th International Conference, CP 2013, Uppsala, Sweden, September 16-20, 2013. Proceedings, Christian Schulte (Ed.) (Lecture Notes in Computer Science, Vol. 8124). Springer, 200–216. https://doi.org/10.1007/978-3-642-40627-0_18
[6]
Hadar Frenkel, Orna Grumberg, Corina Pasareanu, and Sarai Sheinvald. 2020. Assume, Guarantee or Repair. In Tools and Algorithms for the Construction and Analysis of Systems, Armin Biere and David Parker (Eds.). Springer International Publishing, Cham. 211–227. isbn:978-3-030-45190-5 https://doi.org/10.1007/978-3-030-45190-5_12
[7]
Xiang Gao, Sergey Mechtaev, and Abhik Roychoudhury. 2019. Crash-Avoiding Program Repair. In Proceedings of the 28th ACM SIGSOFT International Symposium on Software Testing and Analysis (ISSTA) (ISSTA 2019). Association for Computing Machinery, New York, NY, USA. 8–18. isbn:9781450362245 https://doi.org/10.1145/3293882.3330558
[8]
Xiang Gao, Bo Wang, Gregory J. Duck, Ruyi Ji, Yingfei Xiong, and Abhik Roychoudhury. 2021. Beyond Tests: Program Vulnerability Repair via Crash Constraint Extraction. ACM Trans. Softw. Eng. Methodol., 30, 2 (2021), Article 14, Feb., 27 pages. issn:1049-331X https://doi.org/10.1145/3418461
[9]
Patrice Godefroid, Nils Klarlund, and Koushik Sen. 2005. DART: Directed Automated Random Testing. In Proceedings of the 2005 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI) (PLDI ’05). Association for Computing Machinery, New York, NY, USA. 213–223. isbn:1595930566 https://doi.org/10.1145/1065010.1065036
[10]
Patrice Godefroid, Michael Y Levin, and David Molnar. 2012. SAGE: Whitebox Fuzzing for Security Testing. Commun. ACM, 55, 3 (2012), mar, 40–44. issn:0001-0782 https://doi.org/10.1145/2093548.2093564
[11]
Carla P. Gomes, Ashish Sabharwal, and Bart Selman. 2009. Model Counting. In Handbook of Satisfiability, Armin Biere, Marijn Heule, Hans van Maaren, and Toby Walsh (Eds.) (Frontiers in Artificial Intelligence and Applications, Vol. 185). IOS Press, 633–654. https://doi.org/10.3233/978-1-58603-929-5-633
[12]
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 (TACAS), Parosh Aziz Abdulla and K. Rustan M. Leino (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg. 173–188. isbn:978-3-642-19835-9
[13]
Claire Le Goues, Neal Holtschulte, Edward K. Smith, Yuriy Brun, Premkumar T. Devanbu, Stephanie Forrest, and Westley Weimer. 2015. The ManyBugs and IntroClass Benchmarks for Automated Repair of C Programs. IEEE Trans. Software Eng., 41, 12 (2015), 1236–1256. https://doi.org/10.1109/TSE.2015.2454513
[14]
Claire Le Goues, Michael Pradel, and Abhik Roychoudhury. 2019. Automated Program Repair. Commun. ACM, 62, 12 (2019), Nov., 56–65. issn:0001-0782 https://doi.org/10.1145/3318162
[15]
Zhen Huang, David Lie, Gang Tan, and Trent Jaeger. 2019. Using Safety Properties to Generate Vulnerability Patches. In 2019 IEEE Symposium on Security and Privacy (SP). 539–554. https://doi.org/10.1109/SP.2019.00071
[16]
James C. King. 1976. Symbolic Execution and Program Testing. Commun. ACM, 19, 7 (1976), July, 385–394. issn:0001-0782 https://doi.org/10.1145/360248.360252
[17]
Robert Könighofer and Roderick Bloem. 2013. Repair with On-The-Fly Program Analysis. In Hardware and Software: Verification and Testing, Armin Biere, Amir Nahir, and Tanja Vos (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg. 56–71. isbn:978-3-642-39611-3
[18]
Claire Le Goues, ThanhVu Nguyen, Stephanie Forrest, and Westley Weimer. 2012. GenProg: A Generic Method for Automatic Software Repair. IEEE Transactions on Software Engineering, 38, 1 (2012), 54–72. https://doi.org/10.1109/TSE.2011.104
[19]
Francesco Logozzo and Thomas Ball. 2012. Modular and Verified Automatic Program Repair. In Proceedings of the ACM International Conference on Object Oriented Programming Systems Languages and Applications (OOPSLA ’12). Association for Computing Machinery, New York, NY, USA. 133–146. isbn:9781450315616 https://doi.org/10.1145/2384616.2384626
[20]
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). Association for Computing Machinery, New York, NY, USA. 727–739. isbn:9781450351058 https://doi.org/10.1145/3106237.3106253
[21]
Fan Long and Martin Rinard. 2016. Automatic Patch Generation by Learning Correct Code. In Proceedings of the 43rd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL) (POPL ’16). Association for Computing Machinery, New York, NY, USA. 298–312. isbn:9781450335492 https://doi.org/10.1145/2837614.2837617
[22]
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, Laura K. Dillon, Willem Visser, and Laurie A. Williams (Eds.). ACM, 702–713. https://doi.org/10.1145/2884781.2884872
[23]
Sergey Mechtaev, Jooyong Yi, and Abhik Roychoudhury. 2016. Angelix: Scalable Multiline Program Patch Synthesis via Symbolic Analysis. In Proceedings of the 38th International Conference on Software Engineering (ICSE ’16). Association for Computing Machinery, New York, NY, USA. 691–701. isbn:9781450339001 https://doi.org/10.1145/2884781.2884807
[24]
Martin Monperrus. 2018. Automatic Software Repair: A Bibliography. ACM Comput. Surv., 51, 1 (2018), Article 17, Jan., 24 pages. issn:0360-0300 https://doi.org/10.1145/3105906
[25]
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 ’13, San Francisco, CA, USA, May 18-26, 2013, David Notkin, Betty H. C. Cheng, and Klaus Pohl (Eds.). IEEE Computer Society, 772–781. https://doi.org/10.1109/ICSE.2013.6606623
[26]
Zichao Qi, Fan Long, Sara Achour, and Martin Rinard. 2015. An Analysis of Patch Plausibility and Correctness for Generate-and-Validate Patch Generation Systems. In Proceedings of the 2015 International Symposium on Software Testing and Analysis (ISSTA 2015). ACM, New York, NY, USA. 24–36. isbn:9781450336208 https://doi.org/10.1145/2771783.2771791
[27]
Georgios Sakkas, Madeline Endres, Benjamin Cosman, Westley Weimer, and Ranjit Jhala. 2020. Type error feedback via analytic program repair. In Proceedings of the 41st ACM SIGPLAN International Conference on Programming Language Design and Implementation, PLDI 2020, London, UK, June 15-20, 2020, Alastair F. Donaldson and Emina Torlak (Eds.). ACM, 16–30. https://doi.org/10.1145/3385412.3386005
[28]
Stelios Sidiroglou-Douskos, Eric Lahtinen, Fan Long, and Martin Rinard. 2015. Automatic Error Elimination by Horizontal Code Transfer across Multiple Applications. SIGPLAN Not., 50, 6 (2015), June, 43–54. issn:0362-1340 https://doi.org/10.1145/2813885.2737988
[29]
Stelios Sidiroglou-Douskos, Eric Lahtinen, and Martin Rinard. 2015. Automatic Discovery and Patching of Buffer and Integer Overflow Errors. Massachusetts Institute of Technology, Cambridge, MA, USA. http://hdl.handle.net/1721.1/97087
[30]
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 Proceedings of the 2015 10th Joint Meeting on Foundations of Software Engineering, ESEC/FSE 2015, Bergamo, Italy, August 30 - September 4, 2015, Elisabetta Di Nitto, Mark Harman, and Patrick Heymans (Eds.). ACM, 532–543. https://doi.org/10.1145/2786805.2786825
[31]
Armando Solar-Lezama. 2008. Program Synthesis by Sketching. Ph.D. Dissertation. EECS Department, University of California, Berkeley.
[32]
Armando Solar-Lezama, Liviu Tancau, Rastislav Bodik, Sanjit Seshia, and Vijay Saraswat. 2006. Combinatorial sketching for finite programs. In International Conference on Architectural Support for Programming Languages and Operating Systems - ASPLOS. isbn:1595934510 issn:0163-5964 https://doi.org/10.1145/1168857.1168907
[33]
SV-COMP Website. 2020. International Competition on Software Verification (SV-COMP). https://sv-comp.sosy-lab.org/

Cited By

View all
  • (2024)Patch Correctness Assessment: A SurveyACM Transactions on Software Engineering and Methodology10.1145/370297234:2(1-50)Online publication date: 8-Nov-2024
  • (2024)PyDex: Repairing Bugs in Introductory Python Assignments using LLMsProceedings of the ACM on Programming Languages10.1145/36498508:OOPSLA1(1100-1124)Online publication date: 29-Apr-2024
  • (2024)Combining Structured Static Code Information and Dynamic Symbolic Traces for Software Vulnerability PredictionProceedings of the IEEE/ACM 46th International Conference on Software Engineering10.1145/3597503.3639212(1-13)Online publication date: 20-May-2024
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
PLDI 2021: Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation
June 2021
1341 pages
ISBN:9781450383912
DOI:10.1145/3453483
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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 18 June 2021

Permissions

Request permissions for this article.

Check for updates

Badges

Author Tags

  1. patch overfitting
  2. program repair
  3. program synthesis
  4. symbolic execution

Qualifiers

  • Research-article

Funding Sources

Conference

PLDI '21
Sponsor:

Acceptance Rates

Overall Acceptance Rate 406 of 2,067 submissions, 20%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)302
  • Downloads (Last 6 weeks)30
Reflects downloads up to 24 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2024)Patch Correctness Assessment: A SurveyACM Transactions on Software Engineering and Methodology10.1145/370297234:2(1-50)Online publication date: 8-Nov-2024
  • (2024)PyDex: Repairing Bugs in Introductory Python Assignments using LLMsProceedings of the ACM on Programming Languages10.1145/36498508:OOPSLA1(1100-1124)Online publication date: 29-Apr-2024
  • (2024)Combining Structured Static Code Information and Dynamic Symbolic Traces for Software Vulnerability PredictionProceedings of the IEEE/ACM 46th International Conference on Software Engineering10.1145/3597503.3639212(1-13)Online publication date: 20-May-2024
  • (2024)Evolutionary Testing for Program Repair2024 IEEE Conference on Software Testing, Verification and Validation (ICST)10.1109/ICST60714.2024.00058(105-116)Online publication date: 27-May-2024
  • (2024)Enhanced automated code vulnerability repair using large language modelsEngineering Applications of Artificial Intelligence10.1016/j.engappai.2024.109291138:PAOnline publication date: 1-Dec-2024
  • (2024)When debugging encounters artificial intelligence: state of the art and open challengesScience China Information Sciences10.1007/s11432-022-3803-967:4Online publication date: 21-Feb-2024
  • (2023)Poracle: Testing Patches under Preservation Conditions to Combat the Overfitting Problem of Program RepairACM Transactions on Software Engineering and Methodology10.1145/362529333:2(1-39)Online publication date: 26-Sep-2023
  • (2023)Symbolic encoding of LL(1) parsing and its applicationsFormal Methods in System Design10.1007/s10703-023-00420-361:2-3(338-379)Online publication date: 22-Jun-2023
  • (2023)Enhanced evolutionary automated program repair by finer‐granularity ingredients and better search algorithmsJournal of Software: Evolution and Process10.1002/smr.262436:6Online publication date: 9-Oct-2023
  • (2022)Is this Change the Answer to that Problem?Proceedings of the 37th IEEE/ACM International Conference on Automated Software Engineering10.1145/3551349.3556914(1-13)Online publication date: 10-Oct-2022
  • Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media