运用差分演化算法实现包匹配多层核心基的提取

2017-05-24王则林郝水侠

计算机应用 2017年3期

王则林，郝水侠

(1.南通大学杏林学院，江苏南通 226000； 2.南通大学计算机科学与技术学院，江苏南通 226000； 3.江苏师范大学数学与统计学院，江苏徐州 221116) (*通信作者电子邮箱sxhao@jsnu.edu.cn)

王则林1,2，郝水侠3*

针对网络防火墙、路由器等设备中包匹配的速度问题，提出运用差分演化算法实现包匹配多层核心基的提取。该算法运用多层基础基描述包的多层特征，在每层中分别运用差分演化算法进行比特基和实体基的提取，运用平均自信息和平均互信息量衡量基础基选择的优劣。这种方法可以根据规则库实际规模选择提取比特实体基的层数，非常适应规则库的增长。实验结果表明，所提算法在时间效率、空间效率方面相对于已有的递归数据流匹配算法和基于实数编码的差分演化的包匹配算法，综合性能最优。

包匹配；差分演化算法；平均自信息；平均互信息

在防火墙、路由器等网络设备中，包匹配的速度决定着网络性能。对于包匹配的研究许多学者提出了很多思路。大体可以分成两类：传统的方法[1-9]和基于智能处理的方法[10-12]。传统的方法在速度和内存消耗之间进行权衡，例如递归数据流匹配(Recursive Flow Classification, RFC)算法[8-9]，此方法在时间效率上目前比较理想，但内存消耗非常大，在高维大规模的情况下根本不现实；有的方法像分层智能分割(Hierarchical Intelligent Cuttings, HiCuts)算法[6]，网格特里树(Grid-of-Trie)[5]，时间、空间消耗比较均衡，但只适合于二维情况。这些传统方法目前都很难适应网络发展对包匹配速度的要求。基于智能的算法，在文献[10]中，虽然解决了包的高速匹配问题，但也只是考虑二维小规模的情况。在文献[11]中，运用实数进行编码，对差分演算法的交叉算子的参数进行了研究并且实验论证了此算法适合处理高维大规模问题，但是由于对变异算子的参数没有动态考虑以及变异算子本身的动态变化也没有考虑，这些因素造成算法的预处理时间不够理想。

包匹配是模式匹配的一种特殊应用领域，在这过去几年里，运用机器学习来进行目标识别方法中的特征提取逐渐成为研究热点。受此启发，本文提出运用差分演化算法去寻找每层的基础基，把各层的特征融合起来进行包匹配。

1 相关工作

包匹配是对每一个进入网络或主机的数据包进行扫描，并把它和规则库里数据包进行匹配，在规则库中寻找到相应数据包，并根据相应行为描述对进入的数据包进行相应处理。在核心服务器中相应规则数都比较大，而且随着网络硬件发展以及应用范围扩大，对网速要求也越来越高。光纤普及使各种核心硬件设备处理速度成为网络瓶颈，其中一个重要处理就是包匹配。当今互联网都要求核心设备以线速进行相应处理，这样包匹配工作就要求在大规模情况下线速处理。另外，在IPV6环境下，一个进入数据包根据它的目的IP地址、源IP地址、源端口、目的端口以及上层协议进行匹配，而且其中每个具体的维又是由多位二进制数组成。像源IP地址由128位二进制数组成。这样为了适应如今互联网的需求，包匹配必须是大规模多维线速包匹配。

传统包匹配算法有基于基本数据结构的算法、基于空间分割的算法、启发式算法、基于硬件的算法等。比较有代表性的具体算法有Hierarchical Tires(分层特里树)[2]、Set-pruning Trie(截枝特里树)[3]、Grid-of-Trie，改进的带路径压缩的扩展特里网格树(EGT-PC)[5]、HiCuts、超分层智能分割算法(HyperCuts)[7]、RFC和三态内容可访问存储器(Ternary Content Addressable Memory,TCAM)算法。这些算法有些是在时间和空间效率之间进行权衡，有些虽然在一般情况下性能很好，但在极端的情况下性能却急剧恶化，有些只适合低维、甚至一维的情况却无法适用于多维包匹配的现实要求。因为随着维数的增加，性能会指数恶化。总体而言，传统的算法都无法支持包的线速匹配。基于智能的算法有基于蚁群优化(Ant Colony Optimization, ACO)的算法[9]、基于差分演化(Differential Evolution, DE)的优化算法以及基于神经网络的算法。基于ACO算法解决组合优化问题的优势没有得到充分体现, 此算法在处理包时需要对规则进行排序，导致时间和空间消耗都比较大。另外时间消耗随规则数的增长显著增长，从而也不太适合大规模的规则库的匹配。基于DE的算法当数据的特征和它们的映射不成线性关系时很难计算出最优或近优的α和β组合，通过演化代数对演化进行限制会造成映射的数据空间的分布性能很差。基于神经网络的算法，预处理时间相比较没有优势，说明很难找到关键基础基。本文受深度学习的启发，提出寻找多层关键基础基的思想，在每层关键基础基上对进入的数据包进行识别，在比特基的提取时，对数据包进行分块局部处理。

