Repair Abstractions for More Efficient Data Structure Repair

Despite the substantial advances in techniques for finding and removing bugs, code is often deployed with (unknown or known) bugs, which pose a fundamental problem for software reliability. A promising approach to address this problem is

data structure repair

—a runtime approach designed to perform

repair actions

, i.e., mutations of erroneous data structures to repair (certain) errors in program state, to allow the program to

recover

from those errors and continue to execute. While data structure repair holds much promise, current techniques for repair do not scale to real applications.

This paper introduces

repair abstractions

for more efficient data structure repair. Our key insight is that if an error in the program state is due to a fault in software or hardware, a similar error may occur again, say when the same buggy code segment is executed again or when the same faulty memory location is accessed again. Conceptually, repair abstractions capture how erroneous program executions are repaired using concrete mutations to enable faster repair of similar errors in future. Experimental results using a suite of complex data structures show how repair abstractions allow more efficient repair than previous techniques.