基于双极快速进化特征选择算法的异常入侵检测

◆程新党 赵学武

（南阳师范学院软件学院 河南473061）

基于双极快速进化特征选择算法的异常入侵检测

◆程新党 赵学武

（南阳师范学院软件学院 河南473061）

异常入侵检测技术在入侵检测系统中有着重要的地位，该技术依据用户的正常行为模式来检测未知攻击。但由于网络链接数据复杂多变的特性和冗余无关网络链接属性的干扰，时常导致现有异常检测技术的失效。针对该问题，提出了一种新的双极快速进化算法，该算法在每一代解集的最差与最优两个极端分别引入最差反转进化和最优迭代繁殖等搜索策略，改善算法的收敛速度与全局寻优能力，然后将本算法与特征选择相结合，快速选出最优的网络链接特征组合，并结合决策树ID3算法构造异常入侵检测规则，在数据集KDD CUP99上的多项比较实验表明该算法能够获得较优的特征组合，并取得了较高的检测率与准确率，同时具有较低的误警率，为异常入侵检测模型的设计提供了参考。

入侵检测系统；快速进化算法；决策树；特征选择；异常检测

0 前言

随着计算机技术和通信技术的发展，计算机网络在社会的方方面面扮演着越来越重要的角，但是计算机和网络的安全已经成为人们急需面对的新难题，据统计，黑客入侵事件逐年增加，给个人和相关机构造成了巨大的损失。作为网络安全防御的主要手段之一，入侵检测系统（Intrusion Detection System,IDS）可以检测到多种攻击和入侵行为，并发出报警信号。 目前常见的IDS可以分为异常检测系统、误用检测系统或签名检测系统[1]。早期的入侵检测技术主要利用预定义的已知入侵模式与目标系统的特定行为进行匹配来判断是否有入侵事件发生，具有较高的正确率，但不能发现未知的攻击模式，所以需要经常更新特征库以保证系统的检测效果。而在异常检测系统中，系统基于一定周期内用户的工作模式和网络状态，对网络数据进行分析将偏离正常行为的网络链接判定为入侵事件，这种方法虽然可以发现未知的入侵攻击，但具有较高的误报率。

近年来，基于机器学习的异常入侵检测技术得到较大的发展，研究者们运用分类、聚类或者规则关联等技术对入侵行为进行分析挖掘，并建立了多种数学模型，已经取得了较好的实际效果；但是由于用户行为的多变性和复杂性，不论是分类还是聚类方法，在具体的工程实践中都分别存在着一些问题，比如对初始值敏感，收敛速度慢，易陷入局部最优等。针对这些问题，已经有人提出了一些针对性的改进算法和策略，如文献[2，3，4]。其中Srinoy等人[2]将粗糙模糊聚类的方法应用于冗余数据的消除，并使用粗糙集理论实现对正常异常行为的软划分；在文献[3]中Denatious等人将聚类、分类以及关联规则综合应用到入侵行为的检测发现上；文献[4]中 Mohanabharathi等人将信息增益率与k-means法结合起来用于无线网络系统中行为属性的特征选择与入侵事件的判定。但随着互联网日渐融入人们的生活，网络应用日新月异、丰富多样，这不仅导致了网络数据量的与日俱增，同时对应用层网络数据信息的描述也需要较多的特征，但多数特征对入侵检测来说可能是冗余的，因此庞大而复杂的数据信息导致入侵检测效率低下，而检测复杂度日益上升。现有的研究并不能很好地解决这些逐渐出现问题，最终导致了已经部署的IDS出现了误警率较高或检测率较低的现象，已经对整个社会造成了较大的损失。如何快速选出最佳的表示异常入侵行为的网络链接特征组合，已经成为提升IDS检测效果的一个关键性问题。基于此，本文提出了一种双极性快速进化特征选择算法，旨在以较快的速度选择出最能表征入侵行为的特征组合，再结合特定的分类算法来快速准确地检测到入侵行为，不仅能为IDS的相关技术的研究实施提供技术支持，而且该算法对组合优化问题的研究也有一定的参考意义。

1 相关工作

