文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 工程科技 > 信息与通信 > 入侵检测系统中的模式匹配算法研究
侵权投诉

入侵检测系统中的模式匹配算法研究

综述入侵检测系统中的模式匹配算法,包括经典的单模式匹配算法KMP算法、BM算法和多模式匹配AC算法。在此基础上提出一种改进算法——两端分段匹配算法,并加以验证,最后指出改进模式匹配算法效率的研究方向。

罗金玲 .罗仁:侵检测系统中的模式匹配算法研究刘入 ( )转移函数,,表示从当前状态 s开 3是 g 符的相同位置上;如果在当前的深度上,目标字符没有出现在任何模式中,则模式树的偏移量为树中最短模式的长度。好前缀移动的移动策略为:将模式树移动到一个已被发现是另一个模式子串完全前缀的下一个位置 .或者移动到作为树中另一个模式后缀能够正确匹配目标串的某个前缀的下一个位置。在

始,沿着边上标签为 n的路径所达状态。假如,)边 上的标签为 0那么 u,,;果根节点上出来的如边上的标签没有 a则 go=,, (, 0即如果没有匹配的 字符出现,自动机停留在初态。

( )也是转移函数,示不匹配时自动机的状 4厂表态转移。该函数定义为; )当是£ ) , 最长真后缀并且 W是某个模式的前缀,么 )那就是以为标 签的那个节点。

模式树的移动过程中 .必须确保模式树的偏移量不 能大于树中最短的模式长度。 23两端分段匹配算法 .

( )。 5 q∈Q是初态 (根节点,标识符为 O。 ) ()

6 F是终态集(以模式为标签的节点集1。 于是。目标串中查找模式的过程转化成在模在式树中的查找过程。查找一个串时从模式树的根

基于 B单模式算法和 A M C多模式算法本文提 出一种快速两端分段模式匹配算法,法描述如下:算 ( ) P与左端对齐 . 1将进行 B匹配。如果一 M次性匹配成功,则称为完全匹配,返回结果;如果≠时将提出作为 L, L=尸,,。 即 1{ l…} () 2将+ 1向下进行匹配,到不等时分段。遇 () 3由多次 ( ) ( ) 1、2步骤得,:…,。,

节点开始。沿着以 7中字符为标签的路径往下走。 1 若自动机能够抵达终态,则说明 7中存在模式£ 1 )否则不存在模式。;

