<span class="emphasis_bold"> 基于吸收Markov链的网络入侵路径预测方法 </span>

1 (解放军信息工程大学郑州 450001) 2 (中国科学院软件研究所可信计算与信息保障实验室北京 100190) 3 (河南省信息安全重点实验室郑州 450001) 4 (中国电子技术标准化研究院北京 100007) (wjjhh_908@163.com)

网络入侵是指攻击者利用目标网络中的一些漏洞，通过实施蓄意的多步骤攻击行为来达到最终的攻击目的，使得网络安全领域面临严峻的考验与挑战 [1-3] .如臭名昭著的Zeus僵尸网络 [2] 实施扫描探测、溢出攻击、感染目标主机、病毒传播和窃取用户信息这5个步骤使国家、企业和个人遭受了无法挽回的经济损失.日益泛滥的蠕虫攻击 [3] 也属多步攻击范畴，防护基于多步攻击的网络入侵刻不容缓.入侵路径预测旨在通过分析网络节点的脆弱性关系，从攻击者角度出发，分析可能的攻击路径，预测潜在的攻击行为，挖掘关键威胁节点，为网络安全主动防御提供重要依据，受到国内外学者的广泛关注 [4-20] .

早期研究主要围绕设计随机模型来描述多步攻击状态变迁过程，进而利用概率论及数学推理的相关知识来预测可能的状态转移情形.Yu等人 [4] 利用隐彩色Petri网区分不同攻击行为节点，对告警进行关联，能够预测潜在的攻击路径.吕慧颖等人 [5] 构造了威胁状态转移图来分析威胁事件的时空关联，实时识别威胁状态，并预测攻击路径.考虑到不同攻击步骤间存在因果关联，王硕等人 [6] 将单步攻击间的转移概率表示为因果知识，设计了因果知识网络描述网络入侵过程，并利用Dijkstra算法预测不同能力的攻击者在入侵路径选择上的差异性.刘玉岭等人 [7] 融合攻击方、防护方和网络环境信息，通过时空维度分析，预测了基于攻击威胁的网络安全态势的变化趋势，辅助攻击意图识别和路径预测的研究.

近年来，攻击图(attack graph, AG) [8-22] 作为一种基于图论的脆弱性评估模型，已成为研究多步攻击的主流方法，它从攻击者的角度出发，在综合分析多种网络配置和脆弱性信息的基础上，枚举所有可能的攻击路径，从而帮助防御者直观地理解目标网络内各个脆弱性之间的关系，以及由此产生的潜在威胁.目前研究者已开发多种攻击图自动生成工具(如MulVAL，TVA，NetSPA等 [8] )，兴起了攻击图研究的新一轮热潮.

Kerem [8] 综述了攻击图的研究现状，指出攻击图的可达性分析和路径研究是攻击图研究的重点之一.Sheyner等人 [9] 最早将概率论与攻击图相结合，基于Markov决策过程，利用条件转移概率分析非确定性节点，指出攻击者倾向于选择最有利于实现攻击目标的路径完成状态转移.Sarraute等人 [10] 改进了Floyd-Warshall算法来预测最短攻击路径.Abraham等人 [11] 通过分析漏洞生命周期，预测了路径长度随时间的变化规律.针对攻击发生的不确定性问题，刘强等人 [12] 引入不确定攻击图，利用最佳漏洞利用链，衡量最有可能的攻击路径.陈小军等人 [13] 在攻击图模型中引入转移概率表，利用观测事件推理单步攻击的不确定性，通过累积概率预测最有可能的攻击路径.Zhu等人 [14] 利用聚类告警关联分析，借鉴神经网络技术构建完整攻击场景，挖掘潜在的攻击策略.相关研究还包括路径数量评估 [15] 、路径长度的中位值分析 [16] 、平均路径长度度量 [17] 、最短耗时路径预测 [18] .在实际应用方面，Dai等人 [19] 分析了如何利用攻击图中的最大风险流路径来预测潜在威胁.通过阻断最大可能攻击路径，Nayot等人 [20] 设计了网络安全风险的动态评估方法.

梳理以上研究成果发现，尽管现有研究很多，但主要围绕理想攻击场景下的路径预测展开研究，默认每次漏洞利用都能成功实施，包括了最大可能攻击路径、成功概率和路径数量等，然而理想的最大可能攻击路径不一定是攻击者采用的攻击路径，需对攻击路径的概率分布、原子攻击次数和节点威胁度等进行全面感知分析，更全面地辅助安全管理员决策.

针对此问题，本文将吸收Markov链 (absorbing Markov chain, AMC)引入到攻击图研究领域，由于AMC中状态转移具有无后效性和吸收性质，符合网络攻击的随机性和目标状态节点的可达性特点，提出基于吸收Markov链的攻击路径预测方法.首先证明完整攻击图可以映射到吸收Markov链，然后基于通用漏洞评分标准(common vulnerability scoring system, CVSS) [21] 提出状态转移概率度量方法，分析并构造状态转移概率矩阵，在此基础上设计2种预测算法，计算节点访问次数期望值和攻击路径长度期望值，最后通过实验验证本文方法的有效性.

