基于特征分组聚类的异常入侵检测系统研究

何发镁,马慧珍,王旭仁,冯安然

(1.北京理工大学 图书馆,北京 100081; 2.中国科学院信息工程研究所 中国科学院网络测评技术重点实验室,北京 100093;3.首都师范大学 信息工程学院,北京 100048)

0 概述

入侵检测主要分为误用检测和异常检测两类。误用检测通过与已知攻击进行对比来识别异常或潜在的行为,其对已知的攻击具有很好的检测效果,但是难以检测新的或不常见的入侵。异常入侵检测采用机器学习和统计学的方法,对网络传感器收集来的信息或审计日志进行分析处理,在检测出异常行为或恶意攻击时能及时分类处理以达到保障网络空间安全的目的。随着信息传播速度的不断提升,网络传输产生了大量数据,如果不能及时处理这些数据,将会给网络空间安全带来未知的威胁。网络传感器收集信息得来的数据拥有众多属性,如何在众多属性中提取出有用信息以提高检测率,成为亟需解决的问题。

聚类分析是数据挖掘、模式识别等领域的重要研究内容之一,其将数据集中相似的样本尽可能划分为相同的簇,将相异的样本尽可能划分为不同的簇。在入侵检测研究领域,K-means聚类被广泛应用[1-3],k的取值与初始聚类中心的选择对聚类结果具有重大影响。文献[4]通过设置簇半径L来解决k的取值和初始聚类中心选择问题,但是L的取值又成了一个新的问题。文献[5]通过改进Seeded K-means算法中种子集初始聚类中心的选择来尝试解决由此产生的随机性和盲目性问题,但其并未取得良好效果,原因是种子集本身存在随机性和盲目性。文献[6]通过改进K-means算法来解决初始聚类中心选择问题,但其相当于运行2次K-means算法,效率较低。文献[7-8]通过K-means聚类与其他算法相组合的方式,来解决由于k值与初始聚类中心选择导致的聚类结果不稳定问题。文献[9]提出K-means与ID3决策树相结合的方法,其有效地避免了K-means聚类存在的强制分配与类优势问题。文献[10]使用Self-Organizing Map对数据进行初步聚类,得到聚类中心并作为 K-means的初始聚类中心,然后重新定义簇的边界。文献[11-12]使用K-means将数据聚为k个簇,然后利用Naive Bayes分别对每个簇进行分类处理。文献[13]采用EM(Expectation Maximization)算法获得簇数目k,然后使用K-means将数据聚成k个簇,该方法解决了k过大过小的问题。文献[14]使用K-means将数据聚成k个簇,对每个簇的数据利用Fuzzy Neural Network进行处理,然后每个数据用k+1维的向量表示,其中,第k+1个数值由簇中数据的隶属度表示,从而达到降维的目的,随后采用SVM进行分类处理。文献[15]提出M-LHSVM-ELM(Multi-Level Hybrid Support Vector Machine and Extreme Learning Machine)算法,其将数据聚成k个簇,用k个聚类中心点代替原来的数据,对新得到的数据采用多层SVM和ELM混合的方法进行分类处理,从而缩短模型训练的时间。文献[16]提出神经模糊分类(Neural Fuzzy Classifier,NFC)方法,该方法融合了神经网络和模糊理论。

上述研究通过改进K-means算法以及组合算法,来避免由于k值和初始聚类中心选择导致的聚类结果不稳定问题,但是由于数据分布不均匀,在数据处理过程中未能识别出数据中存在的微小差异,导致对数据量少的攻击的检测率不高。文献[17]通过特征取值分组来更好地描述同类表情中不同特征取值作用间的差异。本文提出一种基于K-means的特征分组聚类方法,以描述网络数据中存在的差异并降低数据维度。初始聚类中心选择不稳定导致的聚类效果不佳和依赖问题由C4.5算法来解决,从而提高对异常入侵和数据量少的攻击的检测率。

1 相关算法

1.1 K-means算法

设训练数据集S是由m个数据对象组成的集合,每个对象由n个属性组成。将S分成k个不相交的簇C1,C2,…,Ck,其中,ci(i=1,2,…,k)为簇Ci数据的平均值,即聚类中心。在本文中,K-means算法对于数据对象之间的相似度度量采用欧氏距离,欧式距离越小,相似度越大;反之,欧式距离越大,相似度越小。 欧氏距离的计算方法如式(1)所示。K-means算法常采用误差和准则函数作为聚类准则函数,其定义如式(2)所示:

(1)

(2)

其中,mi是簇Ci中的数据对象个数,xi是簇Ci中的数据对象,J是所有数据对象的误差和。聚类准则函数的作用是尽可能使簇内数据相似度最大,簇间数据相似度最小,从而使聚类算法获得最佳的聚类结果。K-means算法的处理流程如算法1所示。

算法1K-means算法

输入簇的数目k,包含m个对象的数据集S

输出k个簇的集合

从S中任意选择k个对象作为初始簇中心;

repeat

根据式(1)计算d,将每个对象分配到最相似的簇;

更新簇均值,重新计算每个簇的均值ci;

until准则函数收敛

1.2 决策树

决策树在分类问题中构建的模型以树形结构呈现。文献[18]将信息论中的熵引入决策树研究领域,利用熵计算数据对象各特征对类标签的影响程度,以此寻找最优特征构建决策树。C4.5使用信息增益比作为构建决策树过程中子节点选择时最优属性划分的评估标准[19]。设训练数据集为S,m为总的训练样本个数,F={f1,f2,…,fn}为特征集合,每个数据由n个特征组成。假设有p个类,第i个类包含mi个训练样本。训练样本集S的经验熵为:

(3)

特征fk(k=1,2,…,n)有v个不同的取值{ρ1,ρ2,…,ρv},根据特征fk的取值将样本集S分为v个子集{S1,S2,…,Sv},Sj是特征fk取值为ρj的样本集合,特征fk的经验条件熵为:

(4)

其中,mij是Sj第i类的样本个数。特征fk的信息增益为:

Gain(fk)=H(m1,m2,…,mp)-E(fk)

(5)

特征fk的信息增益比为:

(6)

2 基于特征分组聚类的入侵检测系统

2.1 入侵检测模型

本文将基于特征分组聚类的K-means算法和决策树C4.5算法相结合,提出一种KBFG-C4.5(K-means Based on Feature Grouping Plus C4.5)入侵检测系统,以对数据进行分析处理。其中,基于K-means算法的特征分组聚类记为KBFG。首先对数据进行预处理,按照一定标准对特征实现分组;然后使用K-means算法对每个分组内的数据进行聚类,则分组内的所有特征由聚类后的标签所替代,实现了低层高维数据向高层抽象数据的转化,这样可以更好地区分出数据相似特征中存在的微小差异,同时降低维度,方便数据进一步处理;接着对高层抽象数据使用C4.5算法训练分类模型;最后进行测试,验证模型的有效性。本文KBFG-C4.5入侵检测系统的具体流程如图1所示。

图1 KBFG-C4.5入侵检测系统模型Fig.1 KBFG-C4.5 intrusion detection system model

2.2 特征分组策略

相似特征进行较好的分组,会更好地提取高层抽象数据,提高分类模型的准确率;反之,不合适的特征分组会提高模型训练的时间复杂度,降低模型的准确率。本文提出2种特征分组方式:

1)基于先验知识的特征分组方法,例如将图片的特征按照颜色、形状和光亮度进行分组。

2)均匀分组策略,例如将一个n维的特征分成l组,则每组包含⎣n/l」个特征。

2.3 特征分组聚类算法KBFG

假设数据集S={x1,x2,…,xm},其特征集合为F={f1,f2,…,fn},每条数据由n个特征组成。现将特征集合F依据某种标准进行分组,分为l个属性集,l

算法2KBFG算法

输入样本集S,特征分组数据集St对应的聚类数目kt,1≤t≤l

输出特征分组数据集的簇集合C={C1,C2,…,Ct},St对应的簇集合Ct,1≤t≤l

for i=1∶l

从Si中任意选择ki个样本作为初始簇聚类中心{ci,1,ci,2,…,ci,ki};

end

for i=1∶l

repeat

用ni表示第i个分组的特征数目,将xj分组数据(xj,1,xj,2,…,xj,ni)根据式(1)计算d

将(xj,1,xj,2,…,xj,ni)标记为最小的d所对应的类别λ,更新簇集合Ci,λ=Ci,λ∪{( xj,1, xj,2,…,xj,ni)}

重新计算簇Ci,λ的聚类中心:

until准则函数收敛

end

