KNN-IPSO选择特征的网络入侵检测

冯莹莹，余世干，刘辉

阜阳师范学院信息工程学院，安徽阜阳 236041

KNN-IPSO选择特征的网络入侵检测

冯莹莹，余世干，刘辉

阜阳师范学院信息工程学院，安徽阜阳 236041

为了提高网络入侵检测的正确率，提出一种基于KNN-IPSO选择特征的网络入侵检测模型（KNN-IPSO）。首先采用K近邻算法消除原始网络数据中的冗余特征，并将其作为粒子群算法的初始解，然后采用粒子群算法找到最优特征子集，并对粒子的惯性权重进行自适应调整和种群进行混沌操作，帮助种群跳出局部最优，最后采用KDD CUP 99数据集对KNN-IPSO的性能进行测试。结果表明，KNN-IPSO消除了冗余特征，降低了分类器的输入维数，有效提高了入侵检测正确率和检测速度。

入侵检测；特征选择；特征关联性；改进粒子群算法

1 引言

随着Internet用户增加，网络规模越来越庞大，网络入侵事件日益增多，入侵检测系统作为安全防御的最后一道防线，能够检测各种形式的入侵行为，因此网络入侵检测一直是网络安全中的研究热点[1-2]。

在网络入侵检测过程中，特征选择结果优劣对网络检测速度和正确率产生直接影响[3]。原始网络数据包括大量冗余或无用特征，易出现“维数灾难”问题，而且入侵检测过程需要对海量数据进行处理，实时性要求高。特征选择是指在保持原有网络数据信息完整性的基础上，剔除无用或者冗余特征，以提高网络入侵检测效率[4]。当前网络特征选择方法主要有模拟退火算法、蚁群算法、粒子群优化算法等群智能算法进行特征选择[1，5-6]。其中粒子群优化（Particle Swarm optimization，PSO）算法具有实现简单，需调整的参数少等优点，在网络入侵特征选择中应用最为广泛[7]。由于入侵检测数据的特征维数比较高，直接采用PSO进行特征选择，效率低，而且PSO算法易过早收敛和陷入局部极值，影响特征选择性能[8]。

为了提高网络入侵检测的正确率和检测效率，提出一种基于KNN-IPSO选择特征的网络入侵检测模型（KNN-IPSO）。首先采用K近邻算法消除原始网络数据中的冗余特征，并将其作为粒子群算法的初始解，然后通过粒子之间信息共享、协作找到最优特征子集，最后采用KDD CUP 99数据集对KNN-IPSO的性能进行测试。

2 KNN生成IPSO算法的初始特征子集

设原始网络状态特征数目为M，那么特征集可以表示为：O={Fi，i=1，2，…，M}；消除冗余特征的网络状态特征子集为R；λ(Fi，Fj)用于度量特征Fi和Fj之间关联度；表示特征Fi与消除冗余特征子集R第K个近邻特征的关联度[9]。KNN算法生成的初始特征子集步骤具体如下：

（1）确定KNN算法的初始K值，初始化消除冗余特征子集R，使R=O。

（2）计算特征子集R中的一个每个特征Fi值。

（3）找出Fi值最小的对应的特征，选择，将其K个最相近特征删除，令ε=。

（4）若有K＞cardinality(R)-1，那么K=cardinality(R)-1。

（5）若K=1，表示R中没有特征和其近邻的λ值小于ε了，转到步骤（8）。

（8）将此时R中特征作IPSO算法的初始特征子集，有效地消除了冗余和无用特征。

3 改进粒子群算法选择网络入侵检测特征

3.1 改进的粒子群算法

在标准粒子群（PSO）算法中，每个粒子均具有自己的位置和速度，粒子的位置代表问题的一个可行解，每个粒子按式（1）更新自己的速度v和位置x：

式中，t表示迭代次数；ω称为惯性权重；c1、c2为学习因子，rand是在0～1的随机函数；pbest表示粒子本身经历过的最好位置；gbest表示种群经历过的历史最好位置[10]。

当粒子群中粒子陷入局部最优后，粒子速度变化接近零，种群多样性迅速减小，很难跳出局部最优值，因此，PSO算法极易陷入局部最优解。为了解决该难题，本文提出一种改进粒子群（Improved Particle Swarm optimization，IPSO）算法，具体改进思想为：首先对惯性权重进行自适应调整，动态调整参数；然后根据粒子群的适应度方差判断是否陷入局部最优，如果陷入局部最优，则对种群进行混沌扰动，增加粒子种群的多样性，使粒子易于摆脱局部最优，提高全局搜索能力。

