（计算机软件与理论专业论文）包分类算法的研究及其在防火墙中的应用.pdf

包分类算法的研究及其在防火墙中的应用 摘要 随着计算机网络与通信技术的发展，互联网高速时效性强的特点使得越来 越多的网络设备( 安全网关、路由器) 对数据包处理速度提出了更高的要求。 包分类算法作为这些网络设备中的核心算法，其速度正成为影响网络传输效率 的瓶颈，优秀的包分类算法也是i n t e r n e t 进行有差别服务的基础，因此研究高 效的包分类算法对互联网的发展具有极其重要的作用。 包分类是根据数据包头的多个域，按照规则集中指定的规则，对数据包进 行分类的技术。一般来说，任何规则的包分类都可归结为在多维空间中点的定 位问题。本文介绍了包分类算法的研究背景、定义、研究现状及其在防火墙中 的应用，分析了基于不同原理的包分类技术，深入研究了a f b v 包分类算法及 其不足之处。针对a f b v 算法存在的缺陷，本文提出了一种改进的a f b v ( e a f b v ) 算法。该算法在初始化时引入元组空间的概念重组规则库，将满足 相同条件的规则合并成一个元组，加速了规则的定位；在折叠时采用一次折叠 取代多次折叠的方法，减少了折叠的次数，有效的提高了算法的效率。 本文在l i n u x 环境下，搭建了仿真实验平台。通过实验对比了e a f b v 与 a f b v 的时间效率。实验结果表明，e a f b v 算法无论在初始化时间上还是在平 均查找时间上较a f b v 在都有着一定的提升，适合大规模多维规则库的使用。 关键字：数据包分类；向量折叠；多次折叠；元组空间 r e s e a r c ho np a c k e tc l a s s i f i c a t i o na l g o r i t h m a n di t sa p p l i c a t i o ni nf i r e w a l l a b s t a c t w i t ht h ed e v e l o p m e n to fc o m p u t e rn e t w o r ka n dc o m m u n i c a t i o nt e c h n o l o g y ，t h e h i g hs p e e da n ds t r o n gt i m ee f f e c t i v e n e s sc h a r a c t e r i s t i c so fn e t w o r km a k et h e e q u i p m e n t ss u c ha ss e c u r i t yg a t e w a y sa n dr o u t e r sp r e s e n tt h en e t w o r kw i t hh i g h e r d e m a n d t h es p e e do fp a c k e tc l a s s i f i c a t i o na l g o r i t h m sw h i c hi st h ec o r ea l g o r i t h m o ft h e s ee q u i p m e n t s ，i sb e c o m i n gt h eb o t t l e n e c ko fi n t e r n e tt r a n s m i s s i o n a e x c e l l e n tp a c k e tc l a s s i f i c a t i o na l g o r i t h mi sa l s ot h eb a s e m e n to fi n t e r n e td i f f e r e n t s e r v i c e s s od os o m er e s e a r c ho nt h eh i g h e f f e c tp a c k e tc l a s s i f i c a t i o nt e c h n o l o g y h a sd e e pi n f l u e n c eo nt h ed e v e l o p m e n to fi n t e r n e ti nt h ef u t u r e p a c k e tc l a s s i f i c a t i o ni st h et e c h n o l o g yw h i c hb a s e do nt h ed o m a i no fp a c k e t h e a da n di na c c o r d a n c ew i t ht h er u l e si nt h ed a t a b a s et oc l a s s i f yt h ep a c k e t i n g e n e r a l ，t h ep r o b l e mo fp a c k e tc l a s s i f i c a t i o ni sa l s ot h ep r o b l e mo fp o i n tl o c a t i o ni n t h eh y p e r s p a c e i nt h i sd i s s e r t a t i o nw ei n t r o d u c ep a c k e tc l a s s i f i c a t i o na l g o r i t h m r e s e a r c hb a c k g r o u n d ，t h ed e f i n i t i o no fp a c k e tc l a s s i f i c a t i o na l g o r i t h m ，t h er e s e a r c h s t a t u sa n di t sa p p l i c a t i o ni nt h ef i r e w a l lm e a n w h i l ew ea l s oa n a l y s es o m ek i n d so f p a c k e tc l a s s i f i c a t i o nt e c h n o l o g yw h i c hb a s e do nm a n yk i n d so fd i f f e r e n tp r i n c i p l e s a n dd os o m ed e e pr e s e a r c ho nt h eb e n e f i ta n dd i s a d v a n t a g eo ft h ea f b va l g o r i t h m i n t h i sa r t i c l e ，w ep r o p o s ea ne n h a n c e da l g o r i t h me a f b vi nw h i c hw eu s et h e t h e o r yo ft u p l es p a c et or e g r o u pt h er u l ed a t a b a s ea n dm a k et h er u l e sw i t hs a m e c o n d i t i o ni no n es i n g l et u p l et oa c c e l e r a t et h ep o s i t i o n i n go ft h er u l e si nt h e i n i t i a l i z a t i o nt i m e ，m e a n w h i l ew eu s eu s i n gs i n g l ef o l d i n gr e p l a c em u l t if o l d i n gt o r e d u c et h en u m b e ro ft h ef o l d i n gt i m ea n de f f e c t i v e l yi m p r o v e dt h ee f f i c i e n c yo f t h ea l g o r i t h m i n t h i sd i s s e r t a t i o nw eb u i l das i m u l a t i o np l a t f o r mt o t e s tt i m ee f f i c i e n c y b e t w e e ne a f b va n da f b vu n d e rt h el i n u xo p e r a t i o ns y s t e m t h ee x p e r i m e n t r e s u l t ss h o wt h a te a f b v a l g o r i t h mi sm o r ee f f i c i e n c yi nt h ei n i t i a l i z a t i o nt i m ea n d i nt h ea v e r a g es e a r c ht i m et h a na f b va l g o r i t h m s oi ti ss u i t a b l ef o ru s i n gi nt h e s c a la b l er u led a t a b a s e k e y w o r d s ：p a c k e tc l a s s i f i c a t i o n ；v e c t o rf o l d i n g ；m u l t if o l d i n g ；t u p l es p a c e 插图清单 图2 1 双宿主机结构图4 图2 2 主机过滤型防火墙结构5 图2 3 子网过滤其防火墙结构一5 图3 1t c a m 算法示意图1 2 图3 2b v 算法示意图13 图3 3h i e r a r c h i c a lt r i e 算法示意图1 4 图3 - 4s e t p r u n i n gt r i e 算法与h i e r a r c h i c a lt r i e 算法对比示意图1 5 图3 5 g r i d o f - t r i e 算法示意图1 6 图3 6h i c u t s 算法示意图1 9 图4 1a b vt r i e 树示意图2 2 图4 2 多次折叠示意图2 4 图4 4e a f b v 初始化示意图2 8 图4 5 预处理示意图3 0 图5 1a f b v 算法的功能模块结构图3 3 图5 2 预处理过程示意图3 3 图5 3 预处理t r i e 树建立示意图3 4 图5 4 过滤模块结构图3 5 图5 5 规则数目较少时算法初始化对比图3 9 图5 6 规则数目较多并成倍数增长时算法初始化对比图3 9 图表清单 表3 1 规则表1 3 表4 1 则表2 l 表4 2 重组之后的规则表2 1 表4 3 规则表2 1 表4 4 对应元组表2 7 表4 5 规则表2 9 表4 6 元组表2 9 表5 1 协议序列化对照表3 8 表5 2 算法初始化对比时间表3 8 表5 3 算法平均查找时间对照表4 0 表5 - 4 内存消耗数据表4 1 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成 果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得佥筵王些丕堂或其他教育机构的学位或证书而 使用过的材料。与我一同- t 作的同志对本研究所做的任何贡献均已在论文中作了明确的 说明并表示谢意。 学位论文作者签名：江所犸 签字日期：2 叩7 年手月7 7 日， 学位论文版权使用授权书 本学位论文作者完全了解金筵工些太堂有关保留、使用学位论文的规定，有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授 权佥月曼王些厶堂可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采 用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：丑 签字日期：z 口0 7 年争月 学位论文作者毕业后去向： 工作单位： 通讯地址： 电话： 邮编： 日 嘴产 ， 致谢 值此论文完成之际，我首先要感谢我的导师侯整风教授。本论文的研究工 作是在侯老师悉心指导和关怀下完成的。在三年的研究生学习期间，侯老师对 我思想上、学习工作上的循循善诱和谆谆教诲，以及生活上无微不至的关怀和 照顾，使我终身受益。侯老师渊博的知识、严谨求实的态度以及不断进取、精 益求精的精神，严谨的治学态度和诲人不倦的师长风范，都将对我今后的学习、 工作产生深远的影响，是我一生学习的榜样。感谢侯老师为我们提供了宽松良 好的科研氛围。在侯老师的指导下，我顺利完成了论文的研究和撰写，在此， 再一次对恩师致以崇高的敬意和衷心的感谢! 感谢高汉军、周伟、顾先问、袁刚，朱国正，何琢如、王娟，谷芳芳同学。 与大家在一起，我度过了最开心和最值得回忆的日子。感谢我的好友谢亮，闰 磊，孙安、方钰等同学对我论文的帮助和指导。能够进入计算机学院，和大家 同学共勉，是我的幸运，我将永远不会忘记在一起的点点滴滴。 最后，更要感谢我的父母和家人，他们的无私的关爱是我完成此论文的前 提，也是我未来前进的动力。在此，向我的父母致以崇高的敬意! 衷心的感谢所有关心和帮助过我的人们。 作者：江鹏 二零零九年 第一章绪论 1 1 包分类问题产生的背景 随着互联网技术的日新月异，i n t e r n e t 越来越贴近大众的工作和生活。安全 网关，防火墙，代理服务器等网络设备对网络服务的质量和速度提出了更高的 要求。网络服务提供商( i s p ) ，要考虑到用户的各种不同的要求及其付费行为， 对每个用户提供有差别的网络服务，诸如防火墙过滤技术【l 】、流量限速、v p n 、 居于策略路由，流量整形、流量计费、流量统计等。这些都需要网络设备将数 据包进行分类，再按照类别的不同确定是否转发数据包，数据包应得到什么样 的服务等；另一方面，各种网络设备中的包分类算法的速度正成为制约网络传 输速度的瓶颈。因此，包分类算法速度的快慢，功能的强弱等都会直接影响上 述各种网络性能。 包分类是根据数据包头的多个域，按照规则集中指定的规则，对数据包进 行分类的技术。一般来说，任何规则的包分类可归结为在多维空间中点的定位 问题。近年来随着人们对网络服务质量和速度要求的提高，包分类技术的研究 受到了广泛的关注，成为计算机网络和信息安全领域研究的热点问题。 1 2 包分类研究类型 从包分类研究的侧重点和应用的不同，可以将包分类的研究划分成三种类型 2 1 1 3 1 ： ( 1 ) 以分组的路由查找为依据的包分类。分组的路由查找，也即路由表的查 找，是根据分组头中的目的i p 地址，对不同的分组进行区分。分类算法主要采 用模式匹配查询方法。所区分出的每一分组集合中的各分组，具有相同的路由 表表项属性，如具有相同的转发端口。目前路由表查找的算法很多，相对来说 也比较成熟，但是这种研究仅以区分目的i p 地址为主要内容。 ( 2 ) 以基于规则的分组过滤为依据的包分类。该分类是按照一定的形式语言 规则，描述分组头的相应子域应满足的条件，然后按照这些规则进行相应的分 组区分。所区分出的每一分组集合中的各分组拥有相同的规则属性，如分组的 优先级别、是否被接受或拒绝等。分类所依据的分类特征是根据形式规则而定 的，主要的分类算法采用模式匹配查询方法。 ( 3 ) 以数据流的定量属性为依据的包分类，或称之为数据流的分类。流可以 是长时间维持t c p 连接的一系列数据包，也可以是声音或图像的一系列u d p 数据包。 1 3 包分类算法的研究现状 包分类算法是在9 0 年代中期被提出的，经过十余年的发展，取得了相当大 的突破，已经逐渐形成了基于不同思想的多种算法。1 9 9 8 年v s r i n i v a s a n 提出 了基于t r i e 树的算法g r i do ft r i e s ，该类型算法是构建一个等级索引树，它的 查找匹配过程是用关键字按等级依次搜索该索引树，如果找到一个匹配项，这 个链入的节点就代表一个匹配项。最坏的情况下，这类算法需要访问内存的次 数和域中的最多比特位的个数一致。一般来说基于树型结构的机制对于单个域 的搜索是有效的，但是这种机制的内存存储要求会随着搜索的维数的增加而急 剧增加。 因此人们对多维包分类问题进行了更为深入的研究。s s u r i 在1 9 9 9 年提出 基于元组的t u p l e s p a c es e a r c h 1 0 】算法。该算法是根据各域前缀的长度，将规则 聚合为元组。对每个元组执行一系列的h a s h 查找，确定最高优先级的匹配规则。 这种算法在最坏情况下需要访问内存的次数等于元组表的个数，而元组表的个 数有可能会等于规则集中规则的数目。因此该算法对于规则集的扩展性的支持 有限。 l a k s h m a n 在1 9 9 8 年提出位并行查找算法p a r a l l e lb i t v e c t o r s ( b v ) 1 l j 。它 是将多维规则匹配问题转化为一维规则匹配问题。为每一维设置一个位向量来 标记与这一维相匹配规则，各维并行执行，最后将各维的位向量相与找到最佳 匹配规则。该算法的缺点在读取各维位向量或者聚合向量时需要较多的读取次 数，特别是在规则库规模较大的时候。针对b v 算法的缺点b a b o e s c uf 在2 0 0 1 年提出了a g g r e g a t e db i t v e c t o r ( a b v ) 【l2 j 算法，通过使用位图聚合的方法降低 了b v 算法的内存占用率；随后在2 0 0 3 年l ij i 等又提出了a g g r e g a t e da n df o l d e d b i tv e c t o ra l g o r i t h m ( a f b v ) 1 3 】算法进一步对a b v 算法进行了改进。 最新的分类算法主要是体现在对已有算法的改进上，根据具体的规则库中的 特点提出的启发式算法，如p a n k a jg u p t a 在1 9 9 9 年提出的r f c 1 4 算法以及 m c k e o w nn 等在2 0 0 0 年提出的h i e r a r c h i c a lc u t t i n g 1 5 】算法。该类型的算法充分 利用规则的结构特点和冗余的特性，但是其空间复杂度往往较高。 1 4 论文的主要内容和结构安排 本文对包分类算法进行了研究，深入分析了a f b v 算法，并针对其缺点作 出了改进。提出了一种改进的e a f b v 包分类算法并对其在w i n d o w s 环境下的 性能进行了分析。论文的主要章节安排如下： 第一章：绪论。介绍包分类算法的背景，研究现状及本文所做的工作。 第二章：防火墙技术分析。介绍了防火墙的定义，体系结构及其关键技术。 第三章：经典的包分类算法。本章根据算法的实现特点，介绍四类经典的 包 分类算法，并对它们的性能进行了比较和分析。 第四章：a f b v 分类算法的研究与改进。本章详细介绍了a f b v 包分类算 2 法，针对其折叠思想的不足进行改进，提出了一种改进的e a f b v 包分类算法。 第五章：算法仿真试验及分析。本章搭建仿真平台对比验证了a f b v 与 e a f b v 算法的性能。 第六章：总结与展望。对论文提出算法的总结及对以后工作的展望。 3 第二章防火墙技术 包分类技术作为上个世纪9 0 年代兴起的一种新型技术，广泛的应用于网络 防火墙中，成为防火墙的核心技术之一，在网络安全领域起到了越来越重要的 作用。本章将对与包分类技术紧密相关的防火墙技术进行详细的介绍。 2 1 防火墙的安全体系结构 防火墙的安全体系结构大致分为5 种n7 1 ：过滤路由器结构、双宿主机结构、 主机过滤结构、过滤子网结构、吊带式防火墙结构。 ( 1 ) 过滤路由器防火墙结构 它是通过在传统的路由器中增加分组过滤功能而形成的最简单的防火墙。 这种防火墙的好处是完全透明。但由于是在单机上实现，从而形成了网络中的 “单失效点”。由于路由器的基本功能是转发分组，一旦过滤失败，就会造成 网络直通状态，任何非法访问都会直接进入内部网络。仅选择转发分组并不能 完全排除非法访问，所以内部网络中每个潜在的访问都必须增加其安全措施。 因此这种防火墙不能提供有效的安全防护功能，仅在早期的i n t e r n e t 中使用。 ( 2 ) 双宿主机防火墙结构 该结构主要由至少具有2 个接口、2 块网卡的双宿主机构成。双宿主机一个 接口接内部网络，另一个接口接外部网络。双宿主机内、外的网络可与该堡垒 主机实施通信，而内、外网络之间不能直接通信。该防火墙的安全结构如图2 1 所示。 使用时，一般要求用户先注册，再通过双宿主机访问另一边的网络。由于 代理服务器简化了用户的访问过程，可以做到对用户透明。由于该防火墙仍是 由单机组成，没有安全冗余机制，仍是网络中的“单失效点 ，所以这种防火墙 仍然是不完善的，在现在的i n t e r n e t 中仍有应用。 鱼勉勘鱼 图2 1 双宿主机结构图 ( 3 ) 主机过滤防火墙 这种防火墙是由过滤路由和运行网关软件的堡垒主机构成。该结构中提供 安全保护的堡垒主机仅与内部网络相连，而过滤路由器位于内部网络和外部网 4 络之间。主机过滤防火墙的结构如图2 2 所示。 图2 - 2 主机过滤型防火墙结构 该主机可以完成多种代理，如f t p ，t e l n e t ，还可以完成认证和交互作用， 能够提供完善的i n t e r n e t 访问控制。这种防火墙主机是网络的单失效点，也是 网络黑客集中攻击的目标，安全保障仍不够理想。但这种防火墙投资少，功能 容易实现，也便于扩充，因为应用比较广泛。 ( 4 ) 子网过滤器的防火墙结构 该防火墙实在主机过滤结构中再增加一层参数网络的安全机制，使得内部 网络与外部网络之间有两层隔断。由参数网络的内、外部路由器分别连接内部 网络与外部网络。子网过滤器的防火墙的结构如图2 - 3 所示。 近j 甲甲 选，名磊，痞辫匕d匿， l 外 火墉 i 4 垒主机 。i i i 堪占蠢磊。磊一黝 内* 一络 i 内部舫火墙 图2 3 子网过滤其防火墙结构 这种防火墙把前一种主机的通信功能分散到多个主机组成的网络中，有的 作为f t p 服务器，有的作为e - m a i l 服务器，有的作为w w w 服务器，有的作为 t e l n e t 服务器，而堡垒主机则作为代理服务器和认证服务器置于周边网络中， 以维护i n t e r n e t 与内部网络的连接。这种网络防火墙容易配置，也减少了被闯 入破坏的机会，是一种比较理想的安全防范模式。 ( 5 ) 吊带式防火墙结构 这种防火墙与子网过滤器防火墙结构的区别是作为代理服务器和认证服务 器的网关主机位于周边网络中，另外增加了内部过滤路由器保护内部网络的安 5 全。这样代理服务器和认证服务器是内部网络的第一道防线，内部路由器是内 部网络的第二道防线，而把i n t e r n e t 的公共服务器( f t p 服务器、t e l n e t 服务 器、w w w 服务器、e m a i l 服务器) 置于周边网络中，也减少了内部网络的安全风 险。 应用实践表明，过滤路由器防火墙是简单的安全防范措施，双宿主机防火 墙居中，主机过滤防火墙和子网过滤防火墙安全措施比较理想，而吊带式防火 墙安全防范措施最好，但一般在中小型企业网络应用中还不是很广。 现实意义的防火墙将多种安全技术相结合，将各种单一的防火墙相结合， 如与子网过滤防火墙结构相结合构造的防火墙，使用两台堡垒主机的参数网络 结构，使用外、内部路由器合并的过滤子网结构和多参数网络结构的防火墙。 2 2 防火墙的种类 防火墙技术可根据防范的方式和侧重点的不同而分为很多种类型，但总体 来讲可分为四大类：分组过滤、应用代理，电路级网关t 1 6 1 ，复合型防火墙。 ( 1 ) 分组过滤( p a c k e tf i l t e r i n g ) 分组过滤路由器工作在网络层，又称为包过滤防火墙，是一种通用、廉价、 有效的安全手段。它不针对各个具体的网络服务采取特殊的处理方式还提供分 组过滤功能，在很大程度地满足企业的安全要求。它根据网络的安全策略在规 则表中定义访问控制规则来决定是否同意或拒绝数据包的通过，当数据包到达 时，包过滤防火墙根据数据包中的信息在规则表中进行匹配检查，直到匹配某 条规则为止，若数据包无任何匹配规则，防火墙就使用默认规则进行处理，。 般情况下，默认规则采用的措施是丢弃数据包。包过滤防火墙通过定义基于t c p 或u d p 端口号的过滤规则，来判断是否允许建立特定的连接，如t c l n e t ，f t p 连接等。一些专门的防火墙系统在此基础上又对其功能进行了扩展，如状态检 测等。状态检测又被称为动态包过滤，它实在传统的包过滤基础上的功能扩展。 传统的包过滤防火墙无法处理需要动态开放端口的协议，因为它无法知道哪些 端口需要打开。若使用传统的包过滤，就需要将所有的端口打开，而这往往是 个非常大的范围。动态包过滤通过检查应用程序信息，来判断此端口是否需要 临时打开，而当传输结束时，端口又马上恢复为关闭状态。 包过滤的优点是不用改动客户机和主机上的应用程序，因为它工作在网络 层和传输层，与应用层无关。但其弱点也是明显的：过滤判别的只有网络层 和传输层的有限信息，因而对各种安全要求不可能充分满足；在许多过滤器中， 过滤规则的数目是有限制的，且随着规则数目的增加，性能会受到很大地影响； 由于缺少上下文关联信息，不能有效地过滤如u d p 、r p c 一类的协议；防火 墙需从建立安全策略和过滤规则入手，安全管理人员须对协议本身及其在不同 应用程序中的作用有较深入的理解，需要花费大量的时间和人力；对于采用 6 动态分配端口的服务，如很多与r p c 服务相关联的服务器在系统启动时随机分 配端口的，这样就很难进行有效的过滤；包过滤防火墙只按规则丢弃数据包 而不作记录和报告，没有日志功能。同时它不能识别相同i p 地址的不同用户， 不具备用户身份认证功能，不具备检测通过高层协议实现的安全攻击的能力。 ( 2 ) 应用代理( a p p l i c a t i o np r o x y ) ：也叫应用网关( a p p l i c a t i o ng a t e w a y ) ， 它作用在应用层，其特点是完全阻隔”了网络通信流，通过对每种应用服务编 制专门的代理程序，实现监视和控制应用层通信流的作用。它针对特定的网络 应用服务协议使用指定的数据过滤逻辑，并在过滤的同时，对数据包进行必要 的分析、登记和统计，形成报告。实际中的应用网关通常安装在专用工作站 系统上。 数据包过滤和应用网关防火墙有一个共同的特点，就是它们仅仅依靠特定 的规则判定是否允许数据包通过。一旦满足规则，则防火墙内外的计算机系统 建立直接联系，防火墙外部的用户便有可能直接了解防火墙内部的网络结构和 运行状态，这就会造成非法访问和攻击。 ( 3 ) 电路级网关 电路级网关又叫线路级网关。它在两个主机首次建立t c p 连接时创立一个 电子屏障。电路级网关用来监控受信任的客户或服务器与不受信任的主机间的 t c p 握手信息，这样来决定该会话是否合法，电路级网关是在o s i 模型中会话 层上来过滤数据包，这样比包过滤防火墙要高二层。 电路级网关还提供一个重要的安全功能：代理服务器( p r o x ys e r v e r ) 。代 理服务器是设置在i n t e r n e t 防火墙网关的专用应用级代码。这种代理服务准许 网管员允许或拒绝特定的应用程序或一个应用的特定功能。包过滤技术和应用 网关是通过特定的逻辑判断来决定是否允许特定的数据包通过，一旦判断条件 满足，防火墙内部网络的结构和运行状态便“暴露”在外来用户面前，这就引 入了代理服务的概念，即防火墙内外计算机系统应用层的“链接 由两个终止 于代理服务的“链接”来实现，这就成功地实现了防火墙内外计算机系统的隔 离。同时，代理服务还可用于实施较强的数据流监控、过滤、记录和报告等功 能。代理服务技术主要通过专用计算机硬件( 如工作站) 来承担。 2 3 防火墙关键技术 网络防火墙所涉及到的关键技术主要有：包过滤、代理、s o c k s 、状态检 查、n a t 、v p n 等【1 8 】【1 9 】【2 0 】【2 1 1 。 ( 1 ) 包过滤( p a c k e tf i l t e r ) 技术 在i n t e r n e t 上，所有信息都是以包的形式传输的，包过滤防火墙通过检查 数据流中的每个数据包，根据数据包的源i p 地址、目的i p 地址、t c p u d p 源 端口、t c p u d p 目的端口、t c p 链路状态等因素或它们的组合来确定是否允许数 7 据包通过。只有满足过滤逻辑的数据包才被转发至相应的目的出口端。其余数 据包则被从数据流中删除，以保证网络系统的安全。包过滤技术的判断依据是 防火墙系统内设置的过滤逻辑即通常所称的访问控制列表a c l ( a c c e s sc o n t r o l l i s t ) 。 包过滤技术的优点：标准的路由软件中都内置了包过滤功能，因此无需额 外费用。另外对于用户和应用透明，也就是说不需要用户名和密码来登录，用 户无须改变使用习惯。运行速度快。 包过滤技术的缺点：配置访问控制列表比较复杂，要求网络管理员对 i n t e r n e t 服务有深入了解；没有跟踪记录能力，不能从日志记录中发现黑客的 攻击记录；不能在用户级别上进行过滤；非法访问一旦突破防火墙，即可对主 机上的软件和配置漏洞进行攻击；只检查地址和端口，对通过网络链路层协议 实现的威胁无防范能力；无法抵御数据驱动型攻击：另外，大多数过滤器中缺 少审计和报警机制，且管理方式和用户界面较差：能够或拒绝特定的服务，但 是不能理解特定服务的上下文环境和数据；包过滤规则数目增加会消耗路由器 的内存和c p u 的资源，使路由器的吞吐量下降。 ( 2 ) 代理技术 代理技术的特点是将所有跨越防火墙的网络通信链路分为两段。防火墙内 外计算机系统间应用层的“链接 ，由两个终止于代理服务器上的“链接 来实现，外部计算机的网络链路只能到达代理服务器，从而起到了隔离防火 墙内外计算机系统的作用。此外，代理服务也对过往的数据包进行分析、注册 登记，形成报告，同时当发现被攻击迹象时会向网络管理员发出警报，并保 留攻击痕迹。 代理服务器接收客户请求后会检查验证其合法性，如其合法，代理服务器 客户机取回所需的信息再转发给客户。它将内部系统与外界隔离开来，从外面 只能看到代理服务器而看不到任何内部资源。代理服务器只允许有代理的服务 通过，而其他所有服务都完全被封锁住。这一点对系统安全是很重要的，只有 那些被认为“可信赖的 服务才允许通过防火墙。另外代理服务还可以过滤协 议，如可以过滤f t p 连接，拒绝使用f t p 命令，以保证用户不能将文件写到匿名 服务器。代理服务还具有信息隐蔽、保证有效的认证和登录、简化了过滤规则 等优点。 代理的缺点就是处理信息量有瓶颈。由于代理服务器需要处理流入和流出 的通信量，因而要比简单的包过滤程序慢得多。而且每增加一种新的媒体应用， 还必须对代理进行新的设置。 ( 3 ) 网络地址转换技术n a t 网络地址转换( n e t w o r ka d d r e s st r a n s l a t i o n ) 晗纠的主要功能就是通过将 i p 报头上的未经注册的i p 地址替换为合法的、己获注册的i p 地址，使整个局域 8 网的上的所有主机都可以访问i n t e r n e t 。 n a t 技术有3 种类型抬2 1 ：静态n a t ，动态n a t 和端口地址转换。 静态地址转换：在静态n a t 中，内部局域网地址和外部全局之间建立永久 的一一映射关系。当内部主机数目有限，要求访问英特网且有大量外部惟一地 址需要转换时，这种方法是十分有用的。当n a t 防火墙接收到内部主机的一个数 据包时，检查是否和静态n a t 表中的源地址条目相匹配。如果有的话，使用全局 源地址代替局域源地址并转发数据包。来自目的地址的回复恰好是相反的传输 过程。 动态地址转换：在安装了动态n a t 时，需要定义全部全局地址池以应用于 外部转换。当n a t 路由器或防火墙接收到一个内部数据包，并且配置了动态n a t ， 这时n a t 防火墙从全局地址池中选择下一步可用地址，以代替i p 头的源地址。动 态n a t 中的地址映射可以根据建立在两个给定终端之间的新会话进行改变。 端口地址转换：如果内部进行会话的主机数目大于地址库中的地址数目 时就会发生过载，过载是n a t 中一个可配置的参数，也可称为端口地址转换( p o r t a d d r e s st r a n s l a t i o n ) ，简称p a t 。这种情况下，通过使用惟一的源端口号作 为跟踪机制将内部多个主机指定为相同的全局源地址。 地址转换主要用在内部网络的i p 地址是无效地址和网络管理员希望隐藏内 部网络的i p 地址时，这种技术既解决了i p 地址不足的问题，同时又隐藏了内部 网络真正的i p ，使黑客无法直接攻击内部网络，加强了内部网的安全性。 ( 4 ) 状态检测技术 状态检测检测是第三代网络安全技术。采用的是一种基于连接的状态检测 机制，将属于同一连接的所有包作为一个整体的数据流看待，构成连接状态表， 通过规则表与状态表的共同配合，对表中的各个连接状态因素加以识别。这里 动态连接状态表中的记录可以是以前的通信信息，也可以是其他相关应用程序 的信息，因此，与传统包过滤防火墙的静态过滤规则表相比，它具有更好的灵 活性和安全性。 ( 5 ) 虚拟专用网技术 虚拟专用网( v i r t u a lp r i v a t en e t w o r k ，简称v p n ) 是通过一些公共网络( 如 因特网) 实现的具有授权检查和加密技术的通信方式。其之所以称为虚拟网，主 要是因为整个v p n 网络的任意两个节点之间的连接并没有传统专网所需的端到 端的物理链路，而是架构在公用网络服务商所提供的网络平台，如a t m ( 异步传 输模式) 、f r a m er e l a y ( 帧中继) 等之上的逻辑网络，用户数据在逻辑链路中传 输。v p n 可以帮助远程用户、公司分支机构、商业伙伴及供应商同公司的内部网 建立可信的安全连接，并保证数据的安全传输。基于防火墙的v p n 为了保证安全 性，通常采用国际标准i p s e c 作为加密、认证的协议，加强对通信双方身份的认 证，保证数据在加密、传输过程中的完整性。基于i n t e r n e t 建立的v p n ，可以保 9 护网络免受病毒感染，防止欺骗，防范商业间谍，建立访问控制，强化系统管 理，加强认证等。 防火墙的关键技术都离不开包分类技术的支持，包分类速度的快慢直接影 响到防火墙的性能。将数据包按照规则集中指定的规则快速准确的进行分类， 按照不同的类别执行不同的操作，有助于提高防火墙的运行效率。包分类技术 是防火墙各种关键技术基础，是防火墙最重要的核心技术。 2 4 本章小结 本章主要介绍了防火墙常见的体系结构，简要说明了防火墙的三种基本类 型：分组过滤路由器、应用级网关、电路级网关；分析了包过滤、代理、s o c k s 、 状态检测、n a t 、v p n 等防火墙关键技术。下一章本文将对上述防火墙这些关键 技术的基础与核心：包分类技术及其算法作详细的介绍和分析。 1 0 第三章经典的包分类算法 3 1 概述 如果把分类规则的一个域看作一维空间坐标，则一条分类规则对应d 维空 间中的一个超矩形，一个规则集便是这个多维空间里有一定优先级的超矩形的 集合，而输入的包头对应该多维空间里的一个点。这样包分类问题就成了计 算几何学里的多维空间点的定位问题。根据计算几何学的原理，在一个 有n 个不交叠超矩形的d 维空间内，当点定位算法的最优时间复杂度为 o ( 1 9 n ) 时，空间复杂度将为0 ( n o ) ；或者当时间特性为0 ( ( 1 9 n ) 小1 ) 时，空间 特性要为o ( n ) 1 2 2 。而实际的包分类规则可能是相互交叠的，甚至是包含关 系，所以包分类算法要处理的是更为复杂的多维空间点的定位问题。研究表明， 当d 3 时，包分类算法很难在时间和空间两方面取得较高的性能，因此设计一 种分类速度高效而空间消耗又比较合理的算法依然是一个难题。 3 2 包分类的定义 包分类主要是根据规则集r d ( r u l ed a t a b a s e ) ，为到达的数据包找到与之匹 配的规则项，进行不同的处理。一个规则集r d 包含a 条规则r i ( 0 i n ) 。其 中每条规则都有以下几个部分组成【3 】：相对于数据包包头的每个域有一个规则 表达式f ( i ) ，该规则的优先级p r i ( i ) 以及该规则对应的动作a c t i o n ( i ) 。 数据包匹配规则r i 被定义为：对任意i ( i = l ，2 ，3 n ) ，数据包包头p 的第i 个域p i 】匹配规则r j 的第i 个分量r j 【i 】，其中p 【i 】匹配r j i 】的主要形式有精确 匹配、前缀匹配、范围匹配。 精确匹配：r j i 】用一个值来表示，若p 【i 】= r j 【i 】，则称p 【i 】与r j i 】是精确匹 配。 前缀匹配：r j 【i 】通过一个前缀来指定，若p 【i 】与r j 【i 】表示的前缀相匹配，则 称p i 】与r j i 】为前缀匹配。 范围匹配：r j 【i 通过一个范围指定，即r j i = v a l l ，v a l 2 ，若满足v a l i p i 】 v a l 2 ，则称p 【i 】与r j i 】为范围匹配。 一般来说，任意规则的包分类可归结为在多维空间中点的定位问题：d 维空 间中有n 个d 维长方体( 规则r i ) ，分类问题是确定数据包即给定点位于哪个长 方体中。 由于p 可能匹配规则集r d 中的多条规则而产生了规则冲突，所以需要对每 条规则赋予一个代价或者优先级已解决多重匹配的问题，这样包分类过程就是 在r d 中搜索匹配p 且代价最小的规则r i 的过程，即最佳匹配过程。 定义：给定一个具有n 条过滤规则的规则库r ，与每条规则r i 相联系有一 个代价函数，记为c o s t ( r j ) ，给定一个包头p ，最佳规则匹配过程为在r d 中查 找满足下列条件的过滤规则r j ：( 1 ) r i 是p 的一个匹配过滤规则：( 2 ) 在r d 中不存在其它的过滤规则r k ，r k 与p 匹配且满足e o s t ( r k ) c o s t ( r j ) 。 根据算法的实现特点，包分类算法可以分为四类【2 l 】( 1 ) 基于硬件和硬件优 化的算法，如t c a m ，b v ，a b v ；( 2 ) 基于缓存和特殊数据结构的算法，如 r f c 、g r i do ft r i e 、c r o s s p r o d u c t i n g ；( 3 ) 基于计算几何的算法，如f i s 2 s j 、 g f i l t e r 2 6 】；( 4 ) 基于启发式规则的算法，如e g t - p c i 2 7 1 、t s s 、h y p e r c u t s 、h i c u t s 、 d c f l 2 s l 。本章主要介绍几种经典的包分类算法，并对他们的性能进行分析比 较。 3 3 经典的包分类算法 3 3 1 基于硬件和硬件优化的包分类算法 该类算法主要利用一些特殊的硬件或者硬件设备的某些特性( 如并行性、 流水性) 来实现报文分类。 ( 1 ) t c a m t c a m ( t e r n a r yc o n t e n ta d d r e s s a b l em e m o r y ) 是一种基于内容查找的存储 器，它以变量掩码的形式存储数据项，其中变量和掩码都是w 比特长，这种 形式和i p 地址的表示方法很相似，使得t c a m 在i p 路由查找中得到了广泛应 用。对于包分类问题，若w = 6 4 ，则对于一个二维包分类的规贝j j ( 2 0 2 1 9 6 5 1 枣) 、 ( 1 6 6 1 1 1 ) ，在t c a m 中将以( 2 0 2 1 9 6 5 1 0 ，1 6 6 1 1 1 o 0 ，2 5 5 2 5 5 2 5 5 0 ， 2