提高Snort规则匹配速度新方法的研究与实现

曾传璜，黄侃

江西理工大学信息工程学院，江西赣州 341000

提高Snort规则匹配速度新方法的研究与实现

曾传璜，黄侃

江西理工大学信息工程学院，江西赣州 341000

ZENG Chuanhuang,HUANG Kan.Research and implementation of new method on increasing speed of rule-matching in Snort.Computer Engineering and Applications,2014,50（22）：102-105.

1 引言

随着网络技术的不断发展，网络安全问题在互联网中越来越严峻，入侵检测系统（Network Intrusion Detection System，NIDS）在网络安全扮演着越来越重要的角色，并且已经被广泛应用于各种网络环境中。Snort[1]是一个开源的、具有高匹配精确度的网络入侵检测系统。对于每一种入侵行为，Snort系统按照检测规则[2]，将捕获的数据包与检测规则进行匹配，若匹配成功，则认为构成入侵行为，将数据包信息反馈出来。

2 提高Snort规则匹配速度

改进Snort系统使用的BM[3]算法（或BM改进算法），能够有效提高Snort规则匹配速度，下面介绍BM及BM改进算法。

2.1 BM算法

1977年，Boyer和Moore提出了BM算法（Boyer-Moore）。BM算法的基本思想：采用两种启发式方法：坏字符启发式方法（Badchar）好后缀启发式方法（Goodsuffix）。

坏字符启发式方法（Badchar）：算法在匹配过程中，若某个字符x不匹配：（1）如果字符x在模式串P中没有出现，那么移动至x字符之后。（2）如果x在模式串P中出现，则移动至与x字符对齐进行再匹配。

好后缀启发式方法（Goodsuffix）：若发现某个字符不匹配的同时，但有部份字符匹配，利用已经匹配成功的部份最长子串，将模式串中的匹配最长前缀或后缀字符串的相应位置对齐。

两种方法都产生了一个移动距离，BM算法取较大的一个作为移动距离。BM算法是继BF算法和KMP算法之后提出的，相比BF算法和KMP算法，是一种具有较高匹配效率的算法，可以达到接近线性的时间复杂度。但是在实际应用中，badchar函数应用次数远远超过goodsuffix函数，goodsuffix函数将会制约BM算法的效率。

2.2 BMH算法

1980年，Horspool提出改进的BM算法，即BMH算法[4]。Horspool指出，在实际应用中，badchar函数应用的次数远远超过goodsuffix函数，因此badchar函数起主导作用；BMH算法只考虑badchar函数，在实际应用中也取得显著效果。BMH算法舍弃了难以理解又较难实现的goodsuffix函数，只考虑badchar函数，有效提高了算法的效率，而且理论上能够达到与BM算法相同的时间复杂度。

2.3 BMHS算法

1990年，在BMH算法的基础上，Sunday提出了改进的BMHS算法[5]（Boyer-Moore-Horspool-Sunday），其主要改进思想是：计算badchar函数时，考虑模式串最后一位字符对应的文本串字符在模式串中出现的情况，即利用下一个字符来决定移动距离。具体匹配过程如图1和图2所示。表1演示了BMHS算法的移动过程。BMHS算法是在BM算法和BMH算法的基础上改进的，通常情况下，BMHS算法效率是最高的，匹配速度是最快的，只有当T[k+1]字符出现在模式串P中时，算法效率不如BMH算法。

图1 T[k+1]出现在P中时移动情况

图2 T[k+1]不出现在P中时移动情况

3 改进的BM算法

3.1 算法改进的思路

改进BM算法，可以从以下三个方面思考：

（1）增大窗口移动的最大距离。BM算法、BMH算法、BMHS算法及其他一些改进算法，当首次匹配失败时，窗口即要移动一个最大距离；按照字符等概率原则，在实际情况下，移动一个最大距离的概率是比较高的，因此，增大窗口移动的最大距离，能够有效提高算法的效率。

（2）保证移动最大的安全距离。当匹配失败时，模式串能否移动一个最大的安全距离是算法改进成功与否的关键因素。提高算法性能，尽可能地保证匹配失败时每一次都能够移动最大安全距离，就能够有效减少字符比较次数，提高模式匹配的效率。本方法综合考虑多种情况，尽量保证算法在匹配过程中能够移动一个最大的安全距离。

（3）BMN[6]算法思想的启发。BMN算法是在匹配失败时，考虑模式串P最右端字符对应文本串T中的字符，将此字符与文本串T中的前一字字符和后一个字符组合，分析双字符组合在P中的出现情况来决定右移距离。本文受BMN算法启发，采用双字符序列检测方法，并结合BMH算法，提出了一种改进的BM算法。双字符[7]序列检测法，即在匹配过程中，将两个字符结合为一个整体，与模式串先匹配，以减少模式串与字符串的比较次数，增大窗口移动的最大距离的一种方法。在本方法中，窗口向右移动的最大距离将达到m+2。

3.2 改进算法的基本思想

