（通信与信息系统专业论文）基于模式匹配的网络入侵检测系统的研究与设计.pdf

武汉理工大学硕士学位论文 摘要 计算机网络的飞速发展和广泛应用的同时，网络入侵事件的发生越来越频 繁，造成的危害也越来越严重，网络安全问题日益突出。传统的等一些被动防 御技术体系本身存在的不足，入侵检测技术作为一种主动的网络安全防御手段， 改变了以往的被动防御的特点，通过实时分析网络上的数据，发现潜在的威胁， 能大幅度的提高网络的安全保障能力，使得入侵检测技术成为当前网络安全方 面研究的热点。入侵检测尤其在抵御网络内部的攻击方面，更有优势，被称为 防火墙之后的第二道安全防线。但目前存在人们对入侵检测了解得还不够，检 测技术也不像防火墙那样成熟，因此，开展对入侵检测方面的研究更有深远意 义。网络规模日益扩大，传统防火墙的安全策略模式已经不能满足人们对网络 信息安全的需求，入侵检测作为防火墙的合理补充，自然成为网络安全领域研 究与开发的新热点。 本文的主要内容如下： ( 1 ) 介绍了当前网络安全状况以及安全策略，分析了传统的加密技术、防 火墙以及身份认证等网络安全技术的优点及不足。研究了入侵检测的国内外发 展状况。 ( 2 ) 对入侵检测系统中入侵检测模块的常用b m 模式匹配算法进行了研究， 指出了传统的b m 算法在入侵检测网络环境下的不足，根据入侵检测的特点提 出了一种改进的b m 算法，并与原算法对比进行了性能测试。 ( 3 ) 分析了入侵检测系统的总体结构和系统的各个模块，参考了几种常见 的入侵检测模型和针对当前的计算机网络特点，详细设计并仿真了系统的数据 捕获模块、协议分析模块、入侵检测模块和响应模块。在入侵检测系统的入侵 检测模块使用了改进的b m 算法。然后对设计的入侵检测系统的各模块的功能 进行了测试和改进算法性能的对比测试。最后本文总结了本系统还存在的一些 问题，提出了今后需要改进的地方。希望以后系统功能更强大，运行效率更高。 关键字：入侵检测，b m 算法，网络安全，协议分析 武汉理工大学硕士学位论文 a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fc o m p u t e rn e t w o r k sa n d 谢d ea p p l i c a t i o n ， n e t w o r ki n t r u s i o n sb e c o m em o r ef r e q u e n t , a n ds e r i o u sh a r m , n e t w o r ks e c u r i t yi s s u e s b e c o m ei n c r e a s i n g l yp r o m i n e n t t h et r a d i t i o n a lt e c h n i c a ls y s t e ma n ds o m ed e f e n s i v e i n h e r e n td e f i c i e n c i e s ，a sap r o a c t i v en e t w o r ks e c u r i t yd e f e n s et o o l si n t r u s i o nd e t e c t i o n t e c h n o l o g yh a sc h a n g e dt h ep r e v i o u s d e f e n s i v ec h a r a c t e r i s t i c s i tc a ni d e n t i f y p o t e n t i a lt h r e a t sb yr e a l t i m ea n a l y s i so f d a t ao nan e t w o r k ，s ot h a tg r e a t l yi m p r o v et h e n e t w o r ks e c u r i t yc a p a b i l i t i e s ，m a k i n gi n t r u s i o nd e t e c t i o nt e c h n o l o g yh a sb e c o m et h e f o c u so fr e s e a r c hi nn e t w o r ks e c u r i t y o nt h ei n t e r n a la t t a c k , i d sh a s m o r e a d v a n t a g e ，k n o w na st h es e c o n dd e f e n s el i n ea f t e rt h ef i r e w a l l b u tt h e r ei sp e o p l e h a v en o te n o u g hu n d e r s t a n d i n go fi n t r u s i o nd e t e c t i o n ，a n dn o ta sm a t u r e 嬲f i r e w a l l d e t e c t i o nt e c h n o l o g y , t h e r e f o r e ，t oc a l l o u tt h er e s e a r c ho ni n t r u s i o nd e t e c t i o nh a s m o r ee f f e c t s a st h eg r o w i n gn e t w o r k , t h et r a d i t i o n a lf i r e w a l ls e c u r i t yp o l i c ym o d e l c a l ln o ts a t i s f yp e o p l e sd e m a n do fn e t w o r ki n f o r m a t i o ns e c u r i t y i n t r u s i o nd e t e c t i o na s ar e a s o n a b l es u p p l e m e n to ff i r e w a l l ，t h en e t w o r k ss e c u r i t y r e s e a r c ha n d d e v e l o p m e n tb e c o m en e w h o ts p o t t h em a i nc o n t e n t so ft h i sp a p e ra r eo r g a n i z e da u sf o l l o w s ： ( 1 ) i n t r o d u c e st h ec u r r e n ts t a t u so fn e t w o r ks e c u r i t y a n ds e c u r i t yp o l i c y , a n a l y s i s e da d v a n t a g e sa n dd i s a d v a n t a g e so f t h et r a d i t i o n a le n c r y p t i o n ，f i r e w a l l sa n d a u t h e n t i c a t i o na n do t h e rs e c u r i t yt e c h n o l o g i e s ，i n c l u d i n gt h ed e v e l o p m e n to fi n t r u s i o n d e t e c t i o na th o m ea n da b r o a d ( 2 ) t h eb mp a t t e r nm a t c h i n ga l g o r i t h m su s e di ni n t r u s i o nd e t e c t i o nm o d u l eo f i n t r u s i o nd e t e c t i o ns y s t e mi sa n a l y z e di nd e t a i l ，p o i n t i n go u tt h ed e f i c i e n c i e so ft h e t r a d i t i o n a lb m a l g o r i t h mi ni n t r u s i o nd e t e c t i o nn e t w o r ke n v i r o n m e n t ，a n dp o i n to u t a n i m p r o v e db ma l g o r i t h m a c c o r d i n g t ot h ec h a r a c t e r i s t i c so ft h ei n t r u s i o n d e t e c t i o n t e s ti t sp e r f o r m a n c ec o m p a r i s o no ft h eo r i g i n a la l g o r i t h m ( 3 ) a n a l y s i so fi n t r u s i o nd e t e c t i o ns y s t e ms t r u c t u r ea n de a c hm o d u l eo f t h e s y s t e m ，r e f e r e n c i n gt os e v e r a lc o r r l l t l o ni n t r u s i o nd e t e c t i o nm o d e l sa n df e a t u r e sf o r 武汉理工大学硕士学位论文 t h ec u r r e n tc o m p u t e rn e t w o r k , d e t a i l e dd e s i g na n ds i m u l a t i o nt h ed a t ac a p t u r em o d u l e ， p r o t o c o la n a l y s i sm o d u l e ，a n di n t r u s i o nd e t e c t i o nm o d u l er e s p o n s em o d u l eo ft h e s y s t e m a n du s e st h ei m p r o v e db ma l g o r i t h mi ni n t r u s i o nd e t e c t i o nm o d u l eo ft h e i n t r u s i o nd e t e c t i o ns y s t e m t h e nt h em o d u l e so fi n t r u s i o nd e t e c t i o ns y s t e mw e r e t e s t e da n dc o m p a r i s o nt e s tt ot h ei m p r o v e da l g o r i t h m f i n a l l y , t h ep a p e rs u m m a r i z e s s o m eo ft h ep r o b l e m ss t i l le x i s ti nt h es y s t e ma n dp r o p o s e sa r e a sf o ri m p r o v e m e n ti n t h ef u t u r e h o p et h a tt h es y s t e mm o r ep o w e r f u la n dm o r ee f f i c i e n t k e y w o r d s ：i n t r u s i o nd e t e c t i o n ，b ma l g o r i t h m ，n e t w o r ks e c u r i t y , p r o t o c o la n a l y s i s 独创性声明 本人声明，所呈交的论文是本人在导师指导下进行的研究工作及 取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得 武汉理工大学或其它教育机构的学位或证书而使用过的材料。与我一 同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说 明并表示了谢意q 签名：王走日期：型盥互【卤丛国 学位论文使用授权书 本人完全了解武汉理工大学有关保留、使用学位论文的规定，即： 学校有权保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权武汉理工大学可以将本学位论文的 全部内容编入有关数据库进行检索，可以采用影印、缩印或其他复制 手段保存或汇编本学位论文。同时授权经武汉理工大学认可的国家有 关机构或论文数据库使用或收录本学位论文，并向社会公众提供信息 服务。 ( 保密的论文在解密后应遵守此规定) 研究生( 签名) ：j 一连导师( 签名) ： b 舭喝酮她 武汉理工大学硕士学位论文 第1 章绪论 1 1 课题提出的背景及意义 研究背景随着i n t e m e t 的发展【l 】，网络安全越来越成为一个敏感的话题。建 立网络的目的在于资源共享和信息交流，但这就意味着存安全问题。当系统集 成商精心设计了一个网络信息系统，并采取了一系列安全措施后，如：设置防 火墙，采用加密算法进行密钥传输，进行用户身份认证等。凭什么认为这样的 网络就是安全的呢? 是根据设计方案文件的厚度，还是为此所花的钱数? 到底 如何评价一个网络的安全性呢? 曾听说过这样的定义：“网络的安全程度定义 为该网络被攻击成功的可能性。实际上，通常总是设法保护装有宝贵信息的 计算机，然而，网络安全的强度只取决于网络中最弱连接的强弱程度。黑客认 识到了这一点，他们寻找网络中未受保护的计算机，诸如未常使用的打印机或 传真机( 为了充分利用这些设备，通常是设置成网络共享的，而且几乎都不需要 口令验证) ，利用它们跳到具有敏感信息的计算机。因此，寻找网络中的薄弱环 节和安全漏洞是每个系统管理员和每个黑客都要做的一件事。系统管理员查找 漏洞的目的在于加强防护，黑客探测漏洞的目的在于找到攻击点【2 j ，如果能测量 它，发现它的所在，才有可能控制它，才能领先黑客一步。另一方面，网络是 动态的，黑客也是多谋善变的。买安全产品或服务，并仅配置一次是不够的， 防火墙如此，其他安全产品也是如此。随着网络的应用、工作站以及操作系统 的数量和类型的改变，网络安全的挑战会越来越激烈。黑客就利用网络或系统 安全漏洞，采用各种方式、方法攻击你的系统，因此安全策略应该适应它，而 这正是所要做的。通过跟踪分析黑客行为和手段，研究系统安全的漏洞。通过 检测和监控网络和系统状态，以发现威胁和弱点，以便及时做出安全策略和执 行决定，在黑客攻击之前，先加使用，进行安全防护。计算机互联网络面临的 安全队威胁主要有以下几个方面1 3 j ： ( 1 ) 非授权访问和破坏( “黑客 攻击) 非授权访问：没有的得到系统的授 权或擅自扩大权限，就使用网络或计算机资源越权访问信息。一般有如下形式： 身份攻击、假冒、用户非法进入网络系统进行违法操作、合法用户进行未授权 武汉理工大学硕士学位论文 的操作等。操作系统总不免存在这样那样的漏洞，一些人就利用系统的漏洞， 进行网络攻击，其中主要目标就是对系统数据的非法访问和破坏。“黑客”攻击已 有很多年的历史，黑客活动几乎覆盖了所有的操作系统，包括u n i x 、w i n d o w sn t 储 乎o ( 2 ) 拒绝服务攻击：一种破坏性攻击，最早的拒绝服务攻击是“电子邮件 炸弹 ，它能使用户在很短的时间内收到大量电子邮件，使用户系统能处理正 常业务，严重时会使系统崩溃、网络瘫痪。它不断干扰网络服务系统，正常的 作业流程被改变，使系统响应减慢甚至瘫痪，影响用户的正常使用，甚至可能 使合法用户被排斥而不能进入系统，不能得到相应的服务。 ( 3 ) 计算机病毒：计算机病毒程序很容易做出，有着巨大的破坏性，其危 害已经为人们所认识。单机病毒就已经让人们“淡毒色变”了，而通道网络传播的 病毒无论是在传播速度、传播范围等方面都是单机病毒不能比拟的。 ( 4 ) 特洛伊木马( t r o j a nh o r s e ) 特洛伊木马的名称来源于古希腊的历史故 事。特洛伊木马程序一般是由编程人员编制，它提供了用户所不希望的功能， 这些额外的功能往往是有害的。把预谋的有害的功能隐藏在公开的功能中，以 掩盖其真实企图。 ( 5 ) 数据完整性破坏【4 】通过非法手段获得数据的使用权，添加、删除、修 改或发送某些重要的信息，可以修改网络上传输的数据，以及销毁网络上传输 的数据，替代网络上传输的数据，重复播放某个分组序列。改变网络上传输的 数据把包的先后次序，使攻击者获益，以干扰用户的正常使用。 ( 6 ) 蠕虫( w o r m s ) ：蠕虫是一个或一组程序它可以从一台机器向另一 台机器传播，它同病毒不一样，不需要修改宿主程序就能传播。 ( 7 ) 活板i - ( t r a pd o o r s ) ：为攻击者提供“后门”的一段非法的操作系统程序， 这一般是指一些内部程序人员为了特殊的目的，在所编制的程序中潜伏代码或 保留漏洞。 ( 8 ) 隐蔽通道【5 】：是一种允许违背合法的安全策略的方式进行操作系统进 程间通信( i p c ) 的通道，它分为隐蔽存储通道和隐蔽时间通道，限蔽通道的重要 参数是带宽。在所有的操作系统中，由于u n i x 系统的核心代码是公开的，这使 其成为最易受攻击的目标，攻击者可能先设法登陆到一台u n i x 的主机上，通过 操作系统的漏洞来取得特权，然后再以此为据点访问其它主机，这被称为“跳跃”。 攻击者在到达目的主机之前往往会经过几次这种跳跃，这样，即使被攻击网络 2 武汉理工大学硕士学位论文 发现攻击者从何处发起攻击，管理人员也很难顺次找到他们的最初据点，而且 他们在窃取某台主机的系统特权后，退出时删除系统日志，用户只要能登陆到 u n i x 系统上，就能相对容易的成为超级用户。所以，如何检测自身的漏洞，保 障网络的安全。已成为日益紧迫的问题。 入侵检测到现在还是一门比较新的网络安全技术，被人们认知的程度还不 高，技术上的实现还存在这样或者那样的问题。 主要体现在以下几个点1 6 j ： ( 1 ) 高速网络环境下的检测问题， 机完成，进行分析时使用唯一的标准。 多数入侵检测系统捕获数据由单一的主 当然有一小部分的入侵检测系统使用了 多种技术从监视的网络上收集数据，但是在处理数据时还是在一台主机上面处 理。这样最主要的一个优点就是技术的实现比较简单，其缺点是显而易见的， 检测效率较低，对c p u 的要求过高，检测设备的处理速度问题一直都是影响网 络性能的瓶颈，在高速网络环境下很难实现对全部数据的检测，由此会造成漏 检的情况。 ( 2 ) 漏报和误报问题r 7 1 ，目前检测系统主要使用的检测方法是将捕获到 的数据与特征库中的特征匹配来判断是否有入侵事件发生，现在的特征库组织 还不够先进，如果特征库做得太大，会降低检测速度影响网络性能，做得太小， 很多的入侵行为无法查出，容易造成漏报误报的问题。入侵特征库还要进行不 断地更新，以面对不断出现的新的入侵行为，这对系统的可配置性也有较高的 要求。通过流量统计分析建立的i d s 正常行为的轨迹( 基于异常的入侵检测) ， 当系统运行时的发现网络中数据超过正常阂值，就认为网络可能受到攻击，该 技术实现起来很有难处，建立一个正常轨迹本事就是一个很难实现的事，并且 建立起来的正常轨迹不可能是完美的，很多黑客研究发现漏洞后，利用它进行 一些破换，由此造成更大的破坏。 ( 3 ) 事件响应与恢复机制不完善，这一部分目前几乎都没有得到足够的重 视，很多系统的这一部分没有或者很简单，即使有也是很简单的响应功能，远 不能满足人们的期望和要求。 ( 4 ) 缺乏对入侵检测关键组件的保护，一个系统存在漏洞是一个最严重的 问题，如果系统本身没有保护好自己，不怀好意的人利用它做一些非法的事情， 往往是不能察觉的。 武汉理工大学硕士学位论文 1 2 国内外研究现状 入侵检测的研究开始于2 0 世纪8 0 年代【8 】，在i n t e m e t 兴起之后受到较高重 视得到快速发展是。早在1 9 8 0 年，ja n d e r s o n 等人为美国空军做了一份题为“计 算机安全威胁监控与监视”的技术报告，这份报告被公认为是入侵检测的开山 之作。在报告中，他首次提出了入侵检测的概念就提出了入侵检测的概念，提 出使用审计信息来跟踪用户的可疑行为，并简单地划分了入侵行为。1 9 8 5 年， d e n n i n g 在o a k l a n d 提出了基于统计量分析的、实时和用户行为轮廓( p r o f i l e ) 的入 侵检测技术，做出了第一个实时入侵检测专家系统模型，该模型是入侵检测研 究领域的里程碑，此后大量的入侵检测系统模型开始出现，但是大多是基于d e n n i n g 的统计量分析理论。1 9 8 6 年，乔治敦大学的d o r o t h y 和s r i c s l 的p e t e r n e u m a n n 提出了一个名为i d e s ( i n t r u s i o nd e t e c t i o ne x e r ts y s t e m ) 模型。它的 基本思路为：入侵者的行为和合法用户的异常行为是可以从系统合法用户的正 常行为中区分出来的。为了定义一个用户的正常行为就必须为这个用户建立和 维护一系列的行为轮廓配置，这些配置描述了用户正常使用系统的行为特征。i d e s 可以利用这些配置来监控当前用户活动并与以前的用户活动进行比较，当 一个用户的当前活动与以往活动的差别超出某些预定义的边界条件，即轮廓配 置的各项阈值时，这种活动就被认为是异常的，并且它很可能是一种入侵行为。 进入9 0 年代以后 9 1 ，随着p o r r a s 和k e m m e r e r 基于状态转换分析的入侵检测技 术的提出和完善，根据已知攻击模型进行入侵检测的方法成为该领域研究的另 一热点。第三代检测技术主要是基于协议分析，协议分析的出现极大减小了系 统的计算量、虚警率和识别未知攻击的能力协议分析方法主要是充分利用网络 协议特征的有序性特征来实现。通过协议分析可以减少计算量，发现任何不符 合标准的网络行为，可以检测已知和未知的入侵行为。 从入侵检测系统使用的技术策略上来看，目前较热门的技术主要有基于异 常的入侵检测、误用的入侵检测和混合检测技术等。误用检测技术通过建立检 测模型，对用户的操作行为与模型进行匹配，匹配成功，就视该行为是网络攻 击。误用检测技术的优点是检测己知攻击有效性高、误报率低，缺点是很难识 别未知攻击行为，检测依赖于系统的特征库，因此漏报率一般较高，系统需要 经常升级。异常的入侵检测技术是通过用户行为与正常行为之间的偏离来判断 是否存在入侵，它的优点是能够检测到一些未知入侵，缺点是误报率较高，实 4 武汉理工大学硕士学位论文 现起来相当困难，是现在研究的一个热点。混合检测方法是综合误用和异常检 测两者的优势，在做出判断之前，同时使用误用模型和异常模型因此判断的结 果可能会更为准确和全面。从理论上讲，混合检测技术更好，但在两种技术的 融合上比误用检测技术更加困难，需要进一步的深入研究。 从系统体系结构看，入侵检测系统有层次化入侵检测、通用入侵检测和智 能化的入侵检测等。使用的技术是一些基于神经网络、统计和数据挖掘等分析 技术。目前比较成熟的技术是层次化的入侵检测系统，它的优势在于针对不同 类别的攻击可以采取不同的处理方式，不限于主机或者网络数据，另外，层次 化模型对攻击特征库和安全策略库较为容易设计，检测效率较高。 网络入侵检测防御的基础是i d s ，要确定使用什么样的防御手段，只有先检 测到攻击知道攻击的种类和方法。目前国内外对i d s 的研究比较多，由于各种 技术水平的限制，存在误警率和重复报警率较高的问题，i d s 目前还是不成熟的 产品。目前的入侵检测的关键技术都有各自的优势，但是发展单一，由于技术 实现上的问题，异常检测技术是目前应用最多，主流技术的入侵检测技术。s n o r t 是一个典型的基于异常检测技术的系统，一个较为标准化的入侵检测系统，它 先规则化处理网络数据包，简单的解析数据包，然后将解析后的数据与特征库 进行模式匹配，这种方式优点是统一的标准化处理协议的字段特征，缺点是检 测效率比较低。协议分析技术是目前比较先进的入侵检测技术，其基础也是通 过对异常协议进行分析，协议异常分析检测技术通过监控网络状态，分析网络 协议，检测网络通信数据来判断是否存在入侵。协议分析技术的优点是能准确 定位特征攻击，能弥补异常检测中无法准确判定的缺点，因此，结合协议分析 技术，有针对性地匹配攻击特征行为。基于协议分析技术的入侵检测系统不能 实现对所有攻击类型的检测，所存在的问题有：多样化的协议规则，不同的网 络协议有不同的格式，需要分别对待；单一的协议分析只是解析协议本身，当 面对“正常”的协议时，即协议本身没有问题，比如a r p 欺骗攻击，从流量统 计、数据发送者等角度来看，存在明显的攻击；协议分析技术只能按照协议格 式来解析数据，缺乏适应性。传统的模式匹配技术虽然存在匹配速率较慢的问 题，但是它可以检测具有特征性的攻击行为。因此，结合传统的模式匹配技术 和协议分析技术两者的优点是一个较好的入侵检测方案。 5 武汉理工大学硕士学位论文 1 3 本文主要研究内容 本论文主要的研究内容有以下几点： ( 1 ) 介绍了目前网络中存在的主要安全问题和解决这些安全问题主要用到 的一些技术，分析了这些技术的一些优缺点。 ( 2 ) 对入侵检测系统的概念、入侵检测工作过程进行了介绍，并介绍了目 前使用的入侵检测系统检测技术的存在的一些问题。 ( 3 ) 参考了目前一些入侵检测系统的设计思想，研究并设计了一个简单的 入侵检测系统，对其各个模块进行了详细设计，并对各个模块进行了仿真实验。 ( 4 ) 根据本系统特点，对常规的检测规则做了修改与改进。 ( 5 ) 对入侵检测系统所用的b m 模式匹配算法进行了分析改进，经测试， 较原来的算法性能有所提高。 6 武汉理工大学硕士学位论文 第2 章模式匹配算法及改进 2 1b m 算法简介 模式匹配是入侵检测系统的重要部分【l o 】，匹配速度的快慢直接影响整个系 统的运行效率。字符的模式匹配的定义如下：假设有模式字符串m 的长度是m 和文本字符主串t 的长度为t ，m 和t 都是由字符构成的序列，其中主串t 定 义在一个有限长度的字符文件( 如数字、字母等) 中，字符文件的大小为n 。确 定m 在t 内出现的位置、次数或者m 是否在t 中是否存在相同的字符串是模 式匹配的最终目的。将t 和m 中的字符从左至右进行编号，对于一个指定的偏 移9 ，若t 中有长度为m 的子串与模式串相等那么就认为p 在t 的币处匹配。 b m 算法在进行模式匹配时使用从先前的匹配过程中的信息参与后面模式 串的移动量【1 1 】【1 2 1 ，这样充分利用先前的信息来达到快速匹配的目的。同时根据 模式串的末位字符与主串字符不能匹配的概率一般情况下要大于首个字符，在 模式匹配时，先左对齐模式串与主串t ，自右至左去进行字符比较，同时沿着主 串文本从左向右来移动模式串m 。当字符不匹配时，这样做得好处是可将模式 串移动较远的距离。b m 算法采用坏字符( b a d c h a r ) 和好后缀( g o o d s u f f i x ) 这两种 特别的启发性规则，分别单独计算模式串在这两种规则下的移动量，然后使用 两值当中较大值，也就是尽可能地向右移动模式串m ，减少匹配次数，直至匹 配成功或完毕 下面使用一个例子来说明b m 算法的模式匹配过程。 假设模式串p ：e x a m p l e 文本主串t ：h e r ei sas i m p l ee x a m p l e ( 1 ) 开始：将p l 和t l 左对齐，并从模式串p 的最后一个字符开始从右至 左匹配，如果匹配成功，则依次向左进行下一个字符的比较，直至p 全部匹配 或有匹配失败的情况出现。这时候p m 和t m 不匹配。 第一次匹配： 7 武汉理工大学硕士学位论文 。( 2 ) 此时使用坏字符规则。第一次匹配后发现模式串的p m = “e 与主串 的t m - - “s 不相等，并且t 中字符“s 在模式串中一次都没有出现过，根据 坏字符规则，将模式串右移一个模式串的距离m 使p l 与k l 对齐。 第二次匹配： p lp m k lt n ( 3 ) 使用用坏字符规则。比较字符模式串的p m = “e 和主串的t 2 m _ “p 不相等，但是主串字符的“p ，在模式串中的第5 个位置上出现了，于是将模 式串向右移动2 个位置，对其主串的和模式串的“p ”。 第三次匹配： ( 4 ) 这时候使用好后缀规则。从右至左逐个比较，比较到主串字符“i 时， 与模式串中对应的字符“a 不相等，此时我们知道模式串后缀“m p l e ”已经 完全匹配，虽然在模式串中不存在和“m p l e 一样的子串，但是模式串中的前 缀“e ( b k 右至左的第一个相同字符) 是“m p l e 的子串，此时应将模式串向 右移动6 个位置，p 1 与t n 棚对齐。 第四次匹配 p l p 矗 露棚五 ( 5 ) 使用坏字符规则。比较字符主串的“p ”和模式串的“e 导致不匹配， 但是主串的字符“p 在模式串中的位置5 上出现，将模式串向右移动2 个位置。 到此，匹配完全成功。 第五次匹配： 8 武汉理工大学硕士学位论文 2 2 算法改进 经过上一节的分析知道，模式匹配算法是从某个位置开始，一般是从头开 始，将模式串p 与主串t 按照定规则对齐后根据顺序进行字符的逐个的比较， 比较失败时，就移动模式串到主串的下一个位置相比较，直到完成所全部主串 字符的比较。算法效率高低的关键在于模式串与主串失配后模式串能向后移动 的距离，移动距离的大小是匹配算法效率高低的关键。b m 算法具有较好的模式 串前进能力，匹配速度较高，是目前主要的字符串匹配方法但该算法在某些特 定的环境下仍存在一些问题和可改进之处。 2 2 1 改进思路的提出 在4 1 节中，通过b m 算法的一个匹配过程实例来说明该算法无论是模式串 还是文本主串均是基于很多种编码的随机的字符串，字符库比较大，并且字符 串中出现较多的重复字符的可能性大。这时候b m 算法就会出现一定的局限性。 通过下一个例子来说明： 假设模式串p ：x y x y x y x 主字符串t ：x y c & x y x y x y x c y c y y x c y x 开始进行算法预处理。根据算法的坏字符规则的移动量( p l ( x ) 函数计算公式可得 xyxc l 甲( x ) l628 然后根据算法好后缀规则q 2 ( a ) 函数公式计算可得： a01234567 c h a rxyxyxyx 中2 ( a )7772747l ( 2 ) 第二次匹配，a = 5 ，字符比较3 次；移动量9 2 ( 5 ) = 9 l ( ) - 8 + 6 = 4 9 武汉理工大学硕士学位论文 ( 3 ) 第三次匹配，完全匹配，字符比较8 次：移动量q ) 2 ( 0 ) = 7 。 p lp m ( 4 ) 第四次匹配，a = 5 ，字符比较三次：移动量( p 2 ( 5 ) = 9 ( ) 8 + 6 = 4 。 ( 5 ) 第五次匹配，a = 6 ，字符比较两次；移动量q ) 2 ( 6 ) _ 7 。 此时模式串经过多次比较终于到主串末尾，匹配完成。 在上面例子的模式匹配中，主串的字符数2 4 个，模式串字符个数8 个，但 是总共需将模式串进行5 次移动和进行1 7 的次比较。考察模式匹配的整个过程， 可以知道在第二次匹配时已得到小部分匹配的子串“y x ”。然后接着的第三次匹 配时虽然已完成了模式匹配，但在后面的匹配过程中仍然逐个字符比较了一个 共计8 次模式串的长度；这样第二次匹配时得到的子串匹配信息没有得到充分 的利用。如果充分利用第二次匹配的部分匹配结果，对模式串的子串“y x 进 行记录，那么在第三次匹配时就能够在一定程度上加快模式串移动速度或者减 少字符比较次数，从而提高算法的效率。 2 2 2 算法改进 通过上述分析，本文提出一种改进比较次数复杂度的算法。改进后的算法记 录了字符部分匹配的结果，当上一次匹配计算出的移动量为由2 ( a ) 时，改进后的 算法与原b m 算法主要有两个区别： ( 1 ) 在当前的模式匹配时，如果在主串中找到已记录的上次部分匹配的子 串，这时就可以进行跳跃式比较，根据规则可能部分甚至全部跳过此子串，这 样就减少了字符的比较次数。 ( 2 ) 在计算下一次移动量时需要考虑的函数是s h i f t 来确定模式串的最小移 l o 武汉理工大学硕士学位论文 动距离，即移动距离是取( p l ( x ) 、p 2 ( a ) 和s h i f t 三者中的最大值，这将会进一步加 快模式字符串跳跃速度率。 上次匹配中参考了好后缀规则下的移动量是改进的算法的前提，即上次匹配 中模式串p 与文本主串t 存在部分匹配的情况。假设模式串p 和主串t 中都有 子串为f ，即存在部分匹配的情况，根据子串f 在模式串p 中的所在位置，分别 考虑以下三种情况： ( 1 ) 第一种情况：若模式串p 中存在多个相同的子串f ，则取距离主串最近 的f ，则此时将模式串p 向右移动，使得模式串p 中最左侧子串f 与t 中已与主 串匹配的子串f 对齐，这种情况下p 和t 会有匹配成功的可能。如图2 1 所示。 t p 图2 1改进后的算法在好后缀规则下移动情况一 ( 2 ) 第二种情况：若模式串p 中只存在一个子串c 但p 中的首部只有一 个e 与主串t 中相同的子串，设为e ，此时可将模式串p 整个向右移动使得p 中 左侧子串e 与t 中的子串e 左对齐，如图2 2 所示。 团 t p p 图2 2 改进后算法在好后缀规则下移动情况二 ( 3 ) 第三种情况：若模式p 中子串e 和子串f 同时不存在，也就是说当前 p 与t 对应部分中不会再次出现匹配，那么应将模式串p 向右移动的距离长度为 武汉理工大学硕士学位论文 m ，即向右移动一个模式串的距离。 对于前面的第二种情况，下一次匹配可以使用上一次匹配中得到的部分匹 配信息，由此得到更多的移动量，改进的算法定义了一个临时函数s h i t t 来记录 部分匹配情况。要是在某一次模式串与主串匹配时，若上一次匹配中记录的部 分匹配子串的长度l e i 与当前的部分匹配子串长度i f 比较，i e l 较i q 大，此时就进行 s b j r 的计算。在这种情况下，可称e 为临时记录参数，同时子串f z e 是模式串p 的一个后缀。 在这一次的字符匹配过程中，模式串p 中的a 和主串t 中的b 导致这次失 配，从图4 3 中可以知道紧连的字符串a f 同样是模式串p 的一个后缀子串。在 前面已经假设y l e l l 拘长度大于旧的长度，这样e 的后缀子串包含了a f 。设定y 是 字符a 与b 在主串中的距离，由于e 同时也是f z e 的边界，一个长度为y 1 z f i 的 字符区间存在于在模式串p 中的i f z e l 的后缀子串里，必然会有l e i 的长度小于y ， 而且a 与b 是不相同的，因此e 里面是不可能含有字符b 的，这时子串e 应该至 少移动至b 的右侧方才有可能匹配成功，由此得出s h i f t 最小移动量是l e l 与i f l 的差， 如图2 3 所示。 t p p y l璧 e l a l f 一-i 1 z 7 i r y 图2 3改进算法触发s h i f t 的移动情况 讨论一下改进算法在b m 算法的坏字符规则下的性能。在这种情况下字符x 和字符y 是不等的两个字符，此时按照改进算法可将y 移动上次匹配的子串f 的末尾，移动距离最少是 e l + l 。如图2 4 所示。 1 2 武汉理工大学硕士学位论文 t p p l x i e ， y i e 图2 4 改进算法在坏字符规则下的移动情况 经过以上的改进后，算法流程图如图2 5 所示。 图2 5 改进算法流程图 武汉理工大学硕士学位论文 2 2 3 算法语法描述 b = o ；e = o ；s h i f t = - m ； f o r ( b = o ；b + + ；b o & & p a = t 【b + a 】 i f ( e ! = o & & a 一- - - m - s h i f t a 寻a - e ； e l s e a = a - 1 ； i 坟a - o ) 2 1 8 1 0 4 1 11 1 2 2 5 3 ： 4 9 6 6 + a ? t r p 3 6 0 c n ( 2 9 ) 1 l ：4 3 ：4 5 6 2 2 1 0 4i p2 1 8 1 0 4 1 1 1 1 2 2 5 3 l e n o v o 7 f a 4 f 2 b c d o m a i n 5 7 1 7 6 ： 4 9 6 63 4 4c n a m e t r - s p 3 6 0 c a ， i d o m a i n 】 11 ：4 3 ：4 5 7 1 4 8 5 5i pl e n o v o 7 f a 4 f 2 b c d o m a i n 6 4 9 8 0 2 1 8 1 0 4 111 1 2 2 5 3 ： 3 9 9 9 7 + a ? u p d a t e m 3 6 0 s a f e t o m ( 3 7 ) 1 1 ：4 3 ：4 5 7 1 6 4 0 6i p2 1 8 1 0 4 1 1 1 1 2 2 5 3 l e n o v o 7 f a 4 f 2 b c d o m a i n 6 4 9 8 0 ： 3 9 9 9 713 4 4c n a m e 1 d o m a i n 11 ：4 3 ：4 5 7 6 5 1 0 3 l e n o v o 7 f a 4 f 2 b c d o m a i n 3 6 5 7 6 0 2 1 4 6 4 2 5 8 0 ：s 8 7 3 9 7 1 2 3 2 ：8 7 3 9 7 1 2 3 2 ( 0 ) w i n6 5 5 3 5 1 1 ：4 3 ：4 6 4 4 0 0 2 4i pl e n o v o 7 f a 4 f 2 b c d o m a i n 3 6 6 2 2 2 0 2 5 0 6 4 18 8 0 8 0 ：s 2 0 7 3 4 3 5 3 ：2 0 7 3 4 3 5 3 ( o ) w i n6 5 5 3 5 1 1 ：4 3 ：4 6 5 1 9 8 7 9i p2 2 0 2 5 0 6 4 1 8 8 0 8 0 l e n o v 0 7 f a 4 f 2 b c d o m a i n 3 6 6 2 ：p 1 ：9 1 3 ( 9 1 2 ) a c k3 1 3w i n4 9 6 8 0 11 ：4 3 ：4 6 5 6 3 8 6 5i pl e n o v o 7 f a 4 f 2 b c d o m a i n 6 0 311 2 1 8 1 0 4 1 1 1 1 2 2 5 3 ：u d p ，l e n g t h1 0 6 1 1 6 武汉理工大学硕士学位论文 为了比较算法在字符串模式匹配过程中的体现出来的性能改善，测试时检测 规则数逐步递增，对两种算法进行了测试。其中所用模式串是利用a s c i i 码中 2 6 个英文字母的大小写字符和阿拉伯数字组成的字符库，随机生成长度固定为 1 0 字节作为一条规则； 为确保较d , n 试误差，每一个项测试都进行3 次，取他们的测试结果的平 均值。两种算法的测试结果对比如下表所示： ( 1 ) 运行时间比较 对文本模式串的测试。选取4 0 条模式串作为匹配规则，然后每次增加2 0 条规 则分别对文本主串进行模式匹配，使用计时程序可以得表4 1 所示的运行时间表。 从图中数据可以看出，改进算法性能有一定的提高，大约在1 4 哆分一1 8 左右。 表2 1 两种算法运行时间比较 寝 4 06 08 0l o o 间r 则 s2 冀 原b m 算法l o 2 31 4 5 81 8 6 32 0 5 6 改进的b m 算法 8 7 21 1 8 51 5 1 61 7 1 4 ( 2 ) 算法空间占用情况比较 从上面得出了算法运行的时间上减少了，同时也记录了两种算法的内存使 用情况。根据模式匹配所使用不同的规则数，空间占用的比较表如表4 2 所示。 从表可以知道改进算法所占用的内存空间和原b m 算法相比变化很少，增量大 约在2 左右。 表2 2 两种算法内存占用比较