基于流亲戚关系分组的流量识别算法

关卿，秦宏伟，张文超

（解放军63886 部队，河南洛阳471003）

1 引言

现在因特网上出现了许多新型的网络应用程序，这些应用程序具有比传统应用程序更加复杂的交互结构和流量模式。当前流量分析领域的一个困难是传统的方法无法分析这些新兴的应用所产生的流量，需要一个新的方法来分析这些新兴的应用流量。本文在对当前的流量识别算法进行深入探究的基础上结合网络应用交互特征，提出了一种基于流亲戚关系分组的面向应用的流量识别算法(FRRG 算法)。该算法的核心思想是根据各流之间的外在特性对流进行分组，同一个组中的各流可以认为是同一个应用所产生的。该算法并不对网络数据包的有效载荷[1]进行检测，而是关注于其外在特性，即其五元组信息。因此该算法独立于应用层所使用的具体协议，也与应用层的数据是否加密无关，从而克服了有效载荷检测算法的弊端。

2 相关研究

当前的流量识别算法主要有2 种：有效载荷和非有效载荷[1]流量识别方法。

有效载荷检测算法的基本思想是在包的有效载荷中识别特征位串，这些特征位串含有具体应用层协议的独特特征。网络 上 流 行 的9个P2P 协 议(eDonkey，FastTrack，BitTorrent，OpenNap，W inM x，Gnutella，MP2P，Soulseek，Areas，Direct Connect)都是运行在非标准、用户自定义的私有协议之上，所有对它们进行P2P 流量的有效载荷识别就需要按照每一个特定包格式进行识别。这种方法能够高精度的识别流媒体和P2P所产生的流量，但是，利用该算法进行流量识别存在一些与数据相关或者来自P2P 协议本质特性方面的限制。因为要对有效载荷进行检查，系统的有效载荷正比于被捕获的数据包数量和大小，这就造成了一定量的系统额外开销。另外，当控制会话的端口号变化[2][3]时，这种方法也就不再有效。当控制会话的数据被加密后，比如P2P 的KaZaA[4][5]应用程序，有效载荷检查的方法也没用了。用这种方法来识别因特网流量，需要知道所有应用层协议的所有细节，很明显这是不可能的。

非有效载荷流量识别算法仅仅检测包头信息来识别P2P流，而根本不检测用户的有效载荷，它是基于观察源IP 和目标IP 的连接模式来识别网络流量。该算法使用TCP/UDP 启发式和{IP，port}启发式来进行流量识别。该算法存在有以下的局限性：识别结果粒度太粗，仅能将流量识别为P2P 流和非P2P流，不能提供更加精确的识别，比如识别为具体某个应用所产生的流量；使用的方法太细粒度，仅仅关注于一些P2P 协议中交互的细微特征来进行识别，一旦将来P2P 协议关于这些细微特征有了改变，该算法将毫无用处；利用P2PIP 列表会造成误判，可扩展性较差。

3 基于流亲戚关系分组的流量识别算法

3.1 算法主要思想

流亲戚关系分组 (Flow Relative Relation Group，简写FRRG)的应用层流量识别方法，它的主要思想就是仔细探究同一个应用程序所产生各流的相关依赖性，然后根据所属应用程序将流分组，同一组中的流可以认为是同一个应用程序产生的。该方法包括3个部分，如图1 所示。在此方法中，并没有对每个包进行有效载荷检测，这是因为有效载荷检测会使性能严重下降，而且在许多情况下还不适用。我们仅仅使用包头信息，并将这些信息聚合成流。

图1 流量识别方法示意图

第1 步是构建应用程序特征表(Application Characteristic Table，简写ACT)，这可以通过离线使用多种包分析工具来完成。该表包括应用程序名称、除去动态分配的端口外经常使用的端口、传输层的协议号、以及该应用程序的交互方式等。这些信息在第3 步流亲戚关系计量中用来决定应用程序的名字。

第2 步是决定关键端口(Decide Key Port，简写DKP)。DKP的输入是原始包或流数据，输出流信息和关键端口信息。在这一步中，流信息是根据捕获包的五元组信息得到的，这五元组分别是源IP 地址、源端口、目标IP 地址、目标端口、传输协议。从TCP 流信息中选择出关键端口号，由于许多流的源端口和目的端口都超过1024，这一步并非很简单。因此很有必要分清哪个是关键端口，这样才能准确的定出相应的应用程序名字。

