Article

Starc: static analysis for efficient repair of complex data

Authors:

Bassem Elkarablieh,

Sarfraz Khurshid,

Kathryn S. McKinleyAuthors Info & Claims

OOPSLA '07: Proceedings of the 22nd annual ACM SIGPLAN conference on Object-oriented programming systems, languages and applications

Pages 387 - 404

https://doi.org/10.1145/1297027.1297056

Published: 21 October 2007 Publication History

Abstract

Data structure corruptions are insidious bugs that reduce the reliability of software systems. Constraint-based datastructure repair promises to help programs recover from potentially crippling corruption errors. Prior work repairs a variety of relatively small data structures, usually with hundreds of nodes.

We present STARC which uses static analysis to repair data structures with tens of thousands of nodes. Given a Java predicate method that describes the integrity constraints of a structure, STARC statically analyzes the method to identify: (1) the recurrent fields, i.e., fields that the predicate method uses to traverse the structure; and (2) local field constraints, i.e., how the value of an object field is related to the value of a neighboring object field. STARC executes the predicate method on the structure and monitors its execution to identify corrupt object fields, which STARC then repairs using a systematic search of a neighborhood of the given structure. Each repair action is guided by the result of the static analysis, which enables more efficient and effective repair compared to prior work. Experimental results showthat STARC can repair structures with tens of thousands of nodes, up to 100 times larger than prior work.

STARC efficiency is probably not practical for very large data structures in deployed systems, but opens a promising direction for future work.

References

[1]

William Adjie-Winoto, Elliot Schwartz, Hari Balakrishnan, and Jeremy Lilley. The design and implementation of an intentional naming system. In Proc. 17th ACM Symposium on Operating Systems Principles (SOSP), Kiawah Island, December 1999.

Digital Library

[2]

C. Artho, H. Barringer, A. Goldberg, K. Havelund, S. Khurshid, M. Lowry, C. Pasareanu, G. Rosu, K. Sen, W. Visser, and R. Washington. Combining test case generation and runtime verification. Theoretical Computer Science, 2005.

Digital Library

[3]

Clark Barrett and Sergey Berezin. CVC Lite: A new implementation of the cooperating validity checker. In Proceedings of the 16th International Conference On Computer Aided Verification, Boston, MA, July 2004.

[4]

Douglas Barry. Web Services and Service-Oriented Architectures: The Savvy Manager's Guide., chapter Service Oriented Architecture. Morgan Kaufmann Publishers, 2003.

Digital Library

[5]

Chandrasekhar Boyapati, Sarfraz Khurshid, and Darko Marinov. Korat: Automated testing based on Java predicates. In Proc. International Symposium on Software Testing and Analysis (ISSTA), July 2002.

Digital Library

[6]

B. Cahoon and K. McKinley. Recurrence analysis for effective array prefetching in java. Concurrency and Computation Practice and Experience, 17, February 2005.

Digital Library

[7]

Brendon Cahoon. Effective Compile-Time Analysis for Data Prefetching in Java. PhD thesis, University of Massachusetts, Boston, MA, 2002.

Digital Library

[8]

Edmund. M. Clarke, Orna Grumberg, and Doron~. A. Peled. Model Checking. The MIT Press, Cambridge, MA, 1999.

Digital Library

[9]

Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest. Introduction to Algorithms. The MIT Press, Cambridge, MA, 1990.

Digital Library

[10]

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

Digital Library

[11]

Brian Demsky, Michael D. Ernst, Philip J. Guo, Stephen McCamant, Jeff H. Perkins, and Martin Rinard. Inference and enforcement of data structure consistency specifications. In Proc. International Symposium on Software Testing and Analysis (ISSTA), July 2006.

Digital Library

[12]

Brian Demsky and Martin Rinard. Automatic detection and repair of errors in data structures. In Proc. Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA), 2003.

Digital Library

[13]

