一种基于仿射传播聚类的入侵检测方法

程梦驹，赵 龙，陶洪波，赵成林

(北京邮电大学信息与通信工程学院，北京 100876)

0 引言

随着计算机网络的普及，网络入侵所带来的危害越来越严重。入侵检测系统是一种主动的安全防护系统，通过监视网络流量或主机状态来发现入侵行为并做出响应［1］。入侵检测技术主要分为误用检测(Misuse Detection)和异常检测(Anomaly Detection)［2］。误用检测是指利用已知系统和网络的弱点攻击模式来检测入侵，它对已知的入侵行为有很好的检测效果，而对新的入侵模式无效;异常检测是指利用定量的方式来描述可接受的网络行为，通过分析用户行为与正常行为的偏差来判断是否为入侵行为，它能够检测新的入侵模式，但是存在误检率较高的问题［3］。

基于异常检测的入侵检测系统需要处理大量的网络审计数据，而随着数据挖掘技术的发展，数据挖掘中的聚类方法因其能高效处理海量数据的优势而得到广泛应用。由此建立的入侵检测系统依赖于对训练集中数据样本的学习，所以保证该数据集的洁净性对建立一个有效的入侵检测系统极其重要［4］。但实际上，要为系统的训练收集一个洁净的数据集代价较高，因此无监督的聚类方法成为首选［5］。

在以往的入侵检测中采用的无监督聚类方法大多需要预先设置初始聚类中心和数目，如K均值(k-means)和模糊C 均值(Fuzzy c-means，FCM)等聚类算法［3，6］，如果初始聚类中心选择不当，容易陷入局部极值，得不到准确的聚类结果，导致检测率低和误检率高［7］。下面采用能够自动决定聚类中心和数目的仿射传播聚类算法对训练集进行聚类分析，可以得到准确的聚类结果。通过对KDD CUP99数据集的仿真实验来测试该方法的检测性能，并与传统方法的检测性能进行比较。

1 仿射传播聚类

仿射传播(Affinity Propagation，AP)聚类［8］是由Frey等人提出的一种快速有效的新型聚类算法。AP算法与其他聚类算法最大的不同之处在于它能够自动决定聚类中心和数目。AP算法将每个样本点都看作潜在的聚类中心，通过样本之间传递实时信息迭代竞争成为聚类中心。

首先根据训练数据构造样本之间的相似度矩阵作为算法的输入，一般使用欧氏距离作为样本间相似度的计算方法［6］，样本间距离越小则相似度越大。假设训练数据集为 X={x1，x2，…，xN}，共有N个样本点，每个样本点有m个属性，则任意2个样本点i和k之间的相似度为:

构造相似度矩阵为:

式中，p为偏向参数，表示各样本点成为聚类中心的可能性大小，一般取相同值。p值的大小在迭代中表现为竞争的激烈程度［6］，最终会影响聚类中心的数目。如果p越大，则竞争越激烈，各样本点成为聚类中心的可能性也越大，最后聚类中心的数目越多。

为了找到合适的聚类中心需要从样本中收集相关信息，包括吸引度(Responsibility)和归属度(Availability)［6］，分别用 R(i，k)和 A(i，k)表示。R(i，k)反映样本点k对样本点i的吸引程度，即样本点k作为样本点i的聚类中心的适合程度;A(i，k)反映样本点i选择样本点k为聚类中心的适合程度。若R(i，k)与 A(i，k)之和越大，则样本点 k成为聚类中心的可能性越大。在算法迭代过程中，不断更新所有样本点的R(i，k)和A(i，k)直到满足迭代终止条件，输出聚类结果。R(i，k)与 A(i，k)的迭代计算公式为:

信息更新公式为:

式中，λ为阻尼系数，取值范围为(0，1)，其值越大迭代越慢，但聚类精度越高。为避免发生振荡［5］，λ一般设置为0.9。

AP算法主要步骤如下 :

步骤1 初始化:根据式(1)和式(2)计算相似度矩阵 S，设置参数 p和 λ，p取 S的中值median(S)，初始化 R0(i，k)=A0(i，k)=0。

步骤2 迭代过程:

① 根据式(3)、式(4)和式(7)更新 R(i，k)，根据式(5)、式(6)和式(8)更新 A(i，k);

②寻找聚类中心:对于样本点i，若样本点k使得 R(i，k)+A(i，k)最大，则样本点 k 即样本点 i的聚类中心;

③检查是否满足迭代终止条件:是否达到最大迭代次数，或聚类中心经过一次循环后不再变化。否则转至①。

步骤3 判断得到的聚类中心个数是否满足要求，否则调整p值，重复迭代过程直至满足要求，输出聚类结果。

2 一种基于仿射传播聚类的入侵检测方法

在实际的网络环境中，正常的网络行为在数量上远远大于异常行为(包括入侵行为和用户误操作)。基于无监督聚类的异常检测通常是基于以下2个事实［10］:一是正常的网络行为在数量上远大于网络入侵行为;二是入侵行为在某些特征属性上与正常的网络行为具有不同之处。由于入侵行为模式不同于正常行为，而且数量上占总的网络连接数的比例较小，因此在大量的网络连接数据中表现异常并可被检测出来。

入侵检测模型具体包含以下几个部分［11］:数据收集模块、数据预处理模块、聚类分析模块、标类模块和检测模块，如图1所示。

图1 基于异常检测的入侵检测模型

在实际应用中收集的网络数据可能包含非数值型的特征属性，且不同的特征属性有不同的度量标准，如果不同特征取值的数量级相差较大则会造成大数量特征掩盖小数量特征，影响聚类的准确性。因此需要对原始数据进行预处理，包括非数值型特征的数值化和特征值的标准化处理。

对训练数据的聚类结果中，入侵行为类中的样本数要小于正常行为类中的样本数，将样本数小于阈值α的类标记为入侵，样本数大于阈值α的类标记为正常。在完成标记后，利用标记结果对新样本进行检测，在不断完善和更新聚类结果的同时检测入侵行为。计算新样本到各聚类的欧氏距离，选择距离最近的聚类，根据其标记结果判定该样本是正常行为还是入侵行为。

3 实验结果

为了测试提出的基于仿射传播聚类的入侵检测方法的检测效果，使用目前在入侵检测研究领域广泛使用的KDD CUP99数据集进行仿真实验。

数据集来源于MIT林肯实验室1998DARPA入侵检测评估数据集，共包含490多万条网络连接数据，每一条连接数据包含41个特征，其中7个离散型特征，34个连续型特征。数据集中的入侵数据共分为 4大类:DOS攻击、U2R攻击、R2L攻击和PROBE攻击，细分为39小类。

采用检测率(Detection Rate，DR)和误检率(False Positive Rate，FPR)两个指标来评价入侵检测方法的检测性能。检测率DR表示被正确检测的入侵记录数占总入侵记录数的比例，误检率FPR表示正常记录被检测为入侵行为的总数占正常记录总数的比例。

首先按比例θ从KDDCUP9910%数据集中随机选取入侵数据和正常数据混合组成训练集和测试集进行实验。在实际网络环境中，入侵行为数占总的网络连接数的比例约为1%左右［12］，所以实验中θ取1%。

对原始数据进行标准化处理的步骤如下:

①计算平均绝对偏差S:

式中，Sf为数据集X第f个特征属性的平均绝对误差;xif为数据xi的第f个属性值;mf为数据集 X的第f个属性的均值。

②计算标准化的数据:

式中，Yif即数据xi标准化后的第f个属性值。

在检测过程中，存在2个影响检测结果的参数:AP聚类算法的偏向参数p和标记阈值α。偏向参数p影响聚类的数目，若聚类分析模块输出聚类数目过多，则训练样本中的正常记录分布比较分散，可能导致标记错误，使误检率上升，因此须控制聚类数目在较小水平。标记阈值α影响标记结果，若α值偏大，则越多的类被标记为异常，能够提高检测率，但是可能有较小的正常类被错误标记而造成误检率上升;相反若α值偏小，则能降低误检率，但是检测率也会下降。

从实验结果表 1和表 2可以看出，当 p=0.5median(S)时算法具有较好的检测效果。取p=0.5median(S)时的实验结果与其他检测方法进行对比，这里选取了k-means算法、Y-means算法、一类SVM算法和一种改进的k-means算法［12］与本文使用的方法进行对比，检测率DR和误检率FPR的ROC曲线如图2所示。由对比结果可以看出，当FPR小于2%时，基于AP的方法具有较好的检测效果，当FPR大于2%时，基于AP的方法能够有效提高检测率。

表1 p和α取不同值时的检测率DR (%)

表2 p和α取不同值时的误检率FPR (%)

图2 不同算法的ROC曲线对比

4 结束语

研究了一种基于无监督聚类的入侵检测方法，采用能够自动决定聚类中心和数目的AP算法，不需要进行人工设置初始聚类中心和数目，避免了可能因初始聚类中心选择不当而造成检测率低下的问题。对KDD CUP99数据集的仿真实验结果表明，该方法有良好的检测性能，与其他方法相比能够有效提高检测率。 ■

［1］田俊峰，张 喆，赵卫东.基于误用和异常技术相结合的入侵检测系统的设计与研究［J］.电子与信息学报，2006，28(11):2162 －2166.

［2］程玉青，梅登华，陈龙飞.基于数据挖掘的入侵检测系统模型［J］.计算机技术与发展，2009，19(12):123 －126.

［3］肖立中，邵志清，马汉华，等.网络入侵检测中的自动决定聚类数算法［J］.软件学报，2008，19(8):2140－2148.

［4］ESKIN E，ARNOLD A，PRERAU M，et al.A Geometric Framework for Unsupervised Anomaly Detection:Detecting Intrusions in Unlabeled Data［C］∥Applications of Data Mining in Computer Security.Boston:Kluwer Academic Publisher，2002:77 －101.

［5］刘 涛，马晓宇，胡 景.一种 K-MEANS算法在网络异常检测中的应用［J］.微电子学与计算机，2012，29(5):42－45.

［6］ZHANG H，SONG K.Research and Experiment on Affinity Propagation Clustering Algorithm［C］∥Hohhot:2011 Second International Conference on Mechanic Automation and Control Engineering(MACE)，2011:5996 －5999.

［7］李文华.基于聚类分析的网络入侵检测模型［J］.Computer Engineering，2011，37(17):96 －98.

［8］FREY B J，DUECK D.Clustering by Passing Messages between Data Points［J］.Science，2007，315(5814):972－976.

［9］肖 宇，于 剑.基于近邻传播算法的半监督聚类［J］.软件学报，2008，19(11):2803 －2813.

［10］罗 敏，王丽娜，张焕国.基于无监督聚类的入侵检测方法［J］.电子学报，2003，31(11):1713 －1716.

［11］WANG S.Research of Intrusion Detection Based on an Improved K-means Algorithm［C］∥Shenzhen:2011 Second International Conference on Innovations in Bio-inspired Computing and Applications(IBICA)，2011:274－276.

［12］ZHONG Y，YAMAKI H，TAKAKURA H.A Grid-based Clustering for Low-overhead Anomaly Intrusion Detection［C］∥Milan:20115th International Conference on Network and System Security(NSS)，2011:17－24.