基于改进蚁群算法的网络风险分析与防御加固技术

吴海宁,杜 端,可 红,张 超,郑 舒

(湖北华中电力科技开发有限责任公司,湖北 武汉 430000)

对于愈加复杂的大规模网络而言,随着可能攻击路径的指数级增长,状态攻击图需要大量的迭代与计算才能够描述出所有的安全风险,这也导致其性能大大降低,因此属性攻击图模型应运而生,其核心思想就是以最低成本进行网络安全的加固[1]。

Sheyner使用模型检测的方法来自动生成攻击图,虽然使用该方法可以生成所有的攻击路径,但存在状态空间爆炸的问题[2]。Shiaeles等使用自定义方式生成多目标完全攻击图,但它的时间复杂度较高[3]。目前对于大规模网络的属性攻击图大部分的研究基本集中在攻击图的构建和简化工作中,鲜有针对简化后攻击图的求解优化,因此文中基于一般蚁群算法的缺陷,提出了基于自适应要素更新和自适应遗传算法的局部搜索机制的改进思路,以期提高网络安全风险评估的最小关键集求解和搜索性能。

1 攻击图模型分析

1.1 属性攻击图

属性攻击模型中主要包含攻击和属性2类对象,其中攻击节点代表被原子攻击的节点,而属性节点则代表攻击的前后要素;同时在属性攻击图模型中还包括需求关系和实现关系的边,属性攻击模型的原理如图1所示[4-6]。

图1 属性攻击图示例

在图1中,“c*”文字代表属性,圆形代表攻击,如原子攻击源表示为m,那么对于e1而言,它的执行前提包括c1、c2,执行输出包括c5、c6。从属性攻击图原理可以看出,其问题构建表现出多项式级的复杂性,也就更适用于规模较大的网络安全环境评估。

1.2 关键攻击集分析

当然在一般的大规模网络安全风险评估工作中,往往会通过攻击图优化算法对其进行简化,一方面提高了攻击图的可理解性;另一方面也大大降低后续安全防御加固的成本[7]。

在这里设攻击图AG=(Ns,Nm,Ne,E),其中Ns为初始化的属性节点,在实际中则可以理解为攻击人员所拥有的所有资源;Nm为实际可达的攻击目标;Ne为所有的攻击执行;E为有向边集合。因此,定义一个具体的攻击目标d,PATHS表示d可达的所有路径;同时设C为d目标中的所有攻击节点集合;S为关键节点的集合,那么有∀S∈PATHSS∩C≠Ø。定义N为S的最小节点集合,那么S′⊂N∧S′∈S永不成立。

那么对于属性攻击图AG而言,设存在攻击路径Vi,将其进行序列状态变换成N1,N2,N3…Nn,Ni∈E。那么一次完全的攻击需要从状态一条完整的路径需要从N1持续到Ns,这样Vi则表示为所有攻击集的一个子集。

对于一个具体的s∈S,如果在攻击库中消除了C,那么在状态s下是无法达成攻击目的的;同理若C是s的关键攻击集合。

通过前序描述可以将其理解为数学表达,设在某一个具体网络中包含了原子攻击集A,|A|=m。路径集合C={A1,…,An},其中Ai⊆A∀i={1,…,n},那么有A的碰撞集H⊆A,H∩Ai≠Ø,∀i=1,…,n;设数学函数ω:ω(α)→Z+,那么有碰撞集最小目标函数ω(H)=∑α∈HΣα∈Hω(α)。

当ω(α)达到1时,上述数学问题则可以理解为无权重节点的最小碰撞集的计算,同时由于上述问题描述中集合中的所有元素都能够满足NP问题的前置要求,将攻击图转换为最小碰撞集的数学问题,则可以将关键攻击集分析定性为NP难问题。图2为攻击图实例。

图2 攻击图实例

在图2中可以看到能够到达攻击目标N11的路径共有5条:{N1,N3,N6,N7,N10,N11}、{N1,N4,N6,N7,N10,N11}、{N1,N3,N6,N7,N11}、{N1,N9,N11}、{N1,N4,N6,N7,N11},在通过最小碰撞集的计算后得到{N6,N9}、{N7,N9};这可以看出,如果这2个攻击机得到重点加固,则目标的可达路径则全部被封堵。

1.3 关键集蚁群算法求解

通过上述分析,采用蚁群算法来解决关键攻击集的求解需要进行以下数学定义[8-9]:

(1)

同时在第i个节点在t时刻拥有的所有信息要素的总和为:

(2)

那么在t+1时刻,其增量的信息要素为:

τi(t+1)=ρτi(t)+Δ(τi(t))

(3)

因此求解最优解的过程就是蚁群所拥有的最优路径,定义概率函数为:

(4)

式中:α为信息要素在整体网络中权重,而β则代表贪心权重。那么当α=0,β=1时,则代表了攻击目标可能存在路径的最高概率选择。这样可以看出基于蚁群算法的关键集求解时间复杂度为o(n3),它能够一定程度上解决大规模网络最小关键集的最优化计算问题,但由于蚁群算法的计算性能较低,计算时长较长,同时在不同的α、β参数条件下其计算结果差异较大,甚至会出现过快收敛从而只能达到结果局部最优的情况,因此其收敛与性能稳定性上并不能够完全满足要求[14-15]。

2 基于改进蚁群算法的关键节点描述

由于蚂蚁算法存在着较快的收敛和后期搜索速度过慢等问题,致使算法在局部最优解附近会产生停顿,无法计算全局最优解。同时因为一般蚁群算法自身的正向反馈机制,使得信息要素会产生路径拥塞,从而造成早熟停滞的情况。为了解决这一问题,在蚁群算法中引入了自适应的信息要素动态更新原理,并引入了自适应GA进行上述问题的改进[16-17]。

