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

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