基于主成分分析禁忌搜索和决策树分类的异常流量检测方法

摘 要：

真实网络流量包括大量特征属性，现有基于特征分析的异常流量检测方法无法满足高维特征分析要求。提出一种基于主成分分析和禁忌搜索（PCATS）的流量特征选择算法结合决策树分类的异常流量检测方法，通过PCATS对高维特征进行特征约减和近优特征子集选择，为决策树分类方法提供有效的低维特征属性，结合决策树分类精度和处理效率高的优点，采用半监督学习方式进行异常流量实时检测。实验表明，与传统异常检测方法相比，此方法具有更高的检测精度和更低的误检率，其检测性能受样本规模影响较小，且对未知异常可以进行有效检测。

关键词：异常检测； 决策树； 特征选择； 主成分分析； 禁忌搜索

0 引言

随着网络技术的不断发展和普遍应用，互联网安全的重要性越发凸显。网络异常中的各种攻击异常频繁发生，严重威胁着网络的正常使用。因此如何及时有效地检测网络异常，保证安全的网络环境具有重要的意义。

网络流量异常检测方法主要包括两种：统计分析[1]和机器学习[2]。基于统计的方法具有较高的检测实时性，而检测精度较低，尤其对许多隐蔽攻击无法检测；机器学习方法基于流量特征进行分析检测，由于具有较高的检测精度而成为主要研究方向。基于机器学习的异常检测主要包括聚类方法[3]和分类方法[4]：聚类方法具有无需事先样本的优点，但聚类误差导致检测精度较低；分类方法需要事先进行训练，通过训练模型进行检测，这种方法由于具有较高检测准确性而广泛使用[5-6]。基于分类的异常检测中，特征属性选择对分类精度具有重要影响[7]，实际网络流量维数较高，高维数据无法应用于传统分类算法中，文献[8-10]分别采用支持向量机（Support Vector Machine，SVM）、K最近邻（KNearest Neighbor，KNN）和C4.5算法进行分类检测时都采用低维特征，由于其对特征属性的选择不能较好表征网络流量，造成分类精度较低，影响了检测效果。文献[8]采用SVM方法进行异常分类检测，但SVM适用于较少流量样本使得该方法无法应用于实际网络流量检测。文献[9]采用直推式的异常检测方法具有较高的检测精度，但基于“离线训练，在线检测”的机制下，由于KNN方法需要对每个样本所属类别进行判断而降低了检测效率。文献[10]利用决策树方法具有较低处理时间的特点而基于C4.5决策树算法进行异常流量实时检测，但C4.5根据信息增益率进行节点划分，由于增益值的不稳定导致分类误差较大。

基于此，本文提出了一种基于主成分分析和禁忌搜索（Principal Component Analysis and Tabu Search，PCATS）结合基于最短距离划分决策树（MinDistance Decision Tree， MDDT）分类的异常流量检测方法，通过PCATS方法来减少高维特征空间冗余和选择最优特征子集，为分类检测提供低维和有效的流量属性，结合决策树检测实时性高的特点，该方法可以有效地进行网络流量异常实时检测。

1 相关研究

1.1 基于PCATS的特征选择方法

1.1.1 主成分分析算法

主成分分析（Principal Component Analysis， PCA）是统计学中分析数据的一种有效方法，主要用于特征抽取和数据降维。其思想是利用数据集统计性质的特征空间变换，将一个数据维数较高且互相关联的数据集进行降维。通过PCA降维后，将原始空间转换为新的主成分空间，且各主成分互不相关。

假设含有N个样本的网络流量数据集X={x1，x2，…，xm}∈Rn，其中：Rn为特征空间，m为特征维数。求得变量空间Z={z1，z2，…，zk}，满足k

在使用PCA进行分析时，由于数据中不同的变量往往有不同的量纲，会引起各变量取值的分散程度差异较大，从而影响计算精度。为了消除由于量纲的不同可能带来的影响，首先需要对变量进行标准化处理，然后利用PCA进行降维。

