综述入侵检测系统中的模式匹配算法,包括经典的单模式匹配算法KMP算法、BM算法和多模式匹配AC算法。在此基础上提出一种改进算法——两端分段匹配算法,并加以验证,最后指出改进模式匹配算法效率的研究方向。
第 1 2卷第 2期
重庆科技学院学报 (自然科学版 )
21 0 0年 4月
入侵检测系统中的模式匹配算法研究 罗金玲刘罗仁 (娄底职业技术学院,底 4 7 0 )娄 1 0 0
摘要:综述入侵检测系统中的模式匹配算法,包括经典的单模式匹配算法 K MP算法、M算法和多模式匹配 A B C算法。在此基础上提出一种改进算法——两端分段匹配算法,加以验证,并最后指出改进模式匹配算法效率的研究 方向。 关键词:侵检测;式匹配; MP算法; M算法; C算法;端分段匹配算法入模 K B A两
中图分类号:P 0 T31
文献标识码: A
文章编号:6 3 18 (0 0 0— 19 0 17— 9 0 2 1 )2 0 5— 4
入侵检测系统产生于传统安全策略无法满足日 益苛刻的安全需求的情形下,是一种主动保护自它 己免受攻击的网络安全技术,继防火墙、是数据加密
的基础上提出了一种快速模式匹配算法,称为 K MP 算法 l1 3。该算法克服了 B, 4 F算法的目标串指针在多个字符比较后相等时,只要有 1个字符比较不等便
等传统安全保护措施后的新一代安全保障技术。模 式匹配算法是基于特征匹配的入侵检测系统中的核心算法。据统计,现在大约 9%的入侵检测都是特 5征匹配的人侵检测。由此可见,式匹配算法性能模的优劣直接影响到入侵检测系统的效率。在此介绍几种用于入侵检测的经典模式匹配算法 .在此基并础上提出一种入进算法 .后给出人侵检测系统中最模式匹配算法的选择策略。
需要回溯的缺点 .使算法效率得到了大幅度提高 .时 间复杂度达到最理想的 0 f n,空间复杂度是 D m+ ) () m。 K MP算法的基本思想是:某趟匹配过程中若和不匹配,而前卜1个字符已经匹配,时只需右此移模式串 P目标串不动,,即指针 i回溯,不让与继续比较,动后重新开始比较的位置后仅与移模式串 P有关,与目标串无关,而 因此 k可以通过下面的 n x函数事先确定。 et 定义 n x[1 et函数为: j
1单模式匹配算法 () 1模式匹配。在给定长度为凡的目标串
中 查找长度为 m的模式 P首次或多次出现的过程, ,
m xklkj且 P…: a{l<,< 2 n x ̄= et] 0 一
∥‘。‘ )一
集合非空其他情况 j o时=
1≤凡P;≤≤m。若 P在中出现 1或≤i,_ 1 次
多次,则称匹配成功,否则称匹配失败。
1标记 ) (
() 2单模式匹配算法。目标串中一次只能对 1在 个模式串进行算法匹配。
12 B算法 . M
相对于 B F算法, MP算法虽然消除了主串指 K 针的回溯,不匹配时能使模式串右滑若干位。由在但上述 n x函数可知。滑的最大距离不会超过 1趟 et右匹配操作所进行的比较次数原因在于 K MP算法的匹配操作是从左到右进行的。到 K受 MP算法的启
( )模式匹配算法。在目标串中可同时对多 3多 个模式串进行算法匹配。
高效的模式匹配算法都是设法增大不匹配时目 标串或模式串 P之间的偏移量,以减少总比较次数。下面介绍两种经典的快速单模式匹配算法。 11 K . MP算法 17 9 0年, ok从理论上证明了一维模式匹配问 Co题可以在 O m 2时间内解决。K uh等在 B f+ ) n tt F算法 收稿日期: 0 9 0— 0 2 0— 9 3
发 . oe和 Mor提出一种新的快速字符串匹配算 B yr oe 法一 B算法[ l M。 . 6
B算法基本思想是:开始时将目标串与模 M 式串 P左对齐,自右至左逐个字符进行比较(即首先
作者简介:罗金玲 (9 5,, 16一)女湖南娄底市人,底职业技术学院电子信息工程系副教授,究方向为网络安全。娄研
1 9 5

入侵检测系统中模式匹配算法研究_专业资料。分析了BF,KMP,BM模式匹配算法,在此算法的基础上提出了一种改进的模式匹配算法(FBM),该算法的思想是对BM算法中滑动距离...
入侵检测系统中模式匹配算法的研究_专业资料。互联网的开放性为信息共享和交互提供了极大的便利,但随之而来的网络安全问题也日益明显.入侵检测作为一种主动的信息...
入侵检测系统中模式匹配算法的研究 摘要 入侵检测是网络安全的最后一道防线,模式匹配算法是基于特征匹配的入侵检测系统中的核心算法, 模式匹配的效率决定这类入侵检测...
网络入侵检测系统模式匹配算法研究_专业资料。模式匹配算法是网络入侵检测中的关键所在,它直接影响到网络入侵检测系统的实时检测性能。引入4种模式匹配算法,分析其工作...
在此基础上提出了一种 (, 改进的模式匹配算法应用于我们的系统实现中。实验结果表明, 改进的模式匹配算法, 更适合于网络级入侵检测的实现, 减少了系 统的丢包率...
入侵检测模式匹配算法研究_专业资料。综述了入侵检测模式匹配算法,包括Brute Force算法、Knuth-Pratt-Morris算法、Boyer-Mooer算法、Aho-Corasick算法、Set-wise Boyer...
入侵检测模式匹配算法的研究与改进_专业资料。模式匹配算法是实现基于规则检测的核心技术,其效率直接影响到入侵检测系统的准确性和实时性。通过分析传统的模式匹配算法...
网络技术的飞速发展给入侵检测系统提出新的挑战,需要通过各种途径来提高系统性能,而模式匹配算法的优劣直接影响到入侵检测系统的核心模块——规则匹配模块的运行效率。...
网络入侵检测系统中的模式匹配算法优化研究_专业资料。在网络安全问题的研究中,模式匹配是网络安全入侵检测中一种常用检测算法,由于网络规模越来越大,传统的模式匹配...
入侵检测系统中BM模式匹配算法研究_专业资料。模式匹配算法是基于规则的入侵检测系统的核心。基于BM模式匹配算法研究,可对其进行改进。改进算法有效地加快了模式匹配的...
热门文档