基于子空间聚类的网络流量分类方法

李丹丹++田春伟++李佰洋++孙广路++康+健

摘要：应用层网络流量分类技术对流量控制与管理等研究具有重要意义，针对传统的基于有监督机器学习的分类方法对所有应用程序使用相同的特征，使得某些特征对一种或几种应用类型有区分性，而对其他应用类型的网络流分类产生干扰等问题，提出基于子空间聚类方法的网络流分类框架.利用子空间聚类算法，在总特征集中为每一种类型应用进行特征选择，提取与之相对应的关键特征，自动消除不相关的特征，使得每种应用类型都产生对应的特征签名集，并用这些不同的特征签名对未知的网络流进行分类.实验结果表明：本文提出的方法能够有效地提出每种应用类型的特征签名，并且所提出的特征签名具有明显的可区分性，该方法的分类准确率在93%以上，并且能很好的识别新出现的应用，

关键词：子空间聚类；网络流分类；特征签名

DOI： 10.15938/j.jhust.2015.02.012

中图分类号：TM391.1

文献标志码：A

文章编号：1007-2683（2015）02-0063-06

0 引 言

近年来，具有开放性、共享性等特点的互联网迅速普及并发展壮大，随着网络用户数量的飞速增多，传统的互联网业务已经无法满足人们的需求，越来越多的新型网络应用应运而生.对于网络运营商来说，为了有效利用带宽，并提供更好的服务质量（quality of service，QoS），需要网络能够针对不同应用进行分类.另一方面，互联网的开放性特点允许任何符合其技术标准的设备或软件接人互联网，导致了各种网络恶意攻击事件层出不穷，严重危害网络信息安全与服务，保护网络安全迫在眉睫.网络流量分类技术能够增强网络可控性，帮助研究人员掌握网络上的流量分布情况，帮助网络运营商优化服务质量，预防并阻止各种网络犯罪行为.总而言之，构建网络智能，网络流分类是第一步.

在流量分类研究中，目前广泛采用5元组{源IP、源端口、目的IP、目的端口、传输层协议}（SourceIP，Source PORT，Destination IP，Destination PORT，Protocol）定义数据流，迄今为止，网络流量分类方法主要包括基于端口号匹配的分类方法、基于应用层载荷特征的分类方法、基于主机行为和交互行为的分类方法，以及基于机器学习的分类方法.用于分类的特征主要有端口特征、载荷特征、网络流包级和流级统计特征、主机行为和交互行为特征（根据IP地址、端口等衍生出来的关联特征）.

其中，传统的基于有监督机器学习的分类方法，主要是利用网络流在网络层和传输层的统计特征来识别流量.这种方法使用的特征和训练得到的分类器对所有应用类型的流都是相同的，没有差异和针对性.某些特征对一种或几种应用类型有区分性，而对其他应用类型的流分类产生干扰，导致整体的分类准确率不高.而且，其对于网络数据中新出现协议的识别效果不能令人满意.

针对以上问题，依据样本在不同的数据簇中常常与某些特定的数据特征子集相对应的思想，本文提出了一种新的网络流分类方法：基于子空间聚类的网络流分类方法（subspace clustering-basedmethod，SCM）.它针对每一种应用流独立建立识别模型，然后将这些识别单一应用的模型合在一起，实现多类别分类，而不是同时区分几种应用.换句话说，SCM方法学习独立的识别类A和识别类B，而不是试着同时区分类A和类B.本文使用骨干网络数据集和边界网络数据集对SCM分类方法进行测试，识别精度达到93%，而且对新应用的识别率可以达到90%.由于路由非对称原因导致骨干网中双向流中的某一个方向的流经常丢失，本文中的分类方法使用单向流.

1 子空间聚类算法及网络流分类框架

1.1 子空间聚类算法

子空间聚类问题描述：

设B=B1×B2×…×Bn，代表一个n维数据空间，其中，n为正整数.F是包含m个位于n维特征空间的数据对象的集合，记为F= {Xi|i∈[1，m]，xij=Xi.Bj}，其中，点Xi=（xi1，xi2，…，xij，…，xin。），Xi的第j个属性值xij，为其在哆维上的取值.设k维子空间S^CB其中，k≤n.在SK子空间中的元组集合表示为

在训练期间，SCM分类框架为每种应用类型产生一组签名.产生签名的过程如下：

1）输入：属于同种应用类型的一组流的集合F，每个流feF用n维数值向量表示.

2）输出：流的子集合与特征子空间的对应关系（Fi，Si）即签名，其中F：∈F，S，CB.每一种应用类型可能包含多个签名iE[1，|F|].

