Assertion-based Repair of Complex Data Structures
Google Tech Talks
June 29th, 2007
Data structure corruptions are insidious bugs that reduce the reliability of software systems. Programmers have long used assertions to characterize data structure properties. An assertion violation signals a corruption in the program state. At such a state, it is standard to terminate the program, debug it if possible, and re-execute it.
This talk will discuss a new view: instead of terminating the program, use the violated assertion as a basis of repairing the state of the program and let it continue.
The talk will present a novel algorithm to repair structurally complex data. Given a structure that violates an assertion that represents its integrity constraints, our algorithm performs a systematic search based on symbolic execution to repair the structure, i.e., mutate it such that the resulting structure satisfies the constraints and is similar to the original one.
Experiments using libraries and applications, such as a naming architecture, a database engine, and a software cache show that the algorithm efficiently repairs complex structures,even those with thousands of objects, while enabling systems to recover from potentially crippling errors.