计算机应用   2017, Vol. 37 Issue (5): 1331-1334  DOI: 10.11772/j.issn.1001-9081.2017.05.1331
0

引用本文 

李方伟, 李骐, 朱江. 改进的基于隐马尔可夫模型的态势评估方法[J]. 计算机应用, 2017, 37(5): 1331-1334.DOI: 10.11772/j.issn.1001-9081.2017.05.1331.
LI Fangwei, LI Qi, ZHU Jiang. Improved method of situation assessment method based on hidden Markov model[J]. Journal of Computer Applications, 2017, 37(5): 1331-1334. DOI: 10.11772/j.issn.1001-9081.2017.05.1331.

基金项目

国家自然科学基金资助项目(61271260);重庆市科委自然科学基金项目(cstc2015jcyjA40050)

通信作者

李骐,电子邮箱 airforceli@vip.qq.com

作者简介

李方伟 (1960-), 男, 重庆人, 教授, 博士, 主要研究方向:移动通信技术与理论、信息安全;
李骐 (1990-), 男, 湖北武汉人, 硕士研究生, 主要研究方向:网络安全态势感知;
朱江 (1977-), 男, 湖北荆州人, 副教授, 博士, 主要研究方向:通信理论与技术、信息安全

文章历史

收稿日期:2016-11-01
修回日期:2016-12-05
改进的基于隐马尔可夫模型的态势评估方法
李方伟, 李骐, 朱江    
重庆市移动通信重点实验室 (重庆邮电大学), 重庆 400065
摘要: 针对隐马尔可夫模型(HMM)参数难以配置的问题,提出一种改进的基于隐马尔可夫模型的态势评估方法,更加准确地反映网络的安全态势。所提方法以入侵检测系统的输出作为输入,根据Snort手册将报警事件分类,得到观测序列,建立HMM,将改进的模拟退火(SA)算法与Bauw_Welch(BW)算法相结合对HMM参数进行优化,使用量化分析的方法得到网络的安全态势值。实验结果表明,所提方法能较好地提升模型的精度与收敛速度。
关键词: 网络安全    隐马尔可夫模型    参数优化    模拟退火算法    态势评估    
Improved method of situation assessment method based on hidden Markov model
LI Fangwei, LI Qi, ZHU Jiang     
Chongqing Key Laboratory of Mobile Communications Technology (Chongqing University of Posts and Telecommunications), Chongqing 400065, China
Abstract: Concerning the problem that the Hidden Markov Model (HMM) parameters are difficult to configure, an improved method of situation assessment based on HMM was proposed to reflect the security of the network. The proposed method used the output of intrusion detection system as input, classified the alarm events by Snort manual to get the observation sequence, and established the HMM model, the improved Simulated Annealing (SA) algorithm combined with the Baum_Welch (BW) algorithm to optimize the HMM parameters, and used the method of quantitative analysis to get the security situational value of the network. The experimental results show that the proposed method can improve the accuracy and convergence speed of the model.
Key words: network security    Hidden Markov Model (HMM)    parameter optimization    Simulated Annealing (SA) algorithm    situation assessment    
0 引言

根据2015年1月中国互联网信息中心 (CNNIC) 发布的《第35次中国互联网发展状况报告》显示,截止2014年12月底,我国总体网民中有46.3%的网民遭遇过网络安全问题,我国个人互联网使用的安全状况不容乐观。随着网络安全问题日益突出与严重,一些传统的安全防御技术已力不从心。在这种背景下,一种能够实时反映网络安全状态的方法具有重要研究价值。