使用KBFG算法对每个样本数据按照分组进行聚类,执行完毕后,针对样本集S内的样本数据x,依次将x中第i个分组的ni个特征值由该分组聚类后的标签λ所替代,1≤i≤l。此时样本x的特征值由原来的n个变为l个,实现了低层高维数据向高层抽象数据的转化。有3种特殊情况,具体如下:

1)当l=1时,KBFG算法退化为K-means算法,KBFG-C4.5模型不再适用。

2)当l=n时,KBFG算法对样本集S内的样本数据x的所有特征进行聚类处理,虽然没有降低特征的维数,但是每个特征的特征值进行了聚类抽象,实现了特征值从低层到高层数据的转换,KBFG-C4.5模型适用。

3)当l<

在KBFG算法中,特征分组数据集St对应的聚类数目kt(1≤t≤l)的值需要通过反复实验,根据KBFG-C4.5模型检测评估效果来确定。

3 实验数据特征分组与评估标准

3.1 数据集及特征分组选择

本文使用 kddcup99 数据集[20]进行实验。该数据集的每条数据由 41 个属性和1个类标签组成,数据记录格式如下:

0,udp,private,SF,105,146,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,1,0,0,255,254,1,0.01,0,0,0,0,0,0,Normal

基于先验知识将特征分为 4 个组:TCP 连接的基本特征(第1个～第9个特征),TCP 连接的内容特征(第10个～第22个特征),基于时间的网络流量统计特征(第23个～第31个特征),基于主机的网络流量统计特征(第32个～第41个特征)。

3.2 数据预处理

将数据集中的标称属性值进行数值化[21]。假设一个标称属性包含m个值,则将该标称属性值变为m维向量。例如,数据集“protocol type”的特征值包括tcp、udp、icmp,则将特征值变为(1,0,0)。

数据中各特征的取值范围不同,其中,取值较大的特征将会降低取值较小特征在计算过程中所起的作用,即“大数吃小数”现象。因此,本文对数据进行归一化处理。将特征的取值转化为0到1区间内的值,如式(7)所示:

(7)

其中,Nmin和Nmax分别为特征值的最小值和最大值。

3.3 数据集划分

kddcup99数据集包括训练与测试数据集,总共包含38种攻击,分为4种主要类型:拒绝服务攻击(DoS),远程攻击(R2L),本地用户非法提升权限的攻击(U2R),网络刺探(Probe),其余为正常网络连接数据(Normal)。数据集的数据分布如表1所示。

表1 实验数据分布Table 1 Distribution of experimental data

本文实验使用 10%的训练数据,共494 021个连接数据,其中,包含97 278个正常连接(Normal),攻击连接数据包含22种攻击类型;10%的测试集包含311 029个连接数据,Normal有60 593个,攻击连接数据包含 14种在训练数据集中不存在的新攻击类型。数据集中攻击数据分布如表2所示。

表2 攻击数据分布Table 2 Distribution of attacking data

3.4 评估方法

为了衡量KBFG-C4.5方法的分类效果,本文采用 DR(Detection Rate)、FPR(False Positive Rate)作为评估标准进行分析。将实验数据分为正常类和攻击类,一个性能良好的入侵检测系统将具有高DR值和低FPR 值。DR和FPR的计算公式分别如下:

其中,TP表示将攻击类预测为攻击类的数量,FN表示将攻击类预测为正常类的数量,FP表示将正常类预测为攻击类的数量,TN表示将正常类预测为正常类的数量。

4 实验结果与分析

本文仿真使用一台处理器为Intel®CoreTMi7-4790 CPU @ 3.60 GHz 、内存8.00 GB的64位Windows 7旗舰版的台式机,用weka工具辅助。

首先对实验数据进行预处理,预处理包含2个部分,即标称属性值数值化和所有数据归一化;然后依据数据的特征类型将数据分离成4个新的数据集,即l=4,如图2所示;接着对处理后的数据使用算法2进行降维,将数据转化为图2中用簇号表示的一条数据,如图中C1,6表示该样本第一个特征分组数据经过KBFG算法被聚到簇6中,以此类推;最后使用C4.5算法对高层抽象之后的数据进行分类,输出结果。

图2 数据属性分组示例Fig.2 Example of data attributes grouping

4.1 KBFG分组聚类参数确定

