BM算法的研究与改进.pdfVIP

维普资讯 第 3O卷 第 3期 武汉理工大学学报(骞至差) VoI．30 No．3 2006年 6月 JournalofWuhanUniversityofTechnology June2006 (TransportationScience＆Engineering) BM 算法的研究与改进 闵联营 赵婷婷 (武汉理工大学计算机科学与技术学院 武汉 4300063) 摘要 ：随着 网络 的迅速发展 ，网络安全问题 日益突出，入侵检测技术也成为当今社会关注 的焦点． 对于基于规则的入侵检测来说 ，模式匹配算法非常重要 ，它直接影响到系统的准确性和实时性能． 文 中介绍 了KMP和BM算法 ，对BM 算法的改进进行 了研究，并提出一种改进 的BM算法 ，改进后 的算法极大地提高了匹配速度． 关键词 ：模式匹配算法 ；KMP算法}BM 算法 中图法分类号 ：PP301．6 随着 Internet的飞速发展及 网络规模 El益 的两个是KMP算法和BM 算法．两个算法在最坏 扩大，网络应用趋 向全球化 ，黑客人侵攻击事件也 情况下均具有线性的有哪些信誉好的足球投注网站时间．但在实际使用中， 不断发生．传统 的防火墙技术 已经难 以单独保障 KMP算法并不比最简单 的C库函数StrStr()快 网络的安全，网络入侵检测系统 (networkintru— 多少 ，而BM算法则往往 比KMP算法快上3～5 siondetectionsystem，NIDS)作为一种积极主动 倍．但是BM算法还不是最快 的算法 ，还有很多改 的安全防护技术 ，已成为网络安全领域中研究的 进的BM算法存在，如BMH，IBM算法等等． 热点． 模式匹配问题描述如下． 一 些专 门针对 IDS的攻击使 IDS产生报警泛 正文 P—Pl，P2，…， 洪 ，消耗系统资源，甚至使其瘫痪 ，比如欺骗攻击 、 模式 T—tl，t2，… ，t 崩溃攻击及针对IDS的拒绝服务攻击等．如果IDS (，2》 )要求在P|中寻找等于丁的子串．如果P 中 因受攻击而停止工作，则其保护的网络将暴露在 存在和丁相等的子 串，称为匹配成功，返回子串在 攻击者面前．显然，在研究如何提高IDS的检测全 尸 中的位置 ，否则称为匹配失败，返回0． 面性和准确性 的同时也要增强系统 的安全性 ，保 1．1 KMP算法 证 IDS在受到攻击情况下能正常工作[1]．在入侵 KMP算法的基本思想是将正文P和模式丁 检测系统的实现中，关键 的部分是检测引擎 的实 左端对齐进行 比较，匹配P 和丁，时，若P一71，，则 现．而在检测引擎 的实现 中，关键是数据分析模 继续往前匹配 比较；若尸，≠71，则正文中i不变，模 块．数据分析模块涉及到两个问题 ：如何描述入侵 式中J指向next[j]所指示的位置．next[j]表示当 行为；使用什么样 的算法来快速准确地检测 出入 模式 中第 J个字符与正文 中相应字符匹配失败 侵行为．文中主要探讨第二个问题．对于基于规则 时，在模式 中需重新和正文中该字符进行 比较的 的入侵检测来说 ，模式匹配算法非常重要，它直接 字符的位置 ，这一位置只与模式本身有关，而与正 影响到系统 的准确性和实时性能[2]． 文无关． KMP算法有哪些信誉好的足球投注网站阶段在最坏 的情况下时间复 现有模式匹配算法的分析