基于SQAG模型的攻击熵优化算法

张 俊,张安康,王 辉

(河南理工大学 计算机科学与技术学院,河南 焦作 454000)

0 概述

互联网的快速发展能够满足社会各方面的现实需求,但也引发了越来越多的安全问题。根据国家互联网应急中心发布的《2018年中国互联网网络安全报告》[1],截至2018年底,国家互联网应急中心CNCERT/CC共接收到境内外报告的网络安全事件106 700起。网络安全事件的频发给人们的正常工作与生活带来很大的影响[2]。

为降低网络空间面临的安全风险,研究人员对网络攻击进行了建模。文献[3]将贝叶斯网与攻击图相结合,利用近似贝叶斯推理预测大规模网络路径。文献[4]利用贝叶斯推理对网络进行动态风险评估。文献[5]在利用贝叶斯预测攻击路径时引入时间增益补偿率。文献[6]通过贝叶斯推理直接求出所有节点的置信度。文献[7]在假定目标节点被占据的条件下求出了其余节点的置信度。文献[8]通过攻击图的置信度对网络安全进行了合理度量。文献[9]通过加固置信度较高的节点,降低了网络系统被攻击的风险,使其更加可靠。

本文通过SQAG模型对网络攻击进行建模,利用攻击熵算法消除冗余路径,运用联结树算法进行精确推理,从而获得理想情况下节点置信度的预测值及消除冗余路径后节点置信度的合理值。

1 相关研究

近年来,研究人员在网络攻击图的基础上利用贝叶斯推理对攻击路径进行预测。文献[10]指出攻击图的路径生成和路径分析是攻击图的研究重点之一,明确了在当前的网络攻击图研究中,当节点数增加时路径数目的增加方式是一个NP难问题,但没有给出减少冗余路径的具体方法。

文献[11]提出一个面向内部攻击意图推断的概率攻击图模型,在模型中引入条件概率表来描述单步攻击检测结果的不确定,并在模型基础上给出计算攻击意图的算法以及利用累积概率来预测最有可能发生的攻击路径的方法。该文中给出的起始节点概率是静态的,如果对该模型引入时间维度,那么当防火墙收缩访问尺度时,起始节点概率值将随时间变化,模型可实现对整个攻击过程中攻击意图的预测。

文献[12]提出一种成本收益分析方法,其中风险系数随时间呈指数级降低。将这种风险系数应用在一个包含多次试探攻击的场景中时,攻击时间会变长,但在没有新的节点被占据的情况下,攻击者对网络结构的了解程度不会加深,攻击经验也不会增加,因此风险成本并不会随时间以指数级的速度降低。

文献[13]提出在满足证据变量时间偏序关系的情况下,利用贝叶斯推理计算攻击路径节点置信度的方法。该方法采用似然加权法来近似计算节点置信度,但是在把一个攻击过程分解为多个时间片段后,当每一个时间片段中的网络攻击图对节点置信度的精度要求都比较高时,似然加权法将需要较大的样本量,极大地增加了计算量。

为优化攻击路径,本文提出SQAG模型和攻击熵优化算法,在现有资源状态攻击图的基础上引入时间和当前时刻已经占据的节点,转换成时序贝叶斯网络攻击图模型,根据联结树算法计算出某时刻各个节点的置信度。通过计算某一时刻的攻击熵,进而计算出该时刻的攻击风险成本,对基于深度优先搜索算法得出的攻击路径进行筛选,以实现对现有的攻击路径进行优化的目的。

2 时序网络攻击图

在一个攻击者为获取目标节点而反复进行试探性攻击操作的背景下,本文构造的时序网络攻击图模型主要有3个目标:1)利用该模型对攻击过程进行建模,预测任意时刻的攻击路径;2)根据当前时刻的时序网络攻击图,对子攻击路径进行成本收益分析;3)使模型能够体现出攻击者在该时刻之前已经获取的网络结构、攻击经验等信息,并利用攻击熵对其进行度量。为实现这些目标,在已有模型的基础上进行扩展,添加时间和每一时刻已经占据的资源节点。本文构造的时序网络攻击图模型及其参数定义如下:

定义1(时序网络攻击图模型) SQAG=(T,R,A,E,W,P,Π)是与发生时刻对应的一组有向无环图集。其中:

