一种面向攻击图的即时验证方法

王 婷,董 浩,陈铁明

(浙江工业大学 计算机科学与技术学院,杭州 310023)

1 引 言

互联网是一柄双刃剑，在给人们带来便利与机遇的同时，也使人们暴露在危险之中.随着计算机和互联网技术的飞速发展，网络规模日趋庞大，网络复杂性越来越高，几乎每天都有新的漏洞出现，网络安全面临的挑战日趋增多.近年来网络攻击越来越多，呈现途径多样化、手段复杂化的趋势.攻击者往往将原本孤立的网络漏洞有机结合起来，不同漏洞的组合使攻击者可以进行很难识别和防御的多步骤攻击.

目前保护网络系统免受安全威胁成为了热门的研究领域.传统的漏洞扫描技术将网络中的攻击行为割裂开，独立地分析每个漏洞，无法洞察它们相互作用而产生的威胁，因此不足以应对现如今复杂且隐蔽的网络攻击.攻击图[1,2]作为一种基于的网络脆弱性分析技术[3]，可以展现出不同脆弱性之间关联关系，对网络安全威胁评估具有十分重要的意义.本文提出一种面向攻击图的即时路径搜索方法对大规模网络进行安全评估.通常情况下，只需构造目标网络的部分状态空间，就可以快速搜索到一条可能的完整路径.特别是对大规模网络，这有利于网络安全人员更快速地找到网络系统的安全隐患.

本文第2节介绍了相关研究工作以及本文算法的思路；第3节详细介绍了攻击图，并提出了攻击模型；第4节介绍了攻击路径搜索和攻击路径补全过程，以及相关算法；第5节用对比实验来说明本文所提方法具有良好的性能和可扩展性；最后在第6节做出总结，指明未来的工作方向.

2 相关工作

根据构建方式攻击图可分为状态攻击图和属性攻击图，早期的攻击图大多是状态攻击图[4-6]，由网络安全研究人员以配置文件、攻击者档案、攻击模板数据库为依据，手动创建.在此基础上，结合模型检测、智能规划技术自动生成攻击图，罗列出所有系统状态，来展现网络威胁转移情况.

状态攻击图在处理大规模网络时，存在空间爆炸问题[7]，并且不够直观.因此近年来通常采用属性攻击图进行网络脆弱性分析研究.文献[8]基于属性攻击图搜索所有攻击路径，并提出了最优弥补集问题的近似算法，以最小的代价获得最大的安全收益.文献[9]针对工业控制系统，根据记录的目标状态描绘出所有攻击场景.文献[10]利用反向搜索算法找出物联网系统所有可能攻击路径并将威胁程度量化，制定最优防御策略.文献[11]提出了一种紧凑的图规划算法，从目标状态开始提取相关信息，反向生成所有攻击路径.同样的，文献[12]使用反向深度优先算法生成攻击图，检测网络可达性，为评估整个网路系统的安全性提供了依据.文献[13]利用邻接矩阵自动评估网络漏洞风险，对大规模网络中的重要漏洞进行重点分析，并实现分析结果可视化.文献[14]基于贝叶斯攻击图，采用启发式策略，由针对性的制定防御措施.

应用状态规约技巧可以优化攻击图分析方法，即时验证技术[15-17]只展开基本分支，而不需要构造完整的攻击图.也就是说，在分析网络系统时并不是把系统全部构造完成后再去评估，而是根据网路系统的待检测的安全属性去展开攻击路径，一边构造网络系统模型一边验证攻击行为是否成立.这样做最大的优点是，一旦找到一个反例，即一条攻击路径，算法就会终止，而不必生成其它状态空间，在一定程度上解决了状态空间爆炸问题.

基于上述分析，本文在前人研究的基础上提出了一种面向攻击图的即时验证方法，快速寻找网络中一条可能的攻击路径，而不需要访问所有节点以及找到所有路径，以实现大规模网络安全的快速查找和分析.其主要思路是，首先将网络漏洞、攻击者权限、网络连接情况等信息抽象成攻击图模型的输入，然后在此基础上构建攻击路径搜索算法APS(Attack Path Search)来快速搜寻出一条可行路径.由于APS算法得到的攻击路径丢失了部分信息，必须利用路径补全算法APF(Attack Path Fix)将此攻击路径补充完整.在平均情况下改进明显.

3 攻击图及网络系统建模

3.1 攻击图

