基于粒子群优化的隐马尔科夫模型的复合攻击预测方法

耿 宁

（河北师范大学数学与信息科学学院，河北石家庄050024）

随着计算机网络的应用普及，愈加复杂的网络攻击不断出现，攻击的危害性不断增强。为了确保安全，人们通常会使用入侵检测系统（IDS）等安全措施，但传统的IDS只能检测已知的攻击行为，不能识别攻击者的攻击意图，所以用户会希望根据当前与自身的网络安全状况，进一步预知可能要发生的攻击，识别其攻击意图并进行攻击预警［1］。Ming Yuh Huang在1999年研究网络入侵检测时，首次将攻击意图作为一个单独的因素来考虑，他提出的网络攻击的主动防御技术是当前网络安全领域的一个热点，本文也从攻击意图角度出发，对复合攻击预测进行研究。

1 隐马尔科夫模型

HMM适合应用在与时间序列有关的问题上［2］，已广泛应用于DNA识别、语音识别、分子生物学等领域，近年来逐渐应用到网络复合攻击预测中［3］。HMM模型就是描述观察值与隐藏状态关系的模型。首先有个有限状态集合S＝（S1，S2，…，SN），t时刻的状态为qt，状态是被隐藏的，且状态之间可以不同的概率转换，组成状态转移矩阵A，定义为ɑij＝P［qt＋1＝Sj||qt＝Si］，1≤i，j≤N，然后每个状态又可以不同的概率表现出不同的观察值，组成观察矩阵B，定义为bj（k）＝P［Ok||qt＝Sj］，其中，1≤j≤N；1≤k≤T，O＝｛O1，O2，…，OT｝为观察值集合，在初始时刻，各个状态具备不同的初始概率，定义为Pi＝P［q1＝Si］，1≤i≤N。则λ＝（A，B，P）可表示一个隐马尔科夫模型。

HMM应用于复合攻击预测中，要求系统可以用得到的观察值（报警信息）来挖掘出隐藏在其背后的的真实状态（即攻击意图），需要首先将原始报警信息进行处理，然后用攻击行为概率分布、关联规则法确定初始状态矩阵、状态转移矩阵和观察矩阵。模型中的Baumwelch算法可训练模型中的参数，本文中又引入粒子群算法进行参全局优化。最后用HMM模型中的Forward算法识别攻击场景；Viterbi算法挖掘攻击意图并预测下一步攻击。

2 相关技术的解决方法

2.1 原始报警信息的处理

原始报警信息具有很多属性，其中很多为冗余属性，因此要对其进行事件关联语义分析，对原始报警信息进行格式统一，定义为：Org Aler（ID，Type，Source-IP，Destination-IP，Start／End-Time），处理后的信息格式为：MiniAlert（ID，ID，Type，Source-IP，Destina-tion-IP，Start／End-Time，Count）。处理时把除了ID属性和起始终止时间属性不同，其他属性相同的信息视为重复报警，合并为一个报警。再基于DDos攻击考虑将原始地址不同，目的地址相同的报警信息，合并为一个报警信息，如表1、表2。

表1 原始报警信息

表2 处理后的信息

2.2 状态转移矩阵的确定

状态之间的互相转换组成状态转移矩阵A，ɑij＝P［qt＋1＝Sj||qt＝Si］表示从i状态到j状态的转移概率。而关联规则是记录在网络攻击数据库中各个攻击之间的依赖关系，如IPSweep→PortScan表示攻击者进行攻击时先进行了IPSweep然后进行了PortScan。浏览路径预测很成功地应用了关联规则［4］，借鉴其思想也可应用到攻击预测中。在复合攻击中任意两个攻击步骤intenti，intentj间的转移概率 P（intenti，intentj）可由下面的公式计算：

用上述关联规则算法，挖掘出攻击意图间的关联规则，就可计算出任意两个攻击意图间的转移概率ɑij，则得到状态转移概率矩阵A。

2.3 观察矩阵的确定

对于观察矩阵中各个状态产生的不同观察值概率的确定，在此用统计的方法来确定观察矩阵的值，假设有n个攻击事务集T＝｛t1，...，tn｝，m个攻击意图Q＝｛intent1，...intentm｝，某intentj上的报警信息集 A-lert＝｛Alert1，...Alertt｝。第i个攻击事物为：ti＝（ti［1］，...ti［f］），ti攻击事物中的每一个分量组成攻击意图的集合：intent＝｛ti［1］，...ti［f］｝，攻击者达到其意图j后，产生报警信息Alert，其中Alert∈｛A-lert1，...Alertt｝的概率为：

式中，Sij，Alert＝｛intent|intent∈Sij，intent产生报警信息Alert｝表示在集合Sij中产生报警信息Alert的攻击意图的集合，经过上述计算，可确定观察值产生概率矩阵B。

2.4 粒子群算法对模型参数的优化

