基于RIPPER的网络流量分类方法

曹彦珍++何云斌++朱素霞++孙广路

摘要：利用一种规则学习方法中的重复增量式降低错误剪枝方法解决网络流量分类问题。利用该方法能够挖掘出网络流属性特征和类别之间的相关关系，并将挖掘出的关系构成分类器用于网络流量分类。该方法能够解决传统机器学习方法在网络流量中有大量的不平衡数据集时，分类错误率高等问题。实验证明，该方法在网络流量分类标准数据集上具有很高的分类准确率、查全率和查准率。

关键词：网络流量分类；规则学习；重复增量式降低错误剪枝；不平衡数据

DOI：1015938/jjhust201705016

中图分类号： TP393

文献标志码： A

文章编号： 1007-2683（2017）05-0085-06

Network Flow Classification MethodruleBased

CAO Yanzhen，HE Yunbin，ZHU Suxia，SUN Guanglu

（School of Computer Science and Technology， Harbin University of Science and Technology， Harbin， 150080， China）

Abstract：In this paper， repeated incremental pruning to produce error reduction which is a rule learning method is used to solve network traffic classification The method can be used to dig out the correlations between attributes and classes， which are utilized to build a classifier for traffic classification The proposed method can decrease the classification error rate when the traditional machine learning method has a large number of imbalanced data sets in the network traffic Experiments show that the method has a very high classification of accuracy， recall and precision in network traffic classification standard data sets

Keywords：traffic classification； rulebased learning； repeated incremental pruning to produce error reduction； unbalanced data

收稿日期： 2016-01-28

基金项目： 国家自然科学基金（60903083， 61502123）；黑龙江省新世纪人才项目（1155ncet008）；黑龙江省博士后科研启动基金

作者简介：

曹彦珍（1991—），女，硕士研究生；

朱素霞（1978—），女，博士，副教授

通信作者：

何云斌（1972—），男，博士，教授，Email：hybha@ 163com

0引言

隨着网络中各种应用的逐渐增加，网络越来越难以管理，网络安全问题也越来越严重，在这种情况下网络流量分类技术应运而生。网络流量分类技术是针对网络中的每一条流量进行分类，识别出其所属的应用层协议类型，为流量控制提供依据，是网络安全技术的基础研究之一。同时，网络流分类技术能够增强网络的可控性， 帮助相关的研究人员掌握网络上的流量分布情况， 帮助网络运营商优化服务质量，预防并阻止各种网络犯罪行为[1][2]。

已有的网络流量分类技术有基于端口、基于载荷、基于行为以及基于机器学习等方法。随着越来越多的应用采用动态端口传输，导致基于端口的方法失效；基于载荷的方法有很高的识别精度，但侵犯用户隐私，并且不能识别加密流量；基于行为的方法不能实现实时分类等[3-5]。近几年，机器学习得到了迅猛发展，很多研究者将机器学习方法应用到了网络流分类中，包括朴素贝叶斯（naive bayesian，NB）[6]、支持向量机（support vector machine，SVM）[7]、C45决策树[8]等，并取得了不错的效果。

面对网络应用的快速发展，网络中流量会出现应用协议类别不平衡的情况，而传统的网络流量分类方法的分类性能往往偏向大类，而忽略小类。在面对大量不平衡数据，传统的机器学习方法不能取得很好的效果。因此，本文提出一种基于重复增量式降低错误剪枝（repeated incremental pruning to produce error reduction，Ripper）的网络流量分类方法，由于Ripper方法是按照出现最不频繁的类别到出现最频繁的类别的顺序产生规则的，使得它对于大量的不平衡数据集有很好的分类性能。

本文在第1部分简要介绍了相关工作，包括应用于网络流量分类的机器学习方法以及Ripper方法的应用等。第2部分首先介绍了特征选择方法，然后详细介绍了基于Ripper的网络流量分类方法。第四部分介绍了实验环境和实验数据集，最后一部分得出实验结果并对其进行分析，及得出结论。

1相关工作

随着机器学习在各个领域的广泛应用，基于机器学习[9]的网络流量分类成为近年来的研究热点。2004年，基于机器学习的网络流量分类方法被一些学者提出，这种方法是根据网络流量具有的统计特性来对网络流量进行分类[10]。到现在已经有很多种机器学习方法被引入到网络流量分类的研究中，其中具有代表性的有： Moore等在2005年利用有监督的朴素贝叶斯方法对网络流量进行分类，取得了90%以上平均识别准确率[4]。Erman等在2007年融合了有监督和无监督的机器学习方法，提出了半监督的机器学习方法解决网络流量分类问题，取得了很好的效果[11]。徐鹏等在2008年提出一种基于C45决策树的网络流量分类方法，利用训练数据集中的信息熵来构建模型，这种方法也被证明在分类稳定性上有很好的效果[8]。之后他又提出一种基于支持向量机的网络流量分类方法，该方法能够解决以往方法中条件独立假设的问题，在先验知识相对不足的情况下，具有较高的分类准确率和分类稳定性[7]。Yu Jin等在2012年提出一种模块化的机器学习方法，应用于大型网络的流量分类中并取得了较好的效果[12]。endprint

