网络入侵检测算法研究

刘海涛

摘要：网络入侵检测系统通过对网络中传输数据包的检测来判别网络中的异样数据包，是目前应用最为广泛的网络安全防范工具之一。网络入侵检测系统效率很大程度上取决于网络入侵检测算法效率。其中在Wu-Manber（WM）入侵检测算法中，设置了SHIFT、PREFIX和HASH三个表来实现多模式匹配，但是PREFIX和HASH表的功能类似，因此可以通过HASH表的改进，实现PREFIX和HASH表的融合，来减少算法空间复杂度和减少匹配比对次数，从容提高网络入侵检测算法效率。

关键词：网络安全；入侵检测；模式匹配

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2015）05-0042-02

随着信息技术的发展，人们通过网络获得极大便利的同时，网络安全由于涉及个人、企业和国家的隐私和安全，因此也受到人们极大的关注。入侵检测系统（Intrusion Detection System，IDS ）是网络安全的重要组成部分，通过对网路中传输的数据包进行检测，辨别出网络中的异样数据包，从而实现网络安全防范。入侵检测算法是入侵检测系统的核心，如何快速、准确的检测出网络中的异常数据报是入侵检测算法研究的重点。本文主要对源码开放的Snort入侵检测系统的Wu-Manber（WM）入侵检测模式匹配算法进行分析，并针对WM算法所存在的不足，对其进行改进研究。

1 模式匹配算法概述

模式匹配算法先定义一个长度为n的文本串T，然后定义一个长度为m的模式串P，如果在T中能够完全找到模式串P，则匹配成功，否则匹配失败。模式匹配算法的改进的主要方向就是减少算法的时间、空间需求。

在入侵检测系统中，随着网络带宽的不断增加，网络中数据传输速率越来越快，因此对用于检测网络传输数中异常数据包的模式匹配算法效率提出了更高的要求。如果模式匹配算法的检测速率跟不上网络传输速度，那么在进行入侵检测时会漏检大量的数据包，从而影响入侵检测算法的高效性和准确性，因此如何选择合适的模式匹配算法，对于提高入侵检测算法的检测效率和检测准确性具有非常重要的影响。

2 WM入侵检测算法简介

WM是一个典型的多模式匹配算法，是借鉴BM单模式串算法构造出来的。WM通过采用长度为B的字符块，来扩展坏字符移动规则，同时采用HASH表来BM算法匹配阶段的匹配运算模式，从而提高了匹配效率。

WM具有较高的匹配效率，非常适用于入侵检测系统中。WM算法采用哈希散列和跳跃不可能匹配的方法，来实现匹配。在WM算法中需要使用SHIFT、PREFIX和HASH三个表，并且需要对所有模式进行预处理。其中，读入字符串根据SHIFT表来决定跳跃距离，如果通过SHIFT表判断跳跃距离为0时，就需要进一步基于PREFIX表和HASH表来进行判断；PREFIX表用于存储块尾字符相同的模式传中的手快字符散列值；HASH表用于存储块尾字符散列值相同的模式串值。WM算法执行过程中，通过利用SHIFT、PREFIX和HASH表来完成字符的寻找和扫描。

在WM算法中，如果模式串数量越多，那么模式串后端相同的概率也会越大，根据WM的SHIFT表设计规则，此时模式串的移动距离也会越小，增加比较次数，降低匹配效率。

在WM执行过程中需要遵循如下的原则：

（1）如果在任何模式串中都不包括字符块B，则SHIFT[h]=m-B+1，其中m为模式串的长度，h为B的哈希值。字符串B通常取值2或者3，通过上述公式，可以计算每个块字符与匹配窗口模式串串尾的距离。

（2）如果在某些模式串中能够找到字符块B，而且字符块在模式传中出现的位置为1，则SHIFT[h]=m-1。

WM算法流程如下所示：

①将最短的模式串长度记为m；

②构建HASH表、PREFIX表和SHIFT表，分别表示为HASH[h]、PREFIX[h]和SHIFT[h]；

③如果SHIFT[h]>0，则将窗口跳跃SHIFT[h]的位置；否则，执行下一步；

④如果存在p满足： HASH[h]≤p

3 WM算法存在的不足

WM是一个效率较高的模式匹配算法，但是在入侵检测算法中，WM算法仍然存在如下的不足：

（1）当模式串数量不断增加时，那么拥有相同后缀的模式传输量也会响应增加，那么具有相同哈希值的模式串数量也会增加，从而导致同一个哈希值表项内的串联长度增加，即当确定模式串的后缀的哈希值之后，还需要通过更多次的对比。

