计算机科学 ›› 2021, Vol. 48 ›› Issue (12): 159-169.doi: 10.11896/jsjkx.200800177

• 计算机软件 • 上一篇    下一篇

基于模型的故障树自动生成方法

展万里1,2, 胡军1,2, 谷青范3, 荣灏3, 祁健1,2, 董彦宏1,2   

  1. 1 南京航空航天大学计算机科学与技术学院 南京211106
    2 软件新技术与产业化协同创新中心 南京210007
    3 中国航空无线电电子研究所 上海200233
  • 收稿日期:2020-08-27 修回日期:2020-10-29 出版日期:2021-12-15 发布日期:2021-11-26
  • 通讯作者: 胡军(hujun@nuaa.edu.cn)
  • 作者简介:xxzhwl@163.com
  • 基金资助:
    国家重点基础研究发展计划(973计划)(2014CB744900)

Model-based Fault Tree Automatic Generation Method

ZHAN Wan-li1,2, HU Jun1,2, GU Qing-fan3, RONG Hao3, QI Jian1,2, DONG Yan-hong1,2   

  1. 1 College of Computer Science and Technology,Nanjing University of Aeronautics and Astronautics,Nanjing 211106,China
    2 Collaborative Innovation Center of Novel Software Technology and Industrialization,Nanjing 210007,China
    3 China National Aeronautic Radio Electronics Research Institute,Shanghai 200233,China
  • Received:2020-08-27 Revised:2020-10-29 Online:2021-12-15 Published:2021-11-26
  • About author:ZHAN Wan-li,born in 1997,postgra-duate.His main research interests include software safety ana-lysis and formal methods,etc.
    HU Jun,born in 1973,Ph.D,associate professor,is a member of China Computer Federation.His main research interests include model-based safety ana-lysis,software verification and embedded system design,etc.
  • Supported by:
    National Basic Research Program of China(2014CB744900).

摘要: 基于模型的安全性分析方法能够提高复杂安全关键系统的建模与分析能力。目前故障树被广泛应用于系统安全及可靠性分析中。故障树分析(Fault Tree Analysis,FTA)是一种自上而下的演绎式失效方法,根据故障树分析系统中不希望出现的状态,系统工程中可以尽早确定当前系统模型可能出现的问题并及时避免。面向一类安全关键性系统领域中的系统安全性建模语言AltaRica,基于其语义模型卫士转换系统(Guarded Transition Systems,GTS),设计了从平展化的GTS模型自动构造系统故障树的方法,节省了人工构造故障树的时间,从而加快了系统分析的进度。根据AltaRica3.0语言的语义规则,提取平展化GTS模型的数据构建实例对象;设计了GTS模型划分算法,得到一组独立GTS模型与一个独立断言,通过邻接矩阵构建独立GTS的可达图并获取关键事件序列。最后将处理结束的独立GTS与独立断言相结合,通过断言传播算法得到整个系统的状态及关键事件序列,生成系统故障树。最后通过实例来检验算法的有效性,结果表明,该算法能有效完成从平展化GTS模型自动生成故障树。

关键词: AltaRica, 断言传播算法, 故障树分析, 划分算法, 可达图, 平展化GTS

Abstract: Model-based safety analysis methods can improve the modeling and analysis capabilities of current complex safety-critical systems.At present,fault tree is widely used in system safety analysis and reliability analysis.Fault tree analysis (FTA) is a top-down deductive failure method,which analyzes undesired states in the system according to the fault tree.In the system engineering,the possible problems of the current system model can be determined as early as possible and avoided in time.The work of this paper is oriented to a type of system safety modeling language AltaRica in the aerospace field.Based on its semantic model GTS (guarded transition systems),a method for automatically constructing a system fault tree from the flattened GTS model is designed,which saves the time of artificial fault tree construction,and speeds up the progress of system analysis.According to the semantic rules of the AltaRica3.0 language,extracting the data of the flattened GTS model to construct instance objects,designing the GTS model division algorithm to obtain a set of independent GTS models and an independent assertion,constructing the reachability graph of the independent GTS through the adjacency matrix and obtaining the key event sequence,then,the indepen-dent GTS that has been processed is combined with the independent assertion,the state of the entire system and the sequence of key events are obtained through the assertion propagation algorithm,and the system fault tree is generated.Finally,an example system shows that the algorithm can effectively complete the automatic generation of fault trees from the flattened GTS model.

Key words: AltaRica, Assertion propagation algorithm, Division algorithm, Flattened GTS, FTA, Reachability graph

中图分类号: 

  • TP311
