分类emule服务器

软件学报ISSN1000-9825,CODENRUXUEWE-mail:jos@iscas.
ac.
cnJournalofSoftware,2012,23(6):15001516[doi:10.
3724/SP.
J.
1001.
2012.
04074]http://www.
jos.
org.
cn中国科学院软件研究所版权所有.
Tel/Fax:+86-10-62562563分类不平衡协议流的机器学习算法评估与比较张宏莉,鲁刚+(哈尔滨工业大学计算机科学与技术学院计算机网络与信息安全技术研究中心,黑龙江哈尔滨150001)MachineLearningAlgorithmsforClassifyingtheImbalancedProtocolFlows:EvaluationandComparisonZHANGHong-Li,LUGang+(ComputerNetworkandInformationSecurityTechnologyResearchCenter,SchoolofComputerScienceandTechnology,HarbinInstituteofTechnology,Harbin150001,China)+Correspondingauthor:E-mail:lgang198202@126.
comZhangHL,LuG.
Machinelearningalgorithmsforclassifyingtheimbalancedprotocolflows:Evaluationandcomparison.
JournalofSoftware,2012,23(6):15001516.
http://www.
jos.
org.
cn/1000-9825/4074.
htmAbstract:Inthecaseoftheimbalancedprotocolflows,thechangesofflowdistributionhaveahugeimpactontheaccuracyandstabilityoftrafficclassifiersthatusemachinelearningalgorithms.
Itisveryimportanttoselectasuitablemachinelearningalgorithmtoclassifytheimbalancedprotocolflowsonline.
Bymeansofsingle-factorexperimentdesign,thispaperverifiesthatitispossibleforC4.
5decisiontree,NaveBayeswithkerneldensityestimation(NBK)andsupportvectormachine(SVM)toclassifytrafficwiththefirstfourpacketsoftheTCPconnection.
Aftercomparingtheperformancesofthethreeclassifiersabovementioned,thestudyfindsthatthetestingtimeofC4.
5decisiontreeistheshortestandSVMisthemoststable.
Finally,Baggingalgorithmisappliedtoclassifytraffic.
Theexperimentalresultsshowthat,thestabilityofBaggingissimilartoSVMandthetestingtimeandmodelingtimeofBaggingisclosetoC4.
5decisiontree.
Therefore,Baggingclassifieristhemostsuitabletoclassifytrafficonline.
Keywords:imbalance;featureselection;trafficclassification;ensemblelearning;single-factorexperiment摘要:网络协议流不平衡环境下,流样本分布的变化对基于机器学习的流量分类器准确性及稳定性有较大的影响.
选择合适的机器学习算法以适应网络协议流不平衡环境下的在线流量分类,显得格外重要.
为此,首先通过单因子实验设计,验证了C4.
5决策树、贝叶斯核估计(NBK)和支持向量机(SVM)这3种分类算法统计TCP连接开始的前4个数据包足以分类流量.
接着,比较了上述3种分类算法的性能,发现C4.
5决策树的测试时间最短,SVM分类算法最稳定.
然后,将Bagging算法应用到流量分类中.
实验结果表明,Bagging分类算法的稳定性与SVM相似,且测试时间与建模时间接近于C4.
5决策树,因此更适于在线分类流量.
关键词:不平衡;特征选择;流量分类;集成学习;单因子实验中图法分类号:TP181文献标识码:A基金项目:国家自然科学基金(60903166);国家重点基础研究发展计划(973)(2007CB311101,2011CB302605);国家高技术研究发展计划(863)(2010AA012504,2011AA010705)收稿时间:2010-06-24;定稿时间:2011-06-20张宏莉等:分类不平衡协议流的机器学习算法评估与比较1501准确的网络流量分类是确保网络安全的关键,有助于保护网络资源、强化机构策略,例如带宽限制、网络计费、恶意流量检测等等.
早期使用固定端口号识别流量,但目前许多P2P应用常使用随机端口号.
Mandukar等人[1]发现,端口识别技术已不能识别出30%~70%的互联网流量.
目前,绝大多数机构常采用深度数据包检测(deeppacketinspection,简称DPI)技术分类流量.
DPI技术利用协议分析和还原技术提取协议载荷特征,通过模式匹配算法搜索载荷特征识别流量.
DPI技术准确性高且可靠性好,但主要缺点在于其触犯用户隐私,且对协议负载加密的流量识别能力有限.
为此,Karagiannis等人[2]开发了基于应用行为的流量分类系统BLINC.
BLINC系统关注于主机的会话模式并使用图加以描述,其流量分类准确率可达90%以上.
但BLINC系统只能粗粒度地识别P2P流量,不能够将P2P流量细分到具体的协议.
此外,Kim等人[3]指出,BLINC流量分类系统适合于部署到单宿主边缘网络(single-homededgenetwork)的边界连接处,而不适合于部署到骨干节点.
基于机器学习的流量分类技术也不依赖于应用层负载,它分类的对象是流,流在本文里被定义为使用相同的五元组模式源IP,目的IP,源端口,目的端口,传输层协议进行通信的双向数据包集合,即通信双方的一次会话.
基于机器学习的流量分类技术需要统计数据包层(packet-level)和数据流层(flow-level)信息,例如包大小、包到达时间间隔和流的大小等等.
相比于基于应用行为的流量分类技术,机器学习流量分类技术识别的粒度更细.
目前,基于机器学习的流量分类技术常作为DPI技术的辅助部分,流量分类工具Tstat2.
0[4]就结合使用DPI技术和机器学习技术.
但Tstat2.
0仅利用文献[5]提出的机器学习算法识别skype流量,还不能够利用该方法分类网络中所有流量.
其主要原因在于,基于机器学习的流量分类器受网络环境的影响较大,网络流样本的统计分布发生变化、网络延迟和拥塞等因素都会对基于机器学习的流量分类器产生影响.
本文结合实际的网络环境,比较分析基于监督学习的流量分类器的性能,尤其关注以下两点:(1)网络流样本分布的动态变化对基于机器学习的流量分类器性能的影响;(2)网络流样本分布的不平衡性对基于机器学习的流量分类器性能的影响.
流样本分布的不平衡性在这里是指某一种网络协议的流样本数远远超过其他网络协议.
与以往研究工作不同的是,本文的实验数据集体现出协议流样本分布不平衡性,即数据集中http协议类别的样本数远远大于其他类别的样本数.
本文的研究贡献在于以下几点.
(1)尝试细粒度地将流量按照不同的协议进行区分,而不是粗粒度地将网络流量分类成BULK,P2P和Services等等.
之所以细粒度地识别,是因为同一种应用可以运行多个协议.
例如,emule应用即支持eDonkey协议下载方式,又支持HTTP协议下载方式.
而不同协议流的统计特征不尽相同;(2)根据C4.
5决策树、SVM和NBK这3种不同分类算法的准确性,本文进行了单因子方差分析实验,以确定统计TCP流开始时合适的数据包数目.
统计分析TCP流开始的前若干个数据包来决定整个TCP流的类别,这可以提高流量分类器的分类速度,为机器学习流量分类器在线分类提供依据;(3)本文在协议流样本分布不平衡数据集上,从流的准确性、字节的准确性、召回率和精度这4个指标详细地比较分析C4.
5决策树、NBK和SVM这3种分类算法的性能,分析了协议流样本分布的不平衡性对3种分类算法性能的影响;(4)本文将Bagging集成学习算法应用到流量分类中,解决了C4.
5决策树分类不稳定问题.
本文实验验证了Bagging集成学习分类算法更适合于在线分类流量.
本文第1节阐述机器学习流量分类的相关研究.
第2节分析流量分类算法的原理.
第3节介绍实验环境,给出实验数据集和特征选择的方法.
第4节比较分析C4.
5决策树、NBK和SVM这3种分类算法的实验结果.
第5节介绍基于Bagging集成学习的流量分类器.
第6节总结全文.
1相关研究近年来,国内外关于机器学习的流量分类技术已经有大量的研究,这些研究的侧重点主要在提高分类器的准确性、实时性以及提取和选择有效的网络流特征上.
Moore等人[6]利用NBK算法分类流量,将网络流粗粒度地分成10种不同业务,分类准确性为95%左右.
Li等人[7]在Moore工作的基础上,采用基于相关的快速过滤算法(fastcorrelation-basedfilter,简称FCBF)进行特征选择,选择了12种时空稳定的特征.
Este等人[8]利用互信息量比1502JournalofSoftware软件学报Vol.
23,No.
6,June2012较网络流特征的时空稳定性,发现TCP连接建立后的第一个数据包大小所含的信息量最大,并在不同的时间和地点采集的数据上进行测试,验证了数据包大小是最稳定的特征.
Bernaille等人[9]尝试统计TCP流开始的前5个数据包大小,使用K均值聚类算法分类流量.
Soysal等人[10]评估Bayes网络、决策树和多层感知机(multilayerperceptrons)这3种机器学习算法,发现Bayes网络和决策树更适合于高速分类网络流.
Pietrzyk等人[11]在不同地点采集的数据集上,用NBK算法、Bayes网络和C4.
5决策树这3种机器学习算法进行地点交叉(cross-site)测试,发现训练数据集和测试数据集都是同一地点采集时,3种分类算法都表现出最好的性能;而训练数据集和测试数据集都是在不同地点采集时,3种分类算法的性能都有所下降.
他们认为,造成这种现象的原因是分类算法对训练数据的过拟合(dataoverfitting).
他们同时也发现,相比于其他两种分类算法,C4.
5决策树的分类性能最好.
国内关于流量分类的研究中,徐鹏等人[12]也发现C4.
5决策树分类算法要优于NaveBayes分类算法和NBK分类算法.
文献[1012]仅仅比较了流量分类的流准确性,并没有给出分类的字节准确性,Erman等人[13]发现,0.
1%的大象流占据了整个流量传输字节数的46%.
如果流量分类器未识别出这0.
1%的大象流而得到99.
9%的流准确性,那么流量分类器将损失46%的字节准确性.
表1比较分析了目前国内外基于机器学习的流量分类技术.
Table1Comparisonoftrafficclassificationtechnologies表1流量分类技术的比较文献机器学习算法流量特征流量类别分类粒度是否考虑字节准确性Moore等人[6]NaveBayes和NBK分类算法从完整数据流中提取248种流量特征,包括流持续时间、TCP端口、包到达时间间隔的统计信息、负载大小的统计信息等BULK,DatabaseP2P,Mail,Services等粗粒度否Li等人[7]C4.
5决策树和NaveBayesTCP端口、TCP标识位的统计信息、TCP分段大小的统计信息与文献[6]相同粗粒度是Bernaille等人[9]K均值聚类TCP流开始的前5个数据包大小和包方向eDonkey,ftp,http,kazaa等细粒度否Soysal等人[10]Bayes网络、决策树和多层感知机完整的TCP流统计特征P2P,Web,Bulk等粗粒度否Pietrzyk等人[11]NBK,Bayes网络和C4.
5数据包层面:数据包大小和数据包传输方向数据流层面:TCP端口和标识位的统计信息Web,eDonkey,Mail,Chat,Gnutella等粗粒度否徐鹏等人[12]C4.
5决策树与网络流相关的34个统计特征Web,BT,BULK等粗粒度否徐鹏等人[14]SVM与文献[6]相同与文献[6]相同粗粒度否由表1可见,目前基于机器学习的流量分类技术要么粗粒度地分类流量,要么忽略了分类的字节准确性.
此外,文献[9,15]的流量分类工作没有考虑识别流样本数小于500的网络应用.
然而我们的实验结果表明,即使网络应用传输的数据流非常少,但他们传输的字节数却很大,丢掉这些数据流将会导致分类器的字节准确性下降(详见第3.
2节).
与以往工作相比,本文按照不同协议细粒度地分类流量.
从在线分类流量的角度考虑,在本文的实验数据集上通过单因子方差实验,验证了C4.
5决策树、NBK和SVM统计TCP连接开始的前4个数据包足以分类流量.
本文还从字节准确性、流准确性、各协议类别的召回率和精度这4个指标,详细地比较上述3种分类算法的性能,分析了协议流不平衡性对这3种分类算法性能的影响.
最后,本文将Bagging集成学习算法应用到流量分类中,并在协议流不平衡数据集上与上述3种分类算法做了实验比较分析.
2流量分类算法本节简要介绍NBK、C4.
5决策树和支持向量机SVM这3种分类算法.
张宏莉等:分类不平衡协议流的机器学习算法评估与比较15032.
1NBK分类算法本节先介绍NaveBayes算法,因为NBK分类算法是NaveBayes算法的一般形式.
假定有n个类别Ci(i=1,…,n),任意网络流样本y属于类别Ci的概率为1(|)()iiiiinjjjfyCPCfyCPCPCyPyfyCPC===∑(1)我们将流样本y指派到使得P(Ci|y)(i=1,…,n)最大的类别中,其中,f(.
|Cj)为概率密度函数,NaveBayes算法假设它服从正态分布,但实际上总体的分布常常不是正态分布.
NBK分类算法采用核函数来拟合总体分布,如公式(2)所示.
:()1(|)iijjijxCxcctxftCKnhh==∑(2)这里,h是核带宽(kernelbandwidth),K是核函数.
核函数的值非负且满足()d1Kxx+∞∞=∫.
由于高斯函数有很好的平滑特性,NBK分类算法常采用高斯函数作为核函数.
从公式(1)、公式(2)可以看出,NBK分类算法分类结果依赖于训练样本集的分布状况.
2.
2C4.
5决策树分类算法C4.
5算法采用自顶向下递归分治的方式构造分类模型,其构造的分类模型是一种树的结构,每个分裂节点(非树叶节点)表示一个属性上的测试,每个分枝代表一个测试输出,而每个树叶节点存放一个类标号.
决策树构建的原则就是使每次划分后的不确定性尽可能地小.
C4.
5算法采用信息增益率作为属性选择的度量,每次划分都是选择信息增益率最大的属性作为分裂节点.
假定有n个类别Ci(i=1,…,n),D为网络流的训练样本集.
在训练集D中,分类所需的期望信息(即D的熵)为21()logniiiHDpp==∑(3)其中,pi为训练集D中的流样本属于类别Ci的概率.
假定选择属性A作为分裂节点,属性A根据训练数据集的测试有m个不同的输出,将D划分为m个子集Dj(j=1,2,…,m).
划分后的训练集再分类所需的信息量为1||()()||mjAjjDHDHDD==*∑(4)于是,由公式(3)、公式(4)得到此次划分所获得的信息增益Gain(A)=H(D)HA(D)(5)C4.
5算法使用分裂信息值将信息增益规范化.
分裂信息定义为21||||()log||||mjjAjDDSplitHDDD==*∑(6)因此,信息增益率可定义为()()()GainAgainratioASplitHA=(7)由公式(3)~公式(7)可见,C4.
5决策树算法实际上采用了熵最小选择策略.
该算法每选择一次分裂节点就要计算信息增益率,而信息增益率的计算仍旧依赖于训练样本集中各类别的概率分布.
C4.
5算法采用剪枝法解决训练数据过拟合问题.
剪枝后的分类树更小,复杂度更低,因此在实际网络流分类时,剪枝后的分类树分类速度更快、更好.
2.
3SVM分类算法SVM算法将实际问题通过非线性变换到高维的特征空间,并在高维空间中构造线性判别函数来实现分类.
在构建SVM分类模型时,首先选择多项式、高斯函数等核函数将输入数据映射到高维空间,然后在高维空间中1504JournalofSoftware软件学报Vol.
23,No.
6,June2012搜索线性最佳分类超平面.
分类超平面可描述为**1()sgn(,)kiiiifxwyKxxb==+∑(8)其中,w*和b*是超平面的参数,K(xi,x)是核函数,yi∈{1,1}是类别标记.
本文选择高斯径向基函数作为核函数,xi是第i个训练样本,而x是测试样本.
由公式(8)可见,SVM算法根据f(x)的符号进行分类,即f(x)>0的样本归为一类,而f(x)Fα,a1,Na时,应该拒绝H0,接受H1.
代入相应的参数值,得到Fα,a1,Na=F0.
05,6,35≈2.
34.
基于表5中的数据,我们用Excel的数据分析工具得到F0的值.
发现C4.
5决策树和SVM分类算法的F0分别为0.
032和0.
065,都小于F0.
05,6,35,故可接受H0.
即对于C4.
5决策树和SVM分类算法在统计流开始的不同数据包个数时,分类准确性并无显著性差异.
随着统计的数据包个数增加,提取相应统计特征的时间开销和空间开销也会有所增加.
因此,在本文实验数据集上,对于C4.
5决策树和SVM分类算法而言,选定统计流开始的前4个数据包是最合适的.
NBK分类算法的F0值为6.
006大于F0.
05,6,35,故拒绝H0,接受H1,即NBK分类算法在选定不同数据包个数时,分类准确性有显著性差异.
由图3可见,NBK分类算法的平均分类准确性波动幅度较大,尤其在选定前5个数据包数目时,分类的平均准确性达到最低.
而随着统计分析6,7,8,9个数据包,其准确性逐渐升高,在第9个数据包时,分类准确性到达最高.
但是,统计前9个数据包的平均分类准确性,并未比前4个数据包的平均分类准确性高张宏莉等:分类不平衡协议流的机器学习算法评估与比较1507出很多.
我们用t检验的方法来验证它们之间是否存在显著性差异.
假设统计前9个数据包和前4个数据包的平均分类准确性并无明显差异,即H0:μ4μ9=0,其备择假设为H1:μ4μ9≠0.
检验统计量t0服从自由度为a1的t分布.
这是一个双边假设检验,当t0>tα/2或者t02.
447,故接受H0.
由此得出,NBK分类算法统计TCP连接开始的前9个数据包和前4个数据包的平均分类准确性并无显著性差异.
因此,在本文实验数据集上,对于NBK分类算法,选定统计流开始的前4个数据包特征是最合适的.
3.
4特征选择特征选择是从一组特征中挑选出一些最有效的特征以达到降低特征空间维数的目的,从而降低计算开销,提高分类效率.
本节采用条件熵的方法来度量特征和类别之间的相关性.
设X是特征集,Y是类别集,X和Y之间的相关性计算为()()log(()),log(yxyyRxRyRHYpypyHYXpxpyxpyx∈∈∈==∑∑∑其中,Rx,Ry分别是x和y的取值范围(|).
()HYHYXCYXHY=H(Y)是在数据集上未使用特征集X时,类别集Y的熵值,而H(Y|X)是在数据集上使用特征集X时,类别集Y的熵值.
C(Y|X)是不确定性系数(uncertaintycoefficient),用于度量X和Y之间的相关性.
C(Y|X)的取值范围在[0,1]之间,当值为0时,表示X和Y没有任何关系;当值为1时,表示特征集X可以完全确定Y.
每确定一个特征子集X,就会得到相应的C(Y|X),本文采用贪婪算法在特征子集空间中进行搜索,选择C(Y|X)值最大的特征子集作为特征选择结果.
我们发现,在dump1~dump6不同的数据集上,特征选择的结果也不同.
这就说明在同一个地点不同的时间内,特征与类别的相关性发生变化.
本节取这6个测试数据集上特征选择结果的并集作为最后分类的特征.
我们从25个特征中选择了8个最有效的特征,提取相应特征所花费的时间开销和空间开销列于表6中,其中,n为统计的数据包数目.
Table6Resultsoffeatureselection表6特征选择的结果特征描述空间复杂度时间复杂度push_pkts_serv从服务器到客户端方向,TCP头中设置push位的数据包数O(1)O(n)init_win_bytes_clnt从客户端到服务器方向,以初始窗口发送的TCP负载大小和O(1)O(n)init_win_bytes_serv从服务器到客户端方向,以初始窗口发送的TCP负载大小和O(1)O(n)avg_seg_size_serv从服务器到客户端方向数据包平均负载大小O(1)O(n)act_data_pkt_clnt从客户端到服务器方向,TCP数据包负载至少1字节的数据包数O(1)O(n)serv_port服务器端口O(1)O(1)second_plength_clnt三次握手建立后,从客户端到服务器方向第2个数据包大小O(1)O(1)fir_sec_diff_clnt三次握手建立成功后,从客户端到服务器的第1个数据包大小与三次握手建立时从客户端到服务器方向的ACK包大小的差值O(1)O(1)4分类算法的比较我们用dump1作为训练数据集建立分类模型,并用剩余的5个数据集作为测试.
之所以选择dump1作为训Fig.
3AverageaccuracyofNBKalgorithm图3NBK分类算法的平均准确性4681090858075706560不同数据包个数平均分类准确性(%)NBK951508JournalofSoftware软件学报Vol.
23,No.
6,June2012练集,原因在于:(1)dump1~dump6这6个数据集是按照时间先后顺序获得的,用dump1作为训练集,剩余5个作为测试集,为的是分析不同分类器的分类准确性是否随时间变化;(2)dump1数据集中的样本并没有覆盖所有的类别(ssh类别中流样本数为0).
用dump1作为训练集符合实际流量分类情况,因为网络实际情况中时常出现新的协议流量,而训练集只能够覆盖部分常用的协议类别.
4.
1评价指标(1)召回率和精度基于机器学习的流量识别技术常用召回率(recall)和精度(precision)两个指标来评价识别结果.
漏报(falsenegative)是指属于类别C的流量而被分类成非类别C,真阳性(truepositive)是指属于类别C的流量而被分类成类别C,误报(falsepositive)是指非类别C的流量被分类成为类别C.
假定误报数为FP,漏报数为FN,真阳性数为TP,召回率和精度的计算方法如下:,.
TPprecisionTPFPTPrecallTPFN=+=+(2)流的准确性和字节准确性流的准确性指被正确识别的流数占标注数据集中所有流数的百分比,字节的准确性是指被正确识别的数据流承载的字节数占标注数据集总字节数的百分比.
4.
2流准确性的比较NaveBayes核估计、SVM和C4.
5决策树这3种分类器的流准确性如图4所示.
由图4可见,C4.
5决策树分类算法和NBK分类算法在不同数据集上,分类的流准确性不稳定,但SVM分类算法相对较稳定.
由于数据集是按照时间顺序排列的,3种分类器的流准确性的总体趋势随着时间的推移是逐渐降低的.
文献[15]指出,新协议流量的出现是导致流量分类器准确率下降的主要原因.
但是,当用dump2作为训练集(dump2数据集已经覆盖了所有类别的流量),而用dump3,dump4,dump5和dump6作为测试集时,3种分类器的流准确性也在逐渐下降,如图5所示.
因此,在本文实验数据集上,新协议流量的出现不是造成分类器流准确性下降的主要原因.
从图1(第3.
2节所示)可见,不同时间采集的数据集上,流样本分布也不同.
流样本分布的动态变化造成了3种分类器随着时间的推移整体准确性逐渐下降.
由图4和图5可见,NBK分类算法的流准确性最不稳定,且随着时间的推移下降趋势最快.
Fig.
4FlowaccuracyofthethreeclassifiersFig.
5Flowaccuracywhendump2isusedastrainingdataset图43种分类器的流准确性图5dump2作为训练集时分类的流准确性当用dump1作为训练集时,我们通过对比3种分类器识别各种协议类别的召回率(如图6所示)和精度(如图7所示),发现3种分类器识别http协议的精度差别不大.
对比图6和图4发现:由于SVM对http协议的召回率高且稳定,使得SVM的整体流准确性是3种分类算法中最高且最稳定的;而且在不同数据集上,如果分类算法对http协议识别的召回率高,那么该分类算法的整体准确性也高.
也就是说,在网络协议流不平衡环境下,分类算法对流样本数比例大的类别识别的召回率影响它分类的整体准确性.
100dump2dump3dump4dump5dump6不同数据集流准确性(%)SVMC4.
5NBK9080706050100dump3dump4dump5dump6不同数据集流准确性(%)908070SVMC4.
5NBK张宏莉等:分类不平衡协议流的机器学习算法评估与比较1509Fig.
6Recallofthethreeclassifierswhenclassifyingeachprotocol图63种分类器分类每种协议的召回率Fig.
7Precisionofthethreeclassifierswhenclassifyingeachprotocol图73种分类器分类每种协议的精度由图6和图7可见,3种分类器对于流样本数比例较小的类别、识别的精度和召回率都不稳定.
例如,在dump2数据集上,识别qq协议的召回率和dump4数据集上的召回率相差就很悬殊.
C4.
5和NBK分类算法对于协议类别1.
0召回率0.
80.
60.
40.
20.
0httpedonkeyxunleisslftppop3qqsshsmtpdump2协议类别1.
0召回率0.
80.
60.
40.
20.
0httpedonkeyxunleisslftppop3qqsshsmtpdump3协议类别1.
0召回率0.
80.
60.
40.
20.
0httpedonkeyxunleisslftppop3qqsshsmtpdump4SVMC4.
5NBK协议类别1.
0召回率0.
80.
60.
40.
20.
0httpedonkeyxunleisslftppop3qqsshsmtpdump5协议类别1.
0召回率0.
80.
60.
40.
20.
0httpedonkeyxunleisslftppop3qqsshsmtpdump6SVMC4.
5NBK协议类别1.
0精度0.
80.
60.
40.
20.
0httpedonkeyxunleisslftppop3qqsshsmtpdump2协议类别1.
0精度0.
80.
60.
40.
20.
0httpedonkeyxunleisslftppop3qqsshsmtpdump3协议类别1.
0精度0.
80.
60.
40.
20.
0httpedonkeyxunleisslftppop3qqsshsmtpdump4协议类别1.
0精度0.
80.
60.
40.
20.
0httpedonkeyxunleisslftppop3qqsshsmtpdump5协议类别1.
0精度0.
80.
60.
40.
20.
0httpedonkeyxunleisslftppop3qqsshsmtpdump61510JournalofSoftware软件学报Vol.
23,No.
6,June2012流样本比例极小的类别,例如smtp协议,识别的召回率和精度要高于SVM.
4.
3字节准确性的比较3种分类器总体字节准确性对比如图8所示.
3种分类器在dump4数据集测试的准确性很低,这是因为训练集dump1没有ssh的流量样本,而测试集dump4有ssh大流样本(如图2所示),由于3种分类器识别不到ssh大流,3种分类器字节准确性下降.
这种现象意味着新的协议流量出现,应该重新训练分类器.
SVM和C4.
5决策树分类的字节准确性差异不大.
在dump5测试集上,C4.
5决策树和SVM分类算法的字节准确性明显高于NBK分类算法.
比较3种分类器对每种协议识别的字节准确性如图9所示,C4.
5决策树和SVM分类算法在dump5数据集上,对eDonkey协议识别的字节准确性都较高;而在这个数据集上,eDonkey协议出现了大流.
所以在dump5数据集上,C4.
5决策树和SVM分类算法的总体字节准确性要高于NBK分类算法.
此外,相比于SVM分类算法,C4.
5决策树分类算法更易识别样本比例极小的协议类别,例如smtp协议流.
这意味着,如果样本比例极小的协议产生了大流,C4.
5决策树用作流量分类器是最合适的.
Fig.
9Byteaccuracyofthethreeclassifierswhenclassifyingeachprotocol图93种分类器分类每种协议的字节准确性4.
43种分类算法的建模和测试时间本节实验的测试环境为:测试主机运行WindowsXP系统,主存为3GB,处理器是AMD96502.
3GHZ.
SVM,C4.
5决策树和NBK这3种分类算法在dump1数据集上的建模时间对比见表7.
Fig.
8Byteaccuracyofthethreeclassifiers图83种分类器的字节准确性1.
0dump2dump3dump4dump5dump6不同数据集字节准确性(%)0.
80.
60.
40.
20.
0SVMC4.
5NBKSVMC4.
5NBK协议类别1.
0字节准确性0.
80.
60.
40.
20.
0httpedonkeyxunleisslftppop3qqsshsmtpdump2协议类别1.
0字节准确性0.
80.
60.
40.
20.
0httpedonkeyxunleisslftppop3qqsshsmtpdump3协议类别1.
0字节准确性0.
80.
60.
40.
20.
0httpedonkeyxunleisslftppop3qqsshsmtpdump4协议类别1.
0字节准确性0.
80.
60.
40.
20.
0httpedonkeyxunleisslftppop3qqsshsmtpdump5协议类别1.
0字节准确性0.
80.
60.
40.
20.
0httpedonkeyxunleisslftppop3qqsshsmtpdump6张宏莉等:分类不平衡协议流的机器学习算法评估与比较1511Table7Modelingtimeofthethreeclassifiers(s)表73种分类器的建模时间(秒)算法SVMC4.
5NBK建模时间6.
380.
310.
03由表7可见,SVM分类算法的建模时间明显比C4.
5决策树分类算法和NBK分类算法的建模时间长.
进一步比较3种分类算法在5个测试数据集上的测试时间,见表8.
我们发现,SVM和NBK分类算法的测试时间明显高于C4.
5算法的测试时间,即C4.
5决策树分类算法更适合于在线分类.
Table8Testingtimeofthethreeclassifiers(s)表83种分类器的测试时间(秒)算法测试数据集SVMC4.
5NBKdump23.
8280.
0783.
516dump31.
9850.
0321.
687dump42.
3120.
0632.
188dump51.
3440.
0161.
25dump62.
7660.
0322.
6725基于Bagging集成学习的流量分类器目前,机器学习领域中常采用两种方案解决类别不平衡问题:重新采集样本技术(resamplingtechniques),即样本比例较小的类别多采集一些样本,或者样本比例较大的类别删除一些样本.
这种方案主要的缺点在于破坏了原有各类别样本分布的状况;构建集成学习分类器.
集成学习分类器由一系列单独训练的分量分类器(componentclassifier)构成,其目的是利用单个模型之间的差异改善模型的泛化性能.
集成学习通过选取不同的数据集来获取个体模型间的差异性.
一般来说,差异性越大,泛化能力越强,分类器就越稳定.
本节选用Bagging算法建立集成分类器,因为Bagging算法通过调节一个参数就可以确定分量分类器间的差异性.
5.
1Bagging算法描述Bagging算法从大小为N的原始训练集X中,依次有放回地独立随机抽取N1(N1≤N)个样本形成自助训练集,并将这个过程独立重复进行多次,直到产生多个独立的自助数据集.
然后,在每个自助数据集上独立地训练一个分量分类器,最终的分类判决将根据这些分量分类器各自判决结果的投票决定.
由于C4.
5决策树分类算法能够确保样本比例极小的类别识别率,且测试时间和建模时间都较短,因此本文选择C4.
5决策树分类算法建立分量分类器,试图通过Bagging算法解决原始C4.
5决策树分类算法的不稳定性问题.
鉴于文献[18]的研究方法,我们认为,当N很大时,N1近似服从Poisson(λ)分布,通过调节参数λ值来确定集成学习分类器的差异性.
文献[18]认为,当λ值越小,差异性越大,分类器越稳定.
但是本文发现,λ值越小将导致集成分类器对样本比例小的类别召回率降低.
图10比较了λ=0.
05,λ=0.
1和λ=0.
2时集成学习分类器的召回率情况.
例如,eDonkey协议属于样本比例小的类别,从图10中还可以看出,λ值越小,对eDonkey协议识别的召回率就越小.
我们在分类稳定性与召回率间做了折中,选择λ=0.
1来建立集成学习分类器.
1512JournalofSoftware软件学报Vol.
23,No.
6,June2012Fig.
10RecallofBaggingwithdifferentλ图10选择不同λ时Bagging算法的召回率5.
2流准确性本节对比分析C4.
5决策树、SVM、NBK分类算法以及Bagging集成学习算法分类的流准确性.
由图11可见,基于Bagging算法的流量分类器,其稳定性和准确性相似于SVM分类算法,明显好于C4.
5决策树和NBK分类算法.
但是分类的流准确性也在随着时间逐渐下降(横轴是按照时间顺序排列的数据集),下降趋势要比C4.
5决策树和NBK分类算法更加缓慢.
由召回率和精度对比(如图12、图13所示)可以看出,基于Bagging算法的流量分类器对样本数极少的类别分类能力不如单独使用C4.
5决策树和NBK分类算法.
例如,Bagging集成学习分类器没有识别出smtp协议流.
Fig.
11Flowaccuracyoffourclassificationalgorithms图114种分类算法的流准确性λ=0.
05λ=0.
1λ=0.
2协议类别1.
0召回率0.
80.
60.
40.
20.
0httpedonkeyxunleisslftppop3qqsshsmtpdump202468协议类别1.
0召回率0.
80.
60.
40.
20.
0httpedonkeyxunleisslftppop3qqsshsmtpdump3协议类别1.
0召回率0.
80.
60.
40.
20.
0httpedonkeyxunleisslftppop3qqsshsmtpdump502468协议类别1.
0召回率0.
80.
60.
40.
20.
0httpedonkeyxunleisslftppop3qqsshsmtpdump4协议类别1.
0召回率0.
80.
60.
40.
20.
0httpedonkeyxunleisslftppop3qqsshsmtpdump6100dump2dump3dump4dump5dump6不同数据集流准确率(%)SVMC4.
5NBKBagging9080706050张宏莉等:分类不平衡协议流的机器学习算法评估与比较1513Fig.
12Recalloffourclassificationalgorithmswhenclassifyingeachprotocol图124种分类算法分类每种协议的召回率Fig.
13Precisionoffourclassifierswhenclassifyingeachprotocol图134种分类算法分类每种协议的精度5.
3字节准确性就字节准确性而言,由图14可见,由于未识别出测试集dump4中的ssh大流样本,4种分类器的字节准确性SVMC4.
5NBKBagging协议类别1.
0召回率0.
80.
60.
40.
20.
0httpedonkeyxunleisslftppop3qqsshsmtpdump3协议类别1.
0召回率0.
80.
60.
40.
20.
0httpedonkeyxunleisslftppop3qqsshsmtpdump2协议类别1.
0召回率0.
80.
60.
40.
20.
0httpedonkeyxunleisslftppop3qqsshsmtpdump4协议类别1.
0召回率0.
80.
60.
40.
20.
0httpedonkeyxunleisslftppop3qqsshsmtpdump6协议类别1.
0召回率0.
80.
60.
40.
20.
0httpedonkeyxunleisslftppop3qqsshsmtpdump5SVMC4.
5NBKBagging协议类别1.
0精度0.
80.
60.
40.
20.
0httpedonkeyxunleisslftppop3qqsshsmtpdump202468协议类别1.
0精度0.
80.
60.
40.
20.
0httpedonkeyxunleisslftppop3qqsshsmtpdump3协议类别1.
0精度0.
80.
60.
40.
20.
0httpedonkeyxunleisslftppop3qqsshsmtpdump502468协议类别1.
0精度0.
80.
60.
40.
20.
0httpedonkeyxunleisslftppop3qqsshsmtpdump402468协议类别1.
0精度0.
80.
60.
40.
20.
0httpedonkeyxunleisslftppop3qqsshsmtpdump61514JournalofSoftware软件学报Vol.
23,No.
6,June2012陡然下降.
这就意味着需要重新训练分类器以识别新协议流.
Fig.
14Byteaccuracyoffourclassifiers图144种分类器的字节准确性由图15可以看出:Bagging集成学习流量分类器对于流样本数比例较大的类别,分类字节准确性较高而且稳定;而对于流样本数比例极小的类别,例如smtp协议,其识别的字节准确性不如C4.
5和NBK算法.
Fig.
15Byteaccuracyoffourclassifierswhenclassifyingeachprotocol图154种分类算法分类每种协议的字节准确性5.
4Bagging分类算法的建模时间和测试时间我们在dump1数据集上建立Bagging分类模型的时间为0.
39s,其建模时间略高于C4.
5决策树分类算法,而明显低于SVM分类算法的建模时间(见表7).
Bagging集成学习分类器的测试时间见表9.
对比表8和表9我们发现,Bagging算法的测试时间略高于C4.
5决策树算法的测试时间,高出的时间范围仅在[0.
04,0.
1]之间.
而Bagging算法的测试时间明显小于SVM和NBK分类算法的测试时间.
1.
0dump2dump3dump4dump5dump6不同数据集字节准确率0.
80.
60.
40.
20.
0SVMC4.
5NBKBagging协议类别1.
0字节准确性0.
80.
60.
40.
20.
0httpedonkeyxunleisslftppop3qqsshsmtpdump202468协议类别1.
0字节准确性0.
80.
60.
40.
20.
0httpedonkeyxunleisslftppop3qqsshsmtpdump502468协议类别1.
0字节准确性0.
80.
60.
40.
20.
0httpedonkeyxunleisslftppop3qqsshsmtpdump402468SVMC4.
5NBKBagging协议类别1.
0字节准确性0.
80.
60.
40.
20.
0httpedonkeyxunleisslftppop3qqsshsmtpdump3协议类别1.
0字节准确性0.
80.
60.
40.
20.
0httpedonkeyxunleisslftppop3qqsshsmtpdump6张宏莉等:分类不平衡协议流的机器学习算法评估与比较1515Table9TestingtimeofBagging(s)表9Bagging分类器的测试时间(秒)数据集dump2dump3dump4dump5dump6测试时间0.
1870.
0780.
1250.
0620.
14综上分析,基于Bagging集成学习算法的流量分类器的分类准确性较高且稳定,其测试时间和建模时间较短,因此更适合于在线分类网络流量.
6总结基于机器学习算法的流量分类器应用于在线分类,是目前流量分类研究的一个趋势.
网络环境的变化会影响机器学习流量分类器在线分类的性能.
本文主要分析协议流不平衡性对流量分类器的影响,协议流不平衡是网络环境中常见现象.
本文在网络协议流不平衡的数据集上进行实验分析,得出以下几点结论:(1)流量分类器在线分类时,要能够确保在连接开始时尽早地分类流.
与以往研究结论不同的是,我们发现,在统计流开始的前4~10个数据包时,SVM和C4.
5决策树分类算法的准确性并无显著性差异.
根据尽早分类流的原则,我们选择统计流开始的前4个数据包.
尽管统计不同的数据包数目对于NBK分类算法有显著性差异,但是对于NBK分类算法统计前4个数据包也是最合适的;(2)在网络协议流不平衡的环境下,SVM分类算法要比C4.
5决策树和NBK分类算法稳定.
SVM分类算法对样本比例大的类别具有最好的召回率,但是C4.
5决策树和NBK分类算法更能够确保对样本比例小的类别的召回率和精度.
3种分类算法相比之下,C4.
5分类算法的测试时间最短,NBK的建模时间最短,而SVM的测试时间和建模时间最长;(3)在网络协议流不平衡的环境下,分类器对流样本比例大的类别识别的召回率将影响分类器的总体准确性.
流样本分布的动态变化,是造成机器学习流量分类器整体准确性随着时间的推移逐渐下降的原因之一;(4)在网络协议流不平衡的环境下,基于Bagging集成学习的流量分类器较为稳定,其准确性较高,且测试时间较短,适合于在线分类网络流.
此外,本文发现,虽然提高Bagging集成学习流量分类器的差异性会使分类器更加稳定,但是这种差异性的提高也会使分类器对样本比例较小的类别识别准确性下降.
相比之下,C4.
5决策树和NBK分类算法更能确保对样本比例较小的类别识别的流准确性和字节准确性.
我们未来的研究工作在于进一步改进Bagging算法,使其对流样本比例极小的类别能够有较高的识别率.
此外我们发现,SVM、C4.
5决策树、NBK和Bagging这4种分类算法对迅雷协议流量识别的召回率很低(如图12所示),这是因为迅雷流量默认使用80端口进行通信,其统计特征与http协议流量很相似.
如何将http协议流量与迅雷协议流量准确地区分开,可以作为我们进一步的研究方向.
References:[1]MadhukarA,WilliamsonC.
AlongitudinalstudyofP2Ptrafficclassification.
In:CeballosS,ed.
Proc.
ofthe14thIEEEInt'lSymp.
onModeling,Analysis,andSimulation.
Washington:IEEEComputerSocietyPress,2006.
179188.
[doi:10.
1109/MASCOTS.
2006.
6][2]KaragiannisT,PapagiannakiK,FaloutsosM.
BLINC:Multileveltrafficclassificationinthedark.
In:GuerinR,GovindanR,MinshallG,eds.
Proc.
ofthe2005Conf.
onApplications,Technologies,Architectures,andProtocolsforComputerCommunications(SIGCOMM2005).
NewYork:ACMPress,2005.
[doi:10.
1145/1080091.
1080119][3]KimH,ClaffyKC,FomenkovM,BarmanD,FaloutsosM,LeeK.
Internettrafficclassificationdemystified:Myths,caveats,andthebestpractices.
In:AzcorraA,VecianaG,eds.
Proc.
ofthe2008ACMCoNEXTConf.
NewYork:ACMPress,2008.
112.
[doi:10.
1145/1544012.
1544023][4]Tstat.
TCPstatisticandanalysistool.
2011.
http://tstat.
tlc.
polito.
it1516JournalofSoftware软件学报Vol.
23,No.
6,June2012[5]BonfiglioD,MelliaM,MeoM,RossiD,TofanelliP.
Revealingskypetraffic:Whenrandomnessplayswithyou.
ACMSIGCOMMComputerCommunicationReview,2007,37(4):3748.
[doi:10.
1145/1282380.
1282386][6]MooreAW,ZuevD.
Internettrafficclassificationusingbayesiananalysistechniques.
ACMSIGMETRICSPerformanceEvaluationReview,2005,33(1):5060.
[doi:10.
1145/1064212.
1064220][7]LiW,CaniniM,MooreAW,BollaR.
Efficientapplicationidentificationandthetemporalandspatialstabilityofclassificationschema.
ComputerNetworks,2009,53(6):790809.
[doi:10.
1016/j.
comnet.
2008.
11.
016][8]EsteA,GringoliF,SalgarelliL.
Onthestabilityoftheinformationcarriedbytrafficflowfeaturesatthepacketlevel.
ACMSIGCOMMComputerCommunicationReview,2009,39(3):1318.
[doi:10.
1145/1568613.
1568616][9]BernailleL,TeixeiraR,AkodkenouI.
Trafficclassificationonthefly.
ACMSIGCOMMComputerCommunicationReview,2006,36(2):2326.
[doi:10.
1145/1129582.
1129589][10]SoysalM,SchmidtEG.
Machinelearningalgorithmsforaccurateflow-basednetworktrafficclassification:Evaluationandcomparison.
PerformanceEvaluation,2010,67(6):451467.
[doi:10.
1016/j.
peva.
2010.
01.
001][11]PietrzykM,CosteuxJL,Urvoy-KellerG,En-NajjaryT.
Challengingstatisticalclassificationforoperationalusage:TheADSLcase.
In:FeldmannA,MathyL,eds.
Proc.
ofthe9thACMSIGCOMMConf.
onInternetMeasurementConf.
(IMC2009).
NewYork:ACMPress,2009.
122135.
[doi:10.
1145/1644893.
1644908][12]XuP,LinS.
InternettrafficclassificationusingC4.
5decisiontree.
JournalofSoftware,2009,20(10):26922704(inChinesewithEnglishabstract).
http://www.
jos.
org.
cn/1000-9825/3444.
htm[doi:10.
3724/SP.
J.
1001.
2009.
03444][13]ErmanJ,MahantiA,ArlittM.
Byteme:Acaseforbyteaccuracyintrafficclassification.
In:SenS,SahuS,eds.
Proc.
ofthe3rdAnnualACMWorkshoponMiningNetworkData(MineNet2007).
NewYork:ACMPress,2007.
3537.
[doi:10.
1145/1269880.
1269890][14]XuP,LiuQ,LinS.
Internettrafficclassificationusingsupportvectormachine.
JournalofComputerResearchandDevelopment,2009,46(3):407414(inChinesewithEnglishabstract).
[15]BernailleL,TeixeiraR,SalamatianK.
Earlyapplicationidentification.
In:DiotC,AmmarM,eds.
Proc.
ofthe2006ACMCoNEXTConf.
NewYork:ACMPress,2006.
112.
[doi:10.
1145/1368436.
1368445][16]L7-filter.
ApplicationlayerpacketclassifierforLinux.
2009.
http://l7-filter.
sourceforge.
net[17]L7-filtersupportedprotocols.
2009.
http://l7-filter.
sourceforge.
net/protocols[18]MinkuLL,WhiteAP,YaoX.
Theimpactofdiversityononlineensemblelearninginthepresenceofconceptdrift.
IEEETrans.
onKnowledgeandDataEngineering,2010,22(5):730742.
[doi:10.
1109/TKDE.
2009.
156]附中文参考文献:[12]徐鹏,林森.
基于C4.
5决策树的流量分类方法.
软件学报,2009,20(10):26922704.
http://www.
jos.
org.
cn/1000-9825/3444.
htm[doi:10.
3724/SP.
J.
1001.
2009.
03444][14]徐鹏,刘琼,林森.
基于支持向量机的Internet流量分类研究.
计算机研究与发展,2009,46(3):407414.
张宏莉(1973-),女,吉林榆树人,博士,教授,博士生导师,主要研究领域为网络信息安全,网络测量,并行处理.
鲁刚(1982-),男,博士生,主要研究领域为流量分类,P2P技术.