多模匹配算法AC_BMHS的研究与改进  

RESEARCH AND IMPROVEMENT OF MULTI-MODE MATCHING ALGORITHM AC_BMHS

作　　者：周延森[1] 康艳梅[1] 

机构地区：[1]国际关系学院信息科技系

出　　处：《计算机应用与软件》2012年第10期304-307,共4页Computer Applications and Software

摘　　要：模式匹配算法是影响入侵检测系统性能的关键所在。首先分析主流的单模匹配算法BMSH和BM2算法,将多模匹配算法AC和BMSH结合,得到AC_BMSH算法。对AC_BMSH算法进行分析,指出AC_BMSH算法在匹配中存在两个缺陷:失配时单字符决定移动的距离短和模式串树最大移动距离小;针对AC_BMSH算法的不足,提出一种改进的有更好平均移动距离的多模式匹配算法Improved AC_BMSH(I_AC_BMSH)算法。改进算法采用双字符决定移动距离,失配时扩大模式串树最大移动距离。实验结果表明改进算法I_AC_BMSH相对于AC_BMSH算法有更好的匹配效率。Pattern matching algorithm is the key to affect the performance of intrusion detection system. In this paper we firstly analyse the mainstream single-mode matching algorithm BMSH and BM2 algorithms, derive the AC_BMSH algorithm by combining multi-mode matching algorithm AC with BMSH. On the basis of analysis of AC_BMSH algorithm, we then point out two defects the AC_BMSH matching algorithm has while matching, which are the shorter moving distance determined by single character and the smaller max moving distance of pattern string tree. In order to solve the deficiency of the AC_BMSH algorithm, we propose an improved muhi-mode matching algorithm, improved AC_BMSH （I_AC_BMSH） algorithm, which has better moving average distance. The improved AC_BMSH algorithm adopts double characters to determine the moving distance and expands maximum moving distance of pattern string tree when mismatch. Experiments result shows that I_AC_BMSH algorithm performs better than AC_BMSH algorithm in matching efficiency.

关 键 词：模式匹配 单模匹配 多模匹配 移动距离 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]