为了说明本文改进粒子算法（IPSO）的优越性，利用2个测试函数与文献[11-12]的改进粒子群算法的性能进行对比。算法参数：加速常数c1=c2=2，惯性权重在[0.4，0.9]之间随代数线性递减，函数维度设置为30，种群规模设置为20，每次运行迭代6 000次，每个函数独立搜索运行30次。不同改进粒子群算法的适应度的对数值变化曲线如图1所示。从图1可知，IPSO算法的收敛速度明显优于对比算法，尤其对于多峰值Rastrigin函数，IPSO算法以最快速度找到最优解，而文献[11-12]的改进粒子群算法收敛速度慢，因此本文IPSO算法的搜索能力、收敛精度和收敛速度均优于对比算法。

图1 几种改进粒子群优化算法的性能对比

3.2 编码规则

对于给定含有m维特征的网络状态数据集D，特征选择的目的是选择出一个满足目标函数最优的特征子集R，粒子的个体采用二进制编码规则，选中的特征取为1，否则为0。

3.3 适应度函数

入侵特征选择目标包括两个方面：（1）网络入侵检测正确率更高；（2）特征维数尽量最少，则适应度函数由所选特征子集的大小和检测正确率两部分组成。适应度函数计算公式为：

式中，d为选取特征子集的维数；D为入侵检测原始特征维数；Prate表示检测正确率；λ为检测正确率权重系数。

3.4 IPSO的特征选择步骤

（1）设置IPSO最大迭代次数，位置和速度变化范围等参数值。

（2）收集网络状态信息，提取网络状态特征。

（3）采用0/1串位表示特征集，根据特征间的关联度，采用KNN算法来消除原始特征集的冗余特征，得到IPSO群算法的初始特征子集。

（4）计算当前种群每一粒子的适应度值，选取出粒子历史最优值和全局最优位置。

（5）根据式（4）对惯性权重进行自适应调整，并根据式（1）、（2）更新粒子的位置和速度。

式中，ωmax，ωmin分别为惯性权重的最大值和最小值；ti为当前迭代次数；tmax为最大迭代次数。

（6）计算更新后粒子群的适应度值，并更新粒子最优位置和全局最优位置。

（7）判断是否达到迭代次数，若达到条件，则进入步骤（10）；否则进入步骤（8）。

（8）根据式（5）计算种群适应度方差，如果适应度方差小于门限值，表示易陷入局部最优，则进入步骤（7）进行混沌处理，否则转入步骤（5）继续执行。

式中，fi为每一个粒子的适应度值；为当前粒子群的适应度平均值；f为归一化因子；用于限制σ2的大小。

σ2越小，说明粒子群中粒子波动越小，种群越趋于统一。理论上在全局收敛和早熟收敛情况下σ2=0。但实际上σ2不可能达到0，故在实际判决时，仅需判断σ2小于某一门限值（本文σ2=10-4），即可认为当前粒子群已陷入局部最优。

（9）粒子群的混沌扰动。当粒子群陷入局部极值时，以当前粒子群的gbest为基础产生混沌序列，并用混沌序列中的适应度值最优解来代替当前粒子群中的任一粒子的位置，具体步骤如下：

①将gbest归一化至混沌扰动量r的基本取值范围[0，1]。

②将r作为Jerk混沌系统的初值X(0)，产生M个随机数列。

③将混沌序列还原至原优化变量取值区间，分别计算出对应的适应度值。

④将最小的适应度值对应的粒子，代替粒子群中原任一粒子的位置，由于混沌扰动的初值根据全局最优位置决定，可产生当前全局最优位置附近的若干相邻点，可以帮助陷入局部最优的粒子逃离局部收敛。

（10）根据种群的最优位置得到最优特征子集。

4 仿真实验

4.1 仿真环境

为了测试KNN-IPSO的性能，在P4 3.0 GHz CPU、2 GB RAM，window s XP环境中，采用VC++编程实现仿真实验。数据来自入侵检测的标准数据集——KDD CUP 99数据集，该数据集包括9个星期的空军局域网络连接数据，其中训练集包含500万条记录，测试集包含200万条记录，每一个记录包含41个特征，具体见表1。IPSO算法参数：c1=c2=1.5，种群规模m=20，最大迭代次数tmax=1 000，ωmax=0.9，ωmin=0.4。