不同的学习模型有不同的知识表示形式，其中，规则是一种非常直观和自然的知识表示形式，由于其形式简单、无结构而被广泛研究，并得到快速发展。Ripper方法由Cohen提出[13]，是基于规则学习的方法中较为经典的一种。Nilgün等在2010年将Ripper方法用于对肝炎引起的死亡风险问题进行预测，实验结果显示Ripper方法有不错的预测准确率，并且能够产生非常简单的规则[14]。2011年，Anil Rajput等利用Ripper方法处理电子政务数据，实验结果表明通过Ripper方法产生的规则简单易懂，利于相关人员对电子政务数据的研究和使用[15]。电子科技大学的钟星将Ripper方法用于研究软件缺陷预测，并取得了不错的实验效果[16]。M Tarun等将Ripper方法应用在教育研究中，通过对应试者的相关特征进行分析，并预测该应试者能否通过执照考试，实验结果显示该方法在预测方面有很高的准确率[17]。中国科学技术大学的张小康将Ripper方法应用于恶意代码的检测技术，取得了不错的效果[18]。GMeeraGandhi等在对网络入侵检测的研究中，通过多种评估项对基于规则的几种归纳学习方法进行对比，结果显示Ripper方法在基于规则学习的方法中能表现出很好的性能[19]。

2基于Ripper的流量分类方法

本文首先对网络流分类问题进行形式化定义。给定网络流样本集S={s1，s2，…，sn}，其特征集为F={f1，f2，…，fm}，其中n是样本个数，m是特征维数，则对于某一条样本可以表示为si={si1，si2，…，sim}，1≤i≤n。si的类别 ci∈C，C={c1，c2，…，cq}为类别集合，q为类别数量。

利用基于规则学习的方法处理分类问题通常分为两步：第一步是通过对训练样本归纳学习总结出特征与类别之间的关联关系，形成if-then形式的规则；第二步是利用形成的规则对未知的样本进行匹配检测，以达到分类的目的。本文首先采用ReliefF算法对数据进行降维，然后将降维后的数据利用Ripper方法进行规则提取，得到最简的规则对测试数据进行测试。

21特征选择算法

由于网络流量的特征中存在与类别无关特征和冗余特征，因此需要对数据进行特征选择。本文应用ReliefF算法进行特征选择，该算法通用性较强，复杂性较低。

ReliefF算法是从训练集中每一类的样本中各选择d个距离si最近的样本，其中与si同类的d个样本定义为集合H，与si不同类的样本根据所属类别c的不同分别定义为集合M（c），然后计算不同类别的样本在某一特征t上的相关性，并给予不同的权重，W={wi，w2，…，wp}为最终所求的特征权重向量，并根据权重大小将特征按降序排序，从而得到特征对类别的从强到弱的区分能力顺序。

ReliefF具体算法如下：

算法1 ReliefF

输入：样本集S，特征集F，类别集C，近邻数d，取样次数r

输出：权值向量W

1初始化W=0

2for i←1 to r do

3从S中随机选择一个样本si；

4从与si同类的样本中选择最近的d个近邻，记为H；

5for each c∈C

6从与si不同类的样本中选择最近的d个近邻，记为M（c）；

7wt=wt-∑x∈Hdiff（t，si，x）/（r*d）+

∑c≠class（si）[p（c）1-p（class（si））∑x∈M（c）diff（t，si，x）]/（r*d）

diff（t，si，x）=|sit-xtmaxt-mint|

8endfor

22基于Ripper的流量分类方法

规则学习是通过对训练集的学习，总结归纳出特征值与类别之间的某种关系，形成if-then形式的规则，再利用这些形成的规则对数据集进行匹配检测。规则的一般形式是：

ΛNi=1（ai=vi）→ci（1）

式中：箭头左边项称为规则前件；ai表示特征；vi表示特征值；箭头右边项称为规则后件；ci表示结论，即样本所属的类别。

Ripper方法是一种用于快速分类的规则学习方法，该方法是对增量式降低错误剪枝方法（Incremental Reduced Error Pruning，IREP）的一种改进。对于网络流量中多种应用类别的分类问题，首先按照应用类别出现的频繁程度进行排序，假设{c1，c2，…，cq}是排序后的类别顺序，其中c1是最不频繁的类别， cq是最频繁的类别。然后将类别按照排列好的顺序依次产生规则：首先将c1的样本作为正例，其余类别样本全部作为反例，并产生区别正例和反例的规则，依次执行，直到剩下cq类，并将其作为默认类。这样Ripper方法能够最先处理最不频繁出现的类别，最后处理最频繁出现的类别，使用从一般到特殊的策略进行规则的生成。正是由于Ripper产生规则的特殊性，使它對于处理不平衡数据有很好的性能。

