基于攻击图的空间复杂性优化算法研究*

蔡勇平，朱士瑞，许晓东

（1.江苏大学 计算机科学与通信工程学院，江苏 镇江 212013；2.江苏大学信息化中心，江苏 镇江 212013）

0 引 言

当前，网络系统结构的复杂性越来越高，网络攻击手段也更加复杂化和多样化。为了对网络安全制定更好的防御措施，需要对各种复杂的网络攻击行为进行形式化描述。目前，学术界已提出攻击语言、攻击树、攻击网和攻击图等建模方法[1]。攻击图能够彻底找出网络中安全漏洞的所有关联，并对网络中各主机上的脆弱性关联起来进行综合分析，用图的方式将所有攻击路径展现出来。安全管理人员利用攻击图可以直观观察到网络中各脆弱性之间的关系，然后选择最小的代价对网络脆弱性进行巩固防御。

但是，随着复杂网络中主机数量的增加，生成的攻击图异常复杂，极大地影响了它的可视性。为此，研究人员提出了一些方法。例如，文献[2]为了解决这一问题，提出了不包括定量测量的标准安全评估基线，并使用CVSS作为一个标准的复合评分系统，但不能检测漏洞之间的关联性；文献[3]为了解决漏洞之间的关联性，攻击图技术被用于开发识别企业网络的多级攻击；文献[4]则重点研究了攻击图的生成和改进算法的复杂度。这项研究工作的主要优点是考虑了企业网络中脆弱点之间的相互关系。但是，在大规模网络中，生成的攻击图过于复杂，无法被安全管理人员直接理解和使用。为了解决这一问题，文献[5]试图通过化简数据来改进攻击图的可视性，但是并没有从根本上解决这一问题。为此，Sawila和Ou等[6]将Google的页面分级方法引入攻击图中节点的重要性计算中。

本文提出了一种基于攻击图的空间复杂性优化算法，将复杂的攻击图转换成一种只包含攻击者、漏洞结点和攻击目标的简化图，增大了攻击图的可用性，为安全管理人员制定更加精准的系统安全防范措施提出了可靠意见。

1 基本原理

攻击图是为了发现复杂网络中存在的攻击路径，通过综合攻击者、漏洞结点、攻击目标主机和网络连接关系等因素，提出的一种描述网络安全状态的表示形式。攻击者对网络目标进行攻击时，首先利用某个主机上的脆弱点来获得某个权限，然后在此基础上发起新的攻击。如此反复，直至攻击者达到其攻击的最终目标。因此，攻击者实施的过程是从前提网络状态到结果网络状态的跃迁过程。

定义1：攻击图。攻击图是一个四元组T=(S,τ,S0,SG)，其中S表示状态集，显示系统中存在可能遭受的攻击路径，由系统中漏洞之间的关联关系描述；τ∈S×S是一个传递函数，指的是攻击之间的关系，由攻击间的因果联系和网络连接状态决定；S0∈S是开始状态集，表示攻击者首先发起的攻击，如进行拓扑扫描等；SG∈S是成功状态集，表示满足攻击者攻击目的的攻击状态，同时也是攻击者的最后一步攻击。

定义2：攻击路径。对于一个目标状态Sn∈SG，如果从初始状态S0开始，存在一组状态序列 S1,S2,…,Sn-1，使得 (Si,Si+1)∈ τ,0 ＜ i＜ n-1，则称状态序列S0,S1,…,Sn是一条攻击路径。

定义3：脆弱点，指网络系统中存在的漏洞。本文用通用漏洞评分系统（Common Vulnerability Scoring System）CVSS来表示脆弱点的强弱。

定义4：攻击复杂度。脆弱点的攻击复杂度是用来衡量攻击者成功利用该脆弱点的难易程度。为了更准确阐述本文所用的方法，本文只取最后root权限的攻击结果。

脆弱点的攻击复杂度是计算脆弱点被成功利用概率的基础。它受多种因素的影响，不容易计算。本文参考汪立冬等[7]人对脆弱点攻击复杂度分级的思想，结合实际情况做出修改，将脆弱点的攻击复杂度分为5级，如表1所示，以10为满值。攻击复杂度越趋近于10，越不容易攻击成功。

表1 攻击复杂度量化标准

2 攻击图简化方法

2.1 全局攻击图生成

