基于粗糙集特征约减的网络异常检测方法_赵爱军

摘要：讨论了基于粗糙集特征约简的SVM （支持向量机）异常检测方法，对源自KDD99的实验数据集分别采用SVM 和特征约减后SVM 进行仿真实验，依据实验结果的比较，说明在网络异常检测中基于特征约减后的SVM 和直接采用SVM 相比，在保持检测精度不显著降低的同时，前者能够有效的缩短训练时间.关键词：粗糙集；特征约减；支持向量机；异常检测中图分类号：TP311文献标志码：A文章编号：1671-6191（2010）01-0026-040引言如今，随着网络应用的增长，网络应用已经深入到千家万户，网络安全也受到巨大的威胁.入侵检测技术作为防火墙后的第二道安全闸门，在网络安全系统中发挥着巨大的作用.入侵检测可以分为误用检测和异常检测两种类型.误用检测可以检测出已知的攻击行为，但是对于新的攻击行为无能为力，而异常检测可以通过检测模型检测出新的攻击类型，因此在入侵检测中得到了高度的重视.常用的异常检测方法包括数据挖掘方法[1]，人工神经网络方法[2]等.支持向量机[3]（Support Vector Machine ，SVM ），作为一种特殊的神经网络分支，是一种全新的机器学习方法，是统计学习理论中最年轻、最实用的内容，目前已广泛应用于模式识别、回归估计、函数逼近和密度估计等方面.近年来基于SVM 的网络异常检测算法已屡见不鲜.异常检测系统从网络关键链路收集信息进行分析、判断和决策，其所得原始信息通常高达几十维甚至上百维，直接基于此原始信息的检测判别伴随的是可观的计算开销，因此能高效精简或提炼原始信息的方法就不可或缺了.粗糙集理论[4]的特征约减方法就是其中的一种.本文讨论粗糙集特征约减优化给SVM 异常检测算法带来的性能提升，仿真实验验证了本方法的有效性.1粗糙集与知识表达系统1.1知识表达系统定义1知识表达系统是一个四元组，可定义为S ＝＜U ，RA ，V ，f ＞，其中U 是非空有限对象集，称为论域，R =C ∪D 属性的非空有限集合，子集C 和D 分别称为条件属性集和结果属性集；V =ni =1Σ坠V r 是属性r 的值域；f ：U ×R →V 是一个信息函数，它为每一个对象的每个属性赋予一个信息值.决策表是一类特殊的知识表达系统S ＝＜U ，R ，V ，f ＞.其中R =C ∪D 为非空属性集合，子集C 和D 分别称为条件属性集和结果属性集，具有条件属性和决策属性的知识表达系统称为决策表.1.2决策表离散化由于在处理决策表时，决策表中的数据值的表达必须为离散化的值，所以在处理决策表前必须对决基于粗糙集特征约减的网络异常检测方法赵爱军，谢林柏（江南大学通信与控制工程学院，无锡214122）收稿日期：2009-12-31作者简介：赵爱军（1975-），男，江苏扬州人，江南大学通信与控制工程学院硕士研究生，研究方向为控制工程与网络安全。

基金项目：国家自然科学基金（编号60804013）；江苏省自然科学基金（编号BK2009067）。

