面向云数据中心环境防火墙即服务的并行防火墙规则异常检测的方法

摘要

本发明属于云计算和网络安全防火墙技术领域，具体为一种面向云数据中心环境防火墙即服务的并行防火墙规则异常检测的方法。本发明从云数据中心环境防火墙作为服务FWaaS出发，首先设计了一种同时基于数据包分类与规则分布的并行防火墙，对于并行防火墙规则异常检测的方法，本发明通过建立规则-子段表的方法来检测可能存在的规则异常，并引入重叠集来缩小检测范围，为后序对防火墙规则处理打下基础，并得到防火墙规则的逻辑顺序。实验证明，本发明所设计的并行防火墙规则异常检测方法符合多项功能和性能要求，可以以FWaaS服务的形式应用在云数据中心环境中。

说明书

技术领域

本发明属于云计算和网络安全防火墙技术领域，具体涉及一种面向云数据中心环境防火墙即服务的并行防火墙规则异常检测的方法。 

背景技术

随着互联网的发展与普及，网络安全问题引起了产业界与学术界的广泛关注。作为内部网络抵御外部威胁的第一道门槛，防火墙的安全性和可靠性至关重要。防火墙是一类防范措施的总称，它使得内部网络与Internet之间或者与其他外部网络互相隔离、限制网络互访用来保护内部网络。设置防火墙的目的是为了在内部网络与外部网络之间设立唯一的通道，简化网络安全的管理。

对于流经防火墙的网络流量，防火墙会对其中的数据包进行检测，对那些不符合防火墙策略的数据包进行过滤。实施过滤的原则主要基于数据包中的源/目的地址、源/目的端口号、IP标识和报文传递的方向等具体信息。正因为防火墙的设计简单，非常易于实现，而且价格便宜，所以防火墙被广泛地部署在计算机系统中。也正因为防火墙得到了广泛地应用，所以对如何提高防火墙性能，如何方便地使用防火墙一直是学术研究的热点。

现今，云计算提供“服务”的范围越来越广。除了传统的IaaS，PaaS，SaaS之外，现在已经有了存储即服务(SaaS, Storage as a Service)，网络即服务(NaaS, Network as a Service)，监测即服务(MaaS, Monitoring as a Service)和认证即服务(AaaS, Authentication as a Service)等其他类型的服务。甚至业界已经提出了一切皆服务( XaaS, X as a Service)。这意味着在云数据中心环境下，有越来越多的功能会以“服务”的形式提供给租户。所以为了使未来下一代防火墙能更好地应用在云计算环境中，防火墙需要服务化和虚拟化。防火墙应该作为一种服务提供给消费者，即防火墙即服务(FWaaS, Firewall as a Service)防火墙规则检测是一个智能化的防火墙中必须拥有的一个模块。众所周知，防火墙策略管理是一个非常有挑战的工作，因为防火墙规则之间有着复杂的相互依赖交叉关系。由于云数据中心环境下的网络越来越庞大，防火墙资源被服务化和虚拟化，防火墙的规则也越来越多，尤其云数据中心环境中的租户可以通过租用多条虚拟防火墙来组成自己的并行防火墙，这就出现了多个并行防火墙规则发生冲突的问题。如何保证防火墙规则的正确性和避免冲突是一个难题。因此，本设计侧重于设计面向云数据中心环境防火墙即服务的并行防火墙中规则异常检测的方法。

