Data Structure Repair

March 25, 2005
Brian Demsky | MIT

Programs often make assumptions about the states of the data structures that they manipulate. Errors that cause these data structures to become inconsistent can therefore be especially damaging, since inconsistent data structures may cause software systems to behave unacceptably or even fail catastrophically.

In this talk, I will present my specification-based approach to data structure repair. In this approach, the developer simply writes a declarative specification of the key consistency properties for the data structures. My repair algorithm generator then compiles this specification to automatically generate a repair algorithm for the data structure. The automatically-generated repair algorithm is guaranteed to repair the inconsistencies in damaged data structures and to terminate. I have evaluated my specification-based repair technique on several real-world applications. These applications include: AbiWord, an open source word processor; a parallel x86 emulator; CTAS, an air traffic control tool; FreeCiv, an online game; and a simplified Linux file system. My repair technique successfully enabled these programs to execute through otherwise fatal data structure corruption errors.

Speaker Details

Brian Demsky is a Ph.D. Candidate in the Program Analysis and Compilation Group at the MIT Computer Science and Artificial Intelligence Laboratory. He received a BS in Physics and a BS in Electrical Engineering from the University of Texas at Austin and a SM in Computer Science from the Massachusetts Institute of Technology. He is a recipient of the Fannie and John Hertz Foundation Fellowship. His research addresses software reliability, software debugging, and program understanding.