表1 KDD CUP 99的特征

4.2 对比模型和评价标准确度

为了对KNN-IPSO特征选择方法的性能进行全面、准确地衡量，首先不采用KNN选择特征，直接采用改进粒子群算法进行特征选择（IPSO）；采用KNN对特征进行初始选择，然后采用基本粒子群优化算法（PSO）、蚁群算法（ACO）对相同训练集进行特征选择，并建立相应的入侵检测模型，它们分别命名为：KNN-PSO、KNN-ACO模型，所以模型均采用支持向量机作为分类器。模型性能评价标准为：检测时间、检测正确率和误报率，其中误报率和检测正确率的定义如下：

4.3 网络数据归一化

在KDD CUP 99数据集中，样本特征属性范围各异，而支持向量机分类是根据样本与超平面距离来确定样本的归属，因此少量特征对支持向量分类性能影响大，其他特征影响较小，因此需要进行预处理来消除这种不利影响，对其进行归一化处理，具体为：

式中，n表示训练样本数，xstd表示样本特征标准差。

4.4 KNN参数K值的确定

KNN算法首先要确定参数K的值，为此，K的值从1开始，逐渐增加，然后观察K值选取对网络入侵检测平均正确率的影响，结果见图2。

图2 参数K值对网络入侵检测正确率的影响

从图1知，当KNN的K值从1增加到4时，网络入侵检测的平均正确率大幅度提高；从4增加到7时，网络入侵检测的平均正确率提高幅度较小，当K=7时，达到最优检测正确率；当K值大于7时，检测正确率逐渐降低，因此KNN的参数K=7。

4.5 结果分析

4.5.1 与原始特征的性能比较

采用KNN-IPSO特征选择方法对训练集进行特征选择，提到的特征子集见表2。从表2可知，采用KNN-IPSO对原始特征进行选择后，大幅度降低了特征维数，结果表明，KNN-IPSO算法是一种有效的网络入侵特征选择算法。

表2 KNN-IPSO算法选择的特征子集

对每一种网络入侵类型，采用支持向量机对表2中的特征子集和原始特征集建立相应的入侵检测模型，不同模型的检测时间和正确率见表3。从表3中可知，相对于原始特征的入侵检测模型，KNN-IPSO网络入侵检测模型的检测时间大幅度降低，这主要是由于采用KNN-IPSO进行特征选择后，消除大量的冗余特征，减少了分类器输入向量维数，计算时间复杂度降低，提高了网络入侵检测效率；同时网络入侵检测正确率得以明显提高，这表明冗余特征会对网络分类器的分类性能产生不利影响，导致全部原始特征的入侵检测模型检测正确率降低，说明了对网络入侵检测进行特征选择是必须，可以获得更优的网络入侵检测效果。

表3 特征选择前后的网络入侵检测性能对比

4.5.2 与其他特征算法的性能比较

KNN-IPSO和其他特征算法的入侵检测结果如图3～4所示。对图3～4的结果进行分析，可以得到如下结论：

（1）相对于IPSO算法，KNN-IPSO的网络入侵检测性能优势比较明显，这表明对特征维数较高的入侵检测数据，直接采用IPSO进行特征选择，检测时间长，效率低，然而KNN-IPSO算法通过KNN消除网络入侵的冗余特征，得到了更优的IPSO初始特征，使IPSO的寻优目标更加明确，迭代次数减少，减少了检测时间，提高了网络入侵检测速度，同时KNN-IPSO找到了更优的网络特征子集，网络入侵检测正确率相应得到提高。

（2）相对于KNN-PSO算法，KNN-IPSO的网络入侵检测综合性能明显提升，这说明IPSO通过对粒子群最优位置进行混沌扰动，帮助陷入局最优的粒子逃离局部最优位置，找到全局最优的网络特征子集，消除冗余特征的不利影响，检测速度更快，提高了网络入侵检测正确率。

图3 不同特征选择算法的检测率比较

图4 不同特征选择算法检测时间比较

（3）相对于KNN-ACO算法，KNN-IPSO不仅提高了网络入侵检测正确率，同时检测时间相应减少，这表明采用KNN-IPSO可以获得比KNN-ACO算法更优的特征子集，降低了计算时间复杂度，建立了性能更优的网络入侵检测模型，可以满足现代大规模、高维的网络入侵检测在线、实时要求。