攻击图AG在网络脆弱性分析领域被广泛应用，主要可以分为状态攻击图和属性攻击图，为了增加可读性，本文所提到的攻击图均为属性攻击图.攻击图是一个有向图，通常包含两类节点和两类边.节点包括属性节点和攻击节点，其中属性节点包括网络脆弱性和权限信息，网络脆弱性描述网络主机固有的安全漏洞，而权限节点描述攻击者所具备的权限等级.两类边中，一类是由属性节点指向攻击节点，另一类是由攻击节点指向属性节点.攻击图定义如下.

定义1.AG=(S,T,E)，其中：

1)S={A∪N}是属性节点集合，A是初始条件节点集合，N是可达属性节点集合，T是攻击节点集合.

2)E={ES∪ET}表示有向边集合，即集合ES⊆S×T表示属性节点触发攻击节点的边集合，集合ET⊆T×N表示经过攻击动作获得可达属性节点的边集合.

图1 小型网络配置Fig.1 Simple network topology

3) 一个攻击动作的成功实施，需要满足它所有的前置条件，即前置条件间是与(AND)的关系.假设tn的precon={n1,n2,…,nn}，那么tn←n1∧n2∧…∧nn.一个属性的获得，只需成功实施一个攻击动作即可，即如果有多种攻击可以获得该属性，那么攻击动作间是或(OR)的关系.假设t1,t2,…,tn的postcon={nn}，那么nn←t1∨t2∨…∨tn.

表1 攻击图实例中的属性Table 1 Attributes of attack graph

图1是一个小型网络，由主机0、主机1和主机2组成，其中主机0被攻击者控制，主机1和主机2是目标主机.主机都存在某些漏洞，攻击者可以利用这些漏洞在主机0发动攻击来获得目标主机的控制权.

表2 攻击图实例中的原子攻击Table 2 Atom attacks of attack graph

针对图1小型网络的攻击图如图2所示，该图中圆形代表属性节点，其含义由表1给出.矩形代表攻击节点，其含义由表2给出.如果属性节点有一条指向攻击节点的边，那么该属性节点就是该攻击节点的前置条件.如果攻击节点有一条指向属性节点的边，那么该属性节点就是该攻击节点的后置条件.例如，图2中user(0)和ftp(0,2)是Ftp-rhost(0,2)的前置条件，而trust(0,2)则是Ftp-rhost(0,2)的后置条件.

图2 小型网络攻击图Fig.2 Attack graph of simple network

3.2 攻击路径

定义2.攻击路径是从源主机开始，攻击者实施一系列攻击行为后达到目标goal的过程，由一系列原子攻击按照一定顺序关联而成,定义如下.

1)goal是目标节点，ai∈A,si∈S,ti∈T,0≤i≤n,则粗糙路径*path(goal)=ai→s0→t0→s1→t1→s2→…→si→ti.

2) 对粗糙攻击路径进行补全操作，并且只保留其中的攻击节点,则得到完全攻击路径cpath(goal)=t0→t1→…→ti.

以图2为例，假设goal=root(2)，搜索得到一条可能的粗糙路径*path(root(2))=user(0)→sshd-bof(0,1)→user(1)→ftp(1,2)→Ftp-rhosts(1,2)→trust(1,2)→rsh(1,2) →user(2)→local-bof(2).由于有AND关系的存在,粗糙路径不能代表完整的攻击过程，要对其进行补全操作.经过补全并移除属性节点而得到的完全攻击路径应当是cpath(root(2))=→sshd-bof(0,1)→Ftp-rhosts(1,2)→rsh(1,2)→local-bof(2).具体算法将在后续章节中给出.

3.3 网络系统建模

攻击者要想成功实施一次攻击，必须满足某些前提条件.攻击者需要先通过漏洞扫描发现某网络上的主机是否存在可用于尝试攻击的漏洞，再发动攻击.单次成功实施的攻击不一定能直接达到攻击者的目的.大多数网络攻击包括一系列攻击，这些攻击会逐渐增加网络的脆弱性，直到满足最终攻击的先决条件.成功实施攻击的结果可能包括发现新的漏洞、提升用户权限、打破原有筛选规则以及在其他主机中添加信任关系等.以下为对攻击模型的相关定义.

定义3.漏洞定义为一元组vulner(attribute)，其attribute表示网络系统的固有安全隐患.例如，协议漏洞、软件漏洞、硬件漏洞等.

定义4.网络连接定义为二元组link(sid,did)，sid是源主机的主机号，did是目标主机的主机号.例如，link(s,d)表示主机s和主机d存在网络连接.

定义5.漏洞存在性定义为二元组defect(vulner,link)，其中vulner表示目标主机上可利用的漏洞，link表示源主机和目标主机存在网络连接.例如，假设vulner=(x)，link=(a,b)，那么defect(x,(a,b))表示主机a和主机b之间存在着攻击者可以利用的漏洞x.

