基于分布并行处理的攻击图构建方法研究

马俊春，孙继银，王勇军，赵宝康，陈珊

(1.国防科学技术大学 计算机学院，湖南 长沙410073;2.第二炮兵工程学院，陕西 西安710025;3.中国人民解放军96617 部队，四川 泸州646000)

0 引言

攻击图展示了攻击者逐步利用网络中各脆弱点进行安全破坏的所有可能的攻击路径，安全管理员不仅可以利用它直观地了解目标网络中存在的潜在威胁，进行网络安全评估［1－3］，而且可以将它与IDS(入侵检测系统)等安全产品组合，根据实时安全事件预测攻击者的攻击意图［4－5］。因此，研究大规模复杂网络系统的攻击图构建方法具有重要的现实意义。

攻击图的构建方法经历了从手工分析到自动分析，从分析小型企业网络到大规模复杂网络的发展过程。目前，美国、英国、俄罗斯等都在该方面投入了大量的科研力量，并取得了显著的成果，比较典型的有:Qu 提出的基于Prolog 逻辑的模型构造算法——MulVAL［6］系统，Steven Noel 等开发的基于EDG 模 型 的TVA 系 统［7－8］，Lippmann 等 开 发 的NetSPA 系统［9－10］，等等。

目前已涌现出了多种攻击图构建方法，通过对现有方法进行总结分析发现，利用现有方法构建攻击图存在以下两方面的不足:第一，在现实的应用中，网络安全管理人员不仅需要知道攻击者可能从哪些路径入侵目标主机，还应该了解攻击者能够入侵网络内的哪些主机，但是现有的攻击图构建方法大部分只能用于分析单一攻击目标的安全性。第二，攻击图构建过程存在复杂度高、扩展性能低、状态爆炸等问题，导致攻击图生成时的系统资源消耗较大，从而难以适用于大规模复杂网络系统。

为了解决上述问题，本文提出了一种基于分布并行处理的攻击图构建方法，并采用限制攻击步骤数和分布并行处理技术的优化策略，力图有效降低攻击图的规模，减少生成攻击图所需的系统资源。

1 攻击图建模方法

1．1 相关定义

定义1:脆弱性。由多种硬件、软件、协议、接口等组件构成的计算机网络系统由于技术与设计上的不完善性，往往存在大量的漏洞和缺陷，这些漏洞或缺陷构成了网络系统的脆弱性［11］。

本文脆弱性定义为三元组＜host，cveid，service＞。其中，host 表示主机的IP 地址，cveid 表示该脆弱性在CVE(Common Vulnerabilities Exposures)中对应的编号［12］，service 表示与该脆弱性相关的服务。

定义2:攻击者初始能力。定义为二元组＜host，privilege ＞，即攻击者在主机host 上，拥有privilege 的权限。本文将权限分为root、user 和none 三类。root 为用户的管理员权限，比如Windows 系统中的管理员权限，Linux 或Unix 中的Root 权限;user为普通用户权限，比如Windows 系统中的受限用户的权限，Linux 或Unix 中的User 权限;none 表示基本的访问权限。

定义3:攻击场景。是对目标网络模型参数的描述，包括攻击者初始能力、主机配置、网络配置、防御配置等。通过总结分析相关参考文献，针对大规模复杂目标网络，为了实现大规模目标网络建模的自动化，本文从网络服务、主机和安全防护系统三个层面对目标网络进行建模。

定义4:网络服务建模。网络服务定义为四元组＜host，service，protocol，port ＞，其中host 表示主机的IP 地址，service 表示主机提供的服务，protocol和port 为服务service 所用的协议和端口。

定义5:主机建模。主要描述主机上运行的服务及相关的脆弱性信息，定义为三元组＜host，servicename，cveid ＞，其中host 表示主机的IP 地址，servicename 表示主机提供的服务名称，cveid 表示主机上存在的脆弱性编号。

定义6:安全防护系统建模。定义为四元组＜host1，host2，protocol，port ＞，即防火墙允许主机host1 到主机host2 的协议为protocol，端口为port 的报文。

