Abstract
Fault tree analysis is still widely practiced in high-hazard industries. We propose in this article an algorithm for the reduction of fault tree expressions that are generated from automata representations of failure behaviors. Automata formalisms are increasingly being used to describe systems exhibiting sequence-dependent failures—i.e., the overall outcome like a total failure of the system can depend on the order in which events occur. A set of paths leading to a safety-relevant state is encoded as a standard sum of product canonical form, and without any loss of the significance of the sequencing of events. That is, the corresponding fault tree expression is basically a Boolean formula which is extended with the necessary temporal features (event occurrence priority). Such expressions can then be reduced into minimal canonical forms by using the Boolean methods together with the required temporal logic calculus. Since minimal failure sequences can be determined from the obtained reduced models, the proposed approach can improve the analysis of the dynamic effects of the sequencing of faults and propagated errors in such models. As a consequence, it can have a positive impact on the design of failure prevention measures. A fault tolerant example system exhibiting dynamic behavior is used to highlight the benefits of the approach.
Similar content being viewed by others
References
Boudali, H., Crouzen, P., & Stoelinga, M. (2010). A rigorous, compositional, and extensible framework for dynamic fault tree analysis. Dependable and Secure Computing, IEEE Transactions on, 7(2), 128–143.
Chen, D., Mahmud, N., Walker, M., Feng, L., Lönn, H., & Papadopoulos, Y. (2013). Systems modeling with EAST-ADL for fault tree analysis through HiP-HOPS. In Proceedings of the 4th International Federation of Automatic Control (IFAC) Workshop on Dependable Control of Discrete Systems (DCDS), York, (pp. 91-96). IFAC
Crouzen, P., Hermanns, H., & Zhang, L. (2008). On the minimisation of acyclic models. In International conference on concurrency theory (pp. 295–309). Berlin Heidelberg: Springer.
Dehlinger, J., & Dugan, J. B. (2008). Analyzing dynamic fault trees derived from model-based system architectures. Nuclear Engineering and Technology: An International Journal of the Korean Nuclear Society, 40(5), 365–374.
Dugan, J. B., Bavuso, S. J., & Boyd, M. A. (1992). Dynamic fault-tree models for fault-tolerant computer systems. Reliability, IEEE Transactions on, 41(3), 363–377.
EAST-ADL (2010). EAST-ADL domain model specification, D4.1.1 Retrieved from.http://www.east-adl.info/repository/EAST-ADL2.1/EAST-ADL-Specification_2010-06-30.pdf
Hidalgo, E.M.P., Silva, D.W.R., & De Souza, G.F.M. (2013). “Application of Markov chain to determine the electric energy supply system reliability for the cargo control system of LNG carriers”. In Proc. of ASME 32nd Int. Conf. on Ocean, Offshore and Arctic Engng, 2013.
Joshi, A., Vestal, S., & Binns, P. (2007). Automatic generation of static fault trees from aadl models. In Workshop on Architecting Dependable Systems of The 37th Annual IEEE/IFIP Int. Conference on Dependable Systems and Networks, Edinburgh, UK.
Kolagari, R. T., Chen, D., Lanusse, A., Librino, R., Lönn, H., Mahmud, N., Mraidha, C., Reiser, M., Torchiaro, S., Tucci-Piergiovanni, S., Wägemann, T., & Yakymets, N. (2015). Model-based analysis and engineering of automotive architectures with EAST-ADL: revisited. International Journal of Conceptual Structures and Smart Applications (IJCSSA), 3(2), 25–70. https://doi.org/10.4018/IJCSSA.2015070103.
Konak, A., Coit, D. W., & Smith, A. E. (2006). Multi-objective optimization using genetic algorithms. Reliability Engineering & System Safety, 91(9), 992–1007.
Mahmud, N. (2012). Dynamic Model-based Safety Analysis: from state machines to temporal fault trees. (Ph.D. thesis). Department of Computer Science, University of Hull, Hull, UK.
Mahmud, N. (2015). Advanced fault tree synthesis for systems with dynamic aspects. In Safety and reliability of complex engineered systems (pp. 1635–1643). CRC Press.
Mahmud, N. (2017). A compositional symbolic calculus approach to producing reduced Markov chains. In 63rd Annual Reliability and Maintainability Symposium (RAMS). IEEE.
Mahmud, N., & Mian, Z. (2013). Automatic generation of temporal fault trees from AADL models. In Safety, Reliability and Risk Analysis: Beyond the Horizon (pp. 2741–2749). CRC Press.
Mahmud, N., Papadopoulos, Y., & Walker, M. (2010). A translation of state machines to temporal fault trees. In Proceedings of the 40th IEEE/IFIP International Conference on Dependable Systems and Networks, (pp. 45–51). IEEE.
Mahmud, N., Walker, M., & Papadopoulos, Y. (2012). Compositional synthesis of temporal fault trees from state machines. ACM SIGMETRICS Performance Evaluation Review, 39(4), 79–88.
Merle, G., Roussel, J. M., Lesage, J., & Bobbio, A. (2010). Probabilistic algebraic analysis of fault trees with priority dynamic gates and repeated events. Reliability, IEEE Transactions on, 59(1), 250–261.
Mian, Z., Bottaci, L., Papadopoulos, Y., Sharvia, S., & Mahmud, N. (2015) Model transformation for multi-objective architecture optimisation of dependable systems. In Dependability problems of complex information systems, (pp. 91–110). Springer.
Mitsubishi Heavy Industries. (2010). Technology trends and MHI activities for LNG carriers. Technical Review, 47(3).
Rauzy, A. (2002). Mode automata and their compilation into fault trees. Reliability Engineering & System Safety, 78(1), 1–12.
Rauzy, A., Châtelet, E., Dutuit, Y., & Bérenguer, C. (2003). A practical comparison of methods to assess sum-of-products. Reliability Engineering & System Safety, 79(1), 33–42.
Vesely, W. E., Goldberg, F. F., Roberts, N. H., & Haas, D. F. (1981). Fault Tree Handbook. US Nuclear Regulatory Committee Report NUREG-0492, Washington.
Vesely, W., Stamatelatos, M., Dugan, J., Fragola, J., Minarick, J. III, & Railsback, J. (2002). Fault tree handbook with aerospace applications. NASA Office of Safety and Mission Assurance.
Walker, M., & Papadopoulos, Y. (2009). Qualitative temporal analysis: towards a full implementation of the fault tree handbook. Control Engineering Practice, 17(10), 1115–1125.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher’s note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Mahmud, N. A minimization algorithm for automata generated fault trees with priority gates. Software Qual J 27, 1015–1043 (2019). https://doi.org/10.1007/s11219-019-09444-7
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11219-019-09444-7