[1]WANG P,WU K,YAN F,et al.Security verification method of safety critical software based on system theoretic process analysis[J].Journal of Computer Applications,2019,39(11):3298-3303.
[2]CHE C,LIU Y F.Research on Model Based Safety Analysis [J].Advances in Aeronautical Science and Engineering,2016,7(3):369-373.
[3]HU J,CHEN S,WANG M M.A transformation method for AltaRica3.0 to Promela and its verification[J].Computer Engineering and Science,2017(4):708-716.
[4]PROSVIRNOVA T.AltaRica 3.0:a model-based approach for safety analyses[EB/OL].http://www.researchgate.net/publication/278827421_AltaRica_30_a_Model-Based_approach_for_Safety_Analyses.
[5]PROSVIRNOVA T,BATTEUX M,BRAMERET P A,et al. The AltaRica 3.0 project for model-based safety assessment[J].IFAC Proceedings,2013,46(22):127-132.
[6]BATTEUX M,PROSVIRNOVA T,RAUZY A.Advances in the simplification of Fault Trees automatically generated from AltaRica 3.0 models[M]//Safety and Reliability-Safe Societies in a Changing World.2018:907-914.
[7]RAUZY A B.Guarded transition systems:a new states/events formalism for reliability studies[J].Journal of Risk and Reliabi-lity,2008,222(4):495-505.
[8]OLIVA J J R,LLANES J S,OJEDA M P,et al.Advanced combinatorial method for solving complex fault trees[J].Annals of Nuclear Energy,2018,120:666-681.
[9]LI Z,ZHANG Y.Software Security Test Case Generation Based on Minimum Cut Sets [J].Computer and Digital Engineering,2019,47(7):1772-1775.
[10]HAN S H.A top-down iteration algorithm for Monte Carlo method for probability estimation of a fault tree with circular logic[J].Nuclear Engineering and Technology,2018,50(6):854-859.
[11]BATTEUX M,PROSVIRNOVA T,RAUZY A.Safety mode- ling and assessment with AltaRica 3.0[J/OL].http://www.altarica-association.org/ressources/Tutorial-IMBSA2019.pdf
[12]SONG J,CHEN B,LI X,et al.The software fault prediction model based on the AltaRica language[C]//2019 IEEE 3rd Information Technology,Networking,Electronic and Automation Control Conference (ITNEC).IEEE,2019:2549-2552.
[13]RIVIECCIO U,JUNG A,JANSANA R.Four-valued modal lo- gic:Kripke semantics and duality[J].Journal of Logic and Computation,2017,27(1):155-199.
[14]CHEN R L.Fault tree analysis and calculation method[J]. Technology Innovation and Application,2018 (244):24.
[15]KABIR S.An overview of fault tree analysis and its application in model based dependability analysis[J].Expert Systems with Applications,2017,77:114-135.
[16]KATOEN J P,STOELINGA M.Boosting fault tree analysis by formal methods[M]//ModelEd,TestEd,TrustEd.Springer,Lecture Notes in Computer Science.Springer,Cham,2017:368-389.
[17]ZHU D Q.Research on Fault Diagnosis Technology of avionics equipment[D].Nanjing:Nanjing University of Aeronautics and Astronautics,2002.
[18]ESTEFAN J A.Survey of model-based systems engineering (MBSE) methodologies[J].Incose MBSE Focus Group,2007,25(8):1-12.
[19]CHEN S,HU J,WANG L S.Design and Implementation of Flattening Algorithm for AltaRica 3.0 Model Based on ANTLR[J].Journal of Chinese Computer Systems,2020,41(7):1476-1487.
[20]PROSVIRNOVA T,RAUZY A.AltaRica 3.0 project:compile Guarded Transition Systems into Fault Trees[C]//European Safety and Reliability Conference,ESREL.2013.
[21]DENGB B,DAI B Q,WANGT.Dynamic fault tree analysis of SUBWAY vehicle-mounted ATP system based on Isograph [J].Journal of Safety Science and Technology,2016,12(5):80-85.
[22]LEE D W,KIM I S,NA J W.A Case Study on Safety Analysis Procedure of Aircraft System using the Relex[J].The Journal of Advanced Navigation Technology,2018,22(3):179-188.
[23]BOZZANO M,CIMATTI A,KATOEN J,et al.The COMPASS Approach:Correctness,Modelling and Performability of Aerospace Systems[C]//International Conference on Computer Safety Reliability and Security,2009.
[24]PROSVIRNOVA T,BATTEUX M,BRAMERET P A,et al. The altarica 3.0 project for model-based safety assessment[J].IFAC Proceedings Volumes,2013,46(22):127-132.
[25]MORTADA H,PROSVIRNOVA T,RAUZY A.Safety assessment of an electrical system with AltaRica 3.0[C]//International Symposium on Model-Based Safety and Assessmemt.Springer,Cham,2014:181-194.
[26]CHEN S.Research on System Safety Design Verification Me- thodology Based on AltaRica Model[D].Nanjing:Nanjing University of Aeronautics and Astronautics,2017.
[27]PROSVIRNOVA T.AltaRica 3.0:a model-based approach for safety analyses[EB/OL].http://www.researchgate.net/publication/278827421_AltaRica_30_a_Model-Based_approach_for_Safety_Analyses.
[1] 李清, 刘伟, 管梦真, 杜玉越, 孙红伟.
基于逻辑博弈决策Petri网的应急决策建模与分析
Modeling and Analysis of Emergency Decision Making Based on Logical Probability GamePetri Net
计算机科学, 2022, 49(4): 294-301. https://doi.org/10.11896/jsjkx.210300224
[2] 祁健, 胡军, 谷青范, 荣灏, 展万里, 董彦宏.
一种AltaRica 3.0模型中类的平展化方法
Class Flattening Method for AltaRica 3.0 Model
计算机科学, 2021, 48(5): 51-59. https://doi.org/10.11896/jsjkx.200700184
[3] 唐红英, 胡军, 陈朔, 石梦烨.
面向SysML的系统安全性分析工具与实例研究
System Safety Analysis Tool for SysML and Case Study
计算机科学, 2020, 47(5): 284-294. https://doi.org/10.11896/jsjkx.190600169
[4] 李宛倩, 胡军, 陈松, 张维珺.
面向SysML模型的安全性分析与验证方法
Method of System Safety Analysis and Verification for SysML Models
计算机科学, 2019, 46(11): 100-108. https://doi.org/10.11896/jsjkx.181001850
[5] 李东民,李静,林华锋.
基于故障树分析的嵌入式系统AADL模型可靠性分析方法
Reliability Analysis Method of Embedded System AADL Model Based on Fault Tree Analysis
计算机科学, 2017, 44(6): 182-188. https://doi.org/10.11896/j.issn.1002-137X.2017.06.031
[6] 范亚琼,陈海燕.
基于时序关系的系统失效可达图生成方法
System Failure Reachability Graph Generation Method Based on Temporal Relation
计算机科学, 2017, 44(12): 169-174. https://doi.org/10.11896/j.issn.1002-137X.2017.12.032
[7] 胡军,石娇洁,程桢,陈松,王明明.
一种基于四变量模型的系统安全性建模与分析方法
System Safety Modeling and Analysis Method Based on Four-variable Model
计算机科学, 2016, 43(11): 193-199. https://doi.org/10.11896/j.issn.1002-137X.2016.11.038
[8] 王飞,沈国华,黄志球,马 琳,刘 畅,李海峰,廖莉莉.
一种结合线性时序逻辑和故障树的软件安全验证方法
Method Combining Linear Temporal Logic and Fault Tree for Software Safety Verification
计算机科学, 2015, 42(12): 71-75.
[9] 王丽,秦小麟,许建秋.
室内概率阈值反向最近邻查询
Probabilistic Threshold Reverse Nearest Neighbor Queries for Indoor Moving Objects
计算机科学, 2015, 42(1): 201-205. https://doi.org/10.11896/j.issn.1002-137X.2015.01.045
[10] 张卫祥,刘文红.
基于故障树分析与组合测试的测试用例生成方法
Test Suite Generation Based on Interaction Testing and Fault Tree Analysis
计算机科学, 2014, 41(Z11): 375-378.
[11] 郑雷雷,宋丽华,郭锐,张建成.
故障树分析法在信息安全风险评估中的应用
Application of FAT in Information Security Risk Assessment
计算机科学, 2011, 38(Z10): 106-108.
[12] 谭玲 郑栋 顾庆 陈道蓄.
工作流模型死锁的Petri网分析

计算机科学, 2006, 33(7): 111-114.
[13] .
基于路径的软硬件划分算法

计算机科学, 2006, 33(1): 164-166.
[14] 孙功星 戴贵亮.
神经网络设计的特征空间序贯划分算法

计算机科学, 2003, 30(11): 36-37.
[15] 范哲 顾毓清 等.
分布式虚拟环境中的一种场景动态划分算法—基于竞争的演化算法

计算机科学, 2001, 28(10): 19-23.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!