一种快速的基于BM模式匹配的改进算法

模式匹配算法是入侵检测系统(IDS) 中非常重要的一种算法. 在研究和分析几种常用模式匹配算法的基础 上, 提出一种快速的基于BM(Boyer-Moore) 模式匹配的改进算法—–IBM 算法. 该算法充分利用模式串的末字符和 末字符所对应的文本串的后两字符的唯一性, 同时参考文本串本身的信息来提高模式串的移动量, 使得每次失配后, 在保证不丢失匹配成功可能性的前提下尽可能多地向后跳跃. 实验结果表明, 该算法相比其他模式匹配算法, 在检测 性能和匹配效率上均具有很大优势, 并且能够有效地提高IDS 的检测效率和性能.

A fast improved pattern matching algorithm based on BM

The pattern matching algorithm is a very important method in the intrusion detection system(IDS). Through analyzing and studying the characteristics of the BM(Boyer-Moore) algorithm and BMHS algorithm, an improved algorithm based on BM(IBM) algorithm is proposed. IBM algorithm integrates the merits of other pattern matching algorithms. The IBM algorithm takes full advantage of the uniqueness of the last character of the pattern string and its corresponding to the next two characters of text string to determine the moving distance of the pattern string. Meanwhile, it also takes into account the information of text string itself to increase the amount of move of the pattern string as much as possible, when the text string and pattern string are mismatch. Theoretical analysis and experimental results show that the IBM algorithm can significantly decrease the moving time and shorten the pattern matching time than other pattern matching algorithms, and can effectively improve the detection efficiency and performance of the IDS.