Reduction Methods on Error-Propagation Graphs for Quantitative Systems Reliability Analysis

Clemens DubslaffClemens Dubslaff, Andrey MorozovAndrey Morozov, Christel BaierChristel Baier, Klaus JanschekKlaus Janschek

Clemens Dubslaff, Andrey Morozov, Christel Baier, Klaus Janschek
Reduction Methods on Error-Propagation Graphs for Quantitative Systems Reliability Analysis
Proc. of 30th European Safety and Reliability Conference (ESREL) and 15th Probabilistic Safety Assessment and Management Conference (PSAM), 2020

Details
Bibtex

KurzfassungAbstract
Modern safety-critical systems are heterogeneous, complex, and highly dynamic. They require reliability evaluation methods that go beyond the classical static methods such as fault trees, event trees, or reliability block diagrams. Promising dynamic reliability analysis methods employ probabilistic model checking on various probabilistic statebased models. However, such methods have to tackle the well-known state-space explosion problem. To compete with this problem, reduction methods such as symmetry reduction and partial-order reduction have been successfully applied to probabilistic models by means of discrete Markov chains or Markov decision processes. Such models are usually specified using probabilistic programs provided in guarded command language. In this paper, we propose two automated reduction methods for probabilistic programs that operate on a purely syntactic level: reset value optimization and register allocation optimization. The presented techniques rely on concepts well known from compiler construction such as live range analysis and register allocation through interference graph coloring. Applied on a redundancy system model for an aircraft velocity control loop modeled in SIMULINK, we show effectiveness of our implementation of the reduction methods. We demonstrate that model-size reductions in three orders of magnitude are possible and show that we can achieve significant speedups for a reliability analysis.
Weitere Informationen unter:Further Information: Link
Forschungsgruppe:Research Group: Algebraische und logische Grundlagen der InformatikAlgebraic and Logical Foundations of Computer Science

@inproceedings{DMBJ2020,
  author    = {Clemens Dubslaff and Andrey Morozov and Christel Baier and Klaus
               Janschek},
  title     = {Reduction Methods on Error-Propagation Graphs for Quantitative
               Systems Reliability Analysis},
  booktitle = {Proc. of 30th European Safety and Reliability Conference (ESREL)
               and 15th Probabilistic Safety Assessment and Management
               Conference (PSAM)},
  year      = {2020}
}