E=E1∪E2为关联攻击节点与资源节点的有向边集合,E1⊆R×A表示只有当攻击者成功占据资源节点之后攻击行为才能发生,E2⊆R×A表示只有当攻击行为发生之后才可以占据资源节点。

P=P1∪P2∪P3,其中,P1为初始节点发生的概率,P2=P(ai=true|Pre(ai)=true),Pre(ai)表示攻击事件之前的资源节点取值,P3=P(Con(aj)=true|aj=true),Con(aj)表示攻击事件之后的资源节点取值。

Π表示某一时刻攻击图中某一节点的置信度,Π(ri,ti)表示攻击者在ti时刻成功占据节点ri的概率,Π(aj,ti)表示攻击行为aj在ti时刻发生的概率。

根据以上定义,可以得出SQAG模型。用有向边连接资源节点与攻击行为节点,用深色标注攻击者在该时刻曾经占据的资源节点,并综合考虑and节点和or节点的几种排列组合情况,生成时序网络攻击图的主干结构。根据经验定义起始节点的概率P1以及条件概率P2和P3,得到如图1所示的时序网络攻击图。

图1 时序网络攻击图Fig.1 Sequential network attack graph

如图1所示,在t时刻,攻击者已经成功占据的资源节点为Rc={r1,r2,r3,r4},新一轮的攻击者以概率Pt1(R0)分别占据起始资源节点r1、r2、r3,攻击行为a1、a2以条件概率P2发生,并以条件概率P3分别占据相对应的资源节点r4、r5、r6,最终向目标节点r7靠进。

3 基于SQAG模型的攻击路径

攻击者在占据系统内全部目标资源节点前,从起始节点开始持续进行攻击,若攻击被阻断,则回到起始节点开始新一轮的攻击。为了能够直观地描述攻击演进过程,在时序网络攻击图的基础上定义攻击路径。

