改进的模式匹配算法在入侵检测中的应用

摘要:随着网络技术的高速发展,网络安全问题日益突出,入侵检测技术成为当今关注的焦点。模式匹配算法的性能对入侵检测系统影响很大。在分析现有模式匹配算法的基础上,提出了改进的AC_BM算法,该算法在文本与模式某次匹配失败后,跳过尽可能多的字符,实现更快的匹配过程。实验证明,改进后的算法大大提高了检测的性能。

关键词:入侵检测;模式匹配;BM算法;AC算法;AC_BM算法

中图分类号:TP309文献标识码:A 文章编号:1009-3044(2010)04-0821-03

Application of Improved Algorithm for Pattern Matching in Intrusion Detection

WANG Da-yong

(College of Computer Science and Technology, Harbin University of Science and Technology, Harbin 150080, China)

Abstract: With the rapid development of the network, the security question is outstanding day and day, intrusion detection technique nowadays becomes the focus which the people pays close attention to.An effcetive and precise pattern matching algorithm is important to intrusion decetion system. In this paper, based on the analysis of existing pattern matching algorithms,proposed an improved algoruthm for AC_BM, the algorithm and model in the text after the failure of a particularmatch, skipping as many characters, in order to achieve faster matching process. Results show the improved algorithm greatly improved the performance of detection.

Key words: intrusion detection; pattern matching; BM algorithm; AC algorithm; AC_BM algorithm

随着网络技术的高速发展,个人、企业以及政府部门越来越多的依靠网络传递信息,然而网络的开放性与共享性容易使它受到外界的攻击与破坏,信息的安全保密性受到严重影响。网络安全问题已成为世界各国政府、企业及广大网络用户最关心的问题之一。试图破坏信息系统的完整性、机密性、可信性的任何网络活动都称为网络入侵。

传统的防火墙技术只是一种被动防御性的网络安全工具。首先,入侵者可以找到防火墙的漏洞,绕过防火墙进行攻击。其次,防火墙对来自内部的攻击无能为力。它所提供的服务方式是要么都拒绝,要么都通过,而这是远远不能满足用户复杂的应用要求的。于是就产生了能够主动检测并预防的入侵检测技术。入侵检测技术作为一种积极主动地安全防护技术,已成为网络安全研究领域中的热点[1]。

根据入侵检测系统对数据分析方法的不同,可将其分为两大类:误用检测和异常检测。误用检测是指:根据己知的攻击方法,预先定义入侵特征,通过判断这此特征是否出现来完成检测任务。异常检测是指:根据用户的行为或资源的使用状况的正常程度来判断是否属于入侵[2]。由于异常检测的误检率和漏检率高,因此目前大多数人侵检测系统产品均主要采用误用检测的方法。据统计,现在大约95%的入侵检测都是特征匹配的入侵检测。由此可见,模式匹配算法性能的好坏将直接影响到入侵检测系统的效率。在已有的模式匹配算法中,主要有Boyer-More(简称BM算法)、Aho-Corasick(简称AC算法),AC_BM算法等。本文在分析以上算法的基础上,提出了一种新的改进的AC_BM算法。

1 现有模式匹配算法的分析

1.1 BM算法

BM算法是由R.Boyer和J.Moore提出的一种快速字符串匹配算法。著名的开放源代码的入侵检测系统snort采用的就是BM算法[3]。BM算法的主要思想:BM算法区别于KMP算法,它采用从右向左比较的方法,当匹配发生失败时,模式T右移的计算方法发生了较大的变化。为方便讨论,对给定的模式T=t0t1t2…tm,定义一个从字符到正整数的映射:

dist : c->{1,2,…,m+1}

函数 称为滑动距离函数,它给出了正文中可能出现的任意字符在模式中的位置。函数dist定义如下:

m-j,j为c在模式中的下标,以后面的为准