本文的主要贡献：1)预测不同攻击状态节点访问次数的期望值，并对节点的威胁进行排序；2)分析不同长度攻击路径的概率分布，并计算路径长度的期望值.前者可用于指导网络安全管理员实施脆弱性修复的优先顺序;后者利于掌握攻击者利用不同路径入侵的可能性，并预测完成攻击目标所需攻击步骤的数量.

1 基于吸收Markov链的攻击图

吸收Markov链适用于随机模型的状态转移预测问题，基本思想是将攻击图映射到吸收Markov链，建立基于吸收Markov链的攻击图模型.一方面Markov链的无后效性符合攻击状态转移仅与相邻状态有关的特点；另一方面，网络攻击至少存在一种终止状态，与吸收Markov链的吸收态相符.

1 . 1 预备知识

Table 1 Symbols and Their Descriptions in This Paper
表1 本文主要符号及其描述

定义1 . 原子攻击 a .指攻击者在网络中实施的单个攻击动作，其可能是对主机服务的扫描或对主机漏洞的1次利用，每个原子攻击动作触发攻击者转移到1个攻击状态 S ，原子攻击发生的概率为 p ( a ).

定义2 . 攻击路径 AR .指攻击者从初始状态节点到目标状态节点有向边的集合，攻击路径 AR = S 1 → S 2 →…→ S n .

定义3 . 攻击路径长度 RL .指攻击路径中包含的边的数量，即 RL = n -1.

定义4 . 攻击成功概率 p ( AR ).指攻击路径中所有状态转移都成功的概率 p ( AR )= p ( a 1 )× p ( a 2 )×…× p ( a RL ).

定义5 . 攻击路径期望长度 EARL .指攻击者为实现攻击目标所实施的攻击步骤的数学期望值.

定义6 . 状态访问期望次数.指实现攻击目标过程中，某个状态节点访问次数的数学期望值.

定义7 . 状态节点威胁排序.指不同状态节点对实现攻击目标的贡献排序，节点排序越靠前，表明该节点的威胁越大.

1) 在定义5中，若1个攻击者分别以概率1

3和2

3实施长度为1和4的2条路径，则攻击路径长度期望值 EARL =3.

2) 在定义6中，理想情况下每次状态转移都能成功(对应原子攻击成功实施)，而实际情况下，由于攻击者对网络结构不熟悉，原子攻击存在概率，若攻击状态转移失败，看作是对原状态的重复访问，在存在状态重复转移的情况下，求解 EARL 存在困难性.

3) 在定义7中，对于攻击者而言，漏洞利用越频繁的节点对于实现攻击的贡献值越高，因而对网络安全的威胁越大.本文利用定义6中不同状态节点访问次数期望值的高低对节点威胁进行排序.

1 . 2 攻击图的概念

攻击图是对多步攻击行为关联建模的有效方法，从攻击者角度出发，描述了攻击状态转移过程，是一个有向图，如图1所示:

定义8 . 攻击图 AG .使用一个四元组 AG =( S , A , E , Δ )来表示，其中， S 表示状态节点集合， A 表示原子攻击节点集合， E 表示为状态节点间的有向边集合， Δ 表示状态转移概率集合.

2) E ⊆ S × S ，∀ e i , j ∈ E ， e i , j 表示连接节点 S i 和 S j 的边，其中 S i 表示 e i , j 的起始状态节点， S j 表示 e i , j 的目的状态节点，实现状态转移 e i , j 依赖的原子攻击为 a ；

3) ∀ Δ ( e i , j )∈ Δ ， Δ ( e i , j )表示攻击者由状态 S i 转到状态 S j 的概率 p ( S j | S i )，且 Δ ( e i , j )等于原子攻击 a 的发生概率 p ( a ).

利用脆弱性扫描工具如Nessus，Retina [22] 对网络进行漏洞扫描，依据部署网络的拓扑结构与采集到的脆弱性集，结合攻击图自动生成工具MulVAL [23] 构建攻击图，避免了手动构建的复杂性，是目前的主流构造方法.

1 . 3 吸收Markov链的相关定义

定义9 . Markov链MC [24] .对于一个离散的包含有限状态的随机序列集合 X ={ x 1 , x 2 ,…, x n }，如果每个状态值仅与前一个相邻的状态值有关，而与再之前的状态无关，称为Markov链.

定义10 . 状态转移概率矩阵 P .将Markov链中的状态转移概率用邻接矩阵 P 表示，其中 p i , j 表示状态 x i → x j 的概率，若 x i → x j 不可达，令 p i , j =0，矩阵 P 满足

定义11 . 初始状态.表示攻击者的出发状态，该状态节点只有流出边，没有流入边.

定义12 . 吸收状态.表示攻击者的目标状态，该状态节点只有流入边，没有流出边.

定义13 . 过渡状态.状态序列中，除去吸收状态的其他状态称为过渡状态.

定义14 . 吸收Markov链AMC [24] .含有吸收状态的Markov链称为吸收Markov链，对应状态转移概率矩阵表示为

其中， Q 是 t × t 的矩阵，表示过渡状态间的转移概率； 0 是 r × t 的零矩阵； R 是 t × r 的非零矩阵，表示过渡状态到吸收状态的转移概率； I 是 r × r 的单位矩阵；所有状态数量 n = t + r .

1 . 4 攻击图到吸收Markov链的映射

