应用Q学习决策的最优攻击路径生成方法

李 腾，曹世杰，尹思薇，魏大卫，马鑫迪，马建峰

(西安电子科技大学 网络与信息安全学院，陕西 西安 710071)

网络攻击图和最佳攻击路径规划的分析一直以来都是国内外信息安全领域讨论和研究的热点话题之一。在对系统网络进行渗透测试时，渗透测试人员在了解对方网络拓扑以及主机之间连通性的前提下，都希望能够找到一条代价最小、高效精准的攻击路径，以达到渗透的预期目标。本文所要解决的问题就是如何在一个存在IDS报警的网络主机环境里通过机器学习的方式高效精准地寻找到最优的攻击路径。防守者如果能够提前对攻击路径进行构造，站在攻击者的角度思考问题时，则可以帮助系统防御者更好地防护系统，最终避免攻击和威胁的发生。但由于系统网络的复杂性和诸多不确定因素，如：攻击者的攻击行为选择不确定性，环境反馈因素不确定性，主机系统漏洞利用难度不确定性，等，这些不利的条件都对生成攻击图或攻击路径造成了很大的困难。同时攻击者模型的建立与完善的好坏也将直接影响最优攻击路径的价值大小。所以，综合上述的种种因素，合理、科学、高效地生成攻击图和攻击路径具有不小的挑战与困难。

攻击图是目前十分流行的用来分析网络脆弱性关联度的技术，最早是由文献[1]提出的基于攻击图的网络脆弱性分析方法。针对攻击图构造问题，现有的生成攻击图的方式也有很多，主要可分为基于网络属性(即网络安全状态空间)和基于网络脆弱性这两类，同时大多数都是依靠遍历和搜索图结构来获取攻击图，但存在一定的问题，如状态爆炸、攻击图生成速率较慢等。文献[2]所构建的网络动态威胁分析属性攻击图(DT-AAG)模型，虽然解决了传递环路的问题，但其算法冗余，生成图效率低下。文献[3]通过将节点表达为网络安全状态、有向边表达攻击规则的方法，但是存在节点爆炸的问题，等等。文献[4]提出的方法不同于以往传统的生成攻击图的方式，而是将Q-learning这种动态规划的算法思想运用到网络攻击图的生成方法中去；然而该方法不适合计算规模较大的网络拓扑环境，且后续生成最优攻击路径的效率也较低。文献[5]提出将Q-learning机制直接运用到规划最优攻击路径的问题上，从而不依靠生成攻击图便可直接获取最优攻击路径，同时模拟攻击者不需要训练数据、在线学习即可，并且还解决了算法空间复杂度高、生产最佳路径冗余的问题，但是没有考虑主机集群中存在IDS等报警防御机制等情况，且部分算法和模型定义略显复杂，缺乏针对性，占用了较多的内存资源空间。

为解决上述问题，文中提出了一种基于Q-learning算法的最优攻击路径生成方法。该方法主要以Q-learning 算法决策思想为基础，并改善、简化攻击者决策算法模型，在进行分区可达性的筛检之后，开始模拟攻击者的攻击回合，其间设置环境障碍与影响因素，最终得到最优攻击路径。文中实验模拟了一个中小型公司的内网环境，经过指定的回合数训练学习后，模拟攻击者能够精确、高效地寻找到最优攻击路径，且实验结果表明，目标网络结构越复杂，通过提前分区可达性删除冗余主机的方法越能突出优势。

论文工作的主要贡献在于：

(1) 通过分区和区域可达性分析，降低需要检测的连接数量，提高以Q-learning 算法为核心的模拟攻击者寻找攻击路径的整体学习效率。

(2) 构建复杂有干扰因素的实验环境场景，增强Q-learning算法模型在多变的网络环境中的适应性和决策能力，丰富了实验场景的同时，验证了整体方案的可靠性。

(3) 简化了Q-learning算法模型，使得整个寻路过程更加具有针对性，同时减少占用较多的内存资源空间，使算法变得十分高效。

