A Compositional Semantics of Boolean-Logic Driven Markov Processes

IEEE Transactions on Dependable and Secure Computing, vol. 21, pp. 701–716

Abstract

Boolean-logic driven Markov processes (BDMPs) is a prominent dynamic extension of static fault trees to model repairable and complex dynamic systems. While BDMPs are intensively used in an industrial context for dependability analysis of energy systems, its formal semantics has not been systematically treated. To date, BDMPs are defined as a library of the domain-specific dependability-modelling language Figaro, a library that is neither open source nor publicly available. A rigorous semantic underpinning of BDMPs is indispensable for (1) developing BDMP analysis tools and (2) comparing its expressive power to other related reliability modelling languages. This paper presents a formal semantics to BDMPs using Markov automata (MA), an extension of continuous-time Markov chains (CTMCs) with action transitions that can be used to compose complex MA from smaller MA. This enables us to provide a compositional semantics. That is, we express the semantics of each individual BDMP element as an MA and obtain the MA for the entire BDMP by combining the MA of its elements. This makes the semantics comprehensible, for those who are familiar with automata theory, and easily extensible with new BDMP elements, e.g., to model security aspects. After the entire BDMP is considered, the actions in its MA that were used to “glue” the MA of BDMP elements, are ignored. This results in a CTMC that is amenable to exact numerical analysis by, e.g., efficient probabilistic model-checking techniques. We report on a prototypical implementation of our semantics and empirically show that our semantics yields dependability metrics that correspond to the interpretation by the Figaro knowledge base of BDMPs.

Authors 3

1. Shahid Ali Khan Aachen Department of Computer Science

   RWTH Aachen University

   Affiliation as printed

   Department of Computer Science, RWTH Aachen University, Aachen, Germany

2. Joost-Pieter Katoen Aachen Department of Computer Science

   RWTH Aachen University

   Affiliation as printed

   Department of Computer Science, RWTH Aachen University, Aachen, Germany

3. Marc Bouissou

   Électricité de France (France)

   Affiliation as printed

   EDF-R&D, Electricité de-PSPACEAU-France Palaiseau, Palaiseau, France