基于状态约减的信息攻防图生成算法*

张恒巍，余定坤，寇　广，韩继红

（解放军信息工程大学，郑州　450001）

基于状态约减的信息攻防图生成算法*

张恒巍，余定坤，寇广，韩继红

（解放军信息工程大学，郑州450001）

针对攻防图构建中存在的状态爆炸问题，提出一种基于状态约减的攻防图生成算法。该算法在分析攻击者和目标网络特点的基础上，对独立状态节点的权限进行对比；其在保留最高权限节点的前提下，实现对低权限节点的约减，并去除冗余攻击路径。仿真实验表明算法具有计算复杂度低、能有效降低状态爆炸以及控制攻防图规模等优点。

攻防图，状态爆炸，节点权限，状态约减

0　引言

攻击图是一种攻击行为建模方法，其从攻击者的角度出发，在分析网络结构和系统漏洞的基础上，生成攻击路径，展现针对特定系统的攻击预案集合，能够帮助安全管理人员开展安全风险评估和防御策略选择［1-3］。但是，攻击图所关注的仅是攻击者的行为，并没有考虑防御者可能采取的手段，而信息攻防是攻击者和防御者互相对抗博弈的过程，安全状态及下一步的变化情况是由攻击与防御行为共同决定的，信息安全受双方的对抗行为以及行为所造成结果的影响［4-5］。因此，不能仅从攻击者角度出发，而应将防御行为也考虑进来，从攻防双方的角度出发，建立攻防行为模型，更加全面、准确地反映信息系统安全的实际情况。

有学者在攻击图的基础上进一步提出了攻防图模型。文献［5］提出了用于网络安全测评的防御图模型的概念和定义，但未进一步给出防御图建模、生成方法。文献［6］提出了一种攻防图模型及其生成算法，但其中攻击路径生成方式简单，且未考虑状态空间爆炸的问题。文献［7］提出一种攻防图的生成算法，并用于系统安全态势分析，但对安全状态及其转化分析不足，存在较为严重的状态空间爆炸问题。

本文针对传统攻防图构建方法存在状态爆炸的问题，对攻防图建模过程进行深入研究，提出一种基于状态约减的信息攻防图生成算法。在产生攻击路径时，对各主机的独立状态节点的权限进行对比，仅保留最高权限的节点，约减其余权限较低的节点，并减少重复节点，去除冗余攻击路径，该方法不但能够控制状态空间组合爆炸，而且可以实现对目标网络中主机的覆盖。在此基础上，提出一种较低复杂度的攻防图生成算法，仿真实验和结果分析验证了算法的有效性。

1　基于状态约减的攻防行为建模

1.1基本假设

在借鉴文献［7-8］的基础上，提出如下假设作为研究的基础。

假设1攻击者是智能且贪婪的，在了解网络中的漏洞信息后，知道如何利用漏洞进行攻击，且不会进行无效攻击。

假设2攻击者在一个节点获得权限提升后，可利用此节点发动针对不同节点的攻击。

假设3（单调性假设［7］）攻击者不会为了获取已有的权限而发动攻击，且攻击方向只会向着提升操作权限的方向发展。

1.2攻防图模型

攻防图主要描述了攻击者利用网络漏洞进行多步攻击，以及防御者采取防御策略进行对抗的过程［9-10］。下面给出攻防图的形式化描述。

定义1攻防图ADG（Attack-Defense Graph，简称ADG）。定义五元组ADG=（P，B，P0，PG，Sd）为信息攻防图，简称攻防图。其中，P为攻防图中表示网络安全状态的各个网络节点的集合；B为攻防图的各条边的集合，攻击者通过边（即攻击行为，或称攻击策略）来实现网络安全状态的变迁；P0则表示整个网络信息系统的一个初始状态；PG则表示攻击者在攻击前所确定的目标状态集合；Sd是防御者为抵抗攻击而采取的防御策略的集合。

与攻击图类似的是，攻防图中的节点代表安全状态，表示其自身所拥有的权限及对其他节点的访问能力；边代表攻击者的攻击行为，通过该行为攻击者实现安全状态的迁移，从而获得对不同主机的权限，最终达到目标状态。与攻击图不同的是，攻防图为了全面地反映信息攻防的整体情况，不仅需要对攻击者的行为有所把握，还要对防御者的行为进行考虑和分析。防御者可以针对攻击行为采取相应的防御行为（或称防御策略），防御策略组成集合Sd。

