（计算机系统结构专业论文）防火墙规则集关键技术研究.pdf

摘要 摘要 随着互联网的迅速发展，防火墙包含的规则数目变得越来越多。这种情况， 通常会带来两方面的问题。第一，规则数目的增多，对规则匹配的效率提出了挑 战，规则匹配已经成为防火墙的一个性能瓶颈点。第二，由于规则集中冲突规则 的存在，规则数目的增多，使得有效管理防火墙规则集变得越来越困难。要解决 这两方面的问题，通常需使用以下几项关键技术：规则匹配技术、规则冲突检测 技术、规则冲突消除技术、规则正确性配置技术。研究人员针对以上技术，提出 了相应的算法。这些算法在提高防火墙吞吐率、降低规则集管理难度等方面，取 得了一定效果，但仍然存在不少缺陷，有待于进一步改进和完善。因此，目前仍 有必要对防火墙规则集关键技术进行研究。 本文深入细致地研究了规则数目增多所带来的问题，全面地分析和总结了防 火墙规则集关键技术的研究现状，以及未来的发展趋势，取得了若干创新和成果。 本文的主要创新点如下： 第一，提出了一种快速的高维报文分类算法。 在规则匹配技术，即报文分类技术方面，在b s o l ( b i n a r ys e a r c ho nl e a v e s ) 算法基础之上，本文提出了一种快速的高维报文分类算法m c b f ( m u l t ic u t t i n g s a n db l o o mf i l t e r s ) 。与b s o l 算法不同，m c b f 算法在对规则空间进行分解时，同 时切割所有维，并将叶子规则空间存储在相关的哈希表中；m c b f 算法为每个哈 希表构建一个b l o o mf i l t e r ，而这些b l o o mf i l t e r 被存储在片内s r a m 中。当分类 数据包时，m c b f 算法并行地访问b l o o mf i l t e r ，并根据其结果决定如何访问哈希 表。理论分析和仿真实验表明：m c b f 算法能正确地分类数据包；当分类一个数 据包时，m c b f 算法的哈希表平均查询次数为l ，远小于b s o l 算法：最坏情况下， m c b f 算法的哈希表查询次数为d ( 1 0 9 ( 。) + 1 ) ，其中。是最长维的域长。对于 常见的规则集类型和高维环境而言，该值通常小于等于b s o l 算法在最坏情况下 的哈希表查询次数。 第二，提出了一种基于位向量交集运算的规则冲突检测算法。 在规则冲突检测技术方面，针对现有冲突检测算法效率不高这一情况，本文 a s b v ( a g g r e g a t e dsb i tv e c t o r s ) 算法基础之上，提出了一种基于位向量交集 雉的规则冲突检测算法d b b v ( d o u b l eb i n a r yb i tv e c t o r s ) 。同a s b v 算法类似， 摘要 d b b v 算法也采用了分治思想和位向量技术。但与a s b v 算法不同，在每一维规 则分量的处理过程中，d b b v 算法只需要进行一次位向量交集运算，而a s b v 算 法需要进行多次位向量并集运算；d b b v 算法支持以范围形式表示的规则集，而 a s b v 算法只支持以前缀形式表示的规则集。理论分析和仿真实验表明：d b b v 算法的冲突检测性能优于a s b v 算法。 第三，提出了一种基于切割映射的冲突消除算法。 在规则冲突消除技术方面，针对现有规则冲突消除算法不能彻底消除冲突这 一问题，本文提出了一种基于切割映射的冲突消除算法r c b c m ( r e s o l v i n g c o n f l i c t sb a s e do nc u t t i n gm a p p i n g ) 。r c b c m 算法对不同的冲突类型，采取不同 的处理方法；并以两条冲突规则为基本处理对象，在其冲突消除过程中，顺序切 割优先级较低的规则的每一维分量。理论分析和仿真实验表明：在缝垄8 尘量塑型 ，堕丛尬二f ，堡竺呈! 坚竺鲨堂塑盟堂险、仲窭。 第四，提出了一种基于规则交集运算的规则集比较算法。 在规则正确性配置技术方面，针对应用于d i v e r s ef i r e w a l ld e s i g n 环境的现有 规则集比较算法，效率不高这一情况，本文提出了一种基于规则交集运算的规则 集比较算法r s c b r i ( r u l es e t sc o m p a r i n gb a s e do nr u l e si n t e r s e c t i o n ) 。r s c b r i 算法首先使用r c b c m 算法对规则集进行预处理，将规则集比较问题，转换成多 维空间中的图形比较问题；然后利用规则交集运算，判断图形所占区域和颜色是 否一致，进而确定规则集是否等价。理论分析和仿真实验表明：r s c b r i 算法能检 测出规则集之间的不同点，且时空效率优于现有算法。 关键词：防火墙规则集，规则匹配，规则冲突检测，规则冲突消除，规则正确性 配置 a b s t r a c t 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 ft h ei n t e m e t ，t h en u m b e ro ff i r e w a l lr u l e si s i n c r e a s i n g 。t h i su s u a l l yl e a d st w op r o b l e m s f i r s t ，t h ei n c r e a s i n go ft h en u m b e ro fr u l e s c h a l l e n g e st h ep e r f o r m a n c eo ft h ep a c k e tc l a s s i f i c a t i o nt h a th a sa l r e a d yb e c o m ea p e r f o r m a n c eb o t t l e n e c ki nf i r e w a u s s e c o n d ，w i t ht h ei n c r e a s i n go ft h en u m b e ro fr u l e s ， i ti sm o r ea n dm o r ed i f f i c u l tt oe f f i c i e n t l ym a n a g ef i r e w a l lr u l e s t h e s et w op r o b l e m s c a nb ea d d r e s s e db yf o u rk e yt e c h n i q u e s ：p a c k e tc l a s s i f i c a t i o n ，r u l ec o n f l i c td e t e c t i o n ， r u l ec o n f l i c tr e s o l v i n ga n dr u l ed e p l o y m e n t t os o l v et h ep r o b l e m s ，r e s e a r c h e r sr e c e n t l y p r o p o s e dm a n ya l g o r i t h m s ，b u tm o s to ft h e ms t i l lh a v eaf e wd r a w b a c k sa n dn e e dt ob e i m p r o v e d t h e r e f o r e ，i ti s s t i l ln e c e s s a r yt od of u r t h e rr e s e a r c ho nt h e s ek e yt e c h n i q u e s o ff i r e w a l lr u l es e t t h i sd i s s e r t a t i o ns t u d i e st h ep r o b l e m sc o m i n gf r o mt h ei n c r e a s i n go ft h en u m b e ro f f i r e w a l lr u l e s ，t h o r o u g h l ya n a l y z e sa n ds u m m a r i z e sr e l a t e dw o r k so nf i r e w a l lr u l es e t ， a n dp r o p o s e sn e wa l g o r i t h m st oi m p r o v et h ep e r f o r m a n c ei ns o m es u b - t o p i c s t h e m a j o rc o n t r i b u t i o n so ft h i sd i s s e r t a t i o na r ea sf o l l o w s f i r s t ，t h i sd i s s e r t a t i o np r o p o s e sar a p i da n dm u l t i d i m e n s i o n a la l g o r i t h mf o rp a c k e t c l a s s i f i c a t i o nb a s e do nb s o l ( b i n a r ys e a r c ho nl e a v e s ) ，w h i c hi sn a m e dm c b f ( m u l t ic u t t i n g sa n db l o o mf i l t e r s ) d i f f e r e n tf r o mb s o l ，m c b fc u t sa l ld i m e n s i o n sa t t h es a m et i m et od e c o m p o s er u l es p a c e sa n ds t o r e sl e a fs p a c e si n t oh a s ht a b l e s ；m c b f c o n s t r u c t sab l o o mf i l t e rf o re v e r yh a s ht a b l ea n db l o o mf i l t e r sa r es t o r e di n t o e m b e d d e ds r a m w h e nc l a s s i f y i n gap a c k e t ，m c b fp e r f o r m sp a r a l l e lq u e r i e so n b l o o mf i l t e r sa n dd e c i d e sh o wt ov i s i th a s ht a b l e sa c c o r d i n gt ot h er e s u l t s a l g o r i t h m a n a l y s i sa n dt h er e s u l t so fs i m u l a t i o n ss h o w ：w h e nc l a s s i f y i n gap a c k e t ，t h ea v e r a g e n u m b e ro fh a s h t a b l el o o k u p so fm c b fi s1 ，w h i c hi sm u c hs m a l l e rt h a nt h a to fb s o l ； a tt h ew o r s tc a s e ，t h en u m b e ro fh a s h t a b l el o o k u p so fm c b fi so ( 1 0 9 ( w , 。) + 1 ) ，w h i c h i ss m a l l e rt h a nt h a to fb s o li nm u l t i d i m e n s i o n a le n v i r o n m e n t ，w h e r e 。i st h e l e n g t h ，i nb i t s ，o ft h ed i m e n s i o nw h o s el e n g t hi st h el o n g e s t s e c o n d ，t h i sd i s s e r t a t i o np r o p o s e san e wa l g o r i t h mf o rd e t e c t i n gr u l ec o n f l i c t n a m e dd b b v ( d o u b l eb i n a r yb i tv e c t o r s ) ，w h i c hi sb a s e do na s b v ( a g g r e g a t e dsb i t i t l a b s t r a c t v e c t o r s ) s i m i l a rw i t ha s b v , d b b ve m p l o y st h ed i v i d e d - a n d - c o n q u e rm e t h o da n d b i t v e c t o r s d i f f e r e n tf r o ma s b v , d b b vo n l yn e e d st oc a l c u l a t et h ei n t e r s e c t i o no fb i t v e c t o r so n c ei nt h ec o u r s eo fe v e r yd i m e n s i o n a lp r o c e s s i n g ，w h i l ea s b vn e e d st o c o m p u t et h eu n i o no fb i tv e c t o r sm a n yt i m e s a l s o ，d b b vd o e sn o ts e ta n yr e s t r i c t i o n o nr u l e s ，w h i l ea s b vl i m i t se v e r yf i e l do fr u l e st ob eap r e f i x a l g o r i t h ma n a l y s i sa n d t h er e s u l t so fs i m u l a t i o n ss h o wt h a tt h ep e r f o r m a n c eo fd b b vi sb e a e rt h a nt h a to f a s b v t h i r d ，t h i sd i s s e r t a t i o np r o p o s e sar u l ec o n f l i c tr e s o l v i n ga l g o r i t h mn a m e d r c b c m ( r e s o l v i n gc o n f l i c t sb a s e do nc u t t i n gm a p p i n g ) t h ea l g o r i t h mr e s o l v e sr u l e c o n f l i c t sa c c o r d i n gt ot h ec l a s s i f i c a t i o no fc o n f l i c t s i tt r e a t st w or u l e sa st h eb a s i c o b j e c ta n ds e q u e n t i a l l yc u t se v e r yd i m e n s i o no ft h er u l e sw i t hl o w e rp r i o r i t y a l g o r i t h m a n a l y s i sa n dt h e r e s u l t so fs i m u l a t i o n ss h o wt h a tr c b c mc a nt h o r o u g h l yr e s o l v e c o n f l i c t sa tt h ec o s to fi n c r e a s i n gaf e wr u l e s f o u r t h ，f o rr u l ed e p l o y m e n t ，t h i sd i s s e r t a t i o np r o p o s e sar u l e s e tc o m p a r i n g a l g o r i t h mf o rd i v e r s ef i r e w a l ld e s i g nn a m e dr s c b r i ( r u l es e t sc o m p a r i n gb a s e do n r u l e si n t e r s e c t i o n ) f i r s t ，r c b c mi se m p l o y e di nt h ep r e - p r o c e s s i n gs t a g eo fr s c b r i t h e nt h ep r o b l e mo fr u l es e tc o m p a r i n gi st r a n s f o r m e di n t ot h ep r o b l e mo fg r a p h c o m p a r i n gi nm u l t i d i m e n s i o n a ls p a c e a tl a s t ，r s c b r ic o m p a r e st h e a r e a sa n dt h e c o l o ro fg r a p h st od e c i d ew h e t h e rt h er u l es e t sa r ee q u a lo rn o tb ye m p l o y i n gr u l e s i n t e r s e c t i o n a l g o r i t h ma n a l y s i sa n dt h er e s u l t so fs i m u l a t i o n sn o to n l ys h o w t h a tt h e a l g o r i t h mc a nf i n do u t a l ld i s c r e p a n c i e sa m o n gr u l es e t s ，b u ta l s ov e r i f yt h a tt h e p e r f o r m a n c eo f t h ea l g o r i t h mi sb e t t e rt h a nt h a to ft h ee x i s t i n ga l g o r i t h m k e y w o r d s ：f i r e w a l lr u l es e t ，p a c k e tc l a s s i f i c a t i o n ，r u l ec o n f l i c t sd e t e c t i o n ，r u l e c o n f l i c t sr e s o l v i n g ，r u l ed e p l o y m e n t 1 v 主要符号表 p r i ( r ，) a c t ( r ，) p n + n 丁( p ) t p k p r 。 pgr 彳( 尸) r ? 呱 m a t c h ( p ) 心细，f 瓦吒 t 啦矾j k 主要符号表 域长 规则集维数 第f 维的域长 报文分类算法顺序访问的规则个数 单条规则所占的字节数 c a c h el i n e 的字节数 规则集包含的规则个数 机器字长 规则集 规则集第i 条规则 足的第k 维分量 瓦的左端点值 r , k 的右端点值 足的优先级 冗的处理动作 数据包 正整数集 非负整数集 尸的m 维分量集合 p 的第k 维分量 p 匹配规则足 尸不匹配规则足 p 的处理动作 r ，和尺，冲突 p 的匹配集合 防火墙默认规则 瓦和l 无关 和乙交叉 v i i i 韶 切 - l 1 ， s 楚 p 叮， w 职 r c 玎一j 主要符号表 t 恤8 t i k 瓦t j , r j v r ， r ，吼r j r ，r j r ，f 2 r j 。 r s j d 陆 l e n o 磋 d 丧 p r s , p 卜r s 。 r ，r s r | 乍r s j r s d ( r s 。) 工 0 f r s r g r e 啊 r r s d ( r s 。) r j l p r e f i x ( r s f ) p r e f i x ( r s l ) a n c ( r s , ，七) l e v e l ( r s 。) 饯 鹾 瓦包含巩 毛和n 相关 r 覆盖r 。 r 遮挡r r ，被r ，冗余覆盖 足，对于月i 是多余的 最长维的长度 编号为f 的规则空间 r s 的第k 维分量 前缀包含的比特数 r s j 的第k 维分量左端点值 r s ，的第k 维分量右端点值 尸属于r s , 尸不属于月s r ，属于r s ， r ，不属于r s ， r s 的规则空间规则集合 以非负整数为端点的线段组成的集合 上的二元运算 数轴上不包含任何点的特殊线段 所有规则空间组成的集合 所有可能存在的m 维规则组成的集合 规则空间交集映射 不包含任何数据包的特殊规则 r s 的规则空间精简规则集合 规则空间分解映射 尺s j 的本层前缀 r s 的前缀 r s ，的k 层祖先规则空间 r s 所在的层 m c b f 算法建立的k 层第i 个哈希表 m c b f 算法为碰建立的b l o o mf i l t e r i x 主要符号表 t ( 尸) f 厶 k ； r a c ( r ) 么e ( r 日) f b v ( r ) f b 圪( r h ) s ( 七) e ( 尼) 尸的伪维扩展分量集合 尸的第k 维扩展分量 访问或彤时，尸的关键字 规则冲突检测中，被测规则 与r 相冲突的规则集合 在第k 维上与只h 相冲突的规则集合 a c ( r ) 对应的位向量 彳g ( r h ) 对应的位向量 第k 维分量起始地址集合 第k 维分量结束地址集合 对应的位向量 磋对应的位向量 上上的二元运算 三上的二元运算 三上的二元运算 切割映射 第k 维分量的冲突切割映射 r c b c m 算法处理后的规则个数 足的规则体积 x 似 ， o 誊；脚 1叮嗽 图表索弓 图表索引 表2 1 规则集示例 表2 2 仿真实验规则集信息表 表3 - 1 二维规则集 图3 1 规则集的二维平面表示 图3 2 规则空间分解示例 表3 2 规则空间信息表 表3 3 最坏情况下哈希表查询次数对比 表3 4 最坏情况下访存次数( 丁等于2 0 ，c 等于6 4 字节) 表3 5 最坏情况下访存次数( 7 等于2 0 ，c 等于1 2 8 字节) 表3 6 处理f w l 时的空间性能对比 表3 7 处理f w 2 时的空间性能对比 表3 8 处理f w 3 时的空间性能对比 表3 9 处理f w 4 时的空间性能对比 表3 1 0 处理f w l 时平均情况下哈希表查询次数、访存次数对比 表3 1 l 处理f w 2 时平均情况下哈希表查询次数、访存次数对比 表3 一1 2 处理f w 3 时平均情况下哈希表查询次数、访存次数对比 表3 1 3 处理f w 4 时平均情况下哈希表查询次数、访存次数对比 表4 - 1 规则集第k 维分量 图4 - 1s 俐对应的二叉树 图4 2 俐对应的二叉树 表4 2 数据结构构造时间对比 表4 3 冲突检测性能对比 表5 1r c b c m 算法冲突消除后规则个数 表5 2r c b c m 算法冲突消除时间 表6 1 空间使用量对比 表6 2 运行时间对比 x i 8 2 5 6 6 7 4 5 5 6 6 6 6 9 9 0 o 7 8 8 6 7 9 d d 1坶毖盯以的巧田的加阳丌鸺他踮盯加n 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作 及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其它人已经发表或撰写过的研究成果，也不包含为 获得电子科技大学或其它教育机构的学位或证书而使用过的材料。与 我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确地 说明并表示致谢。 签名：矽 日期：，砷年多月南日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文的 规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘， 允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文的全 部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：么垒盘叁二二导师签名： 日期：研年6 月t o 日 第一章绪论 第一章绪论 1 1 研究背景、目的和意义 随着i n t e m e t 的不断发展，人们对网络安全的要求变得越来越高。防火墙就是 在这样一个环境中应运而生的。近年来随着防火墙的不断发展，防火墙规则集包 含的规则数目，也变得越来越多。这种情况，通常会带来两方面的问题。 第一，防火墙规则数目的增多，使得规则匹配( 规则匹配即报文分类，在本 文中两者可互换使用) 的速度受到了很大的影响。 近年来随着技术的发展，链路速度变得越来越快。从文献【1 可知，1 4 的核 心路由器间的链路速度，达到了o c 7 6 8 ( 即4 0 g b p s ) ；而2 1 的边界链路速度， 则达到了o c 1 9 2 ( 即1 0 g b p s ) 。随着链路速度的提高，人们对包括防火墙在内的 许多网络设备的处理速度，提出了更高的要求。在这样的背景下，对报文分类速 度的要求也随之而增高。 当对报文进行分类时，通常都有一个显而易见的要求，即尽量不要丢包。实 际上在进行报文分类时，还隐含了一个更为重要的要求，即不能缓存包。造成这 一情况的主要原因是：需要为不同类别的网络流，提供不同的服务质量保证，即 提供区分服务。由于报文分类的任务，是确定接收到的数据包所属的网络流。因 此在报文分类完成之前，无法判断接收到的数据包属于哪个网络流。但是又需要 为不同的网络流，提供不同的服务质量保证，因此要求报文分类达到链路速度， 即进行线速处理。 随着防火墙规则数目的增多，以及规则集维数的提高，原有的报文分类算法， 远不能达到进行线速处理的要求。报文分类即规则匹配，已经成为包括防火墙、 路由器在内的许多网络设备的性能瓶颈点【2 一j 。 第二，由于规则集中冲突规则的存在，规则数目的增多，使得有效管理规则 集变得越来越困难。大型企业级防火墙，通常包含有数百条规则；而在这类规则 集中，存在不少相冲突的规则。面对这样的规则集，管理员即使只完成一些最基 本的任务，诸如弄清每条规则的含义以及规则间的关系，也不是一件轻松的事情。 因此在这种情况下，有效管理规则集是很困难的。 要解决这两方面的问题，通常需使用以下几项关键技术：规则匹配技术、规 电子科技大学博士学位论文 则冲突检测技术、规则冲突消除技术、规则正确性配置技术。规则匹配技术用于 解决第一个问题，即提高规则匹配的速度：后三项技术，主要用于解决第二个问 题，即降低规则集的管理难度；但规则冲突检测技术、规则冲突消除技术，又能 有助于提高规则匹配的效率。研究人员针对以上四项技术，提出了相应的算法。 在规则匹配技术方面，现有的规则匹配算法，即报文分类算法，还存在不少 缺陷。虽然提出了众多的报文分类算法，但还没有一种算法能同时满足低时间复 杂度、低空间复杂度、低更新复杂度、灵活的规则表达形式等等条件。 在规则冲突检测技术方面，现有的规则冲突检测算法，虽然能找出所有相冲 突的规则对，但是它们的运行效率都不高，且通常仅支持以前缀形式表示的规则。 在规则冲突消除技术方面，现有的冲突消除算法，仅针对某些特定的规则冲 突类型，不能彻底消除规则集中的所有冲突规则对。 在规则正确性配置技术方面，现有的规则集设计方法，以及测试数据包选取 算法，还不能完全杜绝因规则冲突等原因而引起的配置错误。 从上述讨论可知，虽然现有算法在提高防火墙吞吐率、降低规则集管理难度 等方面，取得了一定效果，但仍然存在不少缺陷，有待于进一步改进和完善。因 此，目前仍有必要对防火墙规则集关键技术进行研究。 1 2 防火墙规则集关键技术研究现状 本文讨论的防火墙规则集关键技术，主要包括规则匹配技术、规则冲突检测 技术、规则冲突消除技术、规则正确性配置技术。下面首先从这几项技术入手， 分析防火墙规则集关键技术的研究现状：然后在下一节讨论这几项技术之间的相 互关系。 1 2 1 报文分类技术 规则匹配技术，即报文分类技术，其基本原理是：根据预先设黄的规则集， 检查数据包的相关字段，例如协议号、源i p 地址、目的i p 地址、源端口号以及目 的端口号等信息，以判断数据包所匹配的规则；最后，按照规则所定义的动作处 理数据包。从该技术的基本原理，容易得出一种最为直观的报文分类算法，即顺 序匹配算法。该算法的基本思路是，将规则集按照优先级从高到低的顺序，组织 成线性表；接收到数据包时，顺序访问线性表中的每一条规则，直到找到匹配规 则为止【2 3 】。可见，顺序匹配算法的时间复杂度，与规则个数是线性关系。随着规 2 第一章绪论 则数目的增多，以及链路速度的提高，顺序匹配算法已经达不到线速处理的要求。 在这种情况下，研究人员提出了许多优秀的报文分类算法。下面分别从基于t c a m ( t e m a r yc o n t e n ta d d r e s s a b l em e m o r y ) 的分类算法、基于哈希表的分类算法、基 于决策树的分类算法、基于t r i e 的分类算法、基于分治思想的分类算法等方面， 分析报文分类算法的研究现状。 1 2 1 1 基于t c a m 的报文分类算法 在t c a m 中，每一个比特可以表示三种值：0 、1 或通配符。通常，每个t c a m 条目都能存放一条以前缀形式表示的规则。因为t c a m 能够并行地访问，存储在 其中的每一个条目，因此，最基本的基于t c a m 的报文分类算法的时间复杂度为 常量。虽然t c a m 的报文分类速度很快，但是由于其自身存在的诸多缺陷，限制 了它的使用范围。 t c a m 的主要缺陷包括：第一，范围扩展。一个范围表示成前缀形式，最坏 情况下会产生2 w 一2 条前缀，其中w 是该范围或前缀所在维的域长。一条聊维的 以范围形式表示的规则，转换成以前缀形式表示的规则，最坏情况下会产生 ( 2 w 一2 ) ”条规则。显然，范围扩展会造成规则数目大量增加，即t c a m 使用量剧 增。第二，能量消耗过大。根据文献 3 】可知，t c a m 每比特能量消耗，是s r a m 每比特能量消耗的1 5 0 倍。第三，t c a m 费用较高。1 m b y t e s 的t c a m ，通常需 要2 0 0 至2 5 0 美元【4 j 。 t c a m 的上述缺陷，特别是第一项缺陷，引起了研究人员的广泛关注。目前， 有关t c a m 的研究大致可以分为以下几类。第一，修改t c a m ，使其能直接支持 范围的存储，例如文献 5 】。这种方法虽然能解决范围扩展所带来的问题，但由于 其需要修改t c a m ，因此，短期内尚不太可能大范围应用。第二，对范围进行编 码，使得规则所占用的t c a m 条目减少，例如文献 6 1 1 】。这类编码方案，通常都 利用范围之间的包含层次关系，对范围进行编码。编码方案虽然可以在一定程度 上，减少t c a m 条目使用的个数，但是并不能完全避免范围扩展所带来的影响。 另外，这类编码方案都要求，在进行报文分类之前对数据包进行编码。这显然会 影响分类的效率。第三，规则集最小化，例如文献 4 ，1 2 1 4 】。规则集最小化，目 前有两个小的研究方向。一是通过减少规则的个数，来降低t c a m 的使用条目， 例如文献 1 2 ，1 3 】。二是在保持规则集语义不变的情况下，修改规则的某些分量， 以使得这些分量所转换成的前缀的个数达到最小，例如文献【4 ，1 4 】。前者对降低 t c a m 条目使用量作用有限；而后者虽然能大量降低t c a m 条目使用量，但到目 电子科技大学博士学位论文 前为止，还没有一种算法能有效地修改规则分量，以使得产生的前缀个数达到最 小。第四，利用多个t c a m ，并在t c a m 之间实现负载平衡，以提高t c a m 的报 文分类效率，例如文献 1 5 1 7 。这种在多个t c a m 中实现负载平衡的方法，依赖 于规则和网络流量的特性，且不能解决范围扩展所带来的t c a m 使用量剧增的问 题。 在上述众多的有关t c a m 的改进方法中，本文认为对范围或者规则进行编码， 以及修改规则分量，以使得t c a m 使用量达到最小，应是今后的两个重要研究方 向。 1 2 1 2 基于哈希表的报文分类算法 哈希表是查询速度很快的一种数据结构。因此，早在报文分类算法研究的初 期，研究人员就开始想方设法地利用这种数据结构，以提高报文分类的效率。由 于规则的每个分量实际上都是一条线段，因此规则分量以及规则自身是无法直接 存储在哈希表中的。 一些研究人员注意到：属于同一个连接的数据包，其报文分类结果是一样的， 且能很容易将连接的标识信息存储在哈希表中。基于这一发现，研究人员提出了 状态检测型防火墙。它的基本原理是：对于连接的第一个数据包，首先对其进行 报文分类；若该数据包被允许通过，则将该连接的标识信息( 例如数据包的五元 组：源i p 地址、目的i p 地址、源端口号、目的端口号、协议号) 加入到哈希表中； 对于连接的非第一个数据包，直接在哈希表中查询，以判断该数据包所属的连接， 是否已在哈希表内；若连接信息已存在，则放行数据包，否则丢弃数据包。很显 然，状态检测型防火墙，对连接的非第一个数据包的处理速度是很快的。但是如 何对连接的第一个数据包进行分类，状态检测型防火墙并未给出具体的说明。另 外，近年来随着p 2 p 应用的深入发展，特别是随着b t 下载、视频直播、点播的广 泛应用，状态检测型防火墙需要维护的连接数也变得越来越多。许多企业防火墙， 需要维护的连接数有时达到几十万甚至上百万。因此，在这种情况下，状态检测 型防火墙的空间使用量变得过大。 另外一些研究人员注意到：虽然规则分量和规则自身无法直接存储在哈希表 中，但是以前缀形式表示的规则分量，以其前缀为关键字，按照不同的前缀长度， 可以存储在相应的哈希表中。基于这一事实，研究人员提出了一种在当时显得与 众不同的一维报文分类算法。该算法为每个不同的前缀长度，构建个哈希表； 前缀长度相同的规则分量，被存储在同一个哈希表中；将规则分量存储在哈希表 4 第一章绪论 中时，其关键字即该规则分量的前缀。当分类数据包时，顺序地访问所有哈希表， 直到找到最长匹配前缀为止。因为最多构建w 个哈希表，因此该一维报文分类算 法的时间复杂度为o ( w ) 。 基于上述方法，文献 1 8 提出了一种多维的报文分类算法t s s ( t u p l es p a c e s e a r c h ) 。t s s 算法规定规则的每一维分量，均以前缀形式表示。t s s 算法根据所 有维不同的前缀长度组合，将规则划分到不同的元组中，并为每个元组建立一个 哈希表。当接收到数据包时，顺序地访问每个哈希表，直到找到具有最高优先级 的匹配规则。对于一维规则集而言，不同的前缀长度，最坏情况下有w 个可能性。 因此，对于聊维的规则集而言，不同的前缀长度组合，最坏情况下有w ”个可能性。 即t s s 算法最坏情况下将建立w ”个哈希表，因此其时间复杂度为o ( w ”) 。显然， t s s 算法难以提供良好的最坏情况下的性能保证。 除了t s s 算法外，文献 1 8 】还提出了一种优秀的二维报文分类算法r s ( r e c t a n g l es e a r c h ) 。r s 算法将所有的元组组织成一个矩形。每个元组向其左侧 同行的元组，存储标记。当接收到数据包时，r s 算法最先访问位于左下角的元组 所对应的哈希表。若匹配到标记，则r s 算法访问右侧同行的相邻元组所对应的哈 希表；若未发现任何匹配项，则r s 算法访问上一行同列的元组所对应的哈希表。 整个报文分类过程，在访问完右上角元组所对应的哈希表后结束。显然分类一个 数据包，r s 算法需要访问2 w 一1 个哈希表，即r s 算法的时间复杂度为o ( 2 w 一1 ) 。 这一时间复杂度，与同类型的g r i d o f - t r i e s 算法的时间复杂度相当。 文献 1 9 1 对r s 算法进行了改进，并提出了一种前缀编码方案。该方案的提出 基于以下两个事实：第一，在r s 算法中，前缀长度分布不均匀，且元组个数过多， 即构建的哈希表个数过多；第二，在实际的规则集中，一条前缀至多被数条前缀 所包含。文献 1 9 1 提出的编码方案，利用前缀之间的层次关系，对前缀进行编码。 该编码方案能够减少前缀的长度，即减少元组和哈希表的个数。注意，若使用文 献【1 9 】提出的编码方案，在接收到数据包时，必须首先对数据包进行编码。 由于需要提供服务质量保证，因此在设计报文分类算法时，研究人员通常都 很关心最坏情况下的时间复杂度。在上述这些基于哈希表的报文分类算法中，报 文分类的时间复杂度与哈希表的个数是呈线性关系的。它们的时间复杂度都相对 较高。 文献 2 0 l 提出了一种很具代表性的一维报文分类算法，以降低最坏情况下的时 间复杂度。与前面讨论的一维报文分类算法类似，文献 2 0 l 提出的报文分类算法， 为每个不同的前缀长度建立一个哈希表。所不同的是，文献 2 0 】提出的算法会在相 5 电子科技大学博士学位论文 关的哈希表中存储标记。当接收到数据包时，文献 2 0 】提出的算法对哈希表进行二 分查找。因此，该算法的时间复杂度为o ( 1 0 9 w ) 。显然文献 2 0 提出的算法，提供 了良好的最坏情况下的性能保证。文献 2 1 和文献 2 2 】提出了一种可控前缀扩展的 方法。使用该方法，能够减少建立的哈希表的个数，从而提高算法速度。 在文献 2 0 1 的基础之上，文献【2 3 】提出了一种非常优秀的基于哈希表的多维报 文分类算法b s o l ( b i n a r ys e a r c ho nl e a v e s ) 。b s o l 算法使用的哈希表，来自于 一棵表示整个空间的t r i e 。b s o l 算法为该t i l e 的每一层，建立一个哈希表；每层 的叶子节点，都被存储在相应的哈希表中；每个叶子节点，又在相关的哈希表中 存储标记。当接收到数据包时，b s o l 算法对哈希表进行二分查找。由于t r i e 的 高度最多为：，其中w 是第f 维的长度，因此在最坏的情况下，分类一个数据 包，b s o l 算法的哈希表查询次数为o ( 1 0 9 ( e 竺。w j ) ) 。当查询完哈希表后，b s o l 算 法通常会顺序访问至多丁条规则。因此，b s o l 算法的时间复杂度为 o ( 1 0 9 ( y , ：l ) + t r u l e s i z e c ) ，其中r u l e s i z e 是单条规则所占的字节数，c 是 c a c h el i n e 的字节数。 虽然以b s o l 算法为代表的基于哈希表的报文分类算法，提供了良好的最坏 情况下性能保证，但是它们的平均性能还有待提高。报文分类时，如何减少哈希 表的访问次数，应是今后有关该类算法的一个重要研究方向。 1 2 1 3 基于决策树的报文分类算法 常见的基于决策树的报文分类算法有：文献 2 4 】提出的a q t ( a r e a b a s e d q u a d t r e e ) 算法、文献 2 5 1 提出的h i c u t s ( h i e r a r c h i c a li n t e l l i g e n tc u t t i n g s ) 算法、 文献【2 6 】提出的h y p e r c u t s ( h y p e rc u t t i n g s ) 算法等等。这种类型的报文分类算法 的基本思想是：按照一定方式，对规则所在的多维空间进行递归分解，并建立一 颗决策树；决策树的根节点，代表整个多维空间，而非根节点代表子空间；递归 分解的结束条件通常是：节点关联的规则个数小于等于预设的阀值r 。当接收到数 据包时，首先访问决策树的根节点；然后根据空间的划分方式，再决定如何访问 下一个节点。通常基于决策树的报文分类算法，会最终访问叶子节点。当访问叶 子节点时，算法应顺序访问该节点所关联的至多r 条规则，以确定数据包所能匹配 的规则。 a q t 算法是一个二维报文分类算法。在对二维空间即平面，进行分解时，a q t 算法递归地将平面分解成四个象限，并计算每个象限关联的规则集合。在计算象 限关联的规则集合时，若一条规则属于多个象限，a q t 算法可以将其单独放在一 6 第一章绪论 处，以避免规则被复制多次。但这种做法，会降低a q t 算法报文分类的速度。因 此，a q t 算法提供了一个调节参数口，以期在报文分类速度、空间使用量和更新 操作复杂度之间达到一种平衡。对平面进行递归分解的结束条件是，象限关联的 规则个