0 引言

随着网络技术的不断发展和普遍应用，互联网安全的重要性越发凸显。网络异常中的各种攻击异常频繁发生，严重威胁着网络的正常使用。因此如何及时有效地检测网络异常，保证安全的网络环境具有重要的意义。

网络流量异常检测方法主要包括两种：统计分析[1]和机器学习[2]。基于统计的方法具有较高的检测实时性，而检测精度较低，尤其对许多隐蔽攻击无法检测；机器学习方法基于流量特征进行分析检测，由于具有较高的检测精度而成为主要研究方向。基于机器学习的异常检测主要包括聚类方法[3]和分类方法[4]：聚类方法具有无需事先样本的优点，但聚类误差导致检测精度较低；分类方法需要事先进行训练，通过训练模型进行检测，这种方法由于具有较高检测准确性而广泛使用[5-6]。基于分类的异常检测中，特征属性选择对分类精度具有重要影响[7]，实际网络流量维数较高，高维数据无法应用于传统分类算法中，文献[8-10]分别采用支持向量机（Support Vector Machine，SVM）、K最近邻（KNearest Neighbor，KNN）和C4.5算法进行分类检测时都采用低维特征，由于其对特征属性的选择不能较好表征网络流量，造成分类精度较低，影响了检测效果。文献[8]采用SVM方法进行异常分类检测，但SVM适用于较少流量样本使得该方法无法应用于实际网络流量检测。文献[9]采用直推式的异常检测方法具有较高的检测精度，但基于“离线训练，在线检测”的机制下，由于KNN方法需要对每个样本所属类别进行判断而降低了检测效率。文献[10]利用决策树方法具有较低处理时间的特点而基于C4.5决策树算法进行异常流量实时检测，但C4.5根据信息增益率进行节点划分，由于增益值的不稳定导致分类误差较大。

基于此，本文提出了一种基于主成分分析和禁忌搜索（Principal Component Analysis and Tabu Search，PCATS）结合基于最短距离划分决策树（MinDistance Decision Tree， MDDT）分类的异常流量检测方法，通过PCATS方法来减少高维特征空间冗余和选择最优特征子集，为分类检测提供低维和有效的流量属性，结合决策树检测实时性高的特点，该方法可以有效地进行网络流量异常实时检测。

1 相关研究

1.1 基于PCATS的特征选择方法

1.1.1 主成分分析算法

主成分分析（Principal Component Analysis， PCA）是统计学中分析数据的一种有效方法，主要用于特征抽取和数据降维。其思想是利用数据集统计性质的特征空间变换，将一个数据维数较高且互相关联的数据集进行降维。通过PCA降维后，将原始空间转换为新的主成分空间，且各主成分互不相关。

假设含有N个样本的网络流量数据集X={x1，x2，…，xm}∈Rn，其中：Rn为特征空间，m为特征维数。求得变量空间Z={z1，z2，…，zk}，满足k

主成分分析通过选择贡献率较大的几个特征值λi对应的特征向量P作为主成分，达到降维的目的。特征贡献率如下式计算：

1.1.2 禁忌搜索算法

禁忌搜索（Tabu Search， TS）算法是一种启发式全局寻优搜索方法，其通过标记已搜索局部最优解和避免迭代计算中重复搜索来获得全局最优解[11]。TS主要思想是：首先确定一个初始有效解z， 对每个解z定义一个邻域Y（z），从当前解的邻域中确定若干的候选解，从中选出最佳候选解。选择最佳候选解是一个搜索过程，为了避免搜索过程限于循环，TS算法通过构造禁忌表和定义停止规则避免了搜索算法的局部最优。其中禁忌表存入前n次禁忌长度，避免了回到原先的解，从而提高了解空间的搜索能力；停止规则定义在若干迭代次数内最优解无法改进时，算法停止。另外禁忌搜索算法中涉及邻域、禁忌表、禁忌长度、特赦规则和初始解等都会直接影响搜索优化结果[12]。

