Computer Science ›› 2018, Vol. 45 ›› Issue (9): 202-206.doi: 10.11896/j.issn.1002-137X.2018.09.033

• Information Security • Previous Articles     Next Articles

Fault Tree Structure Matching Algorithm and Its Application

YUE Xin1, DU Jun-wei1, HU Qiang1, WANG Yan-ping2   

  1. School of Information Science and Technology,Qingdao University of Science & Technology,Qingdao,Shandong 266100,China1
    Sinopec Research Institute of Safety Engineering,Qingdao,Shandong 266000,China2
  • Received:2017-08-30 Online:2018-09-20 Published:2018-10-10

Abstract: A large number of fault trees have been designed and stored with the occurrence of numerous historical accident cases.Structure matching is an effective way to achieve accurate and comprehensive investigation of new accidents by using the existing fault trees with the limited time,manpower and cost.Based on the timing of event evolution and the structural features of causal reasoning,a fault tree structure matching algorithm was proposed.The hidden Markov model of fault tree is constructed and then the Viterbi algorithm is used to predict the optimal matching sequences.Compared with the node-based structure matching algorithm,this algorithm has significant improvement in the accuracy of matching and the detection of structural defects.

Key words: Accident analysis, Fault tree, Hidden Markov model, Structure matching, Viterbi algorithm

CLC Number: 

  • TP399
[1]XU B F,HUANG Z Q,HU J,et al.Time Property Analysis Method for State/Event Fault Tree[J].Journal of Software,2015,26(2):427-446.(in Chinese)
[2]TANAKA H,FAN L T,LAI F S,et al.Fault-Tree Analysis by Fuzzy Probability[J].IEEE Transactions on Reliability,2009,R-32(5):453-457.
[3]CUI T J,MA Y D.Establishment of DSFT and determination of spatial distribution of probability of failure [J].Systems Engineering-Theory & Practice,2016,36(4):1081-1088.(in Chinese)
[4]ALIEE H,ZARANDI H R.A Fast and Accurate Fault Tree
Analysis Based on Stochastic Logic Implemented on Field-Programmable Gate Arrays[J].IEEE Transactions on Reliability,2013,62(1):13-22.
[5]NI J,TANG W,XING Y.A Simple Algebra for Fault Tree
Analysis of Static and Dynamic Systems[J].IEEE Transactions on Reliability,2013,62(4):846-861.
[6]LI Z F,REN Y,LIU L L,et al.Parallel algorithm for finding modules of large-scale coherent fault trees[J].Microelectronics Reliability,2015,55(9/10):1400-1403.
[7]DOOHWAN O H,WON WOO R O.High Performance Pattern Matching algorithm with Suffix Tree Structure for Network Security[J].Pattern matching,2014,51(6):110-116.
[8]LIU P.Tree structure matching pursuit based on Gaussian scale mixtures model[J].Proc Spie,2011,8135(1):813520-813520-8.
[9]ZHANG H W,JIE X F,DUAN Y Y,et al.A directed graph based subgraph matching query algorithm based on adaptive structure outline[J].Chinese Journal of Computers,2017,40(1):52-71.(in Chinese)
[10]LI R Y,HONG L.A subgraph matching method based on inclusion degree[J].Journal of Software,2018,29(6):1792-1812.(in Chinese)
[11]LV Q,QIAO Y,ANSARI N,et al.Big Data Driven Hidden
Markov Model Based Individual Mobility Prediction at Points of Interest[J].IEEE Transactions on Vehicular Technology,2017,PP(99):1.
[12]CHOI K W,HOSSAIN E.Estimation of Primary User Parameters in Cognitive Radio Systems via Hidden Markov Model[J].IEEE Transactions on Signal Processing,2013,61(3):782-795.
[13]SOUALHI A,CLERC G,RAZIK H,et al.Hidden Markov
Models for the Prediction of Impending Faults[J].IEEE Tran-sactions on Industrial Electronics,2016,63(5):3271-3281.
[14]HAGENAUER J.Source-controlled channel decoding[J].IEEE Transactions on Communications,2002,43(9):2449-2457.
[15]NING A,LI X,WANG C.ASE Approach for Large Graphs
Matching[J].Information Technology Journal,2013,12(14):2969-2974.
[1] WEI De-bin,YANG Peng,YANG Li,SHI Huai-feng. Virtual Network Function Fast Mapping Algorithm over Satellite Network [J]. Computer Science, 2020, 47(3): 248-254.
[2] ZHANG Jing, YANG Jian, SU Peng. Survey of Monosyllable Recognition in Speech Recognition [J]. Computer Science, 2020, 47(11A): 172-174.
[3] ZHANG Cheng-wei, LUO Feng-e, DAI Yi. Prediction Method of Flight Delay in Designated Flight Plan Based on Data Mining [J]. Computer Science, 2020, 47(11A): 464-470.
[4] JIA Zhi-chun, LI Xiang, YU Zhan-lin, LU Yuan, XING Xing. QoS Satisfaction Prediction of Cloud Service Based on Second Order Hidden Markov Model [J]. Computer Science, 2019, 46(9): 321-324.
[5] XU Bing-feng, HE Gao-feng, ZHANG Li-ning. Risk Modeling for Cyber-physical Systems Based on State/Event Fault Trees [J]. Computer Science, 2019, 46(5): 105-110.
[6] WU Jian-wei, LI Yan-ling, ZHANG Hui, ZANG Han-lin. HMM Cooperative Spectrum Prediction Algorithm Based on Density Clustering [J]. Computer Science, 2018, 45(9): 129-134.
[7] GONG Fa-ming,ZHU Peng-hai. Word Segmentation Based on Adaptive Hidden Markov Model in Oilfield [J]. Computer Science, 2018, 45(6A): 97-100.
[8] TONG Zhen-ming, LIU Zhi-peng. Next Place Prediction of Massively Multiplayer Online Role-playing Games [J]. Computer Science, 2018, 45(11A): 453-457.
[9] ZHANG Xiao-ce, YAN Xue-feng and ZHOU Yong. Method of SBDD Based on Dynamic Fault Tree [J]. Computer Science, 2017, 44(9): 195-199.
[10] LI Dong-min, LI Jing and LIN Hua-feng. Reliability Analysis Method of Embedded System AADL Model Based on Fault Tree Analysis [J]. Computer Science, 2017, 44(6): 182-188.
[11] CUI Tie-jun, LI Sha-sha and WANG Lai-gui. System Function Structure Analysis in Complete and Incomplete Background Relationship [J]. Computer Science, 2017, 44(3): 268-273.
[12] HUANG Ming-yu, WEI Ou and HU Jun. Fault Tree Generation Based on Fault Configuration [J]. Computer Science, 2017, 44(2): 182-191.
[13] FAN Ya-qiong and CHEN Hai-yan. System Failure Reachability Graph Generation Method Based on Temporal Relation [J]. Computer Science, 2017, 44(12): 169-174.
[14] YANG Lu, YU Shou-wen and YAN Jian-feng. Type-2 Fuzzy Logic Based Multi-threaded Data Race Detection [J]. Computer Science, 2017, 44(12): 135-143.
[15] JI Hai-feng and TIAN Huai-wen. Sketch Recognition Method of Combined Graphs for Conceptual Design [J]. Computer Science, 2016, 43(Z6): 134-138.
Full text



No Suggested Reading articles found!