入侵检测中检测器生成方法的

摘 要：入侵检测器的生成是入侵检测系统的核心,量子遗传算法针对复杂优化问题有很强的搜索能力和最优化性能.该文提出了一种基于量子遗传算法的协同进化检测器生成方法,该算法通过对自然界中的协同进化机制进行模拟,首先将要进化的种群划分为多个子种群,然后各个种群再分别利用量子遗传算法进行优化,使整个入侵检测系统具有良好的自适应性和多样性.

关 键 词：入侵检测器；量子遗传算法；协同进化

中图分类号：TP274文献标识码：A文章编号：1009-3044(2012)13-3199-03

ResearchonGeneratingMethodofDetectorinIDS

LILu-lu

(CollegeofComputerScienceandEngineeringInstitute,YulinNormalCollege,Yulin537000,China)

Abstract:Thegenerationofintrusiondetectiondeviceisthecoreoftheintrusiondetectionsystem,Inplaceofplexproblemofoptimizaion,quantumgeicalgorithmhasstrongsearchingcapabilitiesandthemostoptimalperformance.Inthispaperaquantumgeicalgorithmcoevolutiondetectorgenerationmethodisproposed.Thepopulationneedingtoevolveisdividedtosomechildpopulationbysimulatingnaturecooperativecoevolutionmechani,andeachpopulationusingquantumgeicalgorithmtooptimize,makingwholeintrusiondetectionsystemhasgoodadaptabilityanddiversity.

Keywords:intrusiondetectiondevice,quantumgeicalgorithm,cooperativecoevolution

1概述

随着网络和计算机技术的不断发展,网络安全性问题日益突出起来,入侵检测系统是一种重要的安全防范技术,已成为网络安全的重要保障之一[1-2].目前各种不同的攻击方式不断出现,因此入侵检测中的有关智能性研究逐渐成为入侵检测系统研究领域中的一个重要方向.而入侵检测系统的主要部件是检测器,检测器生成算法是生成有效检测器的关键,是检测异常变化的核心所在[3-4].检测器的设计对入侵检测系统的性能有着重要的影响,其从产生到成熟再到被丢弃,有自身固有的过程和生命周期,可以利用遗传算法来生成一个成熟检测器集,采用交叉、变异等遗传操作对其进行进化,使成熟检测器群体向“非我”进化.但随着问题规模的不断扩大和搜索空间的更加复杂,遗传算法在实际应用中有一定的局限性,不能表现出算法的优越性,出现迭代次数多、收敛速度慢、易陷入局部最优值和过早收敛等问题.

量子遗传算法结合了量子计算和遗传算法的优点,它将量子所具有的独特计算能力和遗传算法的全局寻优能力结合起来,提升了算法的优化性能,比传统遗传算法具有更高的搜索效率[5].该文在现在有研究的基础上提出一种检测器生成方法,该算法通过对自然界中的协同进化机制进行模拟,首先将要进化的种群划分为多个子种群,然后各个种群再分别利用量子遗传算法进行优化,使整个入侵检测系统具有良好的自适应性和多样性.

2相关知识

量子遗传算法本质上是种概率优化方法,其基本思想是基于量子计算原理,用量子比特编码来表示染色体,充分利用量子态的叠加性和相干性,以当前最优个体的信息为指导,通过量子门来完成种群的更新操作,以此来促进算法的收敛,从而来实现目标的最后优化求解.

2.1量子比特

通常在计算机中用二进制0和1来表示信息单元,而在量子计算机中是用一个双态量子系统即量子比特来表示信息单元.量子比特作为信息单位,形式上表示为两种基态|0>和|1>,一般用|0>表示0,用|1>表示1.与经典比特不同,量子比特不仅可以处于两种基态|0>和|1>,而且还可以处在中间态,也就是|0>和|1>的不同叠加态.因此,量子比特的状态可用下式表示：

2.2量子染色体[6]

量子遗传算法是采用量子比特的编码方式,用一个复数对(α,β)表示一个量子比特.若一个量子染色体包含m个量子比特,则由m个复数对组成.这个染色体编码形式如下：

2.3量子旋转门

在量子遗传算法中量子染色体一般是纠缠或叠加的,所以可以用量子门来表示染色体的各个纠缠态或叠加态；父代群体不能决定子代个体的产生,个体的产生是通过父代的最优个体以及它们状态的概率幅决定的.用构造的量子门表示量子叠加态或纠缠态的基态,它们彼此干涉使相位发生改变,以此达到改变各个基态的概率幅的目的.因此,如何构造合适的量子门是量子遗传操作和量子遗传算法亟待解决的关键问题,量子门构造的是否合适会影响到遗传算法的性能.目前在量子遗传算法中通常采用量子旋转门U,U可表示为