2 多层基础基的提取

2.1 基本思想

首先把进入的数据包看作一串二进制流，如图1所示：找到这296位除去8位协议的基础基，就是那关键N位的位点，使规则库中规则达到平均自信息最大。这些位点定义为比特基。

图1 数据包的流格式

Fig. 1Streamformatfordatapackets

在比特基提取过程中，为了统一化、简化处理本文引入图像处理中常用的局部块基思想，如图2。把296位以16位为单位分为18个局部块。分别找到每个局部块中的比特基，进一步进行整合，最后提取到整个288位的比特基。各个局部块假设彼此独立。

图2 比特基提取过程

把图1中的128位源IP地址分为三个部分，见图2，即45位全网ID，16位子网ID，64位接口ID，同样目的IP地址也分为图3所示的三部分。

源端口分为知名端口和动态端口两部分，而且知名端口的范围是0～1023。同样把目的端口也分为两部分，如图4所示。

图3IPV6全球单播地址格式图4 端口分割

Fig. 3IPV6globalunicastaddressformatFig. 4Portsegmentation

这样源IP地址的三部分、目的IP地址的三部分、源端口的两部分、目的端口的两部分共10部分分别视为不可分割的整体。找出10部分中的基础基。在对10部分实体基提取时，染色体含有8个基因，对于超过10位的实体，采取随机选择实体中的8位，对于不足8位，像知名端口部分，低位补零。最后把10个部分的实体基进行整合，使规则库中的平均自信息达到最大。这些基础基定义为实体基。

对进入数据包进行比特基提取，然后进行实体基提取。这两个提取过程组成一层基的提取。定义为比特实体基提取。

可根据解决问题的实际规模来选择用几层比特实体基。可以设置阈值λ，当分类中的规则数规模小于λ，就不再增加层进行比特实体基提取。

2.2 差分演化算法

2.2.1 差分演化算法的现状

每层中比特基和实体基提取都是采用差分演化算法(DE)。差分演化算法是一种高效且简单的优化算法，因其简单易用，鲁棒性能良好，被成功运用于各个领域。近年很多学者对DE算子以及参数进行改善。这些改善是为了在某种程度上去平衡算法的勘探和开采能力。目前改善算法可以分为两类:1)融合其他的技术改进DE算子，从而改善算法收敛性能，如，文献[13]提出使用反向学习初始化种群和产生反向解的反向差分算法；也有考虑相异的变异策略具有相异性能，如，文献[14]提出了一种多变异策略自适应差分算法；另外2013年，文献[15]提出应用精英反向策略去改善DE算子，提高算法的收敛速度。2)考虑传统差分算法对缩放因子和杂交概率两个参数的敏感性，如，文献[16-17]利用演化过程中的反馈信息来自适应调整参数的自适应差分算法；文献[17]把参数编码到个体中同时进行进化的参数自适应差分算法。2011年，Wang等[18]同时考虑变异策略敏感性和参数敏感性问题，在构建策略知识库和参数知识库的基础上，提出一种随机选取策略和参数组合差分演化算法。如上简述，研究人员已对DE进行了大量研究，并且也取得了很多重要的成果。

2.2.2 本文的基本思想

本文采用精英反向学习演化算法实现比特基、实体基的提取，前者采用二进制编码，后者采用实数编码，比特基提取时染色体的位数为16位，实体基提取时染色体位数为8位。

变异算子变异算子是差分演化算法产生新个体的重要方式，它利用群体中不同个体之间差异来对相应个体进行扰动，因而就必须采用不同策略来选择相异个体，而且对两个相异个体产生的距离，缩放因子的取值采取不同策略。这两个问题都是差分演化研究的热点。对相异个体选择,本文采用“DE/rand/1”。

(1)

交叉算子

(2)

Cr=1-Ecur

(3)

其中Ecur为被处理的规则库的信息熵。

选择算子

(4)

精英反向演化算法，要针对精英个体，求出精英的反向个体，思想就是平衡勘探和开采能力，增强多样性，增强寻找全局最优解的能力，避免早熟。在当前群中找出精英个体，也就是最优个体，比特基提取时根据下面的式(5)求出精英反向个体：

