Information Technology Reference
In-Depth Information
A
fault candidate
is a component that
may change
the value at all ob-
servation points to the expected values. A
fix
is a component that
changes
the value at all observation points to the expected values:
∀
i
:
v
faulty
(
OP
i
)=
v
expected
(
R
. The actual fault site is the position where the fault
was injected and it is called
fault site
.
OP
i
)
,
1
≤
i
≤
3
Debugging Algorithms
The CDFG and a set of
m
failure traces (
m
) are the input for automatic
debugging. Three debugging techniques are analyzed in the following: (1)
static analysis, (2) dynamic analysis, and (3) correction-based debugging.
The following sections briefly introduce the methods. For more informa-
tion about the debugging techniques, we refer the reader to the referenced
papers in the respective sections.
≥
1
3.1
Static Analysis
Independent of any failure trace, a static analysis on the CDFG enables to
identify components that have no influence on the output behavior of the
IL program. The redundant code fragments manifest themselves as pending
nodes in the CDFG, i.e., nodes without successors, and are detectable in
linear time (linear in the number of nodes). Only nodes that are in at least
one fan-in of any primary output influence the output behavior. Operations
that are not in any fan-in are redundant, cannot change the output behavior,
and can be removed from consideration. By this, the initial number of fault
candidates is reduced. Therefore, the information is also worthwhile for code
optimization on the IL program. For example, an assignment to a variable
A
is removable, if no read operation is applied to
A
and
A
is not an output or
a state element.
An additional analysis based on static slicing [22] uses the observation
points to further reduce the number of fault candidates. A faulty behavior is
observable at an observation point
OP
i
. Thus, all nodes on the path to any
OP
i
are potential fault candidates. All nodes that are not in the recursive
fan-in of any
OP
i
cannot influence the value at
OP
i
and do not have to be
considered for diagnosis. The nodes on the path from an observation point
OP
i
are recursively computed in linear time.
Let
P
ji
be a set of nodes on the path for failure trace
j
and observation
point
OP
i
. While assuming a single fault, all relevant nodes for debugging
(
P
) are computed by
P
=
P
ji
. For multiple faults the intersection can
be empty, e.g., if a faulty behavior is observed on two observation points
that have disjunctive input cones. One element from each path has to be
selected while assuming multiple faults. However, due to the computational
complexity for computing the hitting set, an over-approximation is considered
formultiplefaultsonly:
P
=
P
ji
. The union of all nodes from any path
are returned as fault candidates in case of multiple faults.