综合考虑以上三个方面，提出一种改进的BM算法。该算法采用双字符序列检测法。首先利用BMH算法确定出一个位移量skip1，继而将T[k+1]T[k+2]组合，分为两种情况讨论，计算出另一个位移量skip2，再与skip1相比，最后确定移动距离，算法实现过程中，尽量确保匹配窗口移动最大的安全距离。实验验证，模式匹配过程中，出现此方法最大位移的概率较高，且此方法能够提高算法效率。该算法的最大的移动距离可以达到m+2。

首先设立一个数组G[8]，数组G用来标记模式串中

表1 BMHS算法移动过程

该算法的核心思想描述如下：当T[i+j]≠P[i]时，表示这一轮匹配失败，首先利用模式串P中最右端字符所对应该的文本串字符T[k]在P中的出现情况，根据BMH算法，记录下此时应该移动的距离，倘若T[k]字符未出现在模式串P中，则可移动距离为skip1=m，若T[k]出现在模式串P中，则计算出可移动新的移动距离skip1，可以肯定此时skip1≤m；继而将T[k+1]T[k+2]结合为一个组合，记为H(y)，将H(y)与模式串P进行匹配，分为以下几种情况讨论：

（1）若P中没有与字符组合H(y)匹配的字符组合时，将H(y)与模式串P的首字符P[1]进行比对，若H(y)中不含P[1]，可以确定，将模式串移动什么位置与H(y)对齐，都不会匹配，skip2的值为m+2；若H(y)含有P[1]，需分两种情况讨论：T[k+1]=P[1]，skip2的值为m+2，T[k+2]=P[1]，skip2的值为m+1。

（2）若P中有与H(y)匹配的字符组合时，分为以下两种情况讨论：

①H(y)不含模式串P的首字符P[1]，考虑已匹配字符T[k]的G(x)值，若G(x)=1，说明字符T[k]只在模式串P最后出现一次且只一次，不管将模式串移动多少位置与H(y)对齐，也不会匹配，skip2为m+2。

②考虑T[k]字符的G(x)值，若G(x)=0，则需要根据H(y)计算出应该移动的距离，产生一个新的skip2值，与skip1进行对比，若skip1＞skip2，则移动skip1；若skip1＜skip2，则移动skip2；若skip1=skip2，则移动skip1。

算法在实现过程中需构造一个单字符检测表skip1和一个双字符序列检测表skip2，skip1主要用于算法的第一步，利用BMH算法思想计算出的位移值skip1，skip2为|Σ|×|Σ|的二维表结构，用于与模式串P进行匹配对比，具体公式如下：每个字符出现的次数，数组G有利于算法的实现，在匹配过程中减少不必要的匹配，增大最大距离出现的概率。如下所示：

双字符序列检测表skip2记录文本串字符T[k+1]T[k+2]在模式串中的存在情况，若在模式串中存在，skip2的值为1；若不存在，skip2的值为0。

算法伪代码如下：

3.3 BM改进算法实例

以2.3节中的BMHS算法实例中的文本串T和模式串P进行匹配：

（1）第一次比较：P[6]=h与T[6]=h匹配，P[5]=c与T[5]=a不匹配，此时T[6]=h，G（h）=1，skip1=6；组合字符H（y）=”wh”，模式串P中没有与H（y）中相匹配的字符，且不含首字符”s”，skip2=8。skip2＞skip1，移动距离为8。

（2）第二次比较：P[6]=h与T[6]=h匹配，P[5]=c与T[5]=r不匹配，此时T[6]=h，G（h）=1，skip1=6；组合字符H（y）=”ch”，与模式串P有相匹配字符已匹配字符”h”的G（h）=1，且不含首字符”s”，skip2=8。skip2＞skip1，移动距离为8。

（3）第三次比较：P[6]=h与T[6]=d不匹配，字符”d”未出现模式串中，skip1=6；组合字符H（y）=”er”，在模式串没有匹配字符，且不含首字符”s”，skip2=8。skip2＞skip1，移动距离为8。

表2 改进的BM算法移动过程

（4）第四次比较：匹配按照P[6]，T[6]，P[5]，T[5]，P[4]，T[4]，P[3]，T[3]，P[2]，T[2]，P[1]，T[1]顺序进行，匹配成功。

在上述比较过程中，窗口移动次数为4次，匹配次数也有所减少，该算法效率较BMHS算法有所增加。

4 算法的性能测试及结果分析

构造双字符序检测跳跃表skip2将产生的二维空间，使算法的时间复杂度为平方阶层O(Σ2)，算法的预处理时间复杂度为O(Σ2)，空间复杂度为O(Σ)。考虑窗口移动最大距离和移动较大距离的概率对算法的影响，最好情况下的时间复杂度能够接近亚线性阶层，最坏情况下时间复杂度为O(m(n-m))。在模式匹配中，有这样的定理：没有算法的计算复杂度比BM算法更优[9]。根据以上综合分析，改进的算法并不希望比BM算法复杂更低，相比BM算法，该算法的平均时间复杂度并不是很高，平均性能优于BM算法及BMH算法、BMHS算法。