定义2(攻击路径) 在t时刻,对于任意一个目标资源节点rn∈Rg,从起始节点R0开始,存在一组由资源节点和攻击节点交替排列的序列r0,a1,r1,a2,…,aj,ri,…,rn,使得节点序列中任意2个相邻节点间总有∈E1或∈E2(0

以图1为例,攻击者可以从起始节点r2和r3出发,经过a2、r6、a4最终到达目标节点r7,其中由r2∩r3、a2、r6、a4、r7按发生顺序组成的节点序列即为一条攻击路径(符号∩表示节点间的and关系)。为便于表示攻击路径所包含的元素及其之间的关系,用某时刻的线序关系集来表示攻击路径,即STEPt-x={,,…,,…,},其中任意一个线序关系表示一条子攻击路径。在图1中,t时刻通向节点Rg={r7}的3条攻击路径如下:

STEPt-1={,,

}

STEPt-2={,,

,}

STEPt-3={,,

r4>,,}

4 攻击熵优化算法

攻击者在时序网络攻击图中任意时刻有多种占据目标节点的路径方式。当某一时刻时序网络攻击图的节点增多时,通向目标节点的攻击路径数量会呈指数级增长。为有效预测实际情况下可能出现的攻击路径,本文定义了攻击熵,用以度量攻击者对网络结构的了解程度和所获取的攻击经验。利用攻击熵计算风险成本,进而将某一时刻下子攻击路径的成本值和收益值进行对比,达到优化攻击路径的目的。

4.1 攻击熵的定义

定义3(攻击熵) 攻击熵是用来描述攻击者对网络结构了解程度和攻击经验平均不确定性的变量,结合时序网络攻击图模型,推导其数学表达式如下:

设P(Attackt-r)是当前时刻未占据节点的联合概率分布,表示为:

其中,Attackt-r是取值于离散联合分布集R-Rc上的随机变量,r∈{1,2,…,nr},nr为该时刻未占据节点的数目。

在此基础上,定义攻击熵如下:

随着攻击的演进,攻击图中未被占领的资源节点数目减少,而攻击者对网络结构了解加深,获得的攻击经验增加,这使得信息的不确定性降低,表现为攻击熵的数值降低,计算得出的风险成本也降低。

4.2 子攻击路径的成本分析

子攻击路径的成本由风险成本和操作成本两部分构成。文献[14]通过对子攻击路径的发生原因进行分析,提出操作成本cost(e)由元操作成本cost(meta-operation)和操作序列成本cost(sequence)两部分组成,表示如下:

cost(e)=α×cost(meta-operation)+

β×cost(sequence)

(1)

其中,e表示子攻击路径。

除了攻击操作需要花费成本外,攻击者在实施网络攻击的过程中还要面临被安全管理人员发现的风险,即需要承担相应的风险成本。因此,在分析子攻击路径成本时,也要考虑风险因素对子攻击路径是否发生影响。

风险系数(用θ表示)是用来衡量某次攻击行为在占领资源节点时被发现的可能性大小的一种度量,它一方面取决于攻击目标对攻击行为的影响系数(用M表示),攻击目标越重要,管理者对其越重视,攻击行为就越容易被检测到;另一方面取决于攻击行为自身的影响系数(用Γ表示),攻击行为越复杂,被发现的可能性就越高;另外还取决于攻击熵,攻击熵越低,攻击者规避风险的能力越强。因此,可以把风险系数θ定义为:

(2)

被攻击目标ri越重要,攻击者的操作aj复杂度越高,攻击熵越大,从而暴露的风险也越大。根据以上分析,风险成本cost(r)可表示如下:

cost(r)=cost(e)×θ(e)

(3)

从式(3)可以看出,风险成本随着风险系数的增长而增长,这符合实际攻击中风险成本的增长趋势。进而子攻击路径的攻击成本可用下式计算:

cost(eji)=ε×cost(e)+μ×cost(r)

(4)

其中,ε和μ分别表示两种成本的权重。

在某一时刻,当子攻击路径上获得的收益大于成本时,认为该条子攻击路径是可行的,否则是不可行的。

4.3 攻击熵优化算法

为解决时序网络攻击图中攻击路径随资源节点个数增加呈指数级增长的问题,本文运用攻击熵优化算法对子路径进行成本收益分析,以减少冗余路径,缩小网络攻击图的规模,具体算法如下:

算法1攻击熵优化算法

输入TSAG

输出STEPt-x

1.n=nr+na

2.Init:matric:G.arc[n,n];G.rel[n,n];G.visited[n];

3.for each ri∈Rorai∈A

4.if ai,rj之间存在有向边e

5.G.arc[i,j]=1

6.if ri,rj之间或者ai,aj之间存在and关系

7.G.rel[i,j]=1

8.if ri,rj之间或者ai,aj之间存在or关系

9.G.rel[i,j]=2

10.end for

11.//用矩阵存储SQAG模型的攻击关系与参数

12.for each ri∈R0

13.DFS(G,i)

14.G.visited[i]=true;

15.输出G.visited[i];

16.for each j

17.if G.rel[i,j]=1

18.输出G.visited[j];

19.//输出当前访问节点

20.Run ACCA

21.c=cost(eji)

22.if(G.arc[i,j]==1 && !G.visited[j]&&(c

23.//进行成本收益分析

24.i=j goto 第11行

25.end for

26.end for

在消除冗余路径的过程中,为利用攻击熵合理计算出风险成本,本文提出一种攻击成本计算算法,具体步骤如下:

算法2攻击成本计算算法

输入SQAG

输出cost(eji)

1.Init a=0;b=0;

2.for each ri∈R

3.if ri∉Rc

4.a=a+1;

5.else b=b+1;

6.end for

7.//计算当前未占据节点和已占据节点

10.//计算当前时刻攻击熵和最大攻击熵

12.cos t(r)=cost(e)×θ(e)

13.cos t(eji)=ε×cost(e)+μ×cost(r)

算法1存储了当前时刻攻击图的信息之后,计算出未占据的节点数,通过调用算法2计算出攻击熵,对其进行归一化,将资源重要性程度影响系数、攻击行为自身影响系数、归一化后的攻击熵累乘计算出风险系数,进而计算出合理的风险成本,加上操作成本后得出攻击成本,进而在算法1中进行成本收益分析,消除冗余路径。攻击熵优化算法利用攻击熵这一参数将攻击者在攻击过程中已经获取的网络结构信息和攻击经验包含在内,使得风险成本的计算比较合理。

5 时序网络攻击图中节点置信度的计算

在时序网络攻击图模型的基础上,利用贝叶斯推理计算节点置信度。相关学者采用似然加权法抽样得出节点置信度的近似值[15-16],但是精度要求高时,似然加权法需要大量的抽样。为能够快速地得到每一时刻各个攻击图各条路径上的节点置信度,本文选择了精确推理中时间效率最高的算法,即联结树算法[17]。

定义4(团集) 团集(Clique,C)是由SQAG模型中某一时刻攻击图中3个节点组成集合的集合,其中3个节点组成的集合称为团。

定义5(联结树) 联结树(Joint Tree,JT)是由SQAG模型的团集C中的元素Ci和有向边集合S中的元素Sj连接成的树状结构。其中,团集和边集满足任何2个团Ci和Cj之间路径上的每个边包含于边集S中,相邻2个点之间的边Sij=Ci∩Cj。令团C1={a3,a4,r7},团C2={a3,a4,a5},则S12为边。

联结树算法步骤如下:

步骤1将时序网络攻击图转换为联结树

为将TSAG模型上的推理转换成JT中的推理,需要将对应的时序网络攻击图2(a)转变为联结树JT=(C,S),将转换过程分解为以下3步:

1)建立Moral图

(1)找出时序网络攻击图中每一个资源节点和攻击节点的父节点。

(2)用无向边将父节点两两相连。

(3)将有向边改为无向边。

如图2(a)所示的时序网络攻击图,其Moral图为图2(b)。

2)三角化Moral图

将Moral图中每一个大于或等于4的环的非相邻节点用无向边连接起来,实现Moral图的三角化。

如图2(b)所示的Moral图,其三角化后的Moral图为图2(c)。

3)建立联结树

