一种高效多模式匹配算法及其在NIDS上的应用.pdfVIP

·64 · 计算机应用研究 2006 年 一 种 高 效 多模 式 匹配 算 法 及 其 在 N IDS 上 的应 用 * 徐 宁, 赖海光, 黄 皓 ( 南京 大学 计算机科学与技术 系 计算机软件新技术 国家重点实验 室, 江 苏 南京 2 10093) 摘 要: 提 出了一种基于 BM 算法 思想的、改进 了的多模 式 串匹配算 法, 并且 讨论 了它在 一个 网络入侵检 测 系 统( NIDS) 中的实际应 用情 况。从具体实验 中可 以看到匹配时 间上 的显著改进 。 关键 词: 多模 式 串匹配; BM 算 法; MP2_BM 算 法; 入侵检 测 中图法分 类号 : TP393. 08 文献标 识码 : A 文章编 号: 1001- 3695( 2006) 02- 0064- 03 An Improved Multi-Pattern Matching Algorithm and Its Application on NIDS XU Ning, LAI Hai-guang, HUANG Hao ( State Key Laboratory for Novel Software Technology, Dept. of Computer Science Technology, Nanjing University, Nanjing Jiangsu 210093, China) Abstract: An improved algorithm based on the ideas of Boyer-Moore method to search for multiple patterns is presented. The application of this algorithm in a network intrusion detection system is also discussed. The experiments demonstrate good im- provement in matching time. Key words: Multi-Pattern Matching; BM Algorithm; MP2_BM Algorithm; Intrusion Detection Boyer-Moore( BM) 算法 [ 1] 是一种 著名的单模 式 串匹配 算 chr[ i] 失配时的跳跃距离。Shift 数组的计算方法如下: 法。应用 BM 算法思想到多模式 串匹配领域 必须有效解决下 如果字符 chr[ i] 在 P 中出现, Shift[ hash( chr[ i] ) ] 的值 为 面两个 问题: 如何保 持最好 的 向右跳跃 性 ( 在 多模 式 串情 况 chr[ i] 在 P 出现的最右位置到模式串最右端的距离; 如果字 符 下, 扫描被匹配 目标 串时每次跳过尽可能多的字符 以减少匹配 chr[ i] 在模式串 P 中不出现, Shift[ hash( chr[ i] ) ] 的值就为 m。 次数) 以及如何 处理好 多个模式 串长度 不等的 问题 。对 于前 例如, 假 设 ∑ = { a, b, c, d} , 模 式 串 P = abc, 目标 串 T = 者, Wu-Manber 算法[ 2] 有着较为广泛 的讨 论, 但在 具体 实现上 bbdaabcc, 通 过 上述 方法得 到 Shift [ hash( a) ] = 2, Shift [ hash 牺