定义7:攻击模式。通过研究分析大量的脆弱性，借鉴CAPEC 攻击模式的脆弱性分类方法，本文将攻击模板知识库进行了改进，抽取出攻击模板的共同点，形成攻击模式。其定义为四元组＜name，precondition，postcondition，cveset ＞，其中name 为攻击模式的名称，precondition 和postcondition 分别对应攻击模式的前提条件和后果，cveset 为包含属于该攻击模式的所有CVE 编号。在实际的应用中，只有当攻击模式的所有前提条件precondition 满足时，此攻击才能被攻击者实施，从而产生后果属性postcondition。

定义8:子攻击图SAG(Sub－attack graph).SAG定义为三元组＜Attribute，Exploit，Edge ＞，其中Attribute 表示属性节点，包括原子攻击的前提属性集合和攻击被实施后所获得的新的后果属性集合。其初始值即初始属性节点集合，描述了目标网络在遭受攻击前主机上所运行的服务、开放的端口、存在的脆弱点以及预处理中提取出的防火墙accept 安全策略等相关属性。Exploit 表示原子攻击节点，攻击者在对目标网络进行攻击时，通过有序的实施原子攻击不断改变目标网络的属性，从而一步一步地达到攻击者的目的。Edge 是有向边集合，包括原子攻击的前提边集合和原子攻击的后果边集合。SAG 满足下列约束:

1)对∀e∈Exploit，令Pre(e)为e 的父节点集合，Post(e)为e 的子节点集合，则(∧Pre(e))→(∧Post(e))，表示只有当原子攻击的所有前提属性全部满足后，攻击者才能实施该原子攻击，且当原子攻击被成功利用后，其后果属性也全部满足。即该约束表示原子攻击的所有前提属性节点之间存在“与”关系。

2)对∀a∈Attribute，令Pre(a)为a 的父节点集合，则(∨Pre(a))→a，表示只要父节点集合中的任意一个原子攻击被成功实施后，属性a 就能被满足。即该约束表示属性节点的父节点集合中的原子攻击之间存在“或”关系。

定义9:父攻击图TAG(Total Attack Graph).TAG 定义为三元组＜SAG，Policy，Edge ＞，其中SAG为采用正向、广度优先搜索的策略构建的子攻击图集合。Policy 为预处理中提取出的防火墙accept 安全策略。Edge 是有向边集合，依据防火墙的accept安全策略，将不同的子攻击图连接起来。

1.2 基于分布并行处理的攻击图构建方法

假设1:单调性。攻击者作为智能主体，对于已经获得的网络属性不会再次作为攻击目标进行攻击。

针对大规模复杂网络系统，为了减小攻击图生成算法的复杂度，首先按照参考文献［13］中Ammann 提出的单调性假设，对攻击者的攻击行为做出假设。其次从分布并行处理的角度将不同区域的目标网络进行脆弱性分析任务划分，提出基于分布并行处理的攻击图构建方法，该方法分为三部分:任务划分、子攻击图生成和父攻击图生成。

1.2.1 任务划分

任务划分的思想及实现方法:首先根据子网内主机的可达性，将大规模复杂网络系统分为多个子网并进行任务编号(以下称为子任务)，即子任务是子网内主机的可达性集合;然后将子任务提交给服务器，服务器会根据子任务个数和处理器的个数，将子任务分配到不同的处理器上，从而实现子任务的并行处理;最后对防火墙安全策略进行预处理，提取出accept 规则，并按子任务进行分类。

1.2.2 子攻击图生成算法及其实现

SAG 生成算法的思想:在多个处理器上分布并行地处理子任务，构建不同子网内的攻击图，即生成子攻击图SAG.为了解决攻击图生成过程中存在的状态爆炸问题，同时还采用了限制攻击步骤数的优化策略。

