（计算机应用技术专业论文）应用协议一致性检查技术研究与应用.pdf

浙江大学硕十学位沧文 摘要 随着专门针对应用层的攻击现象的增多，传统的状态检测防火墙的有效性越 来越低。防火墙的功能重心从网络层发展到了应用层，因而诞生了深度检测技术。 深度检测技术基于数据包的应用层信息，对网络通信进行访问控制。目前，深度 检测技术作为一项新兴技术，仍处于发展和验证阶段。本文旨在通过对深度检测 技术的重要技术应用协议致性检查技术的研究来分析和研究针对应用层 u 攻击的防范方法。 应用协议一致件检查技术对应用协议消息进行协议解码，确认它们是否和应 用协议定义的f 致，过滤不符合应用协议定义的数据包，从而提高网络的安全性。 本文通过分析应用协议消息的通用格式，研究应用协议消息的语义特征，给 出了应用协议消息的“域”和“域规则”的定义，并由此建立应用协议致性规 则模型，解决了合法的应用协议消息的语义特征建模问题。应用协议一致性规则 模型是一个积极安全模型，即规定了一个“白名单”，只有符合白名单的应用层 数据刊能通过检查。 基于应用协议一致性规则模璎，本文完成应用协议一致性枪奄系统的体系结 构和主要功能模块的设计，并针对应用协议一致性规则匹配的关键问题提出了自 己的解决办法：针对域名规则匹配，提出了一种多关键词识别算法；采用一种新 的h y b r i dn f a d f a 实现思路对正则表达式匹配过程进行改进，提高了简单域值 规则匹配的执行效率。 最后，本文实现了h t t p 协议一致性检查系统，通过过滤那些不符合h t t p 协议一致性规则库的h t t p 请求，提高了w e b 服务器的安全性。 关键词：深度检测，应用协议一致性，多关键词匹配，正则表达式匹配 塑兰查兰竺主兰垡丝苎 a b s t r a c t t r a d i t i o n a ls t a t e f u lf i r e w a l lc a n tp r o v i d ee n o u g hp r o t e c t i o na g a i n s tt h ea t t a c k a i m e da tt h ea p p l i c a t i o nl a y e lt h ef u n c t i o no ff i r e w a l lm o v e df r o mt h en e t w o r kl a y e r t ot h ea p p l i c a t i o nl a y e nd e e pp a c k e ti n s p e c t i o nt e c h n o l o g ya n a l y z e st h ea p p l i c a t i o n l a y e rd a t ei nt h en e t w o r kt r a f f i c ，i no r d e rt oe n f o r c es e c u r en e t w o r kc o m m u n i c a t i o n a tp r e s e n t ，d e e pp a c k e ti n s p e c t i o nt e c h n o l o g yi si nt h ep h a s eo fi m p r o v e m e n ta n d v a l i d a t i o n i nt h i s p a p e r , t h ei m p o r t a n t m e t h o do f d e e p p a c k e t i n s p e c t i o l r - - a p p l i c a t i o nl a y e rp r o t o c o lc o n f o r m a n c ea n a l y s i si ss t u d i e d ，i no r d e rt o p u r s u ef o rm e t h o d st op r o t e c t i o nn e t w o r kf r o mt h ea t t a c ka i m e da tt h ea p p l i c a t i o n l a y e r a c c o r d i n gt ot h ed i f f e r e n ta p p l i c a t i o np r o t o c o lo fn e t w o r kt r a f f i c ，a p p l i c a t i o n l a y e rp r o t o c o lc o n f o r m a n c ea n a l y s i st e c h n o l o g ya n a l y z e st h ea p p l i c a t i o nl a y e rd a t a ， i d e n t i f i e sw h e t h e ri ti sc o m l i l yw i t ht h ed e f i n i t i o no f t h ea p p l i c a t i o np r o t o c 0 1 i nt h i sp a p e r , w ea n a l y z et h eg e n e r a lf o r m a to fa p p l i c a t i o nl a y e rm e s s a g e s ，s t u d y t h e i rc o m m o nf e a t u r e s ，d e f i n e s “f i e l d a n d “f i e l dr u l e ，a n d f i n a l l ye s t a b l i s ht h e a p p l i c a t i o np r o t o c o lc o n f o r m a n c er u l em o d e l ，w h i c hm o d e l st h es e m a n t i cf e a t u r e s o fa p p l i c a t i o nl a y e rm e s s a g e t h ea p p l i c a t i o np r o t o c o lc o n f o r m a n c er u l em o d e li s p r o a c t i v ea n ds e c u r e ，w h i c hd e f i n e sa w h i t el i s t ”o n l yt h ea p p l i c a t i o nl a y e r m e s s a g e sc o m p l y i n gw i t hi tc a nt r a v e lo nt h en e t w o r k b a s eo nt h em o d e la g e n e r a la r c h i t e c t u r e o fa n a p p l i c a t i o np r o t o c o l c o n f o r m a n c ea n a l y s i ss y s t e mi sd e s i g n e d f o l l o w i n gp r o b l e m si ss o l v e di nt h es y s t e m ： an e wm u l t i k e y w o r dr e c o g n i t i o ni sd e s i g n e dt op e r f o r mf i e l du a m em a t c h i n ga n da n e wh y b r i dn f a d f aa p p r o a c ht op e r f o r ms i m p l ef i e l dv a l u em a t c h i n g f i n a l l y ，h t t pp r o t o c o lc o n f o r m a n c ea n a l y s i ss y s t e mi si m p l e m e n t e d ，i tf i l t e r s t h eh t t pr e q u e s t sw h i c hd on o tc o m p l yw i t hh t t pc o n f o r m a n c er u l es e t ，t h u se n s u r e t h es e c u r i t yo f w e bs e r v e r s k e y w o r d s ；d e e pp a c k e ti n s p e c t i o n ，a p p l i c a t i o np r o t o c o lc o n f o r m a n c e ， m u l t i p l ek e y w o r d sm a t c h i n g ，r e g u l a re x p r e s s i o nm a t c h i n g n 浙江大学硕士学位论文 1 1 本文的研究背景 第一章绪论 互联网已经r 益成为人类物质社会的重要组成部分。计算机网络在经济和生 活的各个领域正在迅速普及。当前政府、银行、企业等都在组建和发展自己的网 络，并且连接到互联网，实现自己的核心业务以及充分共享、利用互联网的信息 资源。网络逐渐成为这些用户完成相关业务的非常重要的、不可或缺的手段。但 是伴随着网络的发展，也产生了各种各样的问题。其中，网络安全问题尤为突出。 网络安全已经成为国家与困防安全的重要组成部分，同时也是国家网络经济发展 的关键。了解网络面临的各种威胁，防范和消除这些威胁，实现真正的网络安全 已经成了网络发展中最重要的事情。 目前网络安全产品主要细分产品包括防火墙、入侵检测系统( i d s ：i n t r u s i o n d e t e c t i o ns y s t e m ) 、防病毒产品、信息加密以及安全认证等。据i n f o n e t i c sr e s e a r c h 资料显示，2 0 0 5 年第季度全球网络安全市场仍以v p n 和防火墙应用产品和软 件为主，占市场的7 8 ，i d s f l p s 位于第二，市场份额为1 4 ，网关防病毒产品 以8 的占有率居于第三位 1 】。据赛迪网统计，截止到2 0 0 5 年底，防火墙软件以 4 3 4 的份额，成为2 0 0 5 年中国网络安全产品市场中主力军【”。如图1 所示。 9 0 0 5 年中国同拓安全产品审场结构 图12 0 0 5 年中国网络安全产品市场结构图 “防火墙”这个术语来自应用在建筑结构里的安全技术。防火墙在楼宇里用 来隔离不同的公司或房间，尽可能的起防火作用。一旦某个单元起火这种方法保 浙江大学 i 煎士学位论文 护了其它的居住者。然而，多数防火墙罩都有一个重要的门，允许人们进入或离 开大楼。因此，虽然防火墙保护了人们的安全，但这个门在提供增强安全性的同 时允许必要的访问。 在计算机网络中，防火墙是在不同网络( 如可信任的组织内部网络和不可信 任的公共互联网) 或不同安全区域之间设置障碍，阻止对信息资源的非法访问， 也可以用来防止内部信息的外泄。换言之，防火墙是一道“门”，这道门控制不 同网络之间的通信。防火墙监控不同网络之间的任何活动，限制不同网络之间的 通信，以达到防止非法用户侵犯的目的，从而可以提高网络的安全性。 状态检测防火墙是目前使用最广泛的防火墙。但是，随着专门针对应用层的 攻击现象的增多，在攻击防护中，状念检测防火墙的有效性越来越低。很多攻击 手段可以轻易地绕过防火墙进入企业网络。而这些攻击的最大威胁在于，直接面 对企业应用，对企业业务造成最直接地打击。尤其我国信息化的推进，很多企业 的业务关联性大大增加，网络也变得越来越智能化。哪个环节出现问题，都会造 成网络大面积的瘫痪，造成不可预估的损失。 近年来，一项创新的防火墙技术正获得广泛的应用，这就是深度包检测d p i ( d e 印p a c k e t i n s p e c t i o n ) 技术( 也称作深度检测) 。深度检测防火墙，将状态检 测和应用层网关防火墙技术结合在一起，以处理应用程序的流量【4 j 。深度检测防 火墙能够对数据流量迅速完成网络层级别的分析，并做出访问控制决；对于允许 的数据流，根据应用层级别的信息，对负载做出进一步的决策，防范目标系统免 受各种复杂的攻击。 1 2 防火墙技术发展回顾 自从1 9 8 6 年美国d i g i t a l 公司在i n t e m e t 上安装了全球第一个商用防火墙系 统后，提出了防火墙的概念，防火墙技术得到了飞速的发展。防火墙技术经历了 分组过滤、应用代理网关、再到状态检测三个阶段。 最早出现并获得广泛应用的分组过滤式防火墙可以被称为第一代防火墙。最 基本的分组过滤防火墙会根据网络层的参数( 如源i p 地址和目标i p 地址) 检查 通过网络的数据包，再由内建的分组过滤规则依据这些参数来确定哪些数据包被 放行，哪些数据包被阻隔。分组过滤式防火墙的优点在于实现简单，速度快，效 率高。但是它不能防止地址欺骗：不支持应用层协议，访问控制力度太粗；不理 解通信内容，不能处理新的安全威胁。随着网络的快速发展对网络安全产品的要 求越来越高，分组过滤式防火墙逐渐退出市场。 第二代防火墙，也称代理服务器或应用层网关，它代表各种网络客户端执行 应用层连接，即提供代理服务。应用层网关的工作方式与分组过滤技术有很大的 浙江大学硕士学位论文 不同，其所有访问都在应用层( o s i 模型的第七层) 中控制，并且也没有任何网 络客户端能直接与服务端进行通信，起到外部网络向被保护的内部网络申请服务 时中间转接作用，这种方法可以有效地防止对内部网络的直接攻击，安全性较高。 由于每个应用都要求单独的代理服务，应用层网关的配置非常繁琐，而且难于理 解，容易出现配置失误，最终影响网络安全防范能力。此外，使用应用代理网关 会大大增加应用程序的相应时延，因而不能支持大规模的并发连接。 第三代防火墙有效地提高了防火墙的安全性，称为状态检测防火墙。它的工 作方式类似于分组过滤防火墙，只是采用了更复杂的访问控制算法。状态检测防 火墙和分组过滤防火墙实质上都是通过控制决策来提供安全保护的，只是状态检 测型防火墙除了可以利用第三层网络参数执行决策之外，还可以利用网络连接及 应用服务的各种状态来执行决策。另外，所执行的决策也不仅限于数据包的放行 与阻隔，类似加密这样的处理也可以作为一种控制决策被执行。 状态检测防火墙出现，并成为市场上的绝对领导者，它们在9 0 年代中期得 到了迅速发展。1 9 9 3 年，c h e c kp o i n t 公司成功推出了世界上第一台商用的状态 检测防火墙产品【4 j 。 随着新的针对应用层的攻击的出现，防火墙必须具备应用层的过滤能力。i t 业界权威机构g a r t n e r 认为防火墙必须深入检查信息包流的内部来确认出恶意行 为并阻止它们。市场上的包检查解决方案必须提高性能( 比如签名检查) 来寻找 已知的攻击，并理解什么是“正常的”通信，同时阻止异常的数据流。到2 0 0 6 年，7 5 的全球2 0 0 0 强企业将替换他们的防火墙，或者为他们的防火墙增加深 度检测的能力p j 。 1 3 深度检测技术的研究和应用现状 新的深度检测技术仍在不断出现，以实现不同的深度检测功能。高级的深度 检测防火墙整合了包过滤防火墙和状态检测防火墙的所有功能。高级的深度检测 技术一般具有以下四个方面的特征：应用层加密解密、正常化、协议一致性分 析、双向负载检测【4 1 。“应用层加密解密”使得防火墙能够识别应用层的数据内 容；“正常化”保证防火墙使用的模式匹配技术的有效性；“协议一致性”指的是 确认应用层数据流与应用协议规范是否一致；“双向负载检测”功能提供全面的 应用程序保护。 目前已经有对应用层的协议进行深度检测的防火墙产品。c h e e k 1 0 i n t 公司 2 0 0 3 年5 月份推出的a i ( a p p l i c a t i o ni n t e l l i g e n c e ) 是强化防火墙对应用层安全 功能的一个很好的验证。a i 主要完成这些功能：确认通信是否遵循相关的协议 标准：进行异常协议检测；限制应用程序携带恶意数据的能力；对应用层操作进 浙江大学硕士学位论文 行控制。 f xc o m m u n i c a t i o n s 的i n j o yf i r e w a l l 对多种应用层的协议都进行了深度检 测。它采用了多级的深度检测技术，包括协议确认，应用层弱点攻击的保护，邮 件服务器的保护等。其中协议确认是减小导致类似h t t p 和s m t p 服务器的缓冲 器溢出，应用层弱点攻击的保护是通过阻止危险的或者过长的u r l 到达服务器 来实现的，该防火墙对邮件服务器的保护是会对带有病毒、特诺伊木马和蠕虫病 毒的邮件进行过滤【6 j 。 而m i c r o s o f ti s as e r v e r2 0 0 4 采取的应对措施是，针对每一类主流的应用， 如h t t p 、s m t p 、f t p 和s q ls e r v e r 数据库访问( 基于r p c ) 都设置专门的过 滤器，如果未来出现新的应用层威胁，还可以增加相应的过滤器。用户可以针对 每一种过滤器进行应用相关的过滤设置。在这种新的机制下，来自i n t e m e t 的数 据包被发送到各自的过滤器，过滤器会将数据包重组后进行内容扫描和判别。例 如，s m t p 过滤器会等待相关的包到齐后，在转发之前重组邮件对其内容进行扫 描，与已知类型的攻击进行比对，在确认这是正常流量后才允许通过口l 。 国内的防火墙厂商天融信公司的n g f w 4 0 0 0 推出了核检测技术，在操作系 统内核模拟典型的应用层协议，在内核实现对应用层协议的过滤，目前支持的协 议包括h t t p1 0 1 1 、f t p 、s m t p 、p o p 3 、m m s 、h 2 3 2 8 】a 深度检测技术，目前尚处于发展和验证阶段。深度检测技术增加了现有防火 墙的技术实现难度。我们的安全阵线已经处于一种非常复杂的境地，在我们的安 全边界，已经充斥着各种传统的防火墙和入侵检测设备以及各种h o n e y p o t 产品， 深度检测技术的融合能够真正降低这种复杂性还是更进一步恶化现状，还需要我 们认真面对【9 1 。深度检测技术进一步发展给网络提供更灵活而强壮的保护，对应 用层数据的检测将给网络管理员更大的弹性来保护系统避免遭受恶毒的攻击。 1 4 面向深度检测的应用协议一致性检查 在计算机网络中，为了使计算机或终端之间能够正确地传递信息，必须有一 整套关于信息传输顺序、信息格式和信息内容等的约定，这一整套约定称为通信 协议。换句话说，协议是一种标准的程序和格式，使数据通信的双方能够互相理 解、接收信息和交谈的。 计算机或终端之间的通信采用分层结构。国际标准化组织( i s o ) 定义的开 放系统互连参考模型( o s i r m ：o p e ns y s t e mi n t e r c o n n e c t i o nr e f e r e n c em o d e l ) 在功能上把计算机网络划分成七层，即物理层( 最底层) 、数据链路层、网络层、 传输层、会话层、表示层和应用层。o s i 模型只提供了计算机间通信的概念框架， 而模型本身并不提供相关的通信方法。实质的通信是由多种通信协议来定义的。 浙江大学碗士学位硷文 通信只能发生在对等层之间，而各层采用的通信协议是各不相同的，即使是在同 一层，不同的功能要求也可能采用不同的通信协议。 t c p o p ( t r a n s m i s s i o nc o n t r o lp r o t o c o l i n t e m e tp r o t o c o l ，传输控制协议网际 协议) 是目前世界上应用最为广泛的协议族。t c p o p 协议族的应用层有着很多 协议来支持不同的应用，例如，h 丌p 提供访问万维网的功能，f t p 提供应用级 的文件传输服务，t e n e t 提供远程登录( 终端仿真) 服务等等。 应用层出议定义运行在不同端系统上的应用程序进程如何彼此传递消息。在 网络传输过程中，应用协议消息被分割成小的数据包，以便能够快速地通过网络。 深度检测防火墙必须将这些小数据包重新组装为原始数据，确定它们是否和应用 协议定义的一致，以防止其中隐藏的攻击。 应用协议一致性检查，通过对协议消息的不同字段进行解密而实现，当协议 消息中的字段被识别出来后，应用一致性检查引擎基于模式匹配技术，将应用协 议一致性规则与协议消息进行匹配，以判定协议消息中是否含有不合法的数据。 应用协议一致性规则，即应用协议对它所传递的消息的语义规定。利用应用协议 一致性检查技术可以更有效地辨识基于应用层的攻击，提供更全面的应用程序防 护。 1 5 本文的主要工作 围绕面对深度检测的应用协议一致性检查技术研究和应用，本文主要完成了 以下几方面的工作： ( 1 )总结了防火墙技术的发展历史和深度检测技术的发展由来和研究 研究现状，阐述了应用协议一致性检查的目的和机制，并对应用协议一致性检查 相关技术进行了综述。 ( 2 ) 研究应用协议消息的语义特征，提出应用协议一致性规则模型。该 模型解决了合法的应用协议消息的语义特征建模问题，能够直接指导应用协议一 致性检查系统的应用开发。 ( 3 )基于应用协议一致性规则模型，完成通用的应用协议一致性检查系 统的体系结构和主要功能模块的设计，并着重解决了应用协议一致性规则匹配的 两个关键问题：域名规则匹配算法和简单域值规则匹配。 ( 4 ) 实现了h t t p 协议一致性系统，并给出了运行结果。 1 6 本文的组织结构 本文的组织如下： 浙江太学碗士学位| 仑立 通信只能发牛存对等层之间，而各层采用的通信协议是各不相同的，即使是在同 一层，不同的功能要求也日能采用不同的通信协议。 t c p o p ( t r a n s m i s s i o nc o n t r o lp r o t o c o f i n t e m e tp r o t o c o l ，传输控制协议网际 协议) 是目前世界上应用最为广泛的协议族。t c p i p 悱议族的应用层有着很多 协议来支持不同的应用，例如，h t t p 提供访问打维网的功能，f r p 提供应用级 的文件传输服务，t e l n e t 提供远程登录( 终端仿真) 服务等等。 应用层 办议定义运行在不同端系统上的应用程序进程如何彼此传递消息。在 网络传输过程中应j ； j 协议消息被分割成小的数据包，以便能够快速地通过网络。 深度检测防火墙必须将这些小数捕包重新组装为原始数据，确定它们是否和应用 协泌定义的一致，以防止其中隐藏的攻击。 应用协议一致性检查，通过对协议消息的不同字段进行解密i 呵实现，当协议 消息巾的字段被识别出来后，应用一致性检查引擎基于模式匹配技术，将应用协 改致性规则与协议消息进行肛配，以判定坊 义消息中是否含有不合法的数据。 应用协议一致性规j l ! l | ，即应用协议对它所传递的消息的语义规定。利用应用协议 一致性榆查技术可以更有效地辨识基于应片j 层的攻击，提供更全面的应用程序防 护。 1 5 本文的主要工作 罔绕面对深度检测的应用协议致性检查技术研究和应用，本文主要完成了 咀下几方面的工作： ( 1 )总结了防火墙技术的发展历史和深度检测技术的笈展由来和研究 研究现状，阐述了应用协泌一致性检查的目的和机制，并对应用协议一致性检查 相关技术进行了综述。 ( 2 )研究应用协 义消息的语义特征，提出应用协议致性规j i ! i j 模型。该 模型解决了合法的应用西议消息的语义特征建模问题，能够直接指导应用协议一 致性检查系统的应用开发。 ( 3 )基于应用协议一致性规则模型完成通用的应用协议一致性检奄系 统的体系结构和主要功能模块的设计，井着重解决了应用协议一致性规则匹配的 两个关键问题：域名规则匹配算法和简单域值规则匹配。 ( 4 )实现了h t t p 协议致性系统，并给出了运行结果。 1 6 本文的组织结构 本文的组织如下 本文的组织如f 浙江大学硕士学位沦文 第一章绪论，阐述了本文的研究背景、所做的工作和内容组织。 第二章应用协议一致性检查相关技术介绍，对多关键词匹配技术和正则表达 式匹配方法进行了介绍。 第三章应用协议一致性规则模型研究，分析了应用协议消息的通用格式，研 究应用协议消息的语义特征，提出应用协议消息的“域”和“域规则”的概念， 并由此建立应用协议一致性规则模型。 第四章应用协议致性检查系统设计，基于应用协议一致性规则模型，提出 了应用协议一致性检查系统的体系结构，对主要功能模块进行了设计，并给出了 应用协议一致性检查的关键算法。 第五章一个应用开发实例简介，在前两章的基础e ，结合实际应用需求，实 现了h t t p 协议一致性检查系统，并给出了系统运行结果。 第六章结论，总结本文所作的工作，展望进一步的工作。 最后是参考资料以及致谢。 浙江大学硕十学位论文 第二章应用协议一致性检查相关技术介绍 应用协议一致性检查基于模式匹配技术实现，通过应用协议消息与预先定义 的应用协议一致性规则相比较，决定如何处理数据包。本章介绍两类防火墙和入 侵检测系统中经常使用两类的模式匹配方法。 2 1 多关键词匹配 多关键词匹配( m u l t i p l ek e y w o r d sm a t c h i n g ) 有时也称为字典匹配( d i r e c t o r y m a t c h i n g 、s e tm a t c h i n g ) ，它研究从大量数据中快速匹配多个关键词( 多个模式) 的技术。多关键词匹配算法目前被广泛用于网络信息过滤、入侵检测和生物信息 计算的基因序列比较等工作中。这些任务的共同特点是需要处理的数据量大，待 匹配的关键词集合大，这些对多关键词匹配算法的处理能力提出了更高的要求。 从1 9 7 7 年，a h o 提出a c 算法到现在，对多关键词匹配算法的研究从来没有停 l l 过。本节介绍目前最常用的几种多关键词匹配算法。 2 1 1a h o c o r a s i c k 算法 a h o c o r a s i c k 算法( 简称a c 算法) 是多关键词匹配的经典算法。该算法是 u n i x 的f 酗e p 的基础。a c 算法将所有的关键字合并到一个集合中，在匹配前对 关键词集合进行预处理转换成树型有限自动机，然后只需对输入串进行一次扫描 就可以找出输入串中包含的所有关键词。每条从有限自动机的开始状态到其它状 态的路径代表关键词集合中某个关键词的前缀。当输入串中的下一个字符不是预 期字符时，有限自动机转到代表着某个关键词的前缀的那个状态，该前缀是当前 状态所代表的前缀字符串的最长后缀。例如，图2 是由关键字集合 h e ，s h e ，h i s ，h e r s 构造的有限自动机机。假设有限自动机处于状态4 ，而输入串中的下一个字符不 是e ，则有限自动机转到状态1 ，继续处理文本。 浙江大学硕士学位沦文 图2 a c 算法构造的有限自动机 a c 算法通过构造有限自动机来确定关键词在文本中的位置，消除了搜索性 能与关键词数量的相关性。a c 算法的预处理时间随关键词集合的大小呈线性变 化，搜索效率只与文本长度相关，是典型的线性搜索算法1 0 l 。 2 1 2w u m a n b e r 算法 w u m a n b e r 算法是在b o y e r - m o o r e 算法( 简称b m 算法) 基础上派生的多关 键词匹配算法。b m 算法是一个著名的单关键词匹配算法，以后大部分的关键词 匹配算法都是在它的基础上发展而来的。b m 算法采用了启发式规则来跳过不必 要的比较，减少比较的数量，实际运行时速度非常快。b m 算法将关键词和文本 从左端对齐，从关键词右端往左匹配文本。如果匹配成功，则比较位置向关键词 左端移动，继续判断，直到关键词匹配成功或者文本中有不匹配的字符出现。 b m 算法预先计算两个函数：坏字符移动( b a d c h a r a c t e rs h i f t ) 和好后缀移动 ( g o o d - s u f f i xs h i f t ) 。b a d c h a r a c t e rs h i f t 算出字符集中每个字符的在关键词式中的 偏移值。g o o d s u f f i xs l f i f t 将已匹配部分看作整个模式的子模式，考虑模式前面一 段中是否有与此子模式匹配的片断，因此可以使关键词向前移动更远的距离。使 用b m 算法搜索文本发生不匹配时，移动关键词的距离为两种移动距离中的较大 者。 与b m 算法不同的是，w u m a n b e r 算法使用块字符( b l o c kc h a r a c t e r ) 代替 单个字符来计算b a d c h a r a c t e rs h i f t ( s h i f t t a b l e ) ，块字符的大小为b 。在进行匹 配的时候，它使用散列表( h a s ht a b l e ) 选择关键词集合中的一个子集与当前文 本进行匹配，减少了无谓的匹配运算。前缀表( p r e f i xt a b l e ) 用于减少当关键 词拥有相同后缀时的匹配次数。 w u m a n b e r 算法框架如图3 所示： 浙江大学硕士学位论文 预处理 计算s h i f t ，h a s h ，p r e f i x 表 开始匹配 w h i l e ( t e x t tim 鲁is o1 1mys 主de 图5b a d - c h a r a c t e rs h i f t 举例 图5 说明：搜索丌始时，首先从最右边将最短的关键词( t i m e ) 和文本进行 对齐，然后从关键词树的左边的位置开始比较。s 是第一个发生不匹配的字符 ( 坏字符) ，关键词树的最左边的第一个s 出现在关键词t i n s e l 中，将关键词树向 左移动三个字符的距离，将这两个s 对齐。这样因为坏字符而进行的移动就是 b a d c h a r a c t e rs h i t t 。 假设关键词集合仍为 t i m e ，t i r e d ，t i r i n g ，t i n t e d ，t i n s e l ) ，输入文本串为 a u t o m a t o n e ，实际搜索过程中应用g o o d - p r e f i xs h i f t 的情况如图6 所示。 d l e e t 0 e h 硅 、 王 * s y m nos1emr 1匕一cke乏 塑坚奎兰堡主堂堡堕壅 娶袅驻s l d 媳： r 岛d t ing r ed in g 、2 2n ado f omato f t e x t 一西z itomatoe 图6 g o o d p r e f i xs h 帆 图6 说明：搜索开始时，首先从最右边将最短的关键词( t i m e ) 和文本进行 对齐，然后从关键词树的左边的t 位置开始比较。在匹配关键词t o m a t o 中的m 和 文本n 时发生失败。这时，文本己经成功匹配的串是t o 。t o 是关键词t o m a t o 的 后缀，移动4 个字符的距离，将关键词t o m a t o 的后缀和文本中已匹配的t o 对齐。 然后再从关键词的树的最左边继续匹配。这4 个字符的移动距离就是g o o d - p r e f i x s h i f t 。 2 1 5 小结 本节中介绍的四个多关键词匹配算法使用不同的匹配思路，因而其性能约束 也不同。它们的主要目的都是快速地找出输入串中包含的所有关键词。而应用协 议一致性检查要对应用层数据进行协议解码，识别应用协议消息的不同字段，然 后对字段的语义值进行分析。如果简单地把消息字段作为关键词集合，然后在应 用层数据中进行搜索，就完全忽略了应用协议消息的结构特性。我们必须根据应 用协议消息的结构特点，分析对多关键词匹配算法的需求，提出适用的多关键词 匹配算法。 o d a e n m r 1 e ；、 uta 鲁 r n o oeamoen a一txet 浙江大学硕士学位论文 2 2 正则表达式匹配 正则表达式( r e g u l a r e x p r e s s i o n ) 的“祖先”可以一直上溯至对人类神经系 统如何工作的早期研究。w a r r e n m c c u l l o c h 和w a l t e r p i t t s 这两位神经生理学家研 究出一种数学方式来描述这些神经网络。1 9 5 6 年，一位叫s t e p h e nk l e e n e 的数学 家在m c c u l l o c h 和p i t t s 早期工作的基础上，发表了一+ 篇标题为“神经网事件的 表示法”的论文，引入了正则表达式的概念。正则表达式就是用来描述他称为“正 则集的代数”的表达式，因此采用“正则表达式”这个术语。随后，k e n t h o m p s o n 将这一工作应用于搜索算法的早期研究。k e nt h o m p s o n 是u n i x 的主要发明人。 正则表达式的第一个实用应用程序就是u n i x 中的q e d 编辑器。q e d 编辑器后 来发展成为g r e p 程序。从那以后，正则表达式广泛应用于u n i x 和类u n i x 的工 具中，如a w k ，e m a c s ，v i 和p e r l ”j 。 f 则表达式是用来描述或者匹配系列符合某个语法规则的字符串的单个 字符串。正则表达式r 完全由它所匹配的串集来定义。这个集合称为由正则表 达式生成的语言，写作l ( r ) 。这里的语占仅表示“串的集合”。u r ) 首先依赖于 正则表达式r 使用的字符集，它一般是a s c i i 字符的集合或它的某个子集。正 则表达式使用的字符的集合字母表( a l p h a b e t ) ，用希腊符号表示。字母表中的 元素称为符号( s y m b 0 1 ) 。此外正则表达式还可以包含有特殊含义的字符，这样 的字符称作( m e t a c h a r a c t e r ) 。通常，元字符并不是字母表中的字符，否则当其作 为元字符时就与作为字母表中的字符时很难区分。但是，也有例外的情况。这时， 可以使用一些惯例来区分这两种用途。常见的“关掉”元字符的特殊含义的字符 是转义字符( e s c a p ec h a r a c t e r ) 。 最简单的正则表达式就是一个不合任何元字符的普通字符串。如，正则表达 式a 匹配字符a ，f 则表达式a b e 匹配字符串a b e 。最简单的元字符是“”，它能 够匹配任何单个字符。例如，正则表达式“a b ”可以匹配字符串a a b ，a b b ，a c b 等等。 定义1正则表达式是以下的一种【l 驯： 1 基本正则表达式由一个单字符a ( a 是字母表中中的普通字符) ， 以及元字符或元字符巾组成。在第1 种情况下，l ( a ) = a ；在第2 种情 况下，l ( ) = ) ；在第3 种情况下，l ( 中) = ) 。 2 r l s 格式的表达式：其中r 和s 均是正则表达式。在这种情况下， l ( r l s ) = i a r ) ul ( s ) 。 3 r s 格式的表达式：其中r 和s 是正则表达式。在这种情况下， l ( r s ) = l ( r ) l ( s ) 。 4 p 格式的表达式：其中r 是正则表达式。在这种情况下，l ( r + ) = l ( r ) + 。 浙江大学硕士学位沦文 5 ( r ) 格式的表达式：其中r 是正则表达式。在这种情况下，l ( ( r ) ) = l ( n ， 因此，括号并不改变语言，它们只调整运算的优先权。 定义1 只使用了3 种基本运算：合并、连接和重复。但是只使用这3 种运 算符来编写正则表达式有时显得很笨拙。扩展的正则表达式使用了更强大的运算 集合，可以创建更加复杂的正则表达式，因而扩大了正则表达式的表达能力。常 见的扩展运算符如： + 匹配1 个或多个字符 ? 匹配0 个或1 个字符 【 匹配括号中的任何一字符 下面是使用扩展的运算符构造的一个正则表达式： 0 【o 一9 + 其中，反斜杠“”是转义字符，因而它后面的“”失去特别含义，“”表 示范围，“0 - 9 ”表示0 到9 这_ 个数字。“【0 9 】”则匹配这十个数字中的任何一 个。正则表达式“0 f o 一9 1 + ”匹配所有的小数。 不同的应用程序对扩展运算符的支持不尽相同。p e r l ( p r a c t i c a le x t r a c t i o na n d r e p o r t l a n g u a g e ) 之所以具有强大的语言处理能力，重要原因就是它支持相当大 运算符集合，因而它的正则表达式功能之强大是其他编程语言无法达到的。 正则表达式的产生和发展和有限自动机理论的发展是分不开的。有穷自动 机，或有穷状态的机器，是描述( 或“机器”) 特定类型算法的数学方法。特别 地，有穷自动机可用作描述在输入串中识别模式的过程，因此也能用作构造扫描 程序。有穷自动机和正则表达式具有等价性，即正则表达式代表的集合，一定存在 着对应的自动机来接受它，反之亦然。 给定一个f 则表达式r 和一段文本t ，正则表达式匹配问题可以分为如下几 类： 成员判断问题( m e m b e r s h i pp r o b l e m ) ：即判断t 是否属于l ( r ) 。 决策问题( d e c i s i o np r o b l e m ) ：判断t 是否包含一个子串t ，t 属于l ( r ) 。 识别问题( r e c o g n i t i o np r o b l e m ) ：找出t 中所有属于l ( r ) 的子串。 确认问题( i d e n t i f i c a t i o np r o b l e m ) ：报告出t 出所有属于l ( r ) 的子串的 起始位置。 一直以来，解决正则表达式匹配问题的方法主要是依赖构造有限自动机，然 后使用自动机接收字符串。其中，基于( 确定性有穷自动机) 和n f a ( 非确定 性有穷自动机) 的正则匹配算法是最重要的两种方法。总体上说，基于n f a 的 正则表达式匹配方法提供更强大的功能。使用这种方法的语言和工具包括n e t 语言，r u b y ，p e r l ，p y t h o n 和g n ue m a c s 。而大部分版本的a w k 和e g r e p 、k x 和n e x 使用基于d f a 的正则表达式匹配方法。此外，还有些系统结合使用了 浙江大学硕士学位论文 两种方法或者在执行匹配时根据需求在两种方法中进行切换。本节主要介绍这两 种正则表达式匹配方法【1 9 】。 2 2 1 基于n f a 的正则表达式匹配 定义2 n f a ( 非确定性有穷自动机) m 是一个五元组 【1 8 】， 其中： 1 s 是一个有限的状念集合； 2 是字母表，确定性有穷自动机的输入字符都是的元素； 3 6 是状念迁移函数，6 ：s ( u ) 一s ： 4 s o 是自动机的初始状态； 5 f 是s 的一个子集，表示终止状态( 接受状态) 集合。 丌始时，非确定性有穷自动机m 在初始状态s 。，每次它读入一个字符c ，然 后根据6 ( s ，c ) 和6 ( s ，6 ) 的计算结果进行状态的转移。6 ( s ，) 表示不需要任何字符就可 以直接进行状态的转移。这样，每一个输入字符都可咀导致多个状态迁移，也就 是蜕状态迁移的结果是一个状态集合。n f a 的“非确定性”正体现在这里。如 果当字符串结束时它达到了终止状态，那么就说它接受了字符串。 由非确定性有穷自动机m 接受的语言写作l ( m ) 。l ( m ) 是字符串c t c 2 c 。 的集合，其中每个c i u ) ，且存在关系：s i 6 ( s o ，c 1 ) 、s 2 6 ( s l ，c 2 ) ， s n 6 ( s 。1 c 。) ，其中s 。是f ( 即接受状态) 的一个元素。 把自动机用图来表示的话，一般用节点表示状态，而节点之间有标有某个字 符的有向边，表示可以从边的起点通过这个字符转移到边的终点。终止状态节点 使用图7 ( a ) 表示，其余状态使用图7 ( b ) 表示。 o 非终止状态 终止状态 图7 有穷状态机中的节点记号 从正则表达式构造等价n f a 有两个基本的方法：t h o m p s o n 构造法和 g l u s h k o v 构造法。 1 t h o m p s o n 构造法【2 0 】 t h o m p s o n 构造法以其发明者命名。它利用转移( 即由8 导致的状态转移) 将正则表达式的自动机片段“粘在一起”以构成与整个表达式相对应的自动机。 它依照正则表达式的结构：首先为每个基本正则表达式展示一个n f a ，接着通 过连接子表达式的n f a 得到与正则表达式等价的n f a 。 如果正则表达式r = c ，与其等价的n f a 是： 浙江大学硕士学位论文 ( 韵 如果正则表达式r = ，与其等价的n f a 是 ni 偷 u崂 如果j f 则表达式r = r 1 r 2 ，那么只要把r l 和r 2 对应的自动机首尾相接就可 以得到与r 等价的n f a ： 趁立骥亘) 如果正则表达式r = r i ir 2 ，那么只要把把r i 和r 2 对应的自动机的起始状态 和终止状态分别合并就可以得到与r 等价的n f a ： 伊弋刁 【! 垦! j 如果