在KBFG算法中,各分组的聚类数目kt(1≤t≤l)的取值由人工确定。通过反复实验,约定所有分组的聚类数目相等,即k1=k2=…=kt=…=kl=k。当k=5,6,7,8,9,10时,图3所示为KBFG-C4.5模型对攻击类连接数据的检测率情况。从图3可以看出,当k=10时KBFG-C4.5模型检测率DDR=0.997 3,对比k=9时降低 0.003 0。当k=5,6,7,8,9,10时,图4所示为KBFG-C4.5模型对5种连接数据的检测率情况。从图4可以看出,当k=10时,R2L的DDR=0.330 9,对比k=9时降低约0.030 0,当k=10时,DoS的DDR=0.999 3,对比k=9时提高约0.030 0。Normal、U2R、Probe 的DDR在k=10、k=9时均无明显变化。

图3 KBFG-C4.5模型对攻击类连接数据的检测率情况Fig.3 Detection rate of KBFG-C4.5 model for attackingconnection data

图4 KBFG-C4.5模型对5种连接数据的检测率情况Fig.4 Detection rate of KBFG-C4.5 model for fiveconnection data

当k=5,6,7,8,9,10时,图5所示为KBFG-C4.5模型对正常类连接数据的误检率情况。从图5可以看出,当k=10时,误检率FFPR=0。综合上述实验结果,本文最终取k=10。

图5 KBFG-C4.5模型对正常类连接数据的误检率情况Fig.5 False detection rate of KBFG-C4.5 model for normalconnection data

当k=10时,KBFG降维前后数据量对比如表3所示。从表3可以看出,降维后,训练集数据量约缩减87.9%,测试集数据量约缩减85.8%,即KBFG方法能够大幅降低网络数据量。

表3 KBFG降维前后数据量对比Table 3 Comparison of data volume before and after KBFG dimensionality reduction MB

4.2 KBFG-C4.5模型检测能力测试

4.1节的实验结果证实当k=10时KBFG-C4.5模型具有较好的检测效果。为更进一步地证明KBFG-C4.5模型的有效性,从训练集与测试集中抽取部分数据进行实验,数据详情见表4、表5,从中可以看出,训练集与测试集中的攻击类型仅有“ipsweep”一类相同,其余均不同。此次抽样实验将数据分为五大类,实验参数k=10,抽样实验结果如表6所示。由表6可以看出,Normal的检测准确率达到0.997,DoS、Probe、R2L、U2R的检测准确率均达到1.000,说明KBFG-C4.5模型可以检测出新的攻击类且能够正确分类。

表4 训练集抽样数据分布Table 4 Sample data distribution of training sets

表5 测试集抽样数据分布Table 5 Sample data distribution of test sets

表6 抽样实验混淆矩阵Table 6 Confusion matrix of sampling experiments

4.3 结果对比

通过以上实验可知,当k=10时,模型效果最佳。表7、表8是k=10时本文KBFG-C4.5模型与其他模型的对比结果。从表7可知,KBFG-C4.5模型的DR为99.73%,比M-LHSVM-ELM高出4.56个百分点、比NFC高出4.53个百分点、比C4.5高出8.54个百分点,而KBFG-C4.5的FPR=0,其他3种模型的FPR虽然很低,但仍然高于KBFG-C4.5。从表8可知,KBFG-C4.5模型对于Normal、DoS、U2R、Probe的检测率均最优,分别为100%、99.93%、24.12%、100%,均高于其他3种模型。通过以上分析可知,KBFG-C4.5模型由于使用了分组聚类的思想,能够在入侵检测问题上取得良好效果。

表7 4种模型检测率与误检率对比Table 7 Comparison of detection rates and false detection rates of four models %

表8 4种模型对各类攻击的检测率对比Table 8 Comparison of detection rates of four models for various attacks %

5 结束语

本文提出一种基于特征分组聚类的KBFG-C4.5算法,以对网络数据进行检测分析。基于分组聚类思想的KBFG算法能够弱化K-means算法初始聚类中心选择对异常检测效果的影响,较大限度地降低数据维度并提高入侵检测率。实验结果表明,KBFG-C4.5算法具有较高的检测率与较低的误检率。但是,本文算法对于U2R、R2L攻击的检测率未取得很大提升,下一步将分析多种特征分组策略对入侵检测模型的影响并构建一个性能更优的决策函数,以提高模型对U2R、R2L攻击的检测率。