本文使用文提出的基于K最相似聚类的子空间聚类算法，在得到所有一维空间聚类的基础上，查找包含相同数据对象的相似聚类，继而决定子空间搜索方向，然后合并不同维度中的相似聚类，最终得到子空间聚类。该方法用不同子空间中采用的不同密度阈值替代传统算法中的全局密度阈值，提高了子空间聚类算法聚类结果的精度。

该算法的相关定义如下：

定义1（基本聚类） 将使用DBSCAN方法产生的所有一维空间的聚类的集合称为基本聚类，记为C'.

定义2（基本聚类相似度） 给定c.，c：∈C1，其中，c，在Bi维，c：在B，维，且i≠j，其相似度定义为基本聚类c，，C2所包含的相同数据对象元素的数目，记为.sim（ ci，C2）=|C1∩C2|.

定义3（最相似聚类） 给定聚类c∈Cl，c的最相似聚类MSC（C）∈C1满足条件：

定义4（k最相似聚类）给定聚类C∈Cl和正整

该算法的基本步骤如下：

1）对数据做预处理，产生每一维上的基本聚类；

2）计算所有基本聚类之间的相似度；

3）查找每个基本聚类的κ个最相似聚类，当作该基本聚类的合并候选；

4）使用深度优先方法搜索子空间，产生子空间聚类：

5）删除剩余数据噪声点.

先找到基本聚类c∈C1，形成子空间S1，计算Cl中各个基本聚类问相似度，通过得到的基本聚类相似度查找每个基本聚类的k个最相似聚类，合并基本聚类相似度大于等于para（S2）的基本聚类，形成S2子空问，然后不断的递归的搜索，产生子空问聚类.

其中para（Sm）为Sm子空间合并阈值，利用如下公式来获得：

就是Sm子空间期望，它是由总的学习样本数|F|比上Sm子空间投影到每一维产乍的不同元组的数目得到的，算法的详细内容参见.

所有的特征都使用标准的Z-score算法进行标准化，该公式为其中μ和σ分别是通过训练数据算出来的特征的平均值和标准差.

2.2

SCM网络流分类框架

基于子空间聚类算法，本文提出一种新的网络流分类框架SCM.SCM执行两个不同的过程：（a）产生签名（b）网络流分类.具体的分类示意图如图1.

分类过程：在分类期间，一个待分类流需要和所有应用类型各自对应的签名模式做匹配.实质上每一个签名模式都是一个二分类器，只返回是或否.F面是分类的详细过程.

匹配一个签名模式：当一个待分类流匹配某个特定的签名（Fi，Si）时，首先它投影到Si维空间中（提取对应特征集），然后用标准“欧几里得距离”来计算它与Fi中的模式流之问的距离.本文把待分类流到Fi中最近的流的距离作为待分类流到签名的距离（即距离的最小值）.如果待分类流在该签名的预定半径r范围内，则匹配成功，实质上，每一个签名都是一个有|Si|维特征、|Fi|个点和同定半径的最近邻分类器，这个固定的半径保证签名只匹配属于此应用类型的流而不会匹配属于其他应用类型的流.

根据欧几里得公式：

可以看到，即使每一维度的距离都很小，距离d还随维度|Si|升高而递增，而不同子空间的维度可能不相同，所以对所有的子空问都用同一个固定半径不准确，本文用基本的缩放因子/哆T来调节.这样，如果在我们的分类器中使用的一维半径是r，那么对于签名（Fi，Si），

在签名的所有点半径ri的覆盖范围内我们都认为是有效的，

流分类过程：本文中的SCM分类框架包括很多二分类器，每一个二分类器对应一个应用签名（Fi，Si）.假设现在得到t个二分类器：

每一个进入SCM分类框架的流都要被每一个二分类器处理.每一个二分类器都要返回true或false和距离d.因此，结果是两个向量：

1） -个t维的布尔向量其中变量表示二分类器i的返回值.比如，如果X，给流标记为真，f，=l，否则，f，=0.

2） -个n维的数值向量：其中di。表示该待分类流到签名（Fi，Si）之问的距离，由于属于一个应用类型的待分类流可能和多个签名有关，它可能被映射到多个二分类器巾，为了跟踪二分类器和应用类型的映射关系（在训练中得到），我们引进了一个新的向量M，如果二分类器i来自应用App，则M（i）=App，可能会有多个i对应一个应用App.

最后，测试流是否被标记为App或Unknown由下面的算法决定，这个算法用到向量L、D和M：

添加所有L（i）=true的i值到结果集R中；

如果IRI=0，则将该待分类流标记为label=Unknown，因为没有分类器标记这个流；

如果|R|=1，R={k}则将此流标记为M（k），因为只有一个二分类器标记了这个流如果|R|>1，且Vi. ER，|si|<|Sk|，则将此流标记为M（k）.即如果多个分类器同时标记此流，则选择签名维度更高的分类器做标记，因为维度越高，特性越明显.

2 实验结果和分析

