nach oben

Erschienen in:

2020 | OriginalPaper | Buchkapitel

Automated Rare Event Simulation for Fault Tree Analysis via Minimal Cut Sets

verfasst von : Carlos E. Budde, Mariëlle Stoelinga

Erschienen in: Measurement, Modelling and Evaluation of Computing Systems

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Monte Carlo simulation is a common technique to estimate dependability metrics for fault trees. A bottleneck in this technique is the number of samples needed, especially when the interesting events are rare and occur with low probability. Rare Event Simulation (

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-030-43024-5_16/492801_1_En_16_IEq1_HTML.gif

) reduces the number of samples when analysing rare events. Importance splitting is a

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-030-43024-5_16/492801_1_En_16_IEq2_HTML.gif

method that spawns more simulation runs from promising system states. How promising a state is, is indicated by an importance function, which concentrates the information that makes this method efficient. Importance functions are given by domain and

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-030-43024-5_16/492801_1_En_16_IEq3_HTML.gif

experts. This hinders re-utilisation and involves decisions entailing potential human error. Focusing in (general) fault trees, in this paper we automatically derive importance functions based on the tree structure. For this we exploit a common fault tree concept, namely cut sets: the more elements from a cut set have failed, the higher the importance. We show that the cut-set-derived importance function is an easy-to-implement and simple concept, that can nonetheless compete against another (more involved) automatic importance function for

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-030-43024-5_16/492801_1_En_16_IEq4_HTML.gif

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel A Tool for Requirements Analysis of Safety-Critical Cyber-Physical Systems

Nur mit Berechtigung zugänglich

This is given more thorough semantics in [3] via an output function \(\varvec{z}_i\).

This complements standard model checking, where time-bounded properties with large time bounds entail memory problems [25].

Bayes, A.J.: Statistical techniques for simulation models. Aust. Comput. J. 2(4), 180–184 (1970)

Budde, C.E.: Automation of importance splitting techniques for rare event simulation. Ph.D. thesis, Universidad Nacional de Córdoba, Córdoba, Argentina (2017)

Budde, C.E., Biagi, M., Monti, R.E., D’Argenio, P.R., Stoelinga, M.: Rare event simulation for non-Markovian repairable fault trees. In: TACAS 2020 (to appear)

Budde, C.E., D’Argenio, P.R., Hermanns, H.: Rare event simulation with fully automated importance splitting. In: Beltrán, M., Knottenbelt, W., Bradley, J. (eds.) EPEW 2015. LNCS, vol. 9272, pp. 275–290. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-23267-6_18CrossRef

Budde, C.E., D’Argenio, P.R., Monti, R.E.: Compositional construction of importance functions in fully automated importance splitting. In: VALUETOOLS. ICST (2016). https://doi.org/10.4108/eai.25-10-2016.2266501

Cérou, F., Del Moral, P., Furon, T., Guyader, A.: Sequential Monte Carlo for rare event estimation. Stat. Comput. 22(3), 795–808 (2012). https://doi.org/10.1007/s11222-011-9231-6MathSciNetCrossRefMATH

Crouzen, P., Boudali, H., Stoelinga, M.: Dynamic fault tree analysis using input/output interactive Markov chains. In: DSN 2007, pp. 708–717 (2007). https://doi.org/10.1109/DSN.2007.37

D’Argenio, P.R., Monti, R.E.: Input/output stochastic automata with urgency: confluence and weak determinism. In: Fischer, B., Uustalu, T. (eds.) ICTAC 2018. LNCS, vol. 11187, pp. 132–152. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-02508-3_8CrossRef

Garvels, M.J.J.: The splitting method in rare event simulation. Ph.D. thesis, University of Twente, Enschede, The Netherlands (2000)

10.

Heidelberger, P.: Fast simulation of rare events in queueing and reliability models. ACM Trans. Model. Comput. Simul. 5(1), 43–85 (1995). https://doi.org/10.1145/203091.203094CrossRefMATH

11.

Iglewicz, B., Hoaglin, D.: How to Detect and Handle Outliers. ASQC Basic References in Quality Control. ASQC Quality Press, Milwaukee (1993)

12.

Jegourel, C., Legay, A., Sedwards, S.: Importance splitting for statistical model checking rare properties. In: Sharygina, N., Veith, H. (eds.) CAV 2013. LNCS, vol. 8044, pp. 576–591. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-39799-8_38CrossRef

13.

Jégourel, C., Legay, A., Sedwards, S., Traonouez, L.M.: Distributed verification of rare properties using importance splitting observers. In: ECEASST, vol. 72 (2015). https://doi.org/10.14279/tuj.eceasst.72.1024

14.

Junges, S., Guck, D., Katoen, J., Stoelinga, M.: Uncovering dynamic fault trees. In: DSN 2016, pp. 299–310. IEEE (2016). https://doi.org/10.1109/DSN.2016.35