本节给出攻击图中状态转移概率的归一化处理算法，并生成状态转移概率矩阵，在此基础上证明完整的攻击图可以映射到吸收Markov链.

证明. 由于攻击图描述了网络的脆弱性利用关系，通过基于脆弱性利用的多步关联，攻击者最终将达到稳定的终止状态，因此攻击图的终止状态即吸收状态，且至少包含1个吸收状态.

步骤1. 令 i , j =1， G = S ，其中 i 和 j 分别表示矩阵 P 的第 i 行和第 j 列；

步骤4. 对于节点 S i ∈ S ，从节点集合 G 中随机选取1个节点 S j ，令 G ={ G - S j }；

步骤5. 判断状态转移 S i → S j 对应边 e i , j 的概率 Δ ( e i , j )>0是否成立，若不成立，则令状态转移概率矩阵 P 中位置( i , j )对应元素值 p i , j =0，转至步骤3,否则令 e i , j k = e i , j ，将 e i , j k 添加至集合

中，令 k = k +1；

步骤6. 令 j = j +1，若 j ≤ n ，则转至步骤4，否则该步骤结束，令 j =1， k =1， G = S ；

步骤7. 对于集合

中包含的边 e i , j 1 , e i , j 2 ,…, e i , j k ，将

按序赋值给矩阵 P 中第 i 行位置( i , j 1 ),( i , j 2 ),…,( i , j k )上的元素值 p i , j 1 , p i , j 2 ,…, p i , j k ，该步骤结束；

步骤8. 令 i = i +1，若 i ≤ n ，则转至步骤1，对于每个状态节点 S i ，重复步骤4～6，完成节点 S i 流出边的概率值归一化处理，并生成矩阵 P 的第 i 行；若 i > n ，则该步骤结束；

由算法1递归过程可知，时间复杂度的阶数为 O ( n 3 )，算法1执行过程中需要维护 n × n 矩阵 P ，包含 k 个元素集合

因此空间复杂度的阶数为 O ( n 2 )，复杂度符合多项式时间级别.

命题2 . 1个完整的攻击图可以映射为1个吸收Markov链，若以下2个条件成立:

1) 对于任意状态节点 S i 满足定义10，即该节点的所有流出边的概率之和等于1；

2 攻击路径预测

在第1节的基础上，本节首先给出一种通用的基于CVSS的转移概率度量方法，然后分析节点访问次数的期望值，最后计算攻击路径长度的期望值.

2 . 1 基于CVSS的转移概率度量

CVSS由美国国家基础建设咨询委员会发布，是漏洞评估的行业公开标准，其制定的漏洞可利用性评分准则(如图2所示)全面衡量了漏洞的利用难度，通过查询美国国家漏洞数据库(national vulner-ability database, NVD) [25] 可以得到具体值.本文利用攻击难度来度量状态转移概率，给出一种基于CVSS的转移概率度量方法，以增强研究的通用性.

由图2可知，CVSS给出原子攻击 a 依赖漏洞的可利用性得分 score ( a )=20× AV × AC × AU ，且0< score ( a )≤10.得分越高表明漏洞利用越容易，则攻击难度越小，状态转移成功概率越大，当节点转移失败时，定义流向自身边的可利用性得分为10.

设攻击图 AG 中状态转移边 e 的概率值与依赖原子攻击 a 的可利用性得分 score ( a )成正比，即 Δ ( e )= f × score ( a )，其中 f 是比例系数.对于任意节点 S i 的流出边 e i , j 1 , e i , j 2 ,…, e i , j k ，利用算法1标准化处理后的转移概率为

2 . 2 节点访问次数的期望值预测

本节首先给出吸收Markov链中状态转移满足的若干引理，其中引理1给出 n 步攻击后的AMC的状态转移概率矩阵，引理2证明经过 n ( n →∞)步后，过渡状态间的转移概率为0，在此基础上结合概率论，定理1得到状态节点访问次数的期望值求解矩阵，最后给出节点访问次数期望值计算流程.

引理1 . 若 P 是满足定义14的吸收Markov链的状态转移矩阵， p i , j 表示攻击者从节点 S i 转移到 S j 的概率，令

表示攻击者从状态 S i 出发，经过 m 步转移后，到达状态 S j 的概率，则:

引理2 . 攻击者从任意非吸收状态出发，最终都会到达吸收状态，即经过 m ( m →∞)步后，过渡状态间的期望转移概率为0，满足:

证明. 结合定义14和引理1，若上式成立，即要证明

不妨设 Q i , j = u ∈(0,1)，其中 Q i , j 表示攻击者由节点 S i 一步转移到 S j 的概率；令

表示攻击者通过 m 步攻击，由初始节点 S i 经过中间节点 S l 1 , S l 2 ,…, S l m -1 到达目标节点 S j 的概率，得到

因此攻击者最终停留在过渡状态的期望概率为0.

定理1 . 攻击者从过渡状态 S i 出发，在吸收前访问过渡状态 S j 的次数期望值用 N i , j 表示，其中1≤ i , j ≤ t ，设 N 为大小为 t × t 的矩阵，将 N i , j 赋值给矩阵 N 中位置( i , j )元素，称 N 为攻击次数期望值矩阵，则 N =( I - Q ) -1 .

证明. 1) 攻击者从节点 S i 出发，分别经过 m =0,1,2,3,…步，访问节点 S j 的次数期望值总和

