2. 山东中医药大学计算医学实验室, 山东 济南 250355;
3. 山东大学软件学院, 山东 济南 250101
2. Computational Medicine Lab, Shandong University of Traditional Chinese Medicine, Jinan 250355, Shandong, China;
3. School of Software Engineering, Shandong University, Jinan 250101, Shandong, China
据《2016年世界互联网发展乌镇报告》[1]显示, 各国互联网基础设施建设迅速发展, 互联网+[2]、云计算[3]、大数据[4]等产业规模高速扩张。随着网络架构越来越复杂, 网络入侵行为也趋于多样化。2017年2月17日召开的国家安全工作座谈会上提出加强网络安全预警监测, 确保大数据安全。2017年5月12日, 永恒之蓝勒索病毒全面爆发, 医院、学校及政府被大面积入侵。网络安全问题已经上升到国家安全层面。
大数据时代下, 网络结构日益复杂, 数据量呈指数式爆炸增长, 网络信息安全面临更多新的挑战。要针对当前网络大数据的特点, 寻找更加能够保障当前网络安全的工具。
入侵检测[5]作为一种保障网络安全的工具, 可以监视网络流量及可疑活动并提醒系统或网络管理员, 以便于网络管理人员进行应急处置, 从而保障网络的安全, 是当前主流的网络安全检测算法。
1 相关工作入侵检测系统的目的就是要发现网络入侵行为并产生网络预警。基于聚类的入侵检测方法可以对网络数据进行分类, 识别出异常网络流量, 从而实现对攻击行为的报警。聚类算法[6]就是从原始的无标记的数据集中挖掘出潜在的规则或模式, 是一种无监督学习[7]的方法, 在入侵检测中取得了较好的应用效果。其中最常用的一种算法是K-means算法[8]。K-means算法是一种简单的聚类算法, 可以把输入的n个数据对象划分为K个簇, 在入侵检测系统中可以通过聚类有效地区分出正常流量和异常流量, 但存在初始聚类中心及簇数K的选择敏感问题[9], 导致聚类结果不稳定, 使得入侵检测的准确率不高。针对K-means算法的不足, 研究者已经提出了一系列改进算法, 如:Y-means算法[10]用于入侵检测系统中相较于K-means则有改进之处, 这种方法能自动将数据集划分成适当的簇数, 即K值是自动确定的, 不需要提前赋值; 另一种叫做MDKM[11]的改进的动态K-means算法, 可以消除噪音和数据集上的孤立点, 然后通过动态迭代的方法确定K值, 这种异常检测模型能取得较好的检测效果; 此外, 文献[12]提出了基于PSO[13]的K-means算法并将其应用在网络入侵检测中, 该方法使用PSO算法[14]优化生成初始聚类中心, 使得到的聚类结果全局最优, 也可有效提高入侵检测准确率。
但是上述算法中, 仍然存在着初始聚类中心及簇数K的选择敏感问题, 为有效解决该问题, 提高入侵检测算法准确率, 本研究提出一种基于BFOA和改进K-means算法的入侵检测算法(本研究称之为HIDS算法)。
1.1 K-means算法K-means算法[15]是一种典型的基于距离的聚类算法, 核心思想是输入聚类的个数K, 以及包括n个数据的数据集, 输出符合方差最小标准的K个聚类。
该算法的步骤如下:
(1) 随机选取K个中心点。
(2) 在第j次迭代中, 对每个数据对象点, 选择距离最近的中心点Ci, 归为此类其公式表达为
| $ d\left( {{x_i}, {x_j}} \right) = \sqrt {\sum\limits_{K = 1}^d {{{({x_{iK}} - {x_{jK}})}^2}} }, $ |
式中:xi, xj表示两个样本数据; xiK, xjK表示两个样本数据对应的第K个描述属性的具体取值。
(3) 更新中心点为每类的均值。
(4) j＜-j+1, 重复第(2)、(3)步, 直至误差小到某一个值或者达到某一固定的迭代步数，其公式表达为
| $ {\rm{min}}\sum\limits_{i = 1}^K {\sum\limits_{x \in {C_i}} {{\rm{dist}}{{\left( {{c_i}, x} \right)}^2}} }, $ |
式中:ci表示簇中心点; x表示一个样本数据。
(5) 结束, 得到K个聚类。
1.2 BFOA算法为获取初始聚类中心的全局最优解, 本研究引入一种基于细菌觅食优化算法(bacterial foraging optimization algorithm, BFOA)。BFOA[16]是一种模仿大肠杆菌觅食行为的仿生类优化算法。一个虚拟细菌事实上是一个试验方案在其功能面移动来寻找全局最优解。BFOA包括趋化(chemotaxis)、复制(reproduction)和驱散(elimination-dispersal)3个步骤。
(1) 趋化操作:趋化是细菌避免进入有害环境并向富营养区域移动的模式。这个过程是通过翻转和前进来实现的。细菌的每一步趋向性操作定义为
| $ P_{n, j + 1, k, l}^i = P_{n, j, k, l}^i + \mathit{\Delta }\left( {n, i} \right)C\left( i \right), $ |
式中:Pn, j, k, li表示细菌i在经过j步趋向性操作, k步复制操作, l步迁徙操作时候的位置坐标信息; Δ(n, i)是旋转后的一个随机向量; C(i)是翻转过程中指定的随机方向的步长的大小。
(2) 复制操作:经历趋化步骤后, 细菌进行繁殖。一个健康的细菌分裂成两个相同的细菌。这是模拟通过选择最好的一半的种群再现。
(3) 驱散操作:环境的变化可能导致细菌数量突然变化。这些变化可能包括一些细菌的死亡或从一个运动区域到另一个运动区域。这是驱散操作的过程。通过驱散操作可以实现算法的全局寻优功能。趋化过程中的适应值函数为J(i, j, k, l), 令J(i, j, k, l)=J(i, j, k, l)+Jcc(θ, P(j, k, l)), 其中Jcc(θ, P(j, k, l))定义为
| $\begin{array}{l} {J_{cc}}\left( {\mathit{\boldsymbol{\theta }}, P\left( {j, k, l} \right)} \right) = \sum\limits_{i = 1}^s {{J_{cc}}(\mathit{\boldsymbol{\theta }}, {\theta ^i}\left( {j, k, l} \right) = } \\ \;\;\;\;\;\;\;\sum\limits_{i = 1}^s {\left[{-{d_{{\rm{attractant}}}}{\rm{exp}}{{\left( -{{w_{{\rm{attractant}}}}\sum\limits_{m = 1}^p {{\theta _m}-\theta _m^i} } \right)}^2}} \right]} + \\ \;\;\;\;\;\;\;\;\sum\limits_{i = 1}^s {\left[{{h_{{\rm{repellant}}}}{\rm{exp}}\left( {-{w_{{\rm{repellant}}}}\sum\limits_{m = 1}^p {{\theta _m}-\theta _m^i} } \right){^2}} \right]}, \end{array} $ |
式中:Jcc(θ, P(j, k, l)))代表目标函数值, 被添加到实际目标函数去表示时间变化的函数; P(j, k, l))代表种群中个体的位置; s代表细菌种群规模大小; p代表要被优化的变量的数量; θ=[θ1 θ2 … θp]Τ代表p维搜索域中的一个点; dattractant, wattractant, hrepellant, wrepellant代表四个不同的联合和排斥系数。
2 研究方法 2.1 基于阈值的改进K-means算法针对K-means算法对初始聚类中心及K值的选择敏感问题, 本研究采用一种基于阈值的改进K-means算法(简称为T-K-means算法)。该方法针对入侵检测的主要思想是先计算每个属性的平均值, 分别计算连续属性和离散属性的差异, 然后更新簇中心。最后找到距离该记录最近的簇, 如果距离(minTemp)大于阈值(WidthThreshold), 则生成新的簇, 否则插入最小距离簇的末尾。
该方法不需要预先设定K的值, 所得到的簇的数量仅依赖于距离阈值的选取。关于阈值的取值选择问题将在试验验证环节给出。
2.2 HIDS入侵检测算法HIDS入侵检测算法的核心思想是首先利用基于阈值的改进K-means算法确定簇数K的值, 然后利用BFOA算法的趋向性操作进行初始聚类中心全局搜索, 并进一步通过复制操作进行优胜劣汰, 最后使用驱散操作获得全局最优解。HIDS算法的流程图见图 1, 当检测到异常流量时, 系统将产生攻击报警并向网络管理员发出预警信号, 以便网络管理员进行应急处理, 从而保障网络的安全。
|
图 1 HIDS算法流程示意图 Figure 1 HIDS flow chart |
为验证HIDS算法的有效性和测试算法性能, 本研究采用的是网络入侵检测领域比较权威的由林肯试验室收集的KDD99数据集[17]作为试验数据集。该数据集由两部分组成, 分别是训练数据集和测试数据集[18]。训练数据集包含5 000 000多个网络连接记录, 测试数据集大概包含2 000 000个网络连接记录。本研究选取了KDD99提供的10%的训练子集和测试子集作为试验的训练数据集和测试数据集。一条网络连接就是某个时间内从开始到结束的TCP数据包序列, 写成CSV的格式。每条网络连接记录都包含42项, 前41项是特征属性, 最后1项是标记(label)。其中前41项特征分为4大类:TCP连接的基本特征, 包含9种特征; TCP连接的内容特征, 包含13种特征; 基于时间的网络流量特征统计, 包含9种特征; 基于主机的网络流量统计特征, 包含10种特征。
3.2 试验内容(1) 试验环境
试验环境为Intel Corei3、2.4 GHz CPU、8 GB内存、256 GB移动硬盘, 操作系统为Microsoft 7旗舰版, C++程序在Microsoft Visual Studio 2010下编写, 于MATLAB 2009中编写部分程序并嵌入C++中使用, 最后在VS2010中进行了数据测试。
(2) 试验参数设置
距离阈值的取值范围为(0, +∞), 本研究在(0, 7)区间取了部分数值进行试验验证。
关于BFOA算法参数的设置, 经过多次试验结果比较, 如下选择时聚类结果较好。细菌种群规模为S=26, 搜索空间维度P=1, 趋向步骤的步数Nc=50, 复制步骤的次数Nre=4, 游动次数Ns=4, 消除-分散事件的次数Ned=2, 消除-分散事件的概率Ped=0.25, 每代复制数Sr=S/2=13。
(3) 试验设计
在KDD99数据集中, 每一条网络记录就是一条TCP/IP连接, 每一条连接用41个特征来描述, 由这些特征可以区分不同的数据流量。当然这些特征的区分度也是不同的, 从先验知识出发, 对于一条TCP/IP连接而言, 显然IP源、目地址属性要比连接状态属性更具有区分性。本研究根据特征重要性区分, 设计了4组特征选择的试验对比。第1组采用了全部属性, 第2组采用了8个区分性不大的属性, 第3组采用了8个区分性比较好的属性, 第4组采用了14个区分性比较好的属性, 特征选择分组如表 1所示。
|
表 1 特征选择分组表 Table 1 Feature selection grouping |
(4) 数据区分规则
通过观察KDD99数据集的特点以及特征属性的取值范围等特点, 本研究试验制定了相应的数据区分规则, 数据区分规则具体内容详见表 2。
|
|
表 2 数据区分规则表 Table 2 Data distinguishing rule |
(1) 评价指标
一般来讲, 评价入侵检测系统性能的指标是检测率(DR)和误检率(FPR)[19]。DR表示检测到的入侵网络连接记录占入侵数据连接记录总数的百分比，FPR表示被检测入侵的正常网络连接记录占正常网络连接记录总数的百分比。检测率越高并且误检率越低, 说明这个系统的性能越好。
(2) 试验结果
试验结果表明阈值宽度取0.5f, 使用BFOA算法进行优化后, 且当选择第4组试验设计的属性时, 结果最好, 检测率可达98.33%, 误检率达6.419%。4组试验各自的试验结果见图 2。
|
图 2 阈值与检测率之间的关系图 Figure 2 The relation between Widththreshold and DR |
从图 2中可以看出阈值宽度取0.5 f并且当选择第4组试验设计的属性时, 结果最好。此外, 从图 2中可以看出阈值和DR呈负相关, 即阈值只有设置在一定的范围时, 才能取得较好的试验结果, 并且高检测率与低误检率是很难同时获得的。
采用本研究试验方法取得的结果与其他方法[20]的结果比较统计表, 如表 3所示。
|
|
表 3 同类算法试验结果对比统计表 Table 3 Comparison of experimental results of similar algorithms |
针对网络入侵的异常检测问题, 本研究提出了一种基于BFOA和距离阈值的改进K-means算法的入侵检测方法——HIDS算法。试验结果证明, 将HIDS算法应用于IDS所得到的入侵检测结果较传统算法更为稳定, 确保了具有较高检测率的同时还可获得一个较低的误检率, 取得了显著的效果。在对距离阈值和优化参数合理的选择下, 该方法能将正常和异常行为加以区分, 很适用于网络中正常行为与入侵行为有明显不同的数据集, 但该方法阈值参数的确定花费了较高的计算代价。因此, 后期工作将趋于算法更加的优化, 以便于能区分正常流量与异常流量差异小的网络数据。
| [1] | 赵光霞, 宋心蕊. 2016年世界互联网发展乌镇报告[M/OL]. 乌镇: 人民网, 2016[2016-11-18]. http://media.people.com.cn/n1/2016/1118/c40606-28879457-2.html. |
| [2] | WANG Zhu, CHEN Chao, GUO Bin, et al. Internet plus in China[J]. IT Professional, 2016, 18(3): 5-8 DOI:10.1109/MITP.2016.47 |
| [3] | ALI Mazhar, KHAN S U, VASILAKOS A V. Security in cloud computing:opportunities and challenges[J]. Information Sciences, 2015, 305(1): 357-383 |
| [4] | ARDAGNA C A, BELLANDI V, BEZZI M, et al. Model-based big data analytics-as-a-service:take big data to the next level[J]. IEEE Transactions on Services Computing, 2018(99): 1-1 |
| [5] | MODI Chirag, PATEL Dhiren, BORISANIYA Bhavesh, et al. A survey of intrusion detection techniques in cloud[J]. Journal of Network and Computer Applications, 2013, 36(1): 42-57 DOI:10.1016/j.jnca.2012.05.003 |
| [6] | DAVIES D L, BOULDIN, DONALD W. A cluster separation measure[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1979, PAMI-1(2): 224-227 DOI:10.1109/TPAMI.1979.4766909 |
| [7] | THOMAS Hofmann. Unsupervised learning by probabilistic latent semantic analysis[J]. Machine Learning, 2001, 42(1-2): 177-196 |
| [8] | SONG Jingping, ZHU Zhiliang, PRICE Chris. A new evidence accumulation method with hierarchical clustering[C]//2016 IEEE International Conference on Cloud Computing and Big Data Analysis. Chengdu, China: IEEE, 2016: 122-124. |
| [9] | ANIL Jain. Data clustering:50 years beyond K-means[J]. Pattern Recognition Letters, 2010, 31(8): 651-666 DOI:10.1016/j.patrec.2009.09.011 |
| [10] | YU Guan, GHORBANI, NABIL Belacel. Y-means: a clustering method for intrusion detection[C]// Proceedings of Canadian Conference on Electrical and Computer Engineering. Montreal, Canada: IEEE, 2003: 1083-1086. |
| [11] | LI Han. Research and implementation of an anomaly detection model based on clustering analysis[C]// Proceedings of International Symposium on Intelligence Information Processing and Trusted Computing (IPTC 2010). Huanggang, China: IEEE, 2010: 458-462. |
| [12] |
傅涛, 孙民亚. 基于PSO的K-means算法及其在网络入侵检测中的应用[J].
计算机科学, 2010, 38(5): 54-55 FU tao, SUN Minya. K-means algorithm based on PSO and its application in network intrusion detection[J]. Computer Science, 2010, 38(5): 54-55 |
| [13] | ABUROMMAN Abdulla Amin, IBNE REAZ Mamun Bin. A novel SVM-KNN-PSO ensemble method for intrusion detection system[J]. Applied Soft Computing, 2016, 38(1): 360-372 |
| [14] | WEI Benzheng, ZHAO Zhimin, PENG Xin. A novel method of medical image registration based on feature point mutual information and ipso algorithm[J]. Journal of Computational Information Systems, 2010, 7(2): 559-567 |
| [15] | HUANG Zhexue. Extensions to the K-means algorithm for clustering large data sets with categorical values[J]. Data Mining and Knowledge Discovery, 1998, 2(3): 283-304 DOI:10.1023/A:1009769707641 |
| [16] | PANDA Sidhartha, MOHANTY Banaja, HOTA P K. Hybrid BFOA-PSO algorithm for automatic generation control of linear and nonlinear interconnected power systems[J]. Applied Soft Computing, 2013, 13(12): 4718-4730 DOI:10.1016/j.asoc.2013.07.021 |
| [17] | STOLFO S J, WEI Fan, WENKE Lee. Cost-based modeling for fraud and intrusion detection: results from the jam project[C]//Proceedings of the 2000 DARPA Information Survivability Conference and Exposition. Hilton Head, USA: IEEE, 2000: 130-144. |
| [18] | BERNHARD Pfahringer. Winning the kdd99 classification cup:bagged boosting[J]. ACM SIGKDD Explorations Newsletter, 2000, 1(1): 65-66 |
| [19] | RICHARD Lippmann, JOSHUA Haines, DAVID Fried. The 1999 darpa off-line intrusion detection evaluation[J]. Computer Networks, 2000, 34(4): 579-595 DOI:10.1016/S1389-1286(00)00139-0 |
| [20] | KUMAR Gulshan, KUMAR Krishan. Design of an evolutionary approach for intrusion detection[J]. The Scientific World Journal, 2013, 2013(2013): 1-14 |