Endsley[1]首先提出了态势感知的概念,Bass[2]将其运用到网络安全领域。国内方面陈秀真等[3]提出了层次化的网络安全态势评估模型,模型从局域网系统、主机、服务3个层次进行安全威胁态势评估,反映安全动态,管理员可以从安全动态曲线中调整相应的防范策略,提高系统的安全性;李伟生等[4]根据态势与安全事件之间的潜在关系建立贝叶斯网络评估模型,并阐述了相应的信息传播算法,最后以一个例子介绍了贝叶斯网络的计算过程;国外方面,Rahnavard等[5]将网络服务异常检测的过程转化为隐马尔可夫过程,并通过数据测试显示该模型对网络服务异常具有很好的识别率;Rnes等[6]提出了基于隐马尔可夫模型 (Hidden Markov Model, HMM) 网络风险态势评估方法,通过入侵检测系统 (Intrusion Detection System, IDS) 报警序列建模,得到每个主机处在不同安全状态下的概率,从而得到每个主机的安全风险值,进而累加得到整个网络的安全风险值。以上研究在网络安全态势评估方面具有各自优势,但也存在一些不足:一是HMM观测矩阵规模的问题,二是HMM参数配置的问题。

为了进一步完善网络安全评估模型,本文提出一种改进的基于HMM的态势评估方法,通过将报警事件分类,解决观测矩阵规模过大的问题;充分利用模拟退火 (Simulated Annealing, SA) 算法概率突跳特性,解决参数难以配置的问题。然后对主机、网络进行态势评估,绘制各个主机及整个网络的安全态势图,直观反映了主机、网络的安全动态及变化规律,可供管理员参考,提供了决策依据。最后采用一阶灰色模型GM (1, 1)[7]及自回归滑动平均 (Auto-Regressive and Moving Average, ARMA) 模型[8]对主机的安全态势进行预测与实际值进行比较。

1 系统模型

隐马尔可夫模型是一种统计模型[9],用来描述一个含有隐含未知参数的马尔可夫过程。

隐马尔可夫模型由5部分组成:

1) 主机的状态空间。设主机有M种不同的安全状态,对应的集合表示为S={S1, S2, …, SM},qt表示Markov链在t时刻所处的状态,则qt∈(S1, S2, …, SM)。

2) 观测序列的观测值。设有N种报警事件,则观测值集合为O={O1, O2, …, ON},Vt表示在t时刻观测到的观测值,则Vt∈(O1, O2, …, ON)。

3) 主机的初始状态分布。表示主机所处的初始状态,记π=(πi)i=1, 2, …, M,其中πi=P(q1=Si)(1≤iM),表示初始时刻系统处于状态Si的概率为πi

4) 主机的状态转移矩阵。主机处在不同安全状态相互转移的概率,记A=(aij)M×M,其中aij=p(qt+1=j|qt=i)(ij=1, 2, …, M),表示系统在t时刻处于状态i,在下一时刻转移到状态j的概率。

5) 观测值概率密度矩阵。表示观测到某个观测值系统处于某种状态的概率,记B=(bik)M×N,其中bik=P(Vt=Ok|qt=Si)(1≤iM, 1≤kN),表示系统处于状态Si,观测值Ok出现的概率,与所处的观测时间无关。

因此,网络安全态势评估模型可以用λ={M, N, π, A, B}来表示,简记为λ=(πAB)。

2 改进优化HMM参数的算法 2.1 改进思路

“前向-后向”算法[10]的参数学习过程是不断更新HMM的参数,从而使P(O|λ) 最大,其中$ P\left( {O\left| \lambda \right.} \right){\rm{ = }}\sum\limits_{i{\rm{ = 1}}}^N {{a_t}\left( i \right)} {\beta _t}\left( i \right) $

更新参数步骤如下:

$ \mathit{\boldsymbol{\bar \pi }} = {\gamma _1}\left( i \right) $ (1)
$ {\bar A_{ij}} = \frac{{\sum\limits_{t = 1}^{T-1} {{\varepsilon _t}\left( {i, j} \right)} }}{{\sum\limits_{t = 1}^{T-1} {{\gamma _t}(i)} }};1 \le i, j \le M $ (2)
$ {\bar B_{ik}} = \frac{{\sum\limits_{t = 1{\rm{, s}}{\rm{.t}}{\rm{.}}{{{v}}_t} = {O_{{k}}}}^T {{\gamma _t}\left( i \right)} }}{{\sum\limits_{t = 1}^T {{\gamma _t}(i)} }};1 \le i \le M, 1 \le k \le N $ (3)

