Information Technology Reference
In-Depth Information
Repair Abstractions for More Efficient
Data Structure Repair
Razieh Nokhbeh Zaeem, Muhammad Zubair Malik, and Sarfraz Khurshid
The University of Texas at Austin, Austin TX 78712, USA
{
rnokhbehzaeem,mzmalik,khurshid
}
@ece.utexas.edu
Abstract.
Despite the substantial advances in techniques for finding and remov-
ing bugs, code is often deployed with (unknown or known) bugs, which pose
a fundamental problem for software reliability. A promising approach to ad-
dress this problem is
data structure repair
—a runtime approach designed to per-
form
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 re-
pair. 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 loca-
tion 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.
Keywords:
Data structure repair, Error recovery, Runtime analysis.
1
Introduction
Despite substantial advances in finding and removing bugs in code, software systems
are often deployed with unknown or known bugs. Bugs in deployed code can be costly
- not only in terms of the cost of failures they can cause but also in terms of the cost
of fixing them.
Specification-based data structure repair
[6,8,17] is a promising ap-
proach for handling and recovering from errors in deployed systems. The key idea is
to use specifications of crucial properties, e.g., data structure invariants, at runtime for
error recovery. Thus, the specification use is not just for monitoring executions as in
traditional runtime checking, say using assertions [4], but additionally for repairing
erroneous executions by mutating erroneous states to conform to the specifications.
Given an erroneous state and the specification that it violates, data structure repair tech-
niques utilize the specific properties that are violated to perform a sequence of
repair
actions
, which update erroneous field values to new values that conform to the expected
properties.
While data structure repair provides a powerful mechanism for enforcing confor-
mance of actual behavior to expected behavior as specified, existing techniques that
