Information Technology Reference
In-Depth Information
Ta b l e 7 .
The number of
repOK
calls made by DREAM vs Juzi for fixing the errors
Structure
size = 10
size = 500
Juzi
DREAM
Juzi
DREAM
Circular List
8
2
477
2
Doubly Linked List
6
2
251
2
Binary Tree
2
2
2
2
Binary Tree with Parent Pointers
8
2
263
2
repeating error and not the first time error. As expected, Juzi's time to repair is a linear
function for single errors while DREAM was able to fix the error in constant time. The
abstraction rules (Section 3.1) used by DREAM for each of the error are as follows.
-
In the case of circularity violation in the Circular List, DREAM used
First
and
Last
abstractions to point the
next
of the last node to
header
.
-
For Doubly Linked List the
Neighbor
rulewasusedbyDREAM.
-
Binary Tree with acyclicity constraint violation is an interesting case because both
Juzi and DREAM performed equally well. The rule used by DREAM was
Null
,and
it is interesting to note that Juzi also attempts
null
as the first value mutation to a
field.
-
Binary Tree with Parent Pointer having a bad parent field assignment was also able
to exploit the
Neighbor
rule.
Juzi bounds the space of possible mutations to a structure and then performs system-
atic exploration of this space. The implementation of the algorithm employs various
heuristics to make its search efficient but the basic algorithm is memoryless and does
not benefit from observed repairs. DREAM improves over Juzi by remembering the
fixes used earlier and reusing them. A real challenge for DREAM was to recall the prior
fixes when the underlying structure and object references have changed. The abstract
representation and code instrumentation make it possible for DREAM to learn from
Juzi repairs and subsequently try them before exhaustive exploration is attempted.
6
Related Work
Dynamic repair techniques which fix the faults at runtime and keep the state consis-
tent have been in existence for a long time. Examples of such techniques are file sys-
tem utilities such as fsck [10] and chkdsk [21], database check-pointing, and rollback
techniques.
As opposed to generic data structure repair, some systems support dedicated routines
for monitoring and repairing data structures. The idea of dedicated repair routines has
been applied in some commercial systems such as the IBM MVS operating system [22]
and the Lucent 5ESS telephone switch [12]. The most important drawback of such
repair routines is the lack of generality and extensibility.