(1)确定所有的团集,其中团集是三角化后的Moral图中最大全连通图组成的集合,团集中每对不同的团都由无向边连接。

(2)在团集中添加一些边和分割节点构造出一棵联结树T。

图2(c)为三角化后的Moral图,其联结树如图2(d)所示。

图2 时序网络攻击图转换成联接树的过程Fig.2 Process of converting sequential network attack graph into joint tree

步骤2初始化联结树

联结树的初始化是对所有节点给定发生与否的概率,进而得到每个团的分布函数。由时序网络攻击图构建的联结树中的团Ci由3个节点组成,其中每一个节点有2种状态,则共有8种状态组合。令Φi表示团Ci的分布函数,Φij代表团Ci第j个状态组合的分布函数,初始化如下:

for eachΦij=1

步骤3消息传递

消息传递通过更新任意2个团之间的联合概率分布,使得联结树达到全局一致状态。如图3所示是相邻团的节点间进行的一次消息传递[18]。

图3 一次消息传递过程
Fig.3 Process of a message delivery

从团Ci到团Cj进行一次消息传递包括以下3步:

1)产生消息:

(5)

2)吸收信息,更新团节点的分布函数ΦCj:

(6)

3)更新分隔节点的分布函数:

(7)

步骤4概率计算

步骤5条件概率计算

条件概率计算即是在SQAG模型中某些观测到的节点值为True的条件下,计算另外的某个节点发生的条件概率。通过对联结树进行消息传递得到全局一致的联结树[20]。当联结树加入条件e后达到全局一致时,对任意的团节点C有ΦC=P(C,e),e表示加入的条件。

(8)

将某时刻的时序网络攻击图转换为联结树后,对联结树进行赋值,得到一个带有状态组合分布函数的联结树。通过团节点之间的消息传递,联结树达到全局一致。在这种状态下,可得出任意节点的置信度。

6 算法仿真与验证

在一个攻击者为占据所有目标节点而不断反复从起始节点进行攻击的场景中,为证明该模型能够较好地模拟出网络攻击节点置信度随时间变化,本文设计如下实验:首先在matlab软件上实现联结树算法,建立防火墙随时间收紧情况下的模型,结合联结树算法得出各条路径上节点置信度随时间的变化;其次在假设子攻击路径参数(收益、操作成本系数、风险成本系数)为定值的情况下,计算出某时刻优化后的攻击路径及各节点置信度。

以图1的时序网络攻击图为例,利用联结树算法推理计算节点的置信度,其中,条件概率P2=0.7,P3=0.5。随着攻击的进行,防火墙会收缩访问尺度,故可根据经验设定起始节点概率:

P(vi∈R0)=1-0.1×ti,

