基于bm算法的无需预处理的双向匹配算法的研究与实现

《基于bm算法的无需预处理的双向匹配算法的研究与实现》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、基于BM算法的无需预处理的双向匹配算法的研究与实现基于特征匹配技术的入侵检测系统的速率和效率常常依赖于模式匹配算法的精确性，而算法的效率又依赖于算法的选择和实现方式。随着X络技术的发展，匹配算法优劣有可能成为入侵检测系统的瓶颈，因此要提高入侵检测系统的性能必须对原有算法改进或提出新的算法，本文在对经典BM算法分析、研究的基础上，对该算法进行了部分改进，并给出了基于该改进的新的匹配算法。关键词：入侵检测系统；模式匹配；BM算法1.引言入侵检测[1]系统的研究是当前X络安全研究的一个比较新的领域，入侵检测系统作为主动防护系统是构成X络安全防护体系的主要方面之一。目前比较成熟的是基于特

2、征匹配的入侵检测系统，而特征匹配的实质就是字符串匹配问题，即在分组的有效负载或重组后的报文中找到入侵特征字。随着X络应用的日益增长和大量应用层软件的开发，NIDS的设计者必须设法提高攻击分析技术，必须提高对各种入侵模式的特征匹配速度，以适应X络速度的提高和X络流量的增加。因此用高速的匹配算法来分析数据、监控X络就显得格外重要。2.BM匹配算法匹配算法是检测X络攻击的关键，它直接影响系统的实时性能。在对X络数据包搜索入侵特征时，需要一个有效的字符串搜索算法。基本任务就是把存放在入侵检测系统规则集中的己知入侵规则与系统正在检测的X络数据包进行匹配，如果匹配成功则可以断定发生入侵。BM

3、算法是模式匹配算法中的经典算法，广泛应用于入侵检测系统。BM[4]假设前提条件：设M为要匹配的某种模式，T为数据包中的净荷，也就是要进行匹配的文本，模式M的长度为j，文本T的长度为k，(一般地，k>=j)。M从第一个字符到最后一个依次记为M1，M2，……，Mj，T从第一个字符到最后一个依次记为T1，T2，……，Tk。如果对于给定的偏移量s，每个字符Mi∈M1……Mj，匹配相应的字符Ti+s∈T1……Tk，则M位于T中偏移量为s的位置，记作Ti+s…Tj+s=Mi…Mj模式匹配的算法有很多种，如BF算法、KMP算法等，在BF算法中，当文本串T中有一子串与模式串M的一部分相同时

4、，匹配就会碰到回溯的过程，这样就使比较的次数大大增多。而KMP算法有时效率也不是太高。为了改变BF及KMP算法的缺陷，充分利用上次匹配比较中已经得到的部分匹配结果，1977年，RobertBoyer和L.Moore发表了一种新的精确字符串匹配算法，这种算法就是Boyer-Moore算法，简称BM算法。BM算法是应用中较为快速的模式匹配算法，并且被大多数IDS所采用。有实验数据表明，BM算法的匹配速度大约是KMP算法的3～5倍。Boyer-Moore算法的主要思想是：假设将正文T中自位置i起往左的一个子串与模式M进行自右向左的匹配比较中，若发现不匹配，设匹配不成功发生在模式串中的位

5、置为q，则下次应从正文的第i-(j-q)+dist[c](在这里c=Ti-j+q)位置开始重新进行匹配，相当于把模式P向右“滑动”一段距离，也就是跳过dist[c]-(k-q)个字符而无需比较。显然，若字符“c”不出现在模式中或仅仅出现在模式的末端，则模式从匹配失效位置开始向右滑动最大的距离j。又因为在实际的应用中，正文中大部分字符根本不出现在模式串中，因此应用BM算法可以大大加快查找及匹配速度。BM算法的关键是，对于给定的模式M=M1M2…Mj，定义一个从字母到正整数的映射：　dist[c]-->{1，2，…，j}。这里，c∈Σ(Σ为正文T中所有可能的字符集，在这里我们假

6、设Σ为26个英文字母的集合)。dist称为滑动距离函数，它也是BM算法的关键。dist函数给出了正文T中可能出现的任意字符c在模式M中的位置。具体定义如下：算法实例模拟，假如模式P和正文T如下：M1MjP：VIRIST：HERE/HAVE/A/VIRILEUS/VIRIST1Tk利用BM算法执行的步骤为：(1)先计算滑动距离函数dist的值。在本例中，模式串的长度为5，dist[“I”]=1(虽然M2和M4都是字符“I”，但根据定义i应取4，那么j-i就是1，所以dist[“I”]=1)，dist[“R“]=2，dist[“V”]=4，除上述3个字符外，其余字符的dist函数值都

7、为5。(2)开始匹配：①VIRISHERE/HAVE/A/VIRILEUS/VIRIS此时，M5=“S”，T5=“/”，M5≠T5，又因为i0=5，dist[“/”]=5，故应向右滑动5个字符位置，即从第10(i0+dist[“/”])个位置开始比较。②VIRISHERE/HAVE/A/VIRILEUS/VIRIS此时，M5=“S”，T10=“/”，M5≠T10，又因为i1=10，dist[“/”]=5，故应继续向右滑动5个字符位置，即从第15(i1+dist[“/”])个位置开