一种基于BM算法的改进模式匹配算法研究

葛贤银,韦素媛,杨百龙,蒲玄及

摘 要:基于模式匹配的检测方法是目前入侵检测系统的一种重要方法,因此作为模式匹配方法核心的字符串匹配算法直接影响入侵检测系统的性能和效率。在研究现有算法的基础上提出一种改进的模式匹配算法New-Search算法。该算法以BM算法为基础,通过预处理阶段处理,首末字符部分定位的思想,增加字符跳转距离,比较稳定地减少匹配过程中字符比较的次数,提高了匹配的速度和效率。

关键词:入侵检测;模式匹配;KMP算法;BM算法;New-Search算法

中图分类号:TP311文献标识码:A

文章编号:1004-373X(2009)20-073-03

Research of Improved Pattern Matching Algorithm Based on BM Algorithm

GE Xianyin,WEI Suyuan,YANG Bailong,PU Xuanji

(The Second Artillery Engineering College,Xi′an,710025,China)

Abstract:The detecting method based on pattern matching is an important method in intrusion detection system,the key of this is the efficiency of string matching which influences the efficiency of detection directly.An improved pattern matching algorithm named New-Search which is based on BM algorithm is proposed.This algorithm can increase the jumping distance of characters and decrease the comparison times in matching process through the pretreatment step,which takes the idea of the first and last characters′ partial location.In this case,it improves the matching efficiency.

Keywords:intrusion detection;pattern matching;KMP algorithm;BM algorithm;New-Search algorithm

0 引 言

随着网络技术的发展,网络环境变得日益复杂,对于网络安全来说,单纯的防火墙技术暴露出明显的不足和弱点,如不能提供实时入侵检测能力;对于病毒束手无策等。入侵检测系统是继防火墙和信息加密等安全保障技术之后出现的新一代网络安全防护系统,能够有效地弥补上述安全系统的不足[1]。它通过对算机网络或计算机系统中的若干关键点收集信息并对其进行分析,实时地发现网络或系统中是否有违反安全策略的行为和被攻击的迹象,并采取相应措施以避免攻击的发展或尽量减少攻击造成的危害。按照所采用的检测技术,入侵检测系统可以分为误用检测系统和异常检测系统。误用检测系统使用模式匹配的方法来发现入侵行为,是目前入侵检测系统的主流。所以,作为模式匹配方法核心的字符串匹配算法直接影响入侵检测系统的性能和效率[2]。

1 几种经典的模式匹配算法

1.1 KMP(Knuth Morris Pratt)算法

此算法是Knuth D E与Pratt V R和Morris J H同时发现的,因此人们称为KMP算法[3]。KMP算法的基本思想是:若某趟匹配过程中Ti和Pj不匹配,而前j-1个字符已经匹配。此时只需右移模式串P,文本串T不动,即指针i不回溯,让Pk与Ti继续比较。 移动后重新开始比较的位置k仅与模式串P有关,而与目标串T无关,因此k可以通过下k可以通过下面的next函数事先确定。

定义next[j]函数为:k可以通过下面的next函数事先确定。

