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

姜庆民; 吴宁; 刘伟华

您当前的位置：

首页 >

文章列表页 >

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

更新时间：2025-12-08

- 面向入侵检测系统的模式匹配算法研究
- A Fast Pattern Matching Algorithm in Intrusion Detection System
- 西安交通大学学报 2009年43卷第2期页码：58-62
- 作者机构：
  
  西安交通大学电子与信息工程学院,西安,710049
- 作者简介：
- 基金信息：
- DOI：
  中图分类号： TP312
- 网络首发：2009-02-10，
  
  纸质出版：2009
- 稿件说明：
移动端阅览
姜庆民, 吴宁, 刘伟华. 面向入侵检测系统的模式匹配算法研究[J]. 西安交通大学学报, 2009,43(2):58-62.

姜庆民, 吴宁, 刘伟华. A Fast Pattern Matching Algorithm in Intrusion Detection System[J]. 2009, 43(2): 58-62.
姜庆民, 吴宁, 刘伟华. 面向入侵检测系统的模式匹配算法研究[J]. 西安交通大学学报, 2009,43(2):58-62. DOI：

姜庆民, 吴宁, 刘伟华. A Fast Pattern Matching Algorithm in Intrusion Detection System[J]. 2009, 43(2): 58-62. DOI：

摘要

针对入侵检测系统对基于攻击特征的网络数据包的检测效率低和丢包率高的问题

在分析典型的模式匹配算法的基础上

提出了一种 Boyer Moor Horspool Fast(BMHF)匹配算法.引入一个新的判断函数Q(X)指出字符X在模式串中出现的次数

当出现次数为1时可以利用已匹配的信息加大移动距离

同时利用文本串中不匹配字符后面的一个字符进行匹配

从而得到一个移动距离.将不同移动规则下获得的移动距离的最大值作为实际的移动距离

依次进行

直到匹配完成.实验结果表明

BMHF算法的CPU运算时间比典型的模式匹配算法可平均节省5.7%

平均匹配次数减少12.5%.

Abstract

A new fast pattern matching algorithm(called BMHF algorithm)is proposed to improve the detecting efficiency of network data based on attack signature and to decrease the packet loss rate in the intrusion detection system(IDS)

by analyzing popular pattern matching algorithms such as BM algorithm

BMH algorithm and BMHS algorithm. A new function Q(X)is employed in BMHF to identify the number of a character X matching in the pattern string. When Q(X)equals one

the matched information is used to enlarge the shifting distance. A new shifting distance is also calculated according to the character next to non-matched characters in the pattern string. The maximum distance among these shifting distances is used in the BMHF algorithm. The process is repeated until the matching is completed. Experimental results show that the BMHF algorithm has better efficiency. The decrease in the operation time of CPU is 5.7 percent

and the decrease in the average number of matchings is 12.5 percent.

关键词

Keywords

references

YAN Weimin, WU Weimin. Data structure [M]. Beijing, China: Tsinghua University Press,1997.

CHARRAS C, LECROQ T. Exact string matching algorithms [EB/OL].[2008-02-05]. http:∥www-igm.univ-mlv.fr/～ lecroq/string. 1997.

KNUTH D E, MORRIS J H, PRATT V R. Fast pattern matching in strings [J].SIAM Journal on Computing, 1977, 6(2):323-350.

BOYER R S, MOORE J S. A fast string searching algorithm [J].Communications of the ACM, 1977, 20(10): 762-772.

NIGEL-HORSPOOL R. Practical fast searching in strings [J]. Software Practice and Experience,1980,10(6):501-506.

DANIEL M S. A very fast substring search algorithm [J].Communications of the ACM,1990,33(8):132-142.

张娜,张剑. 一个快速的字符串模式匹配改进算法[J]. 微电子学与计算机, 2007, 24(4):102-105.

ZHANG Na, ZHANG Jian. A fast improved algorithm for pattern matching in string [J]. Microelectronics Computer,2007,24(4):102-105.

李洋,王康,谢萍. BM模式匹配改进算法 [J].计算机应用研究, 2004, 21(4): 58-59.

LI Yang, WANG Kang, XIE Ping. The improving algorithm of BM [J]. Application Research of Computers, 2004, 21(4):58-59.

牟永敏,李美贵,梁琦. 入侵检测系统中模式匹配算法的研究 [J]. 电子学报,2006,34(12A):2488-2490.

MU Yongmin, LI Meigui,LIANG Qi. The survey of the pattern matching algorithm in intrusion detection system [J]. Acta Electronica Sinica,2006,34(12A):2488-2490.

蔡晓妍,戴冠中,杨黎斌. 一种快速的单模式匹配算法[J].计算机应用研究,2008,25(1):45-49.

CAI Xiaoyan, DAI Guanzhong, YANG Libin. Faster algorithm for single pattern matching [J]. Application Research of Computers,2008,25(1):45-49.

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

基于隐马尔可夫模型的无线局域网媒体接入控制层入侵检测方法

水蒸气掺混对氨裂解气旋流燃烧与排放特性的影响研究

三塔合一间接空冷系统结构参数对夏季运行特性的影响研究

超临界二氧化碳向心透平轮背间隙内风阻损失及流动特性研究

电子级超纯氮深冷空分流程节能优化研究