Information Technology Reference
In-Depth Information
as defined in Equation
(2)
.The
causality analysis problem
with respect to a
causality definition
CD
, is to identify the set
2
F
|C
Culprit
=
{C ∈
is a cause according to causality definition
CD
,
and no proper subset of
(4)
C
satisfies
CD
}
.
We call the tuple
S,ϕ
S
,Tr,CD
an instance of the causality analysis prob-
lem. It can be seen from the causality definitions that, the reconstruction of the
set
TR
C
of alternative system execution traces is at the heart of the causality
analysis. In [26] we have proposed an approach based on the transformation of
a causality analysis problem instance into an unsatisfiability checking problem
instance. In this paper we extend the technique to handle real-time systems
where a system execution trace is a set of events ordered by their timestamps,
and the system/component specifications are based on both the occurrences and
timestamps of events. In the following, we first show an overview of the causality
analysis framework in Section 3, and detail the techniques for causality analysis
in Section 4 with a case study in Section 5.
3 The Causality Analysis Framework
In a bird's-eye view, the causality analysis process is conceptually divided into
four steps, as shown in Figure 2. The shaded ovals
System Definition
S
,
System
Property
ϕ
S
,observed
Trace
Tr
with system failure, and
Causality Definition
CD
are the input to the analysis; the output is a set
Culprit
of
Minimal Culprits
for the violation of
ϕ
S
on trace
Tr
with respect to the causality definition
CD
.
The intermediate artifacts, shown as unshaded ovals, and the four steps of the
analysis, shown as solid boxes, are discussed below.
Causality Analysis Framework Overview
System
Definition
1. Offline Analysis &
Powerset Construction
Powerset
2
F
of
Faulty Components
Trace with
System Failure
Loop for each
non-empty
element in
2
F
Minimal
Culprits
2. Trace Reconstruction
System
Property
Reconstructed
Set of Traces
Causality
Definition
3. Causality Analysis
& Collecting Causes
Set of
Culprits
4. Culprit
Minimization
Fig. 2.
The Causality Analysis Framework Overview