攻击图模型的生成采用了MulVal工具。MulVal工具是一种多主机、多级漏洞分析的工具，是一种被安全从业人员利用的研究工具，是一种对网络风险主动探测的工具，可以有效检测到网络的配置信息。MulVal常用来生成网络攻击图，生成攻击图的时间复杂度在O(n2)和O(n3)之间。

MulVal的设计原理中，大部分的配置信息可以使用数据记录（Datalog）元组的方式来表示。大部分的攻击技巧和系统安全语义可以使用数据记录规则分类。一个服务程序中暴露出来的可以导致权限提升的规则可以表示如下：

execCode(Attacker,Host,User):-networkService(Ho st,Program,Protocol,Port,User),

vulExists(Host,VulID,Program,remoteExploit,privEscalation),

netAccess(Attacker,Host,Protocol,Port)

MulVal推理引擎采用了一个名为XSB[8]、由StonyBrook开发的建立在逻辑学理论基础上的Prolog系统。它基于输入的关键因子评估数据记录之间的相互关系。

MulVal工具生成攻击图时，主要依赖于网络系统中本身存在的脆弱性信息、网络中主机端口开放情况以及信息系统内部的配置等信息。网络的脆弱性信息主要从传统的漏洞扫描器中获得。不同的漏洞扫描器会产生不同的扫描报告，这就要求该攻击图生成工具有适配器的功能去适配不同的漏洞扫描系统产生的文件。如图1所示，本地数据库同步NVD（National Vulnerability Database）[9]数 据， 漏洞扫描器结合本地同步数据库，对局域网内脆弱性漏洞信息进行扫描。MulVal工具提供了两种漏洞扫描器扫描报告的转化适配器，一种是OVAL扫描器，一种是Nessus漏洞扫描器。适配器的功能主要是将漏洞扫描器产生的报告文件规划为统一的格式，该格式的文件结合网络的配置信息能重新整合成一个标准的攻击图，从而生成工具MulVal的输入文件，可以使用MulVal生成标准的攻击图模型。

图1 漏洞扫描器报告适配方式

2.2 空间复杂性优化算法的定义

通过MulVal生成的攻击图可能太大和过于复杂，因此提出了一个将攻击图的空间复杂性优化为简化图的算法。该算法将复杂攻击图转换成只包含攻击者、漏洞结点和攻击目标的简化图，很好展示攻击者在漏洞之间的动向。具体的空间复杂性优化算法流程如图2所示，分为4个步骤：

步骤1：找到攻击目标和包含漏洞的叶节点之间的所有路径。

步骤2：在包含漏洞的叶节点之间找到所有的顶点以及找到所有有攻击目标的叶节点。

步骤3：找到从叶节点到攻击目标的顶点。

步骤4：发现攻击者首先可能的步骤和相关顶点。

MulVal的 输 出 包 括“input.txt”“Vertices.CSV”“ARCS.CSV”以及“AttackGraph.txt”。其中，“input.txt”是MulVal的输入文件，主要包括一些网络配置、网络结点和漏洞的相关信息。“Vertices.CSV”包含攻击图的一些顶点，“ARCS.CSV”包含所有顶点之间的边。“AttackGraph.txt”是攻击图的文件格式模板。

在空间复杂性优化算法中，Vt（16行）是简化图的顶点，Et（15行）代表的是简化图的边。

图2 算法流程

简化图的算法过程如下：

1.lineofinputFile=Read(input.txt)

2.linesofArcsFile=Read(ARCS.CSV)

3.linesofVerticesFile=Read(Vertices.CSV)

4.linesofAttackFile=Read(AttackGraph.txt)

5.V=defineVertices(linesofVerticesFile)

6.E=defineEdges(linesofArcsFile)

7.attackGoals=defineRootNodes(linesofAttackFile)

8.leaves=defineLeaves(linesofVerticesFile)

9.attackerLocation=defineAttackerLoc(linesofVerti cesFile)

10.G=defineDirectedGraph(V,E)

11.pathsVt=definePathsvulExists(G,attackGoals,lea ves)

13.edgestoNGoalV=defineArchsvPaths(pathsVt)#et

14.Et=edgestoNGoalV+defineArchstoGoals(pInclu deVstoGoals,attackGoals)+defineAttackerFirstSteps(line sOfVerticesFile,pathsVt,attackerLocation)

15.Vt=attackerLocation+attackGoals+{leaves if vulExist=True}

