Data Structure Repair

Опубликовано 6 сентября 2016, 5:25

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.