research-article

Debug-localize-repair: a symbiotic construction for heap manipulations

Authors:

Subhajit RoyAuthors Info & Claims

Formal Methods in System Design, Volume 58, Issue 3

Pages 399 - 439

https://doi.org/10.1007/s10703-021-00387-z

Published: 01 November 2021 Publication History

Abstract

We present Wolverine2, an integrated Debug-Localize-Repair environment for heap manipulating programs. Wolverine2 provides an interactive debugging environment: while concretely executing a program via on an interactive shell supporting common debugging facilities, Wolverine2 displays the abstract program states (as box-and-arrow diagrams) as a visual aid to the programmer, packages a novel, proof-directed repair algorithm to quickly synthesize the repair patches and a new bug localization algorithm to reduce the search space of repairs. Wolverine2 supports “hot-patching” of the generated patches to provide a seamless debugging environment, and also facilitates new debug-localize-repair possibilities: specification refinement and checkpoint-based hopping. We evaluate Wolverine2 on 6400 buggy programs (generated using automated fault injection) on a variety of data-structures like singly, doubly, and circular linked lists, AVL trees, Red-Black trees, Splay Trees and Binary Search Trees; Wolverine2 could repair all the buggy instances within realistic programmer wait-time (less than 5 s in most cases). Wolverine2 could also repair more than 80% of the 247 (buggy) student submissions where a reasonable attempt was made.

References

[1]

Abreu R, Zoeteweij P, Golsteijn R, and Van Gemund AJ A practical evaluation of spectrum-based fault localization J Syst Softw 2009 82 11 1780-1792

[2]

Ball T, Naik M, Rajamani SK (2003) From symptom to cause: localizing errors in counterexample traces. In: Proceedings of the 30th ACM SIGPLAN-SIGACT symposium on principles of programming languages, POPL ’03, New York, NY, USA. ACM

[3]

Bavishi R, Pandey A, Roy S (2016) Regression aware debugging for mobile applications. In: Mobile! 2016: proceedings of the 1st international workshop on mobile development (invited paper), Mobile! 2016, New York, NY, USA., pp 21–22 Association for Computing Machinery

[4]

Bavishi R, Pandey A, Roy S (2016) To be precise: regression aware debugging. In: Proceedings of the 2016 ACM SIGPLAN international conference on object-oriented programming, systems, languages, and applications, OOPSLA 2016, New York, NY, USA. ACM

[5]

Bendersky E. Pycparser: C parser in Python. https://pypi.python.org/pypi/pycparser. Accessed 24 Jan 2017

[6]

Bhatia S, Kohli P, Singh R (2018) Neuro-symbolic program corrector for introductory programming assignments. In: Proceedings of the 40th international conference on software engineering, ICSE ’18, New York, NY, USA. Association for Computing Machinery

[7]

Chandra S, Torlak E, Barman S, Bodik R (2011) Angelic debugging. In: Proceedings of the 33rd international conference on software engineering, ICSE ’11, New York, NY, USA. ACM

[8]

Chatterjee P, Chatterjee A, Campos J, Abreu R, Roy S (2020) Diagnosing software faults using multiverse analysis. In: Bessiere C (ed) Proceedings of the twenty-ninth international joint conference on artificial intelligence, IJCAI-20, vol 7. International Joint Conferences on Artificial Intelligence Organization, pp 1629–1635. Main track

[9]

Chatterjee P, Roy S, Diep BP, Lal A (2020) Distributed bounded model checking. In: FMCAD, July 2020

[10]

Das R, Ahmed UZ, Karkare A, Gulwani S (2016) Prutor: a system for tutoring CS1 and collecting student programs for analysis. CoRR, arXiv:1608.03828

[11]

De Moura L, Bjørner N (2008) Z3: an efficient SMT solver. In: Proceedings of the theory and practice of software, 14th international conference on tools and algorithms for the construction and analysis of systems, Berlin, Heidelberg. Springer-Verlag, pp 337–340

[12]

Demsky B, Rinard M (2003) Automatic detection and repair of errors in data structures. In: Proceedings of the 18th annual ACM SIGPLAN conference on object-oriented programing, systems, languages, and applications, OOPSLA ’03, New York, NY, USA. ACM

[13]

