基于KNN离群点检测和随机森林的多层入侵检测方法

任家东 刘新倩 王 倩 何海涛 赵小林

1(燕山大学信息科学与工程学院 河北秦皇岛 066001)2(河北省软件工程重点实验室(燕山大学) 河北秦皇岛 066001)3(北京理工大学软件学院 北京 100081)4 (软件安全工程技术北京市重点实验室(北京理工大学) 北京 100081) (jdren@ysu.edu.cn)

随着计算机和网络服务的不断发展，计算机和网络的安全已经成为一个重要的问题.网络中异常行为的检测已经成为网络安全领域重要的研究内容.入侵检测系统用来检测和分析网络数据，标识异常的网络行为.通常来讲，入侵检测系统主要分为2类：基于误用的入侵检测系统和基于异常的入侵检测系统[1].基于误用的入侵检测系统可以有效地检测出已知的攻击类型，例如Snort入侵检测系统[2].这种类型的入侵检测系统误报率较低，但是不能很好地识别网络中新的攻击类型.基于异常的入侵检测系统能够根据正常的网络行为建立检测模型，识别出正常行为的偏差值，从而识别网络异常行为[3].这种类型的入侵检测系统能够检测出新的或未知的攻击类型，但又有较高的误报率.

为了降低基于异常的入侵检测系统的误报率，许多数据挖掘和机器学习方法，例如支持向量机(support vector machine， SVM)和神经网络，被应用到入侵检测系统中.目前的许多研究将特征选择或特征提取的方法与一些机器学习的方法相结合，来提高入侵检测系统的准确性，同时降低算法的运行时间.Raman等人[4]提出将超图、遗传算法和支持向量机相结合来实现入侵检测系统.超图和遗传算法用于实现支持向量机模型的参数估计和特征选择，支持向量机用来对特征选择后网络数据进行异常检测，证明了特征选择方法和支持向量机结合可以提高数据识别的准确率.Khammassi等人[5]采用遗传算法和逻辑回归算法进行特征选择，选取最优的特征子集.通过不同的决策树算法证明本方法选取的特征子集对于入侵检测是有效的.Aljawarneh等人[6]采用信息增益来选取重要特征，并提出一种混合投票模型，结合J48，Meta Paging，Random Tree等方法来识别异常数据，该方法能够提高检测的准确性，降低误报率.George[7]选择支持向量机和主成分分析来执行网络数据的异常检测，与贝叶斯分类算法和信息增益降维方法的分类效果进行比较，并证明主成分分析和信息增益降维方法都能改善贝叶斯分类算法的效果，但会降低支持向量机的分类效果[8].

除了上述方法外，一些方法还侧重于研究数据集中数据项的选取，通过采用聚类方法或抽样方法来选取部分有代表性的训练数据.该训练数据与机器学习算法相结合，可以显著降低分类器的训练时间并提高分类的准确率.程晓旭等人[9]采用改进的K-means算法得到全局的最优的聚类划分，降低了异常检测的时间复杂度.Alyaseen等人[10-12]将改进的K-means方法与机器学习方法相结合来构建入侵检测模型.改进的K-means方法能发现数据之间相似的结构或模型，从而能够降低数据集的长度，得到一个高质量的数据集.将改进的K-means与C4.5结合来构造入侵检测模型的分类器，大大降低了入侵检测系统的运行时间[10]；与支持向量机算法相结合有效的提高了异常数据类型DoS(denial of service)，R2L(remote to local)，U2R(user to root)的检测率[11]；与支持向量机和极限学习机(extreme learning machine， ELM)的混合模型相结合来提高入侵检测系统的准确性和效率[12].Roshan等人[13]提出一种自适应的入侵检测系统结合聚类和极限学习机模型，该方法能够以较小的代价检测出已知的和新型的攻击.Enamul等人[14]采用抽样技术与最小二乘支持向量机(least square support vector machine， LS-SVM)的混合模型，抽样技术选择最有代表性的训练数据集，最小二乘支持向量机对网络数据进行分类，标识异常数据类型.

尽管对于网络异常行为检测的研究很多，但仍然存在着某些异常行为(例如Probe(probing)，U2R，R2L)的检测率较低以及各类别检测不均衡的问题.本文主要针对这一问题，提出一个新的混合模型，结合KNN(Knearest neighbors)离群点检测算法和多层随机森林算法来建立入侵检测模型.采用KNN离群点检测算法获取一个小规模、高质量的训练数据集.在此训练数据集上，结合类别检测划分方法，构建多层次的随机森林模型，检测网络异常行为.基准数据集KDD(knowledge discovery and data mining) Cup 1999用来评估本文算法的正确性和检测性能，并在不同大小的测试数据集上验证本文算法的扩展性.