更新后的参数($ \mathit{\boldsymbol{\lambda }} = \mathit{\boldsymbol{\overline \pi }}, \overline {\mathit{\boldsymbol{A, }}} \mathit{\boldsymbol{\overline B}} $),Baum已经证明了P(O|λ)>P(O|λ), 表示在多次迭代后可以得到HMM的一个最大似然估计,但该训练方法容易陷入局部最优。因此,本文提出了改进HMM参数优化的方法。由于在HMM中,参数B的改变对目标函数P(O|λ) 的影响起着至关重要的作用,而参数π和参数A对目标函数P(O|λ) 的影响几乎可以忽略[11]。因此,在训练过程中,应对参数B的取值进行扰动。此外,HMM参数更新的过程是一个多次迭代的过程,对参数B的改变将引起向前-向后变量的改变,从而也实现了对参数A的改变,避免了容易陷入局部最优的问题。

2.2 模拟退火算法的改进

基于改进的模拟退火 (SA) 的HMM参数优化算法 (HMM_SA) 具体步骤如下:

Initialization:初始化模型参数π, A, B,退火初始温度T0,温度冷却系数k,终止温度Tend

步骤1  设置收敛条件χ(如χ=-10-3)。

步骤2  设置降温函数:Tm+1=kTm, m=m+1, k < 1。

步骤3  产生M×N个相互独立满足正态分布的随机变量y,其期望为0,方差为eTm-1,令b′ik=bik+y, 1≤iM, 1≤kN,若b′ik < 0,则令b′ik=0。

步骤4  归一化处理${b_{ik}} = {b'_{ik}}/\sum\limits_{k = 1}^M {{{b'}_{ik}}} $

步骤5  判断P(O|λ) 是否满足收敛条件或满足终止温度:如果满足,则算法结束,取当前P(O|λ) 为最优解;否则转步骤2。

2.3 算法可行性

对于一个算法是否可行,即它是否能在有限的时间内收敛或者达到预期的精度。

对于算法能否在有限时间收敛的问题,由于模拟退火算法具有随机性,转为讨论其渐进收敛性,根据Mapkob理论可以证明[12]:对于优化解,一般可以较快搜索到该邻域的最优解,优化终止;对于恶化解,随着T值的衰减,exp (-Δf/T) 趋近于无穷,故T衰减到一定程度时不再接受。因此,该算法必定会在有限时间内出现解在连续N个步长内不再改变的情况,故算法从概率的角度是渐进收敛的。

2.4 安全态势量化方法

上文定义了网络中的每台主机具有M种状态,根据主机的损害程度,定义4种状态,记为S={1, 2, 3, 4},随着数值的增大,主机风险程度越大。如果能够判断主机处于何种状态,那么就可以定量分析主机的安全态势值。引入态势权值向量C={C1, C2, C3, C4}, 与主机可能处于的4种状态一一对应,根据不同网络,态势权值向量可适当配置。

t时刻主机处于Si的概率γt(i),公式如下:

$ {\gamma _t}\left( i \right) = P\left( {{q_t} = {s_i}|O, \mathit{\boldsymbol{\lambda }}} \right) = \frac{{{\alpha _t}\left( i \right){\beta _t}\left( i \right)}}{{P\left( {O|\mathit{\boldsymbol{\lambda }}} \right)}} = \frac{{{\alpha _t}\left( i \right){\beta _t}\left( i \right)}}{{\sum\limits_{i = 1}^N {{\alpha _t}\left( i \right){\beta _t}\left( i \right)} }} $ (4)

其中:前向变量αt(i)=P(O1O2Ot, qt=si|λ),后向变量βt(i)=P(Ot+1Ot+2OT, qT=si|λ),则主机的安全态势值可以按照式 (5) 去计算:

$ R{\rm{ = }}\sum\limits_{i = 1}^M {{r_i}{c_i}} $ (5)

知道了单个主机的安全态势值,假设网络中有L台主机,就可得到整个网络的安全态势值:

$ {R_{{\rm{all}}}} = \sum\limits_{i = 1}^L {{R_i}} $ (6)

整个隐马尔可夫模型 (HMM) 态势评估模型总流程如图 1所示。