(5)

实体基提取时根据下面的式(6)求出精英反向个体：

(6)

其中：Xe(xe,1,xe,2,…,xe,D)为D维的精英个体。k取[0，1]的随机数，μi，li为xe,i的上下界。

适应值函数设计

在比特基提取时，如果提取的比特基能把规则库中的规则分成两类，并且两类中的规则数目近似，此时的平均自信息最大，系统也就处于一种均衡状态。

假设规则库中的规则被分成N类，每类中规则数分别为(m1,m2,…,mN)，此时规则库的平均自信息按式(7)进行计算:

(7)

在比特基提取中，当进行局部块整合时，依据下面的公式计算平均自信息：

(8)

其中：M为规则库规则总数目。

在实体基提取过程中，必须比较它相对于比特基的信息增长量，运用平均互信息量来衡量，公式如式(9)～(11)：

(9)

(10)

N1、N2分别为比特基中类的数目以及实体基中的类的数目。X为比特基中的类变量，Y为实体基类变量。式(9)和(10)分别站在不同的角度观察信息量的平均变化。

(11)

2.3 算法框架

首先对规则库中的规则进行预处理，根据8位协议的值对数据进行分类。规则库中的规则以8位协议的值为6的TCP和17的UDP居多，其次为1的ICMP和2的IGMP以及为89的OSPF，研究分析得出规则库中规则的8位协议TCP、UDP所占的比重可以让别的协议忽略不计。这样就可以根据8位协议把数据包分为三类TCP、UDP以及其他三类(值分别定义为：0，1，2)。

运用差分演化算法进行包匹配多层基础基提取的算法(DEMBBPM)如下：

fori=1：3

根据图1的8位协议对规则预处理

End for

k=0 (初始化层数)

while最大类规则数目大于阈值λ

k=k+1

fori=1 ：18

根据精英反向差分演化算法对i局部块进行比特基的提取

end for

10)

对18个局部块的比特基进行整合得出288位的比特基

11)

根据比特基对规则分类

12)

Fori=1:10

13)

对每一类进行实体基的提取

14)

End for

15)

对10个部分进行整合得到实体基

16)

针对实体基对规则进行分类

17)

求最大类规则数目

18)

end while

对进入数据包进行匹配：

提取数据包相关信息(赋值给结构数据的各个元素)

Fori=0:k

对进入的数据包的相应位和i层比特基进行位运算

对步骤3)的结果和i层实体基进行位运算

End for

在小于λ个规则的规则链中进行顺序搜索，如搜索到相应的规则，转7)，否则转8)

按规则中的行为对规则进行处理

拒绝处理，同时把此规则写入相应的文件

2.4 性能分析

运用差分演化算法进行包匹配多层基础基提取,虽然算法比较耗时耗空间，但是它只运行一次。在各层的比特基和实体基提取后。对进入的数据包，进行包匹配时，对进入的数据包的比特流和各个基础基进行与操作，寻找到小于λ的类，再按顺序进行匹配。

时间复杂度分析，进入的数据包在每层比特基与操作中，只需要比特位操作16次，在实体基的与操作中只需要比特位操作8次。这样每层比特实体基的匹配中只需要24次位操作，而比特实体基的层数小于logN，成功搜索到相应规则，需要再平均耗时λ/2单位，如不成功再耗时λ单位，故时间复杂度为O(26 logN+λ)即O(logN)。

每次比特基匹配时，只需要16位的比特基空间，而实体基匹配时只需要8位的比特空间，空间复杂度为O(1)。

3 数值实验和分析

本章将本文提出的算法DEMBBPM与算法RFC和基于差分演化的包匹配算法(Real-basedDifferentialEvolutionPacketMatching,RDEPM)〖13〗进行对比实验，因为RFC是目前传统包匹配速度比较理想的算法，RDEPM是目前利用智能算法进行包匹配比较理想的算法。实验是在模拟环境下进行的。在模拟实验中，设置防火墙每秒钟到达4×105个数据包，每一次测试时间为5s，优化算法中的定时器初始时长设为1s。仿真实验所用的操作系统平台是LinuxRedhat9.0，CPU是CoreI7 980XM，10GB内存；所用的模拟器是NS-2(NetworkSimulatorv2.27)。实验中缩放因子取定值0.7，交叉概率Cr由式(3)动态设置。本实验基于6组数据，在6种情况中，当规则数线性增长时，观察相应研究数据各自的变化趋势。在规则数线性增长的情况下，研究三种算法的优劣。本实验是以iptables建立的防火墙规则为实验数据，由于防火墙的规则相比路由器中的规则复杂一些，因而本实验使用前者更具有说服力。另外生成规则时遵循随机生成的原则，以避免偏差和混杂变量。为了尽量减少机会误差，表1实验的结果都是运算50次的平均值，同等规模的规则库50次是针对同一个规则库。

