Fault Trees on a Diet - Automated Reduction by Graph Rewriting

TitleFault Trees on a Diet - Automated Reduction by Graph Rewriting
Publication TypeConference Paper
Year of Publication2015
AuthorsJunges S., Guck D., Katoen J.P, Rensink A., Stoelinga M.IA
EditorLi X., Liu Z., Yi W.
Conference NameProceedings of the First International Symposium on Dependable Software Engineering: Theories, Tools, and Applications (SETTA 2015), Nanjing, China
Date PublishedNovember
PublisherSpringer Verlag
Conference LocationBerlin
KeywordsFault Trees, Graph Transformation, Reduction

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.