图 1 改进的HMM态势评估流程 Figure 1 Process diagram of the improved HMM situation assessment
3 实验结果及数据分析

本文运用两种优化算法对模型进行训练,其计算复杂度比较结果如表 1所示。其中:M为隐马尔可夫模型的主机状态数,D为问题维度,gmax为最大迭代次数。由表可知,虽然改进后的优化算法复杂度有所增加 (这是由于引入了扰动矩阵,它可以使算法跳出局部最优,得到更好的优化结果),但提高了模型的精度和运算效率。

表 1 各算法计算复杂度比较 Table 1 Computational complexity of each algorithm
3.1 数据描述

本文数据使用某安全公司的防火墙日志,总共5天,4台主机,总共783个报警事件。选取2013年11月05日当天,3台比较有代表性的主机,分别为IP地址为172.17.5.25、172.17.5.31、172.17.5.46的主机,共245个报警事件作为数据来研究。

如果直接将报警事件进行输入建模,那么观测概率矩阵B的规模太大、复杂度太大、计算量大、运行时间较长,故需要将报警事件进行分类处理。采用Snort[13-14]来检测防火墙日志,观测序列的种类一共有37种,按威胁程度分成3类,用数字1、2、3来表示,分别表示低、中、高3个等级的威胁程度,表 2是从该手册摘录的一部分攻击类型及其对应的威胁程度。

表 2 Snort手册部分攻击类型及威胁程度 Table 2 Some attack types and their threat levels in Snort handbook
3.2 滑动窗口

由于Bauw_Welch (BW) 算法是一个循环迭代的算法,在实际应用时,观测序列的长度随时间不断增加,如果每次训练都从观测序列首部开始,会计算许多重复部分,从而浪费训练时间,模型也不能实时评估。引用滑动窗口机制能很好地解决以上问题,将观测序列划分为长度为τ的滑动窗口短序列,每训练一个滑动窗口短序列向后移动一位,直到将整个观测序列训练完。这样不仅降低了算法的复杂度,也提高了训练效率。

3.3 参数设置与优化

2.4节中确定了系统的4种状态,状态集合S={1, 2, 3, 4},对应的四种状态分别为Good (良好),Probed (被刺探)、Attacked (被攻击)、Compromised (已侵入)。实验中:Markov链的状态数M=4,观测值类型N=3,观测序列长度t=20,初始参数λ0={π0, A0, B0},根据专家经验,具体取值如下:

π0=(0.7, 0.1, 0.1, 0.1)

$ {\mathit{\boldsymbol{A}}_{\rm{0}}}{\rm{ = }}\left[{\begin{array}{*{20}{c}} {0.8} & {0.1} & {0.07} & {0.03}\\ {0.1} & {0.8} & {0.06} & {0.04}\\ {0.07} & {0.05} & {0.85} & {0.03}\\ {0.03} & {0.05} & {0.07} & {0.85} \end{array}} \right] $B0均匀设置。

为了避免计算中出现“下溢”问题,对P(O|λ) 采用对数化处理,即lg P(O|λ)。

选取IP地址为172.17.5.25的主机为例子分别使用BW算法和HMM_SA算法进行训练,结果如图 2所示。

图 2 不同算法的参数似然值变化情况 Figure 2 Parameter likelihood changes of different algorithms

图 2可知:由于模型参数设置的问题,导致模型的参数似然值较低,不能通过观测序列准确推断主机所处的安全状态; 随着模型经过两种算法训练后,模型的参数似然值得到显著提升,优化后的模型能够更加准确描述报警事件与主机所处安全状态的关系,使模型的评估效果更好。同时使用BW算法进行参数估计时,需经历94次重复迭代,参数似然值才达到收敛,而使用HMM_SA算法时,只需65次就收敛了,而且收敛时的参数似然值更大,表明训练完的模型更加精确。此时,HMM_SA算法的优化能力就得以体现。

观测序列长度t=25,取滑动窗口长度为τ=15,对IP地址为172.17.5.25的主机参数的优化结果如下:

π′=(0, 0, 1, 0)