基于网络拓扑结构和漏洞扫描信息，利用自动生成工具MulVAL生成攻击图 AG ，通过查询NVD数据库得到漏洞可利用性得分，在此基础上给出节点访问次数的期望值预测步骤如下:

输出：以状态节点 S i 为初始节点，在吸收前转移到节点 S 1 , S 2 ,…, S t 的期望次数 N i ,1 , N i ,2 ,…, N i , t ，以及节点威胁排序.

步骤1. 依据算法1，利用2.1节转移概率度量方法，结合 AG 的漏洞可利用性得分生成 AMC 的 n × n 的状态转移概率矩阵 P ，其中矩阵 P 的第 i 行向量的位置( i , j 1 ),( i , j 2 ),…,( i , j k )上的元素值为

步骤2. 由矩阵 P 构造 t × t 的过渡状态间的转移概率矩阵 Q ；

步骤3. 计算 t × t 期望值矩阵 N =( I - Q ) -1 ，输出行向量( N i ,1 , N i ,2 ,…, N i , t )；

步骤4. 依据( N i ,1 , N i ,2 ,…, N i , t )中元素值大小对节点 S 1 , S 2 ,…, S t 的威胁进行排序，步骤结束.

The value next to the arrow line means the transition probability from one state to another.

Fig. 3 Example of attack graph
图3 攻击图实例

为简化说明，图3中状态转移概率值已归一化处理，过渡状态为 S 1 , S 2 , S 3 ，吸收状态为 S 4 ，得到状态转移概率矩阵 Q 和 P ，并计算期望值矩阵 N .

由 N 的第1行可知，从初始状态 S 1 出发，访问节点 S 2 , S 3 次数的期望值为8

7，5

7，此时节点的威胁排序为 S 2 > S 3 .

2 . 3 攻击路径长度的期望值预测

本节在2.2节的基础上，首先给出求解攻击路径长度的期望值向量的推论，在此基础上分析路径长度的期望值计算过程.

推论1 . 攻击者从节点 S i (1≤ i ≤ t )出发，吸收前转移总次数的期望值(期望路径长度)用 T i 表示，设 T 是大小为 t ×1的矩阵， C 是大小为 t ×1的单位矩阵，将 T i 赋值给 T 位置( i ,1)的元素，称 T 为期望路径长度矩阵，则 T = N · C .

证明. 由定理1可知，对于任意节点 S i ，在吸收前转移到节点 S 1 , S 2 ,…, S t 的次数分别为 N i ,1 , N i ,2 ,…, N i , t ，则从节点 S i 出发的期望攻击路径长度 T i = N i ,1 + N i ,2 +…+ N i , t ，因此 T =( T i )=( N i ,1 + N i ,2 +…+ N i , t )= N · C .

结合拓扑分析和漏洞扫描，利用工具MulVAL生成攻击图，查询NVD数据库得到漏洞信息，并设计攻击路径长度的期望值预测方法如下:

输出：状态节点 S i 作为初始节点，攻击路径长度的期望值 T i .

步骤1. 结合算法1和方法1，构造AMC的 n × n 状态转移概率矩阵 P ，位置( i , j 1 ),( i , j 2 ),…,( i , j k )值为

步骤2. 构造AMC的过渡状态间的转移概率矩阵 Q ，大小为 t × t ；

步骤4. 令 C =(1,1,…,1) T ，大小为 t ×1，计算 t ×1的路径长度期望值向量 T = N · C ，输出节点 S i 出发的路径长度的期望值 EARL ( S i )= T i ，步骤结束.

1) 算法执行包含矩阵求逆、矩阵相加和矩阵相乘过程，其中矩阵相乘的时间复杂度最高，当2个 n × n 矩阵相乘时，包含2 n 3 次乘法运算，因此时间复杂度的阶数为 O ( n 3 ).

2) 算法需要维护 n × n 矩阵 P 、 t × t 矩阵 Q 、 t × t 矩阵 N 、 t ×1矩阵 T 和 C ，因此存储复杂度为 O ( n 2 ).

综上，算法复杂度符合多项式时间级别，在当前计算环境下能够执行实时运算.

则从节点 S 1 , S 2 , S 3 出发的攻击路径长度的期望值为20

7，12

7，15

结合定义14，[ Ν · R ] i , j 表示攻击者由过渡状态 S i 转移到吸收状态 S j 的概率.计算

3 实验与分析

为了验证本文方法的有效性和适用性，我们设计了2个实验对该方法进行了测试分析.其中实验1参照文献[6]搭建了一个小型模拟攻防环境；实验2选用林肯实验室提供的经典DARPA2000标准测试集 [26] ，分析DDOS攻击场景下的实验结果.最后给出本方法与现有方法的综合对比分析.

3 . 1 实验1

为验证本文方法的有效性，搭建了一个实际网络来进行测试.实验拓扑如图4所示，网络中包括防火墙、入侵检测系统Snort IDS、2台主机以及3台服务器.防火墙预先设置策略将网络分为2个子网，使得服务器 H 1 ， H 2 分布在DMZ Zone，服务器 H 3 ， H 4 ， H 5 分布在Trusted Zone.防火墙1禁止外部主机访问Trusted Zone中的服务器，仅可以利用HTTP协议(80端口)与DMZ Zone内的主机 H 1 和 H 2 进行通信.防火墙2允许DMZ Zone内的主机和Trusted Zone中的服务器进行通信，且Trusted Zone内的服务器仅可以被动接收服务请求.依据攻击发起的初始位置，攻击分为内部和外部攻击2种.