在入侵检测中，网络连接行为通常需要多个特征（属性）加以描述，例如在KDD CUP99 数据集中，每条数据共包含41个特征，研究表明这些特征中仅有部分与入侵行为密切相关，剩余部分特征对入侵检测来说是冗余无关的，并严重影响着检测的效率与准确度。同时，数据集包含数据量巨大，如果直接进行建模分析不仅运算时间长，而且分类的精度不高。因此运用特征选择算法对数据进行预处理不仅可以缩减运算时间，而且可以提高分类的精度。在机器学习算法中，尤其在涉及高维特征空间时，数据降维操作已经成为常用的数据预处理步骤。自从上世纪70年代，特征选择技术被提出以来，已经成为提升机器学习算法性能的一种重要技术途径，并且被广泛地应用到多个领域，例如：分类、数据挖掘、目标识别、入侵检测等，被证明是一种从原始数据集中去除冗余无关特征的有效手段。在入侵检测方面，唐成华等[5]利用信息增益算法对网络攻击链接数据的特征进行排序，然后利用约登指数删减数据集属性，并取得了较好的聚类效果。Karimi-Nasab等人[6]提出了基于多对象遗传算法（Multi-object genetic algorithm,MOGA）的随机搜索策略；陈友等人[7]提出了一种基于遗传算法（GA）和禁忌搜索相混合的搜索策略；Stein等人[8]提出一种称为遗传决策树的模型，其使用遗传算法选择最优特征子集，然后使用这些子集构造C4.5决策树；Lin和Ying等人[9]使用模拟退火算法（Simulated annealing algorithm）和支持向量机来搜索最优特征子集；Mohanabharuthi等人[4]使用信息增益和k-Means相结合的方法进行特征选择。上述研究表明特征选择虽然方法众多，但主要集中在信息增益和智能算法两大类上，而信息增益法需要人工决定最终需要选择的特征数，同时信息增益最高的若干特征的组合不一定是最优的，所以元智能启发类算法在特征的选择上具有先天优势。本文将运用一种被称为双极性快速进化算法（Bipolar Fast Evolutionary Algorithm BFEA）的特征选择技术搜索最优特征子集，并结合ID3决策树进行分类，在数据集KDD CUP99上的实验结果表明，该算法具有实现简单，收敛速度快，无早熟现象等特点。

决策树算法是Salzberg在1994年所提出的一个非常著名的机器学习算法，决策树主要由节点（内部节点）、弧（有向边）和叶子（叶子节点）三部分组成，每个内部节点与一个属性（特征）对应，根据样本在该属性上的取值范围将样本空间划分为两个或多个类别，每个从节点出发的弧使用对应的属性值进行标注，每个叶子节点代表一个类别。使用训练样本递归地产生决策树，直到不能继续为止，该算法的更多描述以及变种参见文献[11]等。决策树构造完成后，将每个测试样本按照决策树的结构自顶而下进行判决，直到进入叶子节点，则将测试样本标注为该叶子节点对应的类别。目前常用的决策树算法有ID3和C4.5，本文采用ID3算法。

2 双极快速进化特征选择算法

双极性快速性进化算法是针对离散型组合优化问题所提出的一种高效迭代型进化算法，但通过合适的编码方案可以很容易应用到连续型问题的求解上，其基本思想是针对进化类算法中全局寻优能力差、收敛速度慢等缺点，首先引入最差解反转进化策略来快速扩大搜索范围，即在每代解集中，亲和度最差的若干解表明它们与最优解偏离较大，一般的进化类算法是丢弃这些解，而在本算法中则是该重新计算最差解补集的亲和度，并与当前最优解比较决定去留；其次是在算法中增加了最优解迭代繁殖进化策略来细化局部搜索，即利用“优则优待”的原则允许最优解一次产生多个相似子代，因为当前最优解可能已经非常接近全局最优了，所以该策略可以用较少的迭代次数发现全局最优解。实验表明本算法在收敛速度和寻优能力上相对于其他类似算法都具有一定的优势。

本文将该算法应用到IDS标准数据集KDD CUP99上进行网络数据链接的特征选择，并使用决策树（decision tree 简称 DT）ID3算法生成检测规则，然后使用DT分类结果对算法求得的最优特征子集进行评估，亲和度函数设计如下式（1），即约登指数。

其中DR为检测率(Detection Rate)，AR为准确率（Accuracy Rate），对本系统而言就是要求系统具有较高的报警率和较低的误警率。

2.1 算法流程

设特征集合为 F={a1，a2，ai，…am}，m=|F|为集合大小，random()为（0，1）上均匀分布的随机函数，G为最大迭代次数，f(s)为亲和度函数，其流程图如图1所示，描述见下述的1-9个步骤；

