关于快速高效的模式匹配算法的剖析与改进

1、关于快速高效的模式匹配算法的剖析与改良摘要：模式匹配算法是现代化网络入侵检测中的关键环节,本文主要介绍了几种常用的模式匹配算法,并在此根底上,提出一种更快捷、更高效的改良方法,以提升模式匹配的效率与质量,保证网络平安.关键词：模式匹配入侵检测改良随着我国计算机与网络技术的飞速开展,网络应用已涉及到人们生产、生活的各个领域,其重要性日益凸显.随之而来的网络攻击问题也备受关注,给网络平安性带来挑战.传统的网络防御模式,主要采取身份认证、防火墙、数据加密等技术,但是与当前网络发展不适应.在此背景下,入侵检测技术营运而生,并建立在模式匹配根底上,保证检测的快捷性、准确性,应用越来越广泛.1、模式匹配原

2、理概述模式匹配是入侵检测领域的重要概念,源自入侵信号的层次性.结合网络入侵检测的底层审计事件,从中提取更高层次的内容.通过高层事件形成的入侵信号,遵循一定的结构关系,将入侵信号的抽象层次进行具体划分.入侵领域大师kumar将这种入侵信号划分为四大层次,并将每一个层次与匹配模式相对应.以下将分别对四大层次进行分析：(1)存在.只要存在审计事项,就可以证实入侵行为的发生,并深层次挖掘入侵企图.存在主要对应的匹配模式就是“存在模式可以说,存在模式就是在固定的时间内,检查系统中的特定状态,同时判断系统状态.(2)序列.一些入侵的发生,是遵循一定的顺序,而组成的各种行为.具体表现在一组事件的秩序上.序列

3、对应的是“序列模式,在应用序列模式检测入侵时,主要关注间隔的时间与持续的时间.(3)规那么.规那么表示的是一种可以扩展的表达方式,主要通过and逻辑表达来连接一系列的描述事件规那么.一般适用于这种模式的攻击信号由相关活动组成,这些活动之间往往不存在事件的顺序关系.(4)其他.其他模式是不包含前面几种方法的攻击,在具体应用过程中,难以与其他入侵信号进行模式匹配,大多为局部实现方式.2、几种常用的模式匹配算法2.1 ac算法ac算法(aho-corasick)是一种可以同时搜索假设干个模式的匹配算法,最早时期在图书馆书目查询系统中应用,效果良好.通过使用ac算法,实现了利用有限状态自动机结构对所有