16.G2=nx.DiGraph()

17.G2.add_nodes_from(Vt)

18.G2.add_edges_from(Et)

19.showGraph(G2)

1.2.1 血常规检查 抽取患者外周静脉血2 mL并用乙二胺四乙酸二钾(EDTA-K2)抗凝，用Sysmex-3000血常规分析仪进行血常规检查。

20.End procedure

过程1中（第12行，算法中definePathvul Exists()）返回的是所有攻击目标到包括的边的路径。这个过程中，使用一种改进的深度优先搜索算法生成所有由目标到顶点的路径。

过程1：攻击目标与漏洞之间的路径

procedure definePathsvulExists(G,attackGoals,leav es)

allPaths=Ø

For i=1 to length(attackGoals) do

For j=1 to length(leaves) do

leaves[j],attackGoals[i]))

End For

End For

End procedure

过程2（算法第13、14行）返回的是边和包含漏洞的叶结点之间的路径和攻击目标到边之间的路径。

过程2：寻找边到叶结点为真的路径

procedure defineArchsvPaths(pathsVt)

et=Ø

tempPaths=pathsVt

For i=1 to length(vPaths) do

X=vPaths.remove(vPaths(i))

For j=1 to length(X) do

et=et+(X[j].leaf.number,vPaths[i].leaf.number)

tempPath=tempPath.remove(X[j])

End If

End For

End For

return et, tempPath

End procedure

过程3（算法第15行）利用过程2的第二个输出找到攻击目标的所有边。

过程3：找到攻击目标的所有边

procedure defineArchstoGoals(pIncludeVstoGoals,a ttackGoals)

et=Ø

For i=1 to length(pIncludeVstoGoals) do

For j=1 to length(attackGoals) do

If j!=length(attackGoals)Then

If tempPaths[i].leaf.number＞attackGoals[j] and tempPaths[i].leaf.number＜attackGoals[j+1]

Then

et=et+(tempPaths[i].leaf,attackGoals[j])

End If

End If

Else If j==length(attackGoals) then

et=et+(tempPaths[i].leaf,attackGoals[j])

End If

End If

End For

End For

End procedure

过程4（算法第15行）在简化图上找到攻击者第一步可能的边。

过程4：找到攻击者首先可能的步骤和简化图的相关边

procedure defineAttackerFirstSteps(linesOfVertices File,pathsVt,attackerLocation)

For all item in linesOfVerticesFile do

If item includes “hacl” and “internet” then

tempList=tempList+item

End If

End For

For all item in tempList do