图1 BFEA算法流程图

（1）对特征集合F采取不放回采样R=random()*m次，则经过R次采样后，特征集F被划分为集合FY和FN，FY表示被选中的特征集合，FN表示F中未被选中的特征集合，有FN□F，FY□F，且FN∩FY=□，记s=＜FY，FN＞为问题的一个解。

（2）上述步骤1)共执行N+X次，取其中N个不同的解s作为问题的初始解集合，即对特征集F进行了N次异构划分，记初始解集为 S=(s1， s2， … ，si， …， sN)。

（3）对集合S中的si使用式（1）计算亲和度函数值vi=f(si)，然后依照vi对si进行降序排序，将s1存入sbest，其亲和度值存入vbest，取其中前 k=random()*N/2个进行步骤 4)运算， 取后 k’=random()*N/2 进行步骤5)运算，然后删除剩余的N-k-k’个解，构成新的解集S。

（4）对于集合S中的前k个解 si=＜，i=1,2,…k , 设

（7）如果sbest发生变化，且|sbest|＞1,则依次从集合sbest移除一个特征，构成|sbest|个特征子集，遍历每个子集，计算亲和度如果 v’＞vbest, 则用 v’替换 vbest，对应的记入临时变量s’中，遍历结束，如果存在v’＞vbest,则用对应的替换 sbest，然后递归执行该过程。

（8）使用步骤1)中的方法，随机生成若干（小于N-k-k’）个新解，且与解集S中现有解不同，加入到解集S中，使解数量达到N。

（9）评估最优解，如果符合终止条件或达到设定的最大迭代次数G，则输出最优解并结束，否则迭代次数加1，转步骤3)继续执行。

2.2 算法分析

该快速进化算法可以看作是遗传算法GA或其他进化算法的变种，也属于进化算法范畴，但对寻优策略进行了优化。该算法步骤（1）和步骤（8）用来产生初始种群（解集），它们彼此不同且是异质的，相当于执行全局随机搜索，与其他进化类算法相同；本算法中的步骤（3）和步骤（4）类似于GA算法中的交叉运算，即最优染色体的特征重组，而本算法采取的方法是单亲进化，具体措施是随机替换最优解中的若干特征，跳跃幅度和搜索范围更大，而步骤（5）则是针对若干最差解采用完全反转操作，进一步扩大全局搜索范围。本算法的步（6）和步骤（7）用作局部寻优，相当于GA的变异操作，但与变异操作相比，该算法的特征变化幅度更小，局部搜索更细致。经过上述搜索策略上的改善，不仅使算法收敛速度得以提高，而且最终解更接近全局最优。因此本算法可以看作是一种进化算法的改进，其仅用单个父代来产生子代，研究表明（Schwefel 1995）这种使用单个亲代产生单个子代的方式对搜索最为有效[10]。下面对该算法的时间复杂度做个简要的分析。考察上述对算法流程的描述，待求解的规模为m=|F|维，种群规模为N，解的编码长度取大值m，最大进化代数为G；算法中一次亲和度计算时间为T，本例采用ID3算法，其时间为O(m×N×logN) 。算法中步骤（3）和（4）操作时间平均为(m/2) ×(N/4) × T ， 即O(m2×N2×logN)，同理步骤（5）时间也为O(m2×N2×logN)，而步骤6)仅需一次亲和度计算时间T，分析算法步骤（7）其可能导致递归操作，时间复杂度为 O(m×logm)，因此一次迭代所需的时间为O(m2×N2×logN+ m×logm)，即O(m2×N2×logN); 其中时间O(m×N×logN) 由ID3算法消耗，而单独考虑该BFEA算法，其时间复杂度仅为O(m×N)。

2.3 算法收敛性证明

设种群(解集)在第t次迭代共有解N个，分别记作s1t，s2t，…，

sNt， 设所求问题的最优解记为 sbest，亲和度函数记为 f(s)，则算法的收敛性可以定义如下：

定义2.1.

则称算法以概率1收敛到最优解。下面根据上述算法收敛性定义，给出定理2.1。

定理2.1. BFEA算法必然以概率1收敛到全局最优解。现证明如下：

