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

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

2、热点，模式匹配效率的高低决定了这类入侵检测系统的性能。全面综述了应用于入侵检测系统的经典的模式匹配算法，包括单模式匹配算法中的KMP算法、BM算法、RK算法和多模式匹配算法中的AC算法、ACBM算法，并对各种算法的执行效率进行了总结。通过分析算法的思想，提出了未来此类算法的研究方向。关键词：入侵检测；KMP算法；BM算法；RK算法；AC算法；ACBM算法0 引 言    随着网络技术的发展，各种基于网络的应用层出不穷。面对日益突出的网络安全问题，仅靠传统的被动防御已经不能满足要求，能够主动检测并预防的入侵检测系统应运而生。    根据

3、采用的分析方法，入侵检测分为误用检测和异常检测。误用检测是指：根据己知的攻击方法，预先定义入侵特征，通过判断这此特征是否出现来完成检测任务。异常检测是指：根据用户的行为或资源的使用状况的正常程度来判断是否属于入侵。由于异常检测的误检率和漏检率高，因此目前大多数人侵检测系统产品均主要采用误用检测的方法。误用检测中使用的检测技术主要有：模式匹配、专家系统、状态转移等，其中模式匹配原理简单，可扩展性好，而且最为常用。据统计，现在大约95%的入侵检测都是特征匹配的入侵检测。由此可见，模式匹配算法性能的好坏直接影响到入侵检测系统的效率。随着网络传输速度的大幅度提高，入侵检测系统需要处理的数据量越来越大，

4、如果模式匹配算法来不及处理这些实时的大量的数据包，必然会丢弃部分数据包，而这些被丢弃的数据包中很可能就包含有入侵信息，从而造成漏报。在此介绍几种著名的用于入侵检测的模式匹配算法，包括单模式匹配算法和多模式匹配算法，通过对它们进行剖析和实际测试，提出入侵检测系统中模式匹配算法的选择策略和未来的研究方向。1 单模式匹配算法11 相关定义    模式匹配：是指在给定长度为n的目标串T=T1T2Tn中查找长度为m的模式串P=P1P2Pm的首次出现或多次出现的过程。这里Ti(1in)，Pj(1jm)(字符集)，若P在T中出现1次或多次，则称匹配成功，否则称匹配失败。单模式匹

5、配算法：在目标串中1次只能对1个模式串进行匹配的算法。    多模式匹配算法：在目标串中可同时对多个模式串进行匹配的算法。    最简单的模式匹配算法是BruteForce算法(BF算法)。在BF算法的目标串和模式串的字符比较中，只要有1个字符不相等，而不管前面已有多少个字符相等，就需要把目标串T回退，下次比较时目标串T只后移1个字符。虽然算法简单，但效率低下，不适合用于入侵检测系统中，不做重点介绍。    高效的模式匹配算法都是设法增大不匹配时目标串T或模式串P之间的偏移量，以减少总的比较次数。下面介绍

6、3种经典的快速单模式匹配算法。12 KMP算法    1970年，SACook从理论上证明了一维模式匹配问题可以在O(m+2)时间内解决。DEKnuth，VRPratt和THMorris在BF算法的基础上提出了一种快速模式匹配算法，称为KMP算法，该算法消除了BF算法的目标串指针在相当多个字符比较相等后，只要有1个字符比较不等便需要回溯的缺点，使算法的效率得到了大幅度提高，时间复杂度达到最理想的O(m+n)，空间复杂度是O(m)。    KMP算法的基本思想是：若某趟匹配过程中Ti和Pj不匹配，而前j一1个字符已经匹配。此时只需右移模

7、式串P，目标串T不动，即指针i不回溯，让Pk与Ti继续比较。移动后重新开始比较的位置k仅与模式串P有关，而与目标串T无关，因此k可以通过下面的next函数事先确定。    定义nextj函数为：   13 BM算法    相对于BF算法，KMP算法虽然消除了主串指针的回溯，在不匹配时能使模式串右滑若干位，但由上述next函数可知：右滑的最大距离不会超过1趟匹配操作所进了的比较次数j，原因在于KMP算法的匹配操作是从左到右进行的。受到KMP算法的启发，RSBoyer和JSMoore提出一种新的快速字符串匹配算法一BM算法。    BM算法基本思想是：开始时将目标串T与模式串P左对齐，自右至左逐个字符进行比较(即首先比较Pm与Tm)；当某趟比较时Ti与模式串的对应字符不匹配，则把模式串右滑d(x)一段距离，执行由Pm与Ti+d(x)起始的自右至左的匹配检查。BM算法采用以下两条规则计算模式串右移的距离：    (1)好后缀移动。其又分为2种情况：    P已比较部分Pj+1m与其中间的某一子串Pj一s+lms相同，P右移s位。如图1所示。