CN103516550B - 一种面向大规模包分类规则集的规则冲突检测方法及系统 - Google Patents

Abstract

本发明涉及一种面向大规模包分类规则集的规则冲突检测方法及系统，所述方法包括：步骤1，接收并解析规则；步骤2，将解析后的规则划分为全前缀规则、非全前缀规则和无前缀规则；步骤3，采用源IP-目的IP双层哈希表H_SIP-DIP或目的IP哈希表H_*-DIP组织全前缀规则集，并对应在H_SIP-DIP或H_*-DIP中进行规则的增加、删除或查询；步骤4，采用源IP-目的IP双维Tire树T_SIP-T_DIP组织非全前缀规则集，并在T_SIP-T_DIP中进行规则的增加、删除或查询；步骤5，采用链表L_*-*组织无前缀规则集，并在L_*-*中进行规则的增加、删除或查询；步骤6，遍历H_SIP-DIP、H_*-DIP、T_SIP-T_DIP和L_*-*中的每一个规则作为被检规则，检测与被检规则冲突的所有规则。本发明解决了现在技术中规则冲突算法存在的不足。

Description

一种面向大规模包分类规则集的规则冲突检测方法及系统

技术领域

本发明涉及网络包分类领域，特别是涉及一种面向大规模包分类规则集的规则冲突检测方法及系统。

背景技术

随着互联网架构的演进以及互联网应用的发展，基于单一IP地址域的传统路由技术已经不能满足网络业务和网络安全的需求。包分类技术，因其能够依据网络数据包包头中的多个字段(通常是源ip地址，目的ip地址，源端口，目的端口，协议号)对网络流量进行细粒度的分类，已在路由器、防火墙、安全网关等各类网络安全设备中得到了广泛的应用。

包分类技术是以包分类引擎中配置规则集为基础而实现的。随着分类需求的不断增加，规则从单维发展为多维，规则集中的规则数目越来越多，并且规则间的关系越来越复杂，这将不可避免的导致规则冲突的情况出现。当进行包分类时，如果一个数据包同时与两条(或多条)规则匹配，而这些规则所规定的处理动作不一样，则说明这两条(或多条)规则冲突。由于规则冲突，网络安全设备将以出乎意料、违背网络管理员初衷的方式处理网络流量，引起管理混乱。所以，对包分类规则集进行规则冲突检测是非常有意义的。

规则冲突检测是指，查找出规则集中所有的冲突规则对，或者在规则集中查找出与某条规则相冲突的所有规则。对于规则冲突检测算法，国内外已有相关研究。目前已有的规则冲突检测算法有：顺序检测算法、ASBV(AggregatedSBitVectors)算法和DBBV(DoubleBinaryBitVectors)算法。

一、顺序检测算法

将被检测规则与规则集中的每条规则进行比较，以判断其是否冲突。显然，顺序检测算法检测具有O(n²)的时间复杂度，当规则数目较大时，速度较慢。

二、ASBV算法

ASBV算法采用分治思想和位向量技术，先找出每一维的冲突规则集，再求交集，获得最终的冲突规则集。ASBV算法为规则的每一维建立一颗Trie树，Trie树的每个节点，关联两个长度等于规则个数的位向量。这两个位向量的每一位，都对应了一条规则。对于第一个位向量，若某条规则的相应维的前缀，与节点对应的前缀相等，则位向量中该规则对应的bit置1。对于第二个位向量，其值等于左右子节点的第二个位向量的并集。叶子节点的两个位向量相等。当进行冲突检测时，ASBV算法先并行地找出每维上，与被测规则相冲突的规则集合，然后再对这些集合求交集。在每一维的处理过程中，根据被测规则相应的分量前缀，在Trie中进行搜索。每访问一个节点，ASBV算法对节点的第一个位向量求并集。当搜索到规则的分量前缀时，对节点的第二个位向量求并集。ASBV算法有两个缺点：(1)ASBV算法只支持前缀表示的规则；(2)位向量运算过多。(3)空间复杂度太大。

三、DBBV算法

DBBV算法同样采用分治思想和位向量技术，但通过将每一维的分量转化为用范围表示，并使用平衡二叉树数据结构，减少了位向量的运算。但当进行增量更新时，DBBV算法不但要修改二叉树，而且还要修改大量的位向量，所以不适合规则更新频率较快的应用。

从ASBV算法和DBBV算法的思想可以看出，其主要是关注于如何提升冲突检测速度，而对实时增量更新的支持不好。当增加或删除某一规则时，因位向量的长度、与规则的对应关系和值都需要改变，所以需要重构位向量。而对于DBBV算法，增加或删除规则时，对平衡二叉树也需要调整，所以增量更新规则的效率较低。而对于一些应用，如UTM系统，因其支持各安全模块的协调联动，其规则是在不断增加和删除的；并且随着网络规模的不断增大，分类粒度越来越细化，规则数目从千级上升为百万级，这些算法的空间复杂度无法满足要求。

发明内容

本发明所要解决的技术问题是提供一种面向大规模包分类规则集的规则冲突检测方法及系统，用于解决现在技术中规则冲突算法存在的不足。

本发明解决上述技术问题的技术方案如下：一种面向大规模包分类规则集的规则冲突检测方法，包括：

步骤1，创建远程规则接收服务，接收并解析规则；

步骤2，将解析后的规则按源IP和目的IP的前缀情况，划分为全前缀规则、非全前缀规则和无前缀规则；

步骤3，采用源IP-目的IP双层哈希表H_SIP-DIP或目的IP哈希表H_*-DIP组织全前缀规则集，并对应在H_SIP-DIP或H_*-DIP中进行规则的增加、删除或查询；

步骤4，采用源IP-目的IP双维Tire树T_SIP-T_DIP组织非全前缀规则集，并在T_SIP-T_DIP中进行规则的增加、删除或查询；

步骤5，采用链表L_*-*组织无前缀规则集，并在L_*-*中进行规则的增加、删除或查询；

步骤6，遍历全前缀规则集、非全前缀规则集和无前缀规则集中的每一个规则作为被检规则，检测与被检规则冲突的所有规则。

在上述技术方案的基础上，本发明还可以做如下改进。

进一步，所述步骤2具体包括：当解析后的规则的源IP和目的IP的前缀长度均为32时，或者当源IP和目的IP中的一个的前缀长度为0，另一个前缀长度为32时，将该规则划分为全前缀规则；当解析后的规则的源IP或目的IP的前缀长度在1-31之间时，将该规则划分为非全前缀规则；当解析后的规则的源IP和目的IP的前缀长度均为0时，将该规则划分为无前缀规则。

进一步，所述步骤3具体包括：若全前缀规则的源IP和目的IP的前缀长度均为32，或源IP前缀长度为32，目的IP的前缀长度为0，采用源IP-目的IP双层哈希表H_SIP-DIP组织全前缀规则集，并在H_SIP-DIP中进行规则的增加、删除或查询；若全前缀规则的源IP的前缀长度为0，且目的IP的前缀长度为32，采用目的IP双层哈希表H_*-DIP组织全前缀规则集，并在H_*-DIP中进行规则的增加、删除或查询。

进一步，所述H_SIP-DIP分为位于上层的一个源IP哈希表H_SIP和位于源IP哈希表H_SIP下的多个目的IP哈希表H_DIP，且所述在H_SIP-DIP中进行规则的增加具体包括：

步骤3A1，通过待增加规则的源IP在H_SIP中查找是否存在与该源IP对应的节点，若不存在则在H_SIP中添加相应节点，创建该节点下的目的IP哈希表H_DIP，再执行步骤3A2，若存在则直接得到该节点下的目的IP哈希表HDIP，并执行步骤3A2；

步骤3A2，通过待增加规则的目的IP在H_DIP中查找是否存在与该目的IP对应的节点，若不存在则在H_DIP中添加相应节点，并创建该节点下的规则集合S_SIP-DIP，再执行步骤3A3，若存在则直接获得该节点下的规则集合S_SIP-DIP，并执行步骤3A3；

步骤3A3，在S_SIP-DIP中查找是否有待增加规则存在，若不存在，则将待增加规则加入到S_SIP-DIP中，否则结束整个流程。

进一步，所述在H_*-DIP中进行规则的增加具体包括：

步骤3B1，通过待增加规则的目的IP在H_*-DIP中查找是否存在与该目的IP对应的节点，若不存在则在H_*-DIP添加相应节点，并创建该节点下的规则集S_*-DIP，再执行步骤3B2，否则直接获得该节点下的规则集S_*-DIP，并执行步骤3B2；

步骤3B2，在S_*-DIP中查找是否有待增加规则存在，若不存在，则将待增加规则加入到S_*-DIP中，否则结束整个流程。

进一步，所述T_SIP-T_DIP分为源IP树T_SIP和目的IP树T_DIP，所述在T_SIP-T_DIP中进行规则的增加具体包括：

步骤4A1，通过待增加规则的源IP在T_SIP中查找是否存在与该源IP对应的节点，若不存在则在T_SIP中添加相应节点，并创建该节点下的规则集S_SIP，再执行步骤4A2，否则直接获得该节点下的规则集S_SIP，并执行步骤4A2；

步骤4A2，在S_SIP中查找是否有待增加规则存在，若不存在，则将待增加规则加入到S_SIP中，否则结束整个流程。

进一步，所述T_SIP-T_DIP分为源IP树T_SIP和目的IP树T_DIP，所述在T_SIP-T_DIP中进行规则的增加具体包括：

步骤4B1，通过待增加规则的目的IP在T_DIP中查找是否存在与该目的IP对应的节点，若不存在则在T_DIP中添加相应节点，并创建该节点下的规则集S_DIP，再执行步骤4B2，否则直接获得该节点下的规则集S_DIP，并执行步骤4B2；

步骤4B2，在S_DIP中查找是否有待增加规则存在，若不存在，则将待增加规则加入到S_DIP中，否则结束整个流程。

进一步，所述步骤5中在L*-*中进行规则的增加具体包括：在L_*-*中遍历所有规则，查找是否存在待增加规则，若存在，则规则增加失败；若不存在，则待增加规则加入到L_*-*中。

进一步，所述步骤6中遍历全前缀规则集的每一个规则作为被检规则时，包括遍历H_SIP-DIP中的规则作为被检规则和遍历H_*-DIP中的规则作为被检规则。

进一步，当遍历H_SIP-DIP中的规则作为被检规则时，步骤6具体包括：

步骤6A1，遍历被检规则所处节点的规则集S_SIP-DIP中的所有规则，找出冲突规则；

步骤6A2，用被检规则的目的IP，在H_*-DIP哈希表中查找到与该目的IP相对应的节点，若存在，则遍历该节点的规则集，找出冲突规则，否则执行步骤6A3；

步骤6A3，找出被检规则在非全前缀规则集和无前缀规则集中的冲突规则。

进一步，所述步骤6A3中找出被检规则在非全前缀规则集中的冲突规则具体包括：

步骤A，用被检规则的源IP在T_SIP树上做最长前缀匹配，找到与源IP相对应的节点，再对该节点和其所有父节点上的规则集做并集；

步骤B，用被检规则的目的IP在T_DIP树上做最长前缀匹配，找到与目的IP相对应的节点，对该节点及其所有父节点上的规则集做并集；

步骤C，取步骤A和步骤B获得的两个并集的交集，遍历该交集中的规则，找出冲突规则。

进一步，当遍历H_*-DIP中的规则作为被检规则时，步骤6具体包括：

步骤6B1，遍历被检规则所处节点的规则集S_*-DIP中的所有规则，找出冲突规则；

步骤6B2，找出被检规则在非全前缀规则集和无前缀规则集中的冲突规则。

进一步，所述步骤6B2中找出被检规则在非全前缀规则集中的冲突规则具体包括：用被检测规则的目的IP在T_DIP树上做最长前缀匹配，找到与目的IP相对应的节点，对该节点及其所有父节点上的规则集做并集，遍历该并集中的规则，找出冲突规则。

进一步，当遍历T_SIP-T_DIP中的规则作为被检规则时，步骤6具体包括：

步骤6C1，对被检规则R在T_SIP树上所在的节点及所有父节点和子树上的规则集做并集；

步骤6C2，通过被检规则的目的IP在T_DIP树上做最长前缀匹配，找到与目的IP相对应的节点，对该节点及其所有父节点和子树上的规则集做并集；

步骤6C3，对步骤6C1和步骤6C2的两个并集做交集；

步骤6C4，遍历步骤6C3获得的交集中的规则，找出冲突规则；

步骤6C5，遍历L_*-*中的所有规则，找出所有冲突规则。

进一步，当遍历L_*-*的规则作为被检规则时，步骤6具体包括：采用顺序检测算法遍历无前缀规则集中的所有规则，找出所有冲突规则。

本发明的技术方案还包括一种面向大规模包分类规则集的规则冲突检测系统，包括：

规则接收服务接口，用于创建远程规则接收服务，接收并解析规则；

规则预处理模块，其连接所述规则接收服务接口，用于将解析后的规则按源IP和目的IP的前缀情况，划分为全前缀规则、非全前缀规则和无前缀规则；

全前缀规则集处理模块，其连接所述规则预处理模块，用于采用源IP-目的IP双层哈希表H_SIP-DIP或目的IP哈希表H_*-DIP组织全前缀规则集，并对应在H_SIP-DIP或H_*-DIP中进行规则的增加、删除或查询；

非全前缀规则集处理模块，其连接所述规则预处理模块，用于采用源IP-目的IP双维Tire树T_SIP-T_DIP组织非全前缀规则集，并在T_SIP-T_DIP中进行规则的增加、删除或查询；

无前缀规则集处理模块，其连接所述规则预处理模块，用于采用链表L_*-*组织无前缀规则集，并在L_*-*中进行规则的增加、删除或查询；

冲突检测模块，其与所述全前缀规则集处理模块、非全前缀规则集处理模块和无前缀规则集处理模块均相连，用于遍历H_SIP-DIP、H_*-DIP、T_SIP-T_DIP和L_*-*中的每一个规则作为被检规则，检测与被检规则冲突的所有规则。

本发明的有益效果是：本发明公开了一种面向大规模包分类规则集的规则冲突检测方法及系统，其积极效果体现在以下方面：1)冲突检测速度较快。对于全前缀规则，不用复杂的数据结构而是采用哈希表，将复杂的冲突检测转化成一到两次精确匹配，降低时间复杂度；对于非全前缀规则，采用trie树结构组织规则，将相互冲突的规则组织在同一路径和子树中，减少遍历的次数，降低时间复杂度；2)可支持百万级的规则集。通过将规则按照前缀情况进行划分，减少了占规则集比例较大的全前缀规则对trie树的空间增加；3)支持实时增量更新，所述三种数据结构都具有线性时间复杂度的增量更新；4)能在规则冲突检测的过程中添加规则。

附图说明

图1为本发明所述规则冲突检测方法的流程示意图；

图2为本发明实施例中向H_SIP-DIP中添加规则的流程示意图；

图3为本发明实施例中向H_*-DIP中添加规则的流程示意图；

图4为本发明实施例中向T_SIP-DIP中添加规则的流程示意图；

图5为本发明实施例中遍历H_SIP-DIP中的规则作为被检规则的处理流程图；

图6为本发明实施例中遍历H_*-DIP中的规则作为被检规则的处理流程图；

图7为本发明实施例中遍历遍历T_SIP中的规则作为被检规则的处理流程图；

图8为本发明所述规则冲突检测系统的结构示意图。

具体实施方式

以下结合附图对本发明的原理和特征进行描述，所举实例只用于解释本发明，并非用于限定本发明的范围。

根据规则源IP分量和目的IP分量的前缀情况将规则划分为三种：全前缀规则，非全前缀规则和无前缀规则。当解析后的规则的源IP和目的IP的前缀长度均为32时，或者当源IP和目的IP中的一个的前缀长度为0，另一个前缀长度为32时，将该规则划分为全前缀规则；当解析后的规则的源IP或目的IP的前缀长度在1-31之间时，将该规则划分为非全前缀规则；当解析后的规则的源IP和目的IP的前缀长度均为0时，将该规则划分为无前缀规则。本实施例中用源IP-目的IP双层哈希表H_SIP-DIP存储和哈希表H_*-DIP存储全前缀规则，若全前缀规则的源IP和目的IP的前缀长度均为32，或源IP前缀长度为32，目的IP的前缀长度为0，采用源IP-目的IP双层哈希表H_SIP-DIP；若全前缀规则的源IP的前缀长度为0，且目的IP的前缀长度为32，采用目的IP双层哈希表H_*-DIP；用双维Trie树T_SIP-DIP存储非全前缀规则；用链表L_*-*存储无前缀规则。

以上四个表的数据结构如下描述：

(1)H_SIP-DIP是一个源IP-目的IP双层哈希表，分为位于上层的一个源IP哈希表H_SIP和位于源IP哈希表H_SIP下的多个目的IP哈希表H_DIP。源IP哈希表H_SIP以源IP为key，每个节点维护一个以目的IP为key的目的IP哈希表H_DIP。H_SIP中的每个节点N_dip，维护一个规则集合S_SIP-DIP，其中的规则R为<sip,dip,SPORT,DPORT,PROTO>形式。根据现有技术的研究，规则集中具有相同sip和dip的规则的数目不大于20个，所以集合S_SIP-DIP用链表存储。

(2)H_*-DIP是一个以目的IP为key的哈希表，H_*-DIP中的每个节点N_dip维护一个规则集合S_*-dip。S_*-dip用链表存储，其中的规则R为<*，dip，SPORT,DPORT,PROTO>形式，*为通配符，表示源IP可以是任意值，下文中涉及的通配符均类似于此。

(3)T_SIP-TDIP是两个Trie树，T_SIP是用规则的源IP地址建立的Trie树，T_DIP是用规则的目的地址建立的Trie树。对于T_SIP树上的节点N_sip，维护一个源IP分量等于sip的规则集合；对于T_DIP树上的节点N_dip，维护一个目的IP分量等于dip的规则集合。

(4)L_*-*是一个链表表，其中的规则R为<*，*，SPORT,DPORT,PROTO>形式。

如图1所示，本实施例涉及一种面向大规模包分类规则集的规则冲突检测方法，包括：

步骤1，创建远程规则接收服务，接收并解析规则；

步骤2，将解析后的规则按源IP和目的IP的前缀情况，划分为全前缀规则、非全前缀规则和无前缀规则；

步骤3，采用源IP-目的IP双层哈希表H_SIP-DIP或目的IP哈希表H_*-DIP组织全前缀规则集，并对应在H_SIP-DIP或H_*-DIP中进行规则的增加、删除或查询；

步骤4，采用源IP-目的IP双维Tire树T_SIP-T_DIP组织非全前缀规则集，并在T_SIP-T_DIP中进行规则的增加、删除或查询；

步骤5，采用链表L_*-*组织无前缀规则集，并在L_*-*中进行规则的增加、删除或查询；

步骤6，遍历全前缀规则集、非全前缀规则集和无前缀规则集中的每一个规则作为被检规则，检测与被检规则冲突的所有规则。

可知，主要包括有增加规则和检测冲突规则两部分。

一、增加规则

下面以一个待增加规则R＝<sip,dip,sport,dport,proto,op>为例说明如何进行规则的增加。

(一)如图2所示，在H_SIP-DIP中进行规则的增加具体包括：

步骤3A1，通过待增加规则的源IP在H_SIP中查找是否存在与该源IP对应的节点N_sip，若N_sip不存在则在H_SIP中添加相应节点N_sip，并创建节点N_sip下的目的IP哈希表H_DIP，再执行步骤3A2，若存在则直接获得N_sip下的目的IP哈希表H_DIP，并执行步骤3A2；

步骤3A2，通过待增加规则的目的IP在H_DIP中查找是否存在与该目的IP对应的节点N_dip，若N_dip不存在则在H_DIP中添加相应节点N_dip，并创建目的IP对应的节点N_dip下的规则集合S_SIP-DIP，再执行步骤3A3，若存在则直接获得N_dip下的规则集合S_SIP-DIP，并执行步骤3A3；

步骤3A3，在S_SIP-DIP中通过比较剩余四元组<sport,dport,proto,op>的值来遍历查找规则R是否存在，若不存在，则将待增加规则R加入到S_SIP-DIP中，否则结束整个流程。

(二)如图3所示，在H_*-DIP中进行规则的增加具体包括：

步骤3B1，通过待增加规则的目的IP在H_*-DIP中查找是否存在与该目的IP对应的节点N_dip，若N_dip不存在则在H_*-DIP添加相应节点N_dip，并创建节点N_dip下的规则集S_*-DIP，再执行步骤3B2，否则直接获得节点N_dip下的规则集S_*-DIP，并执行步骤3B2；

步骤3B2，在S_*-DIP中通过比较剩余四元组<sport,dport,proto,op>的值来遍历查找规则R是否存在，若不存在，则将待增加规则R加入到S_*-DIP中，否则结束整个流程。

(三)如图4所示，在T_SIP-T_DIP中进行规则的增加有两种并行执行的方式，第一种方式如步骤4A1至步骤4A2所示，包括：

步骤4A1，通过待增加规则的源IP在T_SIP中查找是否存在与该源IP对应的节点N_sip，若N_sip不存在则在T_SIP中添加相应节点N_sip，并创建该节点N_sip下的规则集S_SIP，再执行步骤4A2，否则直接获得该节点N_sip下的规则集S_SIP，并执行步骤4A2；

步骤4A2，在S_SIP中查找是否有待增加规则存在，若不存在，则将待增加规则加入到S_SIP中，否则结束整个流程。

第二种方式如步骤4B1至步骤4B2所示，具体包括：

步骤4B1，通过待增加规则的目的IP在T_DIP中查找是否存在与该目的IP对应的节点N_dip，若N_dip不存在则在T_DIP中添加相应节点N_dip，并创建该节点N_dip下的规则集S_DIP，再执行步骤4B2，否则直接获得该节点N_dip下的规则集S_DIP，并执行步骤4B2；

步骤4B2，在S_DIP中查找是否有待增加规则存在，若不存在，则将待增加规则加入到S_DIP中，否则结束整个流程。

(四)在L_*-*中进行规则的增加具体包括：在L_*-*中遍历所有规则，查找是否存在待增加规则，若存在，则规则增加失败；若不存在，则待增加规则加入到L_*-*中。

二、冲突规则检测

进行冲突检测的基本原理是：对于每一个被检规则R，都维护一个冲突规则集S_C(R)，每找到一个冲突规则R_c，将R_c加入到S_C(R)中，并且将R加入到S_C(R_c)中。

(一)如图5所示，遍历H_SIP-DIP中的规则作为被检规则R＝<sip,dip,sport,dport,proto,op>。

1)遍历所处节点的规则集S_SIP-DIP中的所有规则，找出冲突规则，加入到S_c(R)中。

2)用被检规则的dip，在H_*-DIP表中查找到相应节点N_dip，若N_dip不存在，则遍历该节点的规则集，找出冲突规则,加入到S_c(R)中。

3)找出被检规则在非全前缀规则集中的冲突规则：用sip在T_SIP树上做最长前缀匹配，找到相应的节点N_sip’，再对N_sip’和其所有父节点上的规则集做并集，得到S_c(R_sip)；用dip在T_DIP树上做最长前缀匹配，找到相应的节点N_dip’，对N_dip’、所有父节点上的规则集做并集，得到S_c(R_dip)；再对S_c(R_sip)和S_c(R_dip)做交集，得到S_c(R_sip-dip)，遍历S_c(R_sip-dip)中的规则，找出冲突规则，加入到S_c(R)中。

4)遍历L_*-*中的所有规则，找出所有冲突规则，加入到S_c(R)中。

(二)如图6所示，遍历H_*-DIP中的规则作为被检规则R＝<*,dip,sport,dport,proto,op>。

1)遍历所处节点的规则集S_*-DIP中的所有规则，找出冲突规则,加入到S_c(R)中。

2)找出被检规则在非全前缀规则集中的冲突规则：用dip在T_DIP树上做最长前缀匹配，找到相应的节点N_dip’，对N_dip’、所有父节点上的规则集做并集，得到S_c(R_dip)，遍历S_c(R_dip)中的规则，找出冲突规则，加入到S_c(R)中。

3)遍历L_*-*中的所有规则，找出所有冲突规则，加入到S_c(R)中。

(三)如图7所示，遍历T_SIP树中的规则作为被检规则R＝<sip,dip,sport,dport,proto,op>。

1)R在T_SIP树上所在的节点为N_sip，对N_sip、其所有父节点和子树上的规则集做并集，得到S_c(R_sip)。若sip为*，则S_c(R_sip)为全集。

2)用dip在T_DIP树上做最长前缀匹配，找到相应的节点N_dip。对N_dip、其所有父节点和子树上的规则集做并集，得到S_c(R_dip)。若dip为*，则S_c(R_dip)为全集。

3)对S_c(R_sip)和S_c(R_dip)做交集，得到S_c(R_sip-dip)。

4)遍历S_c(R_sip-dip)中的规则，找出冲突规则，加入到S_c(R)中。

5)遍历L_*-*中的所有规则，找出所有冲突规则，加入到S_c(R)中。

(四)遍历L_*-*中的规则作为被检规则R＝(*,*,sport,dport,proto,op)，采用顺序检测算法遍历无前缀规则集中的所有规则，找出所有冲突规则，加入到S_c(R)中。

(五)对于S_c(R)不为空的规则R，将S_c(R)写入报表文件中。

如图8所示，本实施例还提供了一种面向大规模包分类规则集的规则冲突检测系统，包括：

规则接收服务接口，用于创建远程规则接收服务，接收并解析规则；

规则预处理模块，其连接所述规则接收服务接口，用于将解析后的规则按源IP和目的IP的前缀情况，划分为全前缀规则、非全前缀规则和无前缀规则；

全前缀规则集处理模块，其连接所述规则预处理模块，用于采用源IP-目的IP双层哈希表H_SIP-DIP或目的IP哈希表H_*-DIP组织全前缀规则集，并对应在H_SIP-DIP或H_*-DIP中进行规则的增加、删除或查询；

非全前缀规则集处理模块，其连接所述规则预处理模块，用于采用源IP-目的IP双维Tire树T_SIP-T_DIP组织非全前缀规则集，并在T_SIP-T_DIP中进行规则的增加、删除或查询；

无前缀规则集处理模块，其连接所述规则预处理模块，用于采用链表L_*-*组织无前缀规则集，并在L_*-*中进行规则的增加、删除或查询；

冲突检测模块，其与所述全前缀规则集处理模块、非全前缀规则集处理模块和无前缀规则集处理模块均相连，用于遍历H_SIP-DIP、H_*-DIP、T_SIP-T_DIP和L_*-*中的每一个规则作为被检规则，检测与被检规则冲突的所有规则。

各模块的功能实现方法及细节与上述的规则冲突检测方法相同。以上所述仅为本发明的较佳实施例，并不用以限制本发明，凡在本发明的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。

Claims (10)

1.一种面向大规模包分类规则集的规则冲突检测方法，其特征在于，包括：

步骤1，创建远程规则接收服务，接收并解析规则；

步骤2，将解析后的规则按源IP和目的IP的前缀情况，划分为全前缀规则、非全前缀规则和无前缀规则；

步骤3，采用源IP-目的IP双层哈希表H_SIP-DIP或目的IP哈希表H_*-DIP组织全前缀规则集，并对应在H_SIP-DIP或H_*-DIP中进行规则的增加、删除或查询；

步骤4，采用源IP-目的IP双维Tire树T_SIP-T_DIP组织非全前缀规则集，并在T_SIP-T_DIP中进行规则的增加、删除或查询；

步骤5，采用链表L_*-*组织无前缀规则集，并在L_*-*中进行规则的增加、删除或查询；

步骤6，遍历H_SIP-DIP、H_*-DIP、T_SIP-T_DIP和L_*-*中的每一个规则作为被检规则，检测与被检规则冲突的所有规则。

2.根据权利要求1所述的规则冲突检测方法，其特征在于，所述步骤2具体包括：当解析后的规则的源IP和目的IP的前缀长度均为32时，或者当源IP和目的IP中的一个的前缀长度为0，另一个前缀长度为32时，将该规则划分为全前缀规则；当解析后的规则的源IP或目的IP的前缀长度在1-31之间时，将该规则划分为非全前缀规则；当解析后的规则的源IP和目的IP的前缀长度均为0时，将该规则划分为无前缀规则。

3.根据权利要求2所述的规则冲突检测方法，其特征在于，所述步骤3具体包括：若全前缀规则的源IP和目的IP的前缀长度均为32，或源IP前缀长度为32，目的IP的前缀长度为0，采用源IP-目的IP双层哈希表H_SIP-DIP组织全前缀规则集，并在H_SIP-DIP中进行规则的增加、删除或查询；若全前缀规则的源IP的前缀长度为0，且目的IP的前缀长度为32，采用目的IP哈希表H_*-DIP组织全前缀规则集，并在H_*-DIP中进行规则的增加、删除或查询。

4.根据权利要求1所述的规则冲突检测方法，其特征在于，当遍历H_SIP-DIP中的规则作为被检规则时，步骤6具体包括：

步骤6A1，遍历被检规则所处节点的规则集S_SIP-DIP中的所有规则，找出冲突规则；

步骤6A2，用被检规则的目的IP，在H_*-DIP哈希表中查找到与该目的IP相对应的节点，若存在，则遍历该节点的规则集，找出冲突规则，否则执行步骤6A3；

步骤6A3，找出被检规则在非全前缀规则集和无前缀规则集中的冲突规则。

5.根据权利要求4所述的规则冲突检测方法，其特征在于，所述步骤6A3中找出被检规则在非全前缀规则集中的冲突规则具体包括：

步骤A，用被检规则的源IP在T_SIP树上做最长前缀匹配，找到与源IP相对应的节点，再对该节点和其所有父节点上的规则集做并集；

步骤B，用被检规则的目的IP在T_DIP树上做最长前缀匹配，找到与目的IP相对应的节点，对该节点及其所有父节点上的规则集做并集；

步骤C，取步骤A和步骤B获得的两个并集的交集，遍历该交集中的规则，找出冲突规则。

6.根据权利要求1所述的规则冲突检测方法，其特征在于，当遍历H_*-DIP中的规则作为被检规则时，步骤6具体包括：

步骤6B1，遍历被检规则所处节点的规则集S_*-DIP中的所有规则，找出冲突规则；

步骤6B2，找出被检规则在非全前缀规则集和无前缀规则集中的冲突规则。

7.根据根据权利要求6所述的规则冲突检测方法，其特征在于，所述步骤6B2中找出被检规则在非全前缀规则集中的冲突规则具体包括：用被检测规则的目的IP在T_DIP树上做最长前缀匹配，找到与目的IP相对应的节点，对该节点及其所有父节点上的规则集做并集，遍历该并集中的规则，找出冲突规则。

8.根据权利要求1所述的规则冲突检测方法，其特征在于，当遍历T_SIP-T_DIP中的规则作为被检规则时，步骤6具体包括：

步骤6C1，对被检规则R在T_SIP树上所在的节点及所有父节点和子树上的规则集做并集；

步骤6C2，通过被检规则的目的IP在T_DIP树上做最长前缀匹配，找到与目的IP相对应的节点，对该节点及其所有父节点和子树上的规则集做并集；

步骤6C3，对步骤6C1和步骤6C2的两个并集做交集；

步骤6C4，遍历步骤6C3获得的交集中的规则，找出冲突规则；

步骤6C5，遍历L_*-_*中的所有规则，找出所有冲突规则。

9.根据权利要求1所述的规则冲突检测方法，其特征在于，当遍历L_*-*的规则作为被检规则时，步骤6具体包括：采用顺序检测算法遍历无前缀规则集中的所有规则，找出所有冲突规则。

10.一种面向大规模包分类规则集的规则冲突检测系统，其特征在于，包括：

规则接收服务接口，用于创建远程规则接收服务，接收并解析规则；

规则预处理模块，其连接所述规则接收服务接口，用于将解析后的规则按源IP和目的IP的前缀情况，划分为全前缀规则、非全前缀规则和无前缀规则；

全前缀规则集处理模块，其连接所述规则预处理模块，用于采用源IP-目的IP双层哈希表H_SIP-DIP或目的IP哈希表H_*-DIP组织全前缀规则集，并对应在H_SIP-DIP或H_*-DIP中进行规则的增加、删除或查询；

非全前缀规则集处理模块，其连接所述规则预处理模块，用于采用源IP-目的IP双维Tire树T_SIP-T_DIP组织非全前缀规则集，并在T_SIP-T_DIP中进行规则的增加、删除或查询；

无前缀规则集处理模块，其连接所述规则预处理模块，用于采用链表L_*-*组织无前缀规则集，并在L_*-*中进行规则的增加、删除或查询；

冲突检测模块，其与所述全前缀规则集处理模块、非全前缀规则集处理模块和无前缀规则集处理模块均相连，用于遍历H_SIP-DIP、H_*-DIP、T_SIP-T_DIP和L_*-*中的每一个规则作为被检规则，检测与被检规则冲突的所有规则。