dist(c)=m+1,若c不在模式中或c=tm。例如,T=”pattern”,则dist(p)=6-0=6,dist(a) =6-1=5,dist(t)=6-4=2,dist(e)=2,dist(r)=1,dist(n)=6+1=7。BM算法的基本思想是:假设将主串中自位置 起往左的一个子串与模式进行从右到左的匹配过程中,若发现不匹配,则下次应从主串的i+dist(si)位置开始重新进行新一轮的匹配,其效果相当于把模式和主串向右滑过一段距离dist(si),即跳过dist(si)个字符而无需进行比较。因为在实际应用中,字符表中的大部分字符不出现在模式串中,所以应用BM算法可以大大加快串匹配的速度。

但是随着入侵方法、方式的多样性,入侵的匹配规则也在急速上升,这时仅用BM算法来进行规则匹配,就显得力不从心,效果不佳。

1.2 Aho-Corasick算法

Aho-Corasick算法(简称AC算法)是同时搜索多个模式的经典匹配算法。由贝尔实验室Alfred V.Aho和Margaret J.Corasick发明,最早被使用在图书馆的书目查询程序中,取得了很好的效果[4-5]。AC算法使用了有限状态自动机的结构来接收集合中所有的字符串。自动机是结构化的,这样每个前缀都可用唯一的状态来标志,甚至是那些多个模式的前缀。当文本中的下一个字符不是模式中预期的下一个字符中的一个时会出现一条失败链指向那个状态。代表最长的模式前缀同时也是当前状态的相应后缀。AC算法的复杂性是o(n),预处理阶段的复杂性是o(m)。在用AC算法构造的有限状态自动机中,要为每一个模式串的每一个字符建立一个节点,这样无疑使得该算法的空间使用效率很高。

有限自动机算法是以空间换时间的经典算法,当模式集较大时可能产生空间膨胀问题。AC算法在对输入串进行搜索时没有跳跃而是按顺序输入无法跳过没必要的比较因此在规则不是非常多的实际搜索过程中AC算法性能不佳。

1.3 Aho-Corasick_Boyer-Moore(AC_BM)算法

AC_BM算法把Aho-Corasick和BM算法结合在一起,它具有AC算法的多模式匹配和BM算法的滑动跳跃式移动的特点,并具有线性时间复杂度。AC_BM算法将具有相同前缀的不同模式放在一棵模式树上,然后对这棵树使用BM算法进行匹配[6]。AC_BM算法不像标准BM算法那样一次只移动一个模式,而是移动整棵模式树,同时使用不良字符和良好后缀进行跳跃,以消除不必要的比较。

AC_BM算法尽管效率比BM,AC算法优越,但是构造模式树的速度比较慢,在构造树的过程中会导致内存浪费,并且节点个数多和无规则性导致了状态转向的速度慢,动态增删模式串也比较麻烦。

2 新的模式匹配算法

随着网络流量的迅速增加,以上各种算法的匹配规则和匹配效率已经不能完全适应高速网络的要求,尤其是如今的检测规则在不断增加,对每个数据包可能要匹配的次数也在飞速增加,因此其性能不能完全被满足。在这种情况下,我们在AC_BM算法的基础上并充分结合QS算法中充分利用本次匹配不成功的思想,在文本与模式某次匹配失败后,跳过尽可能多的字符,实现更快的匹配过程。

QS 算法是一种简化的 BM 算法,可以描述为:当P[1…n]与T[i…i+n-1]对齐,就进行匹配,若匹配失败,则分析T[i+n]这个字符,来决定P[1…n]右移的距离,因为当某一次匹配失败后,模式至少向右移动一个位置,在一般情况下,T[i+n]这个字符会出现在下一次的匹配过程中,于是在匹配失败后,可先考虑T[i+n],而不是T[i…i+n-1]中的字符,使得模式的最大右移距离为n+1,而 BM 算法中模式的最大右移距离为n [7]。

改进之一:改进的AC_BM 算法中,当文本与模式树某次匹配失败后,对文本T[i…i+n-1]左边的字符T[i-1]使用坏字符移动,对文本T[i…i+n-1]使用好前缀移动,文本指针移动的距离取其中大的一个,最大移动距离为minlength+1,minlength为模式集合中最短模式的长度。对于文本中任一字符ω,坏字符移动函数可定义如下:

如果ω出现在{P}中,执行*式,否则执行**式。