（2）如果所有模式串中最短模式串的长度m较小，那么每次跳跃的距离会很小，影响模式串的匹配效率，对算法性能造成较大的影响。

4 WM算法的改进

通过对WM算法的分析，在WM算法中，HASH表存储了模式串后缀模式串的哈希值，而在PREFIX表中存储了模式串前缀的哈希值，从而可以看出WM算法中的HASH表和PREFIX表的功能类似，因此可以通过HASH表的改造，将其分成两个区来分别表示原HASH表和PREFIX表中的内容，取消PREFIX表。

构建改进WM算法步骤如下所示：

①记录所有模式串中最小模式串的长度为m；

②确定字符块B的大小，一般B取值为2或者3；

③构建SHIFT 表；

④构建HASH表的左右半区，其中左半区存储原WM算法的HASH表内容，右半区存储原WM算法中PREFIX表的值；

在构建好改进的WM算法之后，使用WM算法来进行入侵检测的匹配流程如下所示：

①计算模式串的SHIFT表；

②计算当前匹配模式串文本的前缀和后缀，并将前缀和后缀的哈希表值分别存储到HASH表中的左右半区中；

③基于SHIFT表对文本串进行扫描，从文本串左端第m个字符开始，整体从模式串的左匹配到右，每次扫描B个字符，如果跳跃距离大于0，则根据SHIFT表中的值后移；

④如果后缀的哈希值在HASH表的作伴去，则寻找HASH表的右半区中是否有与其完全匹配的字符串，如果有则表示模式串完全匹配文本串，如果没有则返回第③步，直到所有的文本串匹配完毕。

从改进WM算法中可以看出，改进WM算法通过将HASH表划分为左右搬去，节省了PREFIX表的构建空间，减少了算法匹配时的对比次数，有效提高了算法效率。

下面以一个具体的实例来对改进WM算法的具体应用进行介绍：

文本串：”Each of us will have a better tomorrow”，匹配字符串为hava，算法中B取值为2。改进WM算法的步骤如下所示：

①计算SHIFT表

计算文本串中每个字符块与匹配窗口内模式串串尾的距离，并且将所得到的距离作为文本中出现时的跳跃距离，SHIFT表中未出现在匹配窗口内的块字符值均为m-B+1=4-2+1=3，最终得到SHIFT表如表1所示：

表1 SHIFT表

[ha＼&av＼&ve＼&其他＼&2＼&1＼&0＼&3＼&]

②计算HASH表

在改进HASH表中的作伴去存储原算法HASH表中的值，有半区存储原算法PREFIX表中的值，最终得到HASH表如表2所示。

表2 HASH表

[ve＼&ha＼&have＼&have＼&]

③匹配过程

取B值为2，从右向左扫描文本串前端的4个字符，并且根据这4个字符的后两位来查找SHIFT表，其中ch在表1中的跳跃距离为3，则向后移动3个距离，后移距离3后的字符串为of，of在表1中的跳跃距离同样为3，依次匹配下去，知道发现ve在表1中的移动距离为0，则转入表2的左半区，查找到have，然后计算have在表2右半去的哈希值，同样也有have，则匹配串have完全匹配文本串。

5 总结

随着网络技术的不断发展，网络入侵检测已经成为了捍卫网络安全的有力武器，而网络入侵检测的效率很大程度上取决于模式匹配算法的效率。在本文的研究中主要针对Snort开源入侵检测系统中的WM多模式匹配算法所存在的问题，进行改进WM多模式匹配算法的设计。

参考文献：

[1] 兰景英，王永恒.snort研究及BM算法改进[J].计算机工程与设计.2008，29（9）：2199-2202.

[2] 张鑫， 谭建龙， 程旗. 一种改进的Wu-Manber 多关键词算法[J]. 计算机应用， 2003，23 （7）：29-31.

[3] 唐谦，张大方. 基于snort的入侵检测引擎比较分析[J].计算机工程与设计2005，26（11）：2884-2886.

[4] 王猛，王小双.snort规则匹配算法改进[J].浙江海洋学院学报：自然科学版，2007，26（2）：215-218.

[5] 马伟华，刘玉梅 ，叶飞 ，杨旭东 .一种改进的Wu-Manber多模式串匹配算法[J]. 应用科技，2007，34（10）：32-34.

[6] 崔玮， 刘建伟， 张其善. 基于snort和改进BM算法的入侵检测系统的研究与实现[J]. 2006，29（6）：144-146.