research-article

Dynamic symbolic data structure repair

Authors:

Ishtiaque Hussain,

Christoph CsallnerAuthors Info & Claims

ICSE '10: Proceedings of the 32nd ACM/IEEE International Conference on Software Engineering - Volume 2

Pages 215 - 218

https://doi.org/10.1145/1810295.1810333

Published: 01 May 2010 Publication History

Get Access

Abstract

Generic repair of complex data structures is a new and exciting area of research. Existing approaches can integrate with good software engineering practices such as program assertions. But in practice there is a wide variety of assertions and not all of them satisfy the style rules imposed by existing repair techniques. I.e., a "badly" written assertion may render generic repair inefficient or ineffective. In this paper we build on the state of the art in generic repair and discuss how generic repair can work effectively with a wider range of correctness conditions.

We motivate how dynamic symbolic techniques enable generic repair to support a wider range of correctness conditions and present DSDSR, a novel repair algorithm based on dynamic symbolic execution. We implement the algorithm for Java and report initial empirical results to demonstrate the promise of our approach for generic repair.

References

[1]

C. Boyapati, S. Khurshid, and D. Marinov. Korat: Automated testing based on Java predicates. In Proc. ACM SIGSOFT International Symposium on Software Testing and Analysis (ISSTA), pages 123--133. ACM, July 2002.

Digital Library

Google Scholar

[2]

É. Bruneton, R. Lenglet, and T. Coupaye. ASM: a code manipulation tool to implement adaptable systems. In Proc. ACM SIGOPS France Journées Composants 2002: Systèmes à composants adaptables et extensibles (Adaptable and extensible component systems), Nov. 2002.

Google Scholar

[3]

G. A. Cohen, J. S. Chase, and D. L. Kaminsky. Automatic program transformation with Joie. In Proc. USENIX Annual Technical Symposium, pages 167--178. USENIX, June 1998.

Digital Library

Google Scholar

[4]

B. Demsky. Data Structure Repair Using Goal-Directed Reasoning. PhD thesis, Massachusetts Institute of Technology, 2006.

Digital Library

Google Scholar

[5]

B. Demsky and M. C. Rinard. Automatic detection and repair of errors in data structures. In Proc. 18th ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA), pages 78--95. ACM, Oct. 2003.

Digital Library

Google Scholar

[6]

B. Elkarablieh, I. Garcia, Y. L. Suen, and S. Khurshid. Assertion-based repair of complex data structures. In Proc. 22nd IEEE/ACM International Conference on Automated Software Engineering (ASE), pages 64--73. ACM, Nov. 2007.

Digital Library

Google Scholar

[7]

B. Elkarablieh and S. Khurshid. Juzi: a tool for repairing complex data structures. In Proc. 30th ACM/IEEE International Conference on Software Engineering (ICSE), pages 855--858. ACM, May 2008.

Digital Library

Google Scholar

[8]

P. Godefroid, N. Klarlund, and K. Sen. Dart: Directed automated random testing. In Proc. ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), pages 213--223. ACM, June 2005.

Digital Library

Google Scholar

[9]

G. Kudrjavets, N. Nagappan, and T. Ball. Assessing the relationship between software assertions and faults: An empirical investigation. In Proc. 17th IEEE International Symposium on Software Reliability Engineering (ISSRE), pages 204--212. IEEE, Nov. 2006.

Digital Library

Google Scholar

[10]

M. Z. Malik, K. Ghori, B. Elkarablieh, and S. Khurshid. A case for automated debugging using data structure repair. In 24th IEEE/ACM International Conference on Automated Software Engineering (ASE). IEEE, Nov. 2009.

Digital Library

Google Scholar

[11]

S. Mourad and D. Andrews. On the reliability of the IBM MVS/XA operating system. IEEE Transactions on Software Engineering (TSE), 13(10):1135--1139, Oct. 1987.

Digital Library

Google Scholar

[12]

K. Sen and G. Agha. Cute and jCute: Concolic unit testing and explicit path model-checking tools. In Proc. International Conference on Computer Aided Verification (CAV), pages 419--423. Springer, Aug. 2006.

Digital Library

Google Scholar

[13]

N. Tillmann and J. de Halleux. Pex - white box test generation for .Net. In Proc. 2nd International Conference on Tests And Proofs (TAP), pages 134--153. Springer, Apr. 2008.

Digital Library

Google Scholar

Cited By

View all

Li ZWang YLin ZCheung SLou JDwyer MDamian DZeller A(2022)NufixProceedings of the 44th International Conference on Software Engineering10.1145/3510003.3510118(1545-1557)Online publication date: 21-May-2022
https://dl.acm.org/doi/10.1145/3510003.3510118
Kirschner LSoremekun EZeller ARothermel GBae D(2020)Debugging inputsProceedings of the ACM/IEEE 42nd International Conference on Software Engineering10.1145/3377811.3380329(75-86)Online publication date: 27-Jun-2020
https://dl.acm.org/doi/10.1145/3377811.3380329
Uva MPonzio PRegis GAguirre NFrias M(2018)Automated workarounds from Java program specifications based on SAT solvingInternational Journal on Software Tools for Technology Transfer (STTT)10.5555/3288063.328808320:6(665-688)Online publication date: 1-Nov-2018
https://dl.acm.org/doi/10.5555/3288063.3288083
Show More Cited By

