2017，53（3）1引言网络漏洞之间存在一定的关联关系，一个漏洞的利用可以为下一个漏洞的攻克提供前提条件，而且这种关联会随着网络规模的增大越来越复杂。攻击图是一种分析网络漏洞关联性的有效工具，可以体现出安全漏洞之间前后承接关系，当网络规模较小的时候可以通过手动分析形成攻击图，但是对于大规模网络来说，其中包含有大量主机节点，而且由于路由器ACL 配置和防火墙端口过滤，导致有物理连接的网络节点之间并不存在实际的数据通路，因此大规模网络不仅节点数量众多，而且连接关系复杂。通过手工方式形成攻击图已不可行，为了进行大规模网络的漏洞分析，需要设计一种网络攻击图的自动生成算法。
生成攻击图需要对网络环境、攻击场景、攻击方式进行建模[1-2]，因此，需要获取网络互联设备、安全设备的配置信息，网络拓扑信息，主机节点的漏洞信息，服务的部署信息，在网络建模的基础上，对网络中漏洞之间的关联关系进行分析，逆向推导所有可以实现攻击目标的攻击路径，最后将多条攻击路径组合形成网络攻击图。网络攻击图的复杂程度随着网络规模的增大呈指数增长，表现为攻击路径变长，攻击路径增多，即攻击图存在的节点爆炸问题。然而，在攻击图挖掘过程中，需要对攻击者做最有利假设[3-4]，即攻击者在实际攻击行为中会选择最容易成功的路径进行攻击，而且攻击路径跳网络攻击图逆向深度优先生成算法
司健，陈鹏，顾宁平，孙凌枫，王蔚旻
SI Jian,CHEN Peng,GU Ningping,SUN Lingfeng,WANG Weimin
中国电子科技集团公司第二十八研究所第一研究部，南京210007
The First Research Department,No.28Research Institute,China Electronics Technology Group Corporation,Nanjing 210007,China
SI Jian,CHEN Peng,GU Ningping,et al.Network attack graph backward depth-first building algorithm.Computer Engineering and Applications,2017,53（3）：131-137.
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 at-tack 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 （lg n ）and optimize the attack graph building result.Key words:network attack graph;attack pattern;available path;segment tree;rule matching
摘要：大规模网络节点数量多，连接关系复杂，现有攻击图生成方法存在节点爆炸问题，针对大规模网络的这种特点，提出了一种逆向深度优先攻击图生成算法。首先对攻击图的相关概念进行了简要介绍，
并分析了逆向生成算法流程。然后，鉴于生成攻击图过程中要对网络可达性进行测试，因此，同时提出了基于区间树的规则匹配算法，最后，对攻击图生成算法进行了实际环境测试，并对测试结果进行了验证分析。实验结果表明，该攻击图生成算法能以O （lg n ）的时间复杂度高效检测网络可达性，优化网络攻击图生成结果。
关键词：网络攻击图；攻击模板；有效路径；区间树；规则匹配
文献标志码：A 中图分类号：TP393doi ：10.3778/j.issn.1002-8331.1505-0175
作者简介：司健（1985—），男，工程师，研究领域为计算机网络；陈鹏（1978—），男，高级工程师，研究领域为计算机网络；顾宁平
（1978—），男，高级工程师，研究领域为计算机网络；孙凌枫（1979—），男，高级工程师，研究领域为计算机网络；王蔚旻（1983—），男，高级工程师，研究领域为计算机网络。
收稿日期：2015-05-21修回日期：2015-12-01文章编号：1002-8331（2017）03-0131-07
CNKI 网络优先出版：2015-12-11,wwwki/kcms/detail/11.2127.TP.20151211.1527.054.html
Computer Engineering and Applications 计算机工程与应用
131
Computer Engineering and Applications计算机工程与应用2017，53（3）
数不会无限制增长，另外，攻击者不会重复获取已经获
取过的节点权限[5]。因此，本文在算法设计中设置了攻
击路径的成功概率阈值，并限制了攻击跳数，从而有效
抑制了攻击图的复杂程度，并防止出现无效路径。并
且，为了避免重复获取权限，在攻击路径生成过程中，对
回环路径进行测试[6]，防止生成环形回路。
最后，鉴于网络可达性是攻击成功的基本前提条
件，本文设计了网络可达性检测算法，通过对网络拓扑
和防火墙规则的分析，形成规则树[7-10]，将攻击连接抽象
为五元组<srcip，dstip，srcport，dstport，protocol>，通过检
测五元组和规则树是否匹配，对网络攻击的可达性前提
进行有效测试。
该网络攻击图生成算法可以去除无意义攻击路径，
有效抑制攻击图规模，分析预测攻击路径，评估网络安
全风险。而且设计了网络攻击的重要前提——网络可
达性的自动判定方法，提出了基于区间树的规则匹配算
法，为攻击图生成算法的研究提供了有力支撑。
2攻击图模型
攻击类型转换2.1攻击场景定义
为了进行攻击路径分析，需要对发动攻击的网络场
景进行建模，攻击场景建模就是对目标评估网络进行抽
象化描述，攻击场景包括目标网络对象集合、对象属性
集合。网络对象包括主机、服务、漏洞，对象属性包括服
务定位、服务可达性、漏洞定位、权限。
定义1主机用ip地址组来表示，因为有的主机可能
有多个地址，定义为<ip-set>，比如<192.168.0.1/24，
172.6.5.16/24>，表示某台主机有两个地址，分别是
192.168.0.1/24和172.6.5.16/24。
定义2服务定义为<service，port>，service表示服务
名称，Port表示服务运行的端口。
定义3漏洞定义为<cveid，service，possible>，cveid
表示该漏洞在CVE漏洞库中的检索编号，service表示
该漏洞利用的服务，possible表示漏洞被单步攻击成功
利用的概率。
漏洞被发现初期攻击主体迅速开发攻击技术，而此
时相应防护手段还未成形，攻击成功率快速上升，随着
时间推延，安全专家开发出相应防御技术，因此到第β
天时攻击成功率达到最大值δ，之后逐渐递减[11-12]。攻
击成功率函数如下：
p(v)=ì
í
î
ï
ï
e tλ1-1,t<β
δ⋅e-(t-β)⋅λ2,t≥β
（1）
其中λ1和λ2是增长因子和衰减因子。
定义4服务定位表示某服务运行在某台主机的某个端口上，定义为四元组ServiceLocation<ip，service，protocol，port>，ip表示服务所在的主机，service表示服务名称，protocol表示服务通信使用的传输层协议，包括TCP和UDP，port表示服务运行端口。比如，ServiceLo-cation<192.168.1.2/32，Sshd，TCP，22>表示在192.168.1.2/ 32主机上部署有sshd服务，该服务以TCP协议运行在22号端口上。
定义5服务可达性表示某源主机可以在符合网络拓扑和防火墙过滤规则的前提下，通过某端口和某目的主机用TCP\UDP通信，定义为五元组NetworkReach-able<srcip，dstip，service，protocol，port>。比如，Network-Reachable<172.16.1.1/32，192.168.1.2/32，Sshd，TCP，22>表示172.16.1.1/32上的Sshd服务可以通过22号端口和192.168.1.2/32进行通信。
定义6漏洞定位表示在某台主机，使用某端口的某服务软件具有哪些漏洞，定义为4元组VulerLocation<ip，service，cveid>，ip表示漏洞所在主机，service表示漏洞利用的服务，cveid表示漏洞的CVE编号。比如，Vuler-Location<192.168.1.3/32，Apache，CVE-2003-0245>表示在主机192.168.1.3/32上的apche web服务器软件存在CVE-2003-0245漏洞。
定义7权限表示攻击者在某台主机上的权限，定义为二元组Right<ip，privilege>，ip表示主机，privilege表示在此主机上的攻击者权限，包括user、root（对应Win-dows系统中SYSTEM）。
2.2攻击模板定义
攻击模板是对具有相同特征的一组漏洞的原子攻击的抽象化描述[11，13]，它描述了一次原子攻击的攻击名称、攻击类型、可利用的漏洞、攻击前提和攻击后果。通过将漏洞分别归类为特定攻击模板，将攻击模板作为攻击图生成过程中的过渡中介，可以减少漏洞的遍历规模，从而有效提高攻击图算法生成效率。
定义8攻击模板定义为一个四元组template<name，vulners，precond，postcond>，其中name表示攻击类型描述，vulners表示该模板包含的漏洞组，precond表示该原子攻击的前提条件，postcond表示该原子攻击的攻击后果。其中vulners漏洞组用CVE（Common Vulnerability and Exposures，公共脆弱性和暴露）漏洞检索库中的漏洞编号来表示。precond一般是由一组形式化语言来描述，包括四种条件，分别是攻击源、目标机上需部署的某种服务，某种服务存在的某种漏洞，目标主机和攻击主机之间存在的网络连接通路，攻击者在攻击主机上具有的特定权限。postcond一般是获取目标机权限，实现拒绝服务，窃取信息等。
CVE库中现已收录的漏洞条目近80000条，通过整理，大致归纳为缓冲区溢出、SQL注入、目录遍历、跨站脚本、权限许可和访问控制、代码注入、OS命令注入等24种攻击模板。以“远程内存溢出获取root权限”为例，其攻击模板如下：
132
2017，53（3）name ：r_buf vulner ：CVE-2003-0245，CVE-2006-2372，CVE-2006-6424，CVE-2006-0026，CVE-2006-2451……precond ：ServiceLocation<s ，ser ，pro ，port>，ServiceLocation<d ，ser ，pro ，port>，VulerLocation<d ，ser ，cveid>，NetworkReachable<s ，d ，pro ，port>，Right <s ，root>postcond ：Right （d ，root ）“远程内存溢出获取root 权限”攻击模板代表了一类通过攻击内存溢出漏洞的攻击行为，这些攻击行为的攻击前提是要求目标主机d 上运行ser 服务，并且这个服务存在vulners 漏洞，攻击主机s 和目标主机d 之间具备网络可达性，在攻击主机上攻击者具有root 权限；攻击后果是攻击者在目标主机d 上获取root 权限。该模板包括的漏洞id 有CVE-2003-0245，CVE-2006-2372等，以CVE-2006-2372为例，该漏洞的实际名称是“Microsoft Windows D
HCP client 服务ACK 应答处理远程缓冲区溢出漏洞”，存在于Windows 操作系统的DHCP 客户端程序中，远程攻击者可以利用此漏洞在客户端上执行任意命令。3攻击图生成网络攻击图可以理解为通过分析单步的原子攻击之间的关联关系，将原子攻击按照先后顺序串接起来形成的。本文的攻击图生成方法是逆向深度优先生成算法，从最终攻击目标主机节点出发，逆向推导攻击路径，通过限定攻击成功率阈值和攻击步骤数目，对攻击图规模进行限制。攻击图中包括两类节点，分别是攻击动作节点和属性节点，攻击动作节点反映了原子攻击的具体攻击行为，属性节点表示攻击前提和攻击后果，对应于攻击模板中的precond 和postcond 。一个原子攻击的后果可能是下一原子攻击的前提，通过前提节点和后果节点将原子攻击关联起来，从而形成攻击路径和攻击图。3.1逆向深度优先攻击图生成算法从攻击的最终目标开始逆向推导，首先遍历模板库，查符合此攻击目标的所有模板类型以及当前攻击目标上存在的模板对应的漏洞，然后遍历符合条件的漏洞，遍历检查攻击前提条件是否符合，如果不符合继续递归运算，如果符合则形成一条攻击路径，并继续遍历其他漏洞。在攻击图生成过程中，检测攻击路径累积成功概率和累积攻击跳数，防止出现无效路径。攻击图生成算法伪代码如下所示：//N e 表示攻击动作，N p 表示攻击前提，N d 表示攻击目标（或者说攻击后果），templateid 和attackobj 分别表示攻击模板和攻击实例，pre 和post 表示attackobj 或者templateid 的攻击前提和后果，N e \N p \N d 是攻击图中的节点，但是也有pre 和post 属性。attack_graph 表示最终生成的攻击图。
//template_set 表示目标主机上的所有目标漏洞对应的攻击模板集合，TEMPLATE_SET 表示攻击模板
库中的模板集合，CVE_SET 表示目标主机上的目标漏洞集合，MIN_CUMULATE_POSSIBLE 表示攻击累积成功概率阈值，MAX_HOP 表示攻击路径最大跳数，攻击最终目标结果是Nd 。//template_set 初始化为空集，cve_set 初始化为CVE_SET ，N d 初始化为Nd template_set ←Φcve_set ←CVE_SET N d ←Nd ；attack_tree_build （N d ）{//遍历攻击模板库中所有模板，根据攻击后果和当前目标主机上的漏洞查符合的模板，获取目标主机上的模板集template_set 。foreach templateid ∈TEMPLATE_SET{
if （templateid.post==N d &&cve_set ∩templateid.cve-set ≠Φ）{
template_set+=templateid ；
templateid.cur_cve_set+=cve_set ∩templateid.cveset ；}}//遍历模板集template_set ，寻每个templateid 对应的攻
击前提。
foreach templateid ∈template_set{
foreach cveid ∈templateid.cur_cve_set{//将cveid 对应的漏洞的攻击源端需部署的软件、所需协议、端口进行部分实例化Attackobj.pre =cveid.Instance_software （）；//进行目的主机和网络系统内其他主机的连通性测试
foreach srcip ∈systemip_set{//使用连接四元组结合过滤规则filter_set 测试网络可
达性//如果可达性测试失败，继续剩余主机的测试if （linktest （N d .ip ，srcip ，attackobj.protocol ，attackobj.dport ，filter_set ）==false ）{continue ；}//如果连通成功，检测攻击主机的软件部署情况是否满
足此攻击实例的前提条件，累计概率和攻击跳数是否超过阈
值//如果满足条件，则将该源IP 所对应攻击的N e 和N p 加入到攻击图中if （satisfy （attackobj.pre ，srcip ）==true ）{
//计算累积概率，检测是否低于成功阈值
if （attackobj.possible*N d .cumu_possible<MIN_CUMULA TE_POSSIBLE ）break ；
//计算攻击跳数，检测是否超过跳数阈值if （（attackobj.hop=N d .hop++）>MAX_HOP ）
司健，陈鹏，顾宁平，等：网络攻击图逆向深度优先生成算法
133
Computer Engineering and Applications 计算机工程与应用
2017，53（3）break ；//加入攻击图之前检测该前提点是否已经存在于攻击路径中，防止打环posttemp =N d .post ；while （posttemp ≠attackobj.pre &&posttemp ≠Nd ）{
posttemp=posttemp.post ；}if （posttemp=attackobj.pre ）//说明打环了，该前提点不合格，会生成无
效路径break ；N e =attackobj.action ；attack_graph.insert （N e ）；//攻击图中插入攻击节点attackobj.pre.cumu_possible=attackobj.possible*N d .cumu_possible ；N p =attackobj.preworkreachable ；attack_graph.insert （N p ）；/攻击图中插入可达性前提节点N p =attackobj.pre.servicelocation ；attack_graph.insert （N p ）；/攻击图中插入服务部署前提节点N p =attackobj.pre.vulnerablelocation ；attack_graph.insert （N p ）；/攻击图中插入漏洞分布前提节点attackobj.pre.s_right.hop=N d .hop ；
attack_tree_build （attackobj.pre.s_right ）；}//以获取当前攻击源权限为目标，递归生成攻击路径//如果不满足条件，则继续查剩余的使srcip 节点满足攻击条件的攻击路径else if （satisfy （attackobj.pre ，srcip ）==false ）{continue ；}}}}}}3.2基于区间树的攻击可达性检测网络攻击图的生成过程中需要对网络可达性进行检测，两个节点之间是否可达是通过检测连接五元组link<srcip ，dstip ，sport ，dport ，protocol>是否符合规则集来验证的。通过采集路由器、防火墙配置信息和网络拓扑信息，生成规则条目，原始规则条目定义为九元组raw_rule<srcip_beg ，srcip_end ，dstip_beg ，dstip_end ，
sport_beg ，sport_end ，dport_beg ，dport_end ，protocol>，原始规则定义了源地址、目的地址、源端口、目的端口的允
许范围和连接协议，多条原始规则条目组织形成规则集rule_set 。规则匹配算法就是在已知连接五元组link 和规则集rule_set 的情况下，计算rule_set 中是否存在允许
范围符合link 的规则，如果存在则计算出符合的规则。红黑树是一种自平衡二叉查树，虽然红黑树不是严格意义上平衡的二叉树，但是其统计性能要好于AVL-树，时间复杂度为O (lg n )[14]，是一种性能优良的查算法，被广泛使用于操作系统底层的内存操作和容器
类模板库。在匹配计算中需要定位link 参数的规则区间，实际上也是查的过程。规则匹配算法的核心数据结构是红黑树，只是对具体的存储节点内容做了扩展，因此其查时间复杂度和红黑树一样，也是O (lg n )。树上的每个节点的key 是规则区间端点值，value_field 包括key 对应的区间S ，左右
子树对应的区间LS 、RS （S=LS+RS ），以及包含该节点区间S 的raw_rule 组成的规则集rule_set （LS 、RS 也有对应的
rule_set_L 和rule_set_R ，子节点的rule_set 和父节点的rule_set_L 或者rule_set_R 相同），节点结构关系如图1所示。
每个规则条目包含5个元素srcip 、srcport 、dstip 、dst-
port 、protocol ，每个元素对应一个区间范围或者单个实数，以元素i 在RAW-SET 中端点的集合建立规则树R-TREE i ，最终建立5个规则树R-TREE i (1≤i ≤5)，对每个连接数据依次查R-TREE i ，最终输出该连接数据符合的规则条目组，如果没有符合的规则条目则认为网络不可达。
规则树建立算法如图2（a ）所示，具体步骤如下：
（1）遍历规则条目，以规则端点为键（key ）建立规则树R-TREE ，R-TREE 的建立算法和红黑树一致，这时的R-TREE 节点中只有键（key ）被赋值，节点取值value_field 为空。
图1规则树节点结构关系示意图
S:(A50,A100)
rule_set1
LS:(A50,key1)rule_set_L1RS:(key1,A100)
rule_set_R1
key1
key2S:(A50,key1)rule_set_L1LS:(A50,key2)rule_set_L2RS:(key2,key1)rule_set_R2key3
RS:(key3,A100)rule_set_R3
S:(key1,A100)rule_set_R1LS:(key1,key3)rule_set_L3
134
2017，53（3）
（a ）规则树建立算法（2）遍历（1）中的R-TREE ，为树中节点value_feild 的S 、LS 、RS 进行赋值，每个节点的S 可以用该节点的父节点的LS 或者RS 进行赋值（root 节点的S 可人为设定），LS 和RS 可以根据S 和key 进行赋值，key 属于LS 还是RS 要根据key 是所在规则区间的左端点还是右端点，如果key 是某个规则区间的右端点，则key 属于LS ，如果key 是某个规则区间的左端点，则key 属于RS 。
（3）在（2）中为S 赋值后，遍历RAW-SET ，根据S 是否为规则条目中元素范围子集来判定该节点的rule_set
是否应该包含对应的raw_rule ，完成rule_set 填充，同理
完成rule_set_L 和rule_set_R 的填充。规则条目匹配就是根据连接数据的srcip 、srcport 、dstip 、dstport 、protocol 进行5棵R-TREE i 的查，并给出查到是否符合规则、符合哪些规则的结果。规则条目匹配算法如图2（b ）所示，具体步骤如下：
（1）用连接数据的srcip 值对R-TREE1（srcip 构成的
规则树）进行查（必须遍历到末端叶子节点）。
（2）如果在遍历R-TREE1的时候，被遍历到的叶子
节点中RULE-SET 为空，说明该连接没有符合的规则，算法结束。
（3）如果被遍历的节点有RULE-SET ，则把RULE-
SET 加入RULE-SET1，
并进入（4）。（4）用连接数据的srcport 值对R-TREE2（srcport 构成的规则树）进行查，重复（2）。（5）如果被遍历的节点没有RULE-SET ，则算法结束，如果有RULE-SET ，则把RULE-SET 加入RULE-
SET2，如果RULE-SET1和RULE-SET2不存在交集，则
说明该连接没有符合的规则，算法结束。
（6）如果RULE-SET1和RULE-SET2存在交集则计算出交集RULE-SET1&RULE-SET2，按照类似的步骤重复（4）、（5）、（6）。
（7）最终如果5个规则树R-TREE
i 的RULE-SETE i 存在交集RULE-SET1∩RULE-SET2∩RULE-SET3∩
RULE-SET4∩RULE-SET5，则说明该连接正常，并且符
合交集中的规则条目。
4实验及分析
实验环境拓扑如图3所示，分为三个网段，192.168.0.0/
24、192.168.1.0/24、192.168.2.0/24，分别编号为0、1、2。
网段之间通过防火墙隔离，防火墙和路由器上分别配置有端口过滤和IP 过滤规则，控制网段之间的可达性。主机192.168.0.2是最终目标主机，攻击目标是获取其SYSTEM 权限。攻击图生成算法最大攻击跳数MAX_HOP 初始
化为3，累积成功率阈值初始化为50%。服务和漏洞的部署分布情况如表1所示。
（b ）规则匹配算法图2
规则树算法流程图主机192.168.0.1192.168.0.2192.168.1.1192.168.1.2192.168.2.1192.168.2.2192.168.2.3服务tomcat7.0.39telnet IIS FTP7.5—PHP 、tomcat RPC core ftp 漏洞编号CVE-2013-4444CVE-2015-0014CVE-2010-3972—CVE-2014-9427CVE-2013-3175CVE-2014-4643利用端口802321—
80
13521
成功率0.80
0.900.750.80
0.80
0.80表1服务和漏洞部署分布表司健，陈鹏，顾宁平，等：网络攻击图逆向深度优先生成算法135
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论