,θ为旋转角.

2.4量子变异[7]

通常情况下在遗传算法中,算法的局部搜索能力以及阻止未成熟染色体收敛这些操作都是通过变异作用实现的,量子变异必须达到量子遗传算法对变异操作的要求,这里我们这样定义量子比特的变异操作：

（1）从种群中以给定的概率pi随机地选择若干个体；

（2）确定变异位,以确定的概率对从（1）中选择的个体随机地确定变异位；（3）对换操作,对换选中位量子比特的概率幅.

2.5协同进化算法[8]

进化算法的本质是优化,是为了使物种在激烈的竞争中能够具备生存的本领以致在竞争中能够生存下来.在一般的遗传算法中要么只涉及到个别群或个体的进化,要么只是涉及种群之间的竞争,几乎没有顾及到个体与个体,种群与种群之间互惠寄生的协同关系.基于以上原因,提出了协同进化算法.协同进化是生态系统中众多进化方式中的一种,进化中种群要生存下来不仅要受自身因素的影响,同时也受周围同类或异类的相互影响,在这些因素的影响下能够生存下来.在进化的过程中种群的个体之间及其与其它种群之间都要进行相互作用相互影响.

3基于量子遗传算法的协同进化检测器生成算法设计思路

算法的基本思想：首先对随机生成的种群进行种群分割,将种群分成若干个子种群.利用空间形态学的原理,根据种群中各个自体间的距离来判断它们是否属于一个分割,各个子群之间互相协作,以确保整个系统的适应度不断提高；用量子遗传算法对单个子群进行进化.量子遗传算法优化检测器的入侵检测模型如图1所示.图1量子遗传算法优化检测器的入侵检测模型

（1）种群的初始化策略

在量子遗传算法中种群初使化操作通常是这样进行的,各个体的量子位概率幅()2,也就是说各个体的全部状态出现的概率相同.协同进化需要多个种群,因此必须增加种群的多样性,所以在初始化时我们将量子位概率空间平均分为N个,即体表N个子群,0、1极限概率为δ,用公式（1）来初始化第k个子种群,也就是将同子种群内的每个个体初始化为量子染色体,每个量子染色体的概率相同,不同子种群个体的状态以不同概率出现,以此来达到增加初始化个体多样性的目的.（2）量子门更新策略

采用进化方程的方式来调整量子门的旋转角大小和方向.这样做有两个好处：一是减少了参数的个数,同时算法的结构也得到了简化；另一个是利用进化方程的记忆的,可以利用个体自身的局部最优信息,邻域种群的最优信息,以及整个种群最优状态的信息,从而使旋转角θ能够得到更加合理的调整,还能够更好地跳出局部极值.进化方程可定义为：U等于

p-xi,其中k1,k2,k3,k4为影响因子,pi,pj是左右邻域种群极值,pm为个体所在种群极值,p为全局极值.

（3）具体实现步骤

Step1：将量子位概率空间平均分为N个,即体表N个子群,0、1极限概率为δ,用公式子种群,也就是将同子种群内的每个个体初始化为量子染色体,每个量子染色体的概率相同,不同子种群个体的状态以不同概率出现,以此增加初始化个体的多样性.

Step2：初始化步骤1中的每一个子群Qi()

Step4：依次对Pi()t进行适应度评估；

Step6：保留步骤5中得到的N个最佳个体,如果此时得到了满意解,则算法终止,否则转入Step7；

Step7：采用（2）中定义的量子门U()

Step8：以确定的概率进行量子变异；

Step9：对于每个新的子代Qi()t+1,算法转至Step4继续进行.

4结论

检测器集的好坏决定了入侵检测系统的性能,因而检测器集的生成算法是入侵检测系统开发中最核心的部分.该文引入量子遗传算法来实现检测器的优化过程,设计了基于遗传算法的检测器生成算法.该算法通过模拟自然界协同进化机制,把需要进化的种群划分为多个子种群,各个种群采用量子遗传算法进行优化,使整个入侵检测系统具有良好的自适应性和多样性.在接下来的研究中,将重点研究侵检测器中各参数的影响程度的问题,以提高入侵检测系统的自适应性和有效性,进一步提高入侵检测的准确率.