第3 步就是对DKP 输出的流数据进行分析、整合，流亲戚关系计量(Flow Relative Relation Computing，简写FRRC)根据各流之间的关系对流进行分组，并用相应的应用程序名字标识该流。绝大多数新兴的网络程序都使用多个会话与一个或多个节点进行交互，所以完全有可能揭示出同一个应用程序所产生的各流的关系。根据这种流与流间的依赖关系，可以将流分成一些组。比如说MSN messenger 所产生的流被FRRC分在同一个组中。分组之后，FRRC 就可以根据应用程序特征表ACT 来决定每个组的应用程序名字。

3.2 应用程序特征表

为了从捕获的流信息中决定应用程序的名字，需要对广泛使用的应用程序之间的交互行为进行研究，并给出这些应用程序的名称、使用的缺省端口号、传输协议以及交互类型。使用tcpdump 和ethereal 对这些应用程序所产生的流量进行分析，然后据此来构建ACT。这个ACT 实际上可看作是IANA端口列表的一个扩展，里面包含了更多的内容。对多个网络上最流行的应用程序做上述实验，即可构建一个ACT，表1 示意了其中的一小部分。

表1 应用程序特征表（部分）

3.3 决定关键端口

所谓关键端口是指在流量识别中起决定作用的端口号。一个正常TCP 的交互使用3 次握手机制在一个服务器和一个客户端之间建立连接，互相发送FIN 数据包来结束这个连接。在TCP 会话中，服务器打开一个端口等待客户发来连接请求。对于流量识别来说，服务器的监听端口是个很重要的端口。那么如何从被捕获的包中得到服务端的监听端口呢？首先，利用3 次握手中使用的SYN 包和SYN- ACK 包。SYN 包的目标端口和SYN- ACK 包的源端口就是服务器的监听端口，利用这个结论可以从所有的TCP 流中决定关键端口号。然而在实际的互联网环境中，经常捕获到SYN 包而没有SYN- ACK 包，所以需要同时检查SYN 包和SYN- ACK 包。在DKP 中一个很基本的步骤就是要检查一个流是否有与之对应的相反流，因此可在决定关键端口时排除没有对应相反流的流。为了提高DKP 算法的性能，可利用这样一个事实：没有系统使用低于1024 的端口号作为客户端随机端口号，系统随机产生的端口号都大于1024。因此可在应用SYN/SYN- ACK 方法之前，通过检查是否有小于1024 的端口号来决定关键端口。

在实际的环境中，还需考虑几种情况。第一，在高速链路上可能无法捕获DKP 所需的所有包，有时这是因为使用了采样机制而有意的丢失一些包，有时则是因为不对称路由和捕获系统性能的限制而丢失一些包。第二，在那些维持时间很长的TCP 会话中，比如流媒体服务、Vo IP 服务、网络游戏等，SYN 包和SYN- ACK 包仅出现在TCP 连接的开始，如果从这些连接的中间开始捕获数据包，则很有可能无法得到这些流的关键端口。第三，还要考虑一些比如Cisco NetFlow 的流数据，它们作为DKP 模块的输入可以将该方法扩展到多个不同的环境中，在这种情况下，流信息可能不包括作为识别关键端口线索的TCP 标志信息(比如Cisco NetFlow V5 不包括这种信息)。为了在DKP 方法中解决这个问题，特提出公理集1 的5 条公理：

公理集1：

前三条公理是显而易见的，后两条公理在普通网络上也都成立。利用DKP 算法和公理集1 的组合，可以识别因特网上几乎所有的TCP 流，剩下的TCP 流可以看作是DoS/DDoS或蠕虫病毒所产生的异常流量。对于UDP 流，因为它不像TCP 流那样使用3 次握手机制，所以不能使用这种方法，但是可以用FRRC 算法直接组合UDP 流。

3.4 流亲戚关系计量

FRRC 算法是基于这样的一个事实：同一个应用程序所产生的各流之间存在相关依赖性，根据这种依赖性FRRC 将每个流归入不同的集合中，属于同一个集合的流是同一个应用程序所产生的。FRRC 算法包括2个连续的过程：外表关系分组 (Facet Relation Group，简写FRG) 和地理关系分组(Geography Relation Group，简写GRG)。

（1）外表关系分组

该算法根据每个流的属性相关性对其进行分类。外表关系可定义为同一个应用程序所产生的2 条流在协议、端口号、IP 地址等方面的关系。公理集2 适用于TCP 流和UDP 流，可以用来进行外表关系分组。

公理集2：