Index Terms

Recommendations

Data structure repair using goal-directed reasoning
ICSE '05: Proceedings of the 27th international conference on Software engineering

Data 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 ...
DSDSR: a tool that uses dynamic symbolic execution for data structure repair
WODA '10: Proceedings of the Eighth International Workshop on Dynamic Analysis

We present DSDSR, a generic repair tool for complex data structures. Generic, automatic data structure repair algorithms have applications in many areas. Reducing repair time can may therefore have a significant impact on software robustness. Current ...
Constraint-Based Program Debugging Using Data Structure Repair
ICST '11: Proceedings of the 2011 Fourth IEEE International Conference on Software Testing, Verification and Validation

Developers 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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ICSE '10: Proceedings of the 32nd ACM/IEEE International Conference on Software Engineering - Volume 2

May 2010

554 pages

ISBN:9781605587196

DOI:10.1145/1810295

General Chairs:
Jeff Kramer
Imperial College, London, UK
,
Judith Bishop
Microsoft Research, Redmond
,
Program Chairs:
Prem Devanbu
University of California at Davis
,
Sebastian Uchitel
University of Buenos Aires, Argentina and Imperial College London, UK

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: 01 May 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ICSE '10

Sponsor:

SIGSOFT

ICSE '10: 32nd International Conference on Software Engineering

May 1 - 8, 2010

Cape Town, South Africa

Acceptance Rates

Overall Acceptance Rate 276 of 1,856 submissions, 15%

Upcoming Conference

ICSE 2025

2025 IEEE/ACM 46th International Conference on Software Engineering

April 26 - May 3, 2025

Ottawa , ON , Canada

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
214
Total Downloads

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

Reflects downloads up to 06 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Li ZWang YLin ZCheung SLou JDwyer MDamian DZeller A(2022)NufixProceedings of the 44th International Conference on Software Engineering10.1145/3510003.3510118(1545-1557)Online publication date: 21-May-2022
https://dl.acm.org/doi/10.1145/3510003.3510118
Kirschner LSoremekun EZeller ARothermel GBae D(2020)Debugging inputsProceedings of the ACM/IEEE 42nd International Conference on Software Engineering10.1145/3377811.3380329(75-86)Online publication date: 27-Jun-2020
https://dl.acm.org/doi/10.1145/3377811.3380329
Uva MPonzio PRegis GAguirre NFrias M(2018)Automated workarounds from Java program specifications based on SAT solvingInternational Journal on Software Tools for Technology Transfer (STTT)10.5555/3288063.328808320:6(665-688)Online publication date: 1-Nov-2018
https://dl.acm.org/doi/10.5555/3288063.3288083
Uva MPonzio PRegis GAguirre NFrias M(2018)Automated workarounds from Java program specifications based on SAT solvingInternational Journal on Software Tools for Technology Transfer10.1007/s10009-018-0503-820:6(665-688)Online publication date: 10-Aug-2018
https://doi.org/10.1007/s10009-018-0503-8
Uva MPonzio PRegis GAguirre NFrias M(2017)Automated Workarounds from Java Program Specifications Based on SAT SolvingProceedings of the 20th International Conference on Fundamental Approaches to Software Engineering - Volume 1020210.1007/978-3-662-54494-5_20(356-373)Online publication date: 22-Apr-2017
https://dl.acm.org/doi/10.1007/978-3-662-54494-5_20
Nokhbeh Zaeem RMalik MKhurshid S(2013)Repair Abstractions for More Efficient Data Structure RepairRuntime Verification10.1007/978-3-642-40787-1_14(235-250)Online publication date: 2013
https://doi.org/10.1007/978-3-642-40787-1_14
Long FGanesh VCarbin MSidiroglou SRinard MGlinz MMurphy GPezzè M(2012)Automatic input rectificationProceedings of the 34th International Conference on Software Engineering10.5555/2337223.2337233(80-90)Online publication date: 2-Jun-2012
https://dl.acm.org/doi/10.5555/2337223.2337233
Long FGanesh VCarbin MSidiroglou SRinard M(2012)Automatic input rectification2012 34th International Conference on Software Engineering (ICSE)10.1109/ICSE.2012.6227204(80-90)Online publication date: Jun-2012
https://doi.org/10.1109/ICSE.2012.6227204
Nokhbeh Zaeem RGopinath DKhurshid SMcKinley K(2012)History-Aware data structure repair using SATProceedings of the 18th international conference on Tools and Algorithms for the Construction and Analysis of Systems10.1007/978-3-642-28756-5_2(2-17)Online publication date: 24-Mar-2012
https://dl.acm.org/doi/10.1007/978-3-642-28756-5_2
Hussain ICsallner CCook JJones J(2010)DSDSRProceedings of the Eighth International Workshop on Dynamic Analysis10.1145/1868321.1868325(20-25)Online publication date: 12-Jul-2010
https://dl.acm.org/doi/10.1145/1868321.1868325

View Options

Login options

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

Cited By

Index Terms

Recommendations

Data structure repair using goal-directed reasoning

DSDSR: a tool that uses dynamic symbolic execution for data structure repair

Constraint-Based Program Debugging Using Data Structure Repair