Elkarablieh B, Khurshid S (2008) Juzi: a tool for repairing complex data structures. In: Proceedings of the 30th international conference on software engineering, ICSE ’08, New York, NY, USA. ACM

[14]

Feser JK, Chaudhuri S, Dillig I (2015) Synthesizing data structure transformations from input–output examples. In: Proceedings of the 36th ACM SIGPLAN conference on programming language design and implementation, PLDI ’15, New York, NY, USA. ACM

[15]

Geeks for Geeks. Data structures. http://www.geeksforgeeks.org/data-structures/. Accessed 24 Jan 2017

[16]

Free Software Foundation. GDB Python API. https://sourceware.org/gdb/onlinedocs/gdb/Python-API.html. Accessed 25 Jan 2017

[17]

Free Software Foundation. GDB: the GNU project debugger. https://sourceware.org/gdb/. Accessed 24 Jan 2017

[18]

Garg A and Roy S Blazy S and Jensen T Synthesizing heap manipulations via integer linear programming Static analysis, SAS 2015. Proceedings 2015 Berlin Springer

[19]

Godefroid P, Klarlund N, Sen K (2005) DART: directed automated random testing. In: Proceedings of the 2005 ACM SIGPLAN conference on programming language design and implementation, PLDI ’05, New York, NY, USA. ACM

[20]

Golia P, Roy S, and Meel KS Lahiri SK and Wang C Manthan: a data-driven approach for Boolean function synthesis Computer aided verification (CAV) 2020 Cham Springer 611-633

[21]

Golia P, Roy S, Slivovsky F, Meel KS (2021) Engineering an efficient Boolean functional synthesis engine. In: ICCAD

[22]

Groce A, Chaki S, Kroening D, and Strichman O Error explanation with distance metrics Int J Softw Tools Technol Transf 2006 8 3 229-247

[23]

Grumberg O, Lerda F, Strichman O, Theobald M (2005) Proof-guided underapproximation-widening for multi-process systems. In: Proceedings of the 32Nd ACM SIGPLAN-SIGACT symposium on principles of programming languages, POPL ’05, New York, NY, USA. ACM

[24]

Gulwani S, Radiček I, Zuleger F (2018) Automated clustering and program repair for introductory programming assignments. In: Proceedings of the 39th ACM SIGPLAN conference on programming language design and implementation, PLDI 2018, New York, NY, USA. Association for Computing Machinery, pp 465–480

[25]

Guo PJ (2013) Online python tutor: embeddable web-based program visualization for CS education. In: Proceeding of the 44th ACM technical symposium on computer science education, SIGCSE ’13, New York, NY, USA. ACM

[26]

Gupta R, Pal S, Kanade A, Shevade S (2017) Deepfix: fixing common C language errors by deep learning. In: Proceedings of the Thirty-First AAAI conference on artificial intelligence, AAAI’17. AAAI Press, pp 1345–1351

[27]

Hoare CAR An axiomatic basis for computer programming Commun ACM 1969 12 10 576-580

[28]

Hu Q, Samanta R, Singh R, and D’Antoni L Chang BY Direct manipulation for imperative programs Static analysis 2019 Cham Springer 347-367

[29]

Hu Y, Ahmed UZ, Mechtaev S, Leong B, Roychoudhury A (2019) Re-factoring based program repair applied to programming assignments. In: ASE ’19. IEEE Press, pp 388–398

[30]

igraph—the network analysis package. http://igraph.org/python/. Accessed 24 Jan 2017

[31]

Jha S, Gulwani S, Seshia SA, Tiwari A (2010) Oracle-guided component-based program synthesis. In: Proceedings of the 32Nd ACM/IEEE international conference on software engineering, ICSE ’10, New York, NY, USA, vol 1. ACM

[32]

Jones JA, Harrold MJ (2005) Empirical evaluation of the tarantula automatic fault-localization technique. In: Proceedings of the 20th IEEE/ACM international conference on automated software engineering, ASE ’05, New York, NY, USA. ACM

[33]

Jose M, Majumdar R (2011) Bug-assist: assisting fault localization in ANSI-C programs. In: Proceedings of the 23rd international conference on computer aided verification, CAV’11, Berlin, Heidelberg. Springer-Verlag

[34]

Jose M, Majumdar R (2011) Cause clue clauses: error localization using maximum satisfiability. In: Proceedings of the 32nd ACM SIGPLAN conference on programming language design and implementation, PLDI ’11, New York, NY, USA. ACM

