基于特征选择和支持向量机的异常检测方法

张 昭，张润莲＋，蒋晓鸽，曾 兵

（1.桂林电子科技大学信息与通信学院，广西桂林541004；2.保密通信重点实验室，四川成都610041）

0 引 言

入侵检测作为一种主动防御技术，可以有效地检测和阻断网络攻击。入侵检测系统按技术实现可分为误用检测和异常检测。异常检测因为可以检测新型的未知攻击行为，成为了研究的热点。

异常检测常用的方法有神经网络、决策树、聚类分析、贝 叶 斯 理 论、 支 持 向 量 机 （support vector machine，SVM）、K临近值算法等。其中，支持向量机［1］将基于结构风险化最小原则运用到异常检测中提高检测性能，具有较高的泛化能力和分类准确率。支持向量机也存在一些不足，一方面，其所需要的参与模型训练的标记数据较难获得；另一方面，其分类时采用的核函数的选取以及核函数的参数优化是一个较难解决的问题。针对上述问题，文献 ［2］通过对比分析几种特征去除方法，提出逐步特征剔除方法，以获得较高的检测率。文献 ［3］提出一种自动标记方法用于基于支持向量机的网络流量异常检测，通过剔除已知的入侵数据，构造不平衡数据集，提高对新型异常的检测能力。文献 ［4］提出一种基于Fisher分的特征提取算法，在保持分类精度不变情况下，降低训练时间和测试时间。文献 ［5］采用一种基于数据不一致率的快速特征提取算法，有效消除数据冗余，提高检测效率。

本文提出一种基于分类模型分类准确率计算的特征选择和支持向量机相结合的异常检测方法。该方法通过测试网络数据的每个特征对支持向量机分类模型的分类准确率，选取出分类准确率高的最优特征组合；并结合支持向量机分类方法进行异常检测。

1 基于特征选择和SVM的异常检测系统结构

异常检测的关键是如何准确、高效地进行数据的分类，即将网络中正常行为产生的数据视为正常类，将入侵行为产生的数据视为异常类。本文采用支持向量机建立数据分类模型，再通过分类模型进行数据分类。为提高检测准确率，在数据分类检测中采用了一种基于分类模型分类准确率计算筛选特征。基于特征选择和支持向量机的异常检测系统模型结构如图1所示。

图1 基于SVM的异常检测模型

在图1中，网络抓包模块采用Sniffer工具实现从网络中抓取数据包。

特征提取模块提取网络数据包的特征信息，构成一组关键特征组合。通常，对网络数据描述的特征有很多，但这些特征有主有次。在数据识别中，通过几个主要特征的组合就可以准确地识别数据。而次要的特征，不仅会增加系统开销，还可能混淆对数据的识别，降低检测的准确性。针对该问题，本文提出一种基于分类模型分类准确率计算的特征选择算法，通过计算每维特征进行数据识别的模型准确率，选取准确率最高的最优特征组合。

数据预处理模块将所提取的特征组合转换为适合于支持向量机处理的特征向量数据。由于支持向量机只能处理数值型的数据，因此，需要对所提取数据进行标准化和归一化处理，并完成数据类型的转换等。对已标记的正常或异常数据经预处理后，将组成训练集用于训练SVM分类模型，而未标记的数据预处理后则用来进行分类检测。

支持向量库模块用于存储SVM训练后所产生的支持向量。

SVM模型训练主要是对输入的训练集进行训练，产生数据分类模型。训练集是由特征向量和其相应的类别标号组成。其中，类别标号是用于区分数据正常或异常的一种标记，通常以 （1，－1）表示。当训练完成后可以产生新的区分正常或异常的分类模型，并将得到的新的支持向量替代原有的支持向量。当有新的训练数据并入时，将支持向量融入到训练数据中形成新的训练集进行训练。

SVM分类检测利用训练产生的分类模型和支持向量库对输入的未标记的数据进行分类检测。这些未标记的数据初始时标注一种自定义的预测标号，在分类检测后将变更为新的类别标号，标识其正常或异常。

输出响应模块则对检测出的异常数据做出报警响应。

2 特征选择算法

