BDDs Strike Back: Efficient Analysis of Static and Dynamic Fault Trees

arXiv (Cornell University)

Abstract

Fault trees are a key model in reliability analysis. Classical static fault trees (SFT) can best be analysed using binary decision diagrams (BDD). State-based techniques are favorable for the more expressive dynamic fault trees (DFT). This paper combines the best of both worlds by following Dugan's approach: dynamic sub-trees are analysed via model checking Markov models and replaced by basic events capturing the obtained failure probabilities. The resulting SFT is then analysed via BDDs. We implemented this approach in the Storm model checker. Extensive experiments (a) compare our pure BDD-based analysis of SFTs to various existing SFT analysis tools, (b) indicate the benefits of our efficient calculations for multiple time points and the assessment of the mean-time-to-failure, and (c) show that our implementation of Dugan's approach significantly outperforms pure Markovian analysis of DFTs. Our implementation Storm-dft is currently the only tool supporting efficient analysis for both SFTs and DFTs.

Authors 4

1. Daniel Basgöze Aachen Software Modeling and Verification

   RWTH Aachen University

   Affiliation as printed

   Software Modeling and Verification , RWTH Aachen University , Aachen , Germany

2. Matthias Volk

   University of Twente

   Affiliation as printed

   Formal Methods and Tools , University of Twente , Enschede , The Netherlands

3. Joost-Pieter Katoen Aachen Software Modeling and Verification

   RWTH Aachen University · University of Twente

   Affiliation as printed

   Formal Methods and Tools , University of Twente , Enschede , The Netherlands

   Software Modeling and Verification , RWTH Aachen University , Aachen , Germany

4. Mariëlle I. A. Stoelinga

   Radboud University Nijmegen · University of Twente

   Affiliation as printed

   Department of Software Science , Radboud University , Nijmegen , The Netherlands

   Formal Methods and Tools , University of Twente , Enschede , The Netherlands