RES for non-Markovian repairable fault trees
465
account for the splitting where the clone was spawned. Now, if a clone observes
a new head (HH), this is even more promising than H, so the splitting can be
repeated. If we make 5 copies of the HH clone, then observing three heads in any
of these copies counts as
1
35 =
1
7 ·
1
5 . Alternatively, observing tails as second flip
(HT ) is less promising than heads. One could then decide not to split such path.
This example highlights a key ingredient of importance splitting: the importance function, that indicates for each state how promising it is w.r.t. the event
of interest. This function, together with other parameters such as thresholds [19],
are used to choose e.g. the number of clones spawned when visiting a state. An
importance function for our example could be the number of heads seen thus far.
Another one could be such number, multiplied by the number of coin flips yet to
come. The goal is to give higher importance to states from which observing the
rare event is more likely. The efficiency of an importance splitting implementation increases as the importance function better reflects such property.
Rare event simulation has been successfully applied in several domains [34,
45, 49, 4, 5, 46]. However, a key bottleneck is that it critically relies on expert
knowledge. In particular for importance splitting, finding a good importance
function is a well-known highly non-trivial task [35, 25].
Our contribution: rare event simulation for fault trees. This paper presents an importance splitting method to analyse rfts. In particular, we automatically derive an importance function by exploiting the description of a system
as a fault tree. This is crucial, since the importance function is normally given
manually in an ad hoc fashion by a domain or res expert. We use a variety
of res algorithms based in our importance function, to estimate system unreliability and unavailability. Our approach can converge to precise estimations
in increasingly reliable systems. This method has four advantages over earlier
analysis methods for rfts—which we overview in the related work section 6—
namely: (1) we are able to estimate both the system reliability and availability;
(2) we can handle arbitrary failure and repair distributions; (3) we can handle
rare events; and (4) we can do it in a fully automatic fashion.
Technically, we build local importance functions for the (automata-semantics
of the) nodes of the tree. We then aggregate these local functions into an importance function for the full tree. Aggregation uses structural induction in the
layered description of the tree. Using our importance function, we implement
importance splitting methods to run res analyses. We implemented our theory
in a full-stack tool chain. With it, we computed confidence intervals for the unreliability and unavailability of several case studies. Our case studies are rfts
whose failure and repair times are governed by arbitrary continuous probability
density functions (pdfs). Each case study was analysed for a fixed runtime budget and in increasingly resilient configurations. In all cases our approach could
estimate the narrowest intervals for the most resilient configurations.
Paper outline. Background on fault trees and res is provided in Secs. 2 and 3.
We detail our theory to implement res for rfts in Sec. 4. Using a tool chain,
we performed an extensive experimental evaluation that we present in Sec. 5.
We overview related work in Sec. 6 and conclude our contributions in Sec. 7.
465
account for the splitting where the clone was spawned. Now, if a clone observes
a new head (HH), this is even more promising than H, so the splitting can be
repeated. If we make 5 copies of the HH clone, then observing three heads in any
of these copies counts as
1
35 =
1
7 ·
1
5 . Alternatively, observing tails as second flip
(HT ) is less promising than heads. One could then decide not to split such path.
This example highlights a key ingredient of importance splitting: the importance function, that indicates for each state how promising it is w.r.t. the event
of interest. This function, together with other parameters such as thresholds [19],
are used to choose e.g. the number of clones spawned when visiting a state. An
importance function for our example could be the number of heads seen thus far.
Another one could be such number, multiplied by the number of coin flips yet to
come. The goal is to give higher importance to states from which observing the
rare event is more likely. The efficiency of an importance splitting implementation increases as the importance function better reflects such property.
Rare event simulation has been successfully applied in several domains [34,
45, 49, 4, 5, 46]. However, a key bottleneck is that it critically relies on expert
knowledge. In particular for importance splitting, finding a good importance
function is a well-known highly non-trivial task [35, 25].
Our contribution: rare event simulation for fault trees. This paper presents an importance splitting method to analyse rfts. In particular, we automatically derive an importance function by exploiting the description of a system
as a fault tree. This is crucial, since the importance function is normally given
manually in an ad hoc fashion by a domain or res expert. We use a variety
of res algorithms based in our importance function, to estimate system unreliability and unavailability. Our approach can converge to precise estimations
in increasingly reliable systems. This method has four advantages over earlier
analysis methods for rfts—which we overview in the related work section 6—
namely: (1) we are able to estimate both the system reliability and availability;
(2) we can handle arbitrary failure and repair distributions; (3) we can handle
rare events; and (4) we can do it in a fully automatic fashion.
Technically, we build local importance functions for the (automata-semantics
of the) nodes of the tree. We then aggregate these local functions into an importance function for the full tree. Aggregation uses structural induction in the
layered description of the tree. Using our importance function, we implement
importance splitting methods to run res analyses. We implemented our theory
in a full-stack tool chain. With it, we computed confidence intervals for the unreliability and unavailability of several case studies. Our case studies are rfts
whose failure and repair times are governed by arbitrary continuous probability
density functions (pdfs). Each case study was analysed for a fixed runtime budget and in increasingly resilient configurations. In all cases our approach could
estimate the narrowest intervals for the most resilient configurations.
Paper outline. Background on fault trees and res is provided in Secs. 2 and 3.
We detail our theory to implement res for rfts in Sec. 4. Using a tool chain,
we performed an extensive experimental evaluation that we present in Sec. 5.
We overview related work in Sec. 6 and conclude our contributions in Sec. 7.