A C算法模式匹配的时间复杂度是 0/, (1并且与 2

( ) 7分为 t t…,个子集,中{,,, 4将 1 12,, t 其 tt… 12 t∈∑。 }

模式集中模式串的个数和每个模式串的长度无关。 无论模式串 J是否出现在目标串 7中。中的每个 p 1 字符都必须输入状态机中。因此无论是最好情况还

() 5将,…, J£, 在,,, j t… f中进行多线 程 A C匹配。回匹配结果。返

是最坏情况, C算法模式匹配的时间复杂度都是 O A ㈤,包括预处理时间在内, C算法总时间复杂度是 A OM+ )其中为所有模式串的长度总和。 ( n, 22 A— M算法 . CB对多模式串匹配而言。 C算法比 B算法高效 A M

下面进行算法测试与分析。 实验机配置: P 4 .;内存 2 6;硬盘 C U P 20 5 MB 4 G操作系统 R d a Ln x .。为了测试本文所 0 B: e H t iu 90

提算法的效率,网络中随机捕获 10在 0 MB数据。从经典入侵检测软件 S ot式库中随机地抽出模式 n r模

得多, A但 C算法必须逐一查看目标串的每个字符, 即必须按顺序输入,能实现跳跃。 B算法则能不而 M够利用“滑”过目标串中的大段字符,而提高右跳从搜索速度。如果将 B算法的这种启发式搜索技术 M应用到 A C算法中 .则可大大提高多模式匹配算法 的效率。

字符串来进行实

验测试。这些值都是利用 Ln x操 iu作系统本身的 t命令所获得。 i me 表 1单模式字符串匹配时间 S

A— M算法是 Jn o g 19 CB a g n在 9 3年结合 A算 J c法的有限自动机和 B算法的连续跳跃思想提出来 M 由表 l见,当比较单字符串时,字符串越大可

的新算法,利用劣势移动表和优势跳转表来实现跳 跃式地并行搜索,算法的时间复杂度为 Om )该算 (n。法的思想是:首先把要查找的多个模式构成一个关键字树,相同的前缀作为树的根节点。模式树从把目标串的右端向左移动,旦模式树确定在适当的一

B所花费的时间越少 .因为 B算法是采用的是 M M

“步”跳思想的算法,式串越长期匹配的速度越快。模 本算法采用了分段技术。受字符串长度的影响,不无

论字符串长短,匹配速度影响不大。 由表 2可见,比较多字符串时,符串数目越当字多 B算法花费的时间越多,而对 A M C算法的影响不大,本算法的影响也不大。对因为 B算法只是单 M模式匹配算法当字符串数目增多时,匹配速度自然 随之增大。而多模式的 A C算法则不受字符串数目

位置,符比较从左向右开始进行。模式树移动时字同时使用坏字符移动和好前缀移动。坏字符移动的 策略为:如果出现不匹配的情况,动模式树,移使得树中其他模式中能与当前目标串正在比较的字符相匹配的那个字符移动到与当前目标串正在比较的字

的限制。本算法由于结合了 B和 A M C算法的优点 .

1 61

入侵检测系统中的模式匹配算法研究

上一页第3页

你可能喜欢

热门文档

相关文档

  • 【论文】入侵检测系统中模式匹配算法研究

    入侵检测系统中模式匹配算法研究_专业资料。分析了BF,KMP,BM模式匹配算法,在此算法的基础上提出了一种改进的模式匹配算法(FBM),该算法的思想是对BM算法中滑动距离...

  • 【论文】入侵检测系统中模式匹配算法的研究

    入侵检测系统中模式匹配算法的研究_专业资料。互联网的开放性为信息共享和交互提供了极大的便利,但随之而来的网络安全问题也日益明显.入侵检测作为一种主动的信息...

  • 入侵检测系统中模式匹配算法的研究

    入侵检测系统中模式匹配算法的研究 摘要 入侵检测是网络安全的最后一道防线,模式匹配算法是基于特征匹配的入侵检测系统中的核心算法, 模式匹配的效率决定这类入侵检测...

  • 【论文】网络入侵检测系统模式匹配算法研究

    网络入侵检测系统模式匹配算法研究_专业资料。模式匹配算法是网络入侵检测中的关键所在,它直接影响到网络入侵检测系统的实时检测性能。引入4种模式匹配算法,分析其工作...

  • 入侵检测中模式匹配算法的研究

    在此基础上提出了一种 (, 改进的模式匹配算法应用于我们的系统实现中。实验结果表明, 改进的模式匹配算法, 更适合于网络级入侵检测的实现, 减少了系 统的丢包率...

  • 【论文】入侵检测模式匹配算法研究

    入侵检测模式匹配算法研究_专业资料。综述了入侵检测模式匹配算法,包括Brute Force算法、Knuth-Pratt-Morris算法、Boyer-Mooer算法、Aho-Corasick算法、Set-wise Boyer...

  • 【论文】入侵检测模式匹配算法的研究与改进

    入侵检测模式匹配算法的研究与改进_专业资料。模式匹配算法是实现基于规则检测的核心技术,其效率直接影响到入侵检测系统的准确性和实时性。通过分析传统的模式匹配算法...

  • 【论文】入侵检测系统中模式匹配算法的改进

    网络技术的飞速发展给入侵检测系统提出新的挑战,需要通过各种途径来提高系统性能,而模式匹配算法的优劣直接影响到入侵检测系统的核心模块——规则匹配模块的运行效率。...

  • 【论文】网络入侵检测系统中的模式匹配算法优化研究

    网络入侵检测系统中的模式匹配算法优化研究_专业资料。在网络安全问题的研究中,模式匹配是网络安全入侵检测中一种常用检测算法,由于网络规模越来越大,传统的模式匹配...

  • 【论文】入侵检测系统中BM模式匹配算法研究

    入侵检测系统中BM模式匹配算法研究_专业资料。模式匹配算法是基于规则的入侵检测系统的核心。基于BM模式匹配算法研究,可对其进行改进。改进算法有效地加快了模式匹配的...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email