2023年7月20日发(作者：)

龙源期刊网

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

作者：冉占军 姚全珠 王晓峰 邹又姣

来源：《现代电子技术》2009年第02期

摘 要：仅依靠传统的被动防御技术已经不能满足如今的网络安全需要，基于模式匹配的入侵检测系统正成为研究和应用的热点，模式匹配效率的高低决定了这类入侵检测系统的性能。全面综述了应用于入侵检测系统的经典的模式匹配算法，包括单模式匹配算法中的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

(′an University of Technology,Xi′an,710054,China;e 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 ile,the efficiency of

various algorithms is h 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的目标串的首次出现或多次出现的过程。这里

中查找长度为m的模式串，

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

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

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

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

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

1.2 KMP算法

1970年，从理论上证明了一维模式匹配问题可以在O(m+n)时间内解决［1］。，和 在BF算法的基础上提出了一种快速模式匹配算法，称为KMP算法［1］，该算法消除了BF算法的目标串指针在相当多个字符比较相等后，只要有1