Fault Trees on a Diet: Automated Reduction by Graph Rewriting

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    6 Citations (Scopus)
    4 Downloads (Pure)

    Abstract

    Fault trees are a popular industrial technique for reliability modelling and analysis. Their extension with common reliability patterns, such as spare management, functional dependencies, and sequencing — known as dynamic fault trees (DFTs) — has an adverse effect on scalability, prohibiting the analysis of complex, industrial cases by, e.g., probabilistic model checkers. This paper presents a novel, fully automated reduction technique for DFTs. The key idea is to interpret DFTs as directed graphs and exploit graph rewriting to simplify them. We present a collection of rewrite rules, address their correctness, and give a simple heuristic to determine the order of rewriting. Experiments on a large set of benchmarks show substantial DFT simplifications, yielding state space reductions and timing gains of up to two orders of magnitude.
    Original languageEnglish
    Title of host publicationDependable Software Engineering: Theories, Tools, and Applications
    Subtitle of host publicationFirst International Symposium, SETTA 2015, Nanjing, China, November 4-6, 2015, Proceedings
    EditorsXuandong Li, Zhiming Liu, Wang Yi
    Place of PublicationCham, Switzerland
    PublisherSpringer
    Pages3-18
    Number of pages16
    ISBN (Electronic)978-3-319-25942-0
    ISBN (Print)978-3-319-25941-3
    DOIs
    Publication statusPublished - Nov 2015
    Event1st International Symposium on Dependable Software Engineering: Theories, Tools, and Applications, SETTA 2015 - Nanjing, China
    Duration: 4 Nov 20156 Nov 2015
    Conference number: 1

    Publication series

    NameLecture Notes in Computer Science
    PublisherSpringer Verlag
    Volume9409
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349
    NameLecture Notes in Programming and Software Engineering
    PublisherSpringer

    Conference

    Conference1st International Symposium on Dependable Software Engineering: Theories, Tools, and Applications, SETTA 2015
    Abbreviated titleSETTA
    CountryChina
    CityNanjing
    Period4/11/156/11/15

    Keywords

    • EWI-26418
    • EC Grant Agreement nr.: FP7/2007-2013
    • EC Grant Agreement nr.: FP7/318490
    • EC Grant Agreement nr.: FP7/318003
    • METIS-315006
    • Fault Trees
    • Reduction
    • IR-98387
    • Graph Transformation

    Fingerprint Dive into the research topics of 'Fault Trees on a Diet: Automated Reduction by Graph Rewriting'. Together they form a unique fingerprint.

  • Cite this

    Junges, S., Guck, D., Katoen, J. P., Rensink, A., & Stoelinga, M. I. A. (2015). Fault Trees on a Diet: Automated Reduction by Graph Rewriting. In X. Li, Z. Liu, & W. Yi (Eds.), Dependable Software Engineering: Theories, Tools, and Applications: First International Symposium, SETTA 2015, Nanjing, China, November 4-6, 2015, Proceedings (pp. 3-18). (Lecture Notes in Computer Science; Vol. 9409), (Lecture Notes in Programming and Software Engineering). Cham, Switzerland: Springer. https://doi.org/10.1007/978-3-319-25942-0_1