Data structure repair using goal-directed reasoning

Software errors, hardware faults, and user errors can cause data structures in running applications to become damaged so that they violate key consistency properties. As a result of this violation, the application may produce unacceptable results or even crash. This dissertation presents a new data structure repair system that accepts a specification of key data structure consistency constraints, then generates repair algorithms that dynamically detect and repair violations of these constraints, enabling the application to continue to execute productively even in the face of otherwise crippling errors. We have successfully applied our system to five benchmarks: CTAS, an air traffic control tool; AbiWord, an open source word processing application; Freeciv, an online game; a parallel x86 emulator; and a simplified Linux file system. 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 experimental results show that our system can effectively repair inconsistent data structures and enable the application to continue to operate successfully.

Department dc:contributor.department

Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2006

Author dc:creator

• Demsky, Brian Charles, 1975-

Advisor dc:contributor.advisor

• Martin C. Rinard.

• Electrical Engineering and Computer Science.

Statement dc:rights

• M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/35524

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/35524