在具体的实现过程中，首先根据Attribute 的初始属性值和攻击者的初始能力，采用正向、广度优先搜索策略，由攻击者所在的起始位置出发，依次分析其可达主机的可攻击性，并将可攻击的主机及其端口记录在队列BFSqueue－attackhost 和BFSqueue－attack 中。即根据子网的初始属性和攻击者的初始能力判断哪些攻击模式可以被攻击者利用，查询攻击模式和子网中的脆弱性信息，把攻击模式实例化;然后根据队列BFSqueue－attackhost 和BFSqueue－attack中的信息，生成攻击路径。算法流程图如图1～图3所示，其中，图1为SAG 生成算法流程图，图2为正向搜索子程序流程图，图3为攻击路径生成子程序流程图。对于攻击者所在的子网，在执行SAG 生成算法时，该子网的初始属性和攻击者的初始能力由用户输入或者工具扫描获得。对于其余的子网，在执行SAG 生成算法时，该子网中攻击者的初始能力从防火墙安全策略的accept 规则获得，即假设accept 规则中的源主机已经被攻击者攻下，是攻击者的起始位置。

图1 SAG 生成算法流程图Fig.1 Flowchart of generating SAG

SAG 生成算法流程图的详细描述:队列BFSqueue－start 存放攻击者的初始能力。第一步，判断BFSqueue－start 是否为空，如果为空，说明没有攻击者，则程序结束，否则提取BFSqueue－start 的第一个元素进行分析，同时删除该元素，依次调用正向搜索子程序(图2所示)和攻击路径生成子程序(图3所示);第二步，循环执行第一步，直至BFSqueuestart 为空，即分析了所有的攻击者。

图2 正向搜索子程序实现流程图Fig.2 Flowchart of forward search algorithm

正向搜索子程序流程图详细描述:在正向搜索算法具体的实现过程中，本文定义了3 个队列:BFSqueue－attackhost、BFSqueue－attack 和BFSqueue.其中BFSqueue－attackhost 以［攻击点主机:目标攻击点］的格式存放攻击成功的主机对集合，该队列反映从起始攻击点到目标攻击点的搜索路径，由于主机可以开放多个端口，可以同时存在多个攻击，因此队列中有重复的元素;BFSqueue－attack 以［攻击点主机:攻击目标主机:目标主机端口］的格式存放攻击成功的主机对集合，由于该队列反映攻击点主机通过哪些端口可以攻下攻击目标主机，因此该队列中没有重复的元素;BFSqueue 是一个动态队列，存放起始攻击点的所有可达主机。

本算法通过两种方式终止正向搜索:1)通过模拟大规模复杂网络系统，利用攻击图生成方法构建的攻击图中存在长度超过10 的攻击路径，但是经过分析真实的攻击事件发现:攻击者不会采用很复杂的攻击手段，不会以太多的主机为跳板进行攻击，即其攻击路径长度一般在5 以内，而且没有发现长度超过10 的。因此在正向搜索算法的实现过程中，采用限制攻击步骤的优化策略。若攻击步骤数超出最大值，则程序终止。2)攻击点主机对应的可达性集合中，没有未被攻击或未被分析的主机，因为根据单调性假设，在可达性集合中，若某台主机在前面的搜索中已经分析过或已经被攻击成功，则该主机为可达性集合中的无效元素，不需要对其再进行分析。

攻击路径生成子程序实现流程图详细描述:本文定义了间隔元素和终端元素:所谓间隔元素，是指由于BFSqueue－attackhost 中有重复的元素，即不同的搜索深度有可能具有相同的攻击路径，因此不同搜索深度的元素之间需用(IP:IP)隔开，(IP:IP)则称为间隔元素;终端元素，是指假设IP1 和IP2 之间存在攻击路径，即(IP1:IP2)满足，IP2 为最终攻击目标，则称该元素为终端元素。本算法结合间隔元素和终端元素，先不考虑端口情况，从BFSqueue－attackhost 的队列尾开始，分析BFSqueue－attackhost 中主机的攻击路径，然后结合BFSqueue－attack 中主机的端口信息，逐一写出攻击路径。

图4所示为核心算法。

1.2.3 父攻击图生成算法及其实现