$ {\mathit{\boldsymbol{A}}^{\bf{'}}}{\rm{ = }}\left[{\begin{array}{*{20}{c}} {0.6432} & {0.1897} & {0.1325} & {0.0346}\\ {0.0564} & {0.8128} & {0.1213} & {0.0095}\\ {0.0354} & {0.0265} & {0.8112} & {0.1269}\\ {0.0421} & {0.0339} & {0.0698} & {0.8542} \end{array}} \right] $
$ {\mathit{\boldsymbol{B}}^{\bf{'}}}{\rm{ = }}\left[{\begin{array}{*{20}{c}} {0.8532} & {0.0921} & {0.0547}\\ {\begin{array}{*{20}{c}} {0.6732}\\ 0 \end{array}} & {\begin{array}{*{20}{c}} {0.2456}\\ {0.7532} \end{array}} & {\begin{array}{*{20}{c}} {0.0812}\\ {0.2468} \end{array}}\\ 0 & {0.3422} & {0.6578} \end{array}} \right] $

通过优化结果可得:优化后的初始状态分布π′处于被攻击的状态收敛于1,通过查找防火墙日志,得知11月5日的第一条日志内容为“Web服务远程SQL注入攻击”,与事实相符,表明该方法有效。其余两台主机得到的实验结果也与事实相符,不再依次描述。

3.4 实验结果分析

设置态势权值向量C=(0.1, 0.4, 0.7, 1),分别表示处于良好、被刺探、被攻击、已侵入状态下的态势权值。为了方便画图,网络安全态势值是以每个小时为单位计算的,每个小时内发生的多次报警事件的网络安全态势值合并为一个值。

汇总所有24 h的态势值之后,得到3台主机和整个网络2013年11月05日当天共245个报警事件的安全态势走势图。通过该图能够直观看出每个时段主机和网络的安全动态,可供管理员参考,提供决策依据。按小时加权后的主机安全态势如图 3所示。

图 3 3台主机24 h的安全态势 Figure 3 Security situation of the 3 host in 24 hours

通过图 3可以看出,主机IP地址为172.17.5.25的主机受到攻击的时段为中午11点~下午3点和晚上6点~晚上10点,这两个时段相对于其他时段态势值突增,需要引起注意,事实上中午11点~下午3点这段时间主机受到了“Web服务远程SQL注入攻击”,晚上6点~晚上10点这段时间主机受到了“Windows系统下MSSQL Slammer蠕虫攻击”;主机IP地址为172.17.5.25的主机受到攻击的时段为早上6点到中午11点,该时段的态势值明显增加,事实上该时段主机受到了“SYN-Flood半开TCP连接淹没拒绝服务攻击”;主机IP地址为172.17.5.46的主机整天的态势相对较低,曲线较为平稳,只是在下午3到晚上8点态势值曲线有异动,事实上,该时段主机“Windows系统远程管理工具PcAnywhere远程登录失败”。

然后,针对主机IP地址为172.17.5.25的主机,以前14小时的数据为基础对后10个小时的数据进行预测,按照引言介绍的2种预测模型,并对得到的预测结果进行绘图,得到的主机安全态势预测曲线如图 4所示。

图 4 主机安全态势预测曲线 Figure 4 Host security situation prediction curre

通过图 4可以看出,2种模型的预测结果都是安全态势先波段上升然后回落最后趋于平稳,GM (1, 1) 预测模型算法简单、易于实现,预测结果能比较平滑地反映主机安全态势走势,但预测精度不高,因此适用总体趋势的预测;ARMA预测模型较为复杂,但能准确反映主机安全态势走势,且误差较小,适用范围更广。

最后将3台主机的态势值相加得到整个网络的安全态势图如图 5所示。

图 5 网络24 h的安全态势 Figure 5 Security situation of the network in 24 hours

通过图 5可以看出整个网络的安全态势走势,在时段早上7点~早上10点、中午12点~下午2点、下午5点~晚上9点网络的安全态势值最高,需要引起注意。

综上所述,实验结果基本反映出主机跟整个网络的安全态势情况,证明本文提出的态势评估方法有效。

4 结语

针对隐马尔可夫模型观测矩阵规模过大和参数难配置的问题,本文提出一种改进的基于隐马尔可夫模型的态势评估方法。在传统BW算法的基础上结合改进的模拟退火算法,使局部最优解能概率性地跳出并最终趋于全局最优解,使评估模型更加精确。通过实验数据的测试,该模型能够较为准确地反映网络的安全态势,证明了该方法的有效性。另一方面,单一的报警数据可能存在较大误报和漏报,这将是未来的研究方向。

参考文献
[1] ENDSLEY M R. Situation Awareness Global Assessment Technique (SAGAT)[C]//Proceedings of the IEEE 1988 National Aerospace and Electronics Conference. Piscataway, NJ:IEEE, 1988:789-795.
[2] BASS T. Intrusion detection systems & multisensor data fusion:creating cyberspace situational awareness[J]. Communications of the ACM, 1999, 43(4): 99-105.
[3] 陈秀真, 郑庆华, 管晓宏, 等. 层次化网络安全威胁态势量化评估方法[J]. 软件学报, 2006, 17(4): 885-897. ( CHEN X Z, ZHENG Q H, GUANG X H, et al. Quantitative hierarchical threat evaluation model for network security[J]. Journal of Software, 2006, 17(4): 885-897. )
[4] 李伟生, 王宝树. 基于贝叶斯网络的态势评估[J]. 系统工程与电子技术, 2003, 25(4): 480-483. ( LI W S, WANG B S. Situation assessment based on Bayesian networks[J]. Systems Engineering and Electronics, 2003, 25(4): 480-483. )
[5] RAHNAVARD G, NAJJAR M S A, TAHERIFAR S. A method to evaluate Web services anomaly detection using hidden Markov models[C]//Proceedings of the 2010 International Conference on Computer Applications and Industrial Electronics. Piscataway, NJ:IEEE, 2010:261-265.
[6] RNES A, VALEUR F, VIGNA G, et al. Using hidden Markov models to evaluate the risks of intrusions[C]//Proceedings of the 9th International Conference on Recent Advances in Intrusion Detection. Berlin:Springer-Verlag, 2006:145-164.
[7] 邓聚龙. 灰预测与灰决策:灰色预测与决策[M]. 武汉: 华中科技大学出版社, 2002 : 173 -212. ( DENG J L. Gray Prediction and Gray Decision:Gray Prediction and Gray Decision[M]. Wuhan: Huazhong University of Science and Technology Press, 2002 : 173 -212. )
[8] BOX G E P, JENKINS G M, REINSEL G C. Time Series Analysis[M]. NJ: John Wiley & Sons, 2013 : 137 -191.
[9] DUGAD R, DESAI U B. A tutorial on hidden Markov models[J]. Proceedings of the IEEE:Applications in Speech Recognition, 2000, 77(2): 25-286.
[10] 周东清, 张海锋, 张绍武, 等. 基于HMM的分布式拒绝服务攻击检测方法[J]. Journal of Computer Research & Development, 2005, 42(9): 1594-1599. ( ZHOU D Q, ZHANG H F, ZHANG S W, et al. A DDoS attack detection method based on hidden Markov model[J]. Journal of Computer Research & Development, 2005, 42(9): 1594-1599. )
[11] JUANG B H, RABINER L R. A probabilistic distance measure for hidden Markov models[J]. AT & T Technical Journal, 1985, 64(2): 391-408.
[12] 康立山, 谢云, 尤矢勇, 等. 非数值并行算法-模拟退火算法[M]. 北京: 科学出版社, 1994 : 56 -59. ( KANG L S, XIE Y, YOU S Y, et al. Numerical Parallel Algorithm-Simulated Annealing Algorithm[M]. Beijing: Science Press, 1994 : 56 -59. )
[13] ROESCH M, GREEN C. Snort users manual[EB/OL].[2016-05-20].http://manual.snort.org/snort_manual.htlm
[14] 李晓芳, 姚远. 入侵检测工具Snort的研究与使用[J]. 计算机应用与软件, 2006, 23(3): 123-124. ( LI X F, YAO Y. Master and use Snort tools for intrusion detection[J]. Computer Applications and Software, 2006, 23(3): 123-124. )