维普资讯 http://www.cqvip.com 第３３卷 第１１期 Ｖｏ１．３３ ・计算机工程 ２００７年６月 Ｊｕｎｅ ２００７ Ｎｏ．１１ Ｃｏｍｐｕｔｅｒ Ｅｎｇｉｎｅｅｒｉｎｇ 安全技术・ 文章编号：１００ｏ＿－３４２８（２００７）１１—ｌｌ１３２—ｌｌ３ 文献标识码：Ａ 中图分类号：ＴＮ９１５．０４ 防火墙规则配置错误快速检测算法 王卫平，陈文惠，朱卫未，陈华平 （中国科学技术大学信息管理与决策科学系，合肥２３００２６） 摘要：在防火墙的规则配置中潜伏着一些问题：安全管理员可能在最初配置规则表的时候，出现一些错误；随着规则表中规则数目的增 长，不忙ｄ的规则之间发生冲突的可能性也相应增加。该文对防火墙规则配置过程中可能出现的错误进行了分析，介绍了防火墙规则配置错 误的几种常见类型，给出了发现错误的算法，并根据防火墙规则表的特点对算法进行了改进，提高了规则配置错误的检测效率。 关健诃：防火墙；包过滤；规则冲突 Ａｌｇｏｒｉｔｈｍ ｆｏｒ Ｆａｓｔ Ｄｅｔｅｃｔｉｎｇ Ｆｉｒｅｗａｌｌ Ｒｕｌｅ Ｃ０ｎｆｉｇｕｒａｔｉ０ｎ Ｍｉｓｔａｋｅｓ ＷＡＮＧ Ｗｅｉｐｉｎｇ，ＣＨＥＮ Ｗｅｎｈｕｉ，ＺＨＵ Ｗｅｉｗｅｉ，ＣＨＥＮ Ｈｕａｐｉｎｇ （Ｄｅｐｔ．ｏｆ Ｉｎｆｏｒｍａｔｉｏｎ Ｍａｎａｇｅｍｅｎｔ＆Ｄｅｃｉｓｉｏｎ Ｓｃｉｅｎｃｅ，Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｓｃｉｅｎｃｅ＆Ｔｅｃｈｎｏｌｏｇｙ ｏｆ Ｃｈｉｎａ，Ｈｅｆｅｉ ２３００２６） ［Ａｂｓｔｒａｃｔ］Ａｓ ｅｎｔｅｒｐｒｉｓｅｓ’ｎｅｔｗｏｒｋ ｓｅｃｕｒｉｔｙ ｂａｒｒｉｅｒ，ｆｉｒｅｗ＇，ｄｌｓ ｐｌａｙ ａ ｖｅｒｙ ｉｍｐｏｒｔａｎｔ ｒｏｌｅ Ｓｉｎｃｅ ｅｎｔｅｒｐｒｉｓｅｓ ｃｏｎｆｉｇｕｒａｔｅ ｆｉｒｅｗａｌｌｓ ａｃｃｏｒｄｉｎｇ ｔｏ ｉｔｓ ｎｅｅｄ；ｔｈｅ ｒｕｌｅ ｔａｂｌｅ ｗｉｌｌ ｂｅ ｉｎｃｌｕｄｅｄ．Ｈｏｗｅｖｅｒ，ｐｒｏｂｌｅｍｓ ｍａｙ ｏｃｃｕｒ ｄｕｒｉｎｇ ｃｏｎｆｉｇｕｒａｔｉｏｎ．Ｏｎ ｏｎｅ ｈａｎｄ，ｔｈｅ ａｄｍｉｎｉｓｔｒａｔｏｒ ｈｉｍｓｅｌｆ ｍａｙ ｍａｋｅ ｓｏｍｅ ｍｉｓｔａｋｅｓ ｄｕｒｉｎｇ ｉｎｉｉｔａｌ ｃｏｎｆｉｇｕｒａｔｉｏｎ．Ｏｎ ｔｈｅ ｏｔｈｅｒ ｈａｎｄ，ｐｏｓｓｉｂｉｌｉｔｙ ｏｆ ｃｏｎｆｌｉｃｔｓ ａｍｏｎｇ ｄｉｆｅｒｅｎｔ ｒｕｌｅｓ ｉｎｃｒｅａｓｅｓ ｗｉｈ ｒｔｕｌｅ ｎｕｍｂｅｒｓ ｉｎ ｔｈｅ ｔａｂｌｅ ｇｒｏⅥ ｉｎｇ Ｔｈｉｓ ｐａｐｅｒ ａｎａｌｙｚｅｓ ｐｏｓｓｉｂｌｅ ｍｉｓｔａｋｅｓ ｉｎ ｔｈｅ ｃｏｎｆｉｇｕｒａｔｉｏｎ ｐｒｏｃｅｓｓ．Ｉｔ ｉｎｔｒｏｄｕｃｅｓ ｓｅｖｅｒａｌ ｆａｍｉｌｉａｒ ｔｙｐｅｓ ｏｆ ｍｉｓｔａｋｅｓ ｉｎ ｃｏｎｆｉｇｕｒａｔｉｏｎ，ｐｕｔｓ ｆｏｒｗａｒｄ ｔｈｅ ａｌｇｏｒｉｔｈｍ ｗｈｉｃｈ ｃａｎ ｆｉｎｄ ｍｉｓｔａｋｅｓ．Ｔｈｅ ｐａｐｅｒ ｉｍｐｒｏｖｅｓ ｔｈｅ ａｌｇｏｒｉｔｈｍ ａｃｃｏｒｄｉｎｇ ｔｏ ｔｈｅ ｃｈａｒａｃｔｅｒｉｓｔｉｃｓ ｏｆ ｔｈｅ ｆｉｒｅｗａｌｌ ｒｕｌｅ ｔａｂｌｅ，ｗｈｉｃｈ ｉｎｃｒｅａｓｅｓ ｅｆｆｉｃｉｅｎｃｙ ｏｆ ｄｅｔｅｃｔｉｎｇ ｃｏｎｆｉｇｕｒａｔｉｏｎ ｍｉｓｔａｋｅｓ． 【Ｋｅ≥，ｗｏｒｄｓ］Ｆｉｒｅｗａｌｌ；Ｐａｃｋｅｔ ｆｉｌｔｅｒｉｎｇ；Ｒｕｌｅ ｃｏｎｆｌｉｃｔ １概述 根据企业制定的安全策略，防火墙中保存着一个访问控 （１）缺少默认规则 当数据包到达防火墙时，防火墙顺序的将其中的规则和 数据包进行比较，直到某一条规则的过滤域和数据包的包头 部分相匹配，再采取该规则规定的动作。如果防火墙的规则 表中所有的规则都和数据包不匹配，那么防火墙就没有办法 决定如何处理这个数据包，错误也就出现了。 （２）存在无关规则 对于防火墙中的任何一条规则，它的源ＩＰ地址域和目标 ＪＰ地址域必须和防火墙连接的网段相关。否则，匹配该规则 的数据包就不可能到达此防火墙，把这种规则称为无关规则。 （３）规则问相互屏蔽 制列表，用以决定当数据包到来时应该采取的操作。该访问 控制列表由许多列表项组成，每个列表项称为一条规则，每 个规则又由３个部分组成：规则号，过滤域和动作域。规则 号是规则在访问控制列表中的顺序，保证了数据包匹配的次 序。过滤域可以由许多项构成，但常用的有５项：源ＩＰ地址， 目标ＩＰ地址，源端口，目标端口和协议。动作域通常只有两 种选择：接受，即允许数据包通过防火墙；拒绝，即不允许 数据包通过。表１就是一个防火墙规则表的样例。 表１防火｜Ｉ规列表样倒 序号 ｌ ２ ３ 协议 ＴＣＰ ＴＣＰ ＴＣＰ 源ＩＰ 地址 ｌ９２ ｌ６８ ３０ ２０ ｌ９２ ｌ６８ ３０ 源端口 ａｎｙ ａｎｙ ａｎｙ 日标ＩＰ 地址 目标 端口 ８０ ８０ 动作 ｄｅｎｙ ａｃｃｅｐｔ 对于防火墙中的每一条规则，都可能会有很多数据包和 它匹配，条件是这些数据包的包头部分和这个规则的过滤域 部分相匹配。把这些数据包放到一起，构成一个集合，记为 该规则的匹配集。考虑两条规则ＲＩ和Ｒ２，ＲＩ在Ｒ２之前， Ｒ２的匹配集是Ｒ１的匹配集的子集，那么规则Ｒ２就不可能 被激活，如果二者的动作域不同，那么规则Ｒ２就被规则ＲＩ 屏蔽了。对于二者动作域相同的情况，下文中有专门的论述。 （４）规则交叉冲突 ｌ９２ ｌ６８ ４０ ４０ ８０ ４ ５ ６ ＴＣＰ ＴＣＰ ＴＣＰ ｌ９２ ｌ６８ ３０ ｌ９２１６８ ３０ ３０ １９２．１６８ ３０ ａｎｙ ａｎｙ ａｎｙ ｌ９２ ｌ６８．４０ ４０ ８０ ２ｌ ２ｌ ｄｅｎｙ ｄｅｎｙ ７ ８ ＴＣＰ ＴＣＰ ｌ９２ ｌ６８ ３０｝ Ｉ９２Ｉ６８ ８Ｏ ４０ ａｎｙ ａｎｙ ｌ９２ ｌ６８ ４０ ４０ Ｉ９２ Ｉ６８ ４０ ２ｌ ａｎｙ ｄｅｎｙ ａｃｃｅｐｔ ９ ＩＯ 】Ｉ ＵＤＰ ＵＤＰ ＵＤＰ １９２１６８ ３Ｏ ａｎｙ ａｎｙ ａｎｙ ｌ９２ Ｉ６８．４０ ５Ｏ ｌ９２ １６８ ４０ ５０ ｊ９２ ｊ６８ ４０ ５３ ５３ ａｎｙ ａｃｃｅｐｔ ａｃｃｅｐｔ ｄｅｎｙ 对于规则ＲＩ和Ｒ２，如果二者的匹配集存在交集，但匹 配集之问并没有包含关系存在，那么规则ＲＩ和Ｒ２就出现了 规则交叉现象，匹配集的交集部分就给出了同时匹配这两条 规则的数据包集合。此时，如果Ｒ１的动作域和Ｒ２的动作域 基金项目：国家“８６３”计划基金资助项目（２００３ＡＡ１０３７１０） ｌ２ ＵＤＰ ａｎｙ ａｎｙ ｄｅｎｙ 当数据包到达防火墙时，顺序查找防火墙规则，直到某 条规则的过滤域部分和数据包相匹配，再采取该规则对应的 动作。但是，规则表的配置很容易出现问题，Ｆ文中给出了 常见的配置错误。 ２规则配置错误的常见类型 在防火墙的规则配置过程中，容易出现以下几种错误： 作者简介：王卫平（１９５３一），女，副教授，主研方向：数据挖掘，信 息安全；陈文惠、朱卫未，博士生；陈华平，教授、博导 收稿日期：２００６—０６—２２ Ｅ－ｍａｉｌ：ｂｒｕｃｅｃｈｅｎ＠ｕｓｔｃ．ｅｄｕ ｌ３２一 维普资讯 http://www.cqvip.com 不同，那么称这两条规则存在规则交叉冲突。 （５）规则冗余 现在回过头来考虑在讨论规则间相互屏蔽时提到的情 况。对于两条规则Ｒ１和Ｒ２，Ｒ１在Ｒ２之前，Ｒ２的匹配集是 Ｒ１的匹配集的子集，如果二者的动作域不同，那么规则Ｒ２ 就被规则Ｒ１屏蔽了，如果二者的动作域相同，那么，Ｒ２就 是Ｒｌ的冗余。 ３规则配置错误检测算法 针对上文列出的５种常见规则配置错误，设计了相应的 算法。共有两个算法来完成规则配置错误的发现， ＤｅｔｅｃｔＳｉｍｐｌｅＥｒｒｏｒ和ＤｅｔｅｃｔＣｏｎｆｉｌｃｔ。算法ＤｅｔｅｃｔＳｉｍｐｌｅＥｒｒｏｒ 可以发现前两种配置错误，因为只要扫描一下规则表就可以 检测到前两种错误，算法比较容易设计，这里就不列出了。 后面３种错误都可以看成是规则间发生冲突，只是冲突的类 型不同而已，算法ＤｅｔｅｃｔＣｏｎｆｌｉｃｔ可以完成后３种规则配置错 误的发现。 ３．１规则冲突检测算法原理 首先采用判定树模型 来进行规则冲突检测。 对于规则Ｒ１和Ｒ２，Ｒ１在Ｒ２之前，判定树的根节点表 示二者协议域的比较，根节点有４个分支，分别表示：（１）Ｒ１ 的协议域是Ｒ２的协议域的真子集；（２）Ｒ１的协议域是Ｒ２的 协议域的超集；（３）Ｒ１的协议域和Ｒ２的协议域相同；（４）Ｒ１ 的协议域和Ｒ２的协议域不相关。对于分枝Ａ、Ｂ和Ｃ来说， 它的根节点接着进行Ｒ１和Ｒ２的源ＩＰ地址域的比较，并根 据比较结果继续创建分枝，这个过程一直持续下去，直到能 够产生比较结果。对于分枝Ｄ，很显然，规则Ｒ１和Ｒ２不可 能产生冲突，Ｒ１和Ｒ２的比较也就完成了。 把判定树模型转化为算法就可以进行规则冲突的检测 了。判定树方法的特点是简单明了，但是速度却比较慢。因 此，在判定树方法的基础上，提出了一种新的规则冲突检测 算法ＤｅｔｅｃｔＣｏｎｆｌｉｃｔ。 ３．２规则冲突检测算法的实现 通过观察判定树模型，可以归纳出３种冲突错误的发生 条件。考虑两条规则Ｒ１和Ｒ２，Ｒ１在Ｒ２之前。如果Ｒ１的 过滤域的每部分是Ｒ２的对应部分的超集，或者和Ｒ２的对应 部分相同，那么，当二者的动作域相同时，发生规则冗余， 当二者的动作域不同时，Ｒ２被Ｒ１屏蔽。如果Ｒ１的过滤域 中至少有一个是Ｒ２的对应部分的超集，同时至少有一个是 Ｒ２的对应部分的真子集，并且剩下的过滤域都和Ｒ２的对应 部分存在包含关系，那么，当二者的动作域不同时，发生规 则交叉冲突。 为了快速地确定规则Ｒ１和Ｒ２之间是否存在规则配置错 误，首先把Ｒ１和Ｒ２的过滤域对应部分相比较，比较结果放 到数组ｔｅｍｐ中。ｔｅｍｐ数组共有５项，ｔｅｍｐ［１］存放的是协议 域的比较结果，共有４种取值：０，１，２，３。０表示Ｒ１的协 议域和Ｒ２的协议域不可比较，ｌ表示Ｒｌ的协议域是Ｒ２的 协议域的真子集，２表示Ｒ１的协议域和Ｒ２的协议域相同，３ 表示Ｒ１的协议域是Ｒ２的协议域的超集。ｔｅｍｐ数组的其它４ 项ｔｅｍｐ［２】，ｔｅｍｐ［３】，ｔｅｍｐ［４］和ｔｅｍｐ［５】，分别对应源ＩＰ地 址域，源端口域，目标ＩＰ地址域和目标端口域的比较结果， 也共有４种取值：０，１，２，３，取值的意义参考协议域。先 上 计算这５项的乘积Ｊｌｔｅｍｐ［ｉ】，如果乘积为０，那么必然有部分 过滤域不可比较，Ｒ１和Ｒ２就没有冲突；如果乘积不为０， 表示所有的ｔｅｍｐ［ｉ］都不等于０，即过滤域相应部分都可以比 较，就继续进行下去。计算 ５ １－Ｉ（ｔｅｍｐ［ ］一１） ｉ＝１ 的值，如果该值不为０，那么所有的ｔｅｍｐ［ｉ］要么是２，要么 是３，表示Ｒ１的过滤域的每部分不是和Ｒ２的对应部分相同， 就是Ｒ２的对应部分的超集，再根据动作域的比较结果，就 可以得出具体的错误类型了；那么如果该值为０呢？这就表 示Ｒ１的过滤域中至少有一个是Ｒ２的对应部分的真子集，再 进行最后一次计算就可以得出比较结果。计算 ５ 兀（ｔｅｍｐ…一３） ｌ 如果该值为０，表示Ｒｌ的过滤域中至少有一个是Ｒ２的 对应部分的超集，那么，再根据动作域的比较结果，我们就 可以判断出Ｒ１和Ｒ２之间是否存在冲突。下面给出算法 ＤｅｔｅｃｔＣｏｎｆｌｊｃｔ： ＤｅｔｅｃｔＣｏｎｆｌｉｃｔ（Ｒｕｌｅ—ｔａｂｌｅ ｒ） ｆ ｆｏｒ ｋ＝ｌ ｔＯ ｒ．ｃｏｕｎｔ一１ ｆｏｒ ｊ＝ｋ＋ｌ ｔｏ ｒ．ｃｏｕｎｔ ｆ Ｃｏｍｐａｒｅ（ｒ［ｋ］，ｒＩｊ］，ｔｅｍｐ）； 把规则ｒ【ｋ］和ｒ［ｉ］的比较结果放入ｔｅｍｐ数组 ／ Ｉｆ（兀ｔｅｍｐ［ｉ］！＝０）ｆ ＝ｌ ５ ｉｆｄ－＝ｌＩ（ ｔｅｍｐ［ｉ］一１）！＝０）ｆ ｉｆ（ｒ［ｋ］．ａｃｔｉｏｎ＝ｒ［ｊ］．ａｃｔｉｏｎ） ｐｒｉｎｔ ｒＵ］是 ｋ］的冗余； ｅｌｓｅ ｐｒｉｎｔ ｒＩｊ］被 ｋ］屏蔽； ） ５ ｅｌｓｅ ｉｆ（兀（ｔｅｍｐ［ｉ］一３）＝０ ａｎｄ ｒ【ｋ】．ａｃｔｉｏｎ！＝ｒ［ｊ］．ａｃｔｉｏｎ） ｉ＝Ｉ ｆｐｒｉｎｔ ｒ［ｊ］和ｒ【ｋ］发生交叉冲突；））） ） ３．３仿真结果 将算法ＤｅｔｅｃｔＳｉｍｐｌｅＥｒｒｏｒ和ＤｅｔｅｃｔＣｏｎｆｌｉｃｔ分别应用于表 １，得到如下结果： 规则表中缺少默认规则 规则８为无关规则 规则１和规则３发生交叉冲突 规则４被规则２屏蔽 从上面算法输出的结果不难看出，算法能够检测到本文 提出的５种防火墙规则配置错误。考虑到企业防火墙规则配 置的保密性，本算法在虚构的规则集上进行了测试，获得了 良好的效果。与以前规则配置错误的检测算法如ＡＢＶ，ＯＢＶ 相比，本算法可以检测到更多的配置错误，在实践中可以进 一步提高规则配置的正确性，增加防火墙的安全性。 但是，上面的规则冲突检测算法ＤｅｔｅｃｔＣｏｎｆｌｉｃｔ还存在着 可以改进的地方。该算法在检测冲突的时候，把每一对规则 都拿出来进行比较，对规则表采用了两个循环操作来发现最 终错误，如果规则表中规则数很多，那么速度就比较慢。因 而可以借鉴包分类算法的思想，进一步地提高规则冲突检测 算法的速度ｏ ４改进的规则冲突检测算法 上文中已经提到了，目前算法执行速度慢的原因在于， 它要对规则表执行两次循环操作。那么为什么要执行两次循 维普资讯 http://www.cqvip.com 环操作呢？这是因为算法并不知道有哪些规则对可能会发生 冲突。如果能够快速地把可能和一条规则发生冲突的规则集 合列出来，就可以把这条规则和集合内的规则依次进行比较， 很明显，这将大大缩短比较的时间，因而可以提高规则冲突 检测的速度。 协议域是规则过滤域部分的其中一项，很显然，协议域 ） ｆｔｅｍｐ＝ｔｅｍＰＵＭｈｉｔＶｅｃｔ２；｝ Ｅｌｓｅ ｆｔｅｍｐ＝Ｕ 惭ｆ２Ｕ ，，ｌｐ； ，半Ｌ表示节点Ｎ以后第一次遇到的有效前缀节点 ， ／／下面是目的ＩＰ地址Ｔｒｉｅ部分 ｔｅｍｐｉ＝０； 不同的规则之间不可能发生冲突，因而可以进行第ｌ项改进： 将协议域为ＴＣＰ的规则单独放入一张表中，名为 ＴＣＰＲｕｌｅＴａｂｌｅ，规则的序号不变，同时，将协议域为ＵＤＰ的 规则单独放入一张表中，名为ＵＤＰＲｕｌｅＴａｂｌｅ，规则的序号也 不变。那么，如果需要查找存在冲突的规则，只需要到相应 ，，得出可能产生冲突的规则 ｔｅｍｐ２＝ｔｅｍｐｎｔｅｍｐｉ： ／／将ｒ和ｔｅｍｐ２中为１的规则进行比较 的表中查找，这可以减少相当一部分搜索时间。 现在考虑规则过滤域中源ＩＰ地址和目的ＩＰ地址两个部 分。以ＴＣＰＲｕｌｅＴａｂｌｅ表为例，建立两个Ｔｒｉｅ Ｊ：一个对应于 该表的源ＩＰ地址部分，另一个对应于该表的目的ＩＰ地址部 分。对于源ＩＰ地址Ｔｒｉｅ中的每一个有效前缀节点Ｎ，都有两 个比特向量与之对应。第１个比特向量（ｂｉｔＶｅｃｔ１）的第ｉ位 为ｌ，当且仅当存在规则ｒ【ｉ】，该规则的源ＩＰ地址域是节点 前缀的精确匹配。第２个比特向量（ｂｉｔＶｅｃｔ２）满足一个恒等式： Ｎ．ｂｉｔＶｅｃｔ ２＝（Ｕ ｃ．ｂｉｔＶｅｃｔ ２）Ｕ Ｎ．ｂｉｔＶｅｃｔ １ 实际上，ｂｉｔＶｅｃｔＩ为１的位表示对应规则的源ＩＰ地址域和节 点前缀相同，ｂｉｔＶｅｃｔ２为ｌ的位表示节点前缀是对应规则的 源ＩＰ地址域的前缀。对于目的ＩＰ地址Ｔｒｉｅ，也做同样的工 作，现在已经对ＴｃＰＲｕｌｅＴａｂｌｅ表构造了两个Ｔｒｉｅ。同样地， 也对ＵＤＰＲｕｌｅＴａｂｌｅ表构造两个Ｔｒｉｅ，构造的方法如上所述。 考虑一条规则Ｒ，需要判断它和哪些规则发生冲突。 （１）察看Ｒ的协议域，如果协议域是ＴＣＰ，那么就到 ＴＣＰＲｕｌｅＴａｂｌｅ表构造的Ｔｒｉｅ去寻找冲突；否则，就在 ｕＤＰＲｕｌｅＴａｂｌｅ表的对应Ｔｒｉｅ寻找。 （２）在源ＩＰ地址Ｔｉｌｅ上寻找。从根节点开始，把所有有 效前缀节点的ｂｉｔＶｅｃｔｌ并在一起，记作ｓ＿ｉｐＶｅｃｔ，结束条件是 找到规则Ｒ的精确匹配节点Ｎ，此时向量ｓ＿ｉｐＶｅｃｔ为ｌ的位 表示对应规则的源ＩＰ地址域要么是Ｒ的前缀，要么和Ｒ相 同。如果Ｎ是有效前缀节点，那么Ｎ的第２个比特向量 ｂｉｔＶｅｃｔ２就记载了这些规则，Ｒ的源ＩＰ地址是它们的前缀， 把Ｎ．ｂｉｔＶｅｃｔ２和ｓ ｉｐＶｅｃｔ并在一起，就可以看到所有和Ｒ的 源ＩＰ地址有关的规则；如果Ｎ不是有效前缀节点，那么把Ｎ 的所有第１次遇到的孩子节点的ｂｉｔＶｅｃｔ２并在一起，条件是 这些孩子节点是有效前缀节点，把合并的结果再和ｓ＿ｉｐＶｅｃｔ 并在一起，也可以看到所有和Ｒ的源ＩＰ地址有关的规则。 （３）对目的ＩＰ地址Ｔｉｌｅ做同样的工作。 （４）将前两步的结果相交，就形成了最终可能出现冲突的 规则。 （５）类似于前面的算法，在第（４）步的结果集内进行比较， 找到冲突规则。伪代码如下： ＦａｓｔＤｅｔｅｃｔＣｏｎｆｌｉｃｔ（ｒｕｌｅ ｒ） ｛ｉｆ（ｒ．ｐｒｏｔｏｃｏｌ＝ＴＣＰ） ｆ／／下面是源ＩＰ地址Ｔｒｉｅ部分 ｔｅｍｐ＝０； ｆｏｒ ｅａｃｈ ｖａｌｉｄ ｐｒｅｆｉｘ ｎｏｄｅ Ｍ ｆｒｏｍ ｒｏｏｔ ｕｎｔｉｌ ａｎ ｅｘａｃｔ ｍａｔｃｈ ｏｆｒ．ｓ—ｌ ｐ ｔｅｍｐ ＭｂｉｔＶｅｃｔ１Ｕｔｅｍｐ； ｉｆ ｒ．ｓ—ｉｐ ｍａｔｃｈｅｓ ａ ｖａｌｉｄ ｐｒｅｆｉｘ ｎｏｄｅ Ｍ —ｌ３４．一 ｝ ｅｌｓｅ ｉｆ（￣ｐｒｏｔｏｃｏｌ＝ＵＤＰ） ｆ…） ｌ 算法ＤｅｔｅｃｔＣｏｎｆｌｉｃｔ在查找与一条规则发生冲突的规则 集的时间复杂度是０（ｎ），而算法ＦａｓｔＤｅｔｅｃｔＣｏｎｆｌｉｃｔ只需在 Ｔｒｉｅ上查找，时间复杂度是０（ｈ），ｈ是Ｔｒｉｅ树的高度。当规 则数很大的时候，算法ＦａｓｔＤｅｔｅｃｔｃｏｎｎｉｃｔ的两个改进可以大 大的缩短规则冲突查询的时间。算法ＤｅｔｅｃｔＣｏｎｆｌｉｃｔ只需要把 规则表存储一次，因而空间复杂度为Ｏ（ｎ），而算法 ＦａｓｔＤｅｔｅｃｔＣｏｎｆｌｉｃｔ分散存储了ＵＤＰ和ＴＣＰ规则，这一步是 不增加存储空间的，关键是接下来它要存储两个Ｔｄｅ树，对 于树的每一个有效前缀节点还要有两个比特向量，因而算法 ＦａｓｔＤｅｔｅｃｔＣｏｎｆｌｉｃｔ需要更多的空间。 ５结论和展望 作为企业网络安全的屏障，防火墙发挥着巨大的作用。 但是，如果没有对防火墙进行正确的配置，这个屏障也就形 同虚设。本文就防火墙的规则配置过程中容易出现的几种错 误进行了分析，并且给出了检测错误的算法。改进后的算法 具有较快的执行速度，可以获得更高的执行效率。 目前对于防火墙规则配置错误的研究还不太多，我们认 为可以对提高规则配置错误的检测速度、进一步明确规则配 置错误的类型这两个方面进行进一步的研究。目前规则配置 错误的分类还不是很完善，进一步研究规则配置错误的分类 可以使我们发现更多的隐藏错误，提高防火墙的安全性。 参考文献 １ Ｇｏｕｄａ Ｍ，Ｌｉｕ Ｘ．Ｆｉｒｅｗａｌｌ Ｄｅｓｉｇｎ：Ｃｏｎｓｉｓｔｅｎｃｙ，Ｃｏｍｐｌｅｔｅｎｅｓｓ，ａｎｄ Ｃｏｍｐａｃｔｎｅｓｓ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ２４ ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｄｉｓｔｒｉｂｕｔｅｄ．２００４．０３． ２ Ａｌ—Ｓｈａｅｒ Ｅ．Ｈａｍｅｄ Ｈ．Ｄｅｓｉｇｎ ａｎｄ Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ ｏｆ Ｆｉｒｅｗａｌｌ Ｐｏ￣ｃｙ Ａｄｖｉｓｏｒ Ｔｏｏｌｓ［Ｒ］．Ｓｃｈｏｏｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ Ｔｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎｓ ａｎｄ Ｉｎｆｏｒｍａｔｉｏｎ Ｓｙｓｔｅｍｓ，ＤｅＰａｕｌ Ｕｎｉｖｅｒｓｉｔｙ，ＣＴＩ－ｔｅｃｈｒｅｐ：０８０１， ２ｏｏ２一Ｏ８． ３ Ｈａｒｉ Ｂ，Ｓｕｒｉ Ｓ．Ｐａｒｕｌｋａｒ Ｇ Ｄｅｔｅｃｔｉｎｇ ａｎｄ Ｒｅｓｏｌｖｉｎｇ Ｐａｃｋｅｔ Ｆｉｌｔｅｒ Ｃｏｎｆｌｉｃｔｓ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ＩＥＥＥ ＩＮＦＯＣＯＭ＇００．２０００－０３． ４ Ｂａｂｏｅｓｃｕ Ｆ Ｖａｒｇｈｅｓｅ Ｇ Ｆａｓｔ ａｎｄ Ｓｃａｌａｂｌｅ Ｃｏｎｆｌｉｃｔ Ｄｅｔｅｃｔｉｏｎ ｆｏｒ Ｐａｃｋｅｔ Ｃｌａｓｓｉｉｆｅｒｓ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ １０ ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｎｅｔｗｏｒｋ Ｐｒｏｔｏｃｏｌｓ．２ｏｏ２． ５ Ｈａｎ Ｊ，Ｋａｍｂｅｒ Ｍ．Ｄａｔａ Ｍｉｎｉｎｇ：Ｃｏｎｃｅｐｔｓ ａｎｄ Ｔｅｃｈｎｉｑｕｅｓ［Ｍ】． ＭｏｒｇａｎＫａｕｆｍａｎｎ，２０００．
