张 珍,万世昌

摘 要:为了进一步提高网络入侵检测技术的检测率,降低误报率和漏报率。针对普通聚类算法存在的聚类结果对随机选取初始聚类中心敏感、分类结果不稳定,从而造成的检测率低、漏报和误报率高的特点。提出一种基于动态聚类算法的网络入侵检测模型,实验结果表明通过在K-均值聚类算法的基础上增加动态迭代调整聚类中心,使聚类结果更稳定更准确。与K-均值聚类等算法相比提高了网络入侵检测的性能,从而表明该算法的可行性、有效性。

关键词:聚类;聚类中心;距离;迭代;入侵检测

中图分类号:TP393文献标识码:A

文章编号:1004-373X(2009)20-085-03

Application of Dynamic Clustering Algorithm in Network Intrusion Detection

ZHANG Zhen,WANG Shichang

(School of Computer Science,Shaanxi Normal University,Xi′an,710062,China)

Abstract:In order to improve the detection rate,lower false alarm rate and missing rate,further.A network intrusion detection model that combines a dynamic clustering algorithm and intrusion detection technology is proposed.The general clustering algorithm is sensitive of the initial cluster center using,and it can make the classification results of instability,resulting in the detection rate is low,and failing to report the characteristics of a high false alarm rate.A model of network intrusion detection based on dynamic clustering algorithm is introduced.Experimental results show that the dynamic clustering results are more stable and more accurate by adding dynamic iteration to adjust the basis of cluster center.To a certain extent,the performance of network intrusion detection is improved,the feasibility and effectiveness of the algorithm are demonstrated.

Keywords:clustering;cluster center;distance;iterative;intrusion detection

0 引 言

随着网络技术的快速发展,网络规模随之不断扩大,计算机已从独立的主机发展到互联的、开放式的系统,这为人们的信息交流和资源共享带来了极大的便利,但同时网络环境也变得越来越复杂[1]。随着Internet大范围的开放以及金融领域的接入,越来越多的系统遭到入侵攻击的威胁,网络安全也面临越来越严重的威胁,这些威胁大多是通过挖掘操作系统和应用服务程序的弱点来实现的。

过去,防范网络安全攻击最常用的方法是使用防火墙,但防火墙技术有它自身的局限性[2]。防火墙本身会有各种漏洞和后门、不能阻止内部攻击、一般不能提供实时的入侵检测等,在这种情况下,单纯以防火墙技术来防范网络攻击已暴露出明显的不足和局限。

入侵检测系统[3,4]是在防火墙和信息加密等网络安全保障技术之后发展起来的新一代网络安全防护系统。它是一种能够动态监控和防御计算机和网络系统入侵行为的安全机制,是对企图入侵、正在进行的入侵或已经发生的入侵的识别过程。它主要通过监控网络和系统的状态和使用情况,检测系统用户的越权使用和系统外部的入侵者对系统的非法入侵。

随着近几年入侵检测技术的不断发展,入侵检测的技术也不断的成熟和完善,出现了一系列的入侵检测方法,如基于数据挖掘技术的;基于数据融合技术的等网络入侵检测方法。但入侵检测的性能还有待进一步提高,很多学者也提出了改进的办法[4-7],如基本免疫模型的入侵检测技术、基于支持向量基的入侵检测技术等。

在此针对传统的基于K-均值聚类算法[8]的入侵检测技术存在对初始聚类中心敏感,分类结果不稳定等特点提出了一种动态聚类算法。

1 聚类算法

聚类法[9]是模式识别中一种常用的方法,它是利用某种相似性度量,把一个未知类别的样本划分为若干有意义的子集,要求相似度高的样本尽量归为一类,而不相似的或相似度较小的样本尽量不在同一类中,把聚类法应用于网络入侵检测系统中,可以将网络流量样本集中的正常流量和异常流量区分开来。

1.1 聚类的基本要素

(1) 定义数据之间的相似度;

(2) 聚类有效性函数(停止判别条件);

① 在聚类算法的不同阶段会得到不同的类别划分结果,可以通过聚类有效性函数来判断多个划分结果中哪个是有效的;

