Fault Trees on a Diet - Automated Reduction by Graph Rewriting
Title | Fault Trees on a Diet - Automated Reduction by Graph Rewriting |
Publication Type | Conference Paper |
Year of Publication | 2015 |
Authors | Junges S., Guck D., Katoen J.P, Rensink A., Stoelinga M.IA |
Editor | Li X., Liu Z., Yi W. |
Conference Name | Proceedings of the First International Symposium on Dependable Software Engineering: Theories, Tools, and Applications (SETTA 2015), Nanjing, China |
Date Published | November |
Publisher | Springer Verlag |
Conference Location | Berlin |
Keywords | Fault Trees, Graph Transformation, Reduction |
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. |
DOI | 10.1007/978-3-319-25942-0_1 |