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

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

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

罗金玲,罗仁:刘入侵检测系统中的模式匹配算法研究比较 P与; m当某趟比较时与模式串的对应字 常快,实际比较次数只有目标串长度的 2%~ 0 0 3%。

符不匹配,将模式串右滑距离 d,则 )执行由 P m与 + ) d起始的自右至左的匹配检查。 M算法采用两 B条规则计算模式串右移的距离:后缀移动和坏字好符移动。 ( )后缀移动, 1好分两种情况。

2多模式匹配算法 与单模式匹配算法相比,多模式匹配算法的优势在于一趟遍历

可以对多个模式进行匹配 .从而大大提高了匹配效率。对于单模式匹配算法,如果要匹配多个模式,么有几个模式就需要几趟遍历。那当然多模式匹配算法也适用于单模式的情况。在人侵检 测系统中,一条入侵特征可能匹配或部分匹配很多

第一种情况, P已比较部分 P[ I当 j…m]+与其 中间的某一子串尸 +…m]同,移 s,[ l 相 P右位 如图 1所示

条规则。如果采用单模式匹配,匹配每条规则时都在 串

需要重新运行匹配算法,率很低。然而。效日益增多 1 jl+ m

的网络攻击使得入侵检测的规则数目仍在不断增

本比[二l_次较 串 P.次比较下

长,因此,纯提高单模式匹配算法的效率,单很难使 入侵检测系统满足越来越大的网络数据吞吐量和日 益增加的攻击。

图 1右滑距离 sj<

目前比较常见的多模式匹配算法有 A oC rs k h - oai c

第二种情况,当 P已比较部分 P U I +…m] 的后缀 Psl[+…m] P的前缀 P 1与[…m—]同, s相 P右 移 s .图 2示。位如所 1 n

算法、h- O ai - oe- o r算法、 n e- A oC rs k B y rM oe - c Mab rWu算 法和 S0Wi oe M oeH sol e s B yl o r opo算法。 e - - 21 A . C算法 A C算法于 l7 9 5年产生于贝尔实验室,最初用于图书馆的书目查询程序。该算法基于有限状态自

串

动机 (S 1在进行匹配之前先对模式串集合 S FA, P进 串 P.次比较本 串 P.次比较下 m s

行预处理,成模式树(形树形 F A, S )然后只需对目标串扫描一次就可以找出所有与其匹配的模式串 P。模式树的构成如图 3示,其中圆圈表示节所点,双圈是根节点,上的字符就是该边的标签,边填

图 2

右滑距离 s

取满足上述两种情况的 S最小值作为移动距

充点圈的标签就是各个模式。

离,因此可以定义一个距离函数 D: ) D1)mi(l+…m = ns l】 =+…m—】力 l s&& ≠一]s )+…m] 5(, 2 耶 =

f ] .m .

( )字符移动。 2坏 P中

的某个字符与中的某个

字符不相同时使用坏字符移动。右滑距离函数 D ) 定义如下: 图 3模式树

m, n tnP) ( o 或 i

在预处理阶段,模式树的各个节点作为状态,根 节点作为初态。标签为模式的节点作为终态,利用转向函数 g和失效函数厂为转移函数,将模式树扩作展成一个树型有限自动机。由模式树扩展所得的

(=且≠ (≤≤m一 ) 1 1) D= )

mj= af x1≤m 1 -, mx l, j ̄= 一} 其他情况

匹配时取移动距离为:= a{ )D J dm x D,z。文献证 明算法需要的预处理时间为 D+ )最坏运行时间 ,为 0[ m+ ) ]即扫描部分运行时问为 O[ - )一 1 m, ( m n

A自动机肘是一个六元组, (,,,,o: C Q∑ gf q, () 1Q是有限状态集(式树上的节点)模。

() 2∑是有穷的输入字符表(数据包中可能出现 的所有字符)。

m]。在大字母表(对于模式长度)相情况下,M算法非 B

1 O 6

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

上一页第2页

你可能喜欢

热门文档

相关文档

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

    入侵检测系统中模式匹配算法研究_专业资料。分析了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