• 中国计算机学会会刊
  • 中国科技核心期刊
  • 中文核心期刊

计算机工程与科学

• 论文 • 上一篇    下一篇

基于SAT求解器的故障树最小割集求解算法

罗炜麟,魏欧,黄鸣宇   

  1. (南京航空航天大学计算机科学与技术学院,江苏 南京 210016)
  • 收稿日期:2016-12-10 修回日期:2017-02-13 出版日期:2017-04-25 发布日期:2017-04-25
  • 基金资助:

    国家自然科学基金(61170043);国家973计划(2014CB7449014);南京航空航天大学研究生创新基地(实验室)开放基金(kfjj20161602);中央高校基本科研业务费

Computing minimal cut sets of fault tree using SAT solver

LUO Wei-lin,WEI Ou,HUANG Ming-yu   

  1. (College of Computer Science and Technology,Nanjing University of Aeronautics and Astronautics,Nanjing 210016,China)
  • Received:2016-12-10 Revised:2017-02-13 Online:2017-04-25 Published:2017-04-25

摘要:

故障树分析广泛应用于核工业、航空航天和交通控制等安全攸关领域的安全性分析。求解故障树的最小割集是故障树分析的关键步骤。目前,对于大规模故障树的最小割集的求解方法主要是将故障树转化为二元决策图之后求解,其主要缺点在于算法在时间和空间上的消耗严重依赖良好的变量顺序。为了减少存储资源并加快求解速度,提出了一种基于可满足性问题的故障树最小割集求解算法。首先,将求解故障树最小割集问题转化为求解布尔可满足性问题。然后,利用可满足性问题求解器,通过迭代分析求得最小可满足解集合,即为对应故障树的最小割集。实验表明,本文算法求得的最小割集准确、有效并且在空间和时间上的消耗均要优于传统的基于二元决策图的故障树最小割集求解算法。

 

关键词: 故障树分析, 安全性分析, 最小割集, 可满足性问题

Abstract:

Fault tree analysis is widely used in the safety analysis of safety crisis areas such as nuclear industry, aerospace engineering, traffic control, etc. It is the key step to solve the minimal cut sets of fault tree in fault tree analysis. The conventional algorithms solving the minimal cut sets of large-scale fault tree are mainly based on the binary decision diagram. Their main drawback is that the time and space consumption of the algorithm relies heavily on a good order of variables. In order to reduce the storage resources and speed up the process, we propose a new algorithm based on Boolean satisfiability problem to solve the minimal cut sets in fault tree analysis. Firstly, we convert this problem into a Boolean satisfiability problem. Secondly, the SAT solver is used to solve the minimal satisfiability of the Boolean formula, namely the minimal cut sets of the fault tree, through the iteration of above processes. Experimental results show that compared with conventional algorithms, this new algorithm is not only more accurate but also more efficient for solving the minimal cut sets in fault tree analysis.

Key words: fault tree analysis, safety analysis, minimal cut set, Boolean satisfiability problem