评估单目标的攻击图自动构建方法SGA-AGC

◆张汉卿

（河北外国语职业学院 河北 066311）

评估单目标的攻击图自动构建方法SGA-AGC

◆张汉卿

（河北外国语职业学院 河北 066311）

本文提出了评估单目标的攻击图自动构建方法SGA-AGC（Single Goal Assessment-Attack Graph Construction）。实验结果表明：搜索深度最大值对算法的影响最大，然后依次是目标网络系统中主机数量、每台主机最多拥有的脆弱性数量和原子攻击数量，本文算法的性能优于文献[4]和文献[5]中的算法。

计算机网络；单目标；攻击图

0 引言

通过分析现有构建方法的不足，根据现实应用的安全需求，本文给出了一种自动构建攻击图的方法：评估单目标的攻击图自动构建方法SGA-AGC。SGA-AGC方法将正向攻击图生成算法和反向攻击图生成算法结合起来，采用多线程的方法，同时从攻击者的初始位置和攻击者的攻击目标出发进行分析，即正向搜索和反向搜索同时进行，大大提高了搜索的速度，从而减小了算法的时间复杂度。

1 问题的提出

定义1：资产。目标网络系统中具有价值的资源，包括数据库、文档信息、软件服务等，是网络安全管理者保护的对象。

定义2：关键资产。由于不同的资产对全局目标网络系统所起的作用是不同的，因此资产的重要程度是不同的，本文将重要程度高的资产称为关键资产。

在现实的应用中，重要程度低的资产尽管也存在着脆弱性，但其对全局目标网络系统的安全性的影响微乎其微，相反，若关键资产的脆弱性被攻击者利用，其对全局目标网络系统的影响将是巨大的、致命的[1]。因此，有的网络安全管理者将脆弱性评估的重点放在对目标网络系统的安全运行起着举足轻重的关键资产上[5]，基于此，本文提出了一种基于正反双向搜索策略的、评估单目标的攻击图自动构建方法SGA-AGC。

2 SGA-AGC算法及其优化策略

定义3：攻击对队列。只有当前提属性集合中的属性都满足时，原子攻击才能被攻击者实施，从而获得后果属性。其中，前提属性集合中的权限属性反映了攻击者拥有的权限，包括Root、User和None；后果属性反映了攻击者实施攻击后，所获得的新属性，包括RunCode、DOS等。为了准确地描述具体的攻击过程，本文定义了攻击对队列，该队列中元素的格式为（权限属性：后果属性）。

定义 4：攻击属性对队列。为了使用Graphviz工具绘制攻击图，本文定义了攻击属性对队列，该队列反映了原子攻击的前提属性集合和后果属性集合，队列中元素的格式为（权限属性：后果属性：攻击属性集）[2]。其中权限属性与后果属性同定义3，攻击属性集合包含了原子攻击前提属性集合中除权限属性外的其它属性，如主机可达性关系和存在的脆弱性等。

定义5：间隔元素。在攻击对队列中，为了将不同搜索深度的攻击对间隔开，本文定义了形式为（c：c）的间隔元素，其中c为任意符号。

定义6：在攻击对队列中，若元素（1c：2c）满足2c为最终攻击目标，则称钙元素为终端元素。

SGA-AGC算法的基本思想：首先将正向攻击图生成算法和反向攻击图生成算法集合起来，采用双线程的方法，同时从起始攻击点和攻击目标出发进行分析，即使正向搜索和反向搜索同时进行[3]；然后利用间隔元素和终端元素生成攻击路径；最后结合攻击路径，利用绘图软件（Graphviz、Visio）生成攻击图。SGA-AGC算法流程图如图1所示。

图1 SGA-AGC算法流程图