2.1 要素动态更新

对于蚁群算法的改进策略中,在路径遍历中下一路径节点的选择采用伪随机比例的机制,其推导函数表示为:

(5)

式中:q是概率随机数,其与下一节点的路径决策呈负相关。

那么式(5)可以转换为:

(6)

(7)

2.2 局部搜索机制

为了解决蚁群算法在搜索过程中存在的后续性能较低的缺陷,前人提出了3-opt、遗传算法等局部搜索机制来改进。文中提出了一种基于自适应的遗传算法来解决搜索性能的问题。具体做法是在每一次迭代后,都会对所获得的攻击集进行最优调整,把所获得的路径相互重新配对,并可行解的计算进行增速,从而使算法的效果更好。

但由于一般的遗传算法在适用大部分研究场景时都具有较大的鲁棒性,因此根据蚁群的种族信息变化动态地设定交叉率和变异率。

因此针对局部搜索机制优化可以表达为数学目标:

(8)

式中:X代表决策因子。那么整体改进思路为首先对蚁群的数量进行初始化,采用每一蚂蚁周期计算一次攻击集合的方式,并将各蚁群按其信息要素的动态更新机制选取的后续节点。并在每次迭代完毕时采用自适应GA计算其循环数量,直至达到预设的数量后退出周期,从而获得最小临界攻击集合。结果表明,该算法的迭代数量在时间复杂度上比传统蚁群算法少,空间复杂度也更低。

3 实验结果与分析

3.1 算法分析

为了验证2.2节中的局部搜索机制改进策略合理性,选取了遗传算法、自适应排序作为基线进行性能分析。其中设定种群的初始数量为60,迭代的上限为200次,一般遗传算法的交叉变异设置为0.79、0.005 8,Adapt排序中分别设定μ1=0.368,μ2=1.4,μ3=1.8,μ4=2.0,其余设定如表1所示;3种算法的适应性曲线如图3所示。

表1 实验设定Tab.1 Test set

图3 适应性变化曲线

由图3可见,在早中期,自适应遗传算法的搜索性能一直非常有优势,直到160次后才开始逐渐放缓。另2种算法从30次迭代开始就一直处于快速下降的趋势,并且在70次后搜索速率就已经很低,超过100次迭代后搜索能力几乎消失。

3.2 仿真实验

3.2.1Oliver问题实验分析

在实例仿真验证中,结合TSPLIB的Oliver30问题进行实验,蚁群算法的实验设定如下:α=1,β=4,ρ=0.5,q= 0.5,迭代上限 500 次;实验结果如表2所示。

表2 Oliver30问题实验结果Tab.2 Experiment results of oliver 30 problem

由表2可知,改进的蚁群算法在Oliver30问题上求解结果,不管是最优解还是平均解都更接近于TSPLIB官方的最优解,最优迭代次数比一般蚁群算法降低200次,因此可以看出基于要素动态更新和局部搜索机制的改进策略大大提高了最小关键攻击集的求解性能。

3.2.2仿真实验

在本次仿真实验中,选取5种属性攻击图,具体如表3所示。

表3 5种攻击图参数Tab.3 Parameters of five attack graphs

在其他参数条件保持一致的情况下,实验结合一般蚁群算法和改进蚁群算法在其最优的参数设定下计算最小关键攻击集和搜索时长,通过大量的实验样本整理最小关键攻击集的数量统计如表4所示。

表4 最小攻击集的数量统计Tab.4 Statistics of min attack set

由表4可以看出,基于改进蚁群算法在最小攻击集的计算能够更大程度地避免攻击路径忽略。

算法比较和搜索时间的对比结果如图4所示。

(a) 最小攻击集数对比

从图4可以看出,随着网络规模的复杂程度增大,攻击路径越来越多时,改进的蚁群算法在最优解的计算上表现出更好的性能,并且搜索的运行时长也更低,比一般蚁群算法的搜索速率提高了9.11%。这可以得知,基于要素动态更新和局部搜索机制的蚁群算法改进更符合当前复杂网络风险评估需求。

3.2.3攻击概率

为了验证基于改进蚁群算法网络安全评估的实用价值,采用12个常见漏洞与标准漏洞评分CVSS和参考文献[5]中方法的原子攻击概率进行了比较,结果如表5所示。

表5 攻击概率对比Tab.5 Comparison of attack probability

从表5可以看出,CVSS中超过一半的攻击概率均为1,文献[5]中攻击概率基本都达到了80%;而文中提出方法的平均攻击概率不超过30%,最高攻击概率为65%。由此可以得出,基于要素动态更新和局部搜索机制的网络安全评估加固能够有效地降低网络攻击的达成率。

4 结语

文中结合属性攻击图模型,分析了属性攻击图中最小关键集的求解等同于NP问题的解决,同时在应用蚁群算法进行计算时发现随着网络规模的增大,一般蚁群算法计算性能较低,计算运行时长较长;同时,在不同的参数条件下求解结果不稳定,甚至会出现过快收敛从而只能达到结果局部最优的情况。因此引出了基于动态要素更新和自适应遗传算法局部搜索机制的改进思路。通过算法分析和实验对比可以看出,提出的算法在最小关键集的计算性能上得到了较大提升,迭代次数相较于一般蚁群算法减少了92%,搜索性能也得到了增强9.11%,同时对比与通用漏洞攻击评分策略攻击概率下降了40%,更适用于大规模网络安全风险的评估应用。