基于二叉决策图的网络可达性计算

计算机工程与应用 ›› 2012, Vol. 48 ›› Issue (4): 74-76.

基于二叉决策图的网络可达性计算

朱随江1，2，刘宇1，2，刘宝旭1，姜政伟1，2

1.中国科学院高能物理研究所计算中心，北京 100049
2.中国科学院研究生院，北京 100080

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2012-02-01 发布日期:2012-04-05

Binary decision diagram-based network reachability computing

ZHU Suijiang1，2, LIU Yu1，2, LIU Baoxu1, JIANG Zhengwei1，2

1.Computing Center, Institute of High Energy Physics, Chinese Academy of Sciences, Beijing 100049, China
2.Graduate School, Chinese Academy of Sciences, Beijing 100080, China

Received:1900-01-01 Revised:1900-01-01 Online:2012-02-01 Published:2012-04-05

摘要/Abstract

摘要： 针对现有攻击图生成方法中普遍通过网络扫描获得网络可达性信息存在信息不完整、耗时长、产生网络干扰等不足，提出一种基于二叉决策图的网络可达性计算方法。该方法利用二叉决策图建模防火墙规则，通过高效的集合运算计算网络可达性。真实环境检测和模拟实验均表明该方法具有精确、耗时短、无网络干扰等优点，适用于大规模网络可达性的计算，推动了攻击图在大规模网络中的应用。

关键词: 攻击图, 网络扫描, 网络可达性, 二叉决策图, 大规模网络

Abstract: Almost all of the available attack graph generating tools get network reachability through network vulnerability scanning. There are some flaws by scanning, such as incomplete information, time consuming, and side-effect on the network. It proposes a novel algorithm to compute network reachability based on binary decision diagram. The algorithm represents firewall rules by corresponding binary decision diagram, computes the reachability by efficient set operations.The algorithm is experimented and used in operational network and simulated network. The result shows that it is accurate, it consumes less time, has no side-effect on the network, and scales well, so it suits for the large-scale network reachability computing and promotes the application of attack graph in large scale network.

Key words: attack graph, network scanning, network reachability, binary decision diagram, large-scale network

朱随江1，2，刘宇1，2，刘宝旭1，姜政伟1，2. 基于二叉决策图的网络可达性计算[J]. 计算机工程与应用, 2012, 48(4): 74-76.

ZHU Suijiang1，2, LIU Yu1，2, LIU Baoxu1, JIANG Zhengwei1，2. Binary decision diagram-based network reachability computing[J]. Computer Engineering and Applications, 2012, 48(4): 74-76.

[1]	高岭1，2，王帆1，高妮1，3，毛勇1. 基于改进蚁群算法的防护策略选择模型[J]. 计算机工程与应用, 2019, 55(7): 100-107.
[2]	王洋，吴建英，黄金垒，胡浩，刘玉岭. 基于贝叶斯攻击图的网络入侵意图识别方法[J]. 计算机工程与应用, 2019, 55(22): 73-79.
[3]	司健，陈鹏，顾宁平，孙凌枫，王蔚旻. 网络攻击图逆向深度优先生成算法[J]. 计算机工程与应用, 2017, 53(3): 131-137.
[4]	刘渊1，李群1，王晓锋2. 基于攻击图和改进粒子群算法的网络防御策略[J]. 计算机工程与应用, 2016, 52(8): 120-124.
[5]	高妮1，2，高岭1，贺毅岳1，3，王帆1. 基于贝叶斯攻击图的最优安全防护策略选择模型[J]. 计算机工程与应用, 2016, 52(11): 125-130.
[6]	陆秋琴，和涛，黄光球，王纯子. 面向对象粗糙信任攻击威胁感知模型[J]. 计算机工程与应用, 2012, 48(30): 103-111.
[7]	姚全珠，苗永军. 基于OBDD的SMC反例生成研究[J]. 计算机工程与应用, 2012, 48(10): 54-58.
[8]	蔡军，徐锡山，叶云，程文聪. 一种大规模网络威胁评估模型[J]. 计算机工程与应用, 2011, 47(20): 105-108.
[9]	孙自广，李春贵，伍轶明. 二值图像序列的符号OBDD表征模型的研究[J]. 计算机工程与应用, 2010, 46(10): 169-170.
[10]	孙艺峻，张宏莉，何慧. 大规模网络安全事件预警可视化算法研究[J]. 计算机工程与应用, 2007, 43(21): 115-117.
[11]	毛捍东,陈锋,张维明. 网络脆弱性建模方法研究[J]. 计算机工程与应用, 2007, 43(15): 1-5.
[12]	王海龙杨岳湘李强. 基于子空间方法的大规模网络流量异常检测[J]. 计算机工程与应用, 2007, 43(11): 153-156.