Information Technology Reference
In-Depth Information
an event that leads to task failure is found, and trace reconstruction is started
only from that particular occurrence; every event that happens before
e
f
is kept
the same as observed.
Compared to the set
TR
t
C
of reconstructed traces produced by task-level trace
reconstruction, the event-level trace reconstruction could produce a smaller set
TR
e
TR
t
C
of traces
more similar
to the observed trace. Using the finer-grained
event-level trace reconstruction, it is comparatively more likely to establish a
necessary cause (Definition 9), since less traces have to be examined for the
“for all” quantification to be satisfied. On the other hand, it is comparatively
less likely to establish a contributory cause (Definition 8), since less possible
alternative traces can be used to satisfy the “exists” quantification.
C
⊆
Full Observability.
Full observability
involves two assumptions: (1) we are able
to put probes at the interfaces of components so that each event is observable,
and (2) the recording facility is capable of capturing all events at component
interfaces. The first assumption is by our consideration of black-box components,
where internal events within a component is not observable, but the events at
its interface are observable. Violations to the second assumption may lead to
undetected faulty components, yielding a smaller set
F
of faulty components.
This may possibly lead to spuriously identified culprits.
Causality Definitions.
Several causality definitions have been discussed in
previous work [13,24,11,15,4,26], all based on the notion of counterfactual rea-
soning [16]. We in this work used the main contributory cause (Definition 9),
but showed that the causality analysis framework is parametric to the causal-
ity definition of choice. The capability of using different causality definitions
in the analysis increases the flexibility for the investigator to make reasonable
arguments.
The definitions of contributory and main contributory causes express different
levels of necessity needed to judge for the cause. If the suciency of causality
definition is of concern, one could use alternative trace reconstruction rules and
causality definitions.
Scalability.
While we are working on larger case studies to gain empirical results
on the scalability of our approach, we foresee two limitations. First, for a given
subset
C
is a necessary cause is coNP-complete for propositional logic [26] and undecidable
in general for first order logic [18]. This limits the scalability of our approach
to the capability of state-of-the-art SAT/SMT solvers, such as Z3 [7]. Second,
we have shown in the paper the direct computation of the minimal culprit,
which requires the explicit generation of the powerset of
C
of suspected faulty components, the complexity of computing whether
, limiting the possible
number of faulty components that can be analyzed practically. Further studies
on algorithms exploiting the underlying structure of the sets of reconstructed
traces could potentially speed up the explicit computation.
F