改进之二:AC_BM 算法在每次文本与模式树匹配失败后都要计算坏字符启发函数和好前缀启发函数,然后取最大值作为偏移量,然而计算好前缀启发函数的时间开销较大,因此,我们在改进的 AC_BM 算法中采用坏字符优先的策略,当利用坏字符启发能得到n或n+1的偏移量时就不再计算好前缀启发函数,而且当模式树在文本中的出现较为稀疏时,改进的 AC_BM 算法在大多数移动过程中可容易得到n+1的最大偏移量,这样就可避免好前缀启发函数的计算,从而可大大缩短模式匹配所需要的时间。

下面对改进的 AC_BM 算法的性能进行分析。改进的 AC_BM 算法预处理阶段时间复杂度为o(|∑|+|P|),这里的|∑|是字符集大小,|P|是模式集P中所有模式长度的总和。最佳性能情况:在每次进行模式树第一个字符与文本比较时都不匹配,且具有最大的偏移量minlength+1, 改进算法具有最佳性能,此时的比较次数为

时间复杂度为o()

最差性能情况:在每次都进行到模式树中最长模式的最后一个字符与文本比较时才发生不匹配,且具有最小偏移量 1,改进算法具有最差性能,此时的比较次数为minlength+[n-2(minlength-1)]maxlength,时间复杂度为o(n maxlength)。平均情况下的时间复杂度与字符的出现概率有关,因此需要通过概率模型进行计算,平均情况下的算法的性能通过找出不匹配字符所花的代价和发现该不匹配后能够移动的距离之比的概率平均值来确定,因为改进的AC_BM 算法在坏字符移动时与原算法不同,因此只需要比较改进算法与原算法在坏字符移动时的平均性能情况,根据上述的确定方法,其平均性能

,

Ccost(i)为计算skip函数所花的代价Sskip(i)为发现字符不匹配后平均能够跳过的字符,而式中Pskip(i,k)为查询第i个字符时,发现不匹配后能够跳过k个字符的概率,而在 AC_BM 算法中

显然,改进的 AC_BM 算法中Sskip(i)比 AC_BM 算法要大,而通常情况下分子Ccost(i)相同,因此改进算法比 AC_BM 算法具有更好的平均性能。

3 实验分析

为了对各个算法的性能、效率做具体的评测,在同一台计算机上进行了算法实现并进行了测试。实验机配置联想台式机,CPU Pentium双核4200,内存1G,硬盘160G,操作系统Windows2000,算法实现的环境是Visual C++6.0。试验中测试了BM,AC,AC_BM和改进的AC_BM算法。我们选取了10M 的纯英文字母作文本,选取长度为5,15,20,30,40,50 的字符作模式串,用上述几种算法进行搜索,比较它们的实际效率。最后得到以下一组数据,如表1所示。

从上面的测试数据可以看出,改进后的算法和前几种算法相比较,在匹配时间上明显缩短,尤其在模式串长度比较长的情况下。

4 结论

随着各种网络应用的不断出现以及网络带宽的不断增加,目前的网络入侵检测系统的处理性能已不能适应大流量网络环境的要求,这就迫切需要提高入侵检测系统的处理性能。本文对模式匹配算法BM和AC和AC_BM算法作了简要的分析,并提出了改进的AC_BM算法。将改进的算法应用到入侵检测系统中,可以有效地提高系统的检测效率。

参考文献:

[1] 曾志峰,杨义先.网络安全的发展[J].计算机工程与应用,2006,24(7):101-103.

[2] 周国民.入侵检测产品市场扫描[J].网络安全技术与应用,2004,12(5):64-67.

[3] Knuth D E,Morris J H,Pratt V R.Fast Pattern Matching in String[J].SIAM Journal on Computing,1977,11(6):323-350.

[4] Aho,A.V,M.J.Corasick.Efficient string matching:an aid to bibliographic search[J].Communications of ACM,1975,18(6):333-340.

[5] 唐正军.入侵检测技术导论[M].北京:机械工业出版社,2004:124-135.

[6] 柴平宣,程时瑞.入侵检测技术分析[J].计算机工程,2005,28(14):164-166.

[7] 康晓宁,蒋东兴,张成,等.分布式高速网络入侵防御系统研究[J].小型计算机系统,2005,26(11):1177-1182.