Ripper方法的流程图如图1所示。

Ripper方法主要分两部分，一部分为扩展，另一部分为收缩，在扩展的过程中，首先将规则集置空，再向规则集中添加条件，直到该规则集能够扩展到涵盖整个数据集为止；而在收缩的过程中，却是不断地删除规则和收缩条件。最后利用式（2）来确定是否达到最精简的规则：

C=xk-xpxk+xp（2）

其中：xk是规则所覆盖的数据个数，xp是没有被覆盖的数据个数，当函数值C不能再变大时方法停止收缩。Ripper方法的具体算法如下：

算法2 Ripper

输入：训练集S

输出：规则集Rendprint

1初始化R={}

2for{c1，c2，…，cq}中的每一类

3将所选中的类别的样本作为正例Pos，其余类别的样本作为反例Neg

4While Pos≠null do

//生长阶段

5把Pos分为生长正例PosGrow （2/3）和剪枝正例PosPrune （1/3）

6把Neg分为生长反例NegGrow （2/3）和剪枝反例NegPrune （1/3）

7通过贪婪算法，在PosGrow集上利用信息增益条件P（log（pt）-log（PT））为特征值生成规则r

//修剪阶段

8根据公式（2）的度量条件在PosPrune和NegPrune上对r进行剪枝，得到规则r′

9把r′加入到规则集R中，并删除r′覆盖的Pos和Neg中的样本

10endWhile

11return R

本文将Ripper方法应用到网络流量分类中，对于某一条样本si， Ripper方法可以提取出以下格式的规则，从而形成规则库：

class1：si1 =a，si2 =b。如果si1为a，si2为b，那么这条样本属于class1；

class2：si3=c，si5=d。如果si3为c，si5为d，那么这条样本属于class2；

class3：true。如果不满足以上任何一个规则，则这条样本属于class3。

3实验

31实验环境

本文在实验中使用了新西兰怀卡托大学Witten教授等人开发的开源工作平台Weka3713[20]。该工具利用Java语言实现了基于朴素贝叶斯、支持向量机、C45决策树、规则等多种分类方法。本文的实验平台为PC机，其CPU为Intel（R）Core（TM）i3340GHz，内存为4G，运行Windows7操作系统。

32实验数据

为了验证方法的有效性，本文采用的数据集是剑桥大学Moore教授等人在网络流量分类上使用的标准数据集[4]。该数据集是从2003年8月20日0时到24时流经3个生物学研究所中共享的网络出口，这些网络样本被分为10个子集，形成实验数据集。

数据集一共包含12类应用，但是某些应用的样本在数据子集中的数量过少，不足以用来训练分类器，因此，这里我们选择其中的六类进行研究，分别是：WWW、MAIL、FTPDATA、DATABASE、P2P、SERVICES。在这六类中，WWW的数量占总数量的一半，其余五类的数量一共占总数量的一半，是一种典型的不平衡数据集。并且，每两个数据子集作为一个实验数据集，即entry01和entry02作为t1，entry03和entry04作为t2，entry05和entry06作为t3，entry07和entry08作为t4，entry09和entry10作为t5。另外，为了得到大量的不平衡数据，我们按照上述的比例将多个数据子集进行合并，形成足够数量的数据样本。表1为通过ReliefF算法选择出的特征子集，表2为实验数据集中各个类别的样本数量。

33实验结果与分析

实验利用t1、t2、t3、t4、t5数据集分别在朴素贝叶斯、支持向量机、C45决策树、Ripper这四个分类器上做的对比实验，表3是将t1作为训练集，将t2、t3、t4、t5分别作为测试集的实验结果。图2、图3和图4是将t1作为训练集，将t2、t3、t4、t5分别作为测试集时，朴素贝叶斯、支持向量机、C45决策树分别与Ripper方法的准确率对比情况。另外，实验也采用各类别的查准率（Precision）、查全率（Recall）和它们的调和平均值FMeasure来评价结果。表4给出在不同方法准确率对比实验中，以t1作为训练集，t4作为测试集时的评价指标。

另外进行了一组分别采用不同样本数的数据集在Ripper方法上进行的对比实验，并对该方法进行评估。在Moore数据集上分别选取了50000个样本、100000个样本、150000个样本以及200000个样本进行实验，在该实验中所采取的实验方法是十折交叉。图5是不同数量的样本的数据集在Ripper方法上的分类准确率。

