葛贤银,韦素媛,杨百龙,蒲玄及

摘 要:基于模式匹配的检测方法是目前入侵检测系统的一种重要方法,因此作为模式匹配方法核心的字符串匹配算法直接影响入侵检测系统的性能和效率。在研究现有算法的基础上提出一种改进的模式匹配算法New-Search算法。该算法以BM算法为基础,通过预处理阶段处理,首末字符部分定位的思想,增加字符跳转距离,比较稳定地减少匹配过程中字符比较的次数,提高了匹配的速度和效率。

关键词:入侵检测;模式匹配;KMP算法;BM算法;New-Search算法

中图分类号:TP311文献标识码:A

文章编号:1004-373X(2009)20-073-03

Research of Improved Pattern Matching Algorithm Based on BM Algorithm

GE Xianyin,WEI Suyuan,YANG Bailong,PU Xuanji

(The Second Artillery Engineering College,Xi′an,710025,China)

Abstract:The detecting method based on pattern matching is an important method in intrusion detection system,the key of this is the efficiency of string matching which influences the efficiency of detection directly.An improved pattern matching algorithm named New-Search which is based on BM algorithm is proposed.This algorithm can increase the jumping distance of characters and decrease the comparison times in matching process through the pretreatment step,which takes the idea of the first and last characters′ partial location.In this case,it improves the matching efficiency.

Keywords:intrusion detection;pattern matching;KMP algorithm;BM algorithm;New-Search algorithm

0 引 言

随着网络技术的发展,网络环境变得日益复杂,对于网络安全来说,单纯的防火墙技术暴露出明显的不足和弱点,如不能提供实时入侵检测能力;对于病毒束手无策等。入侵检测系统是继防火墙和信息加密等安全保障技术之后出现的新一代网络安全防护系统,能够有效地弥补上述安全系统的不足[1]。它通过对算机网络或计算机系统中的若干关键点收集信息并对其进行分析,实时地发现网络或系统中是否有违反安全策略的行为和被攻击的迹象,并采取相应措施以避免攻击的发展或尽量减少攻击造成的危害。按照所采用的检测技术,入侵检测系统可以分为误用检测系统和异常检测系统。误用检测系统使用模式匹配的方法来发现入侵行为,是目前入侵检测系统的主流。所以,作为模式匹配方法核心的字符串匹配算法直接影响入侵检测系统的性能和效率[2]。……