入侵检测系统中模式匹配算法的研究.docx

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

摘要入侵检测是网络安全的最后一道防线，模式匹配算法是基于特征匹配的入侵检测系统中的核心算法，模式匹配的效率决定这类入侵检测系统的性能。本文对入侵检测系统中的模式匹配算法进行了综述，包括经典的单模式匹配算法--KMP算法、BM算法、RK算法和多模式匹配AC算法。对各种算法的性能进行了分析。最后提出了改进模式匹配算法效率的研究方向。关键词:网络安全；入侵检测；模式匹配；多模式匹配
1引言随着Internet应用的普及，网络安全问题也日益突出。入侵是指试图破坏资源的完整性、可用性和保密性的活动的集合。作为防火墙之后网络安全的最后一道防线，入侵检测系统（IDS）是指检测上述行为的活动，识别出未经授权或越权访问系统资源的行为的软硬件系统。由于入侵检测系统可以在一定程度上主动预防和检测出来自系统内、外部的入侵，并作出适当响应，动态改变网络的安全性，因此入侵检测的研究正成为网络安全研究的热点。根据采用的分析技术入侵检测分为误用检测和异常检测[1]。误用检测根据已知的攻击方法，预先定义入侵模式，通过判断这些模式是否出现来完成检测任务。异常检测是指根据用户的行为或资源的使用状况的正常程度来判断是否属于入侵。由于异常检测的误检率和漏检率高，因此目前大多数入侵检测系统产品均属误用检测。误用检测中使用的检测技术主要有：模式匹配、专家系统、状态转移等，而其中因为模式匹配原理简单、可扩展性好而最为常用，例如著名开放源码的入侵检测系统Snort就是基于模式匹配的。由此可见，模式匹配算法的性能直接影响入侵检测系统的检测效率。在高速网络环境，如果模式匹配算法来不及处理大量的实时网络数据包，必然会丢弃部分数据包，而这些被丢弃的数据包中就可能包含入侵信息。本文以下部分介绍几种著名的模式匹配算法，包括单模式匹配算法和多模式匹配算法，为设计入侵检测系统选择模式匹配算法提供指导。
2单模式匹配算法模式匹配是指在给定长度为n的文本串T=T[1]T[2]…T[n]中查找长度为m的模式串P=P[1]P[2]…P[m]的第一次出现的过程。这里T[i]（1≤i≤n），P[j]（1≤j≤m）∈∑（字符集），若在T中能找到P的出现，则称匹配成功，否则称匹配失败。一次只能在文本串中对一个模式串进行匹配的算法，称为单模式匹配算法，可同时对多个模式串进行匹配的算法称多模式匹配算法。平凡的模式匹配算法（BF算法）中，一趟匹配失败后，T只后移一个字符，所以算法简单，但效率低。高效的模式匹配算法都是设法增大不匹配时T的后移量，本节下面介绍3种经典的快速单模式匹配算法，第3节介绍著名的多模式匹配算法—AC算法。2.1KMP算法D.Knuth、J.Morris和V.Pratt提出一种快速模式匹配算法，称为KMP算法[2]。KMP算法的基本思想是：若某趟匹配过程中T[i]和P[j]不匹配，而前j-1个字符已经匹配。此时只需右移模式串P，文本串T不动，即指针i不回溯，让P[k]与T[i]继续比较。移动后重新开始比较的位置k仅与模式串P有关，而与目标串S无关，因此K可以事先确定。若定义函数next(j)=K，则next函数的定义应为：next(j)=Max{k|P[1..K-1]=P[j-k+1..j-1]}KMP算法的时间复杂度是O(m+n)，空间复杂度是O(m)，对BF算法进行了很大的改进。2.2BM算法KMP算法虽然在不匹配时能使模式串右移若干位，但右移的距离不可能超过一趟匹配操作所进行的比较次数j，存在这一问题的根本原因是KMP算法的匹配操作是从左向右进行的。在KMP算法的启发下，R.Boyer和J.Moore提出了一种新的快速字符串匹配算法，即BM算法[3]。BM算法的基本思想是从右向左进行比较。开始时仍是P的最左边与T的最左边对齐，但首先进行Pm与Tm的比较。当某趟比较中出现不匹配时，BM算法采用两条启发性规则计算模式串右移的距离，即坏字符规则和好后缀规则。1)坏字符规则（BadCharacter）P中的某个字符与T中的某个字符不相同时使用坏字符规则右移模式串P，P右移的距离可以通过delta1函数计算出来。delta1函数的定义如下：

2)好后缀规则(GoodSuffix)坏字符规则没有考虑已经取得的部分匹配的情况，而KMP算法却考虑了。该规则将KMP算法和BM算法的思想结合起来，在不丢失真解的前提下确定一个新的移动距离delta2，该函数与样本P有关。具体分以下两种情况，如图1所示。·P中间的某一子串P[j-s+1..m-s]与已比较部分P[j+1..m]相同，可让P右移s位。·P已比较部分P[j+1..m]的后缀P[s+1..m]与P的前缀P[1..m-s]相同，可让P右移s位。满足上面情况的s的最小值为最佳右移距离。delta2的定义如下：d