Fig. 1 The entire flow of the proposed method图1 本文算法的整体流程图

1 基于KNN离群点检测和随机森林的多层入侵检测方法

本节描述提出的方法结合数据选取和多层随机森林算法来进行入侵检测.该方法主要包括4个阶段：1)对训练数据集和测试数据集进行预处理;2)数据选取阶段，得到一个新的规模小、质量高的训练数据集;3)采用新的训练数据集训练多层的随机森林分类器;4)测试校准测试数据集.最终得到测试数据集中正常行为和异常行为的检测结果.本文算法的整体流程如图1所示：

在基准数据集KDD Cup 1999中，10%的训练数据集具有数据量大和数据类别不平衡的问题，该数据集被完全用于分类器时，存在许多引人注意的问题.首先是训练器的训练时间会非常长，可能会因为内存溢出而导致训练失败.其次，因为数据之间的不平衡，导致训练器在分类性能上更偏向于数量较多的类别，使得类别Probe，U2R，R2L的分类准确性偏低.因此本文对训练数据集进行数据抽取，从而降低数据集的大小，并得到新的高质量的训练数据集.

1.1 基于KNN离群点检测的数据选择方法

该部分采用KNN离群点检测算法对数据进行选择.KNN离群点检测算法是一种基于距离的离群点检测算法，最早由Knorr等人在1998年提出.该方法是在KNN的基础上发展而来的，是一种比较简单且易于应用的离群点检测算法.KNN离群点检测算法的基本思想是通过计算数据集D中每个数据与数据集D中其他数据的K近邻平均距离，并对每个点的K近邻平均距离进行降序排序，距离最大的前N个点被认为是离群点.在本文中，离群点被认为是分布稀疏且离高密度的群体较远的点.在数据选择时，删除数据集D中的N个离群点，得到新的数据集D′，新数据集的大小为M=|L-N|，L为原数据集D的大小.

在采用KNN离群点检测算法进行数据选择之前，先将训练数据集分为5类：Normal，Probe，DoS，U2R，R2L，在每一类数据集上执行KNN离群点检测算法，得到一个新的规模小、质量高的训练数据集，该数据集可以有效地改善多层随机森林分类器的训练时间和性能.在网络流量中，由于攻击行为U2R和R2L的样本数量的所占比例非常少，在分类效果上处于劣势，因此U2R和R2L类型不执行离群点删除操作.在Normal，Probe，DoS这3个类别上执行离群点检测算法，每个类别的离群点检测算法设置不同的参数M和K.在本文中通过多次实验获得每个类别中最优的参数M和K，从而得到最优的网络异常行为的检测率.算法1展示了根据KNN离群点检测算法选取新的训练数据集的详细步骤.

算法1. 基于KNN离群点检测的数据选择算法.

输入：10%的训练数据集TD、参数KNormal,MNormal,KProbe,MProbe,KDoS,MDoS;

①DNormal,DProbe,DDoS=∅;*存储不同类别的数据集合*

② for eachdinTD

③ if (d.label==1) thenDNormal.add(d);

④ else if (d.label==2) thenDProbe.add(d);

⑤ else (d.label==3) thenDDos.add(d);

⑥ end if

⑦ end for

produceKOD(D,K,M)

①L=D.length;*数据集D的大小*

②Avg[L],Index=∅;*Avg中存储每条数据的K近邻平均距离,Index中存储前M个数据的索引值*

③d[L]=∅;*存储数据之间的欧氏距离*