南通纺织职业技术学院学报（综合版）Journal of Nantong Textile Vocational Technology College Vol.10，No.1Ma r.2010第10卷第1期2010年3月策表中的连续属性进行离散化处理.常用的离散化处理方法有等距离划分法、等频率划分法、K 均值聚类算法、Naive Scaler 算法等.本文将采用Naive Scaler 算法[5].1.3知识约减知识约减就是在保持知识库分类能力不变的条件下，将其中不相关或不重要的知识约减掉.知识约减中有两个重要概念：约减与核.定义2令荠为一族等价关系，R ∈荠，如果ind (荠)=ind (荠-{R }),则称R 为荠中不必要的，否则为必要的.如果每一个R ∈荠都为荠中必要的，则称荠为独立的,否则称荠为依赖的.定义3设in d （Q ）＝core （P ）=∩red (P )，如果Q 是独立的，且in d （Q ）＝ind （P ），则称Q 为P 的一个约减.P 中所有必要关系组成的集合称为P 的Q 核，记为core （P ）,核与约减的关系为：core （P ）=∩red (P )，其中red (P )为P 的所有约减.2支持向量机2.1线性支持向量机当训练样本集线性可分时，分类超平面可表达为：ω·x +b =0.其中向量ω为分类超平面的权重向量，b 为阈值.其中，最优分类超平面的获得可以解决下面的凸二次优化问题：min ψ(ω)=‖ω‖2/2.约束条件为：y i (ω·x )+b -1叟0，i =1，2，…，n .通过求解，得到最优分类超平面的分类判别函为：f (x )=sgn （ni =1Σ坠i y i (x i ·x ）+b )(1)其中坠i 为拉格朗日乘子，拉格朗日乘子不为0的解向量为支持向量.2.2非线性支持向量机对于非线性分类问题，支持向量机通过某种非线性变换，将输入空间中的训练样本映射到一个高维特征空间，使得训练样本在高维空间中线性可分.根据泛函的相关理论，当函数K (x ，x i ）在满足Mercer 条件时，K (x ，x i ）称为核函数，它对应着某一输入空间到高维特征空间变换后的内积＜ψ(x i ）·ψ(x ）＞.函数W ：X →F 是一个从非线性输入空间到高维特征空间的一种映射，所以当需要求得高维特征空间中的内积只需知道输入向量x 、x i 即可，由K (x i ，x ）=＜ψ(x i ）·ψ(x ）＞将（1）重写,即可得到对应的高维特征空间中对应的分类函数:f (x )=sgn （ni =1Σ坠i y i K (x i ·x ）+b )(2)这样，在高维特征空间中的内积运算就转化为低维输入空间中的一个核函数的计算.分类函数（2）的学习式称为支持向量机.3基于粗糙集与SVM 的异常检测方法原理基本思想：采用粗糙集属性约减方法对实验数据集进行约减，获得一个最小的条件属性集，根据这个最小的条件属性集对训练样本进行相应的约减得到新的训练样本，并对该训练样本进行归一化处理，然后采用支持向量机进行训练.同理，利用最小的条件属性集对测试样本进行约减得到新的测试样本，并进行归一化处理，并采用训练好的支持向量机进行检测.具体过程为：①连续特征的离散化处理：对KDD99中的连续特征采用Na觙ve Scalar 算法[5]进行离散化处理；②训练样本集特征的约减：采用1.3中的基于可辨识矩阵和逻辑运算的约简算法对离散化后的训练样本进行约减，得到训练样本；③检测模型的生成：利用支持向量机对处理后的训练样本进行训练，得到检测模型；④生成测试数据集：对测试样本依次进行离散化和约减，得到处理后的测试样本；⑤利用训练好的检测模型对测试数据集进行预测.赵爱军，等：基于粗糙集特征约减的网络异常检测方法27第1期4实验结果与分析4.1实验中的数据集本文实验中使用了10％KDD99[6]测试数据集中的20000条连接记录，其中Normal ，Probe ，Dos ，R2L ，U2R 各4000条,如表1所示.本文采用高斯核函数exp(-‖x -x ‖2/δ2），并利用交叉验证的方法来确定参数.同时，采用LibSVM [7]来实现模型的训练与测试.4.2数据集的约减由于一个TCP 连接记录的41个属性之中有32个续属性，可以采用Na觙ve Scaler 算法将连续特征离散化.然后利用特征约简算法对选取的10％的数据集进行特征约简，这里可采用Rosetta [8]软件来实现.约减结果如表2所示.表3和表4则分别列出了基于粗糙集特征约简之后和之前数据集SVM 异常检测的测试结果.由表3和表4的实验结果可以看出，基于粗糙集特征约减的SVM 异常检测与基于全部特征的SVM 异常检测相比，基于粗糙集特征约减的SVM 异常检测在各种攻击样本的训练时间和检测时间上都比基于全部特征的SVM 异常检测的训练时间和检测时间短，可以理解为由于特征维数减少，支持向量机的计算量也相应减少，即时间缩短，而且两者在检测率上面相当.在DOS ，U2R ，R2L 这3种攻击类型上面，检测率比全部特征的SVM 异常检测的检测率高，这可解释为通过粗糙集的特征约减，将原始样本中的冗余特征约减掉，能达到更好的检测精度.通过图1中4种样本的迭代次数与平均预测精度上的关系可知，在相同的迭代次数的情况下，基于粗糙集处理过的数据在SVM 上面异常检测时，预测精度更高，同时，通过图2可知，将SVM 和粗糙集属性约减相结合比单独采用SVM 所需的训练时间更短.图1迭代次数与预测精度之间的关系10.90.80.70.60.50.40.30.20.10020406080100120140160180200SVM+RST SVM迭代次数平均预测精度28南通纺织职业技术学院学报（综合版）2010年5结语本文提出的基于粗糙集特征约减的支持向量机的网络异常检测方法在KDD99数据集上进行仿真实验，并和全部特征的数据集采用支持向量机的异常检测相比，前者在检测率上有些许提高，同时在模型的训练以及检测时间上面前者都比后者有明显的缩减，由此可知，基于粗糙集特征约减的支持向量机的网络异常检测方法是可行的.参考文献：[1]S .M .Bridges ，Rayford M .Vaughn .Fuzzy data mining and genetic algorithms applied to intrusion detection [C]//In In Proceedings 23rd National Information Systems Security Conference ，Baltimore ，MD ，2000：13－31.[2]Sung AH ，Mukkamala S .Identify important features for intrusion detection using support vector machines and neural networks [C]//EEE Proceedings of the 2003Symposium on Application and the Internet ，2003：209－216.[3]Vapnik V N .The nature of statistical learning theory [M].New York ：Spring－Verlag ，1995：87－105.[4]Paw lak Z .Rough sets [J].International Journal of Computer and Information Sciences ，1982，（5）11:341－356.[5]张文修,吴伟志.粗糙集理论介绍和研究综述[J].模糊系统与数学，2000，14（4）:1－12.[6]KDD Cup 1999Data [EB/OL].（1999－10-28）[2009-12-10].http ://kdd .ics .uci .edu ／databases ／kddcup99／kddcup99.html .[7]Chih－Chung Chang ，Chih－Jen Lin .LIBSVM :a library for support vector machines [EB/OL].(2009－11-10)[2009-12-10].http ://www .csie .ntu .edu .tw ／～cjlin ／libsvm .[8]Marcin Kierczak.R osetta [EB/OL].(2009－03-19)[2009-12-10].http ://rosetta .lcb .uu .se ／general .（责任编辑：王晓燕）Performance Optimization for Network Anomaly Detection Using Rough SetAttribution Reduction Z HAO Ai -jun ，X IE Lin -bo（School of Communication and Control Engineering ,Jiangnan University ，Wuxi 214122，China ）Abstract ：Discussed method of network anomaly detectio n using rough -set -attribution -reduction -based SVM.The testing data set from KDD 99were experimented by respectively using attribution-reduction-based SVM and original SVM.The experiment results showed that ，compared with applying SVM directly ，to apply attribution-reduction -based SVM in network anomaly detection can reduce effectively training time without obviously losing detection accuracy.Key words ：rough set ；attribution reduction ；SVM ；anomaly detection0.10.090.080.070.060.050.040.030.020.010020406080100120140160180200SVMSVM+RST迭代次数训练时间（s )图2迭代次数与训练时间之间的关系赵爱军，等：基于粗糙集特征约减的网络异常检测方法29第1期。