构造父攻击图的基本思路是:1)将防火墙安全策略的accept 规则进行分类。如果策略中未出现对称的规则，则不需分类，如果出现对称的规则，则将此策略分为A、B 两类，即对称的规则不能同时出现。比如策略中的accept 规则为子网1→子网2，子网1→子网3，子网2→子网1，因为子网1→子网2与子网2→子网1 对称，所以该策略应被分为两类，A 类为子网1→子网2，子网1→子网3，B 类为子网2→子网1.2)依次判断accept 规则中的源主机是否被攻击者攻下，如果被攻下，该SAG不需改变，如果没被攻下，则应去掉SAG 中与之有关的攻击路径。3)依据防火墙安全策略的accept 规则，将所有的SAG 连接起来。

图3 攻击路径生成子程序实现流程图Fig.3 Flowchart of generating attack path

图4 核心算法Fig.4 Core algorithm

父攻击图生成算法程序流程图如图5所示，在算法实现过程中，定义了2 个队列:1)ACCqueue，以Type－规则存放分类好的规则集;2)SAG－queue，存放根据规则集修正后的各类子攻击图集合。算法主要由3 个子程序构成:规则集分类子程序完成对accept 规则进行分类，如图6所示;SAG 生成子程序完成对每一类进行子攻击图生成;TAG 生成子程序完成将每个SAG 经修正后生成TAG，如图7所示。

图5 父攻击图生成算法程序流程图Fig.5 Flowchart of generating TAG

图6 规则集分类子程序流程图Fig.6 Flowchart of classifying rule set

图7 TAG 生成子程序流程图Fig.7 Subroutine flowchart of generating TAG

2 实验结果及分析

图8所示是实验的模拟网络拓扑图。该网络内子网的数目、每个子网内主机的数目及每台主机上存在的脆弱点个数的最大值都由用户输入，且主机上存在的脆弱点是随机分配的。因此，对于该模拟网络，可以通过增大网络内的主机数来改变目标网络的规模，从而实现对大规模复杂网络的模拟。

图8 模拟网络的拓扑图Fig.8 Topology of simulation network

在Linux 下用C 语言实现了本文所提的分布并行攻击图构建方法。为了测试该方法的有效性，从两个不同角度分别进行了实验，并对实验结果进行分析。实验环境如下:服务器Power Edge R710，操作系统RetHat v5.4，内存32 G，CPU 2.26 GHz.

2.1 CPU 耗时实验

目前，涌现出了多种攻击图构建方法，其中做了实验分析的主要有Sheyner［13］和Ou［14］.

本实验模拟了简单的目标网络，该网络内只有一个子网，网络中没有防火墙设备，所有主机可以互相通信;每台主机上最多有5 个脆弱点。针对不同的网络规模，分别采用Sheyner、Xinming Ou 和本文提出的攻击图构建算法生成攻击图，图9展示了3种方法构建攻击图所花费的CPU 时间。从该图中可以看出，Sheyner 方法具有较差的时间复杂度，CPU 耗时随着网络规模成指数增长，而本文所提的方法和Ou 方法的CPU 耗时关于网络规模呈多项式增长，具有良好的时间复杂度。同时，本文所提方法的性能优于Ou，主要原因是在具体的实现过程中，该方法采用限制攻击步骤数的优化策略，从而有效抑制了生成时间的增长速度。

图9 CPU 性能结果比较Fig.9 Compared on CPU performance

2.2 可扩展性实验

本实验模拟了具有复杂拓扑结构的目标网络，该网络由10 个子网构成，每个子网都有防火墙对其进行安全防护;每个子网内没有防火墙，子网内的主机之间可以互相通信;每台主机上最多有5 个脆弱点。图10 展示了本文所提的方法在不同的网络规模下，构建攻击图所花费的CPU 时间。从该图中可以看出，随着网络规模的扩大，CPU 消耗时间也不断增大，但增加的幅度在可以接受的范围内，当主机数目达到1 000 台时，网络构建攻击图的时间也不过11 min，其中，攻击图生成时间只有23 s，其余时间为攻击图可视化(演示用)的时间。