(4) 采用多回合制训练模式，利用多线程并行计算辅助模拟攻击者学习和训练，大大缩减训练时间，并通过遍历搜索Q表的方式得到最优攻击路径，降低算法的复杂度。

1 相关工作

传统的大多数生成分析网络脆弱性的方式都是通过构建攻击图来实现的；采用优先搜索的算法遍历攻击图以获取最优攻击路径，根据攻击图的构建方式可分为状态攻击图和属性攻击图，这也是最常用的两种构建方式。文献[6]对攻击图的基本构成做出了详细的介绍，并且分析了各种攻击图类型的优缺点。但是基于以上两种攻击图所存在的问题是：攻击路径生成速度较慢，并且应对状态爆炸问题而采用的限定路径的方法导致了攻击路径的缺失。LIU等建立的网络攻击节点路径检测模型具有较高的准确性，有效地提高了网络安全分析的效率，但是存在状态爆炸的问题。为了解决攻击图存在的上述问题，降低这些问题对获取最优攻击路径的影响，研究人员将隐马尔可夫模型和攻击图相结合，并采用蚁群优化算法以概率式方法计算最优攻击路径，同时文献[7]在此基础再次进行了深度研究。但将隐马尔可夫模型和攻击图相结合并采用蚁群优化计算的方法在面对大规模计算机集群时，由于其开销问题，无法快速计算出最优攻击路径。同时，文献[8]根据路径的攻击成本，通过蚁群优化算法来进行最优攻击路径的预测，但不足之处在于追求较低的攻击代价的同时，忽略了攻击收益对于预测攻击路径的影响。基于贝叶斯网络的分析模型具有强大的不确定性问题处理能力，同时也能够有效地进行多源信息表达与融合。文献[9]就贝叶斯网络，提出了将CVSS评分系统与其相结合的分析模型，各个节点上的置信度被转化为成本和收益的计算，的确对贝叶斯网络的分析模型进行了优化；但是不足之处在于未考虑单位时间内的攻击收益和成本的差值。文献[10]在消除攻击图上环路的基础上，将模型转换为贝叶斯网络攻击模型(BNAG)，引入节点攻击难度和节点状态变迁度量指标计算节点可达概率。之后，文献[11]又定义了网络攻击增益图(NAPG)模型，根据路径概率、增益速率，利用最优增益路径预测算法实现对最优增益路径的预测。除此之外，文献[12]针对当前攻击图模型中很少考虑攻击事件对所有属性节点置信度的动态影响，提出一种基于贝叶斯攻击图的动态风险评估模型，该模型运用贝叶斯信念网络建立用于描述攻击行为中多步原子攻击间因果关系的概率攻击图。但基于贝叶斯网络的攻击图并没有解决最优弥补集的问题。文献[13]提出了基于转换的攻击图分析方法研究，论证了最优弥补集问题与加权碰集问题之间的等价性，并提供了相应的形式化转换方法。除攻击图外，攻击行为态势和攻击路径的预测也是需要解决的难题。文献[14]为准确、全面地预测攻击行为并量化攻击威胁，提出一种基于攻击预测的安全态势量化方法；该方法也通过设计基于动态贝叶斯攻击图的攻击预测算法，进而推断后续攻击行为。文献[15]通过对无线网络中异常信息的入侵意图进行预测，可以有效地保证网络的安全性和稳定性，但是该模型分析的效率不高。胡昌振团队针对以上的问题提出了将Q-learning的算法思想应用到寻找最优攻击路径上去，这种规划方式主要解决了以下的问题：① 提出的网络模型不需要进行训练，因此不需要收集训练数据；② 可在线学习，实时确定不同时刻不同网络状态对应的最佳攻击路径；③ 学习率使用了退火模型，所以收敛的更加精确；④ 由于不需要生成攻击图，所以可以适用于大规模计算机集群。引入Q-learning算法可以解决大部分基于攻击图生成攻击路径方式所存在的问题，但是同样也带来了新的问题，就文献[5]提出的方案方法来看，其缺点如下：① 算法空间复杂度较高，因此占用内存空间较多；② 存在路径冗余的问题。胡昌振等就之前提出的Q-learning算法的方案提出了进一步的改进措施，其具体的改进措施和优点如下：① 将动作和状态融合，降低算法的空间复杂度；② 加快最优攻击路径的生成速度；③ 使得生产的攻击路径更加简洁有效。但是在胡昌振等改进后的该方法中，并没有在模拟攻击者开始学习寻路之前简化网络拓扑图，使得整个训练过程会增加冗余的环境分支，从而降低模拟攻击者寻路的整体效率。实验环境中也未加入防御措施和防御手段去阻碍、干扰攻击者的训练学习过程，同时立即回报函数定义复杂，使得整个寻路过程缺乏针对性。

