Fault trees on a diet: automated reduction by graph rewriting

TitleFault trees on a diet: automated reduction by graph rewriting
Publication TypeJournal Article
Year of Publication2017
AuthorsJunges S., Guck D., Katoen J.P, Rensink A., Stoelinga M.IA
JournalFormal Aspects of Computing
Volumeonline pre-publication
Date PublishedJanuary

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