Fault Trees on a Diet: Automated Reduction by Graph Rewriting

Research output: Chapter in Book/Report/Conference proceedingConference contribution

  • 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.
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
StatePublished - 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. 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. 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. 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.

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 contribution

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

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). Available from, DOI: 10.1007/978-3-319-25942-0_1