Bassem Elkarablieh, Iván García, Yuk Lai Suen, and Sarfraz Khurshid. Assertion-based repair of structurally complex data. (Under submission).

[14]

Bassem Elkarablieh, Yahya Zayour, and Sarfraz Khurshid. Efficiently generating structurally complex inputs with thousands of objects. In Proc. European Conference on Object-Oriented Programming (ECOOP), July 2007.

Digital Library

[15]

Sanguthevar Rajasekaran Ellis Horowitz. Computer Algorithms. W. H. Freeman, second edition, 1997.

[16]

Michael D. Ernst. Dynamically Discovering Likely Program Invariants. PhD thesis, University of Washington Department of Computer Science and Engineering, Seattle, Washington, August 2000.

Digital Library

[17]

Iván García. Enabling symbolic execution of Java programs using bytecode instrumentation. Master's thesis, The University of Texas at Austin, May 2005.

[18]

Patrice Godefroid. Model checking for programming languages using VeriSoft. In Proc. 24th Annual ACM Symposium on the Principles of Programming Languages (POPL), Paris, France, January 1997.

Digital Library

[19]

Sudhakar Govindavajhala and Andrew W. Appel. Using memory errors to attack a virtual machine. In SP'03: Proceedings of the 2003 IEEE Symposium on Security and Privacy, 2003.

Digital Library

[20]

G. Haugk, F. Lax, R. Royer, and J. Williams. The 5ESS(TM) switching system: Maintenance capabilities. AT&T Technical Journal, 64(6 part 2), 1985.

[21]

Klaus Havelund and Thomas Pressburger. Model checking Java programs using Java PathFinder. International Journal on Software Tools for Technology Transfer, 1999.

[22]

Gerald Holzmann. The model checker SPIN. IEEE Transactions on Software Engineering, 23(5), May 1997.

Digital Library

[23]

Daniel Jackson. Micromodels of software: Modelling and analysis with Alloy, 2001.

[24]

Daniel Jackson. Software Abstractions: Logic, Language and Analysis. The MIT Press, Cambridge, MA, 2006.

Digital Library

[25]