从实现网络行为的数据包中提取数据的特征是一项费时和困难的工作。在数据处理前，去除冗余或者不重要的特征，只提取有效识别网络行为的关键特征集，将有利于提高分类器的训练速度和检测精度。针对该问题，本文构造一种基于分类模型分类准确率计算的特征选择算法。该算法通过逐一选取特征向量中的每一维特征，建立相应的分类模型，以同一数据集分别作为训练集和测试集，分别测试各分类模型对不同类别数据的分类准确率；再根据分类准确率高低，选择分类准确率高的特征集构成最优特征组合。

为更好地描述该算法，先对相关概念进行描述。

定义1 特征向量是指网络数据中反映网络行为的相关特征集合。以F＝｛F1，F2，...，Fi，...，Fm｝表示某种网络行为的特征向量，其中，Fi为该特征向量中的第i维特征，1≤i≤m。

定义2 数据类别是指根据网络攻击行为的不同，将数据划分为相应的类别，如Normal、Probe、Dos、R2l、U2r等网络行为数据类别。以C＝｛C1，C2，...，Cj，...，Cn｝表示所划分的数据类别，其中，Cj表示所划分的第j种数据类别，1≤j≤n。

为评估所选特征对数据分类的影响，本文针对所选特征，采用支持向量机作为分类器建立分类模型，并分别测试各特征在分类模型中对不同类别数据的分类准确率。

定义3 分类准确率矩阵是在进行分类模型训练中通过测试、评估不同向量特征对不同类别数据进行分类的准确率构成的矩阵。以M （i，j）表示分类准确率矩阵，1≤i≤m，1≤j≤n；其中，矩阵的每一行代表以某特征建立分类模型后对不同类别数据进行分类而产生的准确率；每一列表示各特征建立分类模型后针对某类数据的分类准确率。

特征选择算法描述如下：

（1）设有 m 个特征F＝｛F1，F2，...，Fi，...，Fm｝，n个数据类别 ｛C1，C2，...，Cj，...，Cn｝；并初始化分类准确率矩阵M （i，j），其中，1≤i≤m，1≤j≤n；

（2）从F中选取特征Fi作为测试特征，利用Fi建立分类模型并测试各个类别数据的分类准确率；

（3）将各个类别数据的分类准确率｛A（Fi，C1），A（Fi，C2），...，A （Fi，Cj），...，A（Fi，Cm）｝存入 M（i，j）中，其中A（Fi，Cj）表示以特征Fi建立分类模型后对Cj的分类准确率；

（4）重复执行 （2）和 （3），直到k个特征测试结束；

（5）构造特征矩阵。在分类准确率矩阵M（i，j）的每一列中，若对Cj的分类准确率最高为A（Fi，Cj），则表明Fi对Cj分类影响最大。对M（i，j）中的每一列分别进行非递增排序，按照排序后的分类准确率，构造一个对应于准确率顺序的特征序列；通过对所有列排序并构造特征序列，形成一个特征矩阵M’（i，j）；

（6）在特征矩阵M’（i，j）中，选取第一行中对应的特征组合F’建立分类模型并测试其分类准确率A（F’，C’）；

（7）顺序选取矩阵M’（i，j）的下一行中对应的特征集，并将其并入到特征组合F’中，形成新特征组合F’’，利用F’’建立分类模型并测试其分类准确率A（F’’，C’’）；

（8）比较上述两组分类准确率A（F’，C’）和A（F’’，C’’），若分类准确率降低，即 A （F’’，C’’）≤A （F’，C’），则结束特征选择过程，并确定分类准确率最高的特征组合F’为最优特征组合。否则，重复执行步骤 （7）和（8），每次将矩阵M’（i，j）下一行的特征组合并入到前面建立的特征组合中，重新测试并比较其与前一次的分类准确率，直到循环结束或获得最优特征组合。

基于分类模型分类准确率计算的特征选择算法通过选取对分类影响最大的特征组合，降低了参与训练的特征维数，避免了冗余特征对分类检测的影响，提高了检测准确率，并降低了SVM模型在分类检测时的检测时间。

3 支持向量机分类方法

支持向量机分类方法是一种基于小样本的学习方法，它可将由网络连接提取并生成的特征向量映射到更高维空间里，并在此空间中寻求一个能够实现数据分类的最大间隔超平面。将数据分开的最大间隔越大，获得的数据分类误差越小。支持向量机的分类结果可由少数支持向量决定，其计算的复杂性取决于支持向量的数目，而不是样本的维数，从而避免了维数灾难。支持向量机分类算法是一种机器学习方法，需要利用训练集先训练出分类模型，然后才能利用分类模型对测试集进行预测分析。

