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

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

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

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

摘要 入侵检测是网络安全的最后一道防线,模式匹配算法是基于特征匹配的入侵检测系统中的核心算法,模式匹配的效率决定这类入侵检测系统的性能。本文对入侵检测系统中的模式匹配算法进行了综述,包括经典的单模式匹配算法--KMP算法、BM算法、RK算法和多模式匹配AC算法。对各种算法的性能进行了分析。最后提出了改进模式匹配算法效率的研究方向。

关键词: 网络安全;入侵检测;模式匹配;多模式匹配

1 引言

随着Internet应用的普及,网络安全问题也日益突出。入侵是指试图破坏资源的完整性、可用性和保密性的活动的集合。作为防火墙之后网络安全的最后一道防线,入侵检测系统(IDS)是指检测上述行为的活动,识别出未经授权或越权访问系统资源的行为的软硬件系统。由于入侵检测系统可以在一定程度上主动预防和检测出来自系统内、外部的入侵,并作出适当响应,动态改变网络的安全性,因此入侵检测的研究正成为网络安全研究的热点。

根据采用的分析技术入侵检测分为误用检测和异常检测 [1]。误用检测根据已知的攻击方法,预先定义入侵模式,通过判断这些模式是否出现来完成检测任务。异常检测是指根据用户的行为或资源的使用状况的正常程度来判断是否属于入侵。由于异常检测的误检率和漏检率高,因此目前大多数入侵检测系统产品均属误用检测。误用检测中使用的检测技术主要有:模式匹配、专家系统、状态转移等,而其中因为模式匹配原理简单、可扩展性好而最为常用,例如著名开放源码的入侵检测系统Snort就是基于模式匹配的。 由此可见,模式匹配算法的性能直接影响入侵检测系统的检测效率。在高速网络环境,如果模式匹配算法来不及处理大量的实时网络数据包,必然会丢弃部分数据包,而这些被丢弃的数据包中就可能包含入侵信息。本文以下部分介绍几种著名的模式匹配算法,包括单模式匹配算法和多模式匹配算法,为设计入侵检测系统选择模式匹配算法提供指导。

2 单模式匹配算法

模式匹配是指在给定长度为n的文本串T=T[1]T[2]…T[n]中查找长度为m的模式串P=P[1]P[2]…P[m]的第一次出现的过程。这里T[i](1≤i≤n),P[j](1≤j≤m)∈∑(字符集),若在T中能找到P的出现,则称匹配成功,否则称匹配失败。

一次只能在文本串中对一个模式串进行匹配的算法,称为单模式匹配算法,可同时对多个模式串进行匹配的算法称多模式匹配算法。

平凡的模式匹配算法(BF算法)中,一趟匹配失败后,T只后移一个字符,所以算法简单,但效率低。高效的模式匹配算法都是设法增大不匹配时T的后移量,本节下面介绍3种经典的快速单模式匹配算法,

第3节介绍著名的多模式匹配算法—AC算法。

2.1 KMP算法

D.Knuth、J.Morris和V.Pratt提出一种快速模式匹配算法,称为KMP算法[2]。

KMP算法的基本思想是:若某趟匹配过程中T[i]和P[j]不匹配,而前j-1个字符已经匹配。此时只需右移模式串P,文本串T不动,即指针i不回溯,让P[k]与T[i]继续比较。移动后重新开始比较的位置k仅与模式串P有关,而与目标串S无关,因此K可以事先确定。若定义函数next(j)=K,则next函数的定义应为:

next(j)=Max{k| P[1..K-1]=P[j-k+1.. j-1] }

KMP算法的时间复杂度是O(m+n),空间复杂度是O(m),对BF算法进行了很大的改进。

2.2 BM算法

KMP算法虽然在不匹配时能使模式串右移若干位,但右移的距离不可能超过一趟匹配操作所进行的比

第1页

你可能喜欢

  • 入侵检测技术
  • 入侵检测论文
  • 字符串匹配算法
  • 数据挖掘论文
  • 数据挖掘算法
  • 网络安全技术

热门文档

相关文档

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