基于禁忌搜索的特征选择是通过目标函数进行约束的最优化问题，合适的目标函数提高了搜索和最优特征选择的质量。一个好的特征解应在最少的特征数量上保证尽可能多的分类信息。在信息论理论中，一个属性的信息增益越大，其包含的信息量也越大，基于信息增益可以有效评估特征向量的分类信息，因此本文选择信息增益作为目标函数。定义目标函数如下：

禁忌搜索中初始解的选择对禁忌搜索的效果影响很大，在基于网络流量特征的最优特征选择中，由于实际网络流量特征维数较大，会影响禁忌搜索算法的效率，同时网络流量特征的冗余也对最优特征集的选择产生影响。因此禁忌搜索的初始解对搜索效率和质量具有重要影响。

1.1.3 PCATS特征选择算法

特征选择是从特征集CT={c1，c2，…，cn}中选择一个子集CT′={c′1，c′2，…，c′n}，c′≤c。其中：c为原始特征空间大小，c′为特性选择后新特征空间大小。即：通过从原始特征空间中选择部分有效特征组成新的低维特征空间，其本质为一个寻优过程。

网络流量特征属性空间的“维数灾难”严重降低了基于特征分析方法的效率，而这些特征中存在大量的冗余和弱特征属性，需要通过特征约减来去除冗余和弱属性，得到精简特征属性向量。PCATS方法通过PCA对高维特征向量进行有效降维，为禁忌搜索提供了低冗余和低维数的特征向量。结合禁忌搜索寻找近优特征子集的特点，提高了禁忌搜索的效率和精度。因此通过PCATS可以在高维特征空间中寻找最优特征子集。PCATS方法具体步骤如下：

步骤1 禁忌表置空，设置初始化参数：禁忌长度LJ=13，最大迭代次数Dmax=600，最大改进次数max=100。

步骤2 使用PCA对原始网络流量特征进行约减，得到约减特征集T={T1，T2，…，Tp}，p为约减后特征集数量。

步骤3 对特征集T进行二进制编码，得到初始解RinitN。

步骤4 设置终止条件，当达到Dmax时，搜索停止；当通过max寻找最优解无改进时，停止搜索。

步骤5 判断是否满足终止条件，如果满足终止条件，结束运算，输出最优特征子集；否则转到下一步。

步骤6 初始解RinitN代入邻域结构计算邻域解，通过目标函数选择最佳候选解。

步骤7 判断候选解是否满足特赦规则，如果满足，则更新禁忌表中最优解，转入步骤4；否则转到下一步。

步骤8 计算候选解的禁忌属性，选择非禁忌对象的最优值替换禁忌表的最初值，转入步骤4。

步骤9 结束，输出最优特征子集。

1.2 C4.5决策树方法

决策树方法作为一种机器学习方法中的预测模型，代表对象属性和对象值之间的映射关系，它能从无规则的实例集合中归纳出一组采用树形结构表征的分类规则。常用的决策树方法包括：ID3算法、CART算法和C4.5算法等。与其他算法相比，C4.5决策树方法由于具有较高的处理效率和分类稳定性，适用于网络流量的实时分类[13]而在网络流量分类中广泛使用。

决策树创建中内部节点分枝的选择是关键，对于不同划分得到的决策树的性能不同，传统C4.5算法利用信息熵原理，选择信息增益最大的属性作为分类属性。定义样本集S的理想划分S={s1，s2，…，sn}，则信息增益率为

C4.5方法采用信息增益率来确定节点的分枝，文献[14]分析了采用这种方法带来的问题：划分产生的分割信息很小时，增益的值不稳定。这种不稳定可能导致信息增益率很大或者为0，带来较大分类误差。本文采用最短距离划分方法来构建决策树，定义Mantaras范氏距离[15]为两个划分间的距离，采用与理想划分距离最近的属性作为当前节点的测试条件。