证明：所有解构成的解集记为S，其中任一解用s表示，有s∈S，对BFEA算法来说，任一解可以看作为一个特定的状态，记算法的马氏链状态空间为G，其维数记为M=|G|=|S|，分析2.1节所述算法流程，发现每次迭代均是在最优解的基础上通过若干次随机替换而产生下一代最优解，即到达另一状态。设pij为从状态 si到 sj的转移概率，算法的最终目标是寻找最优解，所以 pij的取值共分为三种情况：

（1）随机被选中的若干最优解直接进入下一代 ，即 pij=被选中的概率 。

（2）针对2.1 节算法流程的步骤 3)、4)、5)操作，若 f(si)＞ f(sj)，则进入下一代，概率设为pij。

（3）若 f(si)＜ f(sj) ，则 pij=0；

将解按照亲和度降序排列，则算法的有限状态马氏链一步转移概率矩阵为：

在算法实现中，选择每代最优解中前k个，使之直接进入子代解集，这些解的亲和度值在上下两代之间是相同的；对于那些亲和度值不同的最优值解上下代之间的状态转移则是单向的，即只能向亲和度增大方向转移。设：

即 Sxt为使第 t代解取亲和度值为 f(St-best)的状态集合。因此与最优解集对应的状态集为一闭集。从状态空间的任一状态si开始，最终进入上述闭集Sxt的概率称为闭集Sxt对si的吸收率，而闭集对状态si的吸收率为1 。一般情况下，问题的最优解只有1个，则P11=1，P1j=0（j ）是以全局最优解为超个体的状态转移概率，综上所述可得：

P为齐次马氏链的一步转移矩阵，记t步转移矩阵为Pt=P(t)，由齐次马氏链呈现无后效性的特点可得：

因此可得：

至此，算法收敛性得证。

3 实验与结果分析

3.1 评估标准

本文采用常用的三个性能指标对算法进行评估，即检测率（DR）、正确率（AR）和误警率（FPR），定义分别如下式所示。

较高的检测率和正确率，以及较低的误警率代表较好的IDS性能，是所有IDS检测算法设计与优化的目标。

3.2 实验数据集

本文实验数据采用KDD Cup99数据集，该数据集可以从站点http：//kdd.ics.uci.edu上下载。其中训练数据集包含大量数据记录，每条链接记录使用41个属性（特征）进行描述。在10%数据集中包含391458个拒绝服务类（DoS）攻击，52个权限提升类（U2R）攻击，4107条端口扫描探测类（Probe）攻击，1126条远程登录类（R2L）攻击和97278条正常链接数据。这其中包含大量重复数据，为了更快速地训练模型，在实验中，首先剔除重复数据，将剩余数据按照攻击类别各选部分到新的训练数据集，而测试数据则从KDD Cup99 Corrected（test）中随机抽取，实验所用样本分布情况如表1所示。实验数据集包含离散型和连续型属性数据，为了简化的决策树的结构，需要将连续型数据转化为离散型数据，转化方法采用文献[12]中的经典方法将连续数据划分为2个区间：首先找出数据集中属性为连续型的最大与最小值，分别记为max和min，取中值MP=(min+(max-min)/2)作为分割点进行划分即可。

表1样本数据分布表

3.3 实验结果与分析

算法使用C#语言在Windows7 64位系统上设计实现，运行环境为Intel i5-4200M CPU，2.5GHz，8GB RAM。设定算法最大迭代次数G=500，初始种群（解集）大小为50，算法终止条件为5代之间亲和度增量δ＜0.005（特征数分别取5，10，..35，对算法稍微调整，丢弃长度不符的解即可）。然后分别针对每种情况，算法独立运行10次得到的平均结果如图2、图3和表2所示。对算法不做最优解特征数限制，10次运行后最优解的平均长度为

20个特征数，与文献[9]推荐最优解21～22特征数近似一致。

表2 BFEA不同特征长度下的FPR/DR/AR/f(s)值

图2 特征数与DR、AR的关系图

表2的结果列出了算法在给定特征数的情况下检测率、准确率、误警率以及对应的亲和度函数值，图2则是它们之间的变化趋势图。我们可以很直观的看出随着BFEA算法对样本数据特征的选择与优化组合，不论是检测率、还是准确率都随着特征数的减少而逐渐增大，当特征数为20时基本上达到峰值，而准确率在特征数为 10时达到最大值，但此时检测率并非最大。从图 2还可以看出对KDD CUP99数据集来说，41个特征中冗余无关特征项在一半以上，体现出了特征选择的必要性。

图3 特征数与误警率的关系图

图4 ROC曲线图

