（计算机系统结构专业论文）基于bm和bmhs的单模式匹配算法的研究.pdf

基于b m 和b m h s 的单模式匹配算法的研究 摘要 随着互联网的迅速普及，网络内容“垃圾”已经开始侵入我们的生活。内 容过滤能有效的防止有害信息传播，是网络安全的研究热点。 模式匹配算法是内容过滤的核心技术之一，经典的单模式匹配算法一一 b m 算法，采用了好后缀跳跃规则和坏字符跳跃规则。b m h s 算法简化了b m 算法，只使用坏字符跳跃规则。 本文介绍了网络安全的研究现状和研究内容，分析了经典单模式匹配算法， 提出一种快速的单模式匹配算法( f s b m ) 。该算法结合了b m 算法和b m h s 算 法的优点，将已匹配的后缀和当前窗口后一位字符组合，提高了最大位移( m + 1 ) 的出现概率，有效地加快了匹配速度。 在分析n e t f i l t e r 防火墙框架的基础上，本文设计了内容过滤模块。在同样 的网络环境下，对b m 、b m h s 、f s b m 算法进行测试。实验表明，f s b m 算法 比b m 算法和b m h s 算法在匹配效率上占有很大优势，明显加快了防火墙检测 非法关键字的速度。 关键词：模式匹配，b m ，b m h s ，n e t f i l t e r 框架 t h er e s e a r c hf o rs i n g l e - p a t t e r nm a t c h i n g a l g o r i t h mb a s e do nb m a n db m h s a bs t r a c t w i t ht h ef a s td e v e l o p m e n to ft h ei n t e r n e t ，t h e n e t w o r kc o n t e n t s “g a r b a g e ”h a sa l r e a d yi n v a d e d o u rl i f e c o n t e n tf i l t e r i n gc a ne f f e c t i v e l y p r e v e n t t h e s p r e a d o fh a r m f u li n f o r m a t i o n ，i th a sb e c o m es i g n i f i c a n t p r o b l e m si nn e t w o r ks e c u r i t y p a t t e r nm a t c h i n ga l g o r i t h mi st h ec o r et e c h n o l o g yo fc o n t e n tf i l t e r i n g ， t h ec l a s s i cp a t t e r nm a t c h i n ga l g o r i t h m b ma l g o r i t h ma d o p t e sg o o d s u f f i x j u m pr u l e sa n db a d c h a rj u m pr u l e s b m h sa l g o r i t h mi sas i m p l i e a t i o no fb m a l g o r i t h m ，o n l yu s i n gb a d c h a rj u m pr u l e s t h i sd i s s e r t a t i o ni n t r o d u c e dt h ep r e s e n tc o n d i t i o no ft h ec o n t e n ts a f e t y a n dt h er e s e a r c hc o n t e n t s ，a n a l y s i s e dt h ec l a s s i cs i n g l e p a t t e r nm a t c h i n g a l g o r i t h m ，p r o p o s e daf a s ts i n g l e p a t t e r nm a t c h i n ga l g o r i t h m ( f s b m ) t h i s a l g o r i t h mc o m b i n e st h ea d v a n t a g e so fb ma n db m h sa l g o r i t h m ，c o m b i n e s g o o d s u f f i xa n dt h ei n f o r m a t i o nc a r r i e db yt h ec h a r a c t e rw h i c hi sn e x ta f t e r t h ec u r r e n tw i n d o w ，i n c r e a s et h ep r o b a b i l i t yo fo c c u r r e n c eo ft h el a r g e s t s h i f t ( m + 1 ) ，i m p r o v e st h em a t c h i n gs p e e de f f e c t i v e l y b a s e do nt h ea n a l y s i so fn e t f i l t e rf i r e w a l lf r a m e ，c o n t e n tf i l t e r i n g m o d u l ei sd e s i g n e d t e s t i n gb m 、b m h sa n df s b ma l g o r i t h m si nt h es a m e n e t w o r ke n v i r o n m e n t t e s ts h o w sf s b ma l g o r i t h mi sd o m i n a n to nm a t c h i n g e f f i c i e n c ya n dd i s t i n c t l yi m p r o v e st h es p e e d o ff i r e w a l ld e t e c t i n gi l l e g a l w o r d s k e yw o r d s ：p a t t e r nm a t c h i n g ，b m ，b m h s ，n e t f i l t e rf r a m e i i 插图清单 图2 1 包过滤防火墙7 图2 2 代理服务器型防火墙7 图2 3 状态检测防火墙工作流程图8 图2 4 典型的u t m 网关功能架构1 1 图3 1 文本串和模式串的当前窗口1 3 图4 1p 中存在子串l a x 2 0 图4 2p 中存在前缀v x 2 1 图4 3f s b m 算法流程图一2 3 图5 1n e t f i l t e r 框架在l i n u x 中的位置2 6 图5 2 数据包在n e t f i l t e r 框架中所经过的流程2 7 图5 3 钩子点数组示意图2 8 图5 4 规则结构图3 2 图5 5 内容过滤防火墙测试环境3 4 表格清单 表3 1b m 算法坏字符跳跃表1 4 表3 2b m 算法好后缀跳跃表1 5 表3 3b m 算法匹配过程15 表3 4b m h 算法坏字符跳跃表1 6 表3 5b m h 算法匹配过程1 7 表3 - 6b m h s 算法坏字符跳跃表1 8 表3 7b m h s 算法匹配过程1 8 表4 1b m 、b m h s 、f s b m 算法在一次尝试后的右移距离2 1 表4 2 坏字符跳跃表f s b r n b c 2 4 表4 3 好后缀跳跃表f s b m g s 2 4 表4 4f s b m 算法匹配过程2 4 表5 1 测试系统p c 配置3 5 表5 2 三种匹配算法匹配次数3 6 表5 3 三种匹配算法消耗时间( m s ) 3 6 v l l 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标志和致谢的地方外，论文中不包含 其他人已经发表或撰写过的研究成果，也不包含为获得 金曼王些态堂 或 其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所 做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签字：乙足甄易 签字日期勿矽年争月2 日 学位论文版权使用授权书 本学位论文作者完全了解 金旦曼工业太堂 有关保留、使用学位论文的规 定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被 查阅或借阅。本人授权金目曼王些太堂可以将学位论文的全部或部分论文内 容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇 编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：互元舐 签字日期：年月同 学位论文作者毕业后去向： 工作单位： 通讯地址： 导师签名： 签字日期： 电话： 邮编： 致谢 转眼之间，两年半的研究生生涯即将结束。留下的是深刻而美好的回忆， 迎接的是未来人生新的起点。值此论文完成之际，我对所有合肥工业大学的师 生表示感谢，是你们为我营造了良好的学习氛围。 首先，我要感谢我的导师侯整风教授。侯老师严谨的治学作风、求实的研 究态度、宽厚的为人以及在学术领域的远见卓识，为我树立的学习的榜样。正 因为有侯老师对我的指导和关怀，这篇论文才得以顺利完成。两年半来，侯老 师为我提出了许多宝贵的意见并给予无私的指导和帮助。他渊博的学识、为人 师表的风范、踏实做事的态度令我终身受益匪浅。在此谨向恩师致以最崇高的 敬意和最诚挚的感激。 其次，我要感谢我的父母和妹妹，是他们一直在背后默默地支持我、关爱 我，他们无私的爱是我不断前进的动力，使我顺利完成了学业。 感谢陪我一起渡过两年半研究生生活的同学们，祝愿我们的友谊地久天 长。 最后，衷心感谢评阅、评审、出席论文答辩会的各位专家在百忙之中给予 悉心指导。 i i i 第一章绪论 1 1 概述 1 1 1 本论文研究的背景、目的 随着计算机网络的迅猛发展，网络已经融入人们的生活。网络中的主机可 能会受到非法入侵者的攻击，网络中的敏感数据可能泄露或被修改，网络传送 的信息可能被他人窃听或篡改等等，这些危害直接或间接影响人们的生活，对 网络安全造成了严峻的考验。我国公安部网络安全保卫局发布的2 0 0 9 年全国信 息网络安全状况与计算机病毒疫情调查结果【lj 显示，被调查对象发生网络安全 事件的比例为4 3 ，感染计算机病毒的比例为7 0 5 。经对6 0 0 0 余家政府网 站检测显示，3 7 的政府网站存在网页安全漏洞，极易遭到网页篡改和网页挂 马等攻击破坏。2 0 0 9 年新增病毒样本2 9 9 万个，新增木马2 4 6 万多个。美国工 业安全协会的研究报告也披露，由于知识产权通过e m a i l 形式传输而导致的产 权泄密，使得美国的企业每年损失高达2 4 0 亿美元【2 1 。保障当前网络内容安全 的形势非常严峻，而防火墙技术是保护内容安全的关键技术。 自从c i s e o 公司于19 8 5 年开发出第一代防火墙包过滤防火墙开始，防火 墙技术的发展非常迅速p j 。 1 9 8 9 年，贝尔实验室的d a v ep r e s o t t o 和h o w a r dt r i c k e y 推出了第二代防火墙 电路层防火墙，同时提出了第三代防火墙的工作模型应用层防火墙( 代 理防火墙) 。 1 9 9 2 年，u s c 信息科学院的b o bb r a d e n 和a n n e t t ed e s c h o n 开发出了基于动 态包过滤( d y n a m i cp a c k e tf i l t e r ) 技术的第四代防火墙。1 9 9 4 年，以色列的 c h e c k p o i n t 公司开发出了第一个基于这种技术的商业化的产品。 l9 9 6 年，全球互联网软件集团有限公司首席科学家s c o t t w i e g e l ，开始论证第 五代防火墙架构核心代理体系结构的计划。思科于19 9 7 年发行的c i s c o c e n t r if i r e w a l l 是第一个用此架构的商业产品。但这种技术并没有得到普遍的使 用。 19 9 8 年，n a i 公司推出了一种自适应代理( a d a p t i v ep r o x y ) 技术，并在 其产品g a u n t l e tf i r e w a l lf o rn t 中得以实现。 2 0 0 4 年9 月，i d c ( i n t e r n e td a t ac e n t e r 互联网数据中心) 首度提出“统一 威胁管理”( u t m ) hj 的概念。u t m 网关是一个将防病毒、入侵检测、防火墙、 内容过滤等安全功能集成于一体的综合性防御平台，它采用高可靠性的专用芯 片及专用硬件平台、专用安全操作系统以及紧凑型模式识别语言( c p r l ) 技术 等，实现了对内容的完全性保护。 模式匹配是在文本中搜索指定模式的所有出现位置的算法，广泛应用于内 容过滤防火墙、入侵检测系统、w w w 搜索引擎等领域。模式匹配算法的优劣 直接影响到整个防火墙的内容过滤性能。因此设计更加有效的模式匹配算法是 提高防火墙内容过滤性能的关键。 1 1 2 国内外研究状况分析 最早的模式匹配算法是b r u t e f o r c e 5 】算法，该算法从左到右进行匹配，但 是可能造成回溯。 s a c o o k 在理论上证明了模式匹配问题可以在o ( m + n ) ( m 和1 1 分别为模式串 和文本的长度) 时间内解决。随后，j h m o r r i s 并d v r p r a t t 仿照c o o k 的证明构造 了一个算法。与此同时，d e k n u t h 在研究正文处理时也独立地得到与前述两人 本质上相同的算法。k n u t h 等人提出了第一个在线性时间内解决字符串的模式匹 配算法，该算法简称为称为k m p 算法【6 】。 1 9 7 7 年，r s b o y e r 和j s m o o r e 等人设计了一个与k m p 算法截然不同却有相 同线性时间复杂度的算法，称为b o y e r 。m o o r e 算法【7 1 ( 简称b m 算法) 。b m 算法 通过对组成模式串的字符进行分析，构造坏字符跳跃规则和好后缀跳跃规则， 采用自右向左扫描文本串的方式进行匹配，一旦发现不匹配，就在文本串中跳 过由坏字符跳跃规则和好后缀跳跃规则计算的最大值的距离，从而可以减少需 要匹配比较的字符数目。 r m k a r p 和m o r a b i n 提出t k a r p r a b i n 算法【8 1 ( 简称k r 算法) 。该算法利用 h a s h 方法和素数理论，首先定义一个h a s h 函数，然后将模式串和文本串中长度 为m 的子串利用h a s h 函数转换成数值，匹配时只需比较与模式串具有相同h a s h 值的子串，从而可以加快匹配速度。k r 算法也是线性时间复杂度的单模式匹配 算法，该算法开辟了模式串匹配算法设计的新思路与新方法。 h o r s p o o l 提出了简化的b m 算法一一b m h 算法【9 1 ，该算法仅使用坏字符跳跃 规则，根据当前窗口中文本串最后一个字符来决定右移距离，最大跳跃距离i n 。 d m s u n d a y 提出了b m h s 算法【l o 】。该算法是b m 算法的简化，仅使用b m 算 法中的坏字符跳跃规则，根据当前窗口的下一个字符来决定右移量，最大跳跃 距离为m + l 。 目前，对于单模式匹配算法的研究集中在如何减少匹配次数以及如何降低 匹配时间。 1 2 本论文的研究内容、解决的关键问题 1 2 1 研究内容 ( 1 ) 分析了经典的单模式匹配算法，包括b m ( b o y e r m o o r e ) 算法和 b m h s ( b o y e r m o o r e h o r s p 0 0 1 s u n d a y ) 算法，阐述了这两个算法的原理以及计算 右移量的公式。 ( 2 ) 提出了一种改进的单模式匹配算法一一f s b m 算法，该算法充分利用 已匹配的后缀和字符串后一位字符的信息，以期在每一次跳跃中跳跃尽量大的 距离。详细描述该算法的思想和实现原理，并举例说明。 ( 3 ) 分析了n e t f i l t e r 框架的运行机制及其核心函数和数据结构。在n e t f i l t e r 内容过滤模块中对b m 、b m h s 、f s b m 这三种算法进行测试。 1 2 2 本论文解决的关键问题 ( 1 ) 设计f s b m 算法的预处理函数，包括：构造和生成坏字符跳跃表 f s b m b c ；构造和生成好后缀跳跃表f s b m g s 。 ( 2 ) 设计f s b m 算法的匹配程序。 对于当前尝试，如果匹配成功，当前窗口右移一个字符。如果当前尝试失 败，f s b m 算法根据匹配失败的位置和当前窗口的紧邻下一个字符一起从 f s b m g s 表中取得好后缀跳跃距离，根据当前窗口的紧邻下一个字符从f s b m b c 表中取坏字符跳跃距离，并取这两个跳跃距离的较大者作为实际的跳跃距离。 ( 3 ) 将b m 、b m h s 、f s b m 算法加入到n e t f i l t e r 框架中的内容过滤模块。 1 3 本文的章节安排 第一章绪论。简要介绍了本文的研究目的和意义、研究的现状和主要内容、 需要解决的关键问题以及论文的组织结构。 第二章网络安全。主要介绍了网络安全的特征、防火墙技术以及网络内容 安全的现状、网络内容安全技术和u t m 网关。 第三章单模式匹配算法的研究。主要介绍了几种经典的单模式匹配算法， 分析了它们的原理，并举例说明其匹配过程。 第四章一种单模式匹配改进算法。在分析b m 和b m h s 算法特点的基础上 提出了自己的改进算法一一f s b m 算法，该算法充分利用已匹配的后缀和当前 窗口的后一位字符的信息来决定模式串的右移距离，提高了匹配效率。 第五章实验与结果分析。本章详细介绍了l i n u x 操作系统中的n e t f i l t e r 框 架和i p t a b l e s 工具的原理以及如何开发内核模块，并在此基础上提出了实验方 案，即在n e t f i j t e r i p t a b l e s 系统中对b m 、b m h s 和f s b m 算法的性能进行测试， 并分析测试结果。 第六章总结与展望。 第二章网络安全 随着计算机网络的发展，网络安全面临严峻的挑战，而如何保障网络内容 安全是网络安全的研究重点。本章主要介绍网络安全的特征和关键技术，以及 网络内容安全的现状。 2 1 网络安全概述 网络安全涉及计算机科学、网络技术、密码技术和信息安全技术等诸多领 域。它主要是指网络系统的硬件、软件及其系统中的数据受到保护，不受偶然 的或者恶意的原因而遭到破坏、更改、泄露，系统连续可靠正常地运行，网络 服务不中断。 2 1 1 网络安全的特征 网络安全概括起来有以下5 大特征 1 1 】： ( 1 ) 完整性 数据未经授权不能进行改变的特性。指信息在交换、传输、存储和处理过 程中保持不被丢失、不被修改、和不被破坏的特性，即保持信息原样性，使信 息能正确生成、存储、传输，这是网络安全最基本的特征。 ( 2 ) 保密性 信息不泄露给非授权用户、实体或过程，或供其利用的特性。指信息按给 定要求不泄漏给非授权的实体、个人或过程，或提供其利用的特性，即不允许 向非授权实体或个人泄露任何有用的信息，只允许被授权的实体或个人使用的 特征。 ( 3 ) 不可否认性 指通信双方在信息交互过程中，确信参与者所提供的信息与参与者本身的 真实同一性，即所有参与者都必须承诺其提供信息和操作的不变性，以及不可 能否认或抵赖本人的真实身份。 ( 4 ) 可用性 指在系统运行时能正确存取所需的网络信息，如果系统遭受人为攻击甚至 破坏时，被破坏的信息能迅速恢复，以便继续投入使用。衡量系统面向用户的 安全性能的一项重要指标即为可用性。 ( 5 ) 可控性 指网络系统中的所有信息都要控制在一定的传输范围和存储位置，并且信 息的传播方式以及信息内容都能被有效地控制。 4 2 1 2 威胁网络信息安全的几种攻击手段 黑客主要利用网络协议的缺陷和操作系统的安全漏洞来攻击网络信息安 全，其中攻击网络传输机制是黑客威胁网络安全的主要手段。在实际的网络攻 击手段中有很多种，归纳起来有以下两种：主动攻击和被动攻击( 如窃听) 。以 下为黑客最常用的几种攻击手段2 】： ( 1 ) 窃听：是攻击者经常采用并且不容易被发现的攻击手段。攻击者通过 监控网络数据来获得敏感信息。 ( 2 ) 伪造：攻击者通过伪造或更改i p 地址和数据包头中的i p 地址，冒充 合法用户或可信主机，达到欺骗的目的。 ( 3 ) 重传：攻击者首先截获网络数据，然后再将这些数据发送给接受者。 ( 4 ) 篡改：篡改是一种比较复杂的网络攻击手段，攻击者首先截获发出者 发出的网络数据，并对其内容进行修改，然后再把这些修改后的数据发给接受 者。 ( 5 ) 非授权访问：指没有事先没有经过认证，就非法进入网络系统，访问 网络资源或计算机资源并进行违法操作。 ( 6 ) 拒绝服务攻击：攻击者首先截获某次合法通讯中的数据包，复制后不 停地发送到网络系统中，耗费系统中大量的资源用于处理这些数据包，影响正 常工作。 ( 7 ) 病毒攻击：黑客通过网络传播病毒，因其传播速度快、范围广、破坏 性非常高，所以用户很难抵御攻击。 2 2 防火墙技术 防火墙13 】【1 4 1 5 1 是处于内部网络和外部网络( 如i n t e r n e t ) 之间的一种有效安 全设备，它可通过监测、限制、更改跨越防火墙的数据流，尽可能地对外部网 络屏蔽内部网络的信息、结构和运行状况，最大限度地阻止非法用户( 如黑客、 网络破坏者等) 进入内部网络，从而实现对内部网络的安全保护。 2 2 1 防火墙的功能 ( 1 ) 创建阻塞点 防火墙在内部网络和外部网络间建立个安全控制检查点。检查点建立之 后，防火墙就可以允许、拒绝或重新定向所有流经的数据流。因此在网络安全 行业中将检查点称为“阻塞点”。可以在阻塞点加载内容过滤模块，对经过的 数据包包头信息进行过滤( 即包过滤) ，也可对数据包内容进行过滤( 即内容 过滤) 。 ( 2 ) 隔离不同网络，防止内部信息的外泄 企业、政府部门、部队机关等的秘密是非常受关注的，这些部门网络中极 其细微的细节都有可能包含有关安全的线索而引起外部攻击者的兴趣。使用防 火墙就可以对外部网络屏蔽那些能透漏内部细节的服务，如f i n g e r 能显示主机 用户的注册名、真实姓名，最后登录时间和使用s h e l l 类型等。攻击者非常容易 截获这些信息，并根据所截获的信息对内部网络展开攻击。 ( 3 ) 强化网络安全策略，提供集成功能 以防火墙为中心的安全方案配置，能将安全功能( 如口令、加密、身份认证、 审计等) 部署在防火墙上。这种集中安全管理方式比将网络安全问题分散到各个 主机上更经济，更有效。 ( 4 ) 审计和记录内、外部网络之间的活动 由于防火墙处在内、外部网络之间的阻塞点，因此能对内、外部网络通讯 和访问进行监控审计。当发生可疑动作时，防火墙能进行及时的报警，并提供 网络是否受到破坏及攻击的详细信息。同时防火墙能记录所有经过的访问并对 网络使用情况进行数据统计。网络管理人员根据这些信息可以清楚地了解防火 墙的保护能力和运行状况，及时地将威胁拒之门外。 2 2 2 防火墙技术的分类 根据防火墙结构和构造方法的不同，传统防火墙技术【l6 】分为三类：包过滤 防火墙，代理服务器型防火墙，状态检测防火墙。 ( 1 ) 包过滤防火墙 由于包过滤防火墙【l7 l - 1 - 作在t c p i p 协议的网络层上，所以也被称为网络 层防火墙，如图2 1 所示。包过滤防火墙通过检查数据包的包头信息，根据防 火墙内事先设定的过滤规则进行判断，有选择的允许通过或拒绝通过。数据包 的过滤通过检查数据包的包头信息实现，这些信息包括数据包的源地址、目的 地址、t c p u d p 源端口号、t c p u d p 目的端口号、传输的协议类型( t c p 、 u d p 、i c m p 等) 及数据包头中的各种标志位。包过滤防火墙包括以下两种： 静态包过滤( p a c k e tf i l t e r i n gf i r e w a l l ) 防火墙 这类防火墙是最传统的防火墙，其使用i p 分组报头中存储的信息控制网络 传输。当防火墙设备接收到分组时，将报头中存储的数据属性与过滤规则相匹 配，根据匹配结果的不同，决定该分组是被丢弃还是允许通过。 动态包过滤( d y n a m i cp a c k e tf i l t e r i n gf i r e w a l l ) 防火墙 动态包过滤能动态地决定用户可以使用哪些服务及服务的端口范围，减少 受到攻击的风险。只有符合允许条件的用户请求到达后，动态包过滤防火墙才 开启相应端口并在访问结束后立即关闭端口，避免了静态包过滤防火墙端口开 放的根本缺陷。 图2 1 包过滤防火墙 包过滤防火墙只检查数据包的包头信息，而不检查数据包的内容，所以速 度非常快。 ( 2 ) 代理服务器型防火墙 代理服务器型防火墙【l8 1 也被称为应用网关防火墙，如图3 2 所示，这种防 火墙工作在应用层，是内部网和外部网的隔离点，完全“阻隔”了网络数据流， 通过防火墙策略，实现监视和控制网络通信流的作用。 代理型防火墙有如下两种类型： 应用网关( a p p l i c a t i o ng a t e w a y ) 型防火墙 这类防火墙工作于应用层，针对特定的应用层协议和命令进行解释。它将 用户发来的服务请求进行解析，经过规则过滤与审核后，重新封包成由防火墙 发出的服务请求数据，进行转发。当响应返回时，再次执行与上面过程相反的 动作，防火墙代替服务器对用户请求应答。 客户 图2 - 2 代理服务器型防火墙 7 电路级网关( c i r c u i tp r o x y ) 防火墙电路级网关工作在传输层上，用来监 控两个通信的终点之间的t c p 握手信息并转换数据包。由于它不允许用户建立 端到端的t c p 链接，数据需经过电路级网关转发且内部网络的i p 地址都通 过网络地址转换映射到防火墙i p 地址上，所以将电路绒网关归入代理型防火墙 类型。其工作原理如图2 2 所示。 代理服务器型防火墙的工作过程是：当用户需要访问外部网络服务器时， 对于符合代理防火墙安全策略的连接，代理服务器会代替外部网络服务器回应， 并重新向外部网络服务器发出一个相同请求。当此连接请求得到回应并建立连 接之后，用户和外部网络服务器之间的通信通过代理程序将相应的连接映射实 现。由于代理服务器型防火墙完全“阻隔”了内部网和外部网的直接联系，使 得黑客很难探测防火墙内部系统的信息，从而避免了入侵。 代理服务器型防火墙支持常见的应用服务( 如f i t t p 、h t t p s s s l 、s m t p 、 p o p 3 、p t p 、t e l n e t 等) ，能灵活地控制进出的流量、内容，能过滤数据内 容。但由于为每种应用分剐编写不同的代理程序，降低了透明性，同时代理服 务器型防火墙转发每一个访问请求，所阻速度较慢。 敷据包是i 属于一 、譬? 箩 【封数据包的状女 一 n ：廷口b “哆二! - 、 ， t ，一 # 数据包# 发到最终、 7 扣辩& 敦掘包 口地m 井h * * l 志e 泵 i m 行h 志t 圈2 - 3 状态检测防= j ( 墙r 作流程图 ( 3 ) 状态检测防火墙 状态检测技术m3 又称为动态包过滤技术，是在传统包过滤上的功能扩展， 最早由c h e c k p o i m 公司提出。对于一个新建的应用连接，防火墙根据安全规则 决定是否允许此连接，如果允许建立连接的请求就可| 三【“穿过”防火墙，这 点和普通的包过滤防火墙相同，然后防火墙将该连接的信息存入状态表中，对 该连接的后续数据包，只要符合状态表，可以直接通过。而u d p 协议和i c m p 协议是无连接的，这时防火墙采用“伪连接 的方式进行判断，工作流程如图 2 3 所示。 状态检测防火墙对已经建立连接的数据包不再进行规则检查，因而过滤速 度更快。但尽管增加了基于状态的特征，但其本质上还是包过滤防火墙，无法 深入到上层协议，因此传统包过滤防火墙的一些不足仍然存在。 2 3 网络内容安全 2 3 1 网络内容安全现状 网络内容安全是网络安全的一个重要研究方向，是目前信息安全中最为活 跃的安全领域。内容安全的宗旨1 2 0 是防止未经授权的信息内容进出网络。 w e b 诞生于上世纪9 0 年代中期，经过多年的发展，目前主要表现为三种【2 l 】 形式：超文本( h y p e r t e x t ) 、超媒体( h y p e r m e d i a ) 、超文本传输协议( h t t p ) 。 由于信息的爆炸式膨胀，w e b 中充斥着各种各样的信息，其内容安全面临严峻 的挑战。据g o o g l e 公司统计，g o o g l e 服务器中已经索引了一兆的网页。在如 此巨大数量的网页中存在各种信息，其中不乏色情、暴力、反动以及黑客内容。 据统计，目前垃圾邮件约占全部邮件的9 0 左右，全球企业每年大概要花 8 0 亿到1 0 0 亿美元来解决垃圾邮件问题。垃圾邮件【2 2 】【2 3 1 的泛滥带来了严重的 危害：在互联网上传输时占用大量网络带宽和存储资源，阻塞邮件服务器， 从而降低了网络的运行效率。同时，垃圾邮件成为病毒的载体，危害了互联网 安全。侵犯邮用户隐私权，由于垃圾邮件具有强制性、反复性和传播速度快 等特点，严重干扰了用户的个人生活并损害了用户的利益。成为不良信息的 载体，被少数别有用心者利用来传播各种色情和反动信息，严重危害国家的安 全和社会的稳定。 为了保护网络内容安全，网络内容安全产品应运而生。国外主要有美迅智 公司的r i s kf i l t e r 、w e bf i l t e r 的系列产品以及b l u ec o a t 公司的p r o x ys g 。w e b f i l t e r 是基于网页过滤的内容安全产品，适用于小型办公机构，其主要功能有： 自定义互联网权限；高效的过滤功能；实时监控上网情况记录网络使 用行为。p r o x ys g 则是一款内容过滤产品，可同时实现w e b 内容过滤、病毒 扫描、聊天软件控制，p 2 p 文件共享控制。国内内容安全研究起步较晚，但发 展非常迅速，具有代表性的产品如金山k i n g g a t eu t m ( 统一威胁管理) 安全 网关。该产品可以防范网络攻击，控制非法访问，阻挡病毒入侵，免受垃圾邮 件干扰，避免企业机密信息泄露，进行实时内容监控和系统管理。 9 2 3 2 网络内容安全技术 按照用途的不同，网络内容安全过滤技术主要分为w e b 内容过滤技术和 垃圾邮件过滤技术【2 引。 ( 1 ) w e b 内容过滤技术 w e b 内容过滤技术f 2 5 】主要包括：模式匹配算法全文检索自然语言 处理。 模式匹配算法是应用于w e b 内容安全的基本技术，即在网页中搜索模式 串集合的所有出现位置。根据在匹配过程中需要匹配的模式串个数，模式匹配 算法分为单模式和多模式两种；根据功能划分，模式匹配算法分为三类：精确 模式匹配、近似模式匹配和正则表达式。 基于全文检索技术【26 】的搜索引擎通过采集标引大量网页，提供全局性网络 资源控制与检索机制。将全球或特定领域网络中所有的信息资源做一个完整的 集合、整理和分类，方便用户查找所需信息。 自然语言处理技术【2 7 】包括词法分析、语义分析、自动摘要和文本挖掘等。 而在所有的这些技术中，自动分词、文本分类和文本聚类技术是最基础和最重 要的技术。汉语自动分词是由机器在文本的词与词之间加上分词符号。文本分 类是对未知类型的文字文档进行处理，判别它们属于预定义类别集合中的一个 或多个类别。文本聚类实在没有分类体系和没有训练样本的情况下，对文本集 进行分类。 ( 2 ) 垃圾邮件过滤技术 垃圾邮件过滤技术的研究从9 0 年代中期开始，根据邮件系统的角色不同划 分，可将垃圾邮件过滤技术分为两类【2 引：基于服务器端的过滤，通常运行于邮 件服务器，通过检查信头、信体及附件来阻止那些垃圾信息。基于客户端的过 滤，用户可以采用客户端过滤软件，利用其分拣和过滤功能来设定规则，检查和 匹配所接收的邮件，根据邮件的地址来源、主题和正文内容中的关键词，对那些 符合垃圾邮件特征的邮件执行特定操作。从垃圾邮件过滤技术上划分，目前主要 有基于规则的过滤和基于统计的过滤两类：基于规则的过滤就是通过信头分 析、群发过滤和关键词精确匹配来判定是否为垃圾邮件，基于规则的过滤方法 有r i p p e r 方法、决策树方法、b o o s t i n g 方法和粗糙集方法等。基于统计的过 滤是使用统计方法来解决邮件的二元分类问题，基于统计的过滤方法有 b a y e s i a n 分类算法、s v m 方法等。 2 3 3u t m 网关 随着i t 技术的不断发展，网络攻击行为逐步呈现出复杂化的趋势。传统的 防火墙、入侵检测系统入侵防护系统( i d s i p s ) 或防病毒等单一功能安全产 1 0 闰吲r r , s f 阁闰闰h r 一_ 二 耋望窒全堡堡罨簦l 图2 4 典型的u t m 网关功能架构 ( 1 ) u t m 的关键技术 u t m 网关需要对多项安全技术进行无缝集成，在不降低性能的情况下，实 现七层协议的安全保护。以下具体介绍u t m 网关所包含的关键技术： 内容过滤 内容过滤模块对o s i 模型中描述的所有层次的网络威胁进行实时处理。与 目前的状态检测技术、深度包检测技术等相比，这种技术的安全性更高。它能 将网络层数据重组为应用层对象( 如文件、文档等) ，并对重组之后的应用层对 象采用动态更新的病毒特征码、垃圾邮件特征码、非法关键字等来进行扫描和 分析，从而达到探测出各种威胁( 如病毒攻击、不良w e b 内容、垃圾邮件等) 的目的。 硬件加速技术 由于u t m 网关实现了内容的完全性保护，其需要处理的内容数量势必会大 量增加，而且这些内容还需进行防火墙、防病毒、内容过滤等多项安全检测， 这要求u t m 网关必须具有非常高的性能。目前，a s i c 芯片常被作为提升u t m 网关性能的一个关键组成部分。它集成了各种常用的加密、解密、规则匹配、 数据分析等功能，实现对数据进行硬件加速处理，保证了u t m 网关的正常运作。 专用安全操作系统o s 专用安全操作系统提供了精简而高效的底层支持，可以让硬件平台发挥最 大限度的能力。同时，通过专门的实时性设计，提供实时内容重组和分析能力， 并采用智能排队和管道管理技术对目标数据进行智能化的管理，使各种类型数 据的处理时延达到最小，实时、有效地实现防病毒、防火墙、v p n 、内容过滤 等子系统功能。 紧凑型模式识别语言( c p r l ) c p r l 是为了快速执行完全性内容检测而设计的。这种语言不仅具有非常高 的执行效能，而且能使防病毒、防火墙、入侵检测等多种安全模块非常有效地 协同工作，提升了威胁检测的效率。 动态威胁防护系统( d t p s ) d t p s 是一种全新的处理技术，是对传统安全威胁检测技术的一种突破。 其将防火墙、防病毒、入侵检测等功能模块的检测过程关联在一起，跟踪每一 个安全环节的检测活动，实现信息的共享使用，并通过异常检测引擎检查和启 发式扫描，使系统同时具备对已知和未知威胁的检测能力。 ( 2 ) u t m 网关的优点 一体化设计带来的成本降低。u t m 网关以较低的成本将多种安全功能整 合在同一产品当中，使这些功能协调一致地工作，满足了企业对信息处理安全 的大部分功能，避免了使用多个单功能设备所带来的高昂的采购维护成本。 易于部署和管理。由于u t m 集成多种安全产品的功能，并且采用简单 易用的界面方便用户进行操作和维护，所以无论是部署过程，还是日常的管理 和维护，对于具有同等安全需求的用户来说，其工作强度都有很大的降低。 ( 3 ) u t m 网关的缺点 高集成的风险。将所有安全功能集成在u t m 网关中，使得抵御风险能力 有所下降。u t m 网关一旦出现故障或因自身的漏洞而被攻击，不仅将导致所有 的安全防御措施失效，还会影响整个网络的正常运行。 性能和稳定性。尽管目前已使用了很多专门的软硬件技术来保证u t m 网 关的性能，但由于各功能模块的实现原理、效率等不同，功能模块之间协同工 作容易造成整体性能的下降，而要求更高的性能输出势必会对系统的稳定性造 成一定的影响。 1 2 第三章单模式匹配算法的研究 模式匹配是计算机领域的一个重要研究方向，在w w w 搜索引擎、内容过 滤防火墙、入侵检测系统等领域都有很重要的理论研究和应用价值。模式匹配 算法分为单模式和多模式两种。本章主要研究和分析经典的单模式匹配算法， 包括b m e7 1 、b m he 9 】和b m h s i o l 算法。 3 1 相关定义 定义1 ：单模式匹配算法是指在文本串中检索某个特定模式串的所有出现 位置。在模式匹配过程中，如果在文本串中搜索到与模式串相同的子串，则称 为匹配成功；否则称为匹配失败。 定义2 ：设x ，y 和z 均为字符串，则称x 为x y 的前缀，称x 为y x 的后缀， 称y 为x y z 的子串。 定义3 ：用t 0 ，1 ，n 一1 表示文本串，长度为n ，用p 0 ，1 ，m - 1 】表示要匹 配的模式串，长度为m 。匹配过程中t 与p 中长度为m 的子串的一次比较称为 一次尝试，当前尝试中与p 对齐的t 的子串称为当前窗口，如图3 1 所示。 当前窗口 3 2b f 算法 蛮力算法( b f 算法f 5 1 ) 是最早的单模式匹配算法，其匹配过程就是将文本串 和模式串对齐，从左向右逐个搜索，并依次比较文本串与模式串中的字符是否 全部相同，若全部相同，则一次匹配成功，若模式串中的某一个字符匹配失败， 则将模式串p a t t e r n 向右移动一位，继续从模式串的第一位向右开始搜索，直至 文本末尾结束。 该算法简单、直观，无需任何预处理，因而不需要额外的存储空间，但是 对文本的扫描需要回溯。 t 3 3b m 算法 3 3 1b m 算法的跳跃规则 1 9 7 7 年b o y e r 和m o o r e 提出了著名的b m 算法，该算法在匹配过程中，模 式串p 0 ，1 ，2 ，i t i 一1 】从左向右移动，字符的比较从右向左进行，即按 p m 一1 】，p m 2 】，p 0 】次序进行比较，当匹配失败时，使用坏字符跳跃表和好后 缀跳跃表，并取二者最大值来决定模式串的右移量，移动尽可能远的距离。b m 算法模式串右移算法如下： ( 1 ) 好后缀跳跃规则。具体分以下两种情况： 模式串p 中间的某一子串p j - s + l m s 与已比较部分p j + l m 】相同， 可让p 右移s 位。 p 已比较部分p j + l m 】的后缀p s + l m 】与p 的前缀p 1 m + s 】相同， 可让p 右移s 位。满足上述情况s 的最小值为最佳右移距离。 好后缀跳跃规则定义如下： s r u 沙u ) = m i n s i ( p u + 1 ，川= p j - s + l ，l s ) & & p u 】p l ，- s ( j j ) ， p s + l ，m 】- p 1 9 1o ，历一s 】( ，s ) ) ( 2 ) 坏字符跳跃规则。 假设匹配在文本串t i 】处失败，此时对应的模式串字符为p d 】，利用t 【i 】在模 式串中出现的位置来决定右移量。坏字符跳跃规则定义如下： j k i p p ，= ：甥三裟犹箸嚣舅曼掣器他隋况 3 3 2b m 算法步骤 以文本串“d e c b e f a d e a b a d c d c d e a d b a d 和模式串“c d e a d b a d 为例来模拟 b m 算