STARC: Static analysis for efficient repair of complex data
Data structure corruptions are insidious bugs that reduce the reliability of software systems. Constraint-based data structure repair promises to help programs recover from potentially crippling corruption errors. Prior work repairs a variety of relatively small data structures, usually with hundreds of nodes. We present STARC which uses static analysis to repair data structures with tens of thousands of nodes. Given a Java predicate method that describes the integrity constraints of a structure, STARC statically analyzes the method to identify: (1) the recurrent fields, i. e., fields that the predicate method uses to traverse the structure; and (2) local field constraints, i. e., how the value of an object field is related to the value of a neighboring object field. STARC executes the predicate method on the structure and monitors its execution to identify corrupt object fields, which STARC then repairs using a systematic search of a neighborhood of the given structure. Each repair action is guided by the result of the static analysis, which enables more efficient and effective repair compared to prior work. Experimental results show that STARC can repair structures with tens of thousands of nodes, up to 100 times larger than prior work. STARC efficiency is probably not practical for very large data structures in deployed systems, but opens a promising direction for future work.
static analysis reliability structure repair symbolic execution