2 提出方法

2.1 方法概述

为了解决攻击图的生成结果冗余、生成效率低下以及攻击路径的生成存在需要人工修剪的问题，提出了一种简化网络拓扑、强化具体攻击模型的方法。方法图如图1所示。

该方法通过路由表和防火墙策略规则，计算分区子网间可达性，对目标网络结构进行化简，同时删除冗余的网络拓扑结构分支，并将修改完善后的Q-learning的核心算法决策思想加入到模拟攻击者的决策行为依赖函数中，以回合制的方式反复地进行学习和训练，不断更新自己的行为决策；其间设置监控、障碍干扰攻击者的决策过程，最终获取到最优网络攻击路径序列的方法。在整个寻路过程中，通过利用分区可达性使整体的训练学习效率极大的提高，而且具体化后的Q-learing决策思想模型，能够通过不断的适应环境以此来更新行为-价值表，提高模拟攻击者行为决策的科学性与准确性，以获得最大的回报函数值，并最终达到收敛。同时也能够针对不同的训练环境，作出合理的选择与判断，生成的攻击路径序列也不存在需要人工修剪的问题。

2.2 系统描述

2.2.1 网络拓扑化简

首先获取攻击环境中的网络主机分布结构，绘制网络拓扑图；然后通过图2所示子网可达性判断的方法，根据网络环境中的各路由器的路由表与环境子网表计算出子网间可达性；接着对子网间可达性表进行进一步的细化切分，只筛选出可达的子网，并通过图3所示防火墙规则判断的方法，结合主机网络信息表和防火墙规则表计算出主机可达性，最后得到主机可达性表。主机可达性表包括两种情况，第1种情况是主机之间属于同一子网，第2种情况是主机之间属于不同子网且子网间存在可达关系，若不属于同一个子网且子网间不可达，则不用计算主机之间的连通性。在整个过程中，采用并行的机制进行计算，以提高计算的效率。通过分析分区可达性，可大大减少对攻击者需要训练和学习环境中的冗余主机节点，提高攻击者的整体学习效率。

图2 子网可达性判断伪代码

2.2.2 攻击者模型建立

首先通过漏洞扫描器和人工确认检测，获取该网络环境下各主机中存在的漏洞，建立主机漏洞状态表Host_vulns(HostID，vulnID，vulnScore)，其中HostID指主机名称编号，vulnID指主机漏洞编号，vulnScore指漏洞评级。

然后建立Q-learning学习模型Q，即模拟攻击者的决策行为选择模型。公式如下：

q(St，a)=(1-α)*q(St，a)+α*(Rt+1+γ*maxaq(a，St+1)) ，

(1)