设已 标 记 训 练 集 样 本 集 合 为： （y1，x1），（y2，x2），…，（yi，xi），…， （yl，xl）；其中，yi＝ ｛－1，1｝l为类别标号，1表示正常类，－1表示异常类；xi∈Rn，i＝1，……，l表示n维特征向量。

若要使样本在输入空间可分，则需要在特征空间中寻求如式 （1）所示的广义最优分类超平面，使两类样本到超平面的距离为最大

式中：ω——权重向量，b——偏移值。寻找最优分类超平面的过程实际上是个机器学习问题，其学习问题的核心是最小化求解下列问题

其中，惩罚因子C＞0，ξi为松弛变量，函数（x）用于将输入向量映射到高维特征空间。利用KTT（Karush－Kuhn－Tucker）最优化条件理论和用拉格朗日乘子法可将式 （2）变成其对偶形式

其中，K（xi，xi）＝（xi）T（xj）为核函数，用于将高维空间中的内积运算转换为低维空间的核函数计算，避免了维数灾难。αi和αj为拉格朗日乘子。

根据式 （3）的结果，利用式 （1）和其对偶式 （3）间的关系可得最优ω满足下式

对于未知属类的向量x，采用如下最终分类决策函数

在式 （5）中，可以选用不同的核函数构造不同的支持向量机。常用的核函数有多项式核函数、RBF核函数和Sigmoid核函数。本文采用综合性能最优的RBF［6－7］核函数。

由式 （1）可知，支持向量机分类超平面中含有大量未知参数，通过选取已标记数据参与训练，逐步获取最优参数，从而得到分类模型即分类决策函数。在分类检测时，利用已获得的分类模型，可将输入的待检测未知数据进行分类，输出数据的类别标号。根据类别标号，可判断其为正常或异常数据。

4 仿真实验分析

本文采用Kddcup99［8］数据集进行仿真实验。Kddcup99提供了一个10%的训练子集，其训练集给出了类别标号，本文在训练子集上进行实验。为了便于模型的训练，需要对Kddcup99数据集进行预处理，包括对字符类型数据的量化，以及数据的标准化和归一化处理。

在实验中，采用LibSVM［9－10］作为训练和测试工具，采用C－SVM、RBF核函数，参数c、g、h设为1.2、2.8和0。在Matlab R2011b下实现本文的特征选择算法和支持向量分类方法，并进行测试和仿真。实验测试机器操作系统为 Windows 7，处理器为Intel Core（TM）i3 2.13GHz，内存为2GB。

4.1 数据预处理

在实验中，从Kddcup99的10%训练子集中随机选取一部分作为训练集，从剩余的数据中再随机选取一部分作为测试集。

针对选取的数据集，先进行数据的量化，将数据集中的字符型数据转换为数值型数据，如设置协议类型中的tcp为1，服务类型中的http为1，标志位中的sf为1，等。

其次，针对量化的数据，为避免量化取值的不同而对分类产生影响，进行数据标准化处理。以Zij表示第i条数据记录第j个属性的标准化结果，则Zij的计算方法如下

式中：xij——第i数据记录的第j个属性值；mj——所有数据记录第j个属性的平均值；Sj——所有数据记录第j个属性的平均绝对偏移。

第三，进一步对标准化的数据集采用线性函数转换方法进行归一化处理。以Yij表示数据归一化后的结果，则

式中：zij——第i数据记录的第j个属性的标准化值，

zmax——所有数据记录中第j个属性标准化后的最大值，

zmin——所有数据记录中第j个属性标准化后的最小值。

4.2 实验测试及结果分析

首先采用本文基于分类模型分类准确率计算的特征选择算法对数据集的41维特征进行特征筛选。在测试中，从Kddcup99的10%训练子集中以正常与异常数据比为4∶1的比率随机选取约1万条记录作为测试集，并按照上述的数据预处理方法进行处理。在此基础上，采用本文提出特征选择算法建立分类模型并进行特征筛选，构成最优特征组合。本实验通过计算、比较，测得由矩阵中前三行特征组合构成的最优特征组合具有最高的分类准确率，其包括了8个特征，分别为第1、2、3、5、6、23、33、36维特征。

