468
C. E. Budde et al.
Nondeterminism. Dynamic fault trees may exhibit nondeterministic behaviour
as a consequence of underspecified failure behaviour [15, 27]. This can happen
e.g. when two SPAREs have a single shared SBE: if all elements are failed, and
the SBE is repaired first, the failure behaviour depends on which SPARE gets
the SBE. Monte Carlo simulation, however, requires fully stochastic models and
cannot cope with nondeterminism. To overcome this problem we deploy the theory from [16, 32]. If a fault tree adheres to some mild syntactic conditions, then
its iosa semantics is weakly deterministic, meaning that all resolutions of the
nondeterministic choices lead to the same probability value. In particular, we
require that (1) each BE is connected to at most one SPARE gate, and (2) BEs
and SBEs connected to SPAREs are not connected to FDEPs. In addition to this,
some semantic decisions have been fixed, e.g. the semantics of PAND is fully
specified, and policies should be provided for RBOX and spare assignments.
Dependability metrics. An important use of fault trees is to compute relevant
dependability metrics. Let X t denote the random variable that represents the
state of the top event at time t [14]. Two popular metrics are:
– system reliability: the probability of observing no top event failure before
some mission time T > 0, viz. REL T = Prob
∀ t∈[0,T ] . X t = 0
;
– system availability: the proportion of time that the system remains operational in the long-run, viz. AVA = lim t→∞ Prob (X t = 0).
System unreliability and unavailability are the reverse of these metrics. That is:
UNREL T = 1 − REL T and UNAVA = 1 − AVA.
3 Stochastic simulation for Fault Trees
Standard Monte Carlo simulation (SMC). Monte Carlo simulation takes
random samples from stochastic models to estimate a (dependability) metric of
interest. For instance, to estimate the unreliability of a tree we sample N
independent traces from its iosa semantics. An unbiased statistical estimator
for p = UNREL T is the proportion of traces observing a top level event, that is,
ˆ
p N =
1
N
N
j=1 X
j where X
j = 1 if the j-th trace exhibits a top level failure before
time T and X
j = 0 otherwise. The statistical error of ˆ
p is typically quantified
with two numbers δ and ε s.t. ˆ
p ∈ [p − ε, p + ε] with probability δ. The interval
ˆ
p ± ε is called a confidence interval (ci) with coefficient δ and precision 2ε.
Such procedures scale linearly with the number of tree nodes and cater for a
wide range of pdfs, even non-Markovian distributions. However, they encounter
a bottleneck to estimate rare events: if p ≈ 0, very few traces observe X
j = 1.
Therefore, the variance of estimators like ˆ
p becomes huge, and cis become very
broad, easily degenerating to the trivial interval [0, 1]. Increasing the number
of traces alleviates this problem, but even standard ci settings—where ε is
relative to p—require sampling an unacceptable number of traces [35]. Rare
event simulation techniques solve this specific problem.
C. E. Budde et al.
Nondeterminism. Dynamic fault trees may exhibit nondeterministic behaviour
as a consequence of underspecified failure behaviour [15, 27]. This can happen
e.g. when two SPAREs have a single shared SBE: if all elements are failed, and
the SBE is repaired first, the failure behaviour depends on which SPARE gets
the SBE. Monte Carlo simulation, however, requires fully stochastic models and
cannot cope with nondeterminism. To overcome this problem we deploy the theory from [16, 32]. If a fault tree adheres to some mild syntactic conditions, then
its iosa semantics is weakly deterministic, meaning that all resolutions of the
nondeterministic choices lead to the same probability value. In particular, we
require that (1) each BE is connected to at most one SPARE gate, and (2) BEs
and SBEs connected to SPAREs are not connected to FDEPs. In addition to this,
some semantic decisions have been fixed, e.g. the semantics of PAND is fully
specified, and policies should be provided for RBOX and spare assignments.
Dependability metrics. An important use of fault trees is to compute relevant
dependability metrics. Let X t denote the random variable that represents the
state of the top event at time t [14]. Two popular metrics are:
– system reliability: the probability of observing no top event failure before
some mission time T > 0, viz. REL T = Prob
∀ t∈[0,T ] . X t = 0
;
– system availability: the proportion of time that the system remains operational in the long-run, viz. AVA = lim t→∞ Prob (X t = 0).
System unreliability and unavailability are the reverse of these metrics. That is:
UNREL T = 1 − REL T and UNAVA = 1 − AVA.
3 Stochastic simulation for Fault Trees
Standard Monte Carlo simulation (SMC). Monte Carlo simulation takes
random samples from stochastic models to estimate a (dependability) metric of
interest. For instance, to estimate the unreliability of a tree we sample N
independent traces from its iosa semantics. An unbiased statistical estimator
for p = UNREL T is the proportion of traces observing a top level event, that is,
ˆ
p N =
1
N
N
j=1 X
j where X
j = 1 if the j-th trace exhibits a top level failure before
time T and X
j = 0 otherwise. The statistical error of ˆ
p is typically quantified
with two numbers δ and ε s.t. ˆ
p ∈ [p − ε, p + ε] with probability δ. The interval
ˆ
p ± ε is called a confidence interval (ci) with coefficient δ and precision 2ε.
Such procedures scale linearly with the number of tree nodes and cater for a
wide range of pdfs, even non-Markovian distributions. However, they encounter
a bottleneck to estimate rare events: if p ≈ 0, very few traces observe X
j = 1.
Therefore, the variance of estimators like ˆ
p becomes huge, and cis become very
broad, easily degenerating to the trivial interval [0, 1]. Increasing the number
of traces alleviates this problem, but even standard ci settings—where ε is
relative to p—require sampling an unacceptable number of traces [35]. Rare
event simulation techniques solve this specific problem.