next[j]=max{k1

Pj-kPj-k+1…Pj-1,集合非空

0,其他情况-1(标记),j=0时

KMP算法在最坏情况下的复杂度为O(m+n)。

1.2 BM(Boyer Moore)算法

BM算法[4]的基本思想是:开始时将目标串T与模式串P左对齐,自右至左逐个字符进行比较(即首先比较Tt+m与Tm);当某趟比较时Ti与模式串的对应字符不匹配,则把模式右滑一段距离d(x),执行由Pm与Ti+d(x)起始的自右至左的匹配检查,直到找到要匹配的模式或整个文本搜索完毕。

右滑距离函数d(x)定义如下:

d(x)=m,x not in P或x=Pm且

x≠Pj(1≤j≤m-1)

m-j,j=max{jPj=x,1≤j≤m-1},

其他情况

最差情况下找到所有模式出现的时间复杂度O(mn)。在最好情况下找到模式出现的时间复杂度为O(n/m)。

1.3 QS(Quick Search)算法

QS算法[5]思想如下:假设当前文本指针为t,模式串P与Tt,t+m-1对齐。考虑到文本串字符与模式串字符匹配不成功时,文本指针至少要移动1个位置,那么在下一次匹配过程中,Tt+m是待处理的对象,因而在计算偏移量时,可将Tt+m考虑进去,通过判断Tt+m是否在模式中,从而决定模式串的移动量。对于模式中不出现的字符,其偏移量为m+1。QS算法的主要特征是:模式串的移动量大;在模式串较短的情况小更为有效;最坏情况下找到模式所有出现的时间复杂度为O(mn)。

1.4 AC(Aho Corasick)算法

AC算法[6]是一个同时搜索多个模式的经典多模式匹配算法。所谓多模式匹配算法就是把所有的模式串合并到一个数据结构中,通过对文本进行一次扫描,找到所有模式的所有出现。AC算法使用有限自动机的结构来接收所有的字符串。由于自动机是结构化的,这样每个前缀都可用惟一的状态来标识,甚至是那些多个模式串的共同前缀。当文本中下一个字符不是模式中预期的下一个字符中的一个时,会有一条失败链指向一个状态。这个状态代表最长的模式前缀,同时也是当前状态的相应后缀。AC算法在以下方面得到了改进:同时支持确定型和不确定型有限状态自动机;采用线性链表来初始化状态转移表;在执行过程中,将确定型和不确定型有限状态自动机的状态转移表转换成全矩阵形式,有利于减少内存开销;在每一个状态转移链表中增加一个布尔型变量,来指示状态中是否存在一个匹配的模式。AC算法搜索阶段的时间复杂度为O(n),预处理阶段的时间复杂度为O(M),其中M是所有模式串的长度和[7]。

2 改进模式匹配算法New Search

2.1 算法提出的背景

随着网络攻击技术的发展和攻击手段的多样化,描述攻击行为的特征数目指数上升,检测算法的效率已成为误用检测技术的瓶颈,直接影响系统的实时性能。因而,如何改进字符串匹配搜索算法,提高检测速度,是目前IDS研究的重点之一[8]。另外对于基于误用的入侵检测系统来说,入侵特征匹配是检测过程中最费时的部分。提高入侵检测引擎的速度一直以来都是研究的热点问题[9]。在此提出一种基于BM算法的改进算法,通过对数据进行预处理,增大一次跳过的字符数,从而可进一步减少字符匹配次数,提高算法性能。

2.2 算法的基本思想

算法的基本思想:假设要检测数据报负载T中是否包含模式串P,如果模式串中T中的首末字符不在负载T中,则说明P不在T中;反之,说明P可能在T中,需要调用标准字符串匹配算法来确定P是否为T的子串。

2.3 算法的实现

算法的实现分为两个阶段:预处理阶段和搜索阶段。前者依赖于能快速判断P中首末字符是否在T中的方法,后者依赖于一个快速准确的模式匹配算法。

(1) 预处理阶段。这里主要借助指针函数,首先从负载T中搜索出模式串P的首子符,接着在搜索出的首字符位置加上模式串P的长度,看P的末字符是否与对应位置匹配,如果匹配,标记并存储相应位置;如果不匹配,直接丢弃。

(2) 搜索阶段。主要思想:借助于BM算法,从左向右移动模式串,从预处理阶段中搜索出负载T中与模式串P的首字符位置Ti处进行匹配,即图中1所在的位置。如果不匹配,借助于BM算法,跳转距离为q,即图中的4所在的位置。跳转距离p与预处理阶段搜索出的与P首字符且未字符相同的2,3位置进行比较,如果p>r,则舍弃2所在位置;以4所在位置为准;如果p

图1 思想演示图

流程图如图2所示。

从流程图可以看出最差情况下搜索阶段找到模式的所有出现的时间复杂度为O(mn),最优情况下的时间复杂度为O(n/m)。虽然从复杂度分析上看没有很大改进,但因首末子串在T中同时匹配属于小概率事件。通过这种方法改进,大大加强了跳转距离,一定程度上提高了模式匹配的效率。

图2 算法流程图

2.4 对比试验

算法的实际运行情况比较复杂,在真实语料上的测试数据将更能说明各种算法的效率。选择一篇英文的帮助文件作为测试语料,大小为5.4 MB,选择其中长度为3~10个英文单词、短句作为模式串,总共选择6个,统计各模式串在测试语料中出现的总次数,占用CPU的时间,总的尝试次数和总的比较次数。实验环境为:CPU为奔腾4 2.4 GHz,内存为2 GHz,操作系统为Windows XP,编译环境为VC++6.0。实验数据如表1所示。

表1 算法比较

算法CPU时间 /ms尝试次数字符比较次数

BM算法9 543346 521 628364 807 835

改进算法7 421292 007 214298 319 791

从实验结果来看,改进算法较算法在占用时间、尝试次数和比较次数上效率都有不小的提高,其中占用CPU时间是BM算法的78.5%,总的尝试次数是BM算法的84.2%,总的字符比较次数是BM算法81.8%。

3 结 语

随着网络应用的不断出现以及网络带宽的不断增加,必须加快入侵检测系统的处理性能以适应大流量网络环境的要求。目前入侵检测系统大多是基于模式匹配的系统,因此提高模式匹配的效率是提高系统检测能力的关键[10]。这里对入侵检测系统中应用的模式匹配算法进行了研究,在BM算法基础上进行改进,增大了跳跃距离。实验结果表明,在入侵检测系统中应用此算法,能够显著提高模式匹配的效率,从而提高系统的检测性能。

参考文献

[1]李庚,韩进,谢立.入侵检测中一种新的多模式匹配算法[J].计算机应用研究,2008,25(8):2 474-2 476.

[2]张雷.基于模式匹配的网络入侵检测系统研究[D].成都:西南交通大学,2005.

[3]Knuth D E,Morris J H,Pratt V R.Fast Pattern Matching in Strings[J].SIAM Comput.,1977,6(2):323-350.

[4]Boyer R S,Moore J S.A Fast String Searching Algorithm[J].Commun.ACM,1977,20(10):762-772.

[5]Sunday D M.A Very Fast Substring Search Algorithm[J].Commun.ACM,1990,33(8):132-142.

[6]Aho A V,CorasickM J.Efficient String Matching:An Aid to Bibliographic Search[J].Commun.ACM,1975,18(6):333-340.

[7]张胤.模式匹配型入侵检测系统的改进研究[D].秦皇岛:燕山大学,2006.

[8]谭汉松,彭诗力.一种新的多模式匹配算法[J].计算机工程,2005,31(18):119-120.

[9]李红霞.串匹配型入侵检测系统的改进研究[D].秦皇岛:燕山大学,2005.

[10]蓝华.基于网络匹配的入侵检测系统的研究与设计[D].长春:吉林大学,2005.