, 严妍 2 , 张家琪 1 1. 北京交通大学 通信与信息系统北京市重点实验室, 北京 100044;
2. 中国信息安全认证中心, 北京 100020
收稿日期：2017-05-31
基金项目：中央高校基本科研业务费项目（2017JBM005）
作者简介：贾凡(1976-), 男, 副教授。E-mail:fjia@bjtu.edu.cn
摘要：针对基础K-means算法在KDD 99数据集中检测罕见攻击效果差且效率低下等问题，该文通过数据统计的方式对数据集中各维度与每类攻击类型的相关分析发现，罕见攻击极易被大量的常见攻击所淹没，而当常见攻击被移去时，这些威胁性更大的罕见攻击则能够被更好地识别出来。基于此，该文提出一种改进的基于K-means分层迭代的检测算法，通过有针对性的特征选择来降低K-means聚类的数据维度，经过多次属性消减的K-means聚类迭代操作可以更加精准地检测到不同异常类型的攻击。在KDD 99数据集上的实验结果表明：该算法对原基础的K-means检测算法难以检测到的罕见攻击类型U2R/R2L攻击检测率几乎达到99%左右。同时随着每次分层迭代聚类维度近50%的降低，进一步节省了约90%的异常检测时间。
关键词：异常检测K-means特征消减U2RR2L
K-means based feature reduction for network anomaly detection
JIA Fan1
, YAN Yan2, ZHANG Jiaqi11.Key Laboratory of Communication & Information Systems of Beijing, Beijing Jiaotong University, Beijing 100044, China;
2.China Information Security Certification Center, Beijing 100020, China
Abstract: Although the basic K-means test was used for anomaly detection in the KDD 99 attack dataset, its accuracy and efficiency for detecting rare attacks needs to be improved. Rare attacks, which are usually greater threats, are easily hidden by common threats so the rare attacks can be more easily identified by removing common attacks. An improved hierarchical iterative K-means method was developed based on this finding to detect all kinds of anomalies using feature reduction through correlations to decrease classification the dimensions. The algorithm is able to detect almost every rare attack with a 99% succesful classification rate and for nearly real-time detection with 90% less computations on the KDD 99 data compared with the basic K-means algorithm.
Key words: anomaly detectionK-meansfeature reductionU2RR2L
近年来，互联网和计算机技术的飞速发展给人们的生活方式带来了极大的变革，与此同时，网络安全问题也更为突出。聚类算法[1]作为一种有效的非监督算法，检测前无需训练数据，无需考虑因时间或空间改变带来的正常模型偏差等复杂问题，同时对新出现的攻击形式具有一定检出能力，逐渐成为异常检测中的研究热点以及未来的发展方向[2]。
聚类算法主要分为基于距离、基于密度和群聚法3类。基于距离的近邻法通过计算被测对象与其他样本点之间的Euclid距离或是匹配系数，找出与其最相近的第k个样本，二者的距离或是匹配系数便可作为该对象的异常度。通常异常度超过某预先设定的阈值或是n个异常度最大的对象会被认为异常。为了提升该方法的性能，研究者们在不同方面做出了很多努力[3]。Knorr等[4]改进了异常度的计算，利用d距离内邻居样本的个数作为异常度的倒数，与基于密度的近邻法的思想相近；Wei等[5]将超图的概念引入基于近邻的异常检测算法中，使得该算法可以对有多个不同种类变量的行为进行更为系统的检测；而Bay等[6]注重算法效率的提升，将一些可以肯定的正常行为或是相似的样本事先剔除，仅检验那些有着高度异常可能性的行为。
一般来说，离临近样本越近，样本点所处的位置密度越大，因此，基于密度的近邻法本质上的思想和基于距离的近邻法是一致的。但是，简单的根据被测对象附近样本密度来判断是否异常对于密度差异较大的情形并不适用。Breunig等[7]针对此问题提出了局部异常因子(local outlier factor，LOF)的概念，即将被测对象临近点周围的样本密度与其自身所处位置的样本密度进行比较。正常情况下，LOF应接近1，它的数值越大说明该点越异常，所以LOF也可直接当作异常度来进行判定。LOF是近邻法最经典的算法之一，后来又有很多人在密度计算方法、可处理的数据类型以及效率方面对其进行改进，出现了基于链接的异常因子(connectivity-based outlier factor，COF)[8]、基于入度的异常点检测(outlier detection using in-degree number，ODIN)[9]、多粒度偏离因子(multi-granularity deviation factor，MDEF)[10]等算法。
聚类算法在异常检测领域已经达到了较好的实验效果，目前存在针对罕见异常的聚类结果不理想的问题。本文通过对KDD 99数据集进行K-means聚类来研究网络异常行为检测，并通过数据统计的方式对数据集中各维度进行分析，提出一种改进基础K-means聚类的方法，使得其对U2R及R2L等罕见攻击的检测率以及系统的效率都有较大提升。
1 基于K-means算法的网络异常检测K-means的基本思想是使得聚类后所有样本点到聚类中心各维度的距离的平方和最小，即在计算距离时使用Euclid距离。通过不断迭代，更新聚类中心，使各簇类得到优化。此方法需要提前指定聚类的簇数目K，且每次更新时使用簇内样本点均值作为聚类中心，因此叫做K-means(K均值)聚类法。
1.1 K-means算法K-means聚类算法的实现过程如下。
步骤1??从n个样本中随机选取k个作为初始聚类中心。
步骤2??在计算其他所有样本点到各个聚类中心的Euclid距离后，将其归到最近的类中。
| ${{c}_{i}}={\rm{arg}\ \rm{min}}_{j=1}^{k}\|{{\mathit{\boldsymbol{x}}}_{i}}-{{\mathit{\boldsymbol{u}}}_{j}}{{\|}^{2}}.$ | (1) |
步骤3??根据上式计算所有类各维度的均值，更新中心。
| ${{{{u}'}}_{j}}=\frac{\sum\limits_{i=1}^{n}{{\rm{IF}}\left\{ {{c}_{i}}=j \right\}\cdot {{x}_{i}}}}{\sum\limits_{i=1}^{n}{{\rm{IF}}\left\{ {{c}_{i}}=j \right\}}}.$ | (2) |
步骤4??重复步骤2和3，直到聚类中心不再变化。实际操作时，迭代停止条件如下：
| $\|\mathit{\boldsymbol{{u}'}}-\mathit{\boldsymbol{u}}{{\|}^{2}}<a.$ | (3) |
K-means算法复杂度为O(tkmn)，其中：t为迭代次数，k为聚类的簇个数，m为数据维数，n为样本点总数。
1.2 异常检测数据集描述KDD Cup99数据集[11]由美国国防部高级规划署在MIT Lincoln实验室模拟真实网络环境搜集而成，为公认的网络入侵检测测试数据集[12]。KDD 99提供10%的训练数据集和10%的测试数据集，由于聚类算法无需训练，本文只用到由50万条记录组成的测试集。除大约12%的正常数据外，还有4大类39小类攻击的记录。4类攻击包括拒绝服务DOS、探针PROBE、远程主机未授权访问R2L和本地未授权的特权访问U2R，比例见图 1。
 |
| 图 1 KDD 99数据集各类攻击记录数量分布 |
| 图选项 |
KDD 99测试数据集中每条连接都是一个41维的向量，每一维度代表该连接的一个属性。此外，在验证数据集中，每条记录被加上了第42维，即指明该条记录属于哪一种攻击类型的标签，用来验证聚类的效果。第2—4维和最后的标签为非数值形式的属性，而剩下的38维是数值形式的。这41个属性被分为基本属性、内容属性、基于时间的统计属性以及基于连接的统计属性4大类。表 1对各类属性以及可能反映出的攻击类型进行了总结。
表 1 KDD 99数据集属性分类
| 类别 | 维度 | 包含内容 | 可能相关的攻击 |
| 基本属性 | 1—9 | 持续时间、协议类型(非数值)、服务类型(非数值)、连接状态(非数值)、源—目的字节数、目的—源字节数、是否同一主机或端口、错误分段数、加急包个数 | PROBE、DOS、U2R、R2L |
| 内容属性 | 10—22 | 敏感文件访问次数、登录失败次数、是否登录成功、compromised出现次数、是否超级用户、是否出现su root命令、超级用户访问次数、创建文件次数、Shell命令次数、访问控制文件次数、FTP会话中站连接次数、是否敏感登录/访客 | U2R、R2L |
| 基于时间的统计属性(2 s内) | 23—31 | 相同目的/服务连接数、相同目的/服务的连接中SYN/REJ错误百分比、相同目的连接中相同/不同服务百分比、相同服务连接中不同目的百分比 | PROBE、DOS |
| 基于连接的统计属性(100个连接中) | 32—41 | 相同目的连接数、相同目的相同服务连接数、相同目的相同/不同服务百分比、相同目的相同源端口百分比、相同目的相同服务连接中不同源百分比、相同目的/服务连接中SYN/REJ错误百分比 | PROBE、DOS |
表选项
1.3 数据预处理由于KDD 99数据集存在非数值属性、各维度差异大等特点，难以直接应用K-means算法进行聚类，需要一些预处理步骤来使得聚类过程更加顺利。本文用MATLAB软件进行数据预处理工作，从数值化、归一化、以及基础K-means算法的数据降维3个方面说明本文所用的数据集预处理方法。
1) 数值化。
聚类算法以样本点与聚类中心的距离作为聚类的标准，而KDD数据集中有3个维度(协议类型、服务类型、连接状态)为非数值属性，无法进行距离计算，因此需要将这3个维度的属性化成数值。本文数值化用各属性出现的频数来替代原属性。这样做避免替换时同一属性不同值之间距离不均衡，从而导致错误聚类的问题；将数据集的统计特征融入距离计算中，相当于进行了简单的规则训练，使得聚类更加准确。
预处理的第一步是对2—4维度所有的属性值出现次数进行统计，用各统计结果替换原字符属性。
2) 归一化。
本文所采用的K-means算法进行聚类的标准是样本点与聚类中心的Euclid距离[13]，需要综合考虑多个维度上的距离，同时希望各个维度对最终距离的贡献是相同的。然而，KDD 99数据集中各个维度数值的差异可能十分巨大。因此，在聚类以前，需要对所有维度的数据进行归一化操作。
| $\mathit{y}=\frac{y-{{M}_{\min }}}{{{M}_{\max }}-{{M}_{\min }}}\times 100.$ | (4) |
利用式(4)对数据归一化是各类文献中常用的方式，本文也将使用此方法，为了得到更高的数据精确度，将归一化数值放大100倍[3]。
3) 降低数据维数。
41个维度对于计算Euclid距离来说是一个巨大的难题。统计分析发现有些维度的数值在整个数据集都没有变化，而有些维度之间可以互相换算。因此，基础K-means算法在处理时，一般会将对聚类无用的维度去除，不仅能够降低算法的复杂性，而且在去除无关属性后，能够得到更好的聚类效果。在预处理中，对2类属性进行了删除:第一类在原数据集中操作，删除可以通过其他维度数据计算得到的属性；第二类在归一化处理后的数据集中，根据U2R攻击所占比例约为0.076%的实际情况和假定80%的U2R攻击都带有某一特性，为了使与U2R有关的属性得以保留，将约占0.06%以上的数据变化量小于99的属性进行删除。经过2轮降维处理，需要处理的维度从41个变为20个，分别是原数据集的第2—4、12、22—29、32、33、36—41维度。
通过实验仿真发现该算法聚类后的总检测正确率低，且检测率、准确率等在达到了一定的水平之后，不论增加迭代次数或是聚类维度都无法再有提升，与真正理想的检测系统还是有一定差距。通过每次实验后对数据的观察发现:该算法对R2L/U2R以及部分DOS攻击的检测率极低。并且文[14]所提到的各类K-means算法的仿真结果也存在上述问题。
2 改进的分步K-means聚类算法2.1 算法改进的基本原理在KDD 99数据集中，通过统计每类数据中出现异常值的比例，统计结果如图 2—5所示。
 |
| 图 3 第11—20维度各类型数据异常值所占比例 |
| 图选项 |
 |
| 图 4 第21—30维度各类型数据异常值所占比例 |
| 图选项 |
 |
| 图 5 第31—41维度各类型数据异常值所占比例 |
| 图选项 |
由图 2—5可以发现，某些维度中U2R和R2L出现异常值的比例很高，改进K-means的基本思想是利用不同的维度来有针对性地检测出U2R和R2L。可以看到，第10—22维度中，U2R和R2L出现异常值的比例很高，而第23—35维度中，出现异常值最多的是PROBE和DOS攻击。U2R/R2L检测率如此之低的原因在于这2种攻击的罕见性，由于出现次数少，在进行第二次降维时，与其有关的大部分维度都被删去；而在进行基础K-means实验过程中，当加上与传输控制协议(transmission control protocol，TCP)连接内容有关的维度时，所有基于时间和基于连接的统计属性也会被加入，这些维度数目多、变化大，很容易就淹没了U2R和R2L的特点，且聚类时间会更长。
采用此方法后，由于该K-means算法针对U2R和R2L有了特殊的处理办法，能够提高U2R和R2L两种攻击的识别准确率。
2.2 算法实现本文算法具体算法步骤如下。
步骤1??对数据23、25、26、27、28、38、40、41维度利用K-means算法聚2类，检测出的异常大类标为“DOS/PROBE”，小类标为“OTHER”。
步骤2??对步骤1“DOS/PROBE”数据第5、24、31、37利用K-means算法聚2类，大类为“DOS”，小类为“PROBE”。
步骤3??对步骤1“OTHER”数据13、14、16、17、18维度利用K-means算法聚2类，检测出的小类标为“U2R”，大类标为“OTHER”。
步骤4??对步骤3剩下数据10、22维度利用利用K-means算法聚2类，检测出的大类标为正常数据“NORMAL”，小类标为“R2L”。
3 实验3.1 实验环境所有实验均采用Windows操作系统，CPU为Intel酷睿i7 6700K，GPU为NVIDIA公司的GeForce GTX 1070，内存为32 GB。实验运用MATLAB编写算法。
3.2 实验结果与分析1) 评价指标。
本文采用总检测率(DR)、准确率(PR)、F值以及聚类时间的变化情况来衡量算法性能。
2) 实验结果与分析。
从预处理过的数据集中抽取3个包含5 000条数据的样本集，分别对其进行基础K-means算法和改进K-means分步算法的仿真，每个实验重复3次，计算参数取平均值。其中基础K-means算法配置参数取效果最佳时的聚类簇数k=4，维数m=23，收敛控制参数a=1。表 2为两者在DR、PR、F值、ER、聚类收敛时间和UR检测率这6个方面的比较结果。
表 2 基础K-means算法与改进算法的比较
| 数据集 | DR | PR | F值 | ER | t/s | UR |
| 基础K-means | ||||||
| 抽样1 | 0.967 8 | 0.989 7 | 0.978 6 | 0.010 6 | 181.600 2 | 0.032 3 |
| 抽样2 | 0.959 6 | 0.989 9 | 0.974 5 | 0.010 2 | 200.772 7 | 0.047 4 |
| 抽样3 | 0.961 6 | 0.977 8 | 0.969 6 | 0.028 1 | 195.724 8 | 0.050 3 |
| 平均 | 0.963 | 0.985 8 | 0.974 2 | 0.016 3 | 192.699 2 | 0.043 3 |
| 改进K-means | ||||||
| 抽样1 | 0.987 7 | 0.959 4 | 0.973 3 | 0.107 5 | 15.551/6.781 | 0.997 6 |
| 抽样2 | 0.984 8 | 0.959 2 | 0.971 8 | 0.117 6 | 13.849/9.876 | 0.981 7 |
| 抽样3 | 0.987 | 0.962 3 | 0.974 5 | 0.109 4 | 14.401/8.664 | 0.992 5 |
| 平均 | 0.986 5 | 0.960 3 | 0.973 2 | 0.111 5 | 14.600/8.440 | 0.990 6 |
表选项
表 2中改进K-means算法时间栏分别标注了4次分步聚类总时间以及其中最长的一次聚类时间；由于原攻击类型与改进算法产生的标签并非一一对应关系，所以此处不再对比总检测正确率；但是为了说明对罕见攻击检测效果的提升，加入U2R/R2L检测率UR的比较。从检测结果对比可以看出：1)改进K-means算法的检测率大约提升了2%，对KDD 99的检测率可以稳定在98%以上；2)随着检测率提高，更多数据被归入异常，准确率随之下降，但F值几乎没有变化，误检率也有比较明显的上升，但还是控制在10%左右；3)虽然付出了误检率提高的代价，但是对系统产生最大危害的U2R和R2L攻击的检测率从几乎检测不出到达99%；4)即使不使用并行聚类方案，由于每次聚类维度以及被测数据的减少，检测时间也缩短了90%左右。总的来说，本文的改进方法达到了预期的目标，大大提高了U2R及R2L等罕见攻击的检测率，并提高了系统的检测效率。
4 结论为解决基础K-means算法罕见攻击检测效果差和效率低下的问题，本文提出一种改进的K-means聚类方案。该方案中融入统计的思想，通过对数据集进行分析，找到与每类攻击相关性最大的维度进行针对性的分别检测，这对基础K-means的缺点有一定改善作用。去除已知常见类型的攻击后，U2R及R2L等罕见攻击更容易和正常行为分离；每次聚类维数较基础K-means至少减少50%，随着检测出的攻击被删去，每次聚类需要处理的数据量也越来越少，因此，总体需要的时间被大大缩短，可节省约90%的时间。该算法可以在十几秒内检测几千条数据，经过进一步优化，几乎可以满足实时检测的需求并且可以在多台主机实现并行运算，也符合当前并行数据处理的潮流趋势。
参考文献
| [1] | NI X J, HE D J, FAROOQ A. Practical network anomaly detection using data mining techniques[J]. VFAST Transactions on Software Engineering, 2016, 9(2): 1–6. DOI:10.21015/vtse.v9i2.403 |
| [2] | TROST R. Practical intrusion analysis:Prevention and detection for the twenty-first century[M]. New York: Addison-Wesley, 2009. |
| [3] | BHUYAN M H, BHATTACHARYYA D K, KALITA J K. Network anomaly detection:Methods, systems and tools[J]. IEEE Communications Surveys & Tutorials, 2014, 16(1): 303–336. |
| [4] | KNORR E M, NG R T. Algorithms for mining distance-based outliers in large datasets[C]//Proceedings of the 24th International Conference on Very Large Data Bases. New York, USA: Morgan Kaufmann, 1998: 392-403. |
| [5] | WEI L, QIAN W N, ZHOU A Y, et al. Hot: Hypergraph-based outlier test for categorical data[C]//Proceedings of the 7th Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining. Seoul, Korea: Springer, 2003: 399-410. |
| [6] | BAY S D, SCHWABACHER M. Mining distance-based outliers in near linear time with randomization and a simple pruning rule[C]//Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Washington, DC, USA: ACM Press, 2003: 29-38. |
| [7] | BREUNIG M M, KRIEGEL H P, NG R T, et al. LOF:Identifying density-based local outliers[J]. ACM SIGMOD Record, 2000, 29(2): 93–104. DOI:10.1145/335191 |
| [8] | 季成, 李晓东, 袁坚, 等. 基于K-means算法的DNS查询模式分析[J]. 清华大学学报(自然科学版), 2010, 50(4): 601–604. JI C, LI X D, YUAN J, et al. Analysis of domain name queries based on the K-means algorithm[J]. Journal of Tsinghua University (Science and Technology), 2010, 50(4): 601–604. (in Chinese) |
| [9] | KDD Cup 1999 Intrusion detection dataset[EB/OL]. (1999-10-28). http://kdd.ics.uci.edu/databases/kddcup99/kddcup99.html. |
| [10] | 蒋学英, 李雅珍, 严结苟. 基于SOM神经网络的异常检测算法研究[J]. 计算机科学, 2008, 35(10B): 244–246. JIANG X Y, LI Y Z, YAN J G. Research on anomaly detection algorithm based on SOM neural network[J]. Computer Science, 2008, 35(10B): 244–246. (in Chinese) |
| [11] | MOUSTAFA N, SLAY J. The evaluation of network anomaly detection systems:Statistical analysis of the UNSW-NB15 data set and the comparison with the KDD 99 data set[J]. Information Security Journal:A Global Perspective, 2016, 25(1-3): 18–31. DOI:10.1080/19393555.2015.1125974 |
| [12] | WELLER-FAHY D J, BORGHETTI B J, SODEMANN A A. A survey of distance and similarity measures used within network intrusion anomaly detection[J]. IEEE Communications Surveys & Tutorials, 2014, 17(1): 70–91. |
| [13] | 傅涛, 孙文静, 孙亚民. 基于分箱统计的FCM算法及其在网络入侵检测中的应用[J]. 计算机科学, 2008, 35(4): 36–39. FU T, SUN W J, SUN Y M. FCM algorithm based on Box-FCM statistics and its application in network intrusion detection[J]. Computer Science, 2008, 35(4): 36–39. (in Chinese) |
| [14] | SYARIF I, PRUGEL-BENNETT A, WILLS G. Unsupervised clustering approach for network anomaly detection[C]//International Conference on Networked Digital Technologies (NDT 2012). Berlin, Germany: Springer, 2012: 135-145. |
