×

zbMATH — the first resource for mathematics

Fault trees on a diet: automated reduction by graph rewriting. (English) Zbl 1370.68063
Summary: 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.
MSC:
68P05 Data structures
68M15 Reliability, testing and fault tolerance of networks and computer systems
68Q42 Grammars and rewriting systems
94C12 Fault detection; testing in circuits and networks
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Arnold F, Belinfante A, van der Berg F, Guck D, Stoelinga MIA (2013) DFTCalc: a tool for efficient fault tree analysis. In: Proc of SAFECOMP, LNCS. Springer, Berlin, pp 293-301.
[2] Bozzano, M; Cimatti, A; Katoen, J-P; Nguyen, VY; Noll, T; Roveri, M, Safety, dependability and performance analysis of extended AADL models, Comput J, 54, 754-775, (2011)
[3] Boudali, H; Crouzen, P; Stoelinga, MIA, A rigorous, compositional, and extensible framework for dynamic fault tree analysis, IEEE Trans Dependable Secur Comput, 7, 128-143, (2010)
[4] Boudali, H; Dugan, JB, A discrete-time Bayesian network reliability modeling and analysis framework, Reliab Eng Syst Safety, 87, 337-349, (2005)
[5] Boudali, H; Dugan, JB, A continuous-time Bayesian network reliability modeling and analysis framework, IEEE Trans Reliab, 55, 86-97, (2006)
[6] Bobbio, A; Franceschinis, G; Gaeta, R; Portinale, L, Parametric fault tree for the dependability analysis of redundant systems and its high-level Petri net semantics, IEEE Trans Softw Eng, 29, 270-287, (2003)
[7] Baier, C; Haverkort, BR; Hermanns, H; Katoen, J-P, Model-checking algorithms for continuous-time Markov chains, IEEE Trans Softw Eng, 29, 524-541, (2003) · Zbl 0974.68017
[8] Bobbio, A; Portinale, L; Minichino, M; Ciancamerla, E, Improving the analysis of dependable systems by mapping fault trees into Bayesian networks, Reliab Eng Syst Safety, 71, 249-260, (2001)
[9] Buchacker K (2000) Modeling with extended fault trees. In: Proc of HASE, pp 238-246
[10] Chiacchio, F; Compagno, L; D’Urso, D; Manno, G; Trapani, N, Dynamic fault trees resolution: a conscious trade-off between analytical and simulative approaches, Reliab Eng Syst Safety, 96, 1515-1526, (2011)
[11] Contini S, Cojazzi GGM, Renda G (2008) On the use of non-coherent fault trees in safety and security studies. In: Proc European safety and reliability conf (ESREL), pp 1886-1895
[12] Crouzen P, Hermanns H, Zhang L (2008) On the minimisation of acyclic models. In: CONCUR, vol 5201 of LNCS. Springer, Berlin, pp 295-309 · Zbl 1160.68462
[13] Coppit D, Sullivan KJ, Dugan JB (2000) Formal semantics of models for computational engineering: a case study on dynamic fault trees. In: Proc of ISSRE, pp 270-282
[14] Dugan, JB; Bavuso, SJ; Boyd, MA, Dynamic fault-tree models for fault-tolerant computer systems, IEEE Trans Reliab, 41, 363-377, (1992) · Zbl 0825.68162
[15] Dershowitz N, Jouannaud J-P (1991) Rewrite systems. In: van Leeuwen J (ed) Handbook of theoretical computer science. MIT Press, Cambridge, pp 243-320 · Zbl 0825.68162
[16] Dugan JB, Venkataraman B, Gulati R (1997) DIFtree: a software package for the analysis of dynamic fault tree models. In: Proc of RAMS, IEEE, pp 64-70
[17] Ehrig H, Ehrig K, Prange U, Taentzer G (2006) Fundamentals of algebraic graph transformation. Monographs in Th. Comp. Science. Springer, Berlin · Zbl 1095.68047
[18] Ehrig H (1979) Introduction to the algebraic theory of graph grammars (a survey). In: Ng EW, Ehrig H, Rozenberg G (eds) Graph-grammars and their application to computer science and biology, vol 73 of LNCS. Springer, Berlin, pp 1-69
[19] Ehrig H, Pfender M, Schneider HJ (1973) Graph-grammars: an algebraic approach. In: 14th annual symposium on switching and automata theory, IEEE Computer Society, pp 167-180
[20] Ghamarian, AH; Mol, M; Rensink, A; Zambon, E; Zimakova, M, Modelling and analysis using GROOVE, STTT, 14, 15-40, (2012)
[21] Guck D, Hatefi H, Hermanns H, Katoen J-P, Timmer M (2014) Analysis of timed and long-run objectives for Markov automata. Logical Methods Comput Sci 10(3:17):1-29 (2014) · Zbl 1342.68135
[22] Guck D, Katoen J-P, Stoelinga MIA, Luiten T, Romijn JMT. (2014) Smart railroad maintenance engineering with stochastic model checking. In: Proc of RAILWAYS. Saxe-Coburg Publications
[23] Garavel, H; Lang, F; Mateescu, R; Serwe, W, CADP 2011: a toolbox for the construction and analysis of distributed processes, STTT, 15, 89-107, (2013) · Zbl 1316.68074
[24] Heckel, R, Graph transformation in a nutshell, Electr Notes Theor Comput Sci, 148, 187-198, (2006)
[25] Hermanns H (2002) Interactive Markov chains: the quest for quantified quality, vol 2428 of LNCS. Springer, Berlin · Zbl 1012.68142
[26] Han W, Guo W, Hou Z (2011) Research on the method of dynamic fault tree analysis. In: Proc of ICRMS, pp 950-953
[27] IEC 61025 International Standard:FaultTreeAnalysis. 2nd edn, 2006-12,Reference number IEC61025:2006(E). International Electrotechnical Commission, Geneva, Switzerland · Zbl 1315.90013
[28] Junges S, Guck D, Katoen J-P, Rensink A, Stoelinga M (2015) Fault trees on a diet—automated reduction by graph rewriting. In: Proc of SETTA, vol 9409 of LNCS. Springer, Berlin, pp 3-18 · Zbl 1369.68172
[29] Junges S, Guck D, Katoen J-P, Stoelinga M (2016) Uncovering dynamic fault trees. In: Proc of DSN, IEEE · Zbl 1272.68174
[30] Junges S (2015) Simplifying dynamic fault trees by graph rewriting. Master Thesis, RWTH Aachen University.
[31] Kaiser B (2005) Extending the expressive power of fault trees. In: Proc of RAMS, IEEE, January, pp 468-474
[32] Katoen, J-P; Zapreev, IS; Hahn, EM; Hermanns, H; Jansen, DN, The ins and outs of the probabilistic model checker MRMC, Perform Eval, 68, 90-104, (2011)
[33] Liu D, Xiong L, Li Z, Wang P, Zhang H (2010) The simplification of cut sequence set analysis for dynamic systems. In: Proc of ICCAE, vol 3, pp 140-144
[34] Montani S, Portinale L, Bobbio A, Codetta-Raiteri, D (2006) Automatically translating dynamic fault trees into dynamic Bayesian networks by means of a software tool. In: Proc of ARES, pp 6
[35] Merle G, Roussel J-M (2007) Algebraic modelling of fault trees with priority AND gates. In: Proc of DCDS, pp 175-180
[36] Merle G, Roussel J-M, Lesage J-J (2010) Improving the efficiency of dynamic fault tree analysis by considering gate FDEP as static. In: Proc European safety and reliability conf. (ESREL), pp 845-851
[37] Merle, G; Roussel, J-M; Lesage, J-J; Bobbio, A, Probabilistic algebraic analysis of fault trees with priority dynamic gates and repeated events, IEEE Trans Reliab, 59, 250-261, (2010)
[38] Malhotra, M; Trivedi, KS, Dependability modeling using Petri-nets, IEEE Trans Reliab, 44, 428-440, (1995)
[39] Neuts MF (1994) Matrix-geometric solutions in stochastic models—an algorithmic approach. Dover Publications, Mineola
[40] Pullum LL, Dugan JB (1996) Fault tree models for the analysis of complex computer-based systems. In: Proc of RAMS, IEEE, pp 200-207
[41] Pulungan R, Hermanns H (2008) Effective minimization of acyclic phase-type representations. In: ASMTA, vol 5055 of LNCS. Springer, Berlin, pp 128-143
[42] Raiteri, DC, The conversion of dynamic fault trees to stochastic Petri nets, as a case of graph transformation, ENTCS, 127, 45-60, (2005) · Zbl 1272.68174
[43] Rongxing D, Guochun W, Decun D (2010) A new assessment method for system reliability based on dynamic fault tree. In: Proc of ICICTA, IEEE, pp 219-222
[44] Ruijters, E; Stoelinga, MIA, Fault tree analysis: a survey of the state-of-the-art in modeling, analysis and tools, Comput Sci Rev, 15, 29-62, (2015) · Zbl 1315.90013
[45] Schneier B (1999) Attack trees: modeling security threats. Dr. Dobb’s J 24(12):21-29
[46] Sullivan KJ, Dugan JB, Coppit D (1999) The Galileo fault tree analysis tool. In: Proc of Int Symp on fault-tolerant computing, pp 232-235
[47] Stamatelatos M, Vesely W, Dugan JB, Fragola J, Minarick J, Railsback J (2002) Fault tree handbook with aerospace applications. NASA Headquarters
[48] Yevkin O 2011 An improved modular approach for dynamic fault tree analysis. In: Proc of RAMS, pp 1-5
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.