② 使用有效性函数作为算法停止的判别条件,当类别划分结果达到聚类有效性函数时即可停止算法运行;

(3) 类别划分策略(算法);

通过何种类别划分方式使类别划分结果达到有效性函数。

1.2 聚类有效性函数

(1)最小误差(Jj)[9-11]

C个类别,待聚类数据x,zj为类别Ci的中心:

zj=∑x∈Cix/Ci,Jj=∑x∈wj(k)‖x-zj‖2

式中:Jj越小聚类结果越好。Jj衡量属于不同类别的数据与类别中心的误差和。

(2) 最小方差(Si)

Si=1n2∑x∈Ci ∑x′∈Ci‖x-x′‖2

Si衡量同一类别内数据的平均误差和。

2 动态聚类算法

K-均值的聚类算法具有聚类速度快的优点,但对初始参数敏感;容易陷入局部最优;为了解决上述问题,本文采用动态聚类算法对数据进行聚类分析。

2.1 动态聚类算法的特点

动态聚类算法具有两方面的特点:

(1) 算法要求的类别数为C,即把已知的N个模式集[11]划分为C类。这里C頝可以变动,划分方法通常对模式矩阵或模式向量进行运算并产生一个单一划分;这样就减弱了对初始参数的敏感性。

(2) 算法允许模式样本集从一个聚合类移到另一个聚合类,使初始的不准确划分逐步得到改进,大多数划分方法是一些准则函数取极值的划分。这样可以避免局面最优化。

动态聚类法争取采用最优的划分,减少计算量。

2.2 动态聚类算法的步骤

本文的动态聚类划分采用最常用的均方差准则,动态聚类法操作主要包括下面几个步骤:

(1) 初始化聚类中心或建立第一次划分;

(2) 修改聚合类成员,重新分配模式至聚合类内;

(3) 删除和合并聚合类并认定远离点;

(4) 当误差小于一门限或迭代的数目超出预先设置的数时停止。

3 基于动态聚类算法的入侵检测

从上面介绍的动态聚类算法的步骤可知,动态聚类算法[10]需要两个参数,一个是聚类中心z和聚类数目C,聚类数目C要远小于聚类样本总个数n,选择样本集中的C个作为基于动态聚类算法的入侵检测的聚类原型,然后分别求各样本到聚类中心的距离,根据每次迭代求得的距离更新聚类原型模式直至聚类原型不在变动。该算法的目标是能使聚类域w中的所有样本x到聚类中心的距离的平方和最小。即使Jj=∑x∈wj(k)‖x-zj‖2为最小且Si=1n2∑x∈Ci∑x′∈Ci‖x-x′‖2尽量小。

3.1 动态聚类算法的步骤

算法具体步骤:

(1) 选C个初始聚类中心:z1(1),z2(1),…,zc(1), 这里括号内的“1”标明是第一次迭代。

(2) 计算所有样本与聚类中心的距离‖x-zj(k)‖,j=1,2,…,C,并按最小距离原则进行分类;即Dj(k)=min‖x-zj(k)‖,j=1,2,…,C,则x∈wj(k)。

(3) 重新计算各个类的新的聚类中心向量:zj(k+1)=1Nj∑x∈wj(k)x, (j=1,2,…,C),式Nj中为第j个聚类域wj中所包含的样本个数。以均值向量作为新的聚类中心,可使聚类准则函数Jj最小,有Jj=∑x∈wj(k)x-zj(k+1)2,j=1,2,…,C。

(4) 计算最小方差

Si=1n2∑x∈Ci∑x′∈Ci‖x-x′‖2

式中:Si衡量同一类别内数据的平均误差和;

(5) 若zj(k+1)≠zj(k),则转至步骤(2);若zj(k+1)=zj(k)算法收敛。

3.2 动态聚类算法目标

这种聚类算法在实际中要试探不同的C值及选择不同的聚类中心起始值,或者对C=1,2,…分别使用该算法,准则函数JC将随C值增大而单调的减小。通过迭代算法达到了较好的聚类效果。

该算法的目标是根据每次迭代求得的距离更新聚类原型模式直至聚类原型不再变动。即使聚类域w中的所有样本x到聚类中心的距离的平方和最小且平方差尽量小。

