网络攻击图逆向深度优先生成算法

Network attack graph backward depth-first building algorithm

大规模网络节点数量多,连接关系复杂,现有攻击图生成方法存在节点爆炸问题,针对大规模网络的这种特点,提出了一种逆向深度优先攻击图生成算法。首先对攻击图的相关概念进行了简要介绍,并分析了逆向生成算法流程。然后,鉴于生成攻击图过程中要对网络可达性进行测试,因此,同时提出了基于区间树的规则匹配算法,最后,对攻击图生成算法进行了实际环境测试,并对测试结果进行了验证分析。实验结果表明,该攻击图生成算法能以O(lgn)的时间复杂度高效检测网络可达性,优化网络攻击图生成结果。

Large-scale network has numerous nodes and complicated connection,which causes nodes explosion.Aimingat this characteristic,this paper puts forward a kind of attack graph building algorithm based on backward depth-first.Firstly,it explains the attack graph conception briefly,and analyzes the backward building algorithm.Whereas building attackgraph needs network reachability test,and it brings up rule matching algorithm at the same time.Finally,it validatesthe attack graph algorithm in real network environment,and analyzes the result,which illuminates that the attack graphbuilding algorithm can test network reachability efficiently in O(lgn)and optimize the attack graph building result.