A Fast Pattern Matching Algorithm in Intrusion Detection System

姜庆民; 吴宁; 刘伟华

您当前的位置：

首页 >

文章列表页 >

A Fast Pattern Matching Algorithm in Intrusion Detection System

更新时间：2025-12-08

- A Fast Pattern Matching Algorithm in Intrusion Detection System
- Vol. 43, Issue 2, Pages: 58-62(2009)
- 作者机构：
  
  西安交通大学电子与信息工程学院,西安,710049
- 作者简介：
- 基金信息：
- DOI：
  CLC： TP312
- Online First：10 February 2009，
  
  Published：2009
- 稿件说明：
移动端阅览
姜庆民, 吴宁, 刘伟华. A Fast Pattern Matching Algorithm in Intrusion Detection System[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.

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Intrusion Detection Method of Wireless Local Area Network MAC Layer Based on Hidden Markov Model

Sensitivity Analysis of Foil Geometrical Parameters for the Third-Generation CO2 Gas Foil Bearings Based on Design of Experiments Method

Effects of Steam Addition on the Swirl Combustion and Emission Characteristics of Cracked Ammonia

Numerical Simulation of the Energy Conversion Process in Thermoacoustic Engines with Different Stack Materials

Windage Loss and Flow Characteristics in Impeller Back Gaps of sCO2 Radial Inflow Turbines

Related Author

李金铃 1

周颢 1

赵保华 1

Related Institution

Department of Computer Science and Technology, University of Science and Technology of China

State Key Laboratory of Networking and Switching Technology

Anhui Province Key Laboratory of Software in Computing and Communication

⁰