定义特征属性pi作为测试条件p得到的划分S′={s′1，s′2，…，s′m}，则理想划分S和划分S′的Mantaras范氏距离为：

决策树训练中可能存在过度拟合，这会对新的数据集分类效果产生影响，因此要对初始决策树进行剪枝，从而得到一般的分类规则。本文利用训练数据集中剩余样本，采用悲观错误剪枝（Pessimistic Error Pruning，PEP）算法对生产初始决策树进行剪枝，PEP算法对每棵子树只进行一次检查，具有较快的处理速度。且本方法不需要额外数据集，结合PEP算法可使本方法适用于样本较多数据集。

2 基于特征分类的检测模型

基于特征分类的检测模型如图1所示。首先对网络流量进行提取特征和数据预处理，得到待检测特征向量。离线训练阶段首先需要对高维特征空间通过特征选择进行降维，得到最优特征子集形成训练集，分类训练利用分类算法MDDT得到正常和异常类别，分类训练结果对检测规则库更新实现异常检测。

图片

图1 基于特征分类的检测模型

2.1 数据预处理

网络流量提取的特征中，包含不同数据类型：名词型和数值型等，且不同特征量纲也不同，这种差异会影响分类精度，所以需要将样本的属性值转换为标准的取值空间。本文对于数值型样本属性进行归一化处理，而对于如协议类型、服务类型等名词型属性根据其每个取值在取值空间的出现频次进行标准化处理。归一化方法为：

首先计算样本中每个特征属性的均值和方差：

2.2 特征选择

网络流量的统计特征指的是在报文（packet）和流（flow）的属性中，抽取和端口及协议无关的特征，如报文长度、报文到达间隔时间、报文数量、流的持续时间和流中报文个数等，这些统计特征用特征矢量来表示。如一条网络流F，基于该流的特征描述可表示为F={y1，y2，…，yn}，其中yi代表特征的取值。流的特征集合可能包含多达几百个特征，通过特征选择寻找少量最优特征子集来近似描述流量对提高学习效率等具有重要意义。

在基于网络流量特征的流量分析中，一般情况下，特征数量越大，会产生更高的分析精度。但实际中，过大的特征空间会产生两个问题：1）巨大的特征空间不仅需占用更多的存储空间，而且增加了测量时间，难以应用于实时流量分析中；2）网络流量特征存在大量冗余和弱属性，这些属性不仅降低了分析精度，而且增加了算法处理的复杂度。本文采用PCATS算法，对网络流量初始特征经过PCA进行降维，大大减少了特征冗余和弱属性，给禁忌搜索算法提供了更优的初始解，通过禁忌搜索得到全局最优特征子集，为后续分类算法处理降低了处理时间。

基于特征选择的分类中，不同研究人员选取不同维度的特征向量，典型的选择维度包括37[7]、36[16]和22[17]等。这些特征主要包括流信息（时间、包个数、字节数），包内部时间信息，TCP/IP控制域信息，ACK数量，负载大小，五元组信息等。这些选取方案都是根据表征流量的常用特征如时间，长度信息进行选择，未考虑特征的贡献度及存在的冗余。

本文根据PCATS方法对高维流量特征向量进行最优特征子集选择，提取了22种网络流量特征作为分类训练集的特征库，与传统特征选择方法相比，去除了TCP/IP控制信息、ACK信息等对网络流量表征贡献度较低的特征信息。然而在网络流量表征中，五元组信息表征存在冗余[18]，而基于信息熵的源/目的IP地址对异常流量的表征具有较大贡献度，因此本文采用22个特征属性结合归一化熵的源/目的IP作为最终24个特征属性。选择的特征属性向量如图2所示，其中横坐标为提取的特征属性，纵坐标为Moore数据集中每个特征属性在数据集中所占的比例。

图片

图2 最优特征子集选择

2.3 分类训练

