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

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

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