由于HMM模型本身的Baum-Welch算法会使参数收敛于局部极值。而PSO算法是一种随机搜索算法，它可以在搜索空间进行全局性的搜索，因此比爬山式算法更有可能找到全局最优解。在粒子群优化算法中，每个个体被称为一个粒子。则N个粒子就组成的一个群体，每个粒子i是一个m维的向量xi（i＝1，2，…，N），第i个粒子的移动速度也是一个m维的向量，记为vi（i＝1，2，…，N）。f（x）为待优化的目标函数，粒子群的优化过程可描述为：

式中，w为惯性因子；c1和c2称为加速系数；c1和c2是介于［0，1］之间的随机数；pi（t）（i＝1，2，…N）即第i个粒子在t时刻搜索到的最优位置，代表此时的极值，pg（t）为整个粒子群迄今为止搜索到的最优位置（全局极值）。在PSO-HMM算法的HMM参数优化中，每一个粒子对应一个HMM，粒子在每一次迭代进化后都运行Baum-welch算法对粒子进行局部的优化。算法中的粒子适应度Fitness则是用Viterbi算法计算HMM在当前粒子状态数下的最终输入出概率得到，如表3。

表3 PSO-HMM对HMM参数的优化

2.5 Forward和Viterbi算法介绍

2.5.1 Forward算法步骤如下：

（1）初始化

ɑ1（i）＝pibi（o1），1≤i≤N，pi为t＝1时的初始概率，且pi＝p（qi＝si）。

（2）迭代计算

式中，1≤t≤T-1，1≤j≤N；ɑij＝p（qt＋1＝sj|qt＝si）为状态转移概率；bj（ot）为在观察值ot状态下产生的概率值，bj（ot）＝p（ot|qt＝si）。

（3）终止条件

式中，λ为给定的HMM模型；O为观察序列，O＝｛O1，O2，...，OK｝。

2.5.2 Viterbi算法描述如下：

（1）初始化

δ1（i）＝πibi（O1）＿1≤i≤N，Ψ1（i）＝0

（2）迭代计算

（3）终止条件

（4）求解最佳路径

3 仿真实验与分析

实验中，以美国麻省理工学院林肯实验室提供的DARPA2000［5］作为报警信息源，建立两个复合攻击的隐马尔科夫模型攻击场景，DDoS和FTP Bounce。当收到报警信息“ICMP Echo Reply”和“RPC portmap Sadmind request UDP”时，根据隐马尔科夫模型的Forward算法分别求出两个攻击场景产生此报警信息的概率，见表4。由表4可见，无论是优化前还是优化后都有P（A-lert|DDoS＿HMM）＞P（Alert|FTP Bounce＿HMM），即此时发生的攻击可基本定为DDoS复合攻击，且优化后的P（Alert|DDoS＿HMM）与P（Alert|FTP Bounce＿HMM）的区分差值更明显，即说明优化后能更好地识别攻击场景。收到报警信息序列｛Alert1，Alert2，Alert3｝后，再根据Viterbi算法算出当前已完成的攻击序列为IPSweep和SadmindPing，则下一步要进行的攻击意图预测为SadmindExploit。至此，本实验成功模拟了一次复合攻击的判断预测过程。

表4 报警信息概率对比表

两个攻击场景的初始状态矩阵、状态转移矩阵、观察矩阵参数如矩阵1～3所示：

矩阵1（初始状态矩阵）

矩阵2（状态转移矩阵）

矩阵3（观察矩阵）

4 结束语

本文在当前网络攻击日趋复杂的背景下，提出将复合攻击、攻击意图、粒子群算法和隐马尔科夫模型结合在一起，作为一种基于隐马尔科夫模型的网络攻击预警技术。通过仿真实验，实现了对复合攻击行为的识别和预测工作，充分验证了此方法的有效性。本实验是基于粒子群优化的，则理论上粒子数越多，即攻击场景越多，优化效果就越明显，这也是本实验需要改进的地方，在实际应用中当攻击场景增长后理论上会有更好的效果。

［1］ 张松红，王亚弟，韩继红.基于隐马尔科夫的网络安全预警技术研究［D］.郑州：解放军信息工程大学硕士论文，2007.

［2］ Rabiner L R.A Tutorial on Hidden Markov Models and Selected Application in Speech Recognition［J］.Proceedings of the IEEE，1989，77（2）：257-285.

［3］ Ourston D，Matzner S，Stump W，etɑl.Application of Hidden Markov Models to Detecting Multi＿stage Network Attacks［C］／／Proceedings of the 36th Hawaii International Conference on System Sciences.Hawaii：［s.n.］，2003.

［4］ 金民锁，刘红祥，王 佐.基于隐马尔科夫模型的浏览路径预测［J］.黑龙江科技学院学报，2005，15（3）：167-170.

［5］ LLS＿DDOS＿l.0［EB／OL］.http：www.ll.mit.edu／IST／ideval／data／2000／LLS＿DDOS＿1.0.html.Markov Models.In Proeeedings of the Eurospeech＇95.Madrid，1995：1487-1490.