将量子算法应用于入侵检测的检测器生成过程，提出了一种基于量子免疫原理的检测器生成算法来求解入侵检测问题。算法的基本思想是通过学习自体模式，训练出具有多样性高的抗体，然后用于真实数据的检测。采用kddcup99数据进行仿真实验，用5 000条正常网络连接训练抗体集，将所有攻击数据分类和部分正常数据一起对QIDA的性能做全面测试，仿真结果表明该算法比其他方法更加有效。
1002011,47(11) Computer Engineering and Applications计算机工程与应用 算法第(2)步是对初始抗体群中的个体进行一次测量,以 表2训练集数目不同时的检测效果 获得一组二进制解,测量过程为随机产生一个[0,1],若它大 DOS攻击 Probe攻击 ALL 训练集数目 于概率幅的平方,则测量结果取值1,否则取值0。 DR FAR DR FAR DR FAR 1000 702.3069.0 1.870.02.00 循环过程中,根据上述公式计算抗体的聚合适应度,取其 2000 1.32 895 1.05 中优秀的P个抗体进行复制并变异,将变异后的P个抗体加入 5000 83.0 90.00.95 到原抗体群中,通过聚合适应度的大小,从N+P个抗体中选择 N个最优抗体,再利用量子旋转门进行量子更新,保证抗体群 由表2可看出,当训练集数目越多,训练出的抗体检测率 朝着优秀方向进化。 越高,误报率越低。这是因为训练集太小,就不能包含足够多 的数据来区分正常数据和异常数据,从而使检测器的精度不 仿真实验 够高,随着训练集的增多,精度也不断提高。但是考虑到训练 时间的因素,本文后续的实验都以2000条数据为训练集 41实验数据选取 在实验中,分别测试了4种不同类型的攻击检测效果。为 为了测试本算法的效果,采用了 kdd cup99数据集作为 了直观地比较四种不同类型的攻击以及全部攻击数据的检测 测试集。数据集中包含正常网络数据和22种攻击,攻击可归 效果,做出了相应的ROC曲线,如图1所示。 纳为4类:(1)拒绝服务DOS(2)探测攻击 PROBE(3)远程登录 R2L0(4)非法获取ROOT权限U2R。每条数据包含了41个属 性,本文去掉7个离散型属性,采用其中34个连续数值型属性。 采用数据集上的一个子集10 percent作为实验数据源,饣 -. DOS tr-Probe 共包含有494020条网络连接,其中正常连接97277条,异 R2L 常连接3%6743条。首先将这些数据进行分类,形成正常数据 20 U2R 以及4类不同攻击的样本集。网络实验数据描述如表1所示。 表1实验数据表 数据类型网络连接总数实验中用到的网络连接数 图1四种攻击和总攻击的检测效果图 1000~5000用来训练 在图1中,横坐标代表误报率,纵坐标代表检测率,越靠近 正常数据 97277 10000用来检测 ROC曲线的左上端说明检测效果越好,从图中可看出,DOS攻 391458 391458 击和U2R攻击的检测效果非常好,而 Probe攻击和R2L攻击的 2L 1126 1126 攻击数据 检测效果要相对差一些。但是总的检测效果不错。 U2R 为了评估基于量子免疫的入侵检测方法的实时性,在同样 Prob 4107 4107 的PC机上统计它的训练时间以及检测时间,结果如表3所示。 4,2数据预处理 表3基于量子免疫入侵检测方法的实时性测试 实验采用的数据34个属性中,由丁数据间数值差异较大, 训练 检测(每个攻击类型的测试数据中 应该对原始数据进行规格化处理,以免岀现“大数吃小数”的现 均含有止常的树络连接1000 象"。设输入数据为S={x,x,…,x},则规格化处理步骒如下: 正常数据DOS攻击Pobe攻击R2L攻击U2R攻击 网络连接个数200 401458 14107 11126 (1)计算半均值x=1Sx 158 3 0.5 (2计算标准差()=∑(x-x) 为了便于比较,将Lee的误用检测方法",刘刚博上的基 于遺传算法的检测方法,俞研博士的半聚类异常检测算法 xi 共计3种方法的实验结果与本文的QIDA方法的实验结果列 (3)计算归一化后的值x ( 在一起,如表4所示。 3实验结果分析 表4四种入侵检测方法的效果表 为了评价入侵检测算法的性能,主要考虑两个指标:入侵入检测方法00玫击Pmhe击R2L攻击U2R击 DR FAR DR FAR R FAR DR FAR 检测率DR和入侵检测误报率HAR。通过测试算法对攻击的 Wenke lee 82 9 86.0 60 890 检测率与误报率,能够很好地度量出算法的检测效果。 8002.4582.5 781.00850 检测到的入侵样本数 SAID 7833.5069.01.2800.85755 DR 入侵样本总数 OIDA 9231.2083.01.5850.809800.2 FAR- 被误报为入侵的正常样本数 从表3实时性测试和表4的不同方法入侵检测结果的比 正常样本总数 较可看出 本实验硬件平台为PC( Pentium4CPU3.0GHz,512MB (1)在4种不同的攻击检测中,能看到QIDA的DR指标均 RAM),编程软件为VC60.实验参数设置如下:抗体样规模为要大于Lu和SAID的结果,表明了本文算法生成的检测器集 00,变异个数为20,最大进化代数式50,训练数据为1000、合检测率较高。在FAR指标上,由于本文算法采用提取自体 20005000分三组实验。旋转角M为0.1和0.05之间动的模式,在检测与自体特征较接近的U2R攻击时有一些误报, 态调整。本文实验首先对训练集数目为1000、2000和5000但是总体性能要好于上述两种方法。与Le的方法相比,Q1 分别进行10次实验取平均值,结果如表2。 DA能很好地检测出DOS,R2L和U2R三类攻击,但是 Probe攻 赵丽,李智勇,陈冬,等:求解入侵检测问题的量子免算法 2011,47(11)101 击的检测效果相对差一些,但总的检测效果要比Le的方法好 data using clustering] Proceedings of ACM Css Workshop 很多 Data Mining applied to security, 2001 (2)QDA是通过正常网络连接建立行为模型,如果发现5] Yu yan, Huang Hao. An ensemble approach to intrusion detec 某个网络连接在一定程度上偏离这个模型就认为该网络连接 ion based on improved multi-objective genetic algorithm[J]Jour- 为异常它只需要用到正常数据进行训练,而且对未知的攻击 nal of software,2007,18(6):1369-1378. 也有很好的检测效果,因此具有更强的实用性。 [6 Kim I, Benetley P JAn evaluating of negative selection in an (3)在实时性方面:使用共计396744条攻击和10000条 artificial immune system for network intrusion detection[C]/Ge- netic and Evolutionaty Computation Conference, San francisco 正常数据作为测试集,数据量庞大。但从表3能看出,检测时 July7-11,200l:1330-1337 间非常短,实时性非常好。 通过以上分析,本文的方法在总体性能上比其他方法都7] Li zhiyong. Rudolph G A framework of quantum-inspired multi objective evolutionary algorithms and its convergence condition[c]/ 要理想。 Procccdings of the 9th Annual Confcrcncc on Gcnctic and Evc lutionary Computation, GECCO 07, London, England, United 5结论及展望 Kingdom, ACM, July 7-11, 2007 设计了基于量子免疫原理的检测器生成算法,并用于入8] Li Zhiyong, Rudolph G, Li Kenli Convergence performance com 侵检测测试。通过与其他算法仿真结果分析,本算法的检测 parison of quantum-inspired multi-objective evolutionary 准确率高,而且实时性好,能够在短时间内训练出优秀的抗体 thins[J]. Comnputers and Mathematics with Applicalions, 2009 群,快速地检测出攻击。但是本方法是基于正常网络连接训 57:1843-1854 练出的检测器集,如果入侵数据中的特征与训练数据中的特9】 Han K H Genetic quantum algorithm and its application to com 征很相似,则会出现漏报现象。为了解决这个问题,在接下来 binatorial optimization problem[C]/IEEE Proc of the 2000 Con- gress on Evolutionary Computation. San Diego: IEEE Press, 2000 的研究中,将重点融合数据的各个特性,进一步提高入侵检测 1354-1360. 的准确率。 0]崔逊学基于免疫原理的多日标进化算法群体多样性研究门模 式识别与人工智能,2001,14(3) 参考文献: [11] The UCI KDD Archive. KDD99 cup dataset[EB/OL.[2007-10-10] [I Forrest s, Perelson A S, Allen L, et al. Self-nonself discrimina http://kdd.ics.uci.edu/databases/kddcup99.html tion in a computer[CI/ Proceedings of the1994 IEEe Sympo-[12]伟多信息源的实时入侵检测方法硏究D]西安:四安交通大 sium on Research in Security and Privacy, 1994 学,2005-05 [2] Zhao Bingjie, Sun Fuxiong, Xie Wei. The research of generation [13] Lcc W, Stolfo S J, Mok K wA data mining framework for build- algotithm of detectors in immune-based detection model[c]// ing intrusion detection Models[C]/Proceedings of the 1999 2008 International Symposium on Knowledge Acquisition and IEEE Symposium on Security and Pivacy. Oakland, USA: IEEE Modeling,2008,89:693-697 Press,1999:120-132 3] Wang Qiao, Feng Xiaokai. a detector generation algorithm based[l4]刘刚基于免疫遗传算法的入侵检测系统研究北京:铁道科学 on negative selection[C]//Fourth International Conference on 研究院,2006-07 Natural Computation. IEEE Computer Society, 2008 [5]俞研,黄皓.一种半聚类的异常入侵检测算法[J计算机应用, [4] Portnoy L, Eskin E, Stolfo S Intrusion detection with unlabeled 2006,26(7):1640-1643 上接66页) [4] Valero V, Cambronero M E, Daz G, et al.A Petri net approach 如表1所小,三种情况下的置信区间都将对应的基丁 PETRI for the design and analysis of Web services choreographies[J] 网方法的结果覆盖,从而验证了本文提出方法的正确和有效性。 The Journal of Logic and Algebraic Programming, 2009, 78(5): 6结论 [5] Daz G, Pardo J J, Cambronero M L, et al. Automatic translation of WS-CDL Choreographies to timed Automata[c]/Proc EPEW/ 在本文中提出一种模型驱动的方法来评估基于WS-CDL规 WS-FM,2005:230-242. 范的组合服务的可靠性。该方法以 NMSPN网为中间模型,对 [6 Daz G, Cambronero M E, Pardo JJ, et al. Automatic generation WSCI)中的基本活动活动、结构活动、例外处理、定时控制 of correct Wcb scrviccs chorcographics and orchestrations with 等要素进行定量描述,并给出了分析流程正常完成概率的方法。 Inodel checking techniques[C]/Proc AICT 2006, 2006: 186-196 还在样例研究中用wS-CDL+执行引擎获得了实验运行数据,[7] Tobias p, Trindade d, Applied reliability[M2 end ed. Kluwer:Dor 并采用置信区间分析技术检验了理论模型和结果的止确性。 drecht. 1995 [8 Trivedi K Probability and statistics with reliability, queuing, and 参考文献 computer science applications[M]. West Sussex: John Wiley and [1] Web Services Choreography Description Language, Version 1.0[ZI Sons, England, 2001 2005 [9 Kang Zuling, Wang Hongbing, Hung P C K. WS-CD+: WS-CDL+ [2] Zhou Lei, Zhang Hanyi, Wang Tao, et al. Static check of WS-CDL for web service collaboration[]. Information System Frontiers documents[C]//Proc SOSE, 2008: 142-147. 2007,9(4):375-389 13 Pu Geguang, Zhao Yongxin, Wang Zheng, et al.A denotational model [10] Welcome to the WS-CDL+ Execution Engine Project, Version for Web services choreography[C]//Proc ICDCIT, 2008: 1-12 0.1.1[eb/ ol].(2008-01). httP://wscomposition.seu.edu.cn/index.html