Fault Trees on a Diet - Automated Reduction by Graph Rewriting

  • 5 Citations

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 languageUndefined
Title of host publicationProceedings of the First International Symposium on Dependable Software Engineering: Theories, Tools, and Applications (SETTA 2015)
EditorsXuandong Li, Zhiming Liu, Wang Yi
Place of PublicationBerlin
PublisherSpringer Verlag
Pages3-18
Number of pages16
ISBN (Print)978-3-319-25941-3
DOIs
StatePublished - Nov 2015

Publication series

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

Fingerprint

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.), Proceedings of the First International Symposium on Dependable Software Engineering: Theories, Tools, and Applications (SETTA 2015) (pp. 3-18). (Lecture Notes in Computer Science; Vol. 9409). Berlin: Springer Verlag. DOI: 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.

Proceedings of the First International Symposium on Dependable Software Engineering: Theories, Tools, and Applications (SETTA 2015). ed. / Xuandong Li; Zhiming Liu; Wang Yi. Berlin : Springer Verlag, 2015. p. 3-18 (Lecture Notes in Computer Science; Vol. 9409).

Research output: Scientific - peer-reviewConference contribution

@inbook{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ë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",
isbn = "978-3-319-25941-3",
series = "Lecture Notes in Computer Science",
publisher = "Springer Verlag",
pages = "3--18",
editor = "Xuandong Li and Zhiming Liu and Wang Yi",
booktitle = "Proceedings of the First International Symposium on Dependable Software Engineering: Theories, Tools, and Applications (SETTA 2015)",

}

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), Proceedings of the First International Symposium on Dependable Software Engineering: Theories, Tools, and Applications (SETTA 2015). Lecture Notes in Computer Science, vol. 9409, Springer Verlag, Berlin, pp. 3-18. DOI: 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.

Proceedings of the First International Symposium on Dependable Software Engineering: Theories, Tools, and Applications (SETTA 2015). ed. / Xuandong Li; Zhiming Liu; Wang Yi. Berlin : Springer Verlag, 2015. p. 3-18 (Lecture Notes in Computer Science; Vol. 9409).

Research output: Scientific - peer-reviewConference contribution

TY - CHAP

T1 - Fault Trees on a Diet - 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 - Proceedings of the First International Symposium on Dependable Software Engineering: Theories, Tools, and Applications (SETTA 2015)

PB - Springer Verlag

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, Proceedings of the First International Symposium on Dependable Software Engineering: Theories, Tools, and Applications (SETTA 2015). Berlin: Springer Verlag. 2015. p. 3-18. (Lecture Notes in Computer Science). Available from, DOI: 10.1007/978-3-319-25942-0_1