5 结束语

网络入侵检测要求实时性要求，特征太多会导致计算量大，检测时间慢，而且无用或冗余特征对网络入侵检测产生不利影响，为了解决该难题，提出一种基于KNN-IPSO的网络入侵检测模型（KNN-IPSO）。结果表明，KNN-IPSO在保证检测准确率的前提下，大幅度提高了入侵检测效率，可以满足特征复杂多变的网络入侵检测要求。

[1]闫新娟，谭敏生，严亚周，等.基于隐马尔科夫模型和神经网络的入侵检测研究[J].计算机应用与软件，2012，29（2）：294-297.

[2]姜春茂，张国印，李志聪.基于遗传算法优化SVM的嵌入式网络系统异常入侵检测[J].计算机应用与软件，2011，28（2）：287-289.

[3]井小沛，汪厚祥，聂凯，等.面向入侵检测的基于IMGA和MKSVM的特征选择算法[J].计算机科学，2012，39（7）：96-100.

[4]牟琦，毕孝儒，库向阳.基于GQPSO算法的网络入侵特征选择方法[J].计算机工程，2011，37（14）：103-105.

[5]Denning D E.An intrusion detection model[J].IEEE Transactions on Software Engineering，2010，13（2）：222-232.

[6]Hang C L，Wang C J.A GA-based feature selection and parameters optimization for support vector machines[J].Expert Systems with Applications，2009，31（2）：231-240.

[7]郭文忠，陈国龙，陈庆良，等.基于粒子群优化算法和相关性分析的特征子集选择[J].计算机科学，2008，35（2）：144-146.

[8]高海华，杨辉华，王行愚.基于BPSO-SVM的网络入侵征选择和检测[J].计算机工程，2006，32（8）：37-39.

[9]陈仕涛，陈国龙，郭文忠，等.基于粒子群优化和邻域约简的入侵检测日志数据特征选择[J].计算机研究与发展，2010，47（7）：1261-1267.

[10]李洋，方滨兴，郭莉，等.基于TCM-KNN和遗传算法的网络异常检测技术[J].通信学报，2007，28（12）：48-52.

[11]李莉，李洪奇.基于混合粒子群算法的高维复杂函数求解[J].计算机应用，2007，27（7）：1754-1756.

[12]孙兰兰，王晓超.求解高位函数优化的动态粒子群算法[J].计算机工程与应用，2011，47（27）：36-38.

[13]张雪芹，顾春华.一种网络入侵检测特征提取方法[J].华南理工大学学报：自然科学版，2010，38（1）：81-85.

[14]陈友，沈华伟，李洋.一种高效的面向入侵检测系统的特征选择算法[J].计算机学报，2007，30（8）：1398-1408.

FENG Yingying, YU Shigan, LIU Hui

College of Information Engineering, Fuyang Teachers College, Fuyang, Anhui 236041, China

In order to improve the detection accuracy of network intrusion,this paper proposes a novel network intrusion detection model（KNN-IPSO）based on K Nearest Neighbor and Improved Particle Swarm optimization algorithm to select the features.Firstly,KNN algorithm is used to eliminate redundant features and remove the redundant features of network data and the selected features are taken as the initial solution of PSO,secondly,the optimal features are obtained by PSO which inertia weight is adjusted adaptively and chaotic system is intruded to help the swarm s jump out the local optimal solutions,finally the KDD CUP 99 data sets are used to test the performance of KNN-IPSO.The results show that the proposed model can eliminate the redundant features and reduce the input dimensions of classifier.It can improve the network intrusion detection accuracy and detection speed.

intrusion detection; feature selection; feature relevance; improved particle swarm optimization algorithm

FENG Yingying, YU Shigan, LIU Hui. Network intrusion detection based on KNN-IPSO selecting features. Computer Engineering and Applications, 2014, 50（17）：95-99.

A

TP391

10.3778/j.issn.1002-8331.1312-0257

安徽省高等学校省级自然科学研究项目（No.KJ2013B206）；安徽省高校省级优秀青年人才基金重点项目（No.2013SQRL102ZD）。

冯莹莹（1982—），女，讲师，主要研究领域为网络安全及计算机图形学；余世干（1982—），男，讲师，主要研究领域为嵌入式系统开发；刘辉（1979—），男，讲师，主要研究领域为计算机图像处理。

2013-12-18

2014-03-12

1002-8331（2014）17-0095-05