利用脆弱性扫描工具Nessus对各网段进行扫描，并通过查询NVD得到各主机包含的漏洞信息如表2所示：

Table 2 Host Configuration and Vulnerability Information in Network
表2 网络主机配置及漏洞信息

依据部署网络的拓扑结构与采集的脆弱性集，利用工具MulVAL生成攻击图如图5所示，不同状态间转移依赖的漏洞已标注，到节点自身的状态转移边用虚线标出，边值标注为状态转移的可利用性得分，共有7种不同的攻击状态， S 1 表示外部攻击者的初始状态，各状态信息描述如表3所示:

The value next to the arrow line means the exploitability score of vulnerability.
Fig. 5 Attack graph of experimental network
图5 实验网络攻击图

Table 3 List of the State Information
表3 状态信息表

利用2.1节状态转移概率归一化方法，生成吸收Markov链的状态转移概率表,如表4所示，对应吸收Markov链攻击图如图6所示.

Table 4 Probability Table of State Transition
表4 状态转移概率表

理想情况下，若入侵场景中的每次漏洞利用都成功实施，所有可能的11条入侵路径及其概率分布如表5所示，其中最短路径长度为3，最长路径长度为5，路径长度的中位值为4，理想路径长度的平均值为(4+4+5+3+4+4+5+3+3+3+4)

11=3.818.最大可能攻击路径为 S 1 → S 3 → S 6 → S 7 ，累积成功概率为0.444×0.391×0.5=0.087，该攻击过程描述如下：为获得服务器 H 5 的root权限，攻击者首先对目标网络进行IPsweep地址扫描，搜寻有效主机，发现有效主机 H 2 ，通过端口扫描，发现其通信端口为80，利用postgresql服务上的漏洞CVE 2014-0063，获得root权限；随后攻击者利用bmc服务上的漏洞CVE 2013-4782获得服务器 H 4 的用户权限；进一步以服务器 H 4 为跳板，利用radius服务上的漏洞CVE 2014-1878获得服务器 H 5 的root权限，实现攻击目标.

表5 理想攻击路径长度及其概率分布

在实际情况下，若单步攻击的某次漏洞利用不成功，则状态转移失败，看作到自身状态的1次转移，路径长度加1，因而实际的攻击路径长度往往高于理论的攻击路径长度，下面利用本文方法分析实际网络环境中的路径预测信息.

由图6得到状态转移概率矩阵 P 和 Q ，结合方法1和方法2计算期望矩阵 N 和 T 如下所示:

期望值矩阵 N 的不同行代表从不同初始状态出发访问各节点次数的期望值分布，如图7所示.若节点访问次数越高，表明该节点的威胁程度越大，不同节点的访问次数分布不均匀，表明各节点的威胁程度差别较大.例如外部攻击者从状态 S 1 出发，访问节点 S 2 , S 3 , S 4 , S 5 , S 6 的次数分别为0.741,1.087,0.584,0.628,1.610，此时节点威胁排序为 S 6 > S 3 > S 2 > S 5 > S 4 ，因此在漏洞修复时应首先考虑状态 S 6 ( H 4 上的漏洞CVE 2013-4782).

结合图6,由矩阵 T 可知，从不同节点 S 1 , S 2 , S 3 , S 4 , S 5 , S 6 出发，到达攻击目标 S 7 的期望路径长度分布如图8所示，例如初始状态为 S 1 时的期望攻击路径长度为5.65，表示攻击者平均需要实施5.65次原子攻击才能实现攻击目标.通过实时检测攻击发生的位置，确定攻击者的状态，可以预测后续攻击的期望路径长度，对于安全管理员实时掌握当前的攻击状况、制定安全防护措施具有重要意义.

Fig. 8 Expected attack route length starting from different initial state nodes
图8 从不同状态节点出发的期望攻击路径长度

借鉴文献[6]的实验方法，从课题依托信息安全重点实验室中随机挑选100名学员作为攻击者，分别在部署环境(如图4所示)中进行攻击测试实验，攻击者的初始状态为 S 1 ，公开网络的拓扑结构及漏洞信息，既定攻击目标为 S 7 ，实验时间为2 h.通过实时采集网络中运行的防火墙、Snort IDS和主机日志的告警信息，进一步利用自动化工具ArCSight [27] 分析告警信息，得到100条攻击序列，由于4名攻击者未在规定时间内完成攻击目标，剔除未成功的4条攻击序列后，统计长度为3～17的路径数量分别为17，14，13，12，11，9，6，3，3，2，2，1，1，0，0.

统计测试结果得到平均攻击路径长度为596

96=6.208，与理想攻击路径长度的平均值3.818相差较大，而与本文计算得到的期望攻击路径长度的理论值5.65更为接近，与预期相符.统计不同路径长度出现的概率分布，记录为表6所示的测试值，例如长度为3的攻击序列有17条，因此步长为3的路径统计概率为17

