网络入侵检测系统中模式匹配算法的研究与改进

网络入侵检测系统中模式匹配算法的研究与改进母

王德正

合肥工业人学计算机与信息学院，安徽合肥２３０００９

摘要：入侵检测是网络安全的最后一道防线，模式匹配算法是基于特征匹配的入侵检测系统的核心算法，模式匹配的效率决定了该类入侵检测系统的性能。本文对模式匹配算法进行综述，对各种单模式匹配算法和多模式匹配算法进行了性能分析，提出了改进模式匹配算法一Ｎ刚ｓＡ算法，实验表明该算法具有较高的效率。

关键词：入侵检测系统模式匹配算法多模式匹配算法

』，Ｉ引言

随着Ｉｎｔｅｒｎｅｔ的飞速发展及网络规模的日益扩人，网络应，｝｛ｊ趋向全球化，黑客入侵攻击事件也不断发生。传统的防火墙技术已经难以单独保障网络的安全，网络入侵检测系统（ＮｅｔｗｏｒｋＩｎｔｒｕｓｉｏｎＤｅｔｅｃｔｉｏｎＳｙｓｔｅｍ，很重要的意义。

２模式匹配的定义

所谓模式匹配是指：已知长度为ｎ的文本字符串：Ｔ＝ＴＩＴ２Ｔ３…Ｔｎ和一长度为ｍ（ｍ＜ｎ）的模式字符串：Ｐ＝时，可以直接采用强行搜索算法，其实质就是将模式Ｐ和文本Ｔ从左至右逐个搜索，若在某一位匹配失败，则将模式Ｐ向右移动一位，仍从模式Ｐ的第一位开始搜索。这种算法虽然可以保证正确性，但显然效率不高，

。

，

．｝

‘

：３单模式匹配算法

顾名思义，该算法每次只处理一个模式。常见的单模式匹配算法有ＫＭＰ（Ｋｎｕｔｈ．Ｍｏｒｒｉｓ．Ｐｒａｔｔ）算法、ＫＭＰ算法。

ＫＭＰ算法是由Ｄ．Ｅ．Ｋｎｕｔｈ与Ｖ．Ｒ．Ｐｒａｔｔ和Ｊ．Ｈ．Ｍｏｒｒｉｓ同时发现的。该算法的时间复杂度为０（ｎ＋ｍ）。该

‘，ＮＩＤＳ）作为一种积极、主动的安全防护技术，已成为网络安全领域中研究的热点。在很多的商业入侵检测产品中，都采用了模式匹配算法，其实质就是字符串匹配。冈此，对字符串匹配算法进行深入地研究具有ＰＩＰ２Ｐ３…Ｐｍ，求Ｔ中是否存在长度为ｍ的子串：Ｔｉ．附ＩＴｉ－ｍ＋２Ｔｉ＿ｍ＋３．．．Ｔｉ使得Ｔｉ－ｍ＋ｊ＝Ｐｊ，ｊ＝１，２，３…，ｍ。ｉ９．ｍ。当ｎ不很大在最坏情况下需执行（ｎ．ｍ＋１）木ｍ次字符匹配检查，其时间复杂度为Ｏ（ｍ，－ｃｎ）。ＢＭ（Ｂｏｙｅｒ－Ｍｏｏｒｅ）算法等。其中，较经典的ＢＭ算法由于使用了启发式搜索，能够在搜索时跳过大部分文本，从而使得执行效率得到很大地提高，冈而在ＩＤＳ中运用最为广泛。３．１算法的改进土要有：每当一趟匹配过程中出现字符不匹配时，不需要同溯指针，而是利用己经得到的部分匹配结果，将模式尽可能向右移动后，继续进行比较。

’作者简介ｔ王德正（１９７５．）．男，汉族，安徽泗县人。讲师，硕士研究生，研究方向为计算机网络安全。

ＫＭＰ算法首先对模式串进行预处理，设置一个与模式串长度（ｍ）一致的整数数组ｎ“ｔｆｌ。数组ｎｅｘｔ【ｉ】中保存着一个整数ｋ（ｋ＜ｉ），使得模式ｐ开头的ｋ字符与Ｐ【ｉ】前的ｋ个字符相等。即字符串‘‘ｐ【ｏ】，ｐ【ｌ】．．ｐ【ｋ－１】”与字符串“Ｐ［ｉ－ｋ］，Ｐ［ｉ－ｋ一臻，．Ｐ［ｉ一玎’相遥配。其ｎｅｘｔ蝤数的定义为：’‘

＜

ｎｅｘｔ［ｉｌ＝ｑ№ｏ当啡其㈦瞅黼时ｋ况鼠ＰＯＰｋ＝Ｐｋ＾Ｐ

具体过程是先设置ｎｅｘｔ［０］＝ ｌ，然后假定ｎｅｘｔ［ｉ－１】－ｋ则：

（１）若Ｐ［ｋｌ＝Ｐｉｉ－ｌ】则ｎｅｘｔ［ｉ］＝ｋ＋ｌ，跳出；

（２）若Ｐ［ｋｌ！＝Ｐ［ｉ－１］则ｋ＝ｎｅｘｔ［ｋ］若ｋ＝一ｌ则ｎｅｘｔ［ｉ］－－０，跳出；否则返回笫一步继续处理。

一若模式串与主Ｅ文之闻出现多处部分匹配，该算法能有效摇嵩处理速度；若部分匹配出现缀少。箕速度提高并不明显：’。

３．２ＢＭ算法

ＢＭ算法‘’’是一种单模式精确匹配算法，爆著名的开放源代码的入侵检测系统ｓｎｏｒｔ就采用了ＢＭ算法。ＢＭ算法剥用启发式荣略，跳过不必要的比较．减少了摸式串与文本输入串的比较次数，提亮了匹配效率。

对于单一模式串的匹配，ＢＭ算法的效率是很高。然而，随着入侵方式、方法的不断演变，入侵检测的匹配规剧也：急剧增穰。仅仅经翔ＢＭ算法进｛亍字符串匹配，在匿配的遵度土是远远不够姥。在遴行扮议分轿之后．根据规则之间存在的荧联性，采用在多模式匹配中建立规则树技术，可大幅减少匹配次数。提高躁配速度。’７

４多模式匹配算法

在对多模式算法进行研究前，可对多模式匹再己闯题作如Ｆ描述：

设模式集ｐ＝｛ｐｌ，Ｐ２，Ｐ３…Ｐｋｌ，Ｐｉ为模式集中的一个模式，模式中字簿取自确定的字母表∑。犬文本Ｔ＝ｔｌ，ｔ２。．－ｔｎ，ｔｉ为一个文本块，也由∑中的字符组成。问题可归纳为：找出大文本Ｔ中模式Ｐ的所有匹配。常见的多模式匹配箨法眷ＡＣ算法、ＡＣ．ＢＭ算法等。

４．１ＡＣ算法

Ａｈｏ－Ｃｏｍｓｉｃｋ（简称ＡＣ）口１自动机匹配算法基于一种精巧的模式树（Ｔｒｉｏ。模式树是摆具备如下性质的一棵树Ｋ：。

（１）Ｋ的每 …… 此处隐藏：4572字，全部文档内容请下载后查看。喜欢就下载吧 ……