图10 网络规模与CPU 消耗时间关系曲线Fig.10 Curve between network size and CPU time consumption

由实验结果可以看出本文所提方法具有很好的扩展性，可以适应对国家级公共基础网络或者运营商网络等大规模复杂网络脆弱性综合分析的需要。主要原因是在具体实现的过程中，其首先进行子任务划分;然后将子任务分配到服务器的处理器上，实现多线程并行处理，分布并行地构建不同子网内的攻击图;最后将子攻击图进行融合，生成总的攻击图。

3 结论

本文在前人工作的基础上提出了一种基于分布并行处理的攻击图构建方法。与已有的攻击图生成方法不同，本文提出的方法旨在对网络的整体安全性做出评价，能够表达出所有可达的网络状态及其相应的攻击路径。本文的主要贡献在于，站在防御者的角度，通过采用限制攻击步骤数的优化策略和分布并行处理的技术构建攻击图，提高了攻击图的生成效率，并且降低了攻击图生成时的系统资源消耗，能够用于评估大规模复杂网络系统的整体安全性。由于属性攻击图隐式地展示了攻击路径，不便于直观理解，在后续的研究工作中，将对属性攻击图的化简和可视化管理进行深入研究。

References)

［1］ Ortalo R，Dewarte Y，Kaaniche M.Experimenting with quantitative evaluation tools for monitoring operation security［J］.IEEE Transactions on Software Engineering，1999，25(9－10):633－650.

［2］ 陆余良，夏阳.主机安全量化融合模型研究［J］.计算机学报，2005，5(28):914－920.LU Yu－liang，XIA Yang.Research on target－computer secure quantitative fusion model［J］.Chinese Journal of Computers，2005，5(28):914－920.(in Chinese)

［3］ 冯萍慧，连一峰，戴英侠，等.面向网络系统的脆弱性利用成本估算模型［J］.计算机学报，2006，8(29):1375－382.FENG Ping－hui，LIAN Yi－feng，DAI Ying－jie，et al.An evaluation model of vulnerability exploitation cost for network system［J］.Chinese Journal of Computers，2006，8(29):1375－382.(in Chinese)

［4］ Cuppens F.Alert correlation in a cooperative intrusion detection framework［C］∥Proceedings of the 2002 IEEE Symposium on Security and Privacy，Washington，DC:IEEE Computer Society，2002.

［5］ Ning P，Xu D.Learning attack strategies from intrusion alerts［C］∥Proceedings of the 10‴ACM Conference on Computer and Communications Security.New York:ACM Press，2003:200－209.

［6］ Swiler L P，Phillips C，Ellis D，et al.Computer－attack graph generation tool［C］∥Proceedings DARPA Information Survivability Conference and Exposition (DISCEX II’01)，Vol 2.Anaheim:IEEE Computer Society，2001:1307－ 1321.

［7］ Swiler L P，Phillips C，Gaylor T.A graph－based network－vulnerability analysis system，SAND97－3010/1［R］.Sandia National Laboratories，Albuquerque，New Mexico and Livermore:1998.

［8］ Ritchey R，Ammann P.Using model checking analyze network vulnerability［C］∥Proceedings of IEEE Symposium on Security and Privacy.2001:156－165.

［9］ Sheyner O，Haines Jha S.Automated generation and analysis of attack graph［C］∥Proceedings of IEEE Symposium on Security and Privacy.2002:273－284.

［10］ 王永杰，鲜明，刘进，等.基于攻击图模型的网络安全评估研究［J］.通信学报，2007，28(3):29－34.WANG Yong－jie，XIAN Ming，LIU Jin，et al.Study of network security evaluation based on attack graph model［J］.Journal of Communications，2007，28(3):29－34.(in Chinese)

［11］ Michener J.System insecurity in the internet age［J］.IEEE Software，1999，16(4):62－69.

［12］ CAPEC.Common attack pattern enumeration and classification［EB/OL］.(2009－04－15)［2010－09－26］.http:∥www.capec.mitre.org.