bm算法与其改进算法分析

《bm算法与其改进算法分析》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、农业网络信息·信息教育·2014年第1期AGRfC【【【．ⅡEⅣETDRK【阳R埘ATTOⅣBM算法与其改进算法分析燕红文，杨怀卿(山西农业大学信息科学与工程学院计科系，山西太谷030801)摘要：随着网络入侵检测技术的快速发展，入侵行为的检测算法也日益重要。本文对目前常见单模式匹配算法进行分析总结，以经典的单模式匹配算法为例，分析了其详细的实现过程。并以此为基础，分析了修改后的单模式匹配算法的优缺点，对该算法的继续改进提供了一定的参考意见，指出了单模式继续改进的方向。关键词：BM；模式匹配；单

2、模式；BMH中图分类号：TP315文献标识码：A文章编码：1672—6251(2014)01—0124—03AnalysisonBMandRevisedAlgorithmYANHongwen，YANGHuaiqing(CollegeofInformationScienceandEngineering，ShanxiAgriculturalUniversity，ShanxiTaign030801)Abstract：Thedetectionalgorithmofintrusionbehaviorsha

3、sbecomeincreasinglysignificantwiththerapiddevelopmentofnetworkintrusiondetectionsystem．Thispaperanalyzedandsummarizedthecurrentcommonsingle-patternmatchingalgorithm．Takingtheclassicsinglepatternmatchingalgorithmasexample，weintroducedtheimplementation

4、processofthealgorithmindetail．Onthebasis，thispaperindicatedtheadvantagesanddisadvantagesofrevisedsingle-patternmatchingalgorithm，andprovidedthesuggestionsanddirectionsofthefurtherrevision．Keywords：BM；PatternMatching；single—patern；BMH当今社会。Internet技术高速

5、发展，网络应用规模究其数据分析模块．也就是说第一需要描述出什么样逐渐扩大，并且全球化程度越来越高，随之而来的是的入侵行为，第二是使用何种算法来对入侵行为进行黑客入侵越来越频繁，信息安全问题日趋严重，信息检测。现讨论对于入侵行为的检测算法。选择合适算被泄露、被纂改的情况越发普遍。鉴于此，常规的防法非常重要，它直接影响到系统的准确性和实时性能llJ，范方法是建立防火墙。这是一种被动防御，单独的被检测算法中主要涉及到模式匹配算法，比较著名的算动防御是不能够保证信息安全的。而主动的安全防御法有KMP、B

6、oyer—Moore、BMH、遗传算法，免疫系技术已经是大势所趋，网络入侵检测(networkinstru—统，专家系统，神经网络，贝叶斯定理等算法嘲，可以siondetection)技术就是信息安全领域的一种热点技将其分为两大类多模式匹配算法和单模式匹配算法，术。随着检测技术的发展，攻击技术也在高速发展，本研究将着重介绍单模式匹配算法．详细分析算法思有一些攻击的目标性很强，是指向入侵检测系统的，路。以此为基础，为以后算法的改进提供一定的参考会造成检测系统频繁报警而造成系统资源的浪费，严意见。重

7、的情况会使系统瘫痪或者是系统崩溃，进而产生不1BMfBoyer-Moore1算法可估量的损失。所以在提高入侵检测系统的准确性时BM算法是在1977年有Roberts．Boyer和J也要增强系统本身的安全性，确保检测系统在收到大StrotherMoore提出的一种可以O(n)时间复杂度内，量攻击的前提下可以顺利的工作。一个检测系统其最能够完成字符串匹配的算法，它的效率在大多数场合关键的部分是检测引擎，在检测引擎当中，主要是研都要高于著名KMP算法。下面详细分析这一匹配算基金项目：山西农业大学科技创

8、新基金项目(编号：201318o作者简介：燕红文(1979一)，男，博士，讲师，研究方向：信息教育。通信作者：杨怀卿，硕士，副教授，硕士生导师，研究方向：信息科学工程。收稿日期：2013—11-27·-——124-——《农业网络信息》2014年第1期信息教育法。接把这将匹配成功的地方对齐，并且要使该部分有尽BM算法之所以能够在单模式匹配中有出色的表可能大的幅度嘲。现，是因为该算法用了两个跳转表，一个定义为坏字BM算法由于采用了坏字符表，它可以使用“跳符表delta1．一个定义为好后缀表Delta