15.

Kahn, H., Harris, T.E.: Estimation of particle transmission by random sampling. Natl. Bur. Stand. Appl. Math. Ser. 12, 27–30 (1951)

16.

Law, A.M.: Simulation Modeling and Analysis. McGraw-Hill Education, New York (2014)

17.

L’Ecuyer, P., Le Gland, F., Lezaud, P., Tuffin, B.: Splitting techniques. In: Rubino and Tuffin [24], pp. 39–61. https://doi.org/10.1002/9780470745403.ch3CrossRef

18.

Lee, W., Grosh, D., Tillman, F., Lie, C.: Fault tree analysis, methods, and applications–a review. IEEE Trans. Reliab. R–34(3), 194–203 (1985). https://doi.org/10.1109/TR.1985.5222114CrossRefMATH

19.

Monti, R.E.: Stochastic automata for fault tolerant concurrent systems. Ph.D. thesis, Universidad Nacional de Córdoba, Argentina (2018)

20.

Monti, R.E., D’Argenio, P.R., Budde, C.E.: A compositional semantics for repairable fault trees with general distributions. arXiv e-prints arXiv:1910.10507 (2019)

21.

Nicola, V.F., Shahabuddin, P., Nakayama, M.K.: Techniques for fast simulation of models of highly dependable systems. IEEE Trans. Reliab. 50(3), 246–264 (2001). https://doi.org/10.1109/24.974122CrossRef

22.

Raiteri, D., Iacono, M., Franceschinis, G., Vittorini, V.: Repairable fault tree for the automatic evaluation of repair policies. In: DSN 2004, pp. 659–668 (2004). https://doi.org/10.1109/DSN.2004.1311936

23.

Rubino, G., Tuffin, B.: Introduction to rare event simulation. In: Rubino and Tuffin [24], pp. 1–13. https://doi.org/10.1002/9780470745403.ch1CrossRef

24.

Rubino, G., Tuffin, B. (eds.): Rare Event Simulation Using Monte Carlo Methods. Wiley, New York (2009). https://doi.org/10.1002/9780470745403CrossRefMATH

25.

Ruijters, E., Stoelinga, M.: Fault tree analysis: a survey of the state-of-the-art in modeling, analysis and tools. Comput. Sci. Rev. 15–16, 29–62 (2015). https://doi.org/10.1016/j.cosrev.2015.03.001MathSciNetCrossRefMATH

26.

Sullivan, K., Dugan, J.: Galileo user’s manual & design overview (1998). v2.1-alpha. https://www.cse.msu.edu/~cse870/Materials/FaultTolerant/manual-galileo.htm

27.

Sullivan, K., Dugan, J., Coppit, D.: The Galileo fault tree analysis tool. In: 29th Annual International Symposium on Fault-Tolerant Computing (Cat. No. 99CB36352), pp. 232–235 (1999). https://doi.org/10.1109/FTCS.1999.781056

28.

Vesely, W., Stamatelatos, M., Dugan, J., Fragola, J., Minarick, J., Railsback, J.: Fault tree handbook with aerospace applications. NASA Office of Safety and Mission Assurance, version 1.1 (2002)

29.

Villén-Altamirano, J.: RESTART method for the case where rare events can occur in retrials from any threshold. Int. J. Electron. Commun. 52, 183–189 (1998)

30.

Villén-Altamirano, J.: Importance functions for RESTART simulation of highly-dependable systems. Simulation 83(12), 821–828 (2007). https://doi.org/10.1177/0037549707081257CrossRef

31.

Villén-Altamirano, J.: RESTART vs splitting: a comparative study. Perform. Eval. 121–122, 38–47 (2018). https://doi.org/10.1016/j.peva.2018.02.002CrossRef

32.

Villén-Altamirano, M., Martínez-Marrón, A., Gamo, J., Fernández-Cuesta, F.: Enhancement of the accelerated simulation method RESTART by considering multiple thresholds. In: Proceedings of the 14th International Teletraffic Congress. Teletraffic Science and Engineering, vol. 1, pp. 797–810. Elsevier (1994). https://doi.org/10.1016/B978-0-444-82031-0.50084-6CrossRef

33.

Villén-Altamirano, M., Villén-Altamirano, J.: RESTART: a method for accelerating rare event simulations. In: Queueing, Performance and Control in ATM (ITC-13), pp. 71–76. Elsevier (1991)

Titel: Automated Rare Event Simulation for Fault Tree Analysis via Minimal Cut Sets
verfasst von: Carlos E. Budde
Mariëlle Stoelinga
Verlag: Springer International Publishing
Buch: Measurement, Modelling and Evaluation of Computing Systems
Print ISBN: 978-3-030-43023-8

Electronic ISBN: 978-3-030-43024-5

Copyright-Jahr: 2020
DOI: https://doi.org/10.1007/978-3-030-43024-5_16

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"