1.3攻防行为建模

攻防行为建模应避免出现状态爆炸，无法适应大规模网络的情况，能够高效、灵活、全面地对攻防状态进行分析和研究。本文从对安全状态约简的角度出发，提出一种建模方法。

为描述目标网络，定义Host元组和Connection元组，分别代表网络中的主机以及网络连接关系。

定义2Host（ID，Serf，Vulf）。Host表示网络中的一台主机，为了对网络中运行的一台主机进行描述，使用3个元素，分别是主机ID，用于赋予主机网络中唯一的标识；主机的运行服务列表Serf，用于记录所运行的服务；脆弱性列表Vulf，用于记录主机存在的脆弱性；由此，可以将网络中的主机表达为Host（ID，Serf，Vulf）。

定义3Connection（SH，TH，CP）。Connection表示网络中的主机连接关系。主机之间相互连接，其中一方为发起者，一方为接受者。发起者为源主机，接受者为目的主机，它们之间通过端口互相通信。因此，网络中主机的连接关系可用3个元素进行描述，分别是源主机SH（Source Host）、目的主机TH（TargetHost）和连接端口CP（Connected Port）。由此，可以将主机连接关系表达为Connection（SH，TH，CP）。

传统攻防图生成过程中产生的状态数量巨大，呈指数增长，使得攻防图的产生花费时间多，效率低下。为了减少攻防图生成的复杂度，降低攻防图的规模，本文提出一种状态约简方法。由于网络中的攻防是攻击者借助脆弱性实施攻击，防御者选取防御策略进行抵抗的过程。因此，要对安全状态进行约简，需要对攻击行为及其造成的安全状态迁移进行描述。

安全状态是指攻击者通过获得主机的权限从而使主机达到的一种状态。攻击者进行攻击是否成功，主要体现在攻击者的权限变迁情况。因此，在攻防图中，安全状态可以通过攻击者在主机上所拥有的权限进行表述。本文定义主机权限为4种，即禁止访问、远程访问权限、普通用户权限、管理员权限，4种权限依次递增。

基于上述分析，针对攻击模板，本文从攻击者所在主机、攻击者在主机上拥有的权限、攻击者所在主机与其余主机的联系、攻击目标主机或目标网络、最大攻击步数等角度进行描述。对攻击所在主机采用该主机的ID进行标识；攻击者在主机上拥有的权限可使用权限列表HA-List（Host Authority List）表示；攻击者所在主机与网络中其余主机的联系通过Connection-List列表进行记录；攻击目标主机或目标网络是攻击者的最终目标，使用Target对最终目标主机进行标识；最大攻击步数采用MX （max-steps）来表示。由上，可得攻击模板的形式化表示为：Attack-Template=（ID，Authority-List，Connection-List，Target，MX）。参数具体定义见文献［11］。

由于攻击者可以利用同一主机的不同漏洞，借助网络连接关系，通过不同的攻击行为对另一主机进行渗透和攻击。此时，攻击者在另一主机上便可能获得多种安全状态，所获得的权限也可能有高有低。若这些漏洞并不存在依赖关系，则只需要保留攻击者在另一主机的较高权限的安全状态，这样可有效降低安全状态的总数量。以上过程，称之为安全状态约简（State Reduction）。状态约简原理如图1所示。

图1　状态约简原理

Pi-1和Pj-1是主机n的安全状态，Pi和Pj是主机m的安全状态，而ai和aj则是攻击者的不同攻击行为。若攻击行为ai所对应的漏洞与攻击行为aj不存在依赖关系，且Pi状态下攻击者的权限高于在状态Pj下攻击者的权限，则可以按照图中所示，将攻击行为aj和安全状态Pj删去，仅留下ai和Pi。而若攻击行为ai所对应的漏洞与攻击行为aj存在依赖关系，则攻击者必须先对主机m进行攻击行为aj来达到安全状态Pj，再采取攻击ai才能到达状态Pi，此时不能进行状态约简。