通过以上实验结果可以看出，在相同的数据集下，相比于传统的朴素贝叶斯、支持向量机、C45决策树等方法，Ripper方法有更高的准确率、查准率和查全率。在使用同一种方法时，在不同的样本数进行实验的结果中，增大样本规模会对分类建模效果有一定提升作用。

4结论

本文重点介绍了一种规则学习算法Ripper，并将其应用于网络流量分类的研究中，重点解决传统网络流量分类方法中分类模型偏向大类、忽略小类的问题。在训练过程中，应用ReliefF特征选择算法对数据进行降维，对降维后的数据用Ripper方法进行分类。在Moore数据集上与朴素贝叶斯、支持向量机、C45决策树等方法进行实验对比，结果表明在網络流量数据出现大量的类别不平衡问题时，Ripper方法能够实现很好的分类性能。

参 考 文 献：

[1]MOORE A W，PAPAGIANNAKI K Toward the Accurate Identification of Network Applications[C]//International Workshop on Passive and Active Network Measurement Springer Berlin Heidelberg， 2005： 41-54

[2]孙广路， 郎非， 杨明明 基于混合方法的流量测量系统[J]. 电机与控制学报， 2011， 15（6）： 91-96endprint

[3]FINSTERBUSCH M， RICHTERr C， ROCHA E， et al A Survey of Payloadbased Traffic Classification Approaches[J]. IEEE Communications Surveys & Tutorials， 2014， 16（2）： 1135-1156

[4]CHENG G， WANG S Traffic Classification Based on Port Connection Pattern[C]//Computer Science and Service System （CSSS）， 2011 International Conference on IEEE， 2011： 914-917

[5]董辉， 孙广路， 李丹丹， 等 基于链路同质性的应用层流量分类方法[J]. 哈尔滨理工大学学报， 2013， 18（4）： 84-88

[6]MOORE A W，ZUEV D Internet Traffic Classification Using Bayesian Analysis Techniques[C]//ACM SIGMETRICS Performance Evaluation Review ACM， 2005， 33（1）： 50-60

[7]林森， 徐鹏， 刘琼 基于支持向量机的流量分类方法[J]. 计算机应用研究， 2008， 25（8）： 2488-2490

[8]ZHANG Y， WANG H， CHENG S A Method for Realtime Peertopeer Traffic Classification Based on C4 5[C]//Communication Technology （ICCT）， 2010 12th IEEE International Conference on IEEE， 2010： 1192-1195

[9]王涛，余顺争 基于机器学习的网络流量分类研究进展[J]. Journal of Chinese Computer Systems： Vol33 No5 2012

[10]ROUGHAN M， SEN S， SPATSCHECK O， et al Classofservice Mapping for QoS： a Statistical Signaturebased Approach to IP Traffic Classification[C]//Proceedings of the 4th ACM SIGCOMM conference on Internet measurement ACM， 2004： 135-148

[11]ERMAN J， MAHANTI A， ARLITT M， et al Offline/Realtime Traffic Classification Using Semisupervised Learning[J]. Performance Evaluation， 2007， 64（9）： 1194-1213

[12]JIN Y， DUFFIELD N， ERMAN J， et al A Modular Machine Learning System for Flowlevel Traffic Classification in Large Networks[J]. ACM Transactions on Knowledge Discovery from Data （TKDD）， 2012， 6（1）： 4

[13]COHEN WW Fast Effective Rule Induction[C]//Proceedings of the twelfth international conference on machine learning 1995： 115-123

[14]ULUTA

瘙 塁 DEMIR N， Dal Evaluation of Risk of Death in Hepatitis by Rule Induction Algorithms[J]. Scientific Research and Essays， 2010， 5（20）： 3059-3062

[15]RAJPUT A， AHARWAL R P， DUBEY M， et al J48 and JRIP Rules for EGovernance Data[J]. International Journal of Computer Science and Security （IJCSS）， 2011， 5（2）： 201

[16]钟星 基于数据挖掘和多目标决策的软件缺陷预测方法研究[D]. 电子科技大学， 2011

[17]IVY M T， BOBBY D G Generating Licensure Examinatio Performance Models Using PART and JRip Classifiers： A Data Mining Application in Education[J] International Journal of Computer and Communication Engineering， 2014，3（3）：

[18]張小康 基于数据挖掘和机器学习的恶意代码检测技术研究[D]. 合肥： 中国科学技术大学， 2009

[19]MEERA G G， KUMARAVEL Appavoo Effective Network Intrusion Detection using Classifiers Decision Trees and Decision rules[J] Int J Advanced Networking and Applications， 2010，2（3）：686-692

[20]WITTEN I H， FRANK EData Mining Practical Machine Learning Tools and Technique[M].2nd ed北京：机械工业出版社，2005

（编辑：温泽宇）endprint