④ for (i=0;i

⑤ for (j=0;j

对一个人而言，对国家的认同关系到个人的心灵归宿与肉体归宿，个人在认同国家的同时也享受着这个身份带来的归属感与安全感，因此无论对于任何人而言，国家层面的身份认同与心理认同对于个人生存、成长都是十分重要的，也是个体社会政治化的重要内容。

⑥ 计算数据D(i)和D(j)之间的欧氏距离d[j];

⑦ end for

⑧ 对d进行升序排序;

⑨ 计算d中的前K个数据的平均值Avg[i];

⑩ end for

1.2 多层随机森林模型

随机森林(random forests, RF)最早是由Leo[15]作为一个分类算法提出的，广泛应用于入侵检测和计算生物学等方面.该算法的优势在于：该算法是一种集成学习方法，对于任何类型的数据集，随机森林算法的分类效果和聚类效果要优于大多数算法，并且能够有效处理高维度的数据集.该算法对于参数的设置并不敏感，可以很容易地找到一个合适的随机森林模型.随机森林算法是一个组合分类器，以决策树为基础分类器.该模型的基本思想是：一个森林包含多个决策树，每棵决策树是由有放回的随机抽样样本构造的，也就是说在总的训练集中的有些样本可能多次出现在1棵树的训练集中，也可能从未出现在1棵树的训练集中，并使每棵决策树进行充分生长，不进行任何剪枝，最终的输出结果就是所有决策树进行多数投票的结果.

本文提出以随机森林模型作为基础分类器来构建多层的异常检测分类器.为了更有效地检测异常行为，提出一种新的类别检测划分方法，该方法与多个的随机森林分类器相结合来构建多层的异常检测分类器.新的划分方法和多层随机模型结构如图2所示.该模型包含4个随机森林分类器，第1个分类器(RF1)将数据分为2组：Group1和Group2，Group1包括DoS和Probe，Group2包括Normal，U2R，R2L；第2个分类器(RF2)区分DoS和Probe；第3个分类器(RF3)检测R2L；第4个分类器(RF4)是检测U2R和Normal.根据经验将随机森林模型中树的数量设置为150.

Fig. 2 Multi-level random forests model图2 多层随机森林模型

根据网络流量的相似性，本文提出一种新的类别检测划分方法.该划分方法首先将网络数据划分为2组.对于第1组来说，DoS和Probe在流量特征上更相似，同时与其他的类别有更少的相似性，因此将这2个类别的数据分为1组.对于第2组来说，当发生U2R和R2L攻击时，此时的流量特征与正常的连接区别很小，Normal，U2R，R2L在流量特征上更相似[16]，因此将这3种类别分为1组.这种划分尽可能避免了异常行为在检测时的相互干扰，尤其是异常行为Probe，U2R，R2L的检测.在网络数据中，攻击类型的数目要远小于正常连接的数目，其中Probe，U2R，R2L类别的数据所占的比例非常小，这就使得异常行为检测算法需要在检测率与误报率之间寻找一个平衡，尽可能多得检测出攻击行为，同时避免将正常行为误检为攻击行为.DoS属于大流量的攻击行为，检测相对更容易一些.U2R和R2L属于明显的小流量攻击，并且造成的危害更大，其中U2R被认为是网络中最危险的行为[17].Probe是对网络的扫描和检测，被认为是多种严重攻击的前提行为.因此对Probe，U2R，R2L的检测是至关重要的.与其他算法相比，本文提出的划分方法和多层的随机森林模型能有效地检测出Probe，U2R，R2L，并在所有类别的检测间取得一个平衡，因此，本文提出的划分法和检测模型是合理和有效的.

2 实验结果

本节评估本文提出的算法的性能，所有的实验均在Windows 7 PC，Inter®Pentium®CPU G2020 @2.90 GHz，4.00 GB RAM环境中实现.采用MATLAB 7.8.0实现本文的算法.

2.1 训练集与测试集

KDD Cup 1999数据集是入侵检测领域的基准数据集，被广泛用于入侵检测系统的研究中.该数据集一共包括41个属性和1个类别标签(正常或其他的攻击类型)，其中7个属性(属性2，3，4，7，12，14，22)是离散属性，其他属性是连续属性.在离散属性中属性2，3，4是符号属性，其他是数值属性.这41个属性可以分为4类：TCP连接基本特征、TCP连接内容特征、基于时间的网络流量统计特征和基于主机的网络流量统计特征，如表1所示.数据集中异常数据类型分为4类：DoS，Probe，U2R，R2L.KDD Cup 1999数据集提供了训练和测试数据集.10% KDD训练数据集包括22种攻击类型，测试数据集中还包括额外的17种攻击类型.KDD Cup 1999训练数据集和测试数据集的详细信息如表2所示.

Table 1 Attributes of KDD Cup 1999 Dataset表1 KDD Cup 1999数据集的属性

Table 2 Details of Training Dataset and Testing Dataset in KDD Cup 1999表2 KDD Cup 1999训练数据集和测试数据集中不同类别数据的详细信息

Continued (Table 2)

10%的训练数据集和校准测试数据集在应用到入侵检测方法之前，首先需要进行数据预处理.数据预处理过程共包括5个步骤：1)由于训练数据集中包含重复的数据，首先对训练数据集进行去重处理，将训练数据集由494 021条数据降低为145 586条数据.2)由于训练数据集中属性列num_outbound_cmds，is_hot_login的所有数值均为0，对数据的分类没有任何影响，因此将训练数据集和测试数据集中的属性列num_outbound_cmds，is_hot_login删除.3)将训练集和测试集中的符号属性protocol_type，service，flag转化为数值属性.以属性protocol_type为例，该属性共包括3种：TCP，UDP，ICMP，将这3种类别用数值表示，即1表示TCP，2表示UDP以及3表示ICMP.4)将类别标签转化为数值表示，其中1表示Normal类别，2表示Probe类别，3表示DoS类别，4表示U2R类别以及5表示R2L类别.5)将训练数据集和测试数据集进行[0，1]标准化处理.采用min-max标准化方法对训练集和测试集进行标准化[12]：