100=0.17.同时，依据本文方法，利用Matlab7.1计算长度3(17路径概率分布的理论值如表6所示，理论值与测试值对比如图9所示.

Table 6 Probability Distribution of Attack Route Length by Our Method
表6 本文攻击路径长度的概率分布

1) 长度为3的路径出现概率最大，与本文理论预测结果一致，同时概率值随着路径长度的增大而不断减小，理论值表明当路径长度不断增大时出现概率逐渐趋于0，验证了本文方法的有效性.

2) 实验包含100名攻击者，采集到100个样本，受攻击者自身因素(知识水平、攻击技能、攻击经验等)的影响，不同路径长度出现概率的测试值与理论值不完全相等，但从整体上看，路径长度概率分布的测试结果与理论结果的变化趋势基本一致，符合预期结果.

3 . 2 实验2

本节以林肯实验室提供的DARPA2000数据集中LLDOS1.0攻击场景作为实验对象，文献[14]通过基于聚类的告警关联分析，挖掘了该数据集包含的完整攻击场景，如图10所示，受到广泛认可，并给出如下状态转移概率，本文借鉴该攻击场景进行实验分析：

Δ ( e 2,5 )=0.15,
Δ ( e 2,3 )=0.28,
Δ ( e 3,5 )=0.1,
Δ ( e 1,2 )=0.29,
Δ ( e 2,2 )=0.2,
Δ ( e 2,4 )=0.28,
Δ ( e 4,2 )=0.18,
Δ ( e 4,3 )=0.42,
Δ ( e 4,5 )=0.15,
Δ ( e 5,5 )=1,
Δ ( e 1,4 )=0.33,
Δ ( e 4,4 )=0.18.

利用算法1构造吸收Markov链的转移矩阵 P ，进一步利用算法2和算法3计算矩阵 N 和 T ：

吸收状态节点为 S 5 ， N i , j 表示状态 S i 出发，在到达目标状态之前访问状态 S j 的次数，例如从初始状态节点 S 1 出发，到达节点 S 2 , S 3 , S 4 的次数分别为0.84，5.38，0.98，此时过渡状态节点威胁排序为 S 3 > S 4 > S 2 ，应首先修复状态 S 3 的漏洞.由矩阵 T 可知，从不同节点 S 1 ， S 2 ， S 3 ， S 4 出发，到达目标节点的期望攻击路径长度分别为8.198，7.2，7.692，7.197，结果表明从节点 S 1 出发的攻击者，到达目标状态节点所实施漏洞攻击的平均次数最多.

表7给出了LLDOS1.0攻击场景中理想度量方法和实际度量方法的结果比较，在理想情况下，由于不存在重复状态转移行为，统计得到可能路径数量为8，最短路径长度为2，路径长度类型有2，3，4，所有路径长度的中位值及平均值都是3，攻击意图的累积成功概率为0.14.

相反，在实际情况下，实现攻击意图的期望概率为1，最长和最短期望路径长度分别为8.198和7.197，前者表明平均需要实施8.198次漏洞攻击才能实现目标，后者表明所需要的最少漏洞攻击次数为7.197，该结果显然大于理想路径长度值，与预期相符.因此，利用本文度量方法可以科学评估攻击者当前状态，并准确预测后续攻击行为.

表7 Structural Metrics of LLDOS1 . 0 Attack Scenario
表7 LLDOS1 . 0攻击场景的结构化度量

3 . 3 方案综合对比

本文与典型相关研究的特点比较如表8所示，从表8中可以看出，多数文献均有研究最大可能攻击路径及其概率值.针对理想攻击场景(每次漏洞利用都成功)，本文和文献[6,10,16-17]进一步分析了最短路径，除此之外，本文和文献[6,15-17]能够度量理想攻击路径的数量，其中文献[16-17]和本文又分析了理想路径长度的平均值，且本文和文献[16]进一步讨论了理想路径长度的中位值.

Table 8 Comparison of Features Among Our Method and Others
表8 本文与典型方法的特点比较

特别地，针对实际网络环境(单步攻击实现依赖多次漏洞利用)，本文重点研究了期望路径长度及其概率分布，并给出了状态节点访问次数的期望值预测方法，用于分析节点的威胁排序，更加准确全面地预测攻击路径信息，辅助安全管理员决策，为实际网络环境中应对网络多步攻击威胁提供更多指导.

4 结束语

由于网络入侵者的攻击状态转移过程复杂，因此攻击路径预测对于安全管理员直观地了解攻击过程具有重要意义.考虑到现有方法主要围绕理想攻击路径展开研究，本文将攻击图映射为吸收Markov链，给出了基于通用漏洞评分标准的转移概率量化方法，在此基础上着重研究了实际网络环境中不同状态节点的期望访问次数，用于分析节点的威胁排序，并计算期望攻击路径长度及其概率分布，辅助安全管理员全面分析不同攻击路径的发生概率，掌握攻击者可能实施的原子攻击次数，并预先制定安全防护措施，为防御网络入侵提供指导.

如何结合网络中采集的告警序列，客观地衡量状态转移概率，预测攻击路径长度的期望值，并依据实时观察结果动态修正后续路径长度的期望值，提高复杂攻击场景中预测的准确性和适用性是下一步研究的主要工作.

