Reduction methods on probabilistic control-flow programs for reliability analysis

Research output: Contribution to book/Conference proceedings/Anthology/ReportConference contributionContributedpeer-review

Abstract

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 state-based 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.

Details

Original languageEnglish
Title of host publication30th European Safety and Reliability Conference, ESREL 2020 and 15th Probabilistic Safety Assessment and Management Conference, PSAM 2020
EditorsPiero Baraldi, Francesco Di Maio, Enrico Zio
PublisherResearch Publishing Services
Pages4843-4850
Number of pages8
ISBN (electronic)9789811485930
ISBN (print)978-981-14-8593-0
Publication statusPublished - 2020
Peer-reviewedYes

Publication series

SeriesEuropean Safety and Reliability Conference (ESREL)
Volume2020

Conference

Title30th European Safety and Reliability Conference and 15th Probabilistic Safety Assessment and Management Conference
Abbreviated titleESREL2020 PSAM15
Conference number
Duration1 - 5 November 2020
Degree of recognitionInternational event
Location
CityVenice
CountryItaly

External IDs

ORCID /0000-0002-5321-9343/work/142236707
Bibtex dubslaff+morozov++2020_reduction
Scopus 85085697621
Scopus 85110293718

Keywords

Keywords

  • Cyber-physical systems, Model-based stochastic analysis, Probabilistic model checking, Reduction methods, Register allocation, SIMULINK