一种基于空间排序的防火墙策略搜索方法、系统、终端及存储介质

一种基于空间排序的防火墙策略搜索方法、系统、终端及存储介质

　　技术领域

　　本发明涉及防火墙技术领域，具体涉及一种基于空间排序的防火墙策略搜索方法、系统、终端及存储介质。

　　背景技术

　　现有的防火墙策略搜索方法为：设防火墙上已有策略列表为P[0..N-1]，N为策略数；设待搜索策略为x；假设搜索的目标关系为包含关系：

　　步骤1：遍历列表P，取当前策略P[i]，比较策略x和策略P[i]的源地址，目的地址，目的端口及协议，判断P[i]和x的包含关系，如果P[i]包含x，则将P[i]保存在结果列表R中；

　　步骤2：返回列表R。

　　该搜索方法的算法的时间复杂度为O(N)，耗时较长。

　　发明内容

　　本发明要解决的技术问题在于，针对现有技术的上述缺陷，提供一种基于空间排序的防火墙策略搜索方法，以显著降低算法的时间复杂度，从而使得计算性能显著提升。

　　本发明是这样实现的，本发明提供的一种基于空间排序的防火墙策略搜索方法所采用的技术方案是：搜索的目标关系为包含关系，所述搜索方法包括以下步骤：

　　S1：遍历防火墙上已有的策略列表，获取所述策略列表的当前策略，将所述策略列表的当前策略的源地址、目的地址以及目的端口进行转换，转换后的所述源地址、所述目的地址以及所述目的端口构成三维空间的长方体；

　　S2：计算所述长方体的权重；

　　S3：结束所述策略列表的遍历，得到新策略列表，将所述新策略列表按照从大到小的顺序进行排序；

　　S4：按照所述步骤S1和S2，计算待搜索策略的权重；所述待搜索策略为外界输入的搜索策略；

　　S5：对所述新策略列表进行二分搜索，找到大于或等于所述待搜索策略的权重的最小值；

　　S6：从所述新策略列表中读取子策略列表，遍历所述子策略列表，获取所述子策略列表的当前策略，将所述待搜索策略的协议值、源地址、目的地址以及端口范围与所述子策略列表的当前策略的协议值、源地址、目的地址以及端口范围进行比较，如果所述待搜索策略的协议值、源地址、目的地址以及端口范围与所述子策略列表的当前策略的协议值、源地址、目的地址以及端口范围的比较结果为相等或包含关系，则将所述子策略列表的当前策略在所述策略列表中对应的策略保存到结果列表中；

　　S7：结束遍历，返回所述结果列表。

　　进一步地，所述策略列表为P[0..N-1]，N为策略数；所述策略列表的当前策略为P[i]，将P[i]的源地址转换为(Srcs，Srct)，记为将P[i]的目的地址转换为(Dsts，Dstt)，记为将P[i]的目的端口转换为(Ports，Portt)，记为所述源地址、所述目的地址以及所述目的端口构成三维空间的长方体表示为

　　<(SrcsDsts，Ports)，(SrcsDsts，Ports)>，记为ci。

　　进一步地，所述步骤S2的计算方法为：

　　所述长方体的权重为Wi，如果其中有一个向量的长度为0，则Wi为另外两个向量所构成的长方形的面积，如果其中两个向量的长度都为0，则Wi为剩下的向量的长度，如果三个向量的长度都为0，则Wi记为0，否则，Wi为ci的体积。

　　进一步地，所述新策略列表为w[0..N-1]，N为策略数。

　　进一步地，所述待搜索策略为x，所述待搜索策略的权重为Wx。

　　进一步地，所述待搜索策略的权重的最小值为Wy。

　　进一步地，所述子策略列表为W0-y，所述子策略列表的当前策略为Wj，所述结果列表为R。

　　本发明还包括一种搜索系统，所述搜索系统用于实现如上所述的一种基于空间排序的防火墙策略搜索方法，所述搜索系统包括存储单元、获取单元、计算单元、比较单元以及输出单元；

　　所述存储单元，用于存储如上所述的策略列表和新策略列表；

　　所述获取单元，用于获取如权利要求1所述的外界输入的待搜索策略；

　　所述计算单元，用于实现如上所述的步骤S1～S5；

　　所述比较单元，用于实现如上所述的步骤S6；

　　所述输出单元，用于将如上所述的结果列表输出。

　　本发明还包括一种终端，包括存储器、处理器以及存储在所述存储器中并可在所述处理器上运行的计算机程序，其特征在于，所述处理器执行所述计算机程序时实现如上所述的一种基于空间排序的防火墙策略搜索方法的步骤。

　　本发明还包括一种计算机可读存储介质，所述计算机可读存储介质存储有计算机程序，其特征在于，所述计算机程序被处理器执行时实现如上所述的一种基于空间排序的防火墙策略搜索方法的步骤。

　　与现有技术相比，本发明的有益效果在于：本搜索方法的算法时间复杂度仅为O(N/2+log2N)，使得现有搜索方法的算法时间复杂度O(N)大幅降低，从而显著提升了计算性能。

　　附图说明

　　为了更清楚地说明本发明实施例中的技术方案，下面将对实施例中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。

　　图1是本发明实施例提供的一种基于空间排序的防火墙策略搜索方法流程示意图。

　　图2是本发明实施例提供的一种搜索系统组成示意图。

　　上述附图中的标记为：1、搜索系统；101、存储单元；102、获取单元；103、计算单元；104、比较单元；105、输出单元。

　　具体实施方式

　　为了使本发明的目的、技术方案及优点更加清楚明白，以下结合附图及实施例，对本发明进行进一步详细说明。应当理解，此处所描述的具体实施例仅仅用以解释本发明，并不用于限定本发明。

　　本实施例的附图中相同或相似的标号对应相同或相似的部件；在本发明的描述中，需要说明的是，当元件被称为“固定于”另一个元件，它可以直接在另一个元件上或者也可以存在居中的元件。当一个元件被认为是“连接”另一个元件，它可以是直接连接到另一个元件或者可能同时存在居中元件需要理解的是，若有术语“上”、“下”、“左”、“右”等指示的方位或位置关系为基于附图所示的方位或位置关系，仅是为了便于描述本发明和简化描述，而不是指示或暗示所指的装置或元件必须具有特定的方位、以特定的方位构造和操作，因此附图中描述位置关系的用语仅用于示例性说明，不能理解为对本专利的限制，对于本领域的普通技术人员而言，可以根据具体情况理解上述术语的具体含义。

　　以下结合附图与具体实施例，对本发明的技术方案做详细的说明。

　　本发明提出的一种基于空间排序的防火墙策略搜索方法，较佳实施例如图1所示，搜索的目标关系为包含关系，本搜索方法包括以下步骤：

　　S1：遍历防火墙上已有的策略列表，获取策略列表的当前策略，将策略列表的当前策略的源地址、目的地址以及目的端口进行转换，转换后的源地址、目的地址以及目的端口构成三维空间的长方体；

　　S2：计算长方体的权重；

　　S3：结束策略列表的遍历，得到新策略列表，将新策略列表按照从大到小的顺序进行排序；

　　S4：按照步骤S1和S2，计算待搜索策略的权重；待搜索策略为外界输入的搜索策略；

　　S5：对新策略列表进行二分搜索，找到大于或等于待搜索策略的权重的最小值；

　　S6：从新策略列表中读取子策略列表，遍历子策略列表，获取子策略列表的当前策略，将待搜索策略的协议值、源地址、目的地址以及端口范围与子策略列表的当前策略的协议值、源地址、目的地址以及端口范围进行比较，如果待搜索策略的协议值、源地址、目的地址以及端口范围与子策略列表的当前策略的协议值、源地址、目的地址以及端口范围的比较结果为相等或包含关系，则将子策略列表的当前策略在策略列表中对应的策略保存到结果列表中；

　　S7：结束遍历，返回结果列表；

　　其中，搜索的目标关系为包含关系。

　　上述提供的一种基于空间排序的防火墙策略搜索方法，与现有技术相比，本搜索方法的算法时间复杂度仅为O(N/2+log2N)，使得现有搜索方法的算法时间复杂度O(N)大幅降低，从而显著提升了计算性能。

　　作为本发明的一种实施方式，策略列表为P[0..N-1]，N为策略数；策略列表的当前策略为P[i]，将P[i]的源地址转换为(Srcs，Srct)，记为将P[i]的目的地址转换为(Dsts，Dstt)，记为将P[i]的目的端口转换为(Ports，Portt)，记为源地址、目的地址以及目的端口构成三维空间的长方体表示为

　　<(Srcs，Dsts，Ports)，(Srcs，Dsts，Ports)>，记为ci。

　　作为本发明的一种实施方式，步骤S2的计算方法为：

　　长方体的权重为Wi，如果其中有一个向量的长度为0，则Wi为另外两个向量所构成的长方形的面积，如果其中两个向量的长度都为0，则Wi为剩下的向量的长度，如果三个向量的长度都为0，则Wi记为0，否则，Wi为ci的体积。

　　作为本发明的一种实施方式，新策略列表为W[0..N-1]，N为策略数。

　　作为本发明的一种实施方式，待搜索策略为x，待搜索策略的权重为Wx。

　　作为本发明的一种实施方式，待搜索策略的权重的最小值为Wy。

　　作为本发明的一种实施方式，子策略列表为W0-y，子策略列表的当前策略为Wj，结果列表为R。

　　具体地，本搜索方法的实现方式为：

　　设防火墙上已有策略列表为P[0..N-1]，N为策略数；设待搜索策略为x；假设搜索的目标关系为包含关系，则搜索步骤如下：

　　S1：遍历列表P，取当前策略P[i]，将P[i]的源地址转换为(Srcs，Srct)，记为将P[i]的目的地址转换为(Dsts，Dstt)，记为将P[i]的目的端口转换为(Ports，Portt)，记为构成三维空间的长方体<(Srcs，Dsts，Ports)，(Srcs，Dsts，Ports)>，记为ci；

　　S2：计算ci的权重，记为Wi，计算方法为：如果其中有一个向量的长度为0，则Wi为另外两个向量所构成的长方形的面积，如果其中两个向量的长度都为0，则Wi为剩下的向量的长度，如果三个向量的长度都为0，则Wi记为0，否则，Wi为ci的体积；

　　S3：结束列表P的遍历，得到列表W[0..N-1]，对w按照从大到小的顺序排序；

　　S4：按照步骤S1和S2的方法，计算策略x的权重Wx；

　　S5：对列表w进行二分搜索，找到大于或者等于Wx的最小值Wy；

　　S6：从w列表中取子列表W0-y，遍历W0-y，取当前策略Wj，对比策略x和策略Wj的协议值，源地址，目的地址及端口范围，如果相等或包含则将Wj在列表P中对应的策略保存到结果列表R中；

　　S7：结束遍历，返回结果列表R。

　　本发明还提出了一种搜索系统1，搜索系统1用于实现上述的搜索方法，如图2所示，搜索系统1包括存储单元101、获取单元102、计算单元103、比较单元104以及输出单元105；

　　存储单元101，用于存储策略列表和新策略列表；

　　获取单元102，用于获取外界输入的待搜索策略；

　　计算单元103，用于实现上述步骤S1～S5；

　　比较单元104，用于实现上述步骤S6；

　　输出单元105，用于将结果列表输出。

　　本发明还提出了一种终端，包括存储器、处理器以及存储在存储器中并可在处理器上运行的计算机程序，其特征在于，处理器执行计算机程序时实现上述搜索方法的步骤。

　　本发明还提出了一种计算机可读存储介质，计算机可读存储介质存储有计算机程序，其特征在于，计算机程序被处理器执行时实现上述搜索方法的步骤。

　　优选地，本发明涉及的所有计算机程序采用已有的、公开的、开源的程序代码编写实现；本领域的软件编程人员按照本发明实施例所述的技术方案可以非常容易的实现。

　　以上所述仅为本发明的较佳实施例而已，并不用以限制本发明，凡在本发明的精神和原则之内所作的任何修改、等同替换和改进等，均应包含在本发明的保护范围之内。