分析图3发现误警率在特征数为30个时达到最低，但配合图2，发现该点对应的检测率和准确率都较低。分析图4所示的ROC曲线图发现特征数目为20时效果最好，有着最高的检测率和相对较低的误警率，结合表2特征数目为20时恰好对应着最高亲和度值。但在实际设计IDS系统时，特征数的选择可以根据IDS的检测速度与FPR，DR的实际需求在20，15，10，5之间做出权衡，因此本文的研究对IDS开发设计具有一定的指导意义。

图5 三种算法在不同特征数时的综合性能比较

图 6 三种算法收敛性能比较

图5是三种不同算法的比较，他们分别是BFEA，IG（信息增益）、GA（遗传算法），实验分别用这三种算法在特征数 10，15，20个的情况下进行综合性能比较，发现特征数较少时IG方法最优，这表明在特征数目有严格要求的系统中，使用IG法可以取得最优的效果，但随着特征数的增加，智能算法的优势逐渐明显，即智能算法通过多次迭代，可以找出全局最优的组合。

对算法的限制特征数目，并将最大迭代次数G设为500，取5代之间亲和度增大量δ＜0.005时为算法的终止条件， 比较GA算法、BFEA和文献[9]提出的SA-SVM在本数据集上的收敛速度，实验结果如图6所示。结果表明，BFEA算法在进化代数较少时，与另外两种算法相差不大，但随着进化代数的增加，BFEA收敛速度优势逐渐体现，观察三种算法在较高代数的表现，BFEA有逐渐加快的趋势。

4 结论与后续研究

本文提出了一种新的快速智能进化类特征选择算法，该算法采用一对一进化，最差解逆转进化，最优解迭代小振幅繁殖进化等一系列策略来快速精确地搜索全局最优解。然后我们将该算法与ID3决策树相结合应用到异常入侵检测系统中；针对特征复杂多样（41个特征）的较大规模样本数据（103以上）进行特征选择，并使用 ID3算法生成决策规则进行异常入侵检测实验，在KDD CUP99上的实验结果取得了较高检测率和较低的误警率，证明了该算法相对于其他算法的收敛速度以及求解精度上的优势。此外，本算法不仅可以应用于特征选择这种离散型的最优化组合问题的求解，而且使用合适的编码方案本算法完全可以应用到函数优化领域，这也是我们下一步将要研究的一个内容。

[1]Liao H J，Lin C H R，Lin Y C，et al． Review：Intrusion detection system：A comprehensive review．Journal of Network &Computer Applications，2013．

[2]Srinoy S，Kurutach W，Chimphlee W，et al．Intrusion detection via independent component analysis based on rough fuzzy．Wseas Transactions on Computers，2006．

[3]Denatious D K,John A．urvey on data mining techniques to enhance intrusion detection．International Conference on Computer Communication and Informatics．IEEE，2012．

[4]Mohanabharathi R,Kalaikumaran T,KarthiS． Feature selection for wireless instrusion detection system using filterandwrappermodel．InternationalJournal of Modern EngineeringResearch，2012．

[5]唐成华， 刘鹏程， 汤申生．基于特征选择的模糊聚类异常入侵行为检测．计算机研究与发展，2015．

[6]Karimi-Nasab M,Konstantaras I．A random search heuristic for a multi-objective production planning． Computers & Industrial Engineering，2012．

[7]陈友， 沈华伟， 李洋．一种高效的面向轻量级入侵检测系统的特征选择算法．计算机学报，2007．

[8]Stein G,Chen B,Wu A S,et al．Decision tree classifier for network intrusion detection with GA-based feature selection．Southeast Regional Conference． Kennesaw ，Georgia,Alabama,Usa，2005．

[9]Lin S W,Ying K C,Lee C Y,et al．An intelligent algorithm with feature selection and decision rules applied to anomaly intrusion detection．Applied Soft Computing，2012．

[10]Schwefel H P P．Evolution and Optimum Seeking： The Sixth Generation．John Wiley & Sons,Inc，1995．

[11]潘大胜， 屈迟文．一种改进 ID3型决策树挖掘算法．华侨大学学报：自然科学版，2016．

[12]Anusha K，Sathiyamoorthy E．Comparative study for feature selection algorithms in intrusion detection system．Automatic Control and Computer Sciences，2016．

国家自然科学基金项目（61401242）、河南省基础与前沿技术研究项目（142300410396）资助。