Automatic detection and repair of errors in data structures

ABSTRACT

We present a system that accepts a specification of key data structure consistency constraints, then dynamically detects and repairs violations of these constraints, enabling the program to continue to execute productively even in the face of otherwise crippling errors. Our experience using our system indicates that the specifications are relatively easy to develop once one understands the data structures. Furthermore, for our set of benchmark applications, our system can effectively repair inconsistent data structures and enable the program to continue to operate successfully.

REFERENCES

• 1: Center-tracon automation system. http://www.ctas.arc.nasa.gov/.
• 2: Chandrasekhar Boyapati , Robert Lee , Martin Rinard, Ownership types for safe programming: preventing data races and deadlocks, Proceedings of the 17th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, November 04-08, 2002, Seattle, Washington, USA
• 3: P. Broadwell, N. Sastry, and J. Traupman. FIG: A prototype tool for online verification of recovery mechanisms. In Workshop on Self-Healing, Adaptive and self-MANaged Systems, June 2002.
• 4: 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
• 5: 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]
• 6: 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
• 7: Jong-Deok Choi , Keunwoo Lee , Alexey Loginov , Robert O'Callahan , Vivek Sarkar , Manu Sridharan, Efficient and precise datarace detection for multithreaded object-oriented programs, Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, June 17-19, 2002, Berlin, Germany
• 8: David G. Clarke , John M. Potter , James Noble, Ownership types for flexible alias protection, Proceedings of the 13th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.48-64, October 18-22, 1998, Vancouver, British Columbia, Canada
• 9: 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]
• 10: Manuvir Das , Sorin Lerner , Mark Seigle, ESP: path-sensitive program verification in polynomial time, Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, June 17-19, 2002, Berlin, Germany
• 11: Edsger W. Dijkstra, Self-stabilizing systems in spite of distributed control, Communications of the ACM, v.17 n.11, p.643-644, Nov. 1974 [doi>10.1145/361179.361202]
• 12: Berny Goodheart , James Cox, The magic garden explained: the internals of UNIX System V Release 4: an open systems design, Prentice-Hall, Inc., Upper Saddle River, NJ, 1994
• 13: Jim Gray , Andreas Reuter, Transaction Processing: Concepts and Techniques, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1992
• 14: T. Griffin, H. Trickey, and C. Tuckey. Generating update constraints from prl5.0 specifications. In Preliminary report presented at ATT Database Day, September 1992.
• 15: 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
• 16: 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
• 17: G. Haugk, F. Lax, R. Royer, and J. Williams. The 5ESS(TM) switching system: Maintenance capabilities. AT&T Technical Journal, 64(6 part 2):1385--1416, July-August 1985.
• 18: D. Jackson. Alloy: A lightweight object modelling notation. Technical Report 797, Laboratory for Computer Science, Massachusetts Institute of Technology, 2000.
• 19: Daniel Jackson , Martin Rinard, Software analysis: a roadmap, Proceedings of the Conference on The Future of Software Engineering, p.133-145, June 04-11, 2000, Limerick, Ireland [doi>10.1145/336512.336545]
• 20: Viktor Kuncak , Patrick Lam , Martin Rinard, Role analysis, Proceedings of the 29th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.17-32, January 16-18, 2002, Portland, Oregon
• 21: D. A. Ladd and J. C. Ramming. Two application languages in software production. In Proceedings of the 1994 USENIX Symposium on Very High Level Language(VHLL), October 1994.
• 22: 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]
• 23: Christian Nentwich , Wolfgang Emmerich , Anthony Finkelstein, Consistency management with repair actions, Proceedings of the 25th International Conference on Software Engineering, May 03-10, 2003, Portland, Oregon
• 24: 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
• 25: D. Poirier. Second extended file system. http://www.nongnu.org/ext2-doc/, Aug 2002.
• 26: Rational Inc. The unified modeling language. http://www.rational.com/uml.
• 27: B. D. Sanford, K. Harwood, S. Nowlin, H. Bergeron, H. Heinrichs, G. Wells, and M. Hart. Center/tracon automation system: Development and evaluation in the field. In 38th Annual Air Traffic Control Association Conference Proceedings, October 1993.
• 28: R E Strom , S Yemini, Typestate: A programming language concept for enhancing software reliability, IEEE Transactions on Software Engineering, v.12 n.1, p.157-171, Jan. 1986
• 29: 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]
• 30: J. M. Voas and G. McGraw. Software Fault Injection. Wiley, 1998.

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.4 Software/Program Verification

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features

General Terms:
Design, Languages, Reliability

Keywords:
data structure invariants, data structure repair