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

时间:2022-10-20 06:29:18

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

摘 要:仅依靠传统的被动防御技术已经不能满足如今的网络安全需要,基于模式匹配的入侵检测系统正成为研究和应用的热点,模式匹配效率的高低决定了这类入侵检测系统的性能。全面综述了应用于入侵检测系统的经典的模式匹配算法,包括单模式匹配算法中的KMP算法、BM算法、RK算法和多模式匹配算法中的AC算法、AC-BM算法,并对各种算法的执行效率进行了总结。通过分析算法的思想,提出了未来此类算法的研究方向。

关键词:入侵检测;KMP算法;BM算法;RK算法;AC算法;AC-BM算法

中图分类号:TP301文献标识码:B

文章编号:1004 373X(2009)02 063 05

Application of Pattern Matching Algorithm in Intrusion Detection Technique

RAN Zhanjun1,YAO Quanzhu2,WANG Xiaofeng1,ZOU Youjiao1

(1.Xi′an University of Technology,Xi′an,710054,China;2.College of Computer Science and Engineering,Xi′an Unversity of Technology,Xi′an,710048,China)

Abstract:Relying solely on traditional passive defense technology has been unable to meet today′s network security needs,IDS based on pattern-matching is becoming a hotspot of research and application,the efficiency of pattern matching determines the performance of this kind of IDS.A survey of the intrusion detection system classic pattern matching algorithm is given in this paper,including single pattern matching algorithm:KMP algorithm,BM algorithm,RK algorithm and multi-pattern matching algorithm -AC algorithm,AC-BM algorithm.Meanwhile,the efficiency of various algorithms is summarized.Through analysis of algorithms,future research directions of this kind of algorithm are advanced.

Keywords:intrusion detection;KMP algorithm;BM algorithm;RK algorithm;AC algorithm;AC-BM algorithm

0 引 言

随着网络技术的发展,各种基于网络的应用层出不穷。面对日益突出的网络安全问题,仅靠传统的被动防御已经不能满足要求,能够主动检测并预防的入侵检测系统应运而生。

根据采用的分析方法,入侵检测分为误用检测和异常检测。误用检测是指:根据己知的攻击方法,预先定义入侵特征,通过判断这此特征是否出现来完成检测任务。异常检测是指:根据用户的行为或资源的使用状况的正常程度来判断是否属于入侵。由于异常检测的误检率和漏检率高,因此目前大多数入侵检测系统产品均主要采用误用检测的方法。误用检测中使用的检测技术主要有: 模式匹配、专家系统、状态转移等,其中模式匹配原理简单,可扩展性好,而且最为常用。据统计,现在大约95%的入侵检测都是特征匹配的入侵检测。

由此可见,模式匹配算法性能的好坏直接影响到入侵检测系统的效率。随着网络传输速度的大幅度提高,入侵检测系统需要处理的数据量越来越大,如果模式匹配算法来不及处理这些实时的大量的数据包,必然会丢弃部分数据包,而这些被丢弃的数据包中很可能就包含有入侵信息,从而造成漏报。在此介绍几种著名的用于入侵检测的模式匹配算法,包括单模式匹配算法和多模式匹配算法,通过对它们进行剖析和实际测试,提出入侵检测系统中模式匹配算法的选择策略和未来的研究方向。

1 单模式匹配算法

1.1 相关定义

模式匹配:是指在给定长度为n的目标串T=T1T2…Tn中查找长度为m的模式串P=P1P2…Pm的首次出现或多次出现的过程。这里Ti(1≤i≤n),

Pj(1≤j≤m)∈∑(字符集),若P在T中出现1次或多次,则称匹配成功,否则称匹配失败。

单模式匹配算法:在目标串中1次只能对1个模式串进行匹配的算法。

多模式匹配算法:在目标串中可同时对多个模式串进行匹配的算法。

最简单的模式匹配算法是Brute-Force算法(BF算法)。在BF算法的目标串和模式串的字符比较中,只要有1个字符不相等,而不管前面已有多少个字符相等,就需要把目标串T回退,下次比较时目标串T只后移1个字符。虽然算法简单,但效率低下,不适合用于入侵检测系统中,不做重点介绍。

高效的模式匹配算法都是设法增大不匹配时目标串T或模式串P之间的偏移量,以减少总的比较次数。下面介绍3种经典的快速单模式匹配算法。

1.2 KMP算法

1970年,S.A.Cook从理论上证明了一维模式匹配问题可以在O(m+n)时间内解决[1]。D.E.Knuth,V.R.Pratt和T.H.Morris 在BF算法的基础上提出了一种快速模式匹配算法,称为KMP算法[1],该算法消除了BF算法的目标串指针在相当多个字符比较相等后,只要有1个字符比较不等便需要回溯的缺点,使算法的效率得到了大幅度提高,时间复杂度达到最理想的O(m+n),空间复杂度是O(m)。

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

定义next[j]函数为:

next[j]=max{k|1<k<j且 P1P2…Pk=

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

0,其他情况

-1(标记),j=0时

1.3 BM算法

相对于BF算法,KMP算法虽然消除了主串指针的回溯,在不匹配时能使模式串右滑若干位,但由上述next函数可知:右滑的最大距离不会超过1趟匹配操作所进了的比较次数j,原因在于KMP算法的匹配操作是从左到右进行的。受到KMP算法的启发,R.S.Boyer和J.S.Moore提出一种新的快速字符串匹配算法-BM算法[1-3]。

BM算法基本思想是:开始时将目标串T与模式串P左对齐,自右至左逐个字符进行比较(即首先比较Pm与Tm);当某趟比较时Ti与模式串的对应字符不匹配,则把模式串右滑d(x)一段距离,执行由Pm与Ti+d(x)起始的自右至左的匹配检查。BM算法采用以下两条规则计算模式串右移的距离:

(3) g是转移函数,该函数定义如下:g(s,a):从当前状态s开始,沿着边上标签为a的路径所到的状态。假如(u,v )边上的标签为a,那么g ( u,a ) =v;如果根节点上出来的边上的标签没有a,则g(0,a) =0,即如果没有匹配的字符出现,自动机停留在初态;

(4) f(不匹配时自动机的状态转移)也是转移函数,该函数定义如下:

f(s):当w是L(s)最长真后缀并且w是某个模式的前缀,那么f(s)就是以w为标签的那个节点;

(5) q0∈Q是初态(根节点,标识符为0);

(6) FQ,是终态集(以模式为标签的节点集)。

这样,在目标串中查找模式的过程转化成在模式树中的查找过程。查找一个串T时从模式树的根节点开始,沿着以T中字符为标签的路径往下走:若自动机能够抵达终态v,则说明T中存在模式L (v);否则不存在模式。

AC算法模式匹配的时间复杂度是O(n),并且与模式集中模式串的个数和每个模式串的长度无关。无论模式串P是否出现在目标串T中,T中的每个字符都必须输入状态机中,所以无论是最好情况还是最坏情况,AC算法模式匹配的时间复杂度都是O(n),包括预处理时间在内,AC算法总时间复杂度是O(M+n),其中M为所有模式串的长度总和。

2.3 AC-BM算法

对多模式串的匹配而言,虽然AC算法比BM算法高效得多,但AC算法必须逐一查看目标串的每个字符,即必须按顺序输入,不能实现跳跃,而BM算法则能够利用“右滑”跳过目标串中的大段字符,从而提高搜索速度。如果将BM算法的这种启发式搜索技术应用到AC算法中,则可大大提高多模式匹配算法的效率。许多人据此给出了各种改进的算法。Commentz-Walter最先将BM算法和AC算法结合在一起给出了Commentz-Walter算法;Baeza-Yates结合BMP算法和AC算法也给出了多模式匹配改进算法。

AC-BM算法[5]是Jang-Jong在1993年结合AC算法的有限自动机和BM算法的连续跳跃思想提出来的新算法,利用劣势移动表和优势跳转表来实现跳跃式地并行搜索,算法的时间复杂度为O(mn)。

该算法的思想是:首先把要查找的多个模式构成一个关键字树,把相同的前缀作为树的根节点。模式树从目标串的右端向左移动,一旦模式树确定在适当的位置,字符比较从左向右开始进行。模式树移动时同时使用坏字符移动和好前缀移动。坏字符移动的策略为:如果出现不匹配的情况,移动模式树,使得树中其他模式的能与当前目标串正在比较的字符相匹配的那个字符移动到与当前目标串正在比较的字符的相同位置上,如果在当前的深度上,目标字符没有出现在任何模式中,则模式树的偏移量为树中最短模式的长度。好前缀移动的移动策略为:将模式树移动到一个已被发现是另一个模式子串完全前缀的下一个位置,或者移动到作为树中另一个模式后缀能够正确匹配目标串的某个前缀的下一个位置。在模式树的移动过程中,必须确保模式树的偏移量不能大于树中最短的模式长度。

2.4 AC,AC-BM算法改进情况简介

文献[10]中卢汪节等人针对AC算法在构造状态机时空间冗余较大的情况,对状态机各结点进行压缩存储,使空间性能和时间性能都有提高;文献[11]中万国根等人对AC-BM算法的改进借鉴了BMH算法的思想,取消了原算法的好前缀跳转,优化了坏字符跳转,并修改了skip的计算方法,对大字符集的情况在平均情况下具有更优的性能;文献[12]对AC-BM的改进则是通过预处理思想实现的,在进行AC-BM匹配之前首先扫描首和(或)尾字符,确定其位置,再到相应位置进行匹配,相当于把目标串按模式串首、尾字符分成数段,每段进行比较,段间不含首字符的就直接跳过,不用比较,从而提高效率。

3 算法的实际执行效率

上述这些算法究竟哪种算法具有最好的执行效率呢?能不能仅通过时间复杂度来进行衡量呢?时间复杂度仅是一个度量的范围,表示受几个参数的影响,并不代表一个具体的值,还需要在具体的环境中进行测试。

文献[13]测试了包括上述算法在内的多种单模式和多模式匹配算法的性能。测试平台为:硬件:CPU Intel Xeon 3.46 GHz X 2,内存2 GB DDR,硬盘200 GB SCSI;软件:Windows 2003 Server,Intel IXA SDK4.1。单模式匹配测试的规则集,使用随机生成的8,16,32,48,128位具有代表意义的规则,可以对应端口、IP地址,MAC地址、IPv6地址等,对多模式匹配测试采用Snort系统2.4.3规则集。

单模式匹配算法主要测试模式长度与匹配时间、占用空间及预处理时间的变化关系。测试结果表明:各算法的测试指标在规则长度增长的情况下均呈递增趋势,但BM算法的增长速度最为缓慢,在不太在意存储空间的情况下,BM可以作为优先考虑的算法,同时对IPV6地址也更为合适。

多模式匹配算法的测试项目为规则数与单位匹配时间、占用储存单元、单位预处理时间的变化关系。测试结果表明AC-BM算法在上述3项测试中取得了很好的性能平衡。这也是新

版的Snort系统中选用AC-BM算法的重要原因。

4 入侵检测系统中模式匹配算法的研究方向

常用的模式匹配算法所采用的思想主要有基于字符比较、基于自动机、基于hash查找、基于位逻辑运算和基于Tries树型机构搜索。鉴于目前网络的实际状况,多模式匹配算法更加适合于基于模式匹配的入侵检测系统。这里认为应该从下面3个方面着手:一是继续研究和改进精确的模式匹配,将快速的单模式匹配算法和多模式匹配算法相结合,充分借鉴同类算法的先进思想,如:引入Hash函数、引入自动机、对字符串分块等来不断提高多模式匹配算法的性能;二是尝试采用模糊匹配的策略,国外对此已经开始进行相应的研究;三是对网络数据包和入侵特征进行研究,总结出这两类字符串特点,有针对性地对这两类字符串的匹配问题进行研究。

5 结 语

网络带宽的不断增加、日益严重的网络安全状况要求必须尽快提高网络入侵检测系统的性能。虽然入侵检测系统可以采用很多技术,并且这些技术也在不断的研究和发展中,但是目前主流的实用的入侵检测技术仍然是基于模式匹配的。因此如何提高模式匹配的效率成为研究入侵检测系统的一个关键所在。在此对已有的经典模式匹配算法进行了系统综述,并对入侵检测系统中模式匹配算法的未来研究方向给出了观点。

参考文献

[1]庞善臣,王淑栋,蒋昌俊.BM串匹配的一个改进算法[J].计算机应用,2004,12(12):11-13.

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

[3]张立航,潘正运,刘海峰.基于改进的KR算法在网闸中的实现[J].微计算机信息(管控一体化),2008(24):137-138.

[4]Johnson T,Newman-Wolfe R E.A Comparison of Fast and Low Overhead Distributed Priority Locks [J].Journal of Parallel and Distributed Computing,1996,32(1):74-89.

[5]Jason C C,Staniford S,McAlemey J.Towards Faster String for Intrusion Detection or Exceeding the Speed of Snort [EB/OL]./sotfware/acbm/speed-of-snort-03-16-2001.padf,2003.

[6]黄占友,刘悦.对KMP串匹配算法的改进[A].第四次全国便携计算机学术交流会论文集[C].北京:科学出版社,1997.

[7]涛,方滨兴,胡铭曾.对BM串匹配算法的一个改进[J].计算机应用,2003,23(3):6-8.

[8]张国平,徐汶东.字符串模式匹配算法的改进[J].计算机工程与设计,2007,28(20):4 881-4 884.

[9]蔡晓妍,戴冠中,杨黎斌.一种快速的单模式匹配算法[J].计算机应用研究,2008,25(1):45-46,81.

[10]卢汪节,鞠时光.入侵检测系统中一种改进的AC算法[J].计算机工程与应用,2006(15):146-148.

[11]万国根,秦志光.改进的AC-BM字符串匹配算法[J].电子科技大学学报,2006,35(4):531-533.

[12]周四伟,蔡勇.AC-BM算法的改进及其在入侵检测中的应用[J].微计算机应用,2007,28(1):27-31.

[13]王琢,赵永哲,姜占华.网络处理模式匹配算法研究[J].计算机应用研究,2007,24(12):310-312.

作者简介

冉占军 男,1977年出生,陕西西安人,讲师,硕士研究生。主要研究方向为算法、网络安全。

姚全珠 男,1960年出生,博士,教授。主要研究方向为算法、数据库、网络安全。

王晓峰 女,1966年出生,博士,副教授。主要研究方向为信息安全。

邹又姣 女,1975年出生,硕士,讲师。主要研究方向为信息安全。

上一篇:数字温度传感器在测色系统中的应用 下一篇:基于Matlab的Buck电路的研究