分类方法按照其对标记数据的依赖关系可以分为完全监督学习、无监督学习和半监督学习。完全监督学习分类准确性相对较高，但其完全依赖标记数据样本，这种方法代价昂贵无法应用于实际分类中；无监督学习一般采用聚类算法，无需标记数据进行训练，但其分类准确性较低；而半监督学习通过引入少量标记样本进行训练，不仅提高了训练器性能，而且可以对未知类型进行分类，因此本文采用半监督学习进行分类。

分类算法的选择要求具有较高分类准确性，针对网络流量大样本数据特性能有效实现分类，并且对于分类算法的实时性具有较高要求。文献[5]比较了C4.5和贝叶斯分类器的性能，发现C4.5决策树算法测试时间最短，更适合实时流量识别。本文选择基于C4.5的改进算法进行异常检测分类基于两点考虑： 1）与SVM算法对于小样本的机器学习相比，C4.5对任何样本规模都具有较好分类精度；2）C4.5的结构可以建立方便的规则库。

利用MDDT算法处理分类问题通常分为两步：首先通过训练集进行学习，得到分类模型，然后通过生成的分类模型对流量进行分类。为了满足实时流量分类要求，采用“离线训练，在线识别”机制，在离线构建分类模型中，根据网络流量动态变化进行主动学习，提高分类模型的寿命和分类算法的泛化能力。

3 实验结果及分析

为了验证本文方法的有效性和可靠性，本章采用研究领域普遍使用并认可的数据集Moore和KDD CUP 1999进行实验分析。在基于特征分类的异常检测中，分类的性能对检测效果有直接影响。采用Moore_Set对基于PCATS的分类方法性能进行验证，通过KDD CUP 1999数据集对本文提出的异常检测方法性能进行分析。

3.1 实验数据和环境

3.1.1 KDD CUP 1999数据集

为了评价本文算法对于异常检测的效果，选用Lincoln实验室的KDD CUP 1999网络数据集进行实验。该数据集包括多种网络环境下的攻击异常，主要包括DoS、R2L、U2R和Probing四类。KDD CUP 1999数据集包括大约4900000条记录，4种异常类别和正常类别（Normal）分别通过41个特征属性表征。

为了验证本方法的检测效果，将KDD CUP 1999数据集进行提取，构建三个数据集进行测试。数据集1包括205684个正常流量数据和2648个攻击异常数据；数据集2对数据集1正常数据进行提取，包括120000个正常流量数据和2648个攻击异常数据；数据集3对数据集 1正常数据进行少量抽取，包括10000个正常流量数据和2648个攻击异常数据。三种数据集具体介绍如表1所示。

其中R为特征贡献率阈值，特征维数m选择根据R来确定，一般选择R为85%～95%。

3.1.2 实验环境及工具

本文采用的实验仿真硬件平台为普通PC，该主机配备操作系统为Windows XP Professional SP3，具体配置：CPU为Intel Core2 1.86GHz；内存2GB。实验仿真软件工具采用Matlab 2008和Weka3.6.8。

本文采用异常检测方法中通用检测指标：检测率（True Positive， TP）和误报率（False Positive， FP）作为检测本方法的评价指标。其中分类算法通过准确率（precision）来表征，定义如下：

其中：Ntp表示类型为A的网络流量样本被分类模型正确分类的数量；Nfp为类型为非A的网络流量样本被分类模型分类为类型A的数量。

3.2 实验结果及分析

3.2.1 特征选择分析

对Moore_set数据集（样本个数为22932）分别取不同数量的特征进行特征分类，通过比较分类精度来分析特征数量对流量表征的影响，结果如图3、图4所示。

在使用PCA进行分析时，由于数据中不同的变量往往有不同的量纲，会引起各变量取值的分散程度差异较大，从而影响计算精度。为了消除由于量纲的不同可能带来的影响，首先需要对变量进行标准化处理，然后利用PCA进行降维。