[1]Zhang Huanguo, Han Wenbao, Lai Xuejia, et al. Survey on cyberspace security[J]. Scientia Sinica Informationis, 2016, 46(2): 125-164 (in Chinese)(张焕国, 韩文报, 来学嘉, 等. 网络空间安全综述[J]. 中国科学: 信息科学, 2016, 46(2): 125-164)

[2]Jiang Jian, Zhuge Jianwei, Duan Haixin, et al. Research on botnet mechanisms and defenses[J]. Journal of Software, 2012, 23(1): 82-96 (in Chinese)(江健, 诸葛建伟, 段海新, 等. 僵尸网络机理与防御技术[J]. 软件学报, 2012, 23(1): 82-96)

[3]Liu Yuling, Feng Dengguo, Wu Lihui, et al. Performance evaluation of worm attack and defense strategies based on static Bayesian game[J]. Journal of Software, 2012, 23(3): 712-723 (in Chinese)(刘玉岭, 冯登国, 吴丽辉, 等. 基于静态贝叶斯博弈的蠕虫攻防策略绩效评估[J]. 软件学报, 2012, 23(3): 712-723)

[4]Yu Dong, Frincke D. Improving the quality of alerts and predicting intruder’s next goal with hidden colored Petri-net[J]. Computer Networks, 2007, 51(3):632-654

[5]Lü Huiying, Peng Wu, Wang Ruimei, et al. A real-time network threat recognition and assessment method based on association analysis of time and space[J]. Journal of Computer Research and Development, 2014, 51(5): 1039-1049 (in Chinese)(吕慧颖, 彭武, 王瑞梅, 等. 基于时空关联分析的网络实时威胁识别与评估[J]. 计算机研究与发展, 2014, 51(5): 1039-1049)

[6]Wang Shuo, Tang Guangming, Kou Guang, et al. Attack route prediction method based on causal knowledge[J]. Journal on Communications, 2016, 37(10): 188-198 (in Chinese)(王硕, 汤光明, 寇广, 等. 基于因果知识网络的攻击路径预测方法[J]. 通信学报, 2016, 37(10): 188-198)

[7]Liu Yuling, Feng Dengguo, Lian Yifeng, et al. Network situation prediction method based on spatial-time dimension analysis[J]. Journal of Computer Research and Development, 2014, 51(8): 1681-1694 (in Chinese)(刘玉岭, 冯登国, 连一峰, 等. 基于时空维度分析的网络安全态势预测方法[J]. 计算机研究与发展, 2014, 51(8): 1681-1694)

[8]Kerem K. A taxonomy for attack graph generation and usage in network security[J]. Journal of Information Security and Applications, 2016, 29(C): 27-56

[9]Sheyner O, Haines J, Jha S, et al. Automated generation and analysis of attack graphs[C]

Proc of the 2002 IEEE Symp on Security and Privacy. Piscatawary, NJ: IEEE, 2002: 273-284

[10]Sarraute C, Richarte G, Lucángeli O J. An algorithm to find optimal attack routes in nondeterministic scenarios[C]

Proc of the 4th Int ACM Workshop on Security and Artificial Intelligence. New York :ACM, 2011: 71-80

[11]Abraham S, Nair S. A predictive framework for cyber security analytics using attack graphs[J]. International Journal of Computer Networks & Communications, 2015, 7(1): 1-17

[12]Liu Qiang, Yin Jianping, Cai Zhiping, et al. Uncertain-graph based method for network vulnerability analysis[J]. Journal of Software, 2011, 22(6): 1398-1412 (in Chinese)(刘强, 殷建平, 蔡志平, 等. 基于不确定图的网络漏洞分析方法[J]. 软件学报, 2011, 22(6): 1398-1412)

[13]Chen Xiaojun, Fang Binxing, Tan Qingfeng. Inferring attack intent of malicious insider based on probabilistic attack graph model[J]. Chinese Journal of Computers, 2014, 37(1): 62-72 (in Chinese)(陈小军, 方滨兴, 谭庆丰. 基于概率攻击图的内部攻击意图推断算法研究[J]. 计算机学报, 2014, 37(1): 62-72)

[14]Zhu Bin, Ghorbani A A. Alert correlation for extracting attack strategies[J]. International Journal of Network Security, 2006, 3(3): 244-258

[15]Ortalo R, Deswarte Y, Kaaniche M. Experimenting with quantitative evaluation tools for monitoring operational security[J]. IEEE Trans on Software Engineering, 1999, 25(5): 633-50

[16]Idika N, Bhargava B. Extending attack graph-based security metrics and aggregating their application[J]. IEEE Trans on Dependable & Secure Computing, 2012, 9(1):75-85

[17]Li Wei, Vaughn R B. Cluster security research involving the modeling of network exploitations using exploitation graphs[C]

Proc of the 6th IEEE Int Symp on CLUSTER Computing and the Grid. Piscatawary, NJ: IEEE, 2006: 26-26

[18]Lucangeli J, Sarraute C, Richarte G. Attack planning in the real world [J

OL]. Computer Science, 2013[2017-06-17]. http:

sciencewise.info

articles

1306.4044

[19]Dai Fangfang, Hu Ying, Zheng Kangfeng, et al. Exploring risk flow attack graph for security risk assessment[J]. IET Information Security, 2015, 9(6): 344-353

