微波EDA网,见证研发工程师的成长!
首页 > 射频和无线通信 > 射频无线通信文库 > 模式匹配算法在入侵检测中的应用

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

时间:04-24 来源:互联网 点击:

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

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+2)时间内解决。D.E.Knuth,V.R.Pratt和T.H.Morris在BF算法的基础上提出了一种快速模式匹配算法,称为KMP算法,该算法消除了BF算法的目标串指针在相当多个字符比较相等后,只要有1个字符比较不等便需要回溯的缺点,使算法的效率得到了大幅度提高,时间复杂度达到最理想的O(m+n),空间复杂度是O(m)。
KMP算法的基本思想是:若某趟匹配过程中Ti和Pj不匹配,而前j一1个字符已经匹配。此时只需右移模式串P,目标串T不动,即指针i不回溯,让Pk与Ti继续比较。移动后重新开始比较的位置k仅与模式串P有关,而与目标串T无关,因此k可以通过下面的next函数事先确定。
定义next[j]函数为:


1.3 BM算法
相对于BF算法,KMP算法虽然消除了主串指针的回溯,在不匹配时能使模式串右滑若干位,但由上述next函数可知:右滑的最大距离不会超过1趟匹配操作所进了的比较次数j,原因在于KMP算法的匹配操作是从左到右进行的。受到KMP算法的启发,R.S.Boyer和J.S.Moore提出一种新的快速字符串匹配算法一BM算法。
BM算法基本思想是:开始时将目标串T与模式串P左对齐,自右至左逐个字符进行比较(即首先比较Pm与Tm);当某趟比较时Ti与模式串的对应字符不匹配,则把模式串右滑d(x)一段距离,执行由Pm与Ti+d(x)起始的自右至左的匹配检查。BM算法采用以下两条规则计算模式串右移的距离:
(1)好后缀移动。其又分为2种情况:
①P已比较部分P[j+1…m]与其中间的某一子串P[j一s+l…m―s]相同,P右移s位。如图1所示。

②P已比较部分P[j+l…m]的后缀P[s+l…m]与P的前缀P[l…m―s]相同,P右移s位。如图2所示。

取满

Copyright © 2017-2020 微波EDA网 版权所有

网站地图

Top