2.1数据集

本文使用3份真实流量对SCM子空间聚类方法进行实验验证，这3份数据一份是骨干网络数据和两份是不同的校园网数据.分别收集于2010年与2012年.

本文使用基于载荷的DPl分类技术对网络流进行标记.使用的数据集中包括如下几种应用：Web， Streaming， P2P，Chat， Dns， Games， Mail和其他类型，其中未标记的流约占20%.实验时将这些未识别的流去除掉.图2描述了3份网络数据集中应用层应用类型的分布情况.

2.2特征

本文使用了网络流包级、流级的主要特征，包括流的前6个包的大小、内部时间间隔（IAT）、总字节数、总包数和IAT的最大值，最小值，平均值、标准差等等.

还包含了每个流的前16字节载荷.每个载荷字节都用{0，l，…255}之间的数值表示，据研究，应用层协议头在流中会重现，而载荷的前16字节会包括应用层协议头.所以载荷的前16字节也是重要的特征.每个特征用一个流的特征向量的一维来表示，使用的详细特征见表1.

2.3 实验理论和评估指标

为了评估SCM方法的性能，本文把每一个数据集分成两部分.用其中一部分做训练，用另一部分做测试.训练分类器时，本文只考虑实际流数超过1000个的应用类型.这个数对于收集训练数据不难，而且足够用于抽取好的签名，本文只对单向流产生签名，这样可以分别从客户端到服务器端的交互和从服务器端到客户端的交互中抽取不同的签名.当用对比基准与SCM分类预测结果对照时，需要同时看流的两个方向上所给的标签，如果一个方向标记为未知流，反方向标记为某种已知应用类型，则用反方向标签标记该流.如果两个方向标记的标签不同，则将此流标记为未知.文中所有的实验结果均是对多次实验结果取得的平均值，

本文使用覆盖率（Coverage）、覆盖集识别准确率（aCcuracy）以及新应用检测率（newApp）等评价方法来评价SCM分类器的分类性能.

覆盖率：实际做出预测的样本的数量（没被标记为未知）除以样本总数.

覆盖集的准确率是被正确分类的样本的数量除以预测样本总数.即：其中，TP表示真正（true positive.s），FP表示正错误（false Positives）.具体定义如下：

1）真正：指待测方法将P2P流识别为P2P流的个数；

2）正错误：指待测方法将非P2P的流错误识别为P2P流的个数；

新应用的检测率：

当SCM分类框架对一个训练数据集中不存在的应用类型的流分类时，理想的结果是这个流被标记为未知.例如，如果训练得到的分类器中没有Gaines类型的签名，那么分类器应该将所有测试数据中的Games流标记为未知.由于训练的签名中不存在Games类型，Games类型就代表了一种新的应用.本文暂时删除训练数据中的一种应用类型的流，然后观察分类器如何标记这些“新”应用类型的流.

2.4实验结果及分析

本文在不同配置参数下测试了SCM方法的性能，先用一个数据来测试不同的配置，确定参数供实验中其他数据使用，本文使用DBSCAN算法来产生基簇，DBSCAN有两个参数，流间允许的最大距离ε和最小点数minPts.一维特征空间的有效区域的半径r也设为与ε相同的值r=ε.通过删除低维签名可以调控分类器的准确率，经过实验，我们得到μ为

3，minClu为4，MSCG（c）集合大小为4时子空间聚类算法的聚类效果最好，

为了研究参数敏感性，本文大范围的变换ε，minPts的值来观察实验结果，实验结果表明，参数的变化对我们分类器的分类效果影响很大，本文中使用的默认参数是minPts=10.这些参数值是测试清华骨十网数据得到的，然后对其余2个数据集用与这个分类器同样的配置.图3展示了SCM分类器在3个数据集上的分类表现，虽然使用通过edgel数据得到的分类器配置，但是在3个数据集上的分类效果都很好.Accuracy可达到93%，与朴素贝叶斯分类器的分类结果对比如图3.在调整好参数的情况下，SCM的准确率优于朴素贝叶斯分类器.

SCM在识别新应用方面表现也很好，本文对每种应用类型都做一次新应用测试，然后用所有应朋类，趔各自得到的newApp求平均值.newApp的平均值可达到90%，coverage可达到75%，如图4所示.

3 结 语

本文将子空间聚类方法应用于应用层流量分类中，提出SCM网络流分类框架.在训练过程中，为每种应用类型产生多个流与子特征空间的签名对即二分类器，用于识别单一应用类型的应用.义将多个二分类器组合在一起实现多类别分类.SCM能够有效的对每个应用类型抽取出相应的特征签名，并日.所提出的特征签名具有明显的可区分性，该方法的分类准确率能达到93%以上，超过了朴素贝叶斯分类器，并且能很好的对新出现的应用进行识别.