Information Technology Reference
In-Depth Information
The third and fourth lines of Equation (26) constraint the pairs (
e
i
,e
o
)and
(
e
i
,e
o
) to bound single time chunks of execution for task
AC
(i.e., a single box
in Figure 3). The constraint
α
AC
means, if an event
e
= deq(Q3, empty) at
time
t
is on the reconstructed trace, then its corresponding events (stop and
alarm)mustbeproducedby
AC
within the 10 ms deadline, as well as when
AC
is active.
α
PM
and
α
PI
can be similarly defined.
Causality Analysis Result.
For the constructed constraint
ψ
for each case, we
have manually proved that
ψ
∧¬
ϕ
S
is unsatisfiable for the cases when
C
=
{
PI
}
or
C
=
{
PI,AC
}
, while it is satisfiable for
C
=
{
AC
}
. This result shows that
both
are culprits, according to the main contributory cause
definition (Definition 9). These two subsets are collected as the set of culprits
in Step 3 of the causality analysis framework. In Step 4, the two culprits
{
PI
}
and
{
PI,AC
}
{
PI
}
and
only. This result is consistent with our
intuition in that it is the
PI
task's fault in the first place to put a bogus empty
reservoir message to Q3, which triggers
AC
's fault.
{
PI,AC
}
are minimized to be
{
PI
}
6 Discussion
FreeRTOS Scheduling in Trace Reconstruction.
When defining the
“adding” constraint, we have assumed that the FreeRTOS scheduler would sched-
ule all the tasks the same as on the observed trace during trace reconstruction.
This assumption must be made due to the unavailability of FreeRTOS scheduling
information should the system be rerun. Without this assumption, the analysis
would have to include the FreeRTOS scheduler as part of the system and model
it (or even the entire FreeRTOS operating system) as a component too. This is
by itself a challenging task and is beyond the scope of this paper.
Causality Analysis vs. Fault Diagnosis.
Unlike many approaches to fault
diagnosis, we address the case of black-box components [25], in which internal
flows of information between component input and output are unknown. In this
case, techniques based on computing fault propagation paths lead to an over-
approximation of cause-effect chains. The causality analysis we proposed in the
paper improves the precision of this over-approximation.
Alternative Ways to Trace Reconstruction.
Our causality analysis is based
on counterfactual reasoning [16], where the system behavior is reevaluated on
the possible alternative traces. A commonly used criterion for constructing al-
ternative traces is to measure the
similarity
between the reconstructed traces
and the actual observed one. Causality analysis is only performed on alternative
traces which are
similar
to the observed trace. However, the notion of
similarity
is subjective, reflected by the rules used for the trace reconstruction.
In our approach, the trace reconstruction rules (R1)-(R3) represent a view at
the
task level
: a faulty task is replaced with a good one, and all its events, except
for system inputs, are reconstructed via the “removing” and “adding” operations.
In contrast, one could perform trace reconstruction at the finer grained
event
level
: the trace under analysis is scanned through until the first occurrence
e
f
of
