Abstract: Large-scale network has numerous nodes and complicated connection, which causes nodes explosion. Aiming at 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 attack graph needs network reachability test, and it brings up rule matching algorithm at the same time. Finally, it validates the attack graph algorithm in real network environment, and analyzes the result, which illuminates that the attack graph building algorithm can test network reachability efficiently in O（lgn）and optimize the attack graph building result.

Key words: network attack graph, attack pattern, available path, segment tree, rule matching

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

关键词: 网络攻击图, 攻击模板, 有效路径；区间树, 规则匹配