(1)

2.2 实验评估指标

入侵检测系统中存在许多可利用的评估指标.其中准确性Acc(accuracy)、检测率DR(detection rate)和误报率FAR(false alarm rate)是入侵检测系统中主要的评估指标[4].

(2)

(3)

(4)

其中，TP(true positive)是指将异常样本正确分类为异常样本的数量，TN(true negative)是指将正常样本正确分类为正常样本的数量，FP(false positive)是指将正常样本错误分类为异常样本的数量，FN(false negative)是指将异常样本错误分类为正常样本的数量.

2.3 实验分析

第1个实验用来评估KNN离群点算法检测的性能.KNN离群点检测算法的目标是用来提高多层随机模型分类器的性能.该实验通过比较KNN离群点检测算法和多层随机森林算法构成的混合模型与单一的多层随机森林模型的检测效果，来说明KNN离群点检测算法能改善分类器的性能.为了这一目的，首先选取KNN的离群点检测算法中最优的参数K和M.参数的选取分为3个部分，Probe类别的参数、DoS类别的参数和Normal类别的参数.首先选取Probe类别的参数，将KProbe分为5个层次10，20，30，40，50，在每个层次下选择不同的MProbe来进行实验，实验结果显示在表3中.当KProbe值一定，MProbe增加时，Probe的检测率DRProbe不断上升.当MProbe一定，KProbe增加时，Probe的检测率有稍微的增加.根据表3分析，当MProbe=2 000时，检测率是最高的，在KProbe=40和50，Probe类别的检测率相同.随着KProbe不断增大，Probe的检测率基本上保持不变.因此Probe的参数设置为KProbe=40，MProbe=2 000.

Table 3 Detection Rate of Probe in Different Parameters表3 Probe在不同的参数下的检测率

Fig. 3 The performance comparison between the hybrid model and the single model图3 混合模型和单一模型的性能比较

采用与Probe参数选择类似的方法，通过多次实验，选择DoS和Normal类别的参数.对于DoS类别来说，DoS类别的数据量将会影响RF2分类器检测DoS的检测率，因此由DoS的检测率DRDoS来决定KDoS和MDoS的选取.KDoS从5，10，20，30共4个层次进行分析，MDoS从10 000，15 000，20 000共3个层次进行分析，实验结果显示在KDoS=10，MDoS=15 000时DoS的检测率最高.为了得到更好的MDoS的取值，将MDoS从10 000～15 000进行细粒度的划分.根据实验结果分析，将DoS的参数设置为KDoS=10，MDoS=11 000.对于Normal类别来说，Normal类别的数据量影响Normal和R2L的检测率，因此根据Normal和R2L的检测率来决定KNormal和MNormal的选取.在实验中将KNormal的取值设置为50，100，150，200，250，300共6个层次，MNormal依次设置为2 000，3 000，4 000，5 000，6 000，7 000，8 000，9 000共8个层次进行分析，实验结果显示：随着KNormal的增大，Normal类别的检测率DRNormal先增大后减小；随着MNormal的增大，Normal的检测率不断增大，但变化的幅度并不大.但随着MNormal和KNormal的不断增加，R2L的识别准确率逐渐降低.为使得Normal和R2L都有较高的检测率，本文选取MNormal=6 000，KNormal=150.

通过上述实验分析，在Normal，Probe，DoS这3个类别下，KNN离群点检测算法的参数M和K设置如表4所示.应用KNN离群点检测算法之前和之后不同类别的数据集的数量如表5所示.

Table 4 Parameters of KNN Outlier Detection Algorithm表4 KNN离群点检测算法的参数设置

Table 5 Size of Dataset Before and After Applying KNN

