（管理科学与工程专业论文）防火墙规则匹配算法比较分析研究.pdf

摘要 摘 当今社会，信息安全问题越来越受到企业和个人的重视。防火墙作为一种信 息安全的工具，发挥着“网络安全的第一道闸门”的作用。根据系统管理员的配 置，防火墙能够阻止外部网络未授权的数据包访问内部网络，从而可以保护企业 内部网络。然而如果防火墙配置不当，则很容易使其成为遭受网络攻击的命门， 因而优化防火墙配置，增强防火墙的过滤性能具有重要意义。 本文研究了当前防火墙领域内的两个主要问题：规则的配置和规则的优化问 题。系统地指出了规则之间可能出现的冲突，并简单介绍了两种冲突检测算法。 关于规则的优化问题，本文综合介绍了目前已有的几种算法以及他们的主要思想， 并对各种算法的时间，空间需求进行了分析。 在此基础上，本文还提出了一种改进的优化规则匹配的算法。我们首先结合 非参数统计的理论，建立了一个预测数据包的统计模型，并在此模型预测的概率 及f d t 基础上，提出了规则空间( r u l es p a c e ) 的概念，并给出了规则最优排序的 方法，最后通过仿真实验验证了该算法确实极大地提高了防火墙的过滤能力。 我们将本文提出的算法与已有的算法在时间复杂度，空间复杂度方面进行了 比较分析。我们对几种算法做了仿真实验比较，实验结果表明，在大规则集，范 围匹配的情况下，本文的算法在这些算法之中具有最好的平均性能。 关键词：防火墙冲突检测规则排序算法统计模型规则空间 a b s t r a c t a b s t r a c t i n f o r m a t i o n s e c u r i t y ( i s ) p r o b l e mb e c a m em o r e a n dm o r ei m p o r t a n tf o r e n t e r p r i s e sa n dp e r s o n a li nt h ec u r r e n ts o c i e t y a sat o o lo fi n f o r m a t i o ns e c u r i t y , f i r e w a l lp l a y sa ni m p o r t a n tr o l ea s t h ef r o n to fi n f o r m a t i o ns e c u r i t y f i r e w a ue a r l p r o t e c tt h ei n s i d en e t w o r k so ft h ee n t e r p r i s e a c c o r d i n gt ot h ec o n f i g u r a t i o nf i l e ， f i r e w a l lr e je c t st h eu n a u t h o r i z e dp a c k e t st h o s ec o m ef r o mo u t s i d en e t w o r k st og oi n t o t h ei n s i d en e t w o r k s b u ti faf i r e w a l li sn o tp r o p e r l yc o n f i g u r e d ，i ti se a s i l yt ob e c o m e ab o t t l e n e c ko ft h en e t w o r k , a n de a s yt ob ea t t a c k e d s oo p t i m i z i n gf i r e w a l l c o n f i g u r a t i o n ，e n h a n c i n gt h ep e r f o r m a n c eo ff i r e w a l li so fg r e a ti m p o r t a n c e t h i sp a p e rr e s e a r c h e do nt w om a i nq u e s t i o n so ff i r e w a l lt h e o r y ：o n ei st h e c o n f i g u r a t i o no fr u l e so faf i r e w a u ；t h eo t h e ri st h eo p t i m i z a t i o no ff i r e w a l l i nt h i s p a p e rw ei l l u s t r a t e dt h ea n o m a l i e st h a tm a ye x i s tb e t w e e nt w or u l e s ，a n dw ea l s o i n t r o d u c e dt w oa l g o r i t h m sf o rf i n d i n ga n o m a l i e sb e t w e e nt h er u l e s f o rt h es e c o n d q u e s t i o n ，o p t i m i z a t i o no ff i r e w a l l ，w es y n t h e t i c a l l yi l l u s t r a t e dt h em a i na l g o r i t h m sf o r t h i s q u e s t i o n ，a n dw ea l s oa n a l y z e dt h et i m ea n ds p a c ec o m p l e x i t yo f t h e s e a l g o r i t h m s b e s i d e s ，w ep r o p o s e da na m e l i o r a t ea l g o r i t h mf o ro p t i m i z i n gf i r e w a l lr u l eo r d e r s a c c o r d i n g t ot h et h e o r yo fn o n - p a r a m e t e r ss t a t i s t i c s ，w eg i v eas t a t i s t i c a lm o d e lt h a t f o r e c a s t st h ep a c k e t s b a s e do nt h i sf o r e c a s t i n gp r o b a b i l i t ya n df d ts t r u c t u r e ，w e p r o p o s e dt h ec o n c e p to fr u l e _ s p a c e ，a n dw eg i v eo u t t h e c o n c l u s i o no fo u r o p t i m i z i n go r d e ro fr u l e s t h r o u g ht h ee x p e r i m e n t ，w ec a l ls e et h a tt h i sa l g o r i t h m i m p r o v e st h ep e r f o r m a n c eo ff i r e w a l ls i g n i f i c a n t l y w ea l s oc o m p a r e do u ra l g o r i t h mw i t ht h ec u r r e n ta l g o r i t h m si nt h et i m e c o m p l e x i t ya n ds p a c ec o m p l e x i t y w ec o m p a r eo u ra l g o r i t h mw i t ho t h e ra l g o r i t h m s t h r o u g hs i m u l a t i o ne x p e r i m e n t s m er e s u l ts h o w st h a t ，u n d e rt h ec o n d i t i o no fb i gr u l e s e t sa n dr a n g em a t c h i n g ，o u ra l g o r i t h mp e r f o r m a n c e sb e s ta v e r a g ep r o p e r t ya m o n g t h e s ea l g o r i t h m s k e yw o r d s ：f i r e w a l l ，a n o m a l yc h e c k i n g ，r u l eo r d e r i n ga l g o r i t h m ，s t a t i s t i c a lm o d e l ， r u l e s p a c e i l 中国科学技术大学学位论文原创性声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得的成 果。除已特别加以标注和致谢的地方外，论文中不包含任何他人已经发表或撰写 过的研究成果。与我一同工作的同志对本研究所做的贡献均已在论文中作了明确 的说明。 作者签名：登鸽爹 签字日期：塑习l 二兰二篁 中国科学技术大学学位论文授权使用声明 作为申请学位的条件之一，学位论文著作权拥有者授权中国科学技术大学拥 有学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构送交 论文的复印件和电子版，允许论文被查阅和借阅，可以将学位论文编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。本人 提交的电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 面开 口保密( 盈尊年) 作者签名：王茎堑：丝：导师签名： 签字日期： 幽! 叠! 窒 签字日期： 之皂霉 第一章绪论 1 1 信息安全与防火墙 第一章绪论 在当今社会，信息对于每个企业，每一个人都有着重要的作用和价值。随着 计算机的普及和i n t e m e t 的发展，信息安全问题越来越受到人们的关注。信息的 及时，有效，完整和机密性都已经成为了企业的一项资产，如何保持和保护信息 的这些重要特性也直接影响着企业的经营状况，这些都需要信息安全技术的支持， 由此也产生了一系列的信息安全产品。作为本文的开始部分我们首先了解一下信 息安全。 1 1 1 信息安全简介 信息安全本身包括的范围很大，大到国家军事政治等机密安全，小范围的包 括防范商业企业机密泄露，防范青少年对不良信息的浏览，个人信息的泄露等。 从广义来说，凡是涉及到网络上信息的保密性、完整性、可用性、真实性和可控 性的相关技术和理论都是网络安全的研究领域。 当前比较流行的信息安全产品( 或称信息安全技术) 主要有防火墙，入侵检 测( i d s ) ，入侵防御系统( i p s ) 。防火墙技术作为信息安全的第一道防线，从诞 生至今已经历了很大的发展，本文主要研究的内容便是防火墙技术。 1 1 2 防火墙的概念及作用 防火墙是一种较早的信息安全技术。在计算机网络中，防火墙作为信息安全 的第一道防线，发挥着重要的作用，它可以防止指定类型的信息在外部世界( 称 为不信任网络，如i n t e m e t ) 和内部世界( 称为信任网络) 之间来回移动。防火 墙可以是单独的计算机系统、运行在已有路由器或服务器上的软件服务，或包含 许多支持设备的单独网络。它为数据传输提供了物理访问控制机制，通过配置一 定的规则，防火墙对进出网络的数据包进行筛选过滤；设置在内外部网络的交界 处，防火墙可以阻止非授权用户进入安全网络，还可以防止内部合法用户的超越 使用权限行为，这就是防火墙的主要作用。 第一章绪论 1 2 防火墙的分类 按照处理模式分类，防火墙有5 种主要的处理模式：包过滤防火墙、应用网 关、电路网关、m a c 层防火墙和混合模式的防火墙。下面我们将分别介绍这几 种模式，其中，包过滤型防火墙将成为本文研究的重点。 1 2 1 包过滤防火墙 在介绍包过滤防火墙前，我们首先了解一下数据包的结构。在t c p i p 协议下， 数据以包的方式发送，这类似于将信放入信封中。每个数据包包含首部( 标题或 称包头) 和数据本身，其中首部包含与数据包从哪里来以及要到哪里去等相关的 信息。下图描述了一个典型的t c p i p 数据包。 版本 i h l 服务类型总长度 标识 标志片偏移 生存时间 协议首部校验和 源地址 目的地址 可选项( 加上填充) 数据( 可变长度) 图1 1 典型的t c p h p 数据包格式 从图1 1 可以看出，数据包由首部和数据两个部分构成，首部包含了版本， 首部长度( i h l ) ，服务类型等字段。其中源地址指明了数据包发送节点的i p 地址 和端口号，目的地址指明了接收节点的i p 地址和端口号，协议类型指示了在口 处理完成后，是哪个上层协议接收进来的数据包。源i p 地址( si p ) ，源端口号 ( s，目标i p 地址( di p ) ，目标端口( d和协议类型 是大多数防火墙过滤数据包时主要检测的字段。 包过滤防火墙扫描网络数据包，查找遵循或违反防火墙规则的情况。它在网 络层上检查包，数据包进入网络层时，它检查数据包的标题信息( 包的首部) ， 根据防火墙的配置文件，寻找匹配该数据包包头信息的规则。如果发现匹配某条 规则，则根据该规则，阻止( d e n y ) 或允许( a c c e p t ) 该数据包从一个网络传送到另一 个网络。 包过滤防火墙有三个子类：静态过滤、动态过滤和状态检查。 静态过滤：静态过滤要求开发和安装一些过滤规则，以控制防火墙确定允许 哪些包通过，拒绝哪些包通过。这类防火墙在网络路由器和网关中常见。 动态过滤：动态过滤允许防火墙对紧急事件做出反应，更新或建立处理事件 第一章绪论 的规则。这些反应可以是积极主动的，允许内部用户参与特定的行动，也可以是 消极被动的，在检测到某类不良的包大量出现时，就从某个地址删除所有包。静 态过滤防火墙允许某一类包全部进入，以响应授权的请求，而动态过滤防火墙只 允许指定源、目标和端口地址的包通过防火墙，它根据包标题保护的信息打开和 关闭“门 ，使动态包过滤器成为传统静态包过滤器和应用程序代理之间的一种 中间形式。 状态检查。也称为状态防火墙，它使用状态表跟踪内部和外部系统之间的所 有网络连接。状态表记录了哪一站何时发送了哪个包，来跟踪绘画中每个包的状 态和环境。像第一代防火墙一样，状态检查防火墙也进行包过滤，但它更进一步。 简单的包过滤防火墙只根据数据包的地址允许或拒绝某个包进入，而状态防火墙 可以阻止不响应内部请求的包。如果状态防火墙收到一个不匹配其状态表的包， 就默认通过其a c l 判断是否允许该包通过。 1 2 2 应用网关 应用网关也称为应用级防火墙或应用防火墙，常常安装在专用计算机上，与 过滤路由器分开，但通常和过滤路由器一起使用。应用级防火墙也称为代理服务 器，它运行特定的软件，为服务请求提供代理。应用级防火墙的一个常见例子是， 防火墙阻止对机构内部计算机上的w e b 页面和服务的所有请求和响应，它把这 些请求和响应送到机构网络中不太安全的区域中的中间计算机上。应用防火墙的 主要缺点是，它们是为特定的协议而设计的，不能方便地重新配置为对抗其他协 议的攻击。 1 2 3 电路网关 电路网关防火墙在传输层上工作。连接也是根据地址来授权建立的。与过滤 防火墙一样，电路网关防火墙通常也不理会在网络之间通过的数据流，但阻止网 络之间的直接连接。为此，它们在防火墙的每一端建立了连接特定进程或系统的 信道，在这些信道中，只允许进行授权的通信，例如只有授权用户能使用的特定 类型的t c p 连接。 1 2 4m a c 层防火墙 m a c 层防火墙不像上述防火墙那样著名，使用也不是很广泛，它用于在o s i 网络模式的媒介访问控制层上工作。 3 第一章绪论 我们将防火墙的处理模式与o s i 参考模型相对应如下图，可以看到在o s i 模型中，每个处理模式的防火墙都在不同的层次检查数据。 o s ! 模型 应用网关 电路网关 包过滤 m a c 层防火 1 2 5 混合模式 图1 2 防火墙类型和o s i 参考模型 混合型防火墙组合了其他类型的防火墙的元素，即包过滤和代理服务的元素， 或组合了包过滤和电路网关的元素。另外，混合型防火墙系统还可以包含两个防 火墙设备，每个设备都是一个独立的防火墙系统，但它们是连接起来的，以便串 联工作。 1 3 防火墙的两个主要研究领域 防火墙作为保护企业内部网络安全的一道工具，发挥着重要的作用，每个外 部网络的数据包要想访问内部网络都必须先通过防火墙的验证才能访问内部网 络，未通过验证的数据包则会被过滤掉，从而实现了对内部网络的保护。这个身 份验证就需要根据管理员所配置的规则表来实现，规则表应该能够正确地按照管 理员的预期去过滤数据包，而不应该出现错误而违背管理员的意愿，比如本应该 接受的数据包被过滤掉，这是防火墙的冲突检测问题。 然而，这种身份验证并没有阻止数据包对防火墙的访问，因此验证机制的好 坏，效率的高低直接影响着防火墙的性能。例如当攻击者在单位时间内发送大量 的数据包，或者网络异常繁忙时，如果防火墙过滤速度较慢，在防火墙处就可能 出现网络拥塞，从而容易遭受拒绝服务攻击( d o s ) ，这时防火墙就会成为网络 的一个瓶颈。因此，在正确配置的前提下如何优化防火墙，为防火墙提供一个快 速过滤的机制就显得十分重要，这就需要我们对防火墙进行优化配置，即防火墙 4 第一章绪论 的优化问题。 所以关于防火墙的研究，目前主要集中在这两个方面： 1 作为系统管理员如何正确地配置防火墙，使防火墙规则之间不存在冲突， 即防火墙冲突检测问题。 2 对于已经正确配置的防火墙规则，如何设计过滤算法以提高防火墙过滤 的性能，即防火墙的优化问题。 国内外的许多学者已经就这两方面问题进行过大量的研究，接下来的部分我 们将对目前的主要算法进行综合的介绍。 5 第二章防火墙的冲突检测 第二章防火墙的冲突检测 2 1 防火墙规则简介 规则是防火墙配置文件的重要组成部分，它是防火墙过滤数据包的依据。防 火墙的配置文件包含大量的规则，数据包进入防火墙时，防火墙根据配置文件寻 找与该数据包包头信息相匹配的规则，根据相匹配的规则去处理数据包。每一条 规则可以表示成如下的形式： ( f 1 s 0 八八( r d es d ) - ( a c t i o n ) 可见，规则由三部分组成，其中的o r d e r 为规则号，表示规则在规则表中的 位置。( f i s 1 ) 八( f d s d ) 部分称为过滤域，f i 表示规则过滤域的第i 个字段 ( f i e l d ) ，与数据包的包头部分相对应，s i 代表字段f i 所属的一个非空的区间范围， 如 o ，2 强】，如果数据包包头的f i 字段对应的值在s i 的范围内，就表示字段f i 匹配 规则相应的字段。当且仅当数据包d 包头部分的所有字段f i 都和规则r i 相应的 字段匹配时，称数据包d 匹配这条规则r i 。( a c t i o n ) 称为行动域，它指明了防火 墙对于匹配这条规则的数据包所要执行的动作，一般分为接受( a c c e p t ) 和拒绝 ( d e n y ) 通过两种。这样，规则号，过滤域和行动域就构成了一条规则的主要部分。 大量的规则构成了一个规则表，防火墙配置文件( 或称为防火墙策略) 实际 上就是一个规则表。典型的防火墙规则的过滤域包括五个字段：源地址、目的地 址、源端口、目标端口、服务( 协议) 类型，这些信息包含在了数据包首部的相 应部分。下面是一个典型的规则表实例： 表2 1 一个典型的防火墙规则表实例 o r d e r s - i ps _ p o r td - i pd _ p o r t p r o t o c o la c t i o n 11 9 2 1 6 8 0 18 0 a n y a n yu d pa c c e p t 2 a n ya n y 1 9 2 1 6 8 o 木 a n yi m t pd e n y 3 1 9 2 1 6 8 o 木8 01 9 2 1 6 8 o 1 a n y a n ya c c e p t 4 a n ya n ya n ya n ya n yd e n y 这个规则表有四条规则。其中第一条规则表示允许所有源i p 地址为 1 9 2 1 6 8 0 1 ，源端口号为8 0 且协议类型为u d p 的数据包通过，第2 ，3 ，4 条规 则与此类似。第四条规则是一条默认规则，在这个实例中，它拒绝所有的数据包 通过。 当一个数据包到达时，防火墙从第一条规则开始，逐条比较数据包包头信息 与规则的过滤域，当找到第一条匹配的规则，就不再进行匹配，并执行这条规则 6 第二章防火墙的冲突检测 相应的行动。例如，数据包d ( 奉，+ ，1 9 2 1 6 8 o 枣，木，i m t p ) 至l j 达时，防火墙首先比较d 和规则r l ，发现d 不匹配数据包r i ；于是再比较d 与r 2 ，发现d 匹配规则r 2 ， 于是便执行相应的动作：抛弃该数据包，并且不再比较d 和后面的规则r 3 和。 系统管理员可以根据企业的具体需求，配置规则表，以达到保护企业网络的 目的。 2 2 防火墙规则间的冲突 并不是所有规则表都是正确配置的。如果没有正确配置，防火墙规则之间就 可能会存在冲突，这些冲突轻则增加规则的数目，严重的将会违背管理员过滤包 的意图。我们看下面的一个规则表： 表2 2 有冲突的规则表 规则号 源i p 源端口 目标i p 目标端口协议类型行动 r i 1 9 2 1 6 8 o 18 01 9 2 1 6 8 奎木 a n yt c p a r 2 1 9 2 1 6 8 0 1 a n y 1 9 2 16 8 o 宰1 0 u d p d r 3 a n ya n y 1 9 2 1 6 8 1 1 a n ya n y d r 4 1 9 2 1 6 8 o 18 01 9 2 1 6 8 o 宰l o t e p u d p a r 5 a n y 8 01 9 2 1 6 8 o 宰8 0 a n y d 这是一个没有正确配置的规则表，因为它存在着以下异常： 情况1 。上面的规则r l 和规则r 3 发生冲突，因为对数据包d ( 1 9 2 1 6 8 0 1 ， 8 0 ，1 9 2 1 6 8 1 1 ，a n y ，t c p ) 既匹配r i ，又同时匹配r 3 ，根据第一条规则，防火 墙会允许数据包d 通过；而根据规则r 3 则会阻止该数据包通过，因此如果互换 规则r l 和r 3 ，防火墙将对数据包d 采取完全相反的处理动作。 情况2 。观察上面的规则表，我们可以看出对于数据包d ( 1 9 2 1 6 8 1 1 2 3 ， 8 0 ，1 9 2 1 6 8 0 1 ，1 0 ，t o p ) ，规则表中的五条规则中没有一条与之匹配，防火墙 将不知道对该数据包如何操作。 情况3 。考虑对于数据包d 1 ( 1 9 2 1 6 8 0 1 ，8 0 ，1 9 2 1 6 8 0 木，1 0 ，t o p ) ，它 将匹配第一条规则，对于数据包d 2 ( 1 9 2 1 6 8 0 1 ，8 0 ，1 9 2 1 6 8 0 幸，1 0 ，u d p ) ， 它将匹配第二条规则，而数据包d 1 和数据包d 2 的并集又构成了规则的过滤 域所对应的集合，因此对于规则，这条规则永远都不会被匹配，它在防火墙 中发挥不出任何作用。 上面给出了三种典型的异常，一个好的防火墙配置是不应该存在这种异常的。 除了上面几种异常之外，防火墙规则还存在其他的异常情况，为了给规则异 常一个明确的定义，我们首先考虑一下两条规则( 过滤域) 之间可能存在的关系。 7 第二章防火墙的冲突检测 我们知道过滤域与集合相对应，因此各条规则之间的关系也与集合相类似。 我们可以把两条规则的关系用图形表示如下图： o oo 1 包含 2 相等3 相交4 独立 图2 1 两条规则之间的关系 可见两条规则间存在这下面几种可能的关系： 1 包含( 覆盖) 。如果规则r 和s 满足至少有一个字段f i ，满足s f i 是r f i 的 子集，而对于其他的字段f i ，要么s f j 是r f j 的子集，要么二者相等，这时称规 则r 包含规则s 。我们记作sc r 。 2 完全相等( 精确匹配) 。如果两条规则的任意一个字段都完全相等，那么就 说这两条规则精确匹配。即对于任意的f i ，都有r f 尸s f i 成立。我们记为r = s 。 3 相互独立。如果两条规则r 和s ，至少存在一个字段具有完全不同( 独立) 的取值范围，那么就说这两条规则相互独立。即存在f i 满足r f ins f i = o 。我们 记作r 上s 。 4 相交。当两条不等的规则之间既不独立，又不存在包含关系时，就称这两 条规则是相交的。我们记作r os 。 下面我们给出防火墙规则间所有可能存在的异常以及针对异常应该进行的 处理：。 1 屏蔽异常。当规则r 出现在规则s 的前面，而且r 包含s 时，因为规则r 匹配所有规则s 所匹配的数据包，所以规则s 将永远不会被匹配，这种异常称为 屏蔽异常。屏蔽异常有种扩展情况：如果r 表示规则s 前面的所有规则的并集， 那么当r 包含s 时，也说存在着屏蔽异常，规则s 被屏蔽。前面的情况3 就属于 这种异常。 一 一 屏蔽是一种严重的错误，因为被屏蔽规则从来不起作用。所以发现屏蔽并通 知管理员重新排序或者删除被屏蔽规则来纠正错误非常重要。 2 相关性异常。这种异常出现在两条规则集相交或者相等，而这两条规则的 行动域又不同的情况，这时对于这两条规则的交集部分所包含的数据包，就会出 现相关性异常。如果改变两条规则的相对顺序，对这部分数据包的处理就会产生 与原来不一致。前面的情况1 就属于这种异常。 8 第二章防火墙的冲突检测 处理：通常将这种异常作为一个警告，告诉管理员交换两条规则将会改变防 火墙原来的意图。 3 包含异常。如果规则r 包含s ，规则r 排在规则s 的后面，且r a c t i o n l = s a c t i o n 。 这时r 匹配所有s 所匹配的数据包。这种异常称为包含异常。 处理：包含异常仅仅认为是一个异常警告，所以只需提示管理员即可。但要 注意，如果交换了r 和s 的顺序，将会引入屏蔽异常。 4 冗余异常。如果规则r 包含规则s ，并且r a c t i o n = s a c t i o n ，那么不论r 和s 的顺序如何，规则s 都是冗余的，这种异常称为冗余异常。与屏蔽异常类似，冗 余异常也有扩展情况：如果存在规则r 1 a c t i o n = r 2 a c t i o n = a c t i o n = s a c t i o n ，r = ur i ，并且r 包含s ，那么规则s 也是冗余的。 冗余被认为是一种错误，一个冗余规则对过滤不起作用，但是它增加了过滤 规则表的长度，并且会增加规则查找时间和空间，所以必须及时发现冗余并通知 管理员修改规则或者删除冗余规则。 5 完备性异常。如果存在数据包d ，在规则集中找不到任何规则与d 匹配， 这时防火墙无法根据规则表对数据包d 执行任何操作，这种情况称为完备性异 常。如前面的情况2 。 完备性异常是规则配置的一个严重错误，但处理起来也比较容易。如果发现 存在完备性异常，通常管理员可以通过在规则表的末尾加入一条默认规则r ( a n y ， a n y ，a n y ，a n y ，a n y ) 一 ( d e f a u l ta c t i o n ) 来解决，这条默认规则匹配数据包的 全集，默认行动根据具体要求来设置。 防火墙规则表包含着大量的规则，有时达几百，几千条，正确地配置这些规 则，消除规则间的冲突( 异常) ，可以有效地保护企业网络，相反，如果不能正 确地配置这些规则，将有可能会带来意想不到的后果。另一方面，合理地配置防 火墙，删除冗余的规则可以减少防火墙规则的数目，因此也能提高防火墙过滤的 性能。 防火墙规则数目是庞大的，如果不注意，将很容易在配置规则表时就出现上 述异常，使防火墙不能很好地工作。对此，一些学者提出了相关的防火墙冲突检 测算法，下面我们介绍一种检测规则间冲突的结构f d t 。 2 3 规则的树状表示f d t l i u ( 2 0 0 4 ) 设计了一种表示规则的数据结构_ f d t 。这是一种树型结构，使 用f d t ，可以检测并排除规则表中存在的冲突。该算法将防火墙规则集对应到 一种称为防火墙决策树( f d t ) 的结构，构造f d t 的过程就是消除异常的过程， 9 第二章防火墙的冲突检测 f d t 的递归定义为( 我们用d ( f i ) 表示字段f i 的定义域，即f i 所有可能的取值) ： 1 有唯一的一个没有输入边的节点，称为根节点。其他节点都至少有一条输 入边。有一个或一个以上没有输出边的节点，称为终端节点，终端节点用来表示 行动域。 2 每个节点都有一个标记，记作f ( v ) ，满足 f c v ， 耋二j f d 如果v 不是终端节点 如果v 是终端节点 a 表示允许通过( a c c e p t ) ，d 表示拒绝通过( d e n y ) 3 每条边也有一个标记，记作i ( e ) ，如果e 是节点v 的一个输出边，那么i ( e ) 满足： i ( e ) 冬d ( f ( v ) ) 4 从根到终端节点的一个有向路径称为决策路径。并且同一个决策路径之中 的任意两个节点具有不同的标记。决策路径可以表示成： ( ( f l i ( e 0 ) n ( f 2 i ( e 2 ) ) ，( f d i ( e d ) ) n ( a d ) ) 每个决策路径定义了一条规则和与之匹配的数据包集合，即决策路径，规则 和数据包集合是对应的。 5 在防火墙f 中任意一个节点v 的输出边所构成的集合，记作e ( v ) ，e ( v ) 满足下面两个条件： 1 排他性：i ( e ) ni ( e ) = e 和e 是e ( v ) 中任意两条不同的边 2 完全性。u 。e e ( v ) i ( e ) = d ( f ( v ) ) 同时满足上面5 个性质的树形结构就是f d t 。因为f d t 的每一个决策路径 都对应着一条规则，f d t 也就对应着一个规则集。对于给定的一个规则集c 可 以使用f d t 的构造算法构造出等价的f d t ，根据性质5 的排他性，我们可以知 道f d t 下的规则之间是相互独立的，从而实现了规则表的重构，这一点我们在 后面第三部分仍会提到。 关于f d t 的构造算法，l i u ( 2 0 0 4 ) 等人给出了构造空树，添加分支的算法。 通过将规则逐条插入到准f d t 中得到一个完整的f d t ，具体算法可以参见后面 相应的参考文献。 2 4 其他一些冲突检测算法 关于防火墙冲突检测，m u h a m m a da b e d i n ( 2 0 0 6 ) 也给出了另一种检测算法， 他利用集合分析的方法定义了防火墙规则之间的冲突，然后提出了他的冲突检测 l o 第二章防火墙的冲突检测 算法。在他的算法中，他把规则冲突分成覆盖异常，相关异常，冗余异常几类， 与f d t 不同，他的冲突检测算法首先生成1 1 条相互独立的规则，然后又将具有 相同域的规则合并，因此合并后的规则之间可能存在包含关系。 大多数防火墙配置的规则之间是存在包含关系的，采用这种配置策略的好处 是规则编写起来简单易懂，并且规则数目达到了尽可能的少，而其缺点则是有些 规则不相互独立，不能随意交换规则的顺序，如果管理员没有注意到这一点，就 有个能引致配置错误。 此外，还有学者如d m i f l yr o v n i a g i ( 2 0 0 4 ) 等提出把规则表示成多维空间的一 个超矩形的概念，维数就是过滤域字段的数量，当然，这种结构的过滤算法也就 与多维空间点的处理类似，而与一般的防火墙规则的顺序匹配有所不同。 在本文剩下的部分我们做以下约定：规则用r 表示，数据包用d 表示，。概 率用p 表示，元组用t 表示，字段用f 表示。如无特殊说明，后面的部分都使 用这种表示方法。 第三章防火墙规则匹配的一些优化算法 第三章防火墙规则匹配的一些优化算法 前面我们对防火墙规则，以及如何正确地检测规则之间的冲突做了简单介绍， 下面我们将研究防火墙的另一大问题：防火墙规则表的优化问题，即优化规则表， 以使防火墙快速地找到匹配的数据包。 3 1 优化的目的 防火墙规则表中含有大量的规则，每当来到一个数据包时，防火墙要按照一 定的算法搜索匹配的规则，当防火墙要处理大量的数据包时，算法的好坏将极大 地影响到防火墙的过滤性能。例如对于顺序搜索，规则的先后顺序会很大程度上 影响到搜索的快慢。如果把要匹配的规则放在规则表的第一位，那么防火墙查找 时只需要比较这1 条规则；如果把要匹配的规则放在规则表的最后位置，那么查 找这条匹配规则就需要比较全部的1 1 条规则，这两种排序需要比较次数的差距是 巨大的! 实际的防火墙匹配算法并非如此简单，因为规则之间存在着交叉，重叠部分， 这使得问题变得极为复杂，并且f u l p ( 2 0 0 4 ) 已经证明，多维防火墙的优化是一个 n p - h a r d 问题。也因此有许多学者进行了专门的研究，下面我们对主要的几种规 则匹配算法做下介绍。 3 2 利用空间几何的点定位算法( g e m ) 解决规则匹配问题 这种算法的主要思想是把规则看成是d ( 对应防火墙过滤域字段的数目) 维 空间中的一个超矩形，把规则匹配问题看成是空间几何的点定位问题来解决，而 点定位问题是在计算几何中的一个经典问题，已经有了很多比较成熟的研究。 具体而言，它把防火墙规则的每个字段看成多维空间中的一个维度，在每一 个维度有一个相应的匹配范围。d 个字段的一个组合对应着一条防火墙规则的过 滤域，因此一条规则也就对应着多维空间中的一个方体( 超矩形) ，方体的各条 边与字段的范围相对应。每一个指定的数据包就相当于d 维空间中的一个点，因 此规则匹配的任务就是定位出空间中的任何一点属于哪个方体。 3 2 1 规则与多维空间超矩形的对应关系 在防火墙包匹配问题中，对于给定的数据包，要求找到第一个与其包头部分 1 2 第三章防火墙规则匹配的一些优化算法 匹配的规则。每条规则由像 1 j ，r i 】这样的d 个区间段的组合构成，由于包匹配只关 注过滤域是否与包头信息匹配，因此我们下面对匹配算法的研究中将主要考虑过 滤域，忽略行动域。 下面我们给出这个问题的一个正式定义。我们把每一条规则看作d 维空间的 一个超矩形域，规则的每个字段定义了多维空间的维度，这样每条规则就是一个 d 维超矩形。假设规则集包括n 条规则，我们将得到n 个超矩形，注意这些超矩 形是可以有重叠部分的( 因为规则存在交叉部分) 。 这些超矩形实际上定义了对d 维空间的一个划分，在最坏的情况下，这种划 分将会消耗o ( i l d ) 的空间。点定位问题的超矩形是不存在重叠部分的，为了与点 定位问题对应，进而使用计算几何中的算法，我们可以将这些超矩形重构，重构 后的结构我们称为简单超矩形集，简单超矩形是没有互相重叠的部分的，这样的 超矩形集合称为简单超矩形集。每个简单超矩形对应唯一的一条规则：这条规则 能够匹配超矩形内所有的点，并且是第一条满足此条件的规则。于是，超矩形与 规则一一对应，点与数据包对应，防火墙规则匹配问题就转换成了计算几何学中 的点定位问题。点的坐标由数据包的包头各个字段的值确定，一旦我们知道了某 一点位于哪个超矩形内，那么我们就找到了这个点对应的数据包所匹配的规则， 进一步就能根据这条规则的行动域决定对数据包的处理( 允许通过或丢弃) 。 3 2 2 几何搜索算法( g e m ) 多维空间中的点定位问题的解决算法，其效率取决于所使用的数据结构。 r o v n i a g i n ( 2 0 0 4 ) 使用了下面的数据结构： 首先让每个字段对应一个层级，每一层级内按照字段的匹配区间排成序列。 该算法的数据结构由两部分组成：一部分是一个指针数组，数组元素的内容 由一个头部信息加上一个指针构成，指针用来指向下一字段层次的头部信息。该 头部包含了有关数据的层级对应的字段，匹配的区间，该区间在层级中的顺序号 以及指向第一个层级的指针信息。 第二部分存储了数据所属的层级信息，为搜索结构信息，每一层级都是一些 节点的集合，而每一个节点又是一个数组。数组的每个元素声明了一个简单区间， 并包含了指向下一层级节点的指针。在最后一个层级，以匹配的规则号的信息取 代了指向下一层级节点的指针信息，从而指定了匹配的规则。 按照以上两点，规则的结构如下： ( 第一字段范围 第二字段范围 第d 个字段范围- 规则序号。) 搜索算法：基于上面的数据结构，可以使用这样的搜索算法：我们假设各个 字段按照如下的层级顺序排列：协议类型，源地址，目标地址，源端口，目标端 1 3 第三章防火墙规则匹配的一些优化算法 口。搜索将首先从第一层级开始，这里第一层级的字段就是协议类型。因为每一 区间都已经按照层级内的次序排列，我们可以使用二分搜索算法，在协议类型数 组里，首先寻找到在字段“协议类型”匹配该数据包的那些数据元。接着，对于 第一次搜索到的数据，根据其指针所指的层次，搜索第二层级源地址，同样 使用二分搜索算法找到在“源地址”匹配该数据包的那些单元格，这样二者的组 合就既匹配该数据包的协议类型，又匹配该数据包的源地址。这样的搜索继续应 用到第三层级，第四层级，最终，到第五层级时，后面已经没有下一个层级，此 时指针部分所指的规则号就是匹配该数据包的规则。 这里我们需要提出说明的是，上面使用的搜索算法，只是计算几何中的一种 比较直观易懂的搜索算法，它的空间消耗还是比较大的，计算几何中还有几种其 它具有更好性能的点定位算法，因为这里我们主要是给出一个规则匹配的原理， 因此就不再继续讨论这些算法了。 g e m 算法的主要思想是：对每一个字段，根据规则表取所有可能匹配的区 间，然后将这些区间做笛卡尔积构造出超矩形，这样构造的超矩形覆盖了整个多 维空间。由于规则集的完备性，每个超矩形都能对应上一条规则。它利用了额外 的存储空间存储了规则的信息，从而提高在搜索时间上的效率，但由于做笛卡尔 积运算会占用很多额外的存储空间，当规则数很多时这种算法的空间需求也会很 大的。 3 3t r i e 树搜索算法 上面的g e m 算法实际上使用了大量的存储空间来存储节点信息，t r i e 树搜 索也使用了额外的空间来保存节点信息，但它可以比g e m 搜索节省一定的空间， 因为它消除了冗余的存储空间占用情况。 3 3 1t r i e 树的构建 t i l e 树被广泛应用于字典查找匹配字符串问题中，而如果将字符串的每个字 符看做规则的一个字段，二者的搜索原理就是相近的。t r i e 树的结构与l i u 提出 的f d t 结构有些相似，即树的节点与规则字段对应，字段的匹配范围与边对应。 不同的是，t r i e 树对边进行了排序以便进行搜索，而f d t 则没有对边排序。t i l e 树的建立过程如下。 首先建立一个空树 从第一条规则开始，向树中按照下面的添加算法逐条插入规则，直到规则集 的最后一条规则已插入到树中，t i l e 树构建结束。 1 4 第三章防火墙规则匹配的一些优化算法 为表述清楚，我们先做如下说明。以f i 来表示字段及与其对应的节点，e i 来表示边，i i ( c 3 ) 表示从字段f i 出发的第j 条边e i 所对应的区间，规则r 的字段f i 所对应的区间表示为s i ，添加算法为： 1 如果树为空，则直接将规则插入到树中，插入后树的各条边为插入规则相 应字段的区间范围，即i i ( e 1 ) = s i ，因为只有一条规则，因此这里各个字段只有一 个对应边，用e l 表示。 2 如果树非空，则从字段f l 开始，按照下面原则依次添加节点和边： 若已存在从节点f i 出发的k 条边i i ( e 1 ) ，i i ( e 2 ) i i ( e k ) ，这说明在t r i e 树中已经 存在f ie i i ( e j ) ( j 1 ，2 ，k ) ，假设要插入的规则为r ：( ( f l s 1 ) n ( f 2 s 2 ) ，( f d s d ) ) ，首先对字段f l 做集合运算s i - u k = l l l ( e k ) ，如果( s 1 u 1 扣l i l ( e k ) ) 为空， 表示要插入的规则对应边已经存在，则直接转到下一字段f 2 ；如果( s 1 u j k = 1 1 1 ( e k ) ) 不为空，则令i i ( e j + 1 ) = s i - u 1 k = - l l l ( e k ) ，插入这条边并将i i ( e 0 ，i i ( e 2 ) ，i i ( e j ) ，i i ( e j + 1 ) 按照升序顺序排序，以使插入边i i ( e i + 1 ) 后，从字段f l 出发的各条边满足 i i ( e 1 ) i i ( e 2 ) i i ( e j ) 将当前节点指向下一个节点，直到当前节点指向最后一个节点，这时， 我们便得到了从根节点当前的叶子节点的一个路径，而该路径所对应的规则r 便是匹配数据包d 的规则，搜素过程结束。 这种搜索算法使用了数据挖掘中的分类技术的思想，而搜索算法的效率与字 第三章防火墙规则匹配的一些优化算法 段的排列顺序也是有关的，对于如何排列字段进行优化，可以使用数据挖掘分类 的一些技术，这里我们便不再详细介绍了，因为本文中我们主要考虑过滤算法以 及对规则表的行即规则顺序的优化问题。 相比于g e m 算法存储多维空