B. Jobstmann, A. Griesmayer, and R. Bloem. Program repair as a game. In 17th Conference on Computer Aided Verification (CAV'05), 2005.

Digital Library

[26]

Maria Jump and Kathryn S. McKinley. Cork: Dynamic memory leak detection for java. In Proc. 34th Annual ACM Symposium on the Principles of Programming Languages (POPL), 2007.

Digital Library

[27]

Feras Karablieh, Rida A. Bazzi, and Margaret Hicks. Compiler-assisted heterogeneous checkpointing. In Symposium on Reliable Distributed Systems (SRDS), October 2001.

[28]

Sarfraz Khurshid, Iván García, and Yuk Lai Suen. Repairing structurally complex data. In Proc. 12th SPIN Workshop on Software Model Checking, 2005.

Digital Library

[29]

Sarfraz Khurshid, Corina Pasareanu, and Willem Visser. Generalized symbolic execution for model checking and testing. In Proc. 9th Conference on Tools and Algorithms for Construction and Analysis of Systems (TACAS), Warsaw, Poland, April 2003.

Digital Library

[30]

J. L. Kim and T. Park. An efficient protocol for checkpointing recovery in distributed systems. IEEE Transactions on Parallel and Distributed Systems, Aug 1993.

Digital Library

[31]

James C. King. Symbolic execution and program testing. Communications of the ACM, 19(7), 1976.

Digital Library

[32]

Tim Lindholm and Frank Yellin. The Java Virtual Machine Specification. Addison Wesley, second edition, 1999.

Digital Library

[33]

Barbara Liskov and John Guttag. Program Development in Java: Abstraction, Specification, and Object-Oriented Design. Addison-Wesley, 2000.

Digital Library

[34]

Muhammad Zubair Malik, Aman Pervaiz, and Sarfraz Khurshid. Generating representation invariants of structurally complex data. In Proc. 11th Conference on Tools and Algorithms for Construction and Analysis of Systems (TACAS), 2007.

Digital Library

[35]

Darko Marinov. Automatic Testing of Software with Structurally Complex Inputs. PhD thesis, Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, 2004.

Digital Library

[36]

Samiha Mourad and Dorothy Andrews. On the reliability of the IBM MVS/XA operating system. IEEE Transactions on Software Engineering, 13(10), 1987.

Digital Library

[37]

Alexey Smirnov and Tzi-cker Chiueh. DIRA: Automatic detection, identification, and repair of control-hijacking attacks. In The 12th Annual Network and Distributed System Security Symposium, San Diego, CA, February 2005.

[38]

William Stallings. Computer Organization and Architecture., chapter Cache Memory. Prentice-Hall, Englewood Cliffs, NJ, 2006.

[39]

Yuk Lai Suen. Automatically repairing structurally complex data. Master's thesis, Department of Electrical and Computer Engineering, The University of Texas at Austin, May 2005.

[40]

Willem Visser, Klaus Havelund, Guillaume Brat, and SeungJoon Park. Model checking programs. In Proc. 15th Conference on Automated Software Engineering (ASE), Grenoble, France, 2000.

Digital Library

[41]

Tao Xie and David Notkin. Tool-assisted unit test generation and selection based on operational abstractions. Automated Software Engineering Journal, 2006.

Digital Library

Cited By

Rauf ANawaz MSiddiqui J(2019)Effective State Encoding for Breadth-First Generation of Complex StructuresIEEE Transactions on Reliability10.1109/TR.2019.291198968:3(1154-1167)Online publication date: Sep-2019
https://doi.org/10.1109/TR.2019.2911989
Grech NFourtounis GFrancalanza ASmaragdakis YTip FBodden E(2018)Shooting from the heap: ultra-scalable static analysis with heap snapshotsProceedings of the 27th ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3213846.3213860(198-208)Online publication date: 12-Jul-2018
https://dl.acm.org/doi/10.1145/3213846.3213860
Dhar APurandare RDhawan MRangaswamy SDi Nitto EHarman MHeymans P(2015)CLOTHO: saving programs from malformed strings and incorrect string-handlingProceedings of the 2015 10th Joint Meeting on Foundations of Software Engineering10.1145/2786805.2786877(555-566)Online publication date: 30-Aug-2015
https://dl.acm.org/doi/10.1145/2786805.2786877
Show More Cited By

Index Terms

Starc: static analysis for efficient repair of complex data

Recommendations

Starc: static analysis for efficient repair of complex data
Proceedings of the 2007 OOPSLA conference

Data structure corruptions are insidious bugs that reduce the reliability of software systems. Constraint-based datastructure repair promises to help programs recover from potentially crippling corruption errors. Prior work repairs a variety of ...
Juzi: a tool for repairing complex data structures
ICSE '08: Proceedings of the 30th international conference on Software engineering

This paper describes Juzi, a tool for automatic repair of complex data structures. Juzi takes a Java class representing the data structure as well as a predicate method that specifies the structural integrity constraints as inputs. Juzi instruments its ...
Assertion-based repair of complex data structures
ASE '07: Proceedings of the 22nd IEEE/ACM International Conference on Automated Software Engineering

Programmers have long used assertions to characterize properties of code. An assertion violation signals a corruption in the programstate. At such a state, it is standard to terminate the program, debug it if possible, and re-execute it. We propose a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

OOPSLA '07: Proceedings of the 22nd annual ACM SIGPLAN conference on Object-oriented programming systems, languages and applications

October 2007

728 pages

ISBN:9781595937865

DOI:10.1145/1297027

General Chair:
Richard P. Gabriel
IBM Research, USA
,
Program Chairs:
David F. Bacon
IBM Research, USA
,
Cristina Videira Lopes
University of California, Irvine, USA
,
Guy L. Steele
Sun Labs, USA

ACM SIGPLAN Notices Volume 42, Issue 10
Proceedings of the 2007 OOPSLA conference
October 2007
686 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/1297105
Issue’s Table of Contents

Copyright © 2007 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: 21 October 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

OOPSLA07

Sponsor:

OOPSLA07: ACM SIGPLAN Object Oriented Programming Systems and Applications Conference

October 21 - 25, 2007

Quebec, Montreal, Canada

Acceptance Rates

OOPSLA '07 Paper Acceptance Rate 33 of 156 submissions, 21%;

Overall Acceptance Rate 268 of 1,244 submissions, 22%

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

17
Total Citations
View Citations
411
Total Downloads

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

Reflects downloads up to 16 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Rauf ANawaz MSiddiqui J(2019)Effective State Encoding for Breadth-First Generation of Complex StructuresIEEE Transactions on Reliability10.1109/TR.2019.291198968:3(1154-1167)Online publication date: Sep-2019
https://doi.org/10.1109/TR.2019.2911989
Grech NFourtounis GFrancalanza ASmaragdakis YTip FBodden E(2018)Shooting from the heap: ultra-scalable static analysis with heap snapshotsProceedings of the 27th ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3213846.3213860(198-208)Online publication date: 12-Jul-2018
https://dl.acm.org/doi/10.1145/3213846.3213860
Dhar APurandare RDhawan MRangaswamy SDi Nitto EHarman MHeymans P(2015)CLOTHO: saving programs from malformed strings and incorrect string-handlingProceedings of the 2015 10th Joint Meeting on Foundations of Software Engineering10.1145/2786805.2786877(555-566)Online publication date: 30-Aug-2015
https://dl.acm.org/doi/10.1145/2786805.2786877
Logozzo FBall T(2012)Modular and verified automatic program repairACM SIGPLAN Notices10.1145/2398857.238462647:10(133-146)Online publication date: 19-Oct-2012
https://dl.acm.org/doi/10.1145/2398857.2384626
Logozzo FBall TLeavens GDwyer M(2012)Modular and verified automatic program repairProceedings of the ACM international conference on Object oriented programming systems languages and applications10.1145/2384616.2384626(133-146)Online publication date: 19-Oct-2012
https://dl.acm.org/doi/10.1145/2384616.2384626
Siddiqui JMarinov DKhurshid S(2012)Lightweight Data-Flow Analysis for Execution-Driven Constraint SolvingProceedings of the 2012 IEEE Fifth International Conference on Software Testing, Verification and Validation10.1109/ICST.2012.89(91-100)Online publication date: 17-Apr-2012
https://dl.acm.org/doi/10.1109/ICST.2012.89
Chen GQi ZHuang SNi KZheng YBinder WGuan H(2012)A refined decompiler to generate C code with high readabilitySoftware: Practice and Experience10.1002/spe.213843:11(1337-1358)Online publication date: 13-Jul-2012
https://doi.org/10.1002/spe.2138
Samimi HAung EMillstein T(2010)Falling back on executable specificationsProceedings of the 24th European conference on Object-oriented programming10.5555/1883978.1884015(552-576)Online publication date: 21-Jun-2010
https://dl.acm.org/doi/10.5555/1883978.1884015
Reichenbach CImmerman NSmaragdakis YAftandilian EGuyer S(2010)What can the GC compute efficiently?ACM SIGPLAN Notices10.1145/1932682.186948245:10(256-269)Online publication date: 17-Oct-2010
https://dl.acm.org/doi/10.1145/1932682.1869482
Reichenbach CImmerman NSmaragdakis YAftandilian EGuyer SCook WClarke SRinard MSullivan KSteinberg D(2010)What can the GC compute efficiently?Proceedings of the ACM international conference on Object oriented programming systems languages and applications10.1145/1869459.1869482(256-269)Online publication date: 17-Oct-2010
https://dl.acm.org/doi/10.1145/1869459.1869482
Show More Cited By

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten