一种基于PAM聚类算法的网络异常流量检测方法

摘要

本发明公开了一种基于改进PAM聚类算法的网络流量异常检测方法，包括：流量采集阶段：通过网络分析工具监听网络获取网络数据包；特征提取阶段：提取网络数据包的属性，对一时间段内的网络数据包的属性分别进行信息熵值计算，得到多条多维数据记录；中心选择阶段：根据多维数据记录采用PAM聚类方法对网络数据包的数据点进行聚类，获取近似聚类中心后，通过近似聚类中心选择精确聚类中心；离群点判定阶段：设定阈值，筛选出精确聚类中心距离和局部利群因子均高于阈值的数据点得到离群的异常数据。该方法将改进的PAM聚类算法运用到异常流量检测中去，在继承了聚类无需标记的优势的同时，也降低算法需要的运行时间，具备处理更多数据的能力。

说明书

技术领域

本发明涉及网络异常检测技术，尤其涉及一种基于PAM聚类算法的网络异常流量检测方法。

背景技术

当窥探、入侵等恶意行为发生时，网络上传输的流量在某些特性，如流量大小、数据包长以及数据包特定区域的内容等特性会表现出与正常流量的相异性，若能够尽早检测这些异常流量，就可以提前采取行动来保护网络安全。研究对这些异常流量的检测、定位造成异常的主机，进而对异常主机进行处理，对于避免网络拥塞、保证网络性能、避免网络资源的滥用以及保护网络信息安全，具有重要意义。

聚类是一种普遍的无监督学习方法，旨在将物体分类的有意义的组别。同一个簇中的成员看作相似的，而不同组别中的成员看作不同的。因此产生于不同机制的网络数据会被分到不同的组别中去。k均值(K‐Means)算法属于基于距离的算法，由于该算法的效率较高，所以在科学和工业领域中得到广泛使用。该算法通过初始选择k个中心，然后通过不断的分配非中心并计算新的中心点，直到中心点不再变化。该算法的优点是使确定的K个划分达到平方和误差最小。当类与类之间区别明显时，效果较好。当然该算法也有很多缺点，特别是该方法对所选择出来的聚类中心易受离群点影响，进行均值计算时，若存在一些离群点，则很容易将聚类中心偏离得很远。若将K‐Means算法运用于离群点检测，其选择出来的聚类中心与离群点之间的距离并不明显，导致离群点检测较为困难。

为了克服上述聚类算法所存在的缺陷，本发明提出了一种基于PAM(PartitioningAround Medoids)聚类算法的网络异常流量检测方法。该方法基于一个假设，如果能够获得较为优良的初始划分，则可以有效降低迭代次数。

发明内容

本发明根据其PAM算法特效，采用改进的基于抽样机制以及半径划定的PAM聚类算法，对其聚类中心选择阶段进行了一定比例抽样，先找出近似中心，再通过在近似中心周围寻找精确中心，使得收敛到最优解的速度得到较大提高且保持了原有的检测精度。本发明的目的在于克服现有技术的缺点与不足，提供一种基于抽样机制以及半径划定改进的PAM聚类异常流量检测方法，在继承了聚类无需标记的优势的同时，也具备快速处理数据的能力。

本发明提出了一种基于PAM聚类算法的网络异常流量检测方法，包括如下阶段：

流量采集阶段：通过网络分析工具监听网络获取网络数据包；

特征提取阶段：提取所述网络数据包的属性，对一时间段内的网络数据包的属性分别进行信息熵值计算，得到多条多维数据记录；

中心选择阶段：根据多维数据记录采用PAM聚类方法对所述网络数据包的数据点进行聚类，获取近似聚类中心后，通过所述近似聚类中心选择精确聚类中心；

离群点判定阶段：设定阈值，筛选出所述精确聚类中心距离和局部利群因子均高于所述阈值的数据点，得到离群的异常数据。

本发明提出的所述基于PAM聚类算法的网络异常流量检测方法中，所述方法的流量采集阶段包括下述步骤：

a1.在操作系统下安装流量抓取分析软件；

a2.利用所述流量抓取分析软件开始抓取网络数据包；

a3.将所述网络数据包的显示格式转换为自捕获开始经过的秒数，导出所述网络数据包。

本发明提出的所述基于PAM聚类算法的网络异常流量检测方法中，所述特征提取阶段中，所述网络数据包的属性包括包协议类型、包长度、源IP地址、目的IP地址、源端口和目的端口。

本发明提出的所述基于PAM聚类算法的网络异常流量检测方法中，所述方法的中心选择阶段包括下述步骤：

c1.将所述多维数据记录及所述网络数据包导入系统中用于聚类分析；

c2.对所述网络数据包进行抽样，并根据抽出的数据点对其他所有数据点进行邻域内密度值计算，得到数据点的密度值；

c3.对数据点按密度值进行排序，依次挑出密度最高且离更高密度样本之间距离超过距离阈值的多个数据点；根据密度排序的第一个数据点作为第一个近似聚类中心，依次计算选择密度次高的样本与所述近似聚类中心的距离值；

c4.根据已获取近似聚类中心，为其选择半径并从半径里的数据点里选择候选聚类中心。

本发明的有益效果在于：通过数据挖掘方法进行异常流量检测，可以检测出以往未知的、潜在的异常流量，从而避免将这些流量数据划分到已知的类别中去；通过应用最大信息系数对特征之间的相关性进行估计，避免了对连续型特征进行离散化而造成的结果不精确；再利用特征之间的相关度，对特征进行聚类，将存在冗余的特征聚到一个簇中，并最后取簇中相关度最高的一个属性，加入到最终特征子集；通过对聚类中心选择阶段进行抽样优化，避免对所有的数据记录进行欧式距离的两两运算与保存，极大地降低了这个过程用到的数据量，且仅带来微量检测准确率的下降。

附图说明

图1为本发明基于PAM聚类算法的网络异常流量检测方法的流程图。

图2为实施例中使用Wireshark捕获的流量示意图。

图3为实施例中以120s为单位统计的信息熵。

图4为中心选择阶段步骤中计算数据点密度和距离并在坐标轴上的显示。

具体实施方式

结合以下具体实施例和附图，对本发明作进一步的详细说明。实施本发明的过程、条件、实验方法等，除以下专门提及的内容之外，均为本领域的普遍知识和公知常识，本发明没有特别限制内容。

本发明基于特征选择以及密度峰值聚类的网络流量异常检测方法包括如下四个阶段：

流量采集阶段，通过wireshark监听网络，并将监听到数据包采集到本地，调整时间格式用于下一步；

特征提取阶段，将流量几大特征在一定时间范围内进行信息熵值的计算，形成新的数据记录；

中心选择阶段，对数据样本进行抽样，从样本中选择出近似聚类中心，再从近似中心的邻域内选择精确中心；

离群点判定阶段，设定阈值，筛选出所述精确聚类中心距离和局部利群因子均高于所述阈值的数据点，得到离群的异常数据，以此达到高效、精确的异常流量检测。在本发明具体实施例中，将每个簇中的数据根据其与中心点之间在距离进行排序，选择距离最远的前3％的数据点，并且对这些远距离的点进行局部离群因子的计算，根据下文定义在局部离群因子值。

流量采集阶段包括以下步骤：

a1.在操作系统下安装抓包软件wireshark；

a2.对网络流量数据进行抓取，将一段时间内的网络数据包(如图2所示)保存到本地，格式为tcpdump；

a3.用wireshark打开该以tcpdump为后缀的文件进行查看，wireshark软件默认显示的时间格式为‘yyyy‐mm‐ddhh:mm:ss’的格式，因此需要将时间转为自捕获开始经过的秒数，方便后续的操作。wireshark软件本身提供了流量导出功能，这里可以选择导出为csv格式的文件，方便程序读取。

特征提取阶段包括以下步骤：

b1.对数据进行预处理之后，将第二周的流量以120秒为单位，对各流量要素，分别为包协议类型，包长度，源IP地址，目的IP地址，源端口，目的端口等重要属性特征统计并进行信息熵的计算，形成多维数据记录；以120s为单位统计的信息熵如图3所示。

b2.一些数据特征的熵会在某个时间点形成突变，这种急剧增加或者急剧降低的信息熵可能意味着发生了一些特殊的网络事件，导致网络空间特征分布发生了变化，这种信息熵可能就是要关注的离群点。

中心选择阶段包括以下步骤：

c1.将上述已经计算好各个特征熵值的数据集合导入的数据集合导入系统用于聚类分析；

c2.这一阶段先是进行抽样，对抽出的样本数对其他所有数据成员进行邻域内密度值计算，因此该部分是一个二重循环函数，由于距离的对称性，只需计算距离矩阵的上三角或者下三角时间复杂度即可；

c3.获取近似聚类中心，计算上述数据点的密度和距离两项属性进行计算并显示在如图4所示的坐标轴上，对数据点与横纵坐标围成的矩形面积进行排序，即先对样本按密度进行快速排序，根据密度降序排序选择第一个数据作为第一个中心，接下来依次选择密度次高的数据点与所有已选择的数据中心进行距离值的计算，若距离值过低，在坐标轴上看处于Y轴下半部分(50％)时，意味着该数据点尽管密度较高但是却在聚类中心的附近的高密度区域，并不适合作为另外一个聚类中心。

c4.获取精确聚类中心，根据已获取近似聚类中心，为其选择半径并从半径里的数据点里选择候选聚类中心，尽管也是基于原始最小的代价的思想选择精确聚类中心，但是无需将所有的簇成员加入运算，该算法的时间复杂度取决于被半径R包含的超球体中的数量。改进的K中心点聚类算法的叙述如下:输入簇的数目K，以及参与聚类的n个对象，半径因子θ，输出返回最终所选择的返回的划分中心集合。

(i)对每个样本计算与其他数据之间的距离获得每个样本的密度；

(ii)对样本密度从大到小进行排序；

(iii)将样本最大的样本点挑出来，加入到聚类中心，删去该点以及该点邻域内的所有点；

(iv)重复步骤(iii)直到簇数满了。这样选择出来的初始中心较为接近最终的中心，理论上能够大幅降低PAM迭代的次数。由于已经获得了较为接近最终中心的数据点，接下来的步骤也较为显然；

(v)由于选择出来的聚类中心已经是较为近似的中心，因此无需像原始PAM算法中拿所有簇成员去替换中心，对该中心选择一个半径，而真实的聚类中心往往在近似中心的超球体内，通过这一步再次减少计算量。

(vi)运行上述的PAM聚类算法，直到总代价最低，以获得精确的聚类中心。

离群点判定阶段包括以下步骤：

d1.将成员离其聚类中心较远的数据点选择出来，作为候选离群点；

d2.由于单纯将距离作为判定依据并不十分可靠，因此将同时具有较高的局部利群因子的数据点选择出来，作为最终的选择出来的离群点。在定义局部离群点前，需要定义几个概念：

1、对象p的第k距离(不同于K中心点聚类的簇数K1)

对于正整数k，对象p的第k距离可记作k-distance(p)。

在样本空间中，存在对象o，它与对象p之间的距离记作d(p,o)。如果满足以下两个条件，则认为k-distance(p)＝d(p,o)

1)在样本空间中，至少存在k个对象q，使得d(p,q)＜＝d(p,o);

2)在样本空间中，至多存在k‐1个对象q，使得d(p,q)＜d(p,o)，换句话说，满足这两个标准的k-distance(p)其实就是计算样本空间中其他对象与对象p之间的距离，然后找到第k大的那个距离，即为k-distance(p)。显而易见，如果使用k-distance(p)来量化对象p的局部空间区域范围，那么对于对象密度较大的区域，k-distance(p)值较小，而对象密度较小的区域，k-distance(p)值较大。因此k-distance(p)一定程度上表示的是数据点的绝对密度。

2、对象p的第k距离领域(k‐distance neighborhood of an object p)

已知对象p的第k距离，那么，与对象p之间距离小于等于k‐distance(p)的对象集合称为对象p的第k距离领域，记作：N_kdis(p)(p)。该领域其实是以p为中心，k-distance(p)为半径的区域内所有对象的集合(不包括P本身)。由于可能同时存在多个第k距离的数据，因此该集合至少包括k个对象。可以想象，离群度较大的对象N_kdis(p)(p)范围往往比较大，而离群度小的对象N_kdis(p)(p)范围往往比较小。对于同一个类簇中的对象来说，它们涵盖的区域面积大致相当。

3、对象p相对于对象o的可达距离

可达距离reachdis_k(p,o)＝max{k-distance(o),d(p,o)}，即k-distance(o)和d(p,o)值较大的那个。

4、局部可达密度是基于p的k最近邻点的平均可达密度的倒数。如下:

$>{\mathrm{Lrd}}_k\left(p\right)=\frac{\left|N_k\left(p\right)\right|}{{\Sigma }_{o\in N_k\left(p\right)}reachdis(p,o)}$>

其中N_k(p)表示对象p的第k距离。可以发现，如果对象p的离群度较小，那么对于同一类簇的数据对象reachdis_k(p,o)取k-distance(o)可能性较大，因此它们的Lrd_k(p)值波动性较小；而如果对象p的利群度较大，那么reachdis_k(p,o)取d(p,o)的可能性较大，对于同一类簇的数据对象，它们的Lrd_k(p)$值波动性也比较大，并且Lrd_k(p)值较小。

5、局部离群点因子(LOF)

$>{\mathrm{LOF}}_{MinPts\left(p\right)}=\frac{{\Sigma }_{o\in N_{MinPts\left(p\right)}}\frac{{\mathrm{lrd}}_{MinPts\left(o\right)}}{{\mathrm{lrd}}_{MinPts\left(p\right)}}}{\left|N_{MinPts\left(p\right)}\right|}$>

p的局部离群因子是一个分式，其分子为p的邻居o的密度除以数据点p的局部密度并相加，分母为p在可达距离内的邻居数，它代表了p为离群点的程度。如果对象p的离群程度较大，则它k领域中大多数是离对象p较远且处于某一个类簇的数据对象，那么这些数据对象的lrd应该是偏大，而对象p本身的lrd是偏小，最后所得的lof值也是偏大。反之，如果对象p的离群程度较小，对象o的lrd和对象p的lrd相似，最后所得的lof值应该接近1。

因此，p的lof值越大时，说明其离群程度越高，因此只需对数据点的lof值进行排序，本方法中从距离较远的数据点中选择出30％lof值最高在数据作为离群点。

因此本发明首先通过对原始数据进行抽样，在样本中寻找模糊聚类中心，并通过在模糊聚类中心的邻域范围内对精确聚类中心进行搜寻，减少了距离总和的计算次数，在数据量较大时，能够在保持聚类准确度相当的情况下，有效减少算法运行时间。

本发明的保护内容不局限于以上实施例。在不背离发明构思的精神和范围下，本领域技术人员能够想到的变化和优点都被包括在本发明中，并且以所附的权利要求书为保护范围。