基于量子粒子群优化的网络入侵检测算法

基于量子粒子群优化的网络入侵检测算法*基金项目：江苏省高校自然科学基金资助项目（05KJD52006）；江苏科技大学科研资助项目（2005DX006J）作者简介：徐磊(1986)，男，硕士生，主要研究方向为计算智能；李永忠（1961），男，教授，硕士生导师，计算机应用技术学术带头人，主要研究方向为网络安全、计算机应用、藏文信息处理；李正洁（1987），女，硕士生，主要研究方向为网络与信息安全。徐磊,永忠,正洁XU Lei，LI Yong-zhong，LI Zheng-jie科技大学计算机学院， 212003Department of Computer，Jiangsu University of Science and Technology，JiangsuZhenjiang 212003，China:lei_yxwz163.Network intrusiondetection algorithm based on Quantum-behaved Particle Swarm OptimizationAbstract:In this paper，a hybrid algorithm based on Quantum-behaved Particle Swarm Optimization algorithm and Semi-supervised fuzzy kernel clustering algorithm is proposed.It overcomes the drawbacks of fuzzy clustering methods whichare sensitive to the initial cluster centers and easily trapped into local minima,. Firstly, the few labeled data can generate correct model with supervised clustering, and then the model aids to guide lots of unlabeled data to clustering，so enlarge the numbles of labeled data. At last，those data that still cant be labeled were clustered by the fuzzy kernel method based on Quantum-behaved Particle Swarm Optimization，and determine marker types. Furthermore，KDD CUP99 data set is implemented to evaluate the proposed algorithm. Compared to other algorithms，the results show the outstanding performance of the proposedalgorithm.Key words:intrusion detection; QPSO; semi-supervised clustering; kernel function摘 要：本文提出了一种将量子粒子群优化算法和半监督模糊核聚类算法相结合的混合算法，用以解决入侵检测算法中模糊聚类算法对初始值敏感，容易陷入局部最优的问题。本文算法先对少量标记数据进行监督聚类得到正确模型，运用这个模型指导大量未标记数据进行聚类，扩充标记数据集合，最后对仍没有确定标记的数据利用量子粒子群优化的模糊核聚类算法进行聚类，确定其标记类型。通过KDD CUP99实验数据的仿真，实验结果说明，该算法在入侵检测中能获得理想的检测率和误检率。关键词：入侵检测；量子粒子群优化；半监督聚类；核函数中图分类号：TP393.08 文献标志码：A1 引言入侵检测(Intrusion Detection，ID)是对网络的运行状态进行监视，发现各种攻击企图、攻击行为或者攻击结果，以保证系统资源的可用性、完整性和性。机器学习方法应用于入侵检测系统，能使系统具有更强的适应性、自学习性和鲁棒性，是目前入侵检测研究的一个重要方向。机器学习分为监督学习2，非监督学习1和半监督学习3。半监督学习又分为半监督分类,半监督聚类和半监督回归。半监督聚类1是近几年提出的一种新型聚类方法，它综合了无监督学习2和有监督学习3的优点，提高了聚类的质量，是近几年来机器学习和模式识别领域的重要的研究方向之一。由于基于监督学习的异常检测算法中需要获取大量的标记数据的类别信息，而标记的数据则是相对有限，获得它们需要付出大量的代价；同时基于无监督学习的异常检测算法中根据数据的相似性进行分组，克服了监督学习方法中标记样本不足的缺点，但其检测精度明显低于有监督的检测方法。然而半监督聚类的优越性则是在现实应用中，获得少量的有标记的样本数据是可能的，可以利用少量有监督的样本信息来指导无标签样本进行聚类。已有的半监督检测算法检测精度仍然可以得到提高，特别是针对新攻击类型的检测。针对以上基于机器学习的异常入侵检测算法出现的问题，本文提出了一种基于量子粒子群优化7的半监督模糊核C-均值聚类算法。模糊核C-均值算法9,10(KFCM)是将样本映射到特征空间，在特征空间中用FCM算法进行聚类分析，一定程度上克服了对噪声与野值数据的敏感，能对不同形状分布的数据正确聚类，而且克服了对数据在形状分布的依赖，增强了算法鲁棒性。但KFCM与K-means和FCM一样，其聚类性能具有依赖于初始聚类中心的选择和易陷入局部最优的缺点，因此本文将量子粒子群优化算法应用到半监督模糊核聚类方法中。首先对少量标记数据进行监督聚类得到正确模型，然后利用这些模型指导大量未标记数据的聚类，扩充标记数据集合，最后对仍没有确定标记的数据利用量子粒子群优化的核模糊C-均值算法进行聚类，确定其标记类型。通过KDD CUP99实验数据的仿真验证了QPSO-SKFCM算法的有效性和可行性。2 模糊核C-均值聚类算法传统的模糊C-均值聚类算法4,13算法简单，收敛速度快，在实际中得到了广泛的应用。但是，模糊 C-均值聚类算法只适用于样本分布为高斯分布或团状分布的情况。当样本线性不可分或样本分布为非高斯分布或非椭圆分布时，该算法实用性较差11。针对该问题，Girolami首先提出了将核方法与聚类方法相结合的思想11，通过把模式空间的数据非线性映射到特征空间，增加了模式的线性可分概率，即扩大模式类之间的差异，在高维特征空间达到线性可聚的目的。模糊核C-均值聚类算法的基本思想10,11是：首先利用一个非线性映射，将原空间中的样本映射到核空间中去，然后在这个高维的核空间中运用传统的模糊C-均值聚类。核空间中任意一个样本和均值之间的距离如下所示：设为待分类的样本集，其中：为样本数；为维特征向量。为设定的聚类数目,为个聚类中心，为第个样本对第类的隶属度函数，且满足条件,。模糊聚类问题就是根据聚类准则函数，求得样本集的个聚类中心和隶属度函数矩阵。FCM的聚类准则函数表示为： (1)式中，为加权指数。聚类的目标是使最小化。定义非线性映射，则：，其中，F为高维特征空间。KFCM的聚类准则函数表示为(2)(3)式中：为核函数；为特征空间中的欧氏距离。当核函数采用高斯核时，聚类准则简化为：(4)式中； (5)为高斯核参数。 通过Lagrange乘子法对式(4)求解,可得 (6)(7)3 量子粒子群优化算法3.1 粒子群优化(PSO)算法微粒群算法(Particle Swarm Optimization）是由J.Kennedy博士和Eberhan博士5提出的，它是基于种群的进化收索技术，但是所有基本的和改进的PSO算法不能保证算法的全局收敛，从基本微粒群算法模型可以看出，微粒的飞行速度相当于收索步长，其大小直接影响算法的全局收敛性。3.2 量子粒子群优化(QPSO)算法2004年，Sun等人针对PSO算法的收敛性问题，从量子学的角度出发而提出了一种新的PSO算法模型7。这种模型以DELTA势阱为基础，认为粒子具有量子的行为，并且根据这种模型而提出了具有量子行为的粒子群算法QPSO（Quantum-behaved Particle Swarm Optimization），其实验结果证明QPSO收敛性能有了很大的改进7。在QPSO中，粒子主要迭代公式如下：(8)(9)(10) (11)其中为收缩扩系数，它是QPSO收敛的一个重要的参数，、分别为的初始值和最终值。为第i个粒子的pbest，为全局最优，M为粒子的数目，D为粒子的维数，MAXITER为最大的迭代次数，t是当前的迭代次数。由文献7得到，当大于1.7时不能使QPSO算法收敛，一般的和取1.2和0.7可以使该算法达到较好的收敛性。4 基于量子粒子群优化的半监督模糊核C-均值聚类算法4.1 粒子编码在粒子群聚类算法中，每个粒子是由K个聚类中心组成,样本向量的维数为S，因此粒子表示为SK维向量.粒子位置构造如下：式中，为第个粒子的第个聚类中心。4.2 适应度函数设计定义粒子适应度函数为KFCM算法的目标函数，即： (12)4.3 基于量子粒子群优化的半监督模糊核聚类算法流程如下：算法: QPSO-SKFCM(Quantum-behaved Particle Swarm Optimization Semi-supervised Kernel Fuzzy C-means )算法输入：已标记数据集,未标记数据集,数据集输出：数据的数据类型(攻击或正常)(1)对进行监督聚类，初始化每个聚类中心，各聚类的最大半径(2)对于的样本进行初次聚类，如能正确分类则放到对应的聚类中，否则全部放到中for i=1 to m do计算每个样本与的距离，记为，end forwhile 则or end(3)While 未检测数据集为空，1)利用聚类中心，在数据集中，生成初始隶属度矩阵2)量子粒子群优化算法 (a)利用式(13)计算每个粒子的适应度 (b)初始化， (c)利用式(8)，(9)，(10)，(11)产生新一代个体, 更新，3)核模糊C均值聚类算法 (a)作为初始聚类中心 (b)利用式(6)更新隶属度矩阵，式(7)得到新的聚类中心4)if 则用替换，作为新的聚类中心 else则用替换，作为新的聚类中心end ifend(4)根据最终的隶属度矩阵确定每个样本的类别(攻击或正常)。5 实验与分析为了评价量子粒子群优化半监督模糊核聚类算法在入侵检测上的应用效果，选用入侵检测测试数据KDD CUP99网络数据集作为测试集，该数据集是在入侵检测领域广泛使用的测试集。实验数据中包含四种主要的攻击类型：(1)DoS，拒绝服务攻击(2)U2R，对本地超级用户权限的未授权的访问(3)Probe，扫描与探测行为(4)R2L，对远程主机的未授权的访问。5.1 实验数据的预处理实验中所采用的数据集中共有41个特征属性，在这些特性中有许多冗余的特性，因此只选择其中的21个能够表达用户行为的部分特征作为研究对象，分别是：Duration(l连接持续时间)，Service(目的端网络服务)，protocol_type(协议类型)，Flag(连接正常或错误的标记)等。为了满足检测算法中两个假设的需要，从整个检测数据集中选择4组数据作为实验的数据，每组数据包含110029条记录，其中108929条正常数据，1100条入侵数据，正常数据在每组实验数据中占到了99%，满足了检测算法中正常数据要远多于入侵数据的假设。5.2 测试结果与分析入侵检测算法的性能主要考虑检测率(Detection Rate，DR)和误报率(False Positive Rate ，FPR)。通过这两个指标能够很好的度量出算法的检测效果。DR=检测到的入侵检测样本/入侵样本总数；FPR=被误报为入侵的正常样本数/正常样本数；在实验中所用到有关参数见表1，实验结果见表2。表1 实验参数的选取参数名值取值理由MAXITER250迭代次数大于250后结果基本无变化1.2根据文献70.7根据文献7，0,1使用rand函数取0,1中的一个随机数50根据经验选择的粒子的个数70根据样本选择的聚类数目150默认取值表2 QPSO-SKFCM算法对入侵的检测情况测试数据检测率(%)误报率(%)第一组测试数据87.630.91第二组测试数据84.201.24第三组测试数据90.280.69第四组测试数据86.410.73平均87.130.89从表2可以看出，运用QPSO-SKFCM算法对样本的平均检测率达到87.13%，误报率仅为0.89%。这说明将基于量子粒子群优化的半监督模糊核聚类算法运用到入侵检测中是可行的。将QPSO-SKFCM算法与PSO-FCM算法，FCM算法在数据集中的检测攻击的性能进行比较。实验结果见表3。表3 QPSO-SKFCM算法与其它算法的比较检测算法已知攻击未知攻击DoSU2RProbeR2LDoSU2RProbeR2LQPSO-SKFCM82.387.498.787.578.982.193.573.2PSO-FCM50.283.696.190.262.474.385.767.4FCM32.972.786.593.611.247.821.574.6通过表3可以得到QPSO-SKFCM算法对已知攻击的平均检测率达到了89.7%，而对于未知攻击的平均检测率达到了81.9%。与另外两种算法相比能够更好地检测入侵行为。在未知攻击检测中本文算法对R2L的检测相对其他攻击类型检测略低，这是由于R2L入侵是伪装成合法用户的身份进行攻击,使其特征与正常数据包比较类似，容易造成检测较困难。相比于其他两种算法，本文算法在总体上对未知攻击和已知攻击类型的检测都占有明显的优势。6 总结实验结果说明QPSO-SKFCM算法不仅对已知攻击的检测率接近基于监督的入侵检测方法，而且对未知攻击的检测率也高于基于无监督的入侵检测方法。因为QPSO-SKFCM算法利用少量的标记样本产生正确的样本模型来指导大量未标记样本进行监督聚类，对于聚类后仍没有标记的样本采用量子粒群优化的模糊核C-均值算法进行无监督聚类，实现了对未知攻击的检测，从而有效弥补了单纯基于监督学习或无监督学习的入侵检测算法的不足。通过表3可以看出FCM对R2L的检测还略高于本文算法,并且本文算法在开始都需要预先指定粒子的数目以与参数、，选择适宜的数值对算法的速度和检测的精确性，都有很重要的影响，这也是以后进一步要研究的方向。参考文献：1 BASU S，BANERIEE A，MOONEY R.Semi-supervised clustering by seedingC。Proceedings of the 19th International Conference on Machine LearningSan Francisco，CA：Morgan Kaufmann Publishers，2002；19-262 WESTON JWATKINS CMulti-class support vector machinesRRoyal Holloway，Department of Computer Sciencez :University of London。19983 FLANAGAN J AUnsupervised clustering of symbol stringsC.International Joint Conference on Neural Networks， IJCNN03Portland Oregon，USA:2003,3250-32554 大朋.改进的模糊聚类算法在入侵检测中的研究J.计算机与数字工程，2010，38(3):88-91.5 J Kennedy, R C Eberhart. Particle Swarm Optimization C. Proceedings of the IEEE International Joint Conference on Neural Network s, 1995: 1942-1948.6 Sun J ,Xu W B. A Global Search Strategy of Quantum-behaved Particle Swarm Optimization C.In:Proceedings of IEEE conference on Cybernetics and Intelligent System s, 2004:111-116.7 广全，朱昌明.基于粒子群优化的模糊核聚类算法J.交通大学学报，2009，43(6):101-104.8 裴继红，久伦，维信.一种新的高效软聚类算法J.电子学报：1998,26(2):83-86.9 单凯晶,肖怀铁.初始聚类中心优化选取的核C-均值聚类算法J.计算机仿真，2009,26(7):118-121.10 庆丰,水利，国龙.基于核函数的模糊C均值聚类算法J.集美大学学报，2006,11(4):21-24.11 边肇棋，学工等.模式识别M第2版.:清华大学，2000.12 凌杰，国辉.基于混合粒子群优化的入侵检测研究J.计算机应用与软件，2009,26(4):21-25.6 / 6