其次，从Kddcup99的10%训练子集中随机选取约3万条记录作为训练集，从剩余的数据中再随机选取约1万条记录作为测试集，通过数据预处理，采用筛选出的最优特征组合，测试了其检测准确率、误报率、建模时间及测试时间，并与不进行特征选择的原始41维特征集测试结果进行对比，结果见表1。

表1 不同特征集的测试结果对比

通过表1可以看出，特征选择后误报率有所增加，但其检测率有所提高，且大幅度降低了测试时间，提高了检测效率。

第三，在上一组所选择并进行了数据预处理的训练集和测试集上，进一步对比测试了本文方法、文献 ［2］中的GFA方法、文献 ［5］中的数据不一致率算法和文献 ［6］中的KPCA算法，筛选的特征向量根据相关文献的方法获得。测试结果见表2。

表2 本文方法和其它方法的对比测试结果

表3的结果显示，本文方法的误报率和建模时间略高于其它的方法，测试时间与其它方法相近，但其具有最高的检测准确率。且本文方法在数据检测时提取的特征维数少，也有效降低了系统的数据处理难度。

5 结束语

针对入侵检测中的特征提取和检测准确率问题，本文提出一种基于特征选择和SVM相结合的异常检测方法。该方法采用基于分类模型分类准确率计算的特征选择算法，筛选出尽量少但能够准确识别数据的最优特征组合，并将其与支持向量机分类算法相结合，以获得好的检测效果。实验测试结果表明，本文方法有效提高了检测准确率，降低了检测时间，并降低了系统的数据处理难度。在将来的工作中，将进一步分析不同的核函数对分类准确率的影响并进行优化，降低误报率。

［1］WANG Yanhua，TIAN Shengfeng，HUANG Houkuan.Feature weighted support vector machine ［J］.Journal of Electronics ＆Information Technology，2009，31 （3）：514－518 （in Chinese）.［汪延华，田盛丰，黄厚宽.特征加权支持向量机［J］，电子与信息学报，2009，31 （3）：514－518.］

［2］Li Y.An efficient intrusion detection system based on support vector machines and gradually feature removal method ［J］.Expert System with Applications，2012，39 （1）：424－430.

［3］Carlos A Catania，Facundo Bromberg.An autonomous labeling approach to support vector machines algorithms for network traffic anomaly detection ［J］.Expert Systems with Applications，2012，39 （2）：1822－1829.

［4］ZHANG Xueqin，GU Chunhua.A method of feture extraction［J］.Journal of South China University of Technology（Natural Science Edition），2010，38 （1）：81－86 （in Chinese）. ［张雪芹，顾春华.一种网络特征提取方法 ［J］.华南理工大学学报（自然科学版），2010，38 （1）：81－86.］

［5］CHEN Tieming，MA Jixia，XUAN Yiguang.Fast feature selection method and its application in intrusion detection ［J］.Journal of Communications，2010，31 （9A）：233－238 （in Chinese）.［陈铁明，马继霞，宣以广.快速特征选择方法及其在入侵检测中的应用 ［J］.通信学报，2010，31 （9A）：233－238.］

［6］BAO Panqing，YANG Mingfu.Network intrusion detection based on KPCA and SVM ［J］.Computer Application and Software，2006，23 （2）：125－127 （in Chinese）. ［包潘晴，杨明福.基于KPCA和SVM的网络入侵检测 ［J］.计算机应用与软件，2006，23 （2）：125－127.］

［7］Hsu C W，Chang C C，Lin C J.A practical guide to support vector classification ［EB／OL］.［2010－04－15］.http：／／www.csie.ntu.edu.tw／～cjlin／papers／guide／guide.pdf.

［8］KDD Cup 99KDD dataset ［EB／OL］.［2011－06－16］.http：／／kdd.ics.uci.edu／databases／kddcup99／kddcup99.html.

［9］LibSVM ［EB／OL］.［2011－04－01］.http：／／www.csie.ntu.edu.tw／～cjlin／libsvm／index.html.

［10］Chang ChihChung，Lin ChihJen.LIBSVM：A library for support vector machines ［J］.ACM Transactions on Intelligent Systems and Technology，2011，2 （3）：1－27.