FRG 算法的流程如下：第一在被捕获的流中选择一条流，第二再选择该流所对应的相反流，第三选择与已选择的流在属性源IP 地址、源端口、协议相同的流，第四选择与已选择的流在属性目标IP 地址、目标端口、协议相同的流，第五对在第三步和第四步选择的流重复从第二步到第四步的过程，这个递归的过程一直持续直到没有新的流被选进来。结束了选择的第一条流的组合过程，再从剩下的流中选择另外一条流，继续上述步骤直到没有剩余的流。

可以将FRG 算法毫无修改的应用于UDP 流；然而对于TCP 流，还需要对FRG 算法进行些许修改，这是因为在TCP连接中，客户端不能使用单个端口号建立多个连接，而服务器端却可以使用单个端口号建立多个连接。为了提高FRG 算法的性能，可将该算法应用于DKP 算法的输出流上，当然这些输出流的关键端口已被确定。

（2）地理关系分组

利用FRG 算法，可以将TCP 流和UDP 流分在一些FRG组中，属于同一组中的流可以认为是同一个应用程序所产生。但是，还不能保证同一个应用程序所产生的流被分在同一个FRG 组中。为了解决FRG 算法无法克服的问题，提出一种称为地理关系分组(GRG)的算法。GRG 算法是在FRG 算法的基础上，给出一种定量描述来衡量FRG 各组间的关系：求出每一对FRG 组之间的关系权重，如果这个权重超过一个指定的阈值，便可以将这2个FRG 组合并为一个单一的组。

4 实验及算法对比

4.1 分析标准P2P 协议流量时，PE 算法和FRRG 算法的对比

关闭所有主机上的所有网络软件；运行Ethereal，设置混合模式，并开始捕获包；然后同时在每台主机上运行BitTorren 软件，下载同一个文件；确保所采集到的流量都是BitTorent 软件下载该文件的相关流量。文件下载完毕后，Ethereal 停止捕获报文。将Ethereal 捕获的流量踪迹分别用基于流亲戚关系的流量识别算法和有效载荷检测算法进行分析，所得的结果如图2 所示：

图2 BitTorrent 流量的两种识别算法对比

4.2 分析包括非标准P2P 协议流量时，PE 算法和FRRG 算法的对比

图3 BitTorrent 和ppLive 流量的2 种识别算法对比

运行Ethereal，并开始捕获包；同时在每台主机上运行BitTorren 软件，下载同一个文件；然后同时在每台主机上运行ppLive 软件，观看同一部电影。所有主机的文件都下载完毕后，Ethereal 停止捕获报文。将Ethereal 捕获的流量踪迹分别用基于流亲戚关系的流量识别算法和有效载荷检测算法进行分析，所得的结果如图3 所示.

5 结束语

本文提出的FRRG 算法克服了有效载荷检测算法的弊端，实验结果表明该算法运行良好，在一定的条件下，进行流量识别的准确率较高，并且具有较强的可扩展性。FRRG 算法仅对IP 数据包的三层信息进行分析，由于特征信息较少，因此不可避免造成些许误判，下一步将考虑如何从其它层中抽取特征信息，以及自动构建应用程序特征表等问题，来增强FRRG 算法效率和适用性。

[1]Remco Poortinga,Remco van de Meent,and Aiko Pras.Analysing Campus Traffic Using the meter- M IB[C].Proc.of the Passive and Active Measurement W orkshop(PAM 2002),Mar.25- 27,2002.

[2]Hun- Jeong Kang,Myung- Sup Kim,and James Won- Ki Hong.A Method on Multimedia Service Traffic Monitoring and Analysis[C].Lecture Notes in Computer Science 2867,Edited by Marcus Brunner,Alexander Keller,14th IFIP/IEEE Int’l W orkshop on Distributed Systems:Operations and Management(DSOM 2003), Heidelberg,Germany,Oct.2003:93- 105.

[3]Hun- Jeong Kang,Hong- Taek Ju,M yung- Sup Kim,and James W.Hong.Towards Stream ing Media Traffic Monitoring and Analysis[C].Proc.of 2002 Asia- Pacific Network Operations and Management Symp.(APNOMS 2002),Jeju,Korea,Sept.25- 27,2002:503- 504.

[4]Nathaniel Leibow itz,Matei Ripeanu,and Adam W ierzbicki.Deconstructing the KaZaA Network[C].3rd IEEE W orkshop on Internet Applications(W IAPP'03),June 2003.

[5]Nathaniel Leibow itz,Aviv Bergman,Roy Ben- Shaul,and Aviv Shavit.Are File Swapping Networks Cacheable[C].7th Int’l W orkshop on WebContent Caching and Distribution(WCW),Boulder,Colorado,Aug.14- 4,2002.