464
C. E. Budde et al.
certain performance indicators. Two common metrics are system reliability—the
probability that there are no system failures during a given mission time—and
system availability—the average percentage of time that a system is operational.
In this paper we consider repairable dynamic fault trees. Dynamic fault trees
(dfts [17, 43]) are a common and widely applied variant of fts, catering for
common dependability patterns such as spare management and causal dependencies. Repairs [6] are not only crucial in fault-tolerant and resilient systems,
they are also an important cost driver. Hence, repairable fault trees allow one to
compare different repair strategies with respect to various dependability metrics.
Fault tree analysis. The reliability/availability of a fault tree can be computed
via numerical methods, such as probabilistic model checking. This involves exhaustive explorations of state-based models such as interactive Markov chains
[40]. Since the number of states (i.e. system configurations) is exponential in the
number of tree elements, analysing large trees remains a challenge today [26, 1].
Moreover, numerical methods are usually restricted to exponential failure rates
and combinations thereof, like Erlang and acyclic phase type distributions [40].
Alternatively, fault trees can be analysed using (standard) Monte Carlo simulation (smc [22, 40, 38], aka statistical model checking). Here, a large number
of simulated system runs (samples) is produced. Reliability and availability are
then statistically estimated from the resulting sample set. Such sampling does
not involve storing the full state space so, although the result provided can only
be correct with a certain probability, smc is much more memory efficient than
numerical techniques. Furthermore, smc is not restricted to exponential probability distributions. However, a known bottleneck of smc are rare events: when
the event of interest has a low probability (which is typically the case in highly
reliable systems), millions of samples may be required to observe it. Producing
these samples can take a unacceptably long simulation time.
Rare event simulation. To alleviate this problem, the field of rare event simulation (res) provides techniques that reduce the number of samples [35]. The
two leading techniques are importance sampling and importance splitting.
Importance sampling tweaks the probabilities in a model, then computes the
metric of interest for the changed system, and finally adjusts the analysis results
to the original model [23, 33]. Unfortunately it has specific requirements on the
stochastic model: in particular, it is generally limited to Markov models.
Importance splitting, deployed in this paper, does not have this limitation.
Importance splitting relies on rare events that arise as a sequence of less rare
intermediate events [28, 2]. We exploit this fact by generating more (partial)
samples on paths where such intermediate events are observed. As a simple
example, consider a biased coin whose probability of heads is p = 1 /80. Suppose
we flip it eight times in a row, and say we are interested in observing at least
three heads. If heads comes up at the first flip (H) then we are on a promising
path. We can then clone (split) the current path H, generating e.g. 7 copies of it,
each clone evolving independently from the second flip onwards. Say one clone
observes three heads—the copied H plus two more. Then, this observation of
the rare event (three heads) is counted as 1 /7 rather than as 1 observation, to
C. E. Budde et al.
certain performance indicators. Two common metrics are system reliability—the
probability that there are no system failures during a given mission time—and
system availability—the average percentage of time that a system is operational.
In this paper we consider repairable dynamic fault trees. Dynamic fault trees
(dfts [17, 43]) are a common and widely applied variant of fts, catering for
common dependability patterns such as spare management and causal dependencies. Repairs [6] are not only crucial in fault-tolerant and resilient systems,
they are also an important cost driver. Hence, repairable fault trees allow one to
compare different repair strategies with respect to various dependability metrics.
Fault tree analysis. The reliability/availability of a fault tree can be computed
via numerical methods, such as probabilistic model checking. This involves exhaustive explorations of state-based models such as interactive Markov chains
[40]. Since the number of states (i.e. system configurations) is exponential in the
number of tree elements, analysing large trees remains a challenge today [26, 1].
Moreover, numerical methods are usually restricted to exponential failure rates
and combinations thereof, like Erlang and acyclic phase type distributions [40].
Alternatively, fault trees can be analysed using (standard) Monte Carlo simulation (smc [22, 40, 38], aka statistical model checking). Here, a large number
of simulated system runs (samples) is produced. Reliability and availability are
then statistically estimated from the resulting sample set. Such sampling does
not involve storing the full state space so, although the result provided can only
be correct with a certain probability, smc is much more memory efficient than
numerical techniques. Furthermore, smc is not restricted to exponential probability distributions. However, a known bottleneck of smc are rare events: when
the event of interest has a low probability (which is typically the case in highly
reliable systems), millions of samples may be required to observe it. Producing
these samples can take a unacceptably long simulation time.
Rare event simulation. To alleviate this problem, the field of rare event simulation (res) provides techniques that reduce the number of samples [35]. The
two leading techniques are importance sampling and importance splitting.
Importance sampling tweaks the probabilities in a model, then computes the
metric of interest for the changed system, and finally adjusts the analysis results
to the original model [23, 33]. Unfortunately it has specific requirements on the
stochastic model: in particular, it is generally limited to Markov models.
Importance splitting, deployed in this paper, does not have this limitation.
Importance splitting relies on rare events that arise as a sequence of less rare
intermediate events [28, 2]. We exploit this fact by generating more (partial)
samples on paths where such intermediate events are observed. As a simple
example, consider a biased coin whose probability of heads is p = 1 /80. Suppose
we flip it eight times in a row, and say we are interested in observing at least
three heads. If heads comes up at the first flip (H) then we are on a promising
path. We can then clone (split) the current path H, generating e.g. 7 copies of it,
each clone evolving independently from the second flip onwards. Say one clone
observes three heads—the copied H plus two more. Then, this observation of
the rare event (three heads) is counted as 1 /7 rather than as 1 observation, to