[20]Nayot P, Rinku D, Indrajit R. Dynamic security risk management using Bayesian attack graphs[J]. IEEE Trans on Dependable & Secure Computing, 2012, 9(1): 61-74

[21]Schiffman M. Common vulnerability scoring system (CVSS)[EB

OL]. [2017-06-17]. https:

www.first.org

cvss

[22]Tenable N. Nessus vulnerability scanner[EB

OL]. [2017-06-17]. http:

www.tenable.com

products

nessus-home

[23]Ou Xinming, Govindavajhala S, Appel A W. MulVAL: A logic-based network security analyzer[C]

Proc of the 14th USENIX Security Symp. Berkeley, CA: USENIX Association, 2005: 8-8

[24]Dimitri P, Bertsekas J N. Introduction to probability[EB

OL]. [2017-06-17]. http:

www.sciencedirect.com

science

book

9780128000410

[25]NIST. National vulnerability database[DB

OL]. [2017-06-17]. https:

nvd.nist.gov

[26]MIT Lincoln Laboratory. 2000 DARPA intrusion detection scenario specific data sets[EB

OL]. [2017-06-17]. http:

www.ll.mit.edu

ideval

data

2000data.html

[27]Hewlett-Packard. ArcSight ESM enterprise security manager[OL]. [2017-06-17]. https:

saas.hpe.com

en-us

software

siem-security-information-event-management

Hu Hao , born in 1989. PhD candidate. His main research interests include network security assessment and visual cryptography.

Liu Yuling , born in 1982. PhD. Associate professor. His main research interests include network and system security assessment and network security situation awareness.

Zhang Hongqi , born in 1962. PhD, professor. His main research interests include network security and classification protection.

Yang Yingjie , born in 1971. PhD, professor. His main research interests include security management and situation awareness.

Ye Runguo , born in 1976. PhD. Engineer. His main research interest is the big data security.

Route Prediction Method for Network Intrusion Using Absorbing Markov Chain

Hu Hao 1,3 , Liu Yuling 2 , Zhang Hongqi 1,3 , Yang Yingjie 1,3 , and Ye Runguo 4

1 ( PLA Information Engineering University , Zhengzhou 450001) 2 ( Trusted Computing and Information Assurance Laboratory , Institute of Software , Chinese Academy of Sciences , Beijing 100190) 3 ( Henan Key Laboratory of Information Security , Zhengzhou 450001) 4 ( China Electronics Standardization Institute , Beijing 100007)

Abstract Predictions of network intrusion intention and path are very significant for the security administrator to comprehend the possible threat behaviors of attackers deeply. Existing reports mainly focus on the path prediction under the ideal attack scenario. However, the ideal attack paths are not the real-world paths adopted by the intruders entirely. In order to predict the attack path information of network intrusion accurately and comprehensively, a novel route prediction method based on absorbing Markov chain (AMC) is proposed in this paper. Firstly, a normalization algorithm for state transition probability of AMC is designed with the Markov and absorption properties, then the complete attack graph (AG) proved can be mapped into the AMC. In addition, the probability metric for state transition based on common vulnerability scoring system (CVSS) is designed. Finally, the detailed steps for predicting expected number of visits to attack state and expected number of route lengths are further put forward respectively. Experimental analysis results indicate that our method can quantify the probability distribution of routes with different attack lengths, and calculate the expected number of route lengths. Moreover, it can predict the expected number of atomic attacks needed to compromise the attack goal. The predictions can be used in node threat ranking. Hence, our approach provides more guidance for network security protection in response to network attack threat timely.

Key words intrusion route prediction; attack graph (AG); absorbing Markov chains (AMC); expected route length; node threat ranking

摘要 入侵意图和路径预测对于安全管理员深入理解攻击者可能的威胁行为具有重要意义.现有研究主要集中于理想攻击场景中的路径预测，然而理想攻击路径并不都是入侵者采取的真实路径.为了准确全面地预测网络入侵的路径信息，提出基于吸收Markov链的多步攻击路径预测方法.首先利用吸收Markov链中状态转移的无后效性和吸收性设计节点状态转移概率归一化算法，并证明完整攻击图可以映射为吸收Markov链，进而给出了基于通用漏洞评分标准的状态转移概率度量方法，最后提出攻击状态节点访问次数和路径长度的期望值预测步骤流程.实例分析结果表明:该方法可以量化不同长度攻击路径的概率分布、计算路径长度的期望值、预测实现既定攻击目标所需的原子攻击次数，并对节点威胁进行排序，为及时应对网络攻击威胁提供更多安全防护指导.

关键词 入侵路径预测；攻击图；吸收Markov链；期望路径长度；节点威胁排序

基金项目： 国家重点研发计划项目(2016YFF0204002, 2016YFF0204003)；“十三五”装备预研领域基金项目(6140002020115)；CCF-启明星辰“鸿雁”科研计划基金项目(2017003)；郑州市科技领军人才项目(131PLJRC644)

This work was supported by the National Key Research and Development Program of China (2016YFF0204002, 2016YFF0204003), the Equipment Pre-research Foundation During the 13th Five-Year Plan Period (6140002020115), the CCF-Venus “Hongyan” Scientific Research Plan Foundation (2017003), and the Science and Technology Leading Talent Project of Zhengzhou (131PLJRC644).