Rare event simulation for
non-Markovian repairable fault trees
Carlos E. Budde
1 , Marco Biagi
2 , Raúl E. Monti
1 ,
Pedro R. D’Argenio
3,4,5 , and Mariëlle Stoelinga
1,6
1 Formal Methods and Tools, University of Twente, Enschede, the Netherlands
2 Department of Information Engineering, University of Florence, Florence, Italy
3 FAMAF, Universidad Nacional de Córdoba, Córdoba, Argentina
4 CONICET, Córdoba, Argentina
5 Department of Computer Science, Saarland University, Saarbrücken, Germany
6 Department of Software Science, Radboud University, Nijmegen, the Netherlands
Abstract. Dynamic fault trees (dft) are widely adopted in industry
to assess the dependability of safety-critical equipment. Since many systems are too large to be studied numerically, dfts dependability is often
analysed using Monte Carlo simulation. A bottleneck here is that many
simulation samples are required in the case of rare events, e.g. in highly
reliable systems where components fail seldomly. Rare event simulation
(res) provides techniques to reduce the number of samples in the case of
rare events. We present a res technique based on importance splitting,
to study failures in highly reliable dfts. Whereas res usually requires
meta-information from an expert, our method is fully automatic: By
cleverly exploiting the fault tree structure we extract the so-called importance function. We handle dfts with Markovian and non-Markovian
failure and repair distributions—for which no numerical methods exist—
and show the efficiency of our approach on several case studies.
1 Introduction
Reliability engineering is an important field that provides methods and tools
to assess and mitigate the risks related to complex systems. Fault tree analysis (fta) is a prominent technique here. Its application encompasses a large
number of industrial domains that range from automotive and aerospace system
engineering, to energy and telecommunication systems and protocols.
Fault trees. A fault tree (ft) describes how component failures occur and
propagate through the system, eventually leading to system failures. Technically,
an ft is a directed acyclic graph whose leaves model component failures, and
whose other nodes (called gates) model failure propagation. Using fault trees
one can compute dependability metrics to quantify how a system fares w.r.t.
$ This work was partially funded by NWO, NS, and ProRail project 15474 (SEQUOIA), ERC grant 695614 (POWVER), EU project 102112 (SUCCESS), ANPCyT
PICT-2017-3894 (RAFTSys), and SeCyT project 33620180100354CB (ARES).
The Author(s) 2020
A. Biere and D. Parker (Eds.): TACAS 2020, LNCS 12078, pp. 463–482, 2020.
https://doi.org/10.1007/978-3-030-45190-5_26
$
non-Markovian repairable fault trees
Carlos E. Budde
1 , Marco Biagi
2 , Raúl E. Monti
1 ,
Pedro R. D’Argenio
3,4,5 , and Mariëlle Stoelinga
1,6
1 Formal Methods and Tools, University of Twente, Enschede, the Netherlands
2 Department of Information Engineering, University of Florence, Florence, Italy
3 FAMAF, Universidad Nacional de Córdoba, Córdoba, Argentina
4 CONICET, Córdoba, Argentina
5 Department of Computer Science, Saarland University, Saarbrücken, Germany
6 Department of Software Science, Radboud University, Nijmegen, the Netherlands
Abstract. Dynamic fault trees (dft) are widely adopted in industry
to assess the dependability of safety-critical equipment. Since many systems are too large to be studied numerically, dfts dependability is often
analysed using Monte Carlo simulation. A bottleneck here is that many
simulation samples are required in the case of rare events, e.g. in highly
reliable systems where components fail seldomly. Rare event simulation
(res) provides techniques to reduce the number of samples in the case of
rare events. We present a res technique based on importance splitting,
to study failures in highly reliable dfts. Whereas res usually requires
meta-information from an expert, our method is fully automatic: By
cleverly exploiting the fault tree structure we extract the so-called importance function. We handle dfts with Markovian and non-Markovian
failure and repair distributions—for which no numerical methods exist—
and show the efficiency of our approach on several case studies.
1 Introduction
Reliability engineering is an important field that provides methods and tools
to assess and mitigate the risks related to complex systems. Fault tree analysis (fta) is a prominent technique here. Its application encompasses a large
number of industrial domains that range from automotive and aerospace system
engineering, to energy and telecommunication systems and protocols.
Fault trees. A fault tree (ft) describes how component failures occur and
propagate through the system, eventually leading to system failures. Technically,
an ft is a directed acyclic graph whose leaves model component failures, and
whose other nodes (called gates) model failure propagation. Using fault trees
one can compute dependability metrics to quantify how a system fares w.r.t.
$ This work was partially funded by NWO, NS, and ProRail project 15474 (SEQUOIA), ERC grant 695614 (POWVER), EU project 102112 (SUCCESS), ANPCyT
PICT-2017-3894 (RAFTSys), and SeCyT project 33620180100354CB (ARES).
The Author(s) 2020
A. Biere and D. Parker (Eds.): TACAS 2020, LNCS 12078, pp. 463–482, 2020.
https://doi.org/10.1007/978-3-030-45190-5_26
$