入侵检测系统中模式匹配算法的研究及改进.pdf

2 计 算 机 技术 与 发展 VoI．20 No．2 第 0 期 2010 2 Feb． 2010 年 月 COMPUTERTECHNOI~GYANDDEVELOPMENT 入侵检测系统中模式匹配算法的研究与改进 陶善旗，李 俊，郭伟群，李海龙 (南京航空航天大学信息科学与技术学院，江苏 南京 210016) 摘 要：人侵检测系统的性能很大程度上取决于规则检测的效率，模式匹配算法是规则检测引擎的核心算法。对模式匹 配算法进行了研究，重点分析了多模式匹配算法wu—Mal~r算法。针对wu—Manber算法在单字节模式串下移动距离 短的不足，并结合网络数据包和入侵检测系统中规则的特点，提出了一种适合入侵检测系统的改进的模式匹配算法。该 算法利用位示图方法解决了单字节模式串匹配的问题，增加了移动距离，提高了检测数据包与规则匹配的速度，提升了系 统运行的效率。 关键词 ：入侵检测系统；模式匹配；wu—Manber算法 中图分类号：TP393 文献标识码 ：A 文章编号：1673—629X(2010)02—0167—04 ResearchandImprovementofPatternMatchingAlgorithm forIntrusionDetectionSystem TAOShan—qi，LIJun，GUOWei．qun，LIHai—long (CollegeofInfo．Sci．andTeehn．，NanjingUniv．ofAeronauticsandAstronautics，Yanjing210016，China) Abstract：Performanceoftheintrusiondeteciionsystem isdeterminedbyefficiencyofruledetection．Patternmatchingalgorithmisoneof thecoreMgofithmsinthedetcetionengine．Aresearchofthepatternmatching algorithm isdescribedinthisthesis．ForthelackofWu— Manheralgorithm ’smovedistanceinsingle—bytepatternsituation。andthefeaturesofnetworkpacketsandcharacteristicsofIDS，pre— sentde animprovementofthe胁 一Manheralgoritmh whichsuitableforIDS．刃雄 improvementalgoritmh solvestheproblemofstring matchinsingle—bytepatternsituationusing bitma p，in口寰略 thedistanceofnlov~，)。e凼 thedetectionof~ kets，map~．,estheefficiency． KeyWOI~ IIDs；patternmatching ；W u—Manberalgoritmh O 引 言 符转移机制，但在计算跳跃距离时利用了块字符，扩展 文中主要研究多模式匹配算法WU—Manber算 了不良字符的转移效果来解决BM算法中跳跃距离变 法，针对Wu—Manber算法的不足，并结合算法在入侵 小的问题。 检测系统中的应用，改进了算法性能，提高了人侵检测 预处理阶段，构造 了3个表：Hash表，Shift表和 系统的规则检测效率。