[35]

Kneuss E, Koukoutos M, Kuncak V (2015) Deductive program repair. In: CAV

[36]

Le Goues C, Nguyen T, Forrest S, and Weimer W GenProg: a generic method for automatic software repair IEEE Trans Softw Eng 2012 38 54-72

[37]

Leung A, Sarracino J, and Lerner S Interactive parser synthesis by example SIGPLAN Not 2015 50 6 565-574

[38]

Liblit B, Naik M, Zheng AX, Aiken A, Jordan MI (2005) Scalable statistical bug isolation. In: Proceedings of the 2005 ACM SIGPLAN conference on programming language design and implementation, PLDI ’05, New York, NY, USA. ACM

[39]

Liu C, Yan X, Fei L, Han J, Midkiff SP (2005) SOBER: statistical model-based bug localization. In: ESEC/FSE-13, New York, NY, USA. ACM

[40]

Liu Y, Li B (2010) Automated program debugging via multiple predicate switching. In: Proceedings of the twenty-fourth AAAI conference on artificial intelligence, AAAI’10. AAAI Press

[41]

Loncaric C, Ernst MD, Torlak E (2018) Generalized data structure synthesis. In: Proceedings of the 40th international conference on software engineering, ICSE ’18, New York, NY, USA. Association for Computing Machinery, pp 958–968

[42]

Long F, Rinard M (2016) Automatic patch generation by learning correct code. In: Proceedings of the 43rd annual ACM SIGPLAN-SIGACT symposium on principles of programming languages, POPL ’16, New York, NY, USA. ACM

[43]

Malik MZ, Siddiqui JH, Khurshid S (2011) Constraint-based program debugging using data structure repair. In: 2011 fourth IEEE international conference on software testing, verification and validation, March 2011

[44]

Malik MZ, Ghori K, Elkarablieh B, Khurshid S (2009) A case for automated debugging using data structure repair. In: Proceedings of the 2009 IEEE/ACM international conference on automated software engineering, ASE ’09, USA. IEEE Computer Society

[45]

Mechtaev S, Yi J, Roychoudhury A (2015) DirectFix: looking for simple program repairs. In: Proceedings of the 37th international conference on software engineering, ICSE ’15, Piscataway, NJ, USA, vol 1, pp 448–458

[46]

Mechtaev S, Yi J, Roychoudhury A (2016) Angelix: scalable multiline program patch synthesis via symbolic analysis. In: Proceedings of the 38th international conference on software engineering, ICSE ’16, New York, NY, USA. ACM

[47]

Modi V, Roy S, Aggarwal SK (2013) Exploring program phases for statistical bug localization. In: Proceedings of the 11th ACM SIGPLAN-SIGSOFT workshop on program analysis for software tools and engineering, PASTE ’13, New York, NY, USA. ACM

[48]

Nguyen HD, Qi D, Roychoudhury A, Chandra S (2013) SemFix: program repair via semantic analysis. In: Proceedings of the 2013 international conference on software engineering, ICSE ’13, Piscataway, NJ, USA. IEEE Press

[49]

Nguyen T-T, Ta Q-T, Chin W-N (2019) Automatic program repair using formal verification and expression templates. In: VMCAI

[50]

Nguyen T, Weimer W, Le Goues C, Forrest S (2009) Using execution paths to evolve software patches. In: International conference on software testing, verification and validation workshops, 2009. ICSTW’09. IEEE, pp 152–153

[51]

Pandey A, Kotcharlakota PR, Roy S (2019) Deferred concretization in symbolic execution via fuzzing. In: Proceedings of the 28th ACM SIGSOFT international symposium on software testing and analysis, ISSTA 2019, New York, NY, USA. Association for Computing Machinery, pp 228–238

[52]

Pham V-T, Khurana S, Roy S, and Roychoudhury A Huisman M and Rubin J Bucketing failing tests via symbolic analysis Fundamental approaches to software engineering 2017 Berlin Springer 43-59

[53]

Polikarpova N and Sergey I Structuring the synthesis of heap-manipulating programs Proc ACM Program Lang 2019 3 1-30

[54]

Pu Y, Narasimhan K, Solar-Lezama A, Barzilay R (2016) Sk_p: a neural program corrector for moocs. In: Companion proceedings of the 2016 ACM SIGPLAN international conference on systems, programming, languages and applications: software for humanity, SPLASH Companion 2016, page 39-40, New York, NY, USA. Association for Computing Machinery

[55]

Rolim R, Soares G, D’Antoni L, Polozov O, Gulwani S, Gheyi R, Suzuki R, Hartmann B (2017) Learning syntactic program transformations from examples. In: Proceedings of the 39th international conference on software engineering, ICSE ’17. IEEE Press

[56]

Roy S, Hsu J, Albarghouthi A (2021) Learning differentially private mechanisms. In: 2021 IEEE symposium on security and privacy (SP), Los Alamitos, CA, USA, May 2021. IEEE Computer Society, pp 852–865

[57]

Roy S (2013) From concrete examples to heap manipulating programs. In: Logozzo F, Fähndrich M (eds) Static analysis: 20th international symposium, SAS 2013, Seattle, WA, USA, 20–22 June 2013. Proceedings. Springer, Berlin

[58]

Roy S, Pandey A, Dolan-Gavitt B, Hu Y (2018) Bug synthesis: challenging bug-finding tools with deep faults. In: Proceedings of the 2018 26th ACM joint meeting on European software engineering conference and symposium on the foundations of software engineering, ESEC/FSE 2018, New York, NY, USA. Association for Computing Machinery, pp 224–234

[59]

Sen K, Marinov D, Agha G (2005) CUTE: a concolic unit testing engine for C. In: ESEC/FSE-13, New York, NY, USA. ACM

[60]

Singal D, Agarwal P, Jhunjhunwala S, Roy S (2018) Parse condition: symbolic encoding of ll(1) parsing. In: Barthe G, Sutcliffe G, Veanes M (eds) LPAR-22. 22nd international conference on logic for programming, artificial intelligence and reasoning. EPiC series in computing, vol 57. EasyChair, pp 637–655

[61]

Singh R, Gulwani S, Solar-Lezama A (2013) Automated feedback generation for introductory programming assignments. In: Proceedings of the 34th ACM SIGPLAN conference on programming language design and implementation, PLDI ’13, New York, NY, USA. Association for Computing Machinery

[62]

Singh R, Solar-Lezama A (2011) Synthesizing data structure manipulations from storyboards. In: Proceedings of the 19th ACM SIGSOFT symposium and the 13th European conference on foundations of software engineering, ESEC/FSE ’11, New York, NY, USA. ACM

[63]

Tan SH, Yoshida H, Prasad MR, Roychoudhury A (2016) Anti-patterns in search-based program repair. In: Proceedings of the 2016 24th ACM SIGSOFT international symposium on foundations of software engineering, FSE 2016, New York, NY, USA. Association for Computing Machinery, pp 727–738

[64]

Verma A, Kalita PK, Pandey A, Roy S (2020) Interactive debugging of concurrent programs under relaxed memory models. In: Proceedings of the 18th ACM/IEEE international symposium on code generation and optimization, CGO 2020, New York, NY, USA. Association for Computing Machinery, pp 68–80

[65]

Verma S, Roy S (2017) Synergistic debug-repair of heap manipulations. In: Proceedings of the 2017 11th joint meeting on foundations of software engineering, ESEC/FSE 2017, New York, NY, USA. ACM

[66]

Wang K, Singh R, Su Z (2017) Dynamic neural program embedding for program repair. arXiv, arXiv:1711.07163

[67]

Wang K, Singh R, Su Z (2018) Search, align, and repair: data-driven feedback generation for introductory programming exercises. In: Proceedings of the 39th ACM SIGPLAN conference on programming language design and implementation, PLDI 2018, New York, NY, USA. Association for Computing Machinery pp 481–495

[68]

Weimer W (2006) Patches as better bug reports. In: Proceedings of the 5th international conference on generative programming and component engineering, GPCE ’06, New York, NY, USA. ACM

[69]

Weimer W, Nguyen T, Le Goues C, Forrest S (2009) Automatically finding patches using genetic programming. In: Proceedings of the 31st international conference on software engineering, ICSE ’09, Washington, DC, USA. IEEE Computer Society

[70]

Zeller A (2002) Isolating cause-effect chains from computer programs. In: Proceedings of the 10th ACM SIGSOFT symposium on foundations of software engineering, SIGSOFT ’02/FSE-10, New York, NY, USA. ACM

