入侵检测系统中模式匹配算法的研究
入侵检测系统中模式匹配算法的研究
摘要 入侵检测是网络安全的最后一道防线,模式匹配算法是基于特征匹配的入侵检测系统中的核心算法,模式匹配的效率决定这类入侵检测系统的性能。本文对入侵检测系统中的模式匹配算法进行了综述,包括经典的单模式匹配算法--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算法虽然在不匹配时能使模式串右移若干位,但右移的距离不可能超过一趟匹配操作所进行的比
入侵检测系统中模式匹配算法的研究_专业资料。互联网的开放性为信息共享和交互提供了极大的便利,但随之而来的网络安全问题也日益明显.入侵检测作为一种主动的信息安全...
入侵检测系统中模式匹配算法研究_专业资料。分析了BF,KMP,BM模式匹配算法,在此算法的基础上提出了一种改进的模式匹配算法(FBM),该算法的思想是对BM算法中滑动距离函...
在此基础上提出一种改进算法——两端分段匹配算法,并加以验证,最后指出改进模式匹配算法效率的研究方向。综述入侵检测系统中的模式匹配算法,包括经典的单模式匹配算法KMP...
网络入侵检测系统模式匹配算法研究_专业资料。模式匹配算法是网络入侵检测中的关键所在,它直接影响到网络入侵检测系统的实时检测性能。引入4种模式匹配算法,分析其工作原...
网络处理模式匹配算法研究 3页 免费 基于多模式匹配算法的供应... 3页 免费 基于内容过滤的模式匹配算... 3页 免费 探讨入侵检测系统中模式匹... 2页 2财富...
计算机 光 盘软件 与 应用 210 1年第 2期 1Cmue DSfwr n plctosoptrC otaeadApiain 软件 设计 开发 探讨入侵检测系统中模式匹配算法的研究与实现 万姝 伊 ( 合...
网络入侵检测系统中的模式匹配算法优化研究_专业资料。在网络安全问题的研究中,模式匹配是网络安全入侵检测中一种常用检测算法,由于网络规模越来越大,传统的模式匹配算...
入侵检测系统中多模式匹配算法的研究与改进_专业资料。对网络入侵检测系统中的多模式匹配算法进行研究,重点介绍AC-BNFA算法的匹配过程,并根据AC-BNFA的匹配特点对其进...
网络入侵检测系统中模式匹配算法的研究与改进母王德正合肥工业人学计算机与信息学院,安徽合肥230009 摘要:入侵检测是网络安全的最后一道防线,模式匹配算法是基于特征匹配...
热门文档