定义6.权限定义为二元组right=(id,privilege)，其中id表示主机号，privilege表示攻击者在该主机上拥有的权限,包括none、user和root.例如，right(n,root)表示攻击者在主机n上拥有root权限.

定义7.攻击模板定义为三元组template(atom,precon,postcon)，其中atom是原子攻击，precon是原子攻击的前置条件集合，postcon是原子攻击的后置条件集合.例如，攻击者具有主机a的user权限(即right(a,user)，主机a和主机b存在网络连接(即link=(a,b))，且主机b存在漏洞x(即defect(x,(a,b))，则攻击模板中的atom=x，precon={user(a),x(a,b)}，如果攻击结果是获得主机b的user权限，则postcon={user(b)}.

4 攻击图的即时验证

4.1 攻击路径搜索算法

属性节点在攻击过程中是不断扩展的，相当于攻击者知识库.从初始节点开始进行广度优先搜索，后续节点的产生过程根据节点类型不同有所区别.对属性节点来说，查找可进行的攻击从而获得攻击节点：根据当前属性节点(单个节点)，首先遍历攻击模板库，找到前置条件中包含该属性节点的所有模板，然后遍历攻击者知识库，检查每个模板所有前置条件是否满足，如果符合则生成一个后续攻击节点.由攻击节点查找属性节点较为容易，只需要根据攻击模板的后置结果得出.给定任意一个节点node，将上述后续节点生成过程定义为getChildren(node).

算法1如图3所示，为基于广度优先的攻击路径搜索算法.算法中有4个数据结构，其中有序列表visited(按照访问先后顺序排列)记录已经访问过的节点，队列working存储待访问的节点，列表path记录当前节点路径，列表集合paths存储访问过的path.在第6行-第23行的循环中，首先当前节current从working出列，current所在路径path从paths出列.第9行-第12行判断current是否满足goal，如果满足则停止搜索，否则继续搜索直到working为空.current和path，working和paths两组变量各自同步变化，以此来跟踪记录当前路径.第13行判断current是否有后续子节点，如果存在，则执行第14-第21行的循环，将所有没有被访问过的后续节点加入visited并入队working，再加入对应的path，并将path入列paths.第24行返*path(goal)，如果全部节点搜索完毕，没有发现目标节点，则返回的*path(goal)为空集.

4.2 攻击路径补全算法

在进行补全操作时，一个必要的步骤使获得某节点的父节点.如果由属性节点查找父攻击节点，则需要遍历攻击模板库，找到后置条件中包含该属性节点的所有模板，得到所有可能的攻击节点；如果由攻击节点查找父属性节点，则只需要根据对应攻击模板的前置条件得出所有属性节点.给定任意一个节点node，将上述节点生成过程定义为getParents(node).此外，如果node1在*path(goal)中位于node2之前，将其定义为node1.Pre(node2,*path(goal))为真.

算法2如图4所示，为基于广度优先的路径补全算法.将初始节点集合A，由算法1得到的已访问节点集合visited和粗糙路径*path(goal)一并作为算法2的输入，并沿用算法1的数据结working.在第2行-第21行的循环中，*path(goal)中所有的攻击节点进行判断，对于某个攻击节点current的每一个父节点(current的前置条件)，如果该节点在*path(goal)中没有位于current之前，且该节点不属于A，并且在整个攻击过程中最先生成该节点的攻击节点(current的前置条件的父节点)在*path(goal)中也没有位于current之前，就进行相应的插入操作.重复上述过程直到working为空.最后移除*path(goal)中的属性节点得到cpath(goal)，需要注意的是，如果此时攻击路径中还有重复的节点，则只需保留第一个即可.

4.3 算法实例

用图5的例子来说明算法1和算法2，其中A={a0,a1,a2,a3,a4,a5}，N={s0,s1,s2,s3,s4,s5,s6,s7,s8}，T={t0,t1,t2,t3,t4,t5,t6,t7,t8,t9}.首先将A中节点全部入队working并加入visited，利用current和path，working和paths两组变量各自同步变化实现搜索路径的自动切换.然后进行广度优先搜索，对current的后续子节点进行判断其是否已经被访问，如果是，则进行相应操作.经过循环可以得到一条最先到达t7的路径*path(s6)=a3→t5→s4，但是因为t7的precon={s2,s4,s5}，此时s2和s5还不在visited中，所以无法得到s4的后续节点t7，并且此时还没有找到goal，所以要继续搜索其他路径.不断重复上述过程，当t7的precon全部在visited中，会找到一条可能的粗糙攻击路径*path(s6)=a5→t9→s8→t8→s7→t6→s5→t7→s6.

将由算法1得到的*path(s6)作为算法2的输入，算法2的第一个while循环首先检查t9，将t9入working.t9出队后，由于t9的父节点只有初始节点a5且其已经处于*path(s6)中t9之前的位置(表示攻击者已拥有的知识库)，因而接着while循环检查t8.当检查到t7时，由于getParents(t7)={s2,s4,s5}，其中s5已经处于*path(s6)中t7之前的位置，则跳过.对于s2来说，其父节点为t4，发现两者都不处于*path(s6)中t7之前的位置，则将t4和s2按顺序插入到*path(s6)的t7之前，注意此时t4一定在visited里，再将t4入队working;对于t5和s4的操作也是一样，将两者按顺序插入到*path(s6)的t7之前并将t5加入队列.从队列中获得t4，发现其父节点为s1，而s1有3个父节点t0、t1和t2.对于这种有多个父攻击节点的情况，只选择在visited中位置最靠前的节点即可.这是由于在visited中位置越靠前的节点越接近A，有利于补全操作提早结束.假设在visited中t0比t1位置靠前，则将t0入队并把t0和s1按照顺序插入到*path(s6)的t4之前.其余部分以此类推.经过上述过程，得到*path(s6)=a5→t9→s8→t8→s7→t6→s5→t0→s1→t4→s2→t5→s4→t7→s6.最后再移除*path(s6)中的属性节点得到*path(s6)=t9→t8→t6→t0→t4→t5→t7.

5 性能测试与分析

文献[9-12]所提算法利用深度优先或广度优先搜索攻击路径，均是基于属性攻击图进行反向搜索，必须要遍历所有节点.将上述方式与本文的路径搜索算法和路径补全算法进行对比实验，比较不同方法在不同网络设置、不同网络规模下的CPU运行时间，单位为秒(S)，以及所遍历的节点个数.设置时间阈值，如果运行时间大于3000秒，则认为算法失效.模拟网络由主机、防火墙和路由器构建而成.实验环境为：CPU是Intel Core i5-7300HQ，主频为2.50GHz，RAM是16G，操作系统是windows 10.

在实验1中，目标网络规模主机数量从只有3台逐渐扩大到1000台，将防火墙过滤规则全部设置为any，路由器不进行IP过滤，即各主机之间是全连接的.如表3所示，反向搜索方式和本文算法随着主机数量的增加，CPU运行时间和遍历的节点数量也随之增加.然而使用反向搜索方式对网络进行分析时，必须要找出所有攻击路径，本文算法正向搜索到目标节点就停止搜索，补全后给出一条完全的攻击路径，无须生成整个攻击图，遍历的节点数量明显少于反向搜索方式，所以本文算法拥有良好的性能.

表3 全连接网络对比实验Table 3 Fully connected network comparison experiment

由于现实世界中很少有全连接的网络结构，所以我们通过设置防火墙和路由器的端口过滤和IP过滤规则，控制主机间的可达性，使目标网络不再是全连接.这意味着攻击者要想达到目标节点，可能需要搜索更多节点，进行更多次的原子攻击.实验2目标网络规模主机数量从只有3台逐渐扩大到1000台，观察两种算法在更接近现实的网络环境中的性能表现.如表4所示，当实验2中的目标网络中的主机数量达到1000时，反向搜索方式失效.可以看出，本文算法拥有良好的可扩展性.

表4 非全连接网络对比实验Table 4 Non-fully connected network comparison experiment

为了验证本文算法在最坏情况下依然可行，实验3依旧选取反向搜索方式和本文算法进行比较.目标网络规模主机数量从只有3台逐渐扩大到500台，网络设置同实验1.选择特定目标节点goal使本文算法需要搜索所有路径才能找到goal.如表5所示，在最坏的情况下，即需要搜索全部路径才能找到目标节点goal时，本文算法的CPU运行时间以及所遍历的节点数量略大于反向搜索方式，但是不会带来过多额外开销.这是因为本文算法在找到目标节点后，要对其中一条粗糙攻击路径进行补全操作，给出一个完整的攻击过程.实验3表明，即便在最坏的情况下，本文算法依然有较高的性能和良好的扩展性.

表5 最坏情况下的全连接网络对比实验Table 5 Worst case fully connected network comparison experiment

6 结束语

本文针对大规模网络的安全验证问题进行了研究，提出了面向攻击图的即时验证方法，采用正向搜索方式，并包括补全操作，多数情况下无须生成完整攻击图，就可以给出一条完整的攻击路径.实验结果表明，本文方法具有良好的扩展性和算法性能，可用于快速分析大型网络.未来将继续研究算法优化问题，并且进一步探索其如何更好地解决实际问题.