Data structure repair using goal-directed reasoning

ABSTRACT

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 explicitly translate model repairs into concrete data structure repairs, raising the possibility of 1) incorrect translations causing the supposedly repaired concrete data structures to be inconsistent, and 2) repaired models with no corresponding concrete data structure representation.We present a new repair algorithm that uses goal-directed reasoning to automatically translate model repairs into concrete data structure repairs. This new repair algorithm eliminates the possibility of incorrect translations and repaired models with no corresponding representation as concrete data structures.

REFERENCES

• 1: Center-tracon automation system. http://www.ctas.arc.nasa.gov/
• 2: A. Mishra et al. R++: Using rules in object-oriented designs. In OOPSLA, July 1996.
• 3: George Candea , Armando Fox, Recursive Restartability: Turning the Reboot Sledgehammer into a Scalpel, Proceedings of the Eighth Workshop on Hot Topics in Operating Systems, p.125, May 20-22, 2001
• 4: Stefano Ceri , Jennifer Widom, Deriving Production Rules for Constraint Maintainance, Proceedings of the 16th International Conference on Very Large Data Bases, p.566-577, August 13-16, 1990
• 5: David Patterson , Aaron Brown , Pete Broadwell , George Candea , Mike Chen , James Cutler , Patricia Enriquez , Armando Fox , Emre Kiciman , Matthew Merzbacher , David Oppenheimer , Naveen Sastry , William Tetzlaff , Jonathan Traupman , Noah Treuhaft, Recovery Oriented Computing (ROC): Motivation, Definition, Techniques,, University of California at Berkeley, Berkeley, CA, 2002
• 6: Diane Litman , Peter F. Patel-Schneider , Anil Mishra, Modeling dynamic collections of interdependent objects using path-based rules, Proceedings of the 12th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.77-92, October 05-09, 1997, Atlanta, Georgia, United States
• 7: Brian Demsky , Martin Rinard, Automatic detection and repair of errors in data structures, Proceedings of the 18th annual ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applications, October 26-30, 2003, Anaheim, California, USA
• 8: B. Demsky and M. Rinard. Data structure repair using goal-directed reasoning. Technical Report 950, MIT Computer Science and Artificial Intelligence Laboratory, 2004.
• 9: G. Haugk. The 5ESS(TM) switching system: Maintenance capabilities. AT&T Technical Journal, 64(6 part 2):1385--1416, July-August 1985.
• 10: Jim Gray , Andreas Reuter, Transaction Processing: Concepts and Techniques, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1992
• 11: Roger Hoover, Alphonse: incremental computation as a programming abstraction, Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation, p.261-272, June 15-19, 1992, San Francisco, California, United States
• 12: James C. Corbett , Matthew B. Dwyer , John Hatcliff , Shawn Laubach , Corina S. Păsăreanu , Robby , Hongjun Zheng, Bandera: extracting finite-state models from Java source code, Proceedings of the 22nd international conference on Software engineering, p.439-448, June 04-11, 2000, Limerick, Ireland [doi>10.1145/337180.337234]
• 13: D. A. Ladd and J. C. Ramming. Two application languages in software production. In VHLL, October 1994.
• 14: Gustavo Eduardo Lopez, The design and implementation of Kaleidoscope, a constraint imperative programming language, University of Washington, Seattle, WA, 1997
• 15: Michael Bedford Taylor , Jason Kim , Jason Miller , David Wentzlaff , Fae Ghodrat , Ben Greenwald , Henry Hoffman , Paul Johnson , Jae-Wook Lee , Walter Lee , Albert Ma , Arvind Saraf , Mark Seneski , Nathan Shnidman , Volker Strumpen , Matt Frank , Saman Amarasinghe , Anant Agarwal, The Raw Microprocessor: A Computational Fabric for Software Circuits and General-Purpose Programs, IEEE Micro, v.22 n.2, p.25-35, March 2002 [doi>10.1109/MM.2002.997877]
• 16: Samiha Mourad , Dorothy Andrews, On the reliability of the IBM MVS/XA operating system, IEEE Transactions on Software Engineering, v.13 n.10, p.1135-1139, October 1, 1987 [doi>10.1109/TSE.1987.232855]
• 17: Neeraj K. Gupta , Lalita Jategaonkar Jagadeesan , Eleftherios E. Koutsofios , David M. Weiss, Auditdraw: Generating Audits the FAST Way, Proceedings of the 3rd IEEE International Symposium on Requirements Engineering (RE'97), p.188, January 05-08, 1997
• 18: Mendel Rosenblum , John K. Ousterhout, The design and implementation of a log-structured file system, Proceedings of the thirteenth ACM symposium on Operating systems principles, p.1-15, October 13-16, 1991, Pacific Grove, California, United States
• 19: Stefano Ceri , Piero Fraternali , Stefano Paraboschi , Letizia Tanca, Automatic generation of production rules for integrity maintenance, ACM Transactions on Database Systems (TODS), v.19 n.3, p.367-422, Sept. 1994 [doi>10.1145/185827.185828]
• 20: Seth Hallem , Benjamin Chelf , Yichen Xie , Dawson Engler, A system and language for building system-specific, static analyses, Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, June 17-19, 2002, Berlin, Germany
• 21: T. Griffin et al. Generating update constraints from PRL5.0 specifications. In Preliminary report presented at AT&T Database Day, September 1992.
• 22: S. D. Urban , L. M. L. Delcambre, Constraint Analysis: A Design Process for Specifying Operations on Objects, IEEE Transactions on Knowledge and Data Engineering, v.2 n.4, p.391-400, December 1990 [doi>10.1109/69.63251]

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features

General Terms:
Design, Languages, Reliability

Keywords:
data structure invariants, data structure repair