[71]

Zeller A and Hildebrandt R Simplifying and isolating failure-inducing input IEEE Trans Softw Eng 2002 28 2 183-200

[72]

Zimmermann T and Zeller A Diehl S Visualizing memory graphs Revised lectures on software visualization, international seminar 2002 London Springer-Verlag

Cited By

Roy SHaiduc SSchneider J(2023)A Theorem Proving Approach to Programming Language SemanticsProceedings of the 45th International Conference on Software Engineering: Software Engineering Education and Training10.1109/ICSE-SEET58685.2023.00021(153-165)Online publication date: 17-May-2023
https://dl.acm.org/doi/10.1109/ICSE-SEET58685.2023.00021
Chatterjee PKalita PLahiri SMuduli SSingh VTakhar GRoy SBissyandé TKlein JBird CSarro F(2023)An Integrated Program Analysis Framework for Graduate Courses in Programming Languages and Software EngineeringProceedings of the 38th IEEE/ACM International Conference on Automated Software Engineering10.1109/ASE56229.2023.00101(598-610)Online publication date: 11-Nov-2023
https://dl.acm.org/doi/10.1109/ASE56229.2023.00101
Muduli SRoy S(2022)Satisfiability modulo fuzzing: a synergistic combination of SMT solving and fuzzingProceedings of the ACM on Programming Languages10.1145/35633326:OOPSLA2(1236-1263)Online publication date: 31-Oct-2022
https://dl.acm.org/doi/10.1145/3563332

Index Terms

Debug-localize-repair: a symbiotic construction for heap manipulations

Index terms have been assigned to the content through auto-classification.

Recommendations

Synergistic debug-repair of heap manipulations
ESEC/FSE 2017: Proceedings of the 2017 11th Joint Meeting on Foundations of Software Engineering

We present Wolverine, an integrated Debug-Repair environment for heap manipulating programs. Wolverine facilitates stepping through a concrete program execution, provides visualizations of the abstract program states (as box-and-arrow diagrams) and ...
Bug localization via searching crowd-contributed code
Internetware '14: Proceedings of the 6th Asia-Pacific Symposium on Internetware

Bug localization, i.e., locating bugs in code snippets, is a frequent task in software development. Although static bug-finding tools are available to reduce manual effort in bug localization, these tools typically detect bugs with known project-...
A controlled experiment of different code representations for learning-based program repair
Abstract
Training a deep learning model on source code has gained significant traction recently. Since such models reason about vectors of numbers, source code needs to be converted to a code representation before vectorization. Numerous approaches have ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Formal Methods in System Design

Formal Methods in System Design Volume 58, Issue 3

Nov 2021

124 pages

ISSN:0925-9856

Issue’s Table of Contents

© The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature 2022.

Publisher

Kluwer Academic Publishers

United States

Publication History

Accepted: 08 December 2021

Published: 01 November 2021

Received: 17 April 2020

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 17 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Roy SHaiduc SSchneider J(2023)A Theorem Proving Approach to Programming Language SemanticsProceedings of the 45th International Conference on Software Engineering: Software Engineering Education and Training10.1109/ICSE-SEET58685.2023.00021(153-165)Online publication date: 17-May-2023
https://dl.acm.org/doi/10.1109/ICSE-SEET58685.2023.00021
Chatterjee PKalita PLahiri SMuduli SSingh VTakhar GRoy SBissyandé TKlein JBird CSarro F(2023)An Integrated Program Analysis Framework for Graduate Courses in Programming Languages and Software EngineeringProceedings of the 38th IEEE/ACM International Conference on Automated Software Engineering10.1109/ASE56229.2023.00101(598-610)Online publication date: 11-Nov-2023
https://dl.acm.org/doi/10.1109/ASE56229.2023.00101
Muduli SRoy S(2022)Satisfiability modulo fuzzing: a synergistic combination of SMT solving and fuzzingProceedings of the ACM on Programming Languages10.1145/35633326:OOPSLA2(1236-1263)Online publication date: 31-Oct-2022
https://dl.acm.org/doi/10.1145/3563332
Kalita PSingal DAgarwal PJhunjhunwala SRoy S(2022)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: 1-Dec-2022
https://dl.acm.org/doi/10.1007/s10703-023-00420-3

View Options

View options

Login options

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

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents