一种基于基因式的防火墙规则异常处理优化方法

摘要

本发明涉及网络安全技术领域，公开的一种基于基因式的防火墙规则异常优化处理方法，首先通过树分析的结果快速找出防火墙规则异常，针对树叶节点中有异常区域进行优化；优化的第一个步骤先计算各规则与树的节点面积，第二步骤是利用面积算法更新各规则面积，当规则面积计算结果为0时，表示该规则为不匹配规则，并予以删除；第三步骤使用基因算法将剩余规则进行区块编码，编码结束之后，将基因相同之规则进行选择或是复制，直到所有规则优化结束。本发明能够将会产生规则异常的情况降至最低，达到优化的目的并设计可视化功能，同时将冗余的规则剔除掉，达到规则异常优化之目的。减少规则异常的情况发生，及对于优化规则的效能进行评估。

说明书

技术领域

本发明涉及网络安全技术领域，尤其涉及一种基于基因式的防火墙规则异常处理优化方法。

背景技术

现今的网络已突破时间与空间的限制，为世界带来便利性，但所有事物都有一体两面，带来便利性的同时，也会发生一些安全上的隐忧。网络上的任意入侵攻击程序会让有心人士轻易破坏没有设置防护的网络或是设备；为避免此危害，网络防火墙是目前用来保护内部网络的设备之一，管理者设定防火墙管理政策(Firewall Policy)，正确对防火墙进行访问控制设定(Access Control Configuration)来防护内部网络避免来自外部的攻击。网络防火墙的保护措施是利用封包过滤(Packet filtering)方式，依据管理者订定的规则条件(Firewall rules)，将通过防火墙的封包进行检查，并依据规则的优先权(Order)加以比对，若符合设定的规则条件便执行处理行为(Action)，决定允许通过(Accept)或是丢弃(Drop)此封包。

防火墙有优先匹配(First Matching)特性，而当防火墙规则数目不断增加，大型企业防火墙通常有数万条以上的规则，管理者在制定防火墙规则政策时，容易产生规则互相抵触的情况，进而产生安全漏洞，此现象称为规则异常(Rule Anomaly)。防火墙规则异常有几种情况，通常依照规则之间的Action不同、分布范围与规则优先权分成五种：ShadowAnomaly、Redundancy Anomaly、Correlation Anomaly、Generalization Anomaly、NonAnomaly。

防火墙是网络中负责保护内部网络，为避免受到外界攻击之重要设备，防火墙中的规则设定与依序安排都需要谨慎的考虑与严谨的规划。因为防火墙的规则设定错误，会影响到网络上封包的管理出现漏洞，而造成网络安全的危险。因此，防火墙规则的布署变成一项困难与废时的工作。特别是大型企业的防火墙中，管理者需要根据当下流量的变化而变换防火墙中的规则设置。因此需要有效维护防火墙之策略安全。

防火墙规则的优化方式有许多种，第一种是改变规则之间的顺序，第二种则是移除多余的规则，以减少规则异常的部分。第一种在规则改变顺序时，若是没有仔细思考规则Action或是规则之间的作用影响，反而会造成更多的规则异常，举例来说，一个防火墙中有20条规则，其中有3条规则的比对成功机率较大，而这3条规则的顺序偏偏是防火墙中优先权最低的规则，当相关的封包进来防火墙，要进行条件比对时，必须将比对到最后一条规则才能比对成功，如此一来，会造成许多不必要的比对时间，但若是随意将规则的顺序更动，有可能会造成更多的防火墙规则异常。第二种是将多余规则移除，减少规则数量，以缩短封包的比对时间，多余的规则产生的异常情况包含Shadow Anomaly、Redundancy Anomaly。

防火墙规则优化可视为Set Covering Problem得一种特例，Set CoveringProblem是图形论里面一个很知名的问题，其定义在于给定全集U包含所有元素和n个集合，n个集合组合成1个集合为S，Set Covering Problem要找S中的最小子集合C，使得C子集合里的元素联集等于全集U里的元素。举例来说，有集合U＝{1,2,3,4,5}，S＝{S

发明内容

为克服现有技术的不足，本发明提供一种基于基因式的防火墙规则异常优化处理方法。利用增强型自适性规则异常关系树，快速找出规则异常的区域，并利用基因算法将有异常区域之规则进行删除，把产生规则异常情况降至最低，再来设计可视化功能，让管理者藉由图形，互相比较优化前后的过滤图情况，更加了解规则的过滤区域。

为实现上述发明目的，本发明采用如下技术方案：

一种基于基因式的防火墙规则异常优化处理方法，首先通过Enhanced-ARAR树分析的结果快速找出防火墙规则异常，针对树叶节点中有异常区域进行优化；优化的第一个步骤先计算各规则与Enhanced-ARAR树的节点面积，第二步骤是利用面积算法更新各规则面积，当规则面积计算结果为0时，表示该规则为不匹配规则，并予以删除；第三步骤使用基因算法将剩余规则进行区块编码，编码结束之后，将基因相同之规则进行选择或是复制，直到所有规则优化结束；其步骤如下：

1)、计算各规则面积与Enhanced-ARAR树节点面积，

在进行规则优化之前，先将规则表中分类成每一个接口中的input或是output；防火墙interface 0中input规则，在进行规则优化之前，先计算规则中每一条规则之面积，其算法为规则中的S

2)、删除不匹配规则

计算完各规则与Enhanced-ARAR树之节点面积后，通过下面流程，将所得到的规则总面积扣除规则存在树叶节点中不为第一条规则之节点面积，扫描完所有的树叶节点的所有规则后，当有规则的面积最后结果为0时，则删除该规则，同时删除Enhanced-ARAR树中存在的之规则；

第0000节点的R7不为第一条规则，因此规则总面积里R7之Total area扣除第0000节点中R7的面积；

第0001节点中，R3、R7不为该节点中的第一个规则，总面积里R3、R7的Totalarea扣除第0001节点中R3、R7的面积，当所有节点都扫描完之后，总面积里R8、R9的Total area为0，因此删除R8、R9，而其他规则的Total area皆不做任何变动，之后便完成更新规则面积；

3)、基因算法

上述删除不匹配规则之方法，是删除防火墙中的Shadow Rule，和Action相同，优先权较低，同时被包含的Redundancy Rule，至于若是要删除优先权较高，但被优先权低得规则包含的Redundancy Rule，则使用基因算法来删除，

基因算法(Genetic algorithms,GAs)，是一种用于搜寻近似最佳解的方法，基因算法中组成的元素有族群(population)、染色体(chromosomes)、基因(genetic)、与适应函数(fitness function)，分别介绍以下元素：

(1).族群：染色体组成的集合，初始族群是随机产生的；

(2).染色体：由基因编码组成的序列，编码方式为位串行(bitstring)，染色体代表一组完整的解，代表单一规则；

(3).基因：基因算法中的基本单位，编码过程有许多方式，二进制编码、实数编码、符号编码，代表规则的Action，若Action为Accept，基因设为1，反之设为0；

(4).适应函数：选择所需染色体的条件，就是环境中的“天择”，当适应函数数值越大表示染色体适应的程度越好；

基因算法依据这些元素，先确定染色体编码方式，而后随机产生族群，便完成族群初始化；再利用适应函数挑选出目前适合的个体；适合的个体再经由选择(selection)、交配(crossover)、突变(mutation)计算产生下一子代，直到设定的子代次数或是找到最佳解，满足这些终止条件才会停止演化；

其计算方式有三种，选择(selection)或复制(reproduction)、交配(crossover)、突变(mutation)，重复三种计算直到演化结束；

(1).选择或复制：复制或是选择较优良的染色体，并保留给下一代；

(2).交配：将两个挑选出的染色体，重新排列基因组合，产生出新的染色体；交配方式有三种：单点交配、双点交配、多点交配；

(3).突变：为偶然生发事件，发生机率很低；为某一条染色体的其中某些基因，基因值编码改变；交配方式有三种：单点突变、双点突变、多点突变；选择复制当作基因算法之计算；

a基因编码

在进行基因算法之前，须先做基因编码，编码方式是将S

b基因算法选择或复制

建立完基因编码之后，便开始针对优先权来选择染色体进行选择或复制的计算，若是遇到不相同染色体中的基因，便将两者的染色体保留，反之，若是遇到相同基因，则只复制优先权较低的染色体，删除优先权较高之染色体；

首先挑选到R0规则，R0规则在(11,00)、(11,01)有存在基因，所以比较(11,00)、(11,01)两个基因位置的编码；在(11,00)位置中R0与下一个基因，也就是R1基因比较，两条的规则基因不同，因此两个规则基因皆保留；因为(11,00)在已经比对完之后R0的基因保留，所以(11,01)中存在R0与R7的基因，这组基因是不需要比对了，最后R0规则被保留；

R0规则基因比较完之后，接着R1规则的基因比较；R1在(10,00)、(11,00)有存在基因，所以比较(10,00)、(11,00)中存在的基因；(10,00)中存在的基因有R1与R4的基因，R1与R4基因不相同，因此两个规则基因皆保留；而因为在(10,00)确定R1的基因已经被保留了，所以在(11,00)中存在R1与R7的基因，这组基因是不需要比对，最后R1规则被保留；

R1规则基因比较完之后，接着R2规则的基因比较，R2在(00,01)、(01,01)有存在基因，所以比较(00,01)、(01,01)中存在的基因，(00,01)中存在的基因有R2与R3的基因，R2与R3基因相同，但R3的优先权较低，因此保留R3的基因；而(01,01)中存在R2与R7的基因，R2与R7基因相同，但R7优先权较低，因此保留R7的基因，R2在(00,01)、(01,01)中的基因皆没有保留，因此R2规则就被删除；

R2删除完之后，依照优先权选到R3规则的基因比较；R3在(00,00)、(00,01)、(00,10)、(00,11)有存在基因，所以比较规则表(00,00)、(00,01)、(00,10)、(00,11)中的基因；(00,00)、(00,01)、(01,01)、(00,11)中存在的基因皆有R3与R7的基因，R3与R7基因相同，但R7的优先权较低，因此保留R7的基因；R3规则所有的基因都被淘汰，所以R3规则被删除；

重复上述步骤，直到选取至最后一条规则，便停止复制及选择，更新完的规则表，也就是产生的新子代；新的子代再依照刚刚上述算法重新操作直到找到最佳解或是设定的子代次数便停止演化。

由于采用如上所述的技术方案，本发明具有如下优越性

本发明则是诊断出属于Shadow Anomaly、Redundancy Anomaly，并针对这两个异常情况删除多余规则进行规则优化，在不更动整体过滤图情况下，将会产生规则异常的情况降至最低，并将属于Shadow Rule或是Redundancy Rule删除，达到优化的目的并设计可视化功能，将规则数据转换成流量空间过滤图，让管理者藉由过滤图，了解规则之间的影响范围，同时可以比较优化前与优化后的关系图，让管理者选择优化的情形。

本发明提出防火墙规则异常优化，是为了解决Set Covering Problem，将规则中的SIP与DIP化成流量过滤图，以利用户观察规则的分布范围与规则之间的重迭区域，再利用Enhanced-ARAR树为切割基准，将过滤图切割，可快速判断有规则异常的节点区域，接着利用异常区块之节点进行不匹配规则的删除，将永远不会被执行的规则删除；再将更新的规则表与Enhanced-ARAR树依照基因算法进行规则异常优化，将冗余的规则也剔除掉，达到规则异常优化之目的。

优化结果使用可视化功能，将优化前后之结果同时呈现，让使用者可一目了然优化前后比对，也可让使用者选择是否需优化，而非强制优化，达到使用者心目中的优化方式。而发明也比三种不同算法，在使用上，在时间处理上基因演法比较快，在结果呈现上也较两者算法来的准确，在各种因素考虑下，证明了基因算法之优化效能比Greedyalgorithm、Dynamic Programming来得好。

本发明通过研究动机，防火墙优化属于Set Covering Problem，建构在Enhanced-ARAR树基础上，使用基因算法减少规则异常的情况，通过系统开发环境与呈现可视化功能的结果，不同算法对于优化规则的评估效能。

附图说明

图1Enhanced-ARAR树切割结果图；

图2node_SIP切割编码图；

图3验算法时间比较图；

图4算法记忆体使用比较图；

图5算法过滤图比较图。

图6删除不匹配规则流程图。

具体实施方式

如图1至图6所示，一种基于基因式的防火墙规则异常优化处理方法，是在本系统上实现规则异常优化之方法，首先通过Enhanced-ARAR树分析的结果快速找出防火墙规则异常，针对树叶节点中有异常区域进行优化。优化的第一个步骤先计算各规则与Enhanced-ARAR树的节点面积，第二步骤是利用面积算法更新各规则面积，当规则面积计算结果为0时，表示该规则为不匹配规则，并予以删除。第三步骤使用基因算法将剩余规则进行区块编码，编码结束之后，将基因相同之规则进行选择或是复制，直到所有规则优化结束。

以下详细叙述如何使用防火墙异常的结果来优化防火墙规则。

1、计算各规则面积与Enhanced-ARAR树节点面积

在进行规则优化之前，先将规则表中分类成每一个接口中的input或是output。表1为防火墙interface 0中input规则表，在进行规则优化之前，先计算规则表中每一条规则之面积，其算法为规则中的S

表1防火墙interface 0中input原始规则表与总面积表

表2 Enhanced-ARAR树各节点面积与存在规则

2删除不匹配规则

计算完各规则与Enhanced-ARAR树之节点面积后，通过下面流程，将所得到的规则总面积扣除规则存在树叶节点中不为第一条规则之节点面积，扫描完所有的树叶节点的所有规则后，当有规则的面积最后结果为0时，则删除该规则，同时删除Enhanced-ARAR树中存在的之规则。如流程图6。

以规则表1与图1Enhanced-ARAR树为例，图1中第0000节点的R7不为第一条规则，因此表1规则总面积表里R7之Total area扣除第0000节点中R7的面积，第0001节点中，R3、R7不为该节点中的第一个规则，总面积表里R3、R7的Total area扣除第0001节点中R3、R7的面积，当所有节点都扫描完之后，总面积表里R8、R9的Totalarea为0，计算完的结果如表3所示。

表3规则面积表

因此删除R8、R9，而其他规则的Total area皆不做任何变动，之后便完成更新规则面积表，结果如表4所示。

表4.更新规则面积表

3基因算法

上述删除不匹配规则之方法，是删除防火墙中的Shadow Rule，和Action相同，优先权较低，同时被包含的Redundancy Rule，至于若是要删除优先权较高，但被优先权低得规则包含的Redundancy Rule，则使用基因算法来删除。

基因算法(Genetic algorithms,GAs)，是一种用于搜寻近似最佳解的方法，其方法根据自然界中「物竞天择，适者生存」的演化与淘汰机制所发展出来的算法。1975年，JohnH.Holland在其著作中Adaptation in Natural and Artificial Systems，依据生物进化的抽象概念，提出基因算法架构。

基因算法中组成的元素有族群(population)、染色体(chromosomes)、基因(genetic)、与适应函数(fitness function)，分别介绍以下元素：

(1).族群：染色体组成的集合，初始族群是随机产生的，在发明代表规则表。

(2).染色体：由基因编码组成的序列，编码方式为位串行(bitstring)，染色体代表一组完整的解，在本文代表单一规则。

(3).基因：基因算法中的基本单位，编码过程有许多方式，例如：二进制编码、实数编码、符号编码。在本文中是以二进制方式编码。代表规则的Action，若Action为Accept，基因设为1，反之设为0。

(4).适应函数：选择所需染色体的条件，就是环境中的「天择」，当适应函数数值越大表示染色体适应的程度越好。

基因算法依据这些元素，先确定染色体编码方式，而后随机产生族群，便完成族群初始化。再利用适应函数挑选出目前适合的个体。适合的个体再经由选择(selection)、交配(crossover)、突变(mutation)计算产生下一子代，直到设定的子代次数或是找到最佳解，满足这些终止条件才会停止演化。

为了演化出更优良的后代，其计算方式有三种，选择(selection)或复制(reproduction)、交配(crossover)、突变(mutation)，重复三种计算直到演化结束。

(1).选择或复制：复制或是选择较优良的染色体，并保留给下一代。

(2).交配：将两个挑选出的染色体，重新排列基因组合，产生出新的染色体。交配方式有三种：单点交配、双点交配、多点交配。

(3).突变：为偶然生发事件，发生机率很低。为某一条染色体的其中某些基因，基因值编码改变。交配方式有三种：单点突变、双点突变、多点突变。在本文当中，选择复制当作基因算法之计算。

3.1基因编码

a基因编码

在进行基因算法之前，须先做基因编码，编码方式是将S

编码结束之后，各规则便在存在的编码位置填上基因，而定义为若试规则Action为Accept基因设为1，反之为0。直到最后一条规则填完，便完成规则编码表。

表5.规则编码表

b基因算法选择或复制

建立完基因编码之后，便开始针对优先权来选择染色体进行选择或复制的计算，若是遇到不相同染色体中的基因，便将两者的染色体保留，反之，若是遇到相同基因，则只复制优先权较低的染色体，删除优先权较高之染色体。

从表5中的规则编码表中，首先挑选到R0规则，R0规则在(11,00)、(11,01)有存在基因，所以比较(11,00)、(11,01)两个基因位置的编码。在(11,00)位置中R0与下一个基因，也就是R1基因比较，两条的规则基因不同，因此两个规则基因皆保留。因为(11,00)在已经比对完之后R0的基因保留，所以(11,01)中存在R0与R7的基因，这组基因是不需要比对了，最后R0规则被保留，产生的规则表不变。

R0规则基因比较完之后，接着R1规则的基因比较。R1在(10,00)、(11,00)有存在基因，所以比较(10,00)、(11,00)中存在的基因。(10,00)中存在的基因有R1与R4的基因，R1与R4基因不相同，因此两个规则基因皆保留；而因为在(10,00)确定R1的基因已经被保留了，所以在(11,00)中存在R1与R7的基因，这组基因是不需要比对，最后R1规则被保留，产生的规则表不变。

R1规则基因比较完之后，接着R2规则的基因比较。R2在(00,01)、(01,01)有存在基因，所以比较(00,01)、(01,01)中存在的基因。(00,01)中存在的基因有R2与R3的基因，R2与R3基因相同，但R3的优先权较低，因此保留R3的基因；而(01,01)中存在R2与R7的基因，R2与R7基因相同，但R7优先权较低，因此保留R7的基因。R2在(00,01)、(01,01)中的基因皆没有保留，因此R2规则就被删除，规则表变动结果如表6所示。

表6删除R2变动后规则表

R2删除完之后，依照优先权选到R3规则的基因比较。R3在(00,00)、(00,01)、(00,10)、(00,11)有存在基因，所以比较规则表(00,00)、(00,01)、(00,10)、(00,11)中的基因。(00,00)、(00,01)、(01,01)、(00,11)中存在的基因皆有R3与R7的基因，R3与R7基因相同，但R7的优先权较低，因此保留R7的基因。R3规则所有的基因都被淘汰，所以R3规则被删除，便动后的规则表如表7所示。

表7删除R3之变动后规则表

依照此方式重复上述步骤，直到选取至最后一条规则，便停止复制及选择，更新完的规则表，也就是产生的新子代如表8所示。新的子代再依照刚刚上述算法重新操作直到找到最佳解或是设定的子代次数便停止演化。

表8新的子代规则表

4.功能实现

本发明是在高效率异常诊断系统上做功能扩充，是针对防火墙中的规则表进行优化。防火墙规则表呈现如表9所示。

表9.防火墙管理接口

5.算法比较与分析

防火墙规则优化为Set Covering Problem，而Greedy algorithm是常见解决SetCovering Problem的算法之一，Greedy algorithm得宗旨在于每一次的选择都采取当前状态下最有利的选择，从而希望结果是最好的算法。而Dynamic Programming则是常见的优化算法之一。

因此本发明Greedy algorithm、Dynamic Programming这三种方法优化的时间以及建立数据结构所需时间与内存使用量。

本发明使用的基因算法在时间执行上较Greedy algorithm、DynamicProgramming快，是因为Greedy algorithm要一条一条规则寻找，直到找到最多元素之规则为止，而且还要比对每一条规则是否有重复的元素，才会使Greedy algorithm得运行时间比较长，而Dynamic Programming必须找出每一条规则在每个面积阶段中最好的价值，再利用价值去寻找最佳的规则组合，因此在时间的执行上也较基因算法慢。时间比较结果如图3所示。

而内存方面，基因算法、Greedy algorithm与Dynamic Programming这三个算法都需要建立Enhanced-ARAR树，利用Enhanced-ARAR树的结果进行优化运算，因此使用的内存差不多相同。内存空间使用比较如图4所示。

图5为三种验算法四种过滤图比较结果，Greedy algorithm在执行优化算法时，因为并没有考虑规则优先权与其Action，在最后结果只选取R7一条规则，即使挑选当下状态最有利之结果，就以现实结果来看，是不可能会有只有1条规则的防火墙存在的，因此若是要使用Greedy algorithm来优化防火墙异常规则，就必须考虑更多因素。而DynamicProgramming在DP_order方法中有考虑优先权，但一样没有考虑到Action，在时间执行上较本方法慢，而且在优化规则异常结果中，Dynamic Programming算法所得出的结果改变了原始过滤图，在正确性上有改善的空间。