新的小规模、高质量的数据集用于训练多层的随机森林分类器.图3展示了混合的KNN离群点检测算法和多层随机森林的模型(混合模型)与单一的多层随机森林模型(单一模型)的检测性能，混合模型在准确率和检测率上要优于单一模型，并有一个可以接受的误报率.对异常类型Probe，U2R，R2L的检测效果明显优于单一模型，DoS的检测效果略高于单一模型，Normal类型的检测率略微低于单一的模型，但仍然是很好的识别结果.该实验说明KNN离群点检测算法可以有效的提高多层随机森林模型的准确率和检测率，并能提高DoS，Probe，U2R，R2L异常类型的检测率.

为了说明多层随机森林算法的性能要优于其他分类算法这一问题，本文将混合的多层极限学习机算法(混合ELM模型)与混合的多层随机森林算法(混合RF模型)进行对比，图4说明了多层随机森林算法的准确率、检测率以及对各个数据类的检测率都要优于多层极限学习机模型，同时该模型具有较低的误报率.

为了说明本文算法的扩展性，将本文提出的算法在不同大小的测试集上进行测试，检测其准确率、检测率、误报率以及不同类别的检测率是否随着数据集的变化保持稳定.从校准测试数据集中随机无放回抽取数据，构成3个不同大小的测试数据集(25%校准数据集，50%校准数据集和100%校准数据集)，如表6所示.图5展示了不同测试集的检测效果，随着测试集的增大，本文提出的算法在准确率、检测率和误报率上均能保持稳定.对于不同类别的检测率，除了DoS的检测率下降了大约3%，其他类别的检测率均保持稳定或略微提高.说明本文提出的算法能适应不同大小的测试数据集，有很好的扩展性.

Table 6 Different Size of Three Testing Dataset 表6 3个不同的测试数据集的数据量

Fig. 4 The performance comparison between the hybrid RF model and the hybrid ELM model图4 混合的随机森林模型和极限学习机模型的性能比较

Fig. 5 The detection performance of different testing dataset图5 不同测试集的检测性能

入侵检测方法在网络异常检测时要求做到网络异常行为的实时性检测.为了说明多层随机森林算法检测的检测效率，将多层随机森林算法与单一随机森林算法的检测时间在多个不同规模的测试集上进行对比，如图6所示.本文提出的多层随机森林算法比单一随机森林算法的运行时间要稍微高一点，但在不同规模的数据集上，运行时间仅差1 s左右.在整个测试数据集上，检测时间不到8 s，因此本文提出的方法可以高效地检测网络入侵行为，满足入侵检测中实时性的要求.

为了更好地验证本文提出的算法，在整个校准数据集上将本文算法与其他4种算法相比较，表7展示了比较的结果.表7说明本文提出的算法具有较高的准确率和检测率，同时有一个可以接受的误报率.在Probe，U2R，R2L的检测上要明显优于其他算法，Normal，DoS的检测率略微低于其他算法.传统的极限学习机算法和随机森林算法能更好的识别出正常的行为，对于异常行为，尤其是Probe，U2R，R2L的检测率均比较低.Genetic算法有较高的误报率，这是因为正常的行为被大量误判为异常的行为.Multiclass SVM同样对于Probe，U2R，R2L的检测率较低.本文算法的优势在于有较高的准确率和检测率，能很好的检测出Probe，U2R，R2L，同时在每个类别的检测率之间取得一个平衡.

Fig. 6 The running time comparison between multi-level RF and the single-level RF图6 多层和单层随机森林运行时间比较

Table 7 Performance Comparison Between the Proposed Method and Other Algorithms表7 本文算法和其他算法的性能比较

Note: The font of bold type indicates the best detection result achieved by the proposed or comparied methods.

3 总 结

在大量的网络数据中，为了更有效地检测网络异常行为，本文提出一种新的混合的入侵检测方法，该方法结合KNN离群点检测算法和多层次的随机森林模型来检测异常的网络行为.采用KNN离群点检测算法来检测并删除训练数据集中的离群数据，得到一个小规模、高质量的训练数据集，该数据集可以有效地改善分类器的训练时间和检测性能.根据网络流量的相似性，提出一种新的类别检测划分方法，该方法能对不同的类别进行有效的辨别.结合这种划分方法，提出的多层随机森林模型能有效的检测异常行为.基准数据集KDD Cup 1999用来评估本文算法的性能.不同大小的测试数据集用来评估本文算法，说明该算法具有良好的扩展性.与其他算法相比，本文的算法准确率要明显优于其他算法.该算法的主要贡献在于对Probe，U2R，R2L这3个异常类别的检测，其检测率要远远优于其他算法，并在不同类别的检测率之间取得一个平衡.