经对现有技术的文献检索发现， S.Al-Shaer等在防火墙策略冲突检测方面做了很多的研究工作。在文献[Al-Shaer E, Hamed H. Design and implementation of firewall policy advisor tools[J]. DePaul University, CTI, Tech. Rep, 2002；Al-Shaer E S, Hamed H H. Firewall policy advisor for anomaly discovery and rule editing[C]//Integrated Network Management, 2003. IFIP/IEEE Eighth International Symposium on. IEEE, 2003: 17-30； Al-Shaer E S, Hamed H H. Modeling and management of firewall policies[J]. Network and Service Management, IEEE Transactions on, 2004, 1(1): 2-10.]中，作者提出防火墙规则的5种关系：Exactly Matched，Inclusively Matched，Completely Disjoint，Partially Disjoint，Correlated。基于这5种关系，作者画出了两条防火墙规则间关系的状态图，之后作者提出了基于状态图的规则异常检测方法。， S.Al-Shaer等又在[Al-Shaer E S, Hamed H H. Discovery of policy anomalies in distributed firewalls[C]//INFOCOM 2004. Twenty-third AnnualJoint Conference of the IEEE Computer and Communications Societies. IEEE, 2004, 4: 2605-2616； Al-Shaer E, Hamed H, Boutaba R, et al. Conflict classification and analysis of distributed firewall policies[J]. Selected Areas in Communications, IEEE Journal on, 2005, 23(10): 2069-2084.]中把成果扩展到分布式防火墙中，着手研究防火墙间的策略冲突检测。但这些成果都是基于传统的防火墙的，并不能直接应用在云数据中心环境下。在文献[Fulp E W. Parallel firewall designs for high-speed networks[C]//INFOCOM 2006. 25th IEEE International Conference on Computer Communications. Proceedings. IEEE, 2006: 1-4.]提出了一种并行防火墙的模型：可以把防火墙规则按一定的分类方式（比如按TCP，UDP分类）分布到不同的防火墙中。数据包按照自身是TCP或UDP分流到相应的防火墙中。这种防火墙的设计可以大大提高防火墙的效率。但作者只是提出了简单的分类方法，且分类方法没有和数据流量的特性关联起来，所设计的系统也不能进行动态扩展。在文献[Hamed H H, El-Atawy A, Al-Shaer E. Adaptive Statistical Optimization Techniques for Firewall Packet Filtering[C]//INFOCOM. 2006, 6: 1-12.]中，作者提出了应该尽早地过滤掉不需要的数据包，这样防火墙的效率才能提高。所以作者抽取出防火墙规则中“Deny”的规则，把这些规则集称为                                                规则。规则集能尽早地过滤掉数据包，从而减少了数据包在防火墙内停留的时间。规则集能够依据数据流量的变化而进行动态调整，从而达到较好的效果。如果数据流中有较多可以拒绝的数据包，该防火墙在性能上是有很大的提升的；但是如果有数据流中存在大量能通过防火墙的包，那么防火墙的性能并没有多大的提升。而且，论文也没考虑不能匹配的数据包。虽然作者没有使用首次匹配方法，但尽早过滤数据包的思想仍值得借鉴。在文献[Rupali Chaure,  Shishir K. Shandilya Firewall anamolies detection and removal techniques – a survey International Journal on Emerging Technologies 1(1): 71-74(2010)]中,作者调研了几种防火墙规则冲突的检测方法，然后提出“irrelevant anomaly”仍然是个研究的难点，因为防火墙是要根据数据包的动态变化而增减防火墙中的规则，这在目前的算法中研究很少。但这种冲突可以通过动态重新排列防火墙规则来达到一个较好的效果。

在云数据中心环境防火墙技术方面，文献[Hajjat M, Sun X, Sung Y W E, et al. Cloudward bound: planning for beneficial migration of enterprise applications to the cloud[J]. ACM SIGCOMM Computer Communication Review, 2010, 40(4): 243-254.]提出了传统服务从本地服务器搬到云端后所会带来的问题。文章先讨论了部分服务迁移到云端所要遵循的各种限制（如安全等）及迁移到云端之后所带来的效益，之后讨论了迁移过程中所带来的防火墙规则的迁移。文献主要考虑了原先的服务是在一个局域网内，但迁移之后是位于不同的局域网内，要使这两种服务之间还是能够相互访问，这就要求更改本地及云端的防火墙策略，使服务之间的数据包能通过防火墙。但文章所提到的防火墙并没有突出云数据中心环境的特色。在[Khakpour A R, Liu A X. First Step Toward Cloud-Based Firewalling[C]//Reliable Distributed Systems (SRDS), 2012 IEEE 31st Symposium on. IEEE, 2012: 41-50.]中，作者认为为了减少防火墙成本，可以把防火墙部署到因特网服务提供商上，使用因特网服务提供商提供的过滤服务。这类似于云计算中的“服务”的思想。但作者的防火墙还是体现在传统的防火墙上，不适应云数据中心环境。文献[Lee S, Purohit M, Saha B. Firewall placement in cloud data centers[C]//Proceedings of the 4th annual Symposium on Cloud Computing. ACM, 2013: 52.]也认为可以把防火墙部署在数据中心，为了隔离虚拟机的通信，虚拟机之间的数据包必须强制通过防火墙，所以很多数据包需要重新路由。论文虽然把防火墙作为一个集中设备来部署，但没有发挥出云数据中心环境中虚拟化的特点。在文献[Yu S, Doss R, Zhou W, et al. A general cloud firewall framework with dynamic resource allocation[C]//Communications (ICC), 2013 IEEE International Conference on. IEEE, 2013: 1941-1945.]中，作者提出了一种适用于云数据中心环境中的防火墙。作者认为可以把防火墙打包成模块，每个模块具有特定的功能，而租户可以通过组合不同的模块搭建自己的防火墙。所以这种防火墙是一条流水线，本质上还是线性的，不能进行动态伸缩。

发明内容

本发明的目的在于提出一种面向云数据中心环境防火墙即服务的并行防火墙规则异常检测的方法。

现今，云计算提供“服务”的范围越来越广。除了传统的IaaS，PaaS，SaaS之外，现在已经有了存储即服务(SaaS, Storage as a Service) ，网络即服务(NaaS, Network as a Service)，监测即服务(MaaS, Monitoring as a Service)和认证即服务(AaaS, Authentication as a Service)等其他类型的服务。甚至业界已经提出了一切皆服务( XaaS, X as a Service)。这意味着在云数据中心环境下，有越来越多的功能会以“服务”的形式提供给租户。

所以为了使未来下一代防火墙能更好地应用在云计算环境中，防火墙也需要服务化和虚拟化，作为一种服务提供给租户和消费者，即防火墙即服务(FWaaS, Firewall as a Service)。由于云数据中心环境中防火墙已经被虚拟成资源池，所以，在云数据中心环境中，租户可以很方便地通过租用多条虚拟防火墙来组建自己的并行防火墙，提高防火墙的性能。

传统的并行防火墙通常基于两种并行方案：基于数据包分类的并行方案和基于规则分布的并行方案。这两种方案都有各自的优点和缺点，传统的防火墙架构没有具备云计算的诸多特性，不符合云计算灵活性的要求，所以如何使防火墙能拥有云计算的特点，可以更好地部署在云数据中心环境当中，需要亟待解决。

本发明结合两种传统方案的优点，设计了一种适用于FWaaS的同时基于数据包分类与规则分布混合模式的并行防火墙。与传统的防火墙相比，该并行防火墙有负载均衡，动态调整，动态伸缩的特点，使防火墙系统有更高的效率，且更适合应用于云数据中心环境。本发明着重于对租户租用多条虚拟防火墙形成并行防火墙时如何对规则异常进行检测。本发明通过建立规则-子段表来检测可能存在的规则异常，并引入重叠集来缩小检测范围，为后序防火墙规则处理打下坚实的基础，也可以确立规则的逻辑顺序。最后通过实验验证了所设计的主要算法，实验证明，本发明所设计的并行防火墙符合多项功能和性能要求，可以较好地部署在云数据中心环境中。

本发明提出的基于云数据中心环境的适用于FWaaS的并行防火墙规则异常检测的方法，具体步骤为：

第一步: 并行防火墙的规则分段

(1) 分段与子段的规划

在云数据中心环境防火墙作为服务面向多租户的并行防火墙的架构中，要对防火墙规则进行检测，分析出规则之间的异常；然后根据异常的类型，决定是否能自动解决，或是让管理员人工做决策，保证每条防火墙规则都能过滤符合要求的数据包；

每条防火墙规则都能过滤符合要求的数据包。防火墙规则分段就是要把防火墙规则分割成不相交的子段，使每个子段所能过滤的数据包空间没有重叠，也就是说，所有子段之间没有重叠，即所有子段之间不相交。

定义-1：防火墙规则分段是指把规则的过滤空间划分成互相不重叠的子空间，其中每个子空间就代表一个子段。所以子段的集合就是防火墙规则分段的结果。

用形式化语言可以把防火墙规则分段定义为：

分段：是的分段

   

其中，表示规则能够过滤的数据包的空间，与中子段所能过滤的数据包空间是一致的。

子段和规则有些区别，规则中字段只有4种关系：=，?，?，≠；而在子段中，字段有5种关系：=，?，?，∩，≠，因为段字段可以表示任意起始位置到终止位置的范围，其中规则中字段和子段中字段的=，?和?这两中关系也称作字段匹配。

现在对子段中字段的关系做出说明：如果两个子段和所对应的字段取值为和，当和表示同一个范围时，那么有；除此之外，如果有表示的范围是的子集，那么有；除此之外，如果有表示的范围是的超集，那么有；除此之外，若表示的范围与有相交，那么有; 除此之外，和的关系为。

所以，子段中的∩关系是排除了=，?，?的相交关系。

子段中的字段有∩关系，而规则中的字段没有∩关系，这主要是因为规则中的字段只能表示特定的范围。

如IP网络地址表示了之间的IP地址；与规则中字段不同的是，子段需要表示不相交的数据空间集，这就要求子段中的字段可以表示任意范围的空间，所以子段中的IP地址可以表示这样的地址段，而这些地址段在防火墙规则中是不可能表示的。正因为子段能表示任意的数据包空间范围，所以子段的字段有∩关系，如和就是∩关系。

为了更好地阐述不同字段所对应的关系，可以把字段与关系绘制成如下表：

表   字段基础关系表

为了把处理范围扩展到防火墙段，可以新定义两种关系称为部分相交与完全相交。

定义-2：如果防火墙子段和有存在交集的字段，但也存在不匹配的字段，那么就称子段和是部分相交关系的。

部分相交：防火墙规则与是部分相交的

          

                

定义-3：如果防火墙规则和所有字段都存在交集，那么就称规则和是部分完全相交关系的。

完全相交：防火墙规则与是完全相交的

          

             and

                        

         

                 

把防火墙规则进行分段有助于提示规则之间的相互关系，这样能更好地进行冲突检测。可以把等价匹配，包含匹配，无关，部分包含匹配，相关匹配，部分相交，完全相交这7种关系称为防火墙规则的扩展关系。

并行防火墙规则分段分析

显然防火墙规则的<规定了该规则所能过滤的数据包空间。比如对于5元组<TCP, 10.10.0.*, any, 192.168.10.10, 80>来说，只能匹配是TCP的，且源地址属于10.10.0.*，目的地址是192.168.10.10，目的端口为80的数据包。

防火墙规则中的字段很可能存在交集，所以防火墙规则所能过滤的数据包集合可能也存在交集。

推论-1：如果两条防火墙规则匹配的数据包空间有重叠，当且仅当规则中所有字段都有交集。

证明：显然，如果两条规则有一个字段不相同，那么可以依据该字段来区分两条规则所能过滤的数据包空间，也就是说，两个数据包空间在该字段上不重叠。所以，当存在不相交的字段时，整个所表示的地址空间不会重叠，即当规则中所有字段都有交集时，数据包空间有重叠。这也从反面证明了数据包空间有重叠时，规则中每个字段都有交集。

所以，根据推论-1，可以看出，只要两条规则存在不相交的字段，即包含关系。那么这两条规则表示的数据包空间就不可能重叠。部分包含，部分相交，无关都包含字段关系，所以这3种规则关系所对应的规则的数据包空间不重叠。我们只需考虑等价匹配，包含匹配，完全相交，相关这4种关系。具体如下表描述：

表2  数据包重叠

 等价包含部分包含相关无关部分相交完全相交数据包空间重叠YYNYNNY

对于分段来说，只需要选取一个字段对防火墙规则进行划分，使得任意两个子段在该字段上都没有重叠。这也确保了每个子段所表示的数据包空间都是独立不相交的空间。

由于重叠的字段只有=，?，?，∩这4种情况，接下来将介绍如何对字段进行分割。可以把字段分割分成以下5种情况，其他情况可以转换成这5种情况之一。

假设现在需要划分子段和子段。

情况1: 。

参见图9。

由图9可知，这种情况下，和共可分割成4个部分。其中：

即与的分段共产生4个子段，

显然，分成了和两个子段，而被分成了和两个子段。

情况2： 。

参见图10。

    此时，与可被分为,,和。所对应的子段为：

情况3：。

参见图11。

此时，与可被分为,,和。所对应的子段为

情况4： 。

参见图12

此时，与可被分为,和。所对应的子段为

情况5： 。

参见图13。

此时，与可被分为,和。所对应的子段为

在每种情况划分的子段中，有两种类型的子段：属于或属于的子段。这个过程也是算法中函数，算法会分别把这两种子段分别加入到对应的规则集或子段集中。算法的具体介绍将在下小节中展开。

混合模式并行防火墙规则分段算法的设计

上小节阐述了如何把相交的防火墙按照某个字段进行分段。接下来，将对防火墙规则分段的具体算法进行设计。显然，算法是要把规则集划分成子段集。规则只能在两种情况下加入到子段集中：

情况1：规则与子段集中某一子段相等。

情况2：规则与子段中所有的子段都不相交。

所以，对于不满足这两种情况的规则与子段，可以依照分段方法把规则和子段先进行划分，然后把属于规则的分段重新加入到规则集中；把属于子段的分段重新加入到子段集中取代原来的子段。这样规则集与子段集中的元素会被越分越小，直到上述两种的情况发生。算法的效果就是把规则集中的规则划分为不相交了子段。防火墙规则分段算法具体实现的伪代码如下：

Algorithm -1 防火墙规则分段Input 防火墙规则集ROutput防火墙子段集S1：2：   3：       4：       5：           6：            7：           8：           9：10:

第二步: 并行防火墙规则重叠的检测

在防火墙中，由于防火墙规则的复杂性，规则之间的异常难以完全避免。基于上一步骤中提出来的分段，可以很方便地找出防火墙规则的重叠部分。由于子段之间是没有交集的，所以对于有涉及到有重叠的子段，防火墙管理员可以方便地指明防火墙对该段的处理方法——接收或拒绝，而系统也可以依据管理员的决定来重新调整防火墙规则的顺序。

本步骤将使用二维坐标法来表示防火墙规则与子段之间的关系，使用二维坐标能很方便地显示所有防火墙之间的关系。利用该二维矩阵，可以把具有重叠的防火墙放到重叠集里，这样就可以理出哪些规则是与顺序无关的，哪些规则是与顺序有关的，防火墙规则的异常可以放到相交集中来解决。

规则-子段矩阵表示法

根据字段划分的定义，任意一条防火墙规则都可表示为一系列子段的集合的并集。所以用规则-子段矩阵能很方便地表示规则与子段之间的关系。在规则-子段矩阵中，我们在纵坐标上表示防火墙规则，在横坐标上表示子段。假设有以下规则：

            

把这些规则分成子段之后，可以绘制出如下规则-子段表。5条防火墙规则被划分成了10个子段。其中A表示规则允许数据包通过，N表示规则不允许数据包通过

 S₀S₁S₂S₃S₄S₅S₆S₇S₈S₉S₁₀R₀ A AA A   AR₁N N     NNNR₂     A     R₃N N     NNNR₄       N   

表3  规则-子段表

 (2)防火墙规则重叠集的构建

显然，可以依据规则-子段图可以把具有重叠的防火墙放入独立的集合中，这种独立的集合就是重叠集。重叠集的定义可以如下描述：

重叠集：防火墙规则集合是规则的重叠集

        

          

           

          

          

从定义中可以看出，重叠集是对整个规则集合的一个划分，重叠集之间的规则是完全不相交的，而且每个重叠集都是最小划分，也就是说，重叠集里面不能包含其他重叠集。

接下来分析构建重叠集的算法。对于每一个子段，如果有多条规则与它对应，那么系统要把这些规则包含在新的重叠集当中。如果规则已经存在于其他重叠集中，那么把该重叠集也包含进来。构建防火墙重叠集算法的伪代码如下：

Algorithm -2 构建防火墙重叠集Input 防火墙规则-子段表Output防火墙规则重叠集1：2：    3：       4：           5：       6：           7：               8：                   9：                   10：   11：

建立好防火墙规则的重叠集之后，就可以很方便地知道哪些规则是没有重叠的，哪些规则是有重叠的。在不同重叠集中的规则过滤包的效果与顺序无关顺序，且交换顺序不改变防火墙的一致性。

当然，为了能更好地构建防火墙，需要对每个防火墙规则重叠集进行规则异常的解决，因为，目前防火墙重叠集中仅是存在重叠的规则，有些重叠可以通过规则调整取消，从而使某些规则不在重叠集里。

第三步: 并行防火墙规则冗余检测与解决方法

上一步骤描述了用二维坐标规则-子段矩阵来表示规则与子段之间的关系，进而划分出规则的重叠集。本小节将介绍对重叠集内的规则的处理方法，我们的目标是解决尽可能多的重叠部分，尽而缩小重叠集的规模。

由于重叠集中的规则所覆盖的子段是在一定范围内的，所以可以把重叠集中的规则和其对应的子段单独画成规则-子段矩阵。

有以下两种情况会导致防火墙规则在某一子段上是多余的：

情况1：该子段上防火墙规则前面已有其他规则对数据包进行了匹配处理，这种情况也可以称为覆盖。

情况2：在该子段上，防火墙规则前面没有其他规则，但在后面出现的第一条规则的动作与该规则是一致的，那么后面的规则在该子段上可以替代这条规则。这种情况也称为替代。

所以，如果某条规则在对应的所有子段上都被覆盖或可以替代的，那么这条规则显然是多余的，可以删除这条规则而不改变整个防火墙的一致性。移除冗余规则之后的重叠集，可能可以进一步划分成更多的重叠集，所以有必要对处理之后的重叠集作进一步的划分。

消除重叠集中的冗余规则的算法伪代码如下：

Algorithm -3 消除重叠集中的冗余规则Input 防火墙规则-子段关系表，重叠集Output消除冗余的重叠集1：2：    3：       4：           5：   6：

对于其他的可能存在的防火墙规则异常，在这里并没有着重考虑。但对其他规则异常的消除，规则-子段表都提供了一个良好的处理平台。本发明使用规则-子段处理方法是因为这种方法能得到防火墙规则的逻辑顺序，还具有很强的扩展性，为以后的工作打下了扎实的基础。

第四步: 对并行防火墙规则按照逻辑顺序重新排序

由于防火墙规则使用首次匹配的方法对数据包进行匹配处理，所以在重叠集中的规则必须按原有的顺序排列才能保证与原来防火墙的一致性。在调整规则顺序的时候必须考虑到防火墙规则的逻辑顺序，进行重新排序。

逻辑顺序可以从两个方面来考虑：

（1）逻辑顺序就是在重叠集中规则所对应的顺序。由于重叠集中的任一规则都存在另一规则与之存在重叠关系。所以重叠集中的规则必需按照租户设定的顺序排列，否则可能造成对数据包处理的不一致。

（2）对于每一个数据包而言，在重叠集中可能存在两条或两条以上的规则可以与之匹配。只要这些规则能够按原来相应的顺序排列，就可以确保防火墙能对该数据包进行正确处理。

所以，为了确保防火墙的一致性，必须使规则按照逻辑顺序重新排序，使防火墙对数据包的处理结果和原防火墙保持一致。

附图说明

图1 实验拓扑。

图2 初始规则。

图3 规则及其对应的子段。

图4 规则-子段表。

图 5 重叠集。

图 6 去除重复的重叠集。

图 7 重叠集中规则的处理效率。

图 8 普通规则的处理效率。

图9 划分子段和子段的情况1图示。

图10 划分子段和子段的情况2图示。

图11 划分子段和子段的情况3图示。

图12 划分子段和子段的情况4图示。

图13 划分子段和子段的情况5图示。

图14 本发明方法的流程框架。

具体实施方式

(1) 实验环境

本发明实验数据源采用XXXX项目中的数据源。云审计系统将对XX数据中心的主机日志，网络流量，网络设备日志，HYPERVISOR日志，用户操作日志等进行记录并监控异常行为。

一方面，我们部署了一个简易系统来验证系统的可行性。实验环境中，虚拟子网部署在OpenStack云上，实验对出防火墙的数据包进行统计，图1所示为实验拓扑。

另一方面，我们使用模拟实验的方法对系统的性能进行分析。实验采用虚拟子网出防火墙的数据包对算法进行验证。实验采用Thinkpad X220 (酷睿i5 2450M/4GB/320GB/ Ubuntu)进行相应的实验性能测试。所有的测试代码通过Python进行，分析工作使用Microsoft Office Excel进行。

 (2) 防火墙分段算法验证

 2.1 分段算法正确性验证

本发明在前面已经设计了如何将防火墙规则分段，建立规则-子段矩阵，并依据该规则-子段矩阵把多余的规则删除，确定那些存在重叠的规则的逻辑顺序。为了验证整个过程的正确性，假设有如图2所示的防火墙规则。

从图2可以看出，防火墙规则中存在各种重叠。经过分段之后，防火墙规则将被分成不相交13个子段。图3展示了规则与子段具体的关系，在图3中，规则的表示与子段一样，字段将使用某一段范围表示，在每一条规则后面是它包含的子段。比如规则包含,,,,这5个子段。

由上图3可知，每条防火墙由一个或几个子段组成，每个子段都相互独立，不存在交集。把上面的关系用规则-子段矩阵可表示成图4所示。

其中，字符表示防火墙规则接受对应子段所表示的空间的数据包；字符表示防火墙规则拒绝对应子段所表示的空间的数据包。从图中可以看到清楚看到每条规则与子段之间的关系。比如，在上，有三条规则存在重叠。接下来可以依据RS Table构建防火墙规则重叠集，如图5所示。

图5表示防火墙规则和与其他规则没有重叠，而,和存在重叠。接下来，对多余的规则进行检测。检测的结果如下：

这是因为在每个子段上都被其他规则覆盖。所以删除不影响防火墙对数据包的匹配，如图6所示。

这里需要声明的是，上述图所展示的中间步骤结果，都是代码执行过程中的截图，代码所执行的环境为Ubuntu下的IDLE。

分段算法效率分析

接下来将对算法效率进行分析，文章分别使用不同的防火墙规则数量对算法进行测试，得出不同防火墙数量所需要的时间。

图7是使用比较复杂并相互重叠的防火墙规则对算法进行测试。可以看到，在防火墙规则相互重叠的情况下，算法的效率是指数型的。因为，算法会把有重叠的规则不断地分段直到规则之间不存在冲突。带有重叠的规则会产生子段，只有与子段集中所有子段不存在冲突或与某一子段相等的规则才会被加入到子段集中。但在现实情况中，很少会出现大规模的规则都存在冲突，也就是说，防火墙规则的最大子段集不可能达到如实验中的70条或80条这种程度，所以本实验是对算法的一个极限测试。

下面将在普通情况下对算法进行测试。普通情况下防火墙规则存在冲突，但最大重叠集通常是比较小的，不会达到60条这种程度，见图8所示，由图8可以看出，算法对防火墙规则处理的时间和防火墙规则数量基本成正比。这是因为，在防火墙没有异常的情况下，算法直接将防火墙规则放入到子段集中，所以花的时间与防火墙规则数量基本成正比。