Information Technology Reference
In-Depth Information
Ta b l e 6 .
Time taken to repair erroneous Red Black Trees (ms). TO represents a time out of
500,000 ms.
Cobbler/DREAM
Cobbler
DREAM
(Size = 10)
(Size = 500)
(Size = 500)
Repair
1
282
582
864
TO
TO
TO
7
11
0
14 54642 54667
N/A
2
249
521
770
TO
TO
TO
5
37
0
40 56042 56119
N/A
3
331
772
1103
TO
TO
TO
6
9
0
11 53954 53974
N/A
4
251
494
745
TO
TO
TO
6
1045
0 1048 53508 55601
N/A
5.2
Evaluation: DREAM with Juzi Back-End
In this section, we compare DREAM with the original Juzi [8, 9] repair algorithm for
efficiency improvement. Juzi uses imperative descriptions of data structure invariants
called
repOk
methods [26]. Given a predicate
repOK
that represents desired structural
integrity constraints and a structure
S
1
that violates them, the Juzi algorithm performs
repair actions that mutate the given structure to generate a new structure
S
2
that satisfies
the constraints. Each repair action assigns some value to a field of an object in the
structure. This assignment is made based on the exploration of the possible set of field
assignments to reference variables. The fundamental problem that Juzi addresses is
the enormous number of combinations of field assignments that make it impossible
to enumerate all possible assignments (even for small structures) and check whether
any assignment represents a repaired structure. DREAM drastically reduces this search
space for error patterns that are repeated. The basic Juzi algorithm assumes that each
structural error is purely random and requires re-execution of the search for repair every
time. When the errors are repeated, Juzi performance does not improve but DREAM is
able to use repair abstractions to quickly fix the error.
Both Juzi and imperative implementation of DREAM have to check the structure
for validity after every mutation. Therefore, the number of calls made to
repOK
(the
routine checking of structural validity) is a good measure of the size of the exploration
each algorithm had to perform before fixing the structure. In our experiments, we use
the number of calls made to
repOK
to compare the efficiency of the two algorithms.
In our experiments we used the following structures:
-
A Linked List based implementation of Circular List. The errors injected in this
structure violated the circularity constraint.
-
Doubly Linked List with bad previous field assignment. The violated structural
constraint is that
next
is the transpose of
previous
.
-
Binary Tree with acyclicity constraint violation.
-
Binary Tree with Parent Pointer having a bad parent field assignment. The violated
structural constraint is that
child
is the transpose of
parent
.
Table 7 summarizes the results of our experiments with the subject structures. For
these experiments, each structure had only one injected error in it, also the error was a