其中，①α表示学习效率，决定现实的Q值与估计的Q值之间的误差有多少会被模拟攻击者所学习到，从而更新Q表中的值；在这个模型中，α取常数值0.01；不同于文献[5]中所设定那样，假设该攻击者具有稳定的学习能力，不会受环境的因素等其他因素的影响，在具体化攻击者模型的同时简化了公式，降低算法的复杂度；②γ表示对未来奖励的衰减值；若γ取值为(0，0.5)，则表示该攻击者在一定的评价指标下只考虑眼前的利益价值，而容易忽略长远的价值，即缺乏远见意识；若γ取值为(0.5，1.0)递增上涨，则表示该攻击者逐渐有远见，不满足于眼前的利益，而考虑长久化的利益，从而获取最优攻击路径的效果会更佳；根据对攻击者的模拟情况来看，对γ的取值为常数0.9，表示这是一个有经验且有远见的攻击模拟攻击者；③Rt+1表示模拟攻击者到达下一状态的立即奖励；④ maxaq(a，st+1)表示模拟攻击者想象自己在下一状态时采取在该状态下的行为集合所得到的Q值中的最大值。

同时简化立即回报函数R(S，S′)，淡化中间过程主机在整个攻击过程中的价值分量，统一设置立即回报值为0：

R(S，S′)=0(S′≠S_IDS&&S′≠S_TARGET) 。

(2)

提高IDS报警主机和最终目的主机在此过程中的绝对影响，分别设置立即回报值为

R(S，S_TARGET)=TARGET_VALUE，R(S，S_IDS)=-(TARGET_VALUE+1) ，

(3)

其中，TARGET_VALUE为除目标主机之外的其余主机的漏洞评级的均值加上目标主机的漏洞评级。

2.2.3 最优攻击路径构造

通过上述所构造的基于Q-learning的决策算法，将该算法加入到模拟攻击者的决策行为选择函数中，同时设置模拟攻击者的初始主机位置并确定目标主机，然后开始获取最优攻击路径。在整个决策模型中，设置ε-greedy的值为0.9，ε-greedy为用在决策上的一种策略，具体表示模拟攻击者在90%的情况下会根据Q表给模拟攻击者的状态价值反馈来选择自身的行为；而在10%的情况下，模拟攻击者会随机选取自身的行为，不依据Q表进行决策。获取最优攻击路径的过程如下：首先获取网络结构，接着根据图4所示主机可达性计算的方法获取主机可达性表，然后通过漏扫和人工确认获取主机漏洞状态表，漏洞作为已知条件，通过二次确认部署成功，并同时初始化Q表。接下来的寻路训练采用回合制的方式进行，初始化回合数为n，在每次回合中，利用图5所示获取最优攻击序列的方法模拟攻击者进行寻路学习并根据Q-learning算法模型同步更新Q表。但在利用图5方法寻路的整个过程中，会发生两种情况：一是成功获取到目标主机权限，二是被配置有IDS异常行为检测报警系统的主机检测到，并被永久封禁IP。两种情况都代表着一回合的结束，但在后者情况中模拟攻击者需要更换IP代理再次进行寻路学习训练，直到回合数达到设定要求。在第n+1次寻路过程里，重新设置Q-learning算法模型中的ε-greedy值为1，使模拟攻击者在该回合中完全按照之前寻路训练得到的Q表进行决策判断，以获取最终的最优攻击路径序列。

图4 主机可达性计算伪代码

3 实验与分析

3.1 实验设置

本次实验场景选择为模拟一家公司的内网环境，公司内网中存在内网服务器区、技术部vlan、财政部vlan、市场部vlan、内部文件信息区。攻击者初始主机位置在该公司技术部的一名员工主机上，目标主机为内部文件信息区的某一存储大量信息文件的主机。通过实验网络环境中的各路由器的路由表与环境子网表计算出子网间可达性，接着对子网间可达性表进行进一步的细化切分，只筛选出可达的子网，并通过主机网络信息表和防火墙规则表计算出主机可达性，从而获取主机可达性表，并删除了冗余主机节点。

3.2 获取攻击路径