SGA-AGC算法的优化策略：一方面，攻击者不会采用很复杂的攻击手段，即攻击者不会以太多的主机为跳板进行攻击；另一方面，在正向搜索过程中，有的攻击路径不会出现攻击目标，或者在反向搜索过程中，有的攻击路径不会出现起始攻击点，对这样的攻击路径进行更深层次的搜索是没有意义的。因此，SGA-AGC算法采用限制搜索深度的优化策略，在具体的实现过程中，用户可以设定搜索深度的最大值。

3 实验结果与分析

为了验证SGA-AGC算法的可行性、有效性和可扩展性，本文从不同的角度进行实验分析。实验环境如下：服务器PowerEdge R710，操作系统RetHat v5.4，内存32G，CPU 2.26GHz。

由SGA-AGC算法性能分析可知，该算法性能与目标网络系统中主机数量H、搜索深度最大值N、每台主机最多拥有的脆弱性数量Nvul、原子攻击数量Nexploit等参数有关[4]。为了验证不同网络环境下这些参数对算法性能的影响，分别设计了如下四组实验。

第一组实验验证网络系统中主机数量对算法性能的影响。令每台主机最多拥有的脆弱性数量为1，原子攻击数量为1，搜索深度最大值为5，当目标网络系统中主机数量不同时。算法CPU消耗时间随着H的增加呈多项式增加趋势。

第二组实验验证搜索深度最大值对算法性能的影响。令每台主机最多拥有的脆弱性数量为1，原子攻击数量为1，主机数量为300，当搜索深度最大值不同时，算法CPU消耗时间随着N的增加呈指数增加趋势。

第三组实验验证每台主机最多拥有的脆弱性数量对算法性能的影响。令主机数量为300，搜索深度最大值为5，原子攻击数量为1，当主机最多拥有的脆弱性数量不同时，算法CPU消耗时间随着Nvul的增加呈线性增加趋势。

第四组实验验证原子数量对算法性能的影响。令主机数量为300，搜索深度最大值为5，原子攻击数量为1，当原子数量不同时，算法CPU消耗时间随着Nexploit的增加呈线性增加趋势。

由上述四组实验结果可知，在SGA-AGC算法中，搜索深度最大值N对算法性能的影响最大，然后依次是目标网络系统中主机数量H、每台主机最多拥有的脆弱性数量Nvul和原子攻击数量Nexploit，该实验结果与算法性能分析结果一致。

目前，与SGA-AGC算法比较相近并且做了类似实验分析的主要有文献[4]和文献[5]。其中，文献[4]所提算法（算法1）是一种迭代算法，从攻击图出发，采用深度优先的搜索策略，反向搜索攻击路径；文献[5]提出了DFAGG算法（算法2），从初始状态出发，采用深度优先的搜索策略搜索能够到达攻击目标的攻击路径。

4 结论

本文通过深入分析现有攻击图构建方法的不足，针对评估单目标安全性的需求，提出了评估单目标的攻击图自动构建方法SGA-AGC。SGA-AGC算法采用正反双向的搜索策略，首先将正向攻击图生成算法和反向攻击图生成算法结合起来；然后利用间隔元素和终端元素生成只与攻击目标有关的攻击路径；最后结合攻击路径，利用Graphviz、Visio软件生成攻击图。为了验证算法的可行性、有效性和可扩展性，从不同的分析角度做了验证实验，实验表明本文算法大大减小了时间复杂度，从而显著提高了其性能。

[1]张海霞, 连一峰, 苏璞睿等.基于安全状态域的网络评估模型[J].软件学报, 2009.

[2]VARDI Y, ZHANG Cunhui. Measures of network vulnerability[J]. IEEE Signal Processing Letters, 2007.

[3]陈峰.基于多口标攻击图的层次化网络安全风险评估方法研究[M].长沙: 国防科技大学出版社, 2009.

[4]MELL P. The common vulnerability scoring system (CVSS)and its applicability to federal agency systems[R]. NIST Interagency Report 7435, 2007.

[5]Xinming Ou. A logic-programming approach to network security analysis[D]. Princeton: Princeton University, 2005.