基于FP-Growth 算法的P2P 业务流量特征
自动识别机制
李娜，何刚*
作者简介：李娜，（1988-），女，研究生，宽带流量监控. E-mail: nxln@163.com
5 （北京邮电大学信息与通信学院，北京 100876）
摘要：本文提出一种基于FP-Growth 算法的P2P 业务流量特征自动识别机制，该机制将流量
特征识别设计为一种正反馈结构，在识别过程中强化并扩展了流量特征，并通过构建流量数
据的FP-Tree 提高了特征识别的时间效率并获得了较高的识别准确率。实验对比了Aprioi
算法和FP-Growth 算法的效率，对本文提出的机制的准确度和效率进行了验证。
10 关键词：深度报文检测；流量特征识别；P2P 业务
 0 引言
P2P 网络是一种分布式网络, 网络的参与者( Peer )共享他们所拥有的一部分资源(处理
能力、 存储能力、 网络连接能力、 内容等) ,这些共享资源能被其他对等节点直接访问而
30 无需经过中间实体。P2P(peer-to-peer)业务由于其可扩展性，健壮性，高性价比以及负载均
衡等优点，近年来在数据下载，在线视频方面得到了广泛的应用。其迅速发展的同时也带来
了诸多问题，例如对网络带宽的大量占用，影响传统Internet 应用，网络运营的成本增加以
及p2p 系统本身的安全问题等。解决这些问题，需要引入对p2p 业务的识别机制。
传统的应用层业务流量识别主要基于对协议端口识别。然而，随着网络技术的发展，以
35 P2P 为代表的应用层协议为了避免防火墙或主机的限制，开始大量采用动态端口策略,接近
70%的Kazaa P2P 流量使用并非默认端口[1]，基于固定端口的流量识别的局限性越来越明显，
已经不能满足新的业务流量识别的要求。
针对传统流量识别技术的局限性，研究机构和科研人员提出了DPI（Deep Packet
Inspection）和DFI（Deep Flow Inspection）技术。这两种技术除了对L3 层和L4 层的源地址、
40 目的地址、源端口、目的端口以及协议类型前面的分析外，还增加了应用层分析，识别各种
应用及其内容。DFI 面向流，在处理速度和维护成本上有一定优势；DPI 面向报文，逐报文
分析，识别的粒度细于DFI。
 目前P2P 协议的流量特征识别主要面临以下问题：1）识别方法以手动抓包人工分析为
主，识别效率和准确率不高；2）新应用协议增加速度很快，传统的识别方法不具备扩展性，
45 在增加新业务时扩展系统比较困难[2]。
为了解决上述问题，本文提出一种基于数据挖掘算法的P2P 业务流量特征自动提取机
制。首先，我们建立了一个用于挖掘P2P 业务流量特征的数据库，为了保证数据的可靠性，
该数据库中流量数据通过仿真获得。之后，我们对数据进行预处理并应用FP-Growth 算法进
行流量特征提取。数据预处理包括对冗余数据和噪声数据的过滤以及对数据格式的改变。数
50 据预处理的目的是提高挖掘算法的效率。最后，经过验证的P2P 流量特征被自动添加入特
征识别文件库。在P2P 流量特征识别过程中引入FG-Growth 算法可以解决识别的效率以及
准确率问题。特征识别文件库增加了特征识别系统的可扩展性。
本文其余部分组织如下。第二节介绍P2P 业务流量识别和数据挖掘算方法在特征提取
中应用的相关工作。第三节对基于FP-Growth 算法的P2P 业务流量特征自动识别机制进行
55 了概述。第四节具体描述了数据挖掘所需的数据库建立以及使用FP-Growth 算法自动生成流
量特征的过程。第五节给出了实验的结果和对结果的分析。第六节对本文进行了总结并提出
了未来的工作。
1 相关工作
控制P2P 通信的前提是对P2P 通信进行有效的识别。由于P2P 协议动态地使用端口，
60 甚至占用传统业务的知名端口，传统的基于IP 和端口的分类技术很难识别、 跟踪或控制此
类通信。
控制P2P 通信的研究已经获得了大量的成果。[3]提出了URL 过滤策略，该策略的原理
是限制种子文件的生效。文献[4]提出了针对IP 和端口控制策略，能够自动提取协议应用层
流量特征，自动提取算法的引入提高了特征识别的效率和正确率。但是该方法无法识别采用
65 动态端口通讯的应用层协议。
基于流量特征的检测技术BDFI（Deep Flow Inspection）也被应用于P2P 通信控制。P2P
应用在传输层表现出来的流量特征相对于其它应用有很大差异。 DFI 是通过检测这些可统
计出的流量特征来发现P2P 应用，DFI 可以发现新的 P2P 应用并检测加密 P2P 应用。很大
概率区分出网络中的P2P 流量和其他非P2P 流量。但DFI 对P2P 应用分类的能力较弱影响
70 了检测精度，需要结合其它技术， 如端口检测来提高检测精度。在实际工程的使用中，往
往无法达到令人满意的效果，故较少采用此方法。
DPI 技术也是P2P 流量特征识别的主要方法。正则表达式以及硬件层面的字符串匹配一
直都是研究的热点[5] [6]。Subhabrata，Sen 等人提出了一种基于应用签名的P2P 流量检测方
法[7]， 实际上仍是深度包检测技术的一种。
75 由于应用层流量数据数量巨大而且内部关联复杂，用人工分析的方法已经无法应对获取
流量特征的需求，数据挖掘算法被广泛的应用于网络流量特征的提取。[8]应用数据挖掘算法
对网络特征字符串和数据报长进行了分析。
Apriori 算法[9]和FP-Growth 算法[10]均为数据挖掘关联规则领域中具有很大影响力的算
法。文献[10]提出了FP-Growth 算法。该算法通常用于挖掘事务间的关联关系。FP-growth 算
80 法的优点在于不需要产生频繁项候选集，缺点是需要递归生成条件数据库和条件FP-tree，
因此内存开销比较大。文献[11]将该算法应用于基于多分类规则的事务分类。本文提出的基
于FP-Growth 算法的P2P 业务流量特征自动识别机制是DPI 技术与数据挖掘算法在P2P 流
 量特征识别中的应用。