O1=find the first occurrence of‘(‘

tempList2=tempList2+string between O1 and O2

O2=find the third occurrence of ‘,’

End For

For all item in tempList2 do

For item2 in pathsVt do

If item2.find(item)Then

firstSteps=firstSteps+item.number

End If

End For

End For

For all item in firstSteps do

firstPSteps=firstPSteps+(attackerLocation,item)

End For

End procedur

3 实验分析

3.1 网络拓扑和实验环境

网络拓扑图如图3所示，有包含Web服务器和文件服务器在同一子网的五种服务。一个Citrix和VPN服务器在同一个网络中，还具有两个工作站运行Acrobat和浏览器。另外，有两层防火墙为网络和路由器防火墙。此网络拓扑中的网络连接用以下规则阐述：①攻击者在Internet上可以通过HTTP协议和HTTP端口访问Web服务器、VPN服务器、Citrix服务器和通信服务器。②web服务器和其他机器之间双向连接。③VPN服务器和Citrix服务器、工作站通过HTTP协议和HTTP端口之间存在双向连接。④通信服务器和数据之间通过HTTP协议和端口进行双向访问。⑤文件服务器和工作站可以通过NFS协议和NFS端口相互访问。

图3 网络拓扑

网络拓扑图中有4种不同的漏洞，漏洞由唯一的标识符来识别。这些标识符由国家脆弱性数据库（NVD）掌握。Citrix服务器包含了代号为“1020-0490”CVE漏洞，是基于浏览器的漏洞，它被攻击后，远程入侵者可以在目标计算机上执行任意代码的操作。VPN服务器包含的“2010-0492”CVE是有关IE8浏览器的，攻击者可以在目标机器上执行任意代码。通信服务器中包含的漏洞为“2010-0483”CVE，主要与windows的VBScript有关。当使用IE浏览器时，攻击者可以在目标计算机上执行任意代码。数据库包含“2010-0494”CVE漏洞，主要与IE 6、IE 7和IE 8有关。攻击者可以进行跨站点脚本攻击，如表2所示。

表2 网络拓扑中的漏洞

3.2 攻击图和简化图的生成

使用MulVal生成的网络攻击图，如图4所示，显示了攻击图中的相关结点。攻击图中有3个不同的顶点。正方形顶点（结点6，结点13，结点8）与系统配置有关，如防火墙规则允许Web服务器从浏览器或机器上的故障软件进行访问。菱形顶点（结点10，结点3，结点28）表示攻击者可能在系统中获得潜在的特权或访问权限，如Web服务器上的代码执行特权。椭圆的顶点（结点11，结点4，结点29）连接条件、后置条件，如攻击者必须具有访问漏洞的机器才能利用该漏洞获得特权。

优化算法：

1."execCod(citrixServer,user)","OR",0

2."RULE 3(remote exploit for a client program)","AND",0

3."accessMaliciousInput(citrixServer,victim_2,ie)","OR",0

4."R ULE 2 2 (B ro w si n g a ma l ic io u s website)","AND",0

5."attackerLocated(internet)","LEAF",1

6."hacl(citrixServer,internet,httpProtocol,httpPort)","LEAF",1

7."inCompetent(victim_2)","LEAF",1

8."hasAccount(victim_2,citrixServer,user)","LE AF",1

9."vulExists(citrixServer,'CVE-2010-0490',ie,rem oteClient,privEscalation)","LEAF",1

10,"execCode(commServer,user)","OR",0

11."RULE 3 (remote exploit for a client program)","AND",0

12."accessMaliciousInput(commServer,victim_1,wi ndows_2000)","OR",0

13."RULE 22 (Browsing a malicious website)","AND",0

14."hacl(commServer,internet,httpProtocol,httpPort)","LEAF",1

15."inCompetent(victim_1)","LEAF",1

16."hasAccount(victim_1,commServer,user)","LE AF",1

17."vulExists(commServer,'CVE-2010-0483',wind ows_2000,remoteClient,privEscalation)","LEAF",1

18."execCode(dataHistorian,root)","OR",0

19."RULE 2 (remote exploit of a server program)","AND",0

20."netAccess(dataHistorian,httpProtocol,httpPort)","OR",0

21."RULE 5 (multi-hop access)","AND",0

22."hacl(commServer,dataHistorian,httpProtocol,htt pPort)","LEAF",1

23."networkServiceInfo(dataHistorian,mountd,http Protocol,httpPort,root)","LEAF",1

24."vulExists(dataHistorian,'CVE-2010-0494',mo untd,remoteExploit,privEscalation)","LEAF",1

25."execCode(vpnServer,user)","OR",0

26."RULE 3 (remote exploit for a client program)","AND",0

27."accessMaliciousInput(vpnServer,victim_5,open vpn)","OR",0

28."RULE 22 (Browsing a malicious website)","AND",0

29."hacl(vpnServer,internet,httpProtocol,httpPort)","LEAF",1

30."inCompetent(victim_5)","LEAF",1

31."hasAccount(victim_5,vpnServer,user)","LE AF",1

32."vulExists(vpnServer,'CVE-2010-0492',openvp n,remoteClient,privEscalation)","LEAF",1

利用该算法对攻击图进行改进，结果如图5所示。可以看出，转换图只包含攻击者位置、漏洞和攻击者的顶点。这种简化图可以很容易使安全管理员理解网络的安全状态。

图4 攻击图

图5 简化图

4 结 语

随着互联网技术的发展，接入到互联网的主机数量呈现迅猛的发展趋势，带来的网络安全问题日益凸显。攻击图技术是一种在攻击发生前的主动探测[10]，但随着网络规模的扩大，攻击图的生成存在空间状态爆炸问题，产生了很多冗余的攻击路径，往往影响网络安全管理员的分析效率。为了解决这一问题，本文提出了一种基于攻击图的空间复杂性优化算法，将复杂的攻击图转换成一种只包含攻击者、漏洞结点和攻击目标的简化图，增大了攻击图的可用性，并通过实验证明了该方法的有效性。后续将在现有的成果上进一步研究该简化图在网络脆弱性量化分析上的作用，进一步完善攻击图模型在网络脆弱性评估中的价值。