i=1,2,3,ti=0,1,2,3,4,5,6

以STEPt-1和STEPt-2为例,画出在满足上述假设的情况下7个时刻各条攻击路径上节点发生的置信度,如图4所示,其中图4(a)和图4(b)攻击路径节点分别为r1、a1、r5、a4、r7和r2、r3、a2、r6、r7。

图4 节点置信度随时间的变化过程Fig.4 Change process of node confidence degree with time

在图4(a)和图4(b)中,随着防火墙收缩访问尺度,各条折线上从高到低的圆点分别代表STEPt-1和STEPt-2上7个时刻各节点置信度随时间均呈下降趋势。可以看出,随着攻击的演进,防火墙收缩访问尺度,起始节点发生概率降低,导致该时刻此条路径上的所有节点置信度都相应地降低。以上分析没有考虑随着攻击熵的增加,某些子攻击路径的风险成本增加,导致攻击路径变化。

计算各个攻击阶段下对应Attackt-r的攻击熵,如图5所示。

图5 攻击熵与未占据节点个数的关系Fig.5 Relationship of attack entropy and number unoccupied nodes

经过长时间的攻击之后,攻击者未占据的节点随时间逐渐减少,攻击者对网络系统不确定性的了解程度降低,攻击经验增加,攻击熵也随之降低。

根据经验,设定图1中的网络系统某时刻攻击权对应的子攻击路径上的攻击参数如表1所示。运行算法1和算法2的代码可得,攻击权w1对应的子攻击路径上的成本小于收益,而攻击权w2、w3、w4、w5对应的子攻击路径上的成本大于收益,从而可知利用算法1和算法2可合理删除攻击者认为不可能发生的子攻击路径,证明了该算法可以实现路径优化。

表1 ti=6时子攻击路径上的攻击参数Table 1 Attack parameters on sub-attack path at ti=6

为进一步描述优化后的攻击路径,利用联结树算法进行推理,计算STEP6-1和STEP6-2上各节点置信度如图6所示,其中图6(a)和图6(b)攻击路径节点分别为r1、a1、r5、a4、r7和r2、r3、a2、r6、r7。由图6可以看出,STEP6-1可行的攻击路径有{},STEP6-2可行的攻击路径有{},与图4推演出的攻击路径对比可知,利用攻击熵优化算法消除了冗余子攻击路径,进而利用联结树算法推理优化后的节点置信度更加接近实际情况。

图6 STEP6-1和STEP6-2上的节点置信度Fig.6 Node confidence degree on STEP6-1 and STEP6-2

对于未使用攻击熵优化算法的情况,即此时风险系数的计算方式为θ(e)=Γ(aj)×M(ri),进行优化后的攻击路径及其节点置信度如图7所示 ,其中图7(a)和图7(b)攻击路径节点分别为r1、a1、r5、a4、r7和r2、r3、a2、r6、r7。

图7 未运用攻击熵时STEP6-1和STEP6-2上的节点置信度Fig.7 Node confidence degree on STEP6-1 and STEP6-2 without attack entropy

对比图6和图7可知,图6中STEP6-1上a1和STEP6-2上a2置信度都不为0,而在图7中它们的置信度为0。这是由于攻击熵的引入使得在计算风险成本时,将攻击者在多次试探性攻击的过程中所获取的攻击经验和对网络结构的了解程度包含在内,导致攻击者的风险成本变低,故可能发生的子攻击路径变多。由图6和图7对比可以看出,引入攻击熵算法可合理消除冗余路径。

7 结束语

对网络攻击进行合理建模并实时高效地预测攻击路径是网络安全领域研究的热点。本文在已有研究基础上,提出时序攻击图模型和攻击熵优化算法,通过定义在时序网络攻击图中的攻击熵概念,描述攻击者对网络结构了解程度的加深与攻击经验的增加对风险成本的影响,利用攻击熵计算风险成本,合理地消除时序网络攻击图中的冗余路径。在使用攻击熵优化算法合理减少冗余路径后,应用精确推理中的联结树算法得到节点置信度的精确值,进而对攻击路径进行实时预测。本文所提算法没有考虑防御者对攻击方式的了解程序,因此在进行成本收益分析时,不能充分体现双方的博弈过程,下一步将对此进行改进。