得到所生成的主机可达性表后，开始100次回合数的寻路训练，在第101次寻路过程中，将ε-greedy值设置为1，表示模拟攻击者完全依赖Q表进行行为决策的选择，通过前面回合过程中的训练学习，Q表中的值已达到收敛，即通过Q表进行决策可有效地反映模拟攻击者的学习效果与决策结果。模拟攻击者最终获取到最优攻击路径序列为：Attack_ sequence=[H1，H2，H9，H8，H7，Ht]，即H1H2H8H7Ht这条攻击路径，如图6所示。经过检测，所得路径确为本实验环境中的最优攻击路径。同时，改变实验环境主机拓扑结构，主机结构变化为图7的连通性结构，再次进行实验分析。根据同样的方法得到的最优攻击序列为：Attack_ sequence=[H1，H5，H6，H9，H12，H15，HT]，如图5所示，经过检测，所得路径也确为该环境下的最优攻击路径。

图6 初始环境下最优攻击路径

3.3 性能对比

在本节中，通过控制变量的方法，测试在不同的回合数设定值的条件下，模拟攻击者每回合的时耗情况，即平均回合时耗(总时耗/回合数)。同时，将本文方法与文献[5]的方法进行对比，在相同的网络环境下，测试不同网络主机数量对总时耗的影响。图8和图9为实验数据结果。

图8结果表明，随着回合数的增加，模拟攻击者的每回合时耗不断下降，且下降比例随着回合数的增加比例同步上升。在文中所建立的Q-learning决策模型中，Q表扮演了很重要的角色，通过Q表的不断迭代更新，Q表在模拟攻击者的行为决策选择中产生的积极影响也越来越大，表明模拟攻击者有更大的可能性去选择更加适合的下一步行为。

图8 攻击者每回合的时耗情况

图9结果表明，随着环境主机数量的不断增加，在主机数量不太大，网络环境复杂度有限的情况下，两种方法的总时耗相差不大。但随着主机数量的大幅度增加，文中方法与文献[5]所提出Q学习改进方法的差异逐渐拉大，且文中方法的总时耗增加幅度远小于与胡昌振等所提出Q学习改进方法中的总时耗的增加幅度。该结果是因为文中方法在进行模拟训练之前，先对目标网络环境的网络拓扑结构进行了分区域可达性判断，删除了大量冗余节点，在环境主机数量逐渐增大的过程中，该步骤便对整个寻路过程产生了极大的积极影响。该实验结果进一步证实了在复杂度高的网络环境中，通过分区和区域可达性分析来化简网络拓扑结果，删除冗余主机节点，有利于降低检测数量，提高寻路过程的效率。

最后，从准确度的角度比较了文中方案与胡昌振团队方法的差异。图10实验结果表明，在寻路试验次数不太多的情况下，文中方法的准确度不及他文方法；但随着试验次数的不断增加，文中所建立的模拟攻击者模型对目标环境的适应能力也逐渐增强；同时在本文的Q-learning决策算法模型中，将部分参数常数化，使得模拟攻击者的模型变得十分具体，这在面对一个陌生的网络环境是不太友好的，但随着熟悉程度的增加，辅助模拟攻击者进行决策行为选择的Q表总体趋势逐渐达到收敛，模拟攻击者对该网络环境的决策能力与适应能力也并行提高。所以在实验次数达到一定的程度下，文中方法与胡昌振团队的准确度大致相同，并在某些时间段中，文中方法的准确度高于胡昌振团队的方法的准确度。

文中方法的P-R曲线图如图11所示，P-R曲线图的平衡点BEP在(0.56，0.58)区间，该值表明文中方法的机器学习具有良好的性能与可靠性。

图10 准确度差异比较情况

4 结束语

将Q-learning算法思想运用到寻找最优攻击路径的方法中去，同时对攻击者决策模型、环境等具体措施做出了针对性的改进。并且，方法中加入了分区域分析主机可达性、删除冗余主机节点的策略。经过实验之后，得到了准确的最优攻击序列。同时，所采用的算法模型显著地降低了算法的复杂度，减少了所占内存空间，并在复杂网络环境下具有突出的优势。在后续工作中，首先需要进一步完善模型，减少常数化参数的设定，增强模型的扩展性。其次，改进获取最优攻击路径的方式，使获取过程更加的科学、准确，减少或避免出现最优攻击路径生成存在冗余节点、攻击路径生成不全等其他问题。