表1 不同规则数的各算法性能比较

从表1的数据看出本文提出的算法在整体性能上有绝对的优势。

从表1显示出本文提出的算法在各个规模下平均初始化时间消耗性能都逊色于其他两个算法，但是本文的算法在基础基的提取上只执行一次,既不像RFC算法每次包匹配都必须初始化,也不像RDEPM需要经常初始化。

从表1展现出本文提出的算法在各个规模下性能都比其他两个算法好，特别是和RFC算法相比，优越性更明显。这主要因为,本文的算法初始化进行的是多层比特实体基的提取,它能抓住规则库中错综复杂规则间的关联,找到基本的核心特征。

从表1表明本文提出的算法在内存消耗上性能也明显优越于其他两个算法，当规模较大时，这种优越性更明显。特别是传统的RFC算法，当规模达到100k时内存消耗大到算法根本无法运行。当规则库和映射域之间不是线性关系时，RDEPM算法无法找到α和β的最优组合，甚至都无法找到它们的近似组合，这样就会导致规则的分布性能欠佳，从而内存的消耗也会无效增加。

表2分别是规则数为103和5×105时，而且实验进行20次，每次同样规模的规则库是不一样，最坏情况下两个智能算法的性能比较。

表2显示在最坏情况下，RDEPM各项性能都比DEMBBPM差，甚至在平均性能比较中占优势的预处理时间也风光不再。因为RDEPM主观假设规则库的规则和映射空间之间是线性关系，这是一个致命的假设。因为当它们之间不是线性关系时，就会导致性能恶化。而本算法(DEMBBPM)没有假设这种线性关系。

表2 不同规则数最坏性能比较

表3显示在各规模下本文提出的算法都优越于RDEPM，反映本算法在特征提取时，提取的特征更优越，更能反映问题的本质。

4 结语

本文受深度学习的启发，针对包匹配，创造性地运用多层基础基去提取包的多层特征，在每层中分别运用精英反向差分演化算法进行比特基和实体基的提取，运用平均自信息作为衡量基础基选择的优劣。本算法扩展性能好，可以根据规则库实际规模选择提取层数。数值实验显示，本算法效果不错。

)

[1]WARKHEDEP,SURIS,VARGHESEG.Fastpacketclassificationfortwo-dimensionalconflict-freefilters[C]//Proceedingsofthe20thAnnualJointConferenceoftheIEEEComputerandCommunicationsSocieties.Piscataway,NJ:IEEE, 2001: 1434-1443.

[2]GUPTAP,MCKEOWNN.Algorithmsforpacketclassification[J].IEEENetwork, 2001, 15(2): 24-32.

[3]SRINIVASANV,VARGHESEG,SURIS,etal.Fastandscalablelayerfourswitching[J].ACMSIGCOMMComputerCommunicationReview, 1998, 28(4): 191-202.

[4]FELDMANA,MUTHUKRISHNANS.Tradeoffsforpacketclassification[C]//Proceedingsofthe19thAnnualJointConferenceoftheIEEEComputerandCommunicationsSocieties.Piscataway,NJ:IEEE, 2000: 1193-1202.

[5]GUPTAP,MCKEOWNN.Packetclassificationwithhierarchicalintelligentcuttings[J].IEEEMicro, 2000, 20(1): 34-41.

[6]SINGHS,BABOESCUF,VARGHESEG,etal.Packetclassificationusingmultidimensionalcutting[C]//Proceedingsofthe2003conferenceonApplications,Technologies,Architectures,andProtocolsforComputerCommunications.NewYork:ACM, 2003: 213-224.

[7]GUPTAP,MCKEOWNN.Packetclassificationonmultiplefields[C]//Proceedingsofthe1999ConferenceonApplications,Technologies,Architectures,andProtocolsforComputerCommunication.NewYork:ACM, 1999: 147-160.

[8]TSAIC-H,CHUH-M,WANGP-C.Packetclassificationusingmulti-iterationRFC[C]//Proceedingsofthe2013IEEE37thAnnualComputerSoftwareandApplicationConferenceWorkshops.Washington,DC:IEEEComputerSociety, 2013: 748-753.

[9]VANLUNTERENJ,ENGBERSENAPJ.Multi-fieldpacketclassificationusingternaryCAM[J].ElectronicsLetters, 2002 , 38(1): 21-23.

