Enhancing constraint-based repair of data structure errors that recur using memoization
Pages 1823 - 1832
Abstract
Data structure repair has been proposed as an error recovery mechanism to increase software resilience when errors happen at runtime for a deployed system. Although substantial work has been done on data structure repair, scalability remains a key challenge and applicability remains rather restricted.
We present two constraint-based data structure repair techniques that build on the well-known Korat solver, which introduced an effective backtracking search to find all object graphs that satisfy user given structural properties within the user given bounds. Our baseline technique repairs an erroneous data structure by adapting the Korat search. While this approach is effective for repairing a data structure, it suffers from re-exploration when applied on data structures with similar errors that recur due to a fault in software or hardware that is exercised repeatedly. We introduce memoization to amortize the cost of a Korat search over repeated repairs that overlap in search. Our experimental results show that our memoized technique is effective for repairing data structure errors that recur.
References
[1]
Chandrasekhar Boyapati, Sarfraz Khurshid, and Darko Marinov. 2002. Korat: Automated testing based on Java predicates. In International Symposium on Software Testing and Analysis. 123--133.
[2]
Brian Demsky and Martin C. Rinard. 2003. Automatic detection and repair of errors in data structures. In Conference on Object-oriented Programing, Systems, Languages, and Applications. 78--95.
[3]
Brian Demsky and Martin C. Rinard. 2005. Data structure repair using goal-directed reasoning. In International Conference on Software Engineering. 176--185.
[4]
Nima Dini, Cagdas Yelen, Zakaria Alrmaih, Amresh Kulkarni, and Sarfraz Khurshid. 2018. Korat-API: a framework to enhance korat to better support testing and reliability techniques. In Symposium on Applied Computing. 1934--1943.
[5]
Nima Dini, Cagdas Yelen, Milos Gligoric, and Sarfraz Khurshid. 2019. Extension-Aware Automated Testing Based on Imperative Predicates. In International Conference on Software Testing, Validation and Verification. 25--36.
[6]
Nima Dini, Cagdas Yelen, and Sarfraz Khurshid. 2017. Optimizing Parallel Korat Using Invalid Ranges. In International Symposium on Model Checking Software. 182--191.
[7]
Niklas Een and Niklas Sorensson. 2003. An Extensible SAT-solver. In International conference on theory and applications of satisfiability testing. 502--518.
[8]
Bassem Elkarablieh, Ivan Garcia, Yuk Lai Suen, and Sarfraz Khurshid. 2007. Assertion-based repair of complex data structures. In International Conference on Automated Software Engineering. 64--73.
[9]
Bassem Elkarablieh, Sarfraz Khurshid, Duy Vu, and Kathryn S. McKinley. 2007. Starc: static analysis for efficient repair of complex data. In Conference on Object-Oriented Programming, Systems, Languages, and Applications. 387--404.
[10]
Bassem Elkarablieh, Darko Marinov, and Sarfraz Khurshid. 2008. Efficient Solving of Structural Constraints. In International Symposium on Software Testing and Analysis. 39--50.
[11]
Antonio Filieri, Marcelo F. Frias, Corina S. Pasareanu, and Willem Visser. 2015. Model Counting for Complex Data Structures. In International Symposium on Model Checking Software. 222--241.
[12]
Patrice Godefroid, Nils Klarlund, and Koushik Sen. 2005. DART: directed automated random testing. In Conference on Programming Language Design and Implementation. 213--223.
[13]
George Haugk, Frederick M. Lax, Robert D. Royer, and John R. Williams. 1985. The 5ESS(TM) switching system: Maintenance capabilities. AT&T Technical Journal 64, 6 (1985), 1385--1416.
[14]
Ishtiaque Hussain and Christoph Csallner. 2010. Dynamic Symbolic Data Structure Repair. In International Conference on Software Engineering. 215--218.
[15]
HyperSQL. 2020. HyperSQL Java database. http://hsqldb.org/.
[16]
Daniel Jackson. 2006. Software Abstractions - Logic, Language, and Analysis.
[17]
Sarfraz Khurshid, Iván García, and Yuk Lai Suen. 2005. Repairing Structurally Complex Data. In SPIN Workshop on Model Checking Software. 123--138.
[18]
Sarfraz Khurshid, Corina S. Pasareanu, and Willem Visser. 2003. Generalized Symbolic Execution for Model Checking and Testing. In International Conference on Tools and Algorithms for the Construction and Analysis of Systems. 553--568.
[19]
Korat. 2020. Korat Webpage. http://korat.sourceforge.net.
[20]
Shuvendu K. Lahiri, Robert Nieuwenhuis, and Albert Oliveras. 2006. SMT Techniques for Fast Predicate Abstraction. In International Conference on Computer Aided Verification. 424--437.
[21]
Barbara Liskov and John Guttag. 2001. Program Development in Java: Abstraction, Specification, and Object-Oriented Design. Addison-Wesley.
[22]
Darko Marinov. 2005. Automatic testing of software with structurally complex inputs. Ph.D. Dissertation. Massachusetts Institute of Technology, Cambridge, MA, USA. http://hdl.handle.net/1721.1/30161
[23]
Aleksandar Milicevic, Sasa Misailovic, Darko Marinov, and Sarfraz Khurshid. 2007. Korat: A Tool for Generating Structurally Complex Test Inputs. In International Conference on Software Engineering. 771--774.
[24]
Sasa Misailovic, Aleksandar Milicevic, Nemanja Petrovic, Sarfraz Khurshid, and Darko Marinov. 2007. Parallel test generation and execution with Korat. In International Symposium on Foundations of Software Engineering. 135--144.
[25]
Matthew W. Moskewicz, Conor F. Madigan, Ying Zhao, Lintao Zhang, and Sharad Malik. 2001. Chaff: Engineering an Efficient SAT Solver. In Design Automation Conference. 530--535.
[26]
Samiha Mourad and Dorothy Andrews. 1987. On the Reliability of the IBM MVS/XA Operating System. IEEE Transactions on Software Engineering (1987), 1135--1139.
[27]
Pengyu Nie, Marinela Parovic, Zhiqiang Zang, Sarfraz Khurshid, Aleksandar Milicevic, and Milos Gligoric. 2020. Unifying execution of imperative generators and declarative specifications. Proc. ACM Program. Lang. 4, OOPSLA (2020), 217:1--217:26.
[28]
Martin Rinard. 2003. Resilient computing. Technical Report. MIT Computer Science and Artificial Intelligence Laboratory.
[29]
Hesam Samimi, Ei Darli Aung, and Todd Millstein. 2010. Falling Back on Executable Specifications. In European Conference on Object-Oriented Programming. 552--576.
[30]
Koushik Sen, Darko Marinov, and Gul Agha. 2005. CUTE: a concolic unit testing engine for C. In International Symposium on Foundations of Software Engineering. 263--272.
[31]
Tao Xie, Darko Marinov, and David Notkin. 2004. Rostra: A Framework for Detecting Redundant Object-Oriented Unit Tests. In International Conference on Automated Software Engineering. 196--205.
[32]
Razieh Nokhbeh Zaeem, Divya Gopinath, Sarfraz Khurshid, and Kathryn S. McKinley. 2012. History-Aware Data Structure Repair Using SAT. In International Conference on Tools and Algorithms for the Construction and Analysis of Systems. 2--17.
[33]
Razieh Nokhbeh Zaeem and Sarfraz Khurshid. 2010. Contract-Based Data Structure Repair Using Alloy. In European Conference on Object-Oriented Programming. 577--598.
[34]
Razieh Nokhbeh Zaeem, Muhammad Zubair Malik, and Sarfraz Khurshid. 2013. Repair Abstractions for More Efficient Data Structure Repair. In International Conference on Runtime Verification. 235--250.
Index Terms
- Enhancing constraint-based repair of data structure errors that recur using memoization
Recommendations
Constraint-Based Program Debugging Using Data Structure Repair
ICST '11: Proceedings of the 2011 Fourth IEEE International Conference on Software Testing, Verification and ValidationDevelopers have used data structure repair over the last few decades as an effective means to recover on-the-fly from errors in program state. Traditional repair techniques were based on dedicated repair routines, whereas more recent techniques have ...
Data structure repair using goal-directed reasoning
ICSE '05: Proceedings of the 27th international conference on Software engineeringData structure repair is a promising technique for enabling programs to execute successfully in the presence of otherwise fatal data structure corruption errors. Previous research in this field relied on the developer to write a specification to ...
A Case for Automated Debugging Using Data Structure Repair
ASE '09: Proceedings of the 24th IEEE/ACM International Conference on Automated Software EngineeringAutomated debugging is becoming increasingly important as the size and complexity of software increases.This paper makes a case for using constraint-based data structure repair, a recently developed technique for fault recovery, as a basis for automated ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
March 2021
2075 pages
ISBN:9781450381048
DOI:10.1145/3412841
- Conference Chairs:
- Chih-Cheng Hung,
- Jiman Hong,
- Program Chairs:
- Alessio Bechini,
- Eunjee Song
Copyright © 2021 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]
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 22 April 2021
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
Conference
SAC '21
Sponsor:
SAC '21: The 36th ACM/SIGAPP Symposium on Applied Computing
March 22 - 26, 2021
Virtual Event, Republic of Korea
Acceptance Rates
Overall Acceptance Rate 1,650 of 6,669 submissions, 25%
Upcoming Conference
SAC '25
- Sponsor:
- sigapp
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 138Total Downloads
- Downloads (Last 12 months)63
- Downloads (Last 6 weeks)11
Reflects downloads up to 15 Jan 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in