4、字符串的接收过程.自动机具有结构性特征,且每一个前缀都利用唯一状态显示,甚至可同时应用于多个模式的前缀中.如果文本中的某一个字符不属于模式中预期的下一个字符范围内,或者可能出现错误链接的指向状态等,那么最长模式的前缀同时也可作为当前状态相对应的后缀.ac算法的复杂性在于o(n),预处理阶段的复杂性那么在于o(项.在采取ac算法的有限状态自动机中,应该在每一个字符的模式串中分别建立节点,提升该算法的使用效率与质量.目前,应用有限自动计算法是一种较为典型与常用的方法,如果模式集比拟大,可能引发空间膨胀问题.在使用ac算法时,搜索输入串过程中没有跳跃,直接根据顺序输入,因此在规那么较少的情况下,ac

5、算法的搜索性能并不理想.2.2 kmp算法kmps算法与简单的算法有所不同,如果某一次的匹配失败,那么模式串不一定是向右移动一格,即使向右移动,也未必从模式的起点位置开始匹配.kmp的具体计算方法为：当某次试匹配成功之后,如果tx?px,那么即使在模式之前j-1个字符全部匹配,而实现已经获知子模式p1p2px-1,且最常的首子串与尾子串同等,即：p1p2pk-1=px-k+1pjxk+2pj-k,那么在下一次的匹配过程中,就可以将模式串向右移动,表示为nextx,代表当模式串中的第x个字符和主串中的相应字符出现“失配现象,那么模式中就需要重新与主串中的字符位置进行比较,在预处理时就可以完成ne

6、xtx的计算工作.为了能完整表达完全匹配的各种情况,以上各首子串必须保证为最长.因此,对于任何一个子模式来说p1p2px,其中1Wxwn,“自匹配中的首子串都是唯一的,仅能与模式的自身结构相关.通过应用kmp算法,采取一次将模式向右移动假设干位置的方式,保证匹配过程中不需要任何回溯.在相对较好的情况下,使用kmp算法的时间复杂度是0m+n,nextx的计算时间复杂度是02.3 bm算法bm算法是单模式匹配算法的其中一种,属于精确的字符串匹配算法,采取从右向左的比拟方式,应用了“坏字符与“好后缀两种启发原那么.bm算法与kmp算法具有一定区别,主要是对模式串的扫描方式相反,即由从左向右改为从右向

7、左.采用bm算法采用这种扫描方式的优势在于：如果在正文中出现了个别模式没有的字符,那么可以将此模式迅速掠过正文.应用bm算法,关键在于如何提升正文的匹配速度,尤其是字符在该模式中的具体位置.假设模式为w1,n,同时定义函数x,函数x明确了正文中可能产生字符的模式位置：x>(1,2,3,4,n),且x6.函数x的定义如下：对于每一个x6来说,假设在执行正文的位置j起“返前一段以及模式从左向右的匹配检查过程中,无论在哪一位置,如果存在不匹配现象,就开始执行从wn和tj+x的从右向左的匹配检查.这种检查的效果相当于将模式向右侧滑动一段距离.很明显,tj不会在模式中出现或者仅在模式的末端存在,向

8、右侧滑动的最大距离为n.3、一种新的模式匹配算法随着计算机与网络的不断应用与拓展,网络流量迅速增加,各种匹配原那么与匹配效率逐渐落后,无法满足现代化高速网络的开展需要.尤其随着各种检测规那么的不断提出,各种数据包匹配的次数也有所改变,因此很难完全满足性能.针对这一情况,在各种根本算法的根底上,充分利用“本次匹配不成功原那么,在匹配失败的情况下,尽量跳过多个字符,实现迅速匹配目标.实际上,本文介绍的快速高效的全新模式匹配算法qs,是bm的简化算法形式,具体描述如下：当p1,2n和ti,i+1,i+n-1对齐的情况下,就可以实现匹配.如果匹配失败,就分析ti+n个字符,以此判断右移p1,2n的距离

9、.由于某一次匹配失败之后,模式会至少向右侧移动一格位置,那么一般情况下,ti+n字符就会在下一次匹配中出现.因此,匹配失败后,就可以综合考虑ti+n而非ti,i+1,i+n-1中的某个字符,这样模式最大右移的距离是n+1,在bm算法中那么是n.以下将对两种改进方法分别进行论述：(1)经过改良的算法,如果文本和模式的某次匹配失败,那么对于ti,i+1,i+n-1左边的字符ti-1就可以采取坏字符移动的方式,而ti,i+1,i+n-1那么采取好前缀移动.在文本中,应该取指针移动距离最大的一个,即minlength+1(minlength)是模式集合中的最短模式长度.针对文本中的所有字符(w)来说,

10、可将坏字符的移动函数定义为：如果w出现在p中,那么执行公式(1),否那么执行公式(2).(2)在传统的匹配算法中,当匹配失败之后,就会分别计算坏字符启发函数或者好前缀启发函数,然后取其中最大值,作为移动量.但是每次计算的时间比拟长,因此需要改良坏字符优先策略.如果利用坏字符启发可以实现n或者n+1的量,就不需要再计算前缀启发函数,最大限度地缩短模式匹配算法时间.经过改良的算法,预处理时间复杂度是0(11+1pl),此处II代表字符集的大小,IpI那么是模式集中所有的模式长度综合.这种算法的最正确情况为：在每次模式树的第一个字符和文本比拟不匹配,而且存在偏移量的最大值minlength+1,改良

11、算法的最正确性能,那么比拟的次数为：在每次进行模式树中的最长模式,最后一个字符和文本比拟时匹配失败,那么最小偏移量是1,改良之后的算法也具备最差性能,这种情况下的比拟次数为：minlength+n-2(minlength-1)maxlength,时间复杂度是0(nmaxlength).在平均情况下,时间复杂度和字符出现概率相关,可以通过概率模型计算.由上可见,随着各种网络应用的不断完善,网络入侵检测计算日益开展,逐渐无法适应网络环境的要求,必须加快改良与优化策略,将改良的算法应用于入侵检测系统中,提升检测效率,保证网络安全运行.参考文献1陈围.采用集合切分编码的大容量模式匹配算法j.计算机应用研究,2021(6).2王烁.字符串模式匹配的硬件加速研究j.中国科学技术大学：通信与信息系统.2021.3孙伟.基于模式匹配和协议分析的入侵检测技术研究j.湖南大学：计算机应用技术,2006.4鲁宏伟,魏凯,孔华锋.一种改良的kmp高效模式匹配算法j.华中科技大学学报,2006(10).5张航,王宏志,李建中