由于攻防图建模不仅要考虑攻击者的攻击行为，还需要对防御者的策略进行分析考虑。因此，引入攻防模板对攻击者、防御者的行为规则进行描述。一个攻防模板应由攻击者行为、攻击者在源主机和目标主机上的权限、攻击利用的漏洞、攻击后攻击者在目标主机上的权限、防御策略、攻防收益组成。攻防模板可形式化表示为一个元组：Attack-Defense Template=（AM，SHA，THA，Vul，THA’，AR，DS，DR），其中AM（Attack Movement）为攻击者的攻击行为，SHA（Source Host Authority）为攻击者在源主机上的权限，THA（TargetHostAuthority）为攻击者在目标主机上的权限，Vul为攻击者所利用的网络中的漏洞，THA’为攻击者攻击后在目标主机上具有的权限，AR（Attack Reward）表示攻击者通过攻击所获得的回报，DS（Defense Strategies）表示防御者为减少其损失所采取的防御策略，DR（Defense Reward）表示防御者通过采取防御策略所获得的回报。参数具体定义见文献［11-12］。

2　攻防图构建框架与生成算法

攻防图的建模和生成首先需要对目标网络中的漏洞信息、拓扑结构信息、配置文件信息等进行收集和掌握，并进行分析和研究，之后将攻防模板、攻击模板输入攻防图生成算法，通过网络安全状态约简，生成优化后的攻防图，如图2所示。

图2　攻防图构建框架

攻防图生成算法是构建攻防图的关键和核心，在基于状态约减的攻防行为建模研究的基础上，提出下面的攻防图生成算法。

首先从攻击者已获得最高权限的主机出发，对目标网络进行扫描，收集拓扑信息、漏洞信息等。然后，攻击者利用漏洞对网络中的主机进行攻击，以获得更高的权限。此后，攻击者又可基于已获得一定权限的主机对网络中与该主机相关联的、具有漏洞的其他主机进行攻击。攻击行为持续进行，直到达到攻击目标。另一方面，防御者选取可用的防御策略实施抵抗，最终形成攻防图。

依据以上思路，给出基于安全状态约简的攻防图生成算法的具体描述。

基于状态约简的攻防图生成算法

原始主机队列和主机权限队列

算法中攻击路径生成部分是算法的主体。其中，主机信息队列用Host_queue表示；攻击者在主机上具有的权限队列由HA_queue表示；随着攻防进程的推进，新产生的状态节点队列由P_queue表示；状态节点间的相互关系用Connection_queue表示；攻击过程由攻击模板attack_template_queue描述；Initialize函数用于队列生成和初始化，QueueEmpty函数用于判断队列是否为空，Dequeue函数用于从队列中取出元素，Attack函数用于判定攻击是否成功；State Reduction是状态约简函数，依据1.3节的方法实现对安全状态的约简，避免产生状态爆炸现象。

分析算法可知，本文提出的攻防图生成算法的空间复杂度为O（nml），时间复杂度为O（n2mt），其中n表示网络中的主机数，m表示主机的漏洞数，l表示主机所拥有的权限状态，t表示漏洞处理时间。算法的复杂度为多项式级别，时空开销较低，满足应用需求。

3　仿真实验与结果分析

为验证本文提出方法的有效性，采用如图3所示的网络环境进行仿真实验。其中，攻击者位于主机0处发动攻击，并具有该主机的最高权限。目标网络由防火墙、入侵检测系统、主机1和主机2组成。

图3　网络拓扑结构

主机1和主机2分别为Web服务器、数据库服务器，操作系统为Linux，具体参数如下页表1所示。

假设攻击者具有主机0的管理员权限，且具有主机1和主机2的远程访问权限。由于防火墙的隔离防护作用，外部主机仅能使用主机1的ftp、Http服务和主机2的ftp服务。

表1　主机提供的服务及其漏洞

依据上述假设构造攻防模板，假定攻击目标是获得主机2的管理员权限，由此控制数据库服务器。由于防火墙的存在，攻击者无法直接使用主机2的数据库服务，但是由于主机存在漏洞，且漏洞之间具有相互联系，攻击者可以利用漏洞及其关联性进行攻击，实现目标。假设攻击策略如表2所示，包括攻击行为的名称、类别、攻击致命度AL［12］。防御者可选的防御策略如表2所示。

表2　攻防策略描述

在对攻防行为建模后，利用文献［7］的方法，未进行状态约简直接生成攻防图，结果如图4所示，共有攻击路径13条，状态结节31个。

图4　未约简的攻防图