2 P2P 业务流量特征自动识别机制概述
85 2.1 流量特征自动识别架构
图1 流量特征识别架构
如图1 所示，流量特征自动识别架构主要由四个模块组成，各模块主要功能如下：
90 训练数据集合模块提供P2P 流量数据，数据按照具体应用不同进行分类。
流量特征生成模块由两个子模块构成，分别是数据预处理模块和流量特征生成算法模
块。数据预处理模块的作用是改变训练数据集合提供的P2P 流量数据结构，适应流量特征
生成算法的需要。流量特征生成算法模块使用FP-Growth 算法生成P2P 业务的流量特征。
流量特征库和特征匹配算法共同构成流量特征匹配模块。流量特征库中存储了由流量特
95 征生成模块生成的特征。特征匹配算法通过字符串匹配对流量进行识别。
识别结果模块中存储识别成功的数据报文。经验证后这些识别成功的数据报文会被加入
到训练数据集中，形成一个闭环，对流量特征集合不断进行优化和更新，提高自动识别的成
功率。
2.2 FP-Growth 算法
100 特征字符串是最常用的一种识别特征，通常可以将特征字符串包括两种类型：应用层协
议报头中的特征字符串以及协议控制信息中的特征字符串。前者是指报文中版本号、协议名
称等；后者包括命令代码、标识信息等。这2 种类型的特征字符串在连接建立后传递的前
几个数据包的前部分出现的概率较大，且在相同偏移的数据包内出现同一特征字符串的概率
更大，如Qvod 协议在连接建立后会出现一些长度为81 的报文，这些报文有固定的关键字
105 特征，第15 位开始的4 位是0x51、0x56、0x4f、0x44（QVOD），第20 位开始的8 位是
0x70、0x72、0x6f、0x74、0x6f、0x63、0x6f、0x6c（protocol）。本文希望通过数据挖掘关
联规则方面的FP-Growth 算法对P2P 流量进行分析，获得P2P 业务流量特征。
FP-Growth(Frequent-PatternTree-Growth)算法的主要步骤包括：构造整个事务数据库的
FP-tree；挖掘FP-tree 频繁项关联项。具体步骤在[10]中有详细介绍，本文不再具体描述。
110 FP-Growth 算法与Aapriori 算法相比，最大的改进之处在于，提出通过建立FP-Tree 数据结
构来替代频繁项候选集，极大的减少了数据交换和频繁匹配的开销。因此，在挖掘效率上
FP-growth 算法明显优于Apriori 算法，特别是在稠密数据库中，频繁项集的长度很大的情况
下，FP-growth 算法的优势越明显。
 P2P 业务的流量特征通常需要多条数据报文才能确定，这一特点决定P2P 业务流量特征
115 获取需要进行对大量的数据挖掘。FP-Growth 算法能够在保证识别准确度的情况下减少对存
储空间的占用并提升识别效率。这也是本文选用FP-Growth 算法挖掘流量特征的原因。
3 基于FP-Growth 算法的P2P 流量特征生成
3.1 P2P 业务流量数据预处理
本文提出的流量数据预处理包括两个两步骤: 1)流量数据集合的构造; 2)流量数据重新
120 编码。
我们定义同一业务同一连接中序号相同的报文为相同偏移报文。[8]指出业务层流量特征
集中于偏移为m 的数据报文的前n 个字节中。因此没有必要对全部原始流量数据进行挖掘，
只需要选择部分数据进行分析。另外，[8]并未对n 的取值同特征识别的正确率的关系进行分
析，我们在第五节对此关系进行分析。
125 同一连接中流量特征经常出现于报文中相对固定的位置，特征与位置关系密切，同一字
符串出现的位置所代表的意义并不相同。为了将不同位置处的相同字节内容区分开，且同时
使内容直接与位置相关联,本文将位置属性作为流量特征的一部分，对原始数据进行重新编
码。此编码方法使得特征字符串直接与位置相联系，能够提高准确率。
流量数据预处理的具体方法如下：
1)提取偏移为m 的(1≤m≤M) 数据包的前n 个字节，记为0 1 { , ,..., } n 130 I= i i i 。提取M
个数据包是为了在从偏移为1 的数据包挖掘得到的特征不足以有效得出流量特征时，迭代从
偏移大于等于2 的数据包中继续挖掘特征；2)对I 的字节进行重新编码。I 中每个单字节扩
展为双字节，第一个字节以16 进制编码形式表示原字节在应用层载荷中的位置，第 2 个字
节为原字节的 16 进制表示值，得到0 1 ' { ', ',..., '} n I = i i i 。
135 3.2 流量数据的FP-Tree 构造及特征挖掘
流量数据的FP-Tree 构造过程如表1 所示。令项集1 2 { ', ',..., '} m K= I I I 。项集K 存储
于事务数据库中。本文将支持度定义为sup( ') | ' | / | | mn j I =i K，其中| '| j i 为' j i 在K 出现的
学术论文网Tag：代写论文 代写代发论文 代发论文 职称论文发表