[10]SREELAJANK,VIJAYALAKSHMIPAIGA.Antcolonyoptimizationbasedapproachforefficientpacketfilteringinfirewall[J].AppliedSoftComputing, 2010, 10(4): 1222-1236.

[11]WANGZ,WUZ,ZHANGB.Packetmatchingalgorithmbasedonimprovingdifferentialevolution[J].WuhanUniversityJournalofNaturalSciences, 2012, 17(5): 447-453.

[12] 王则林,吴志健,尹兰.IPV6环境下的高维大规模包匹配算法[J].电子学报，2013,41(11):2181-2186.(WANGZL,WUZJ,YINL.HighdimensionlargescalepacketmatchingalgorithminIPV6 [J].ActaEletronicaSinica, 2013, 41(11): 2181-2186.)

[13]RAHNAMAYANS,TIZHOOSHHR,SALAMAMMA.Opposition-baseddifferentialevolution[J].IEEETransactionsonEvolutionaryComputation, 2008, 12(1): 64-79.

[14]QINAK,HUANGVL,SUGANTHANPN.Differentialevolutionalgorithmwithstrategyadaptationforglobalnumericaloptimization[J].IEEETransactionsonEvolutionaryComputation, 2009, 13(2): 398-417.

[15] 汪慎文,丁立新,谢承旺,等.应用精英反向学习策略的混合差分演化算法[J].武汉大学学报(理学版),2013,59(2):111-116.(WANGSW,DINGLX,XIECW,etal.Ahybriddifferentialevolutionwitheliteopposition-basedlearning[J].JournalofWuhanUniversity(NaturalScienceEdition), 2013, 59(2): 111-116.)

[16]ZHANGJ,SANDERSONAC.JADE:adaptivedifferentialevolutionwithoptionalexternalarchive[J].IEEETransactionsonEvolutionaryComputation, 2009, 13(5): 945-958.

[17]BRESTJ,GREINERS,BOSKOVICB,etal.Self-adaptingcontrolparametersindifferentialevolution:acomparativestudyonnumericalbenchmarkproblems[J].IEEETransactionsonEvolutionaryComputation, 2006, 10(6): 646-657.

[18]WANGY,CAIZ,ZHANGQ.Differentialevolutionwithcompositetrialvectorgenerationstrategiesandcontrolparameters[J].IEEETransactionsonEvolutionaryComputation, 2011, 15(1): 55-66.

ThisworkispartiallysupportedbytheNationalNaturalScienceFoundationofChina(61070008),theApplicationResearchProjectofNantongScienceandTechnologyBureau(BK2014057).

WANG Zelin, born in 1973, Ph. D., associate professor. His research interests include network security, intelligent computing.

HAO Shuixia, born in 1973, Ph. D., associate professor. Her research interest include parallel algorithm, intelligent algorithm.

Extracting kernel basis using differential evolution algorithm for packet matching

WANG Zelin1,2, HAO Shuixia3*

(1.XinglinCollege,NantongUniversity,NantongJiangsu226000,China; 2.SchoolofComputerScienceandTechnology,NantongUniversity,NantongJiangsu226000,China; 3.SchoolofMathematicsandStatistics,JiangsuNormalUniversity,XuzhouJiangsu221116,China)

Aiming at the speed of packet matching in network firewall, router and other equipment, a differential evolution algorithm was proposed to extract the multi-layer core base of package matching. The multi-layer foundation was used to describe the multi-layer characteristics of the packet. In each layer, the bit basics and entitative basics were extracted using differential evolution algorithm and average self- information and the average mutual information were used to evaluate the quality of kernel basis. This method was adapt to select the number of layers of the extracted entity base according to the actual size of rule base, which is very suitable for the growth of rule base. The experimental results show that The proposed algorithm is the first known algorithm to be applied to packet matching efficiently. Compared with RFC (Recursive Flow Classification) algorithm and RDEPM (Real-based Differential Evolution Packet Matching) algorithm, the performance of the proposed algorithm is superior in terms of time efficiency and space efficiency.

packet matching; differential evolution algorithm; average self-information; average mutual information

2016- 08- 11;

2016- 10- 24。

国家自然科学基金资助项目(61070008)；南通市科技局应用研究项目(BK2014057)。

王则林(1973—)，男，江苏南通人，副教授，博士，主要研究方向：网络安全、智能计算；郝水侠(1973—)，女，江苏徐州人，副教授，博士，主要研究方向：并行算法、智能算法。

1001- 9081(2017)03- 0777- 05

10.11772/j.issn.1001- 9081.2017.03.777

TP393