利用本文提出的基于安全状态约简的攻防图生成算法，得到结果如下页图5所示。可以看出，在引入单调性假设并对状态进行约简后，攻击路径为9条，状态节点为23个。由此可见，对安全状态进行约简可有效降低攻防图规模和状态爆炸程度，使攻防行为建模更加合理、高效、实用。

将本文方法和文献［5-7］进行对比，结果如表3所示。

表3　方法比较

图5　约简后的攻防图

由表3可以看出，相比其他文献，本文方法在攻防图生成方面，具有状态节点、攻击路径数量少，攻防图规模较小，算法复杂度较低等优点，在一定程度上减小了状态爆炸，取得了较好效果。

4　结论

本文面向攻防图自动生成的需求，针对传统攻防图构建方法存在状态爆炸的问题，通过分析攻击者和目标网络的特点以及传统算法的不足，在设计合理假设的前提下，提出了基于状态约减的攻防图生成算法。通过对该算法的复杂度分析和仿真实验验证，表明算法具有计算复杂度低，能有效降低状态爆炸，控制攻防图规模等优点。在下一步的工作中，将在大规模的真实网络中进一步验证算法的性能并进行改进。

［1］LIU X，REN TC，MA L，etal.Research on an improved information network security defence model and production method［C］//Proceedings of the 15th IEEE Conference on DecisionandControlCancun，Mexico：Springer，2013：829-834.

［2］吴金宇，金舒原，杨智.基于网络流的攻击图分析方法［J］.计算机研究与发展，2014，50（8）：497-1505.

［3］宋舜宏，陆余良，夏阳，等.基于贪心策略的网络攻击图生成方法［J］.计算机工程，2012，38（2）：126-13.

［4］王元卓，林闯，程学旗，等.基于随机博弈模型的网络攻防量化分析方法［J］.计算机学报，2010，33（9）：1748-1762.

［5］姜伟，方滨兴.基于攻防随机博弈模型的防御策略选取研究［J］.计算机研究与发展，2012，47（10）：1214-1223.

［6］刘刚，李千目，张宏.基于状态攻防图模型的网络安全防御策略生成方法［J］.计算机应用，2013，33（11）：121-125.

［7］SHAMIIOR O，HANBERGE J.Automated generation and analysisofattack-defensegraphs［C］//Proceedingsof the51th IEEE Symposium on Security and Privacy，Washington DC：IEEEComputer Society，2013：273-284.

［8］李玲娟，孙光辉.网络攻击图生成算法研究［J］.计算机研究与发展，2014，20（10）：171-175.

［9］张恒巍，张健，王晋东，等.基于连通度算子的系统漏洞风险评估研究［J］.计算机工程与设计，2015，36（1）：71-76.

［10］何江湖，潘晓忠.基于漏洞关联攻击代价的攻击图生成算法［J］.计算机应用研究，2012，29（5）：1908-1913.

［11］MAN D P，ZHANG B，YANGW，etal.Amethod for global attack graph generation［C］//Proceedings of the 9th IEEE ConferenceonNetworking，NewYork：Springer，2013：736-741.

［12］王晋东，余定坤.静态贝叶斯博弈主动防御策略选取方法［J］.西安电子科技大学学报（自然科学版），2015，20 （10）：102-107.

Attack-defense Graph Generation Algorithm Based on State Reduction

ZHANG Heng-wei，YU Ding-kun，KOU Guang，HAN Ji-hong
（PLA Information Engineering University，Zhengzhou 450001，China）

To solve the issue of state explosion in attack-defense graph generation，an algorithm of attack-defense graph generation based on state reduction is proposed.This algorithm compares the authority of nodes in independent state on the basis of analyzing the characteristics of attacker and the target network.It achieves reduction to low-privileged nodes and elimination of redundant attack path under the premise of reserving nodes of highest permission.Simulation results show that the algorithm has advantages of low computational complexity，effectively reducing state explosion and controlling the scale of attack-defense graph.

attack-defensegraph，stateexplosion，node permission，state reduction

TP393

A

1002-0640（2016）08-0064-06

2015-06-25

2015-07-17

国家自然科学基金（61303074；61309013）；河南省科技攻关计划基金资助项目（12210231003；13210231002）

张恒巍（1978-），男，河南洛阳人，博士研究生，讲师。研究方向：信息安全与网络对抗、安全风险评估。