Fault Trees on a Diet: Automated Reduction by Graph Rewriting

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

    5 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

    Fingerprint

    Nutrition
    Directed graphs
    Scalability
    Experiments

    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

    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
    Junges, Sebastian ; Guck, Dennis ; Katoen, Joost P. ; Rensink, Arend ; Stoelinga, Mariëlle Ida Antoinette. / Fault Trees on a Diet : Automated Reduction by Graph Rewriting. Dependable Software Engineering: Theories, Tools, and Applications: First International Symposium, SETTA 2015, Nanjing, China, November 4-6, 2015, Proceedings. editor / Xuandong Li ; Zhiming Liu ; Wang Yi. Cham, Switzerland : Springer, 2015. pp. 3-18 (Lecture Notes in Computer Science). (Lecture Notes in Programming and Software Engineering).
    @inproceedings{a26d669b7e40475fa4de83ebdb4d8a54,
    title = "Fault Trees on a Diet: Automated Reduction by Graph Rewriting",
    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.",
    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",
    author = "Sebastian Junges and Dennis Guck and Katoen, {Joost P.} and Arend Rensink and Stoelinga, {Mari{\"e}lle Ida Antoinette}",
    note = "Foreground = 20{\%}; Type of activity = conference; Main leader = UT; Type of audience = scientific community; Size of audience = 40; Countries addressed = international;",
    year = "2015",
    month = "11",
    doi = "10.1007/978-3-319-25942-0_1",
    language = "English",
    isbn = "978-3-319-25941-3",
    series = "Lecture Notes in Computer Science",
    publisher = "Springer",
    pages = "3--18",
    editor = "Xuandong Li and Zhiming Liu and Wang Yi",
    booktitle = "Dependable Software Engineering: Theories, Tools, and Applications",

    }

    Junges, S, Guck, D, Katoen, JP, Rensink, A & Stoelinga, MIA 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. Lecture Notes in Computer Science, vol. 9409, Lecture Notes in Programming and Software Engineering, Springer, Cham, Switzerland, pp. 3-18, 1st International Symposium on Dependable Software Engineering: Theories, Tools, and Applications, SETTA 2015, Nanjing, China, 4/11/15. https://doi.org/10.1007/978-3-319-25942-0_1

    Fault Trees on a Diet : Automated Reduction by Graph Rewriting. / Junges, Sebastian; Guck, Dennis; Katoen, Joost P.; Rensink, Arend; Stoelinga, Mariëlle Ida Antoinette.

    Dependable Software Engineering: Theories, Tools, and Applications: First International Symposium, SETTA 2015, Nanjing, China, November 4-6, 2015, Proceedings. ed. / Xuandong Li; Zhiming Liu; Wang Yi. Cham, Switzerland : Springer, 2015. p. 3-18 (Lecture Notes in Computer Science; Vol. 9409), (Lecture Notes in Programming and Software Engineering).

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

    TY - GEN

    T1 - Fault Trees on a Diet

    T2 - Automated Reduction by Graph Rewriting

    AU - Junges, Sebastian

    AU - Guck, Dennis

    AU - Katoen, Joost P.

    AU - Rensink, Arend

    AU - Stoelinga, Mariëlle Ida Antoinette

    N1 - Foreground = 20%; Type of activity = conference; Main leader = UT; Type of audience = scientific community; Size of audience = 40; Countries addressed = international;

    PY - 2015/11

    Y1 - 2015/11

    N2 - 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.

    AB - 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.

    KW - EWI-26418

    KW - EC Grant Agreement nr.: FP7/2007-2013

    KW - EC Grant Agreement nr.: FP7/318490

    KW - EC Grant Agreement nr.: FP7/318003

    KW - METIS-315006

    KW - Fault Trees

    KW - Reduction

    KW - IR-98387

    KW - Graph Transformation

    U2 - 10.1007/978-3-319-25942-0_1

    DO - 10.1007/978-3-319-25942-0_1

    M3 - Conference contribution

    SN - 978-3-319-25941-3

    T3 - Lecture Notes in Computer Science

    SP - 3

    EP - 18

    BT - Dependable Software Engineering: Theories, Tools, and Applications

    A2 - Li, Xuandong

    A2 - Liu, Zhiming

    A2 - Yi, Wang

    PB - Springer

    CY - Cham, Switzerland

    ER -

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