4 实验环境与实验分析

4.1 实验环境

为了证明本文算法的有效性,实验中采用了不同的检测数据[12],包括正常数据、Probe攻击数据、Dos攻击数据、U2R攻击数据、R2L攻击数据等。实验环境采用操作系统Windows vistal,Intel Pentium CPU 24 GHz,内存4 GB,程序执行环境采用Matlab 7.0。

4.2 实验分析

将收集到的全部数据进行实验,经过数据预处理得到训练数据8 760条,测试数据4 532条,进行基于动态聚类的入侵检测算法的处理,通过多次测试,得到如表1所示的实验结果。

表1 实验结果

数目类型检测率漏报率误报率

正常数据73.263.2110.45

Probe攻击62.175.4211.09

Dos攻击58.984.058.11

U2R攻击79.352.9812.53

R2L攻击68.573.0910.78

从以上的数据统计可以看出,通过基于动态聚类算法的检测方法进行网络入侵检测,算法在检测率和错检率上得到了改进,满足了系统的安全检测需求。

但由于聚类中心多次迭代的原因,可能使检测的时间增长,并且在实验结果中体现出某个类别的检测率偏低而错检率偏高。但是从其他攻击方式的检测率和错检率来看,算法的效率和有效性还是得到了很大的改进。

图1 几种入侵检测方法的性能比较

为了进一步检验算法的有效性,同其他入侵检测方法进行了对比实验,得到如下实验结果。依次为[13]基于数据挖掘方法(DM )、K-均值方法(KM)、 支持向量机方法(SVM )和基于动态聚类算法的检查率。

通过对比的实验结果可以看出,基于动态聚类的算法较其他入侵检测方法在检测率方面有了一些提高。采用基于支持向量机和数据挖掘的检测方法的训练速度和运算量都比较大,而采用K-均值方法容易造成局部优化等原因,使得它们的检查效率低于基于动态聚类算法的效率,这也充分证明了动态聚类算法应用于系统入侵检测的有效性。

5 结 语

本文在介绍了动态聚类算法并将此方法用于网络入侵检测。通过实验和与其他方法的对比实验说明了该方法用于网络入侵检测的有效性,可以在一定程度上提高了检测效率,降低错报率和误报率。所以可将动态聚类算法有效得用于网络入侵检测。

参考文献

[1]Ajith Abraham,Ravi Jain.Soft Computing Models for Network Intrusion Detection Systems[J].Computational Intelligence,2005(4):191-207.

[2]Can Longzheng,Yu Shmgsheng,Wang Xiaofeng,et al.Network-based Anomaly Intrusion Detection with Numeric-and-Nominal with Data[J].Journal of Shanghai University(English Edition),2006,10(5):415-420.

[3]Sang Kyun Noh,Yong Min Kim,Dong Kook Kim,et al.Network Anomaly Detection Based on Clustering of Sequence Patterns[J].Computer Science,2006(3981):349-358.

[4]苏璞睿,冯登国.基于进程行为的异常检测模型[J].电子学报,2006,34(10):1 809-1 811.

[5]罗守山.入侵检测[M].北京:北京邮电大学出版社,2003.

[6]张超,霍红卫,钱秀槟,等.入侵检测系统概述[J].计算机工程与应用,2004(3):116-179.

[7]伊静,刘培玉.入侵检测中模式匹配算法的研究[J].计算机应用与软件,2005,22(1):112-114.

[8]Huy Anh Nguyen,Deokjai Choi.Application of Data Mining to Network Intrusion Detection:Classifier Selection Model[J].Lecture Notes in Computer Science,2008(5):399-408.

[9]朱永宣.基于模式识别的入侵检测关键技术研究[M]。 北京邮电大学,2006(9):4-18.

[10]舒宁,马洪超,孙和利.模式识别的理论与方法[M].武汉:武汉大学出版社,2004.

[11]曹谢东.模糊信息处理及应用[M].北京:科学出版社,2003.

[12]赵曦滨,井然哲,顾明.基于粗糙集的自适应入侵检测方法[J].清华大学学报:自然科学版,2008,48(7):1 165-1 168.