综合比较匹配过程中的字符比较次数、窗口比较次数和匹配所花费时间，对BM、BMH、BMHS和改进的BM算法进行测试。

实验首先使用随机的100个字符kajfieanygjbhawio gjeaengeagjwgqhklaiweakjgoawotoasgjadkjafieakdfifueikv jaisdifasqieanpaetnvjeaechlda，分别用BM、BMH、BMHS和改进的BM算法测试，统计模式串se，sea，sear，searc，search，searchi，searchin，searching用不同算法匹配时字符比较次数和窗口移动次数，结果如图3和图4所示。

图3 四种算法字符比较次数对比

图4 四种算法窗口移动次数对比

另测试不同算法模式匹配时所花费时间对比，在下列的实验环境下进行。内存：2 GB；主频：Intel双核；操作系统：Windows XP；Snort版本：2.9.1；程序实现使用C++语言，Visual C++6.0编译软件；结果察看使用Kiwi日志文件工具。实验分别用四种算法BM、BMH、BMHS和改进的BM算法，对服务器上随机的同样数量的数据包[10]进行测试，所花费的时间如图5所示。

图5 四种算法消耗时间对比

通过观察可知，改进的BM算法比BM、BMH、BMHS在窗口移动次数上有所减少，时间花费上也更少，由此可知，BM改进算法更优越。BM改进算法能够增大最大的移动距离，减少移动次数以及增大最大距离出现的概率。改进后的Snort规则匹配速度较以前有一定的提高，说明算法的改进是成功的，会对Snort系统今后的发展有所帮助。

5 小结

Snort系统凭借其自身的优势，在现代网络安全中得到越来越广泛的应用，提高其规则匹配的速度是研究的热点。本文提出的改进算法，应用于Snort系统中，能够提高Snort系统的效率，对于Snort系统及其他入侵检测系统都有可操作之处。

[1]Koziol J.Intrusion detection with Snort[M].吴溥峰，孙默，许诚，译.北京：机械工业出版社，2005：31-35.

[2]任晓峰，董占球.提高Snort规则匹配速度方法的研究与实现[J].计算机应用，2003，23（4）：59-61.

[3]Boyer R S，Moore J S.A fast string searching algorithm[J]. Communications of the ACM，1977，20：762-772.

[4]Horspool R N.Practical fast searching in strings[J].Software Practice&Experience，1980，10（6）：501-506.

[5]Sunday D M.A Very fast substring search algorithm[J]. Communication of the ACM，1990，33（8）：132-142.

[6]何畏，汪荣贵，查全民.一种新的快速移动单模式匹配算法[J].合肥工业大学学报：自然科学版，2010，33（5）：665-669.

[7]王浩，张霖，张庆.基于双字符序检测的BM模式匹配改进算法[J].计算机工程与科学，2012，34（3）：113-117.

[8]张娜，张剑.一个快速的字符串模式匹配改进算法[J].微电子学与计算机，2007，24（4）：102-105.

[9]李雪宝，刘宝旭.字符串匹配技术研究[J].计算机工程，2004，30（22）：24-26.

[10]王杰，王同军，孙珂珂.提高Snort规则匹配速度的新方法[J].计算机工程与应用，2009，45（28）：109-111.

ZENG Chuanhuang,HUANG Kan

IDS plays an increasingly important role in network security sector,Snort is one of IDS with open source,the theme we continuously researching improves the efficiency of the matching algorithm,so that IDS can reduce running time.The key to improve the efficiency of the matching algorithm is to increase the maximum distance and ensure moving the biggest safe distance.The improved algorithm is based on the BM algorithm and adopted the double characters sequence detection method.It results the maximum distance add tom+2and can move the biggest safe distance each time.Finally, through the experiment,when this algorithm applied to Snort,it can reduce times of comparing character and mobile windows. At the same time,it can improve the efficiency of Snort.

system of Snort;improved BM algorithm;maximum distance

入侵检测系统在网络安全中扮演着越来越重要的角色，Snort作为一个开源的入侵检测系统，改进其使用的匹配算法，使其能够减少运行时间，提高效率是不断研究的主题。对于模式匹配算法，增大其最大移动距离和保证其能够移动最大的安全距离是提高算法效率的关键。改进算法在BM算法的基础上，采用双字符序列检测方法，增大匹配过程中最大移动距离至m+2，并保证匹配失败时，每一次都能够移动最大的安全距离。将该改进算法应用于Snort系统中。实验验证，该算法能够减少字符比较次数和窗口移动次数，同时提高Snort系统的效率。

Snort系统；改进的BM算法；最大移动距离

A

TP309

10.3778/j.issn.1002-8331.1211-0322

School of Information Engineering,Jiangxi University of Science and Technology,Ganzhou,Jiangxi 341000,China

曾传璜（1964—），男，副教授，硕士生导师，主要研究方向为计算机网络安全，数据库应用技术。E-mail：huangkan0918@163.com

2012-11-26

2013-01-23

1002-8331（2014）22-0102-04

CNKI网络优先出版：2013-02-28,http://www.cnki.net/kcms/detail/11.2127.TP.20130228.1148.020.html