单 凯,高仲合,李凤银
SHAN Kai,GAO Zhonghe,LI Fengyin
曲阜师范大学 计算机科学学院,山东 日照276826
School of Computer Science College,Qufu Normal University,Rizhao,Shandong 276826,China
在单机环境下使用朴素贝叶斯分类方法对P2P流量进行识别时会把数据集一次性读入内存[1],显然这已经不再适合大规模的数据集,然而,使用大数据训练出来的分类器会提高识别率[2],这就使了单机环境下的流量识别受到了限制;朴素贝叶斯分类[3-4]使用的特征属性传统的做法是依据人为经验[5]进行选择,使得特征属性缺乏客观性[6],进一步降低了流量的识别率;当前大部分P2P 流量识别只能对非加密流量进行粗粒度的识别,缺乏实用性。
本文改进了云计算环境下的属性约简算法并提出了云计算环境下的朴素贝叶斯分类算法,使用改进后的属性约简算法获取了约简属性集合,并将该集合应用到了朴素贝叶斯分类算法中,再使用大数据集P2P 流量对分类器进行训练,最后,使用该分类器对流量进行识别。实验表明,算法具有很好的加速比,对各类P2P 流量的识别率均达到了95%以上,也可以识别加密流量,并且结果具有客观性。
Map/Reduce[7]是Google 提出的云计算模型,用户无需考虑数据分块、节点通信等问题,只需实现Map和Reduce函数[8]来完成计算。Map 函数接受键值对<key,value>作为参数生成键值对<key,listofvalues>集合,把该集合传给Reduce 函数,Reduce 会按照key对数据进行规约操作,得出最后的结果<key′,value′>集合[9]。
Google 和Apache 都实现 了Map/Reduce 模型,本文使用Apache 的Hadoop[10]开源框架。Hadoop 框架中有一个master 节点和多个slave 组成,master 负责调度构成一个作业的所有任务,这些任务分布在不同的slave上。master 对slave 监控,slave 仅负 责执行由master 指派的任务[11]。
粗糙集理论是在不破坏现有知识决策能力的条件下,对知识系统进行降噪排除冗余信息,使知识空间更简练。
定义1[12]称S=(U,A,V(a),f)为一个决策系统,其中U是非空集合,称为论域;A为非空集合,称为属性集合,A=C∪D,C∩D=Φ,C为条件属性集合,D为决策属性集合;V(a) 为属性a∈A的值域;f(x,a) 为U→V(a)的单一映射函数,使得x∈U对应的属性a在值域V(a)中有唯一值。一般的S=(U,C∪{d})表示只有一个决策属性的决策系统。
定义2[12]在决策系统S=(U,C∪{d})中,称ind(A)={(x,y)∈2U|∃a∈A,f(x,a)=f(y,a)}为S的一个等价关系,其中A⊆C∪{d}。用[X]A={x∈X,y∈X|∃a∈A,f(x,a)=f(y,a)}表示由等价关系ind(A)划分的等价类。
定义3[12]对于决策系统S=(U,C∪{d}),若ind(A-{a})=ind(A)则称属性a为可去除的。当∀a∈C′,a不可去除时,C′⊆C称为C约简,记作SRED(C)。
推广到P2P 识别上来就是,P2P 流量的特征属性C,与P2P 流量的类别{d},及其每条流对应的属性值组成决策表S,通过约简去除冗余特征属性,得到最简属性集合。
本文对DIS算法[13]进行了改进,设计了适合P2P流量特征属性约简的算法。由于采用P2P应用的类别作为决策属性d,而对于相同数据集属性d的辨别能力DISd是固定的;再次采用比较辨别能力大小的方法来选择属性,在比较时计算DISd会浪费一定时空复杂度,因此可以去掉DISd,改进后的公式为,显然使用改进后的公式效率会有所提升。改进后的算法的思想是找到一个约简的属性集合SRED使其辨识能力与待约简集合的辨别能力相同,即。
改进后的算法如下:
Map1、Reduce1、Map2、Reduce2 四个函数实现一个Job,通过这个Job 来计算属性的辨别能力。
(1)Map1 函数(Object,Text),输入:<文件名,类别各属性值>,输出:<属性 属性值,1>,功能是分割各属性及其值为Reduce阶段做准备。
(2)Reduce1 函数(Text,Intwritable),输入:<属性属性值,1>,输出<属性 属性值,总数>,功能是计算具有相同属性属性值对象个数。
(3)Map2 函数(Object,Text),输入:<属性 属性值,总数>,输出:<属性,总数>,功能是去掉属性值,为Reduce阶段做准备。
(4)Reduce2 函数(Text,Intwritable),输入:<属性,总数>,输出<属性,DIS>,功能是计算属性的DIS。
下面是四个函数的实例分析,Map1 和Reduce1 的算法实例如图1 所示,然后由Map2 和Reduce2 函数计算得出:。
图1 约简算法实例分析
表1 朴素贝叶斯分类实例
通过贝叶斯分类P2P 流量的思想:首先对数据集进行训练获得类别的初始概率和特征属性在各属性之下的概率,生成分类策略;然后在流进行识别时比较各特征属性对于属性值的极大后验概率来确定分类。
在云计算环境下的朴素贝叶斯分类算法包括训练阶段和分类阶段,训练阶段用来训练分类器,分类阶段用来分类P2P 流量。
(1)训练阶段云计算算法NBT
训练阶段算法如下:
1.统计各类别的流条数计算P(h);
2.调用MapReduce结果计算每Nh和nij;
3.根据改进的公式计算P(c|h);
4.输出P(c|h)和P(h)到文件。
①Map函数(Object,Text),输入<文件名,类别 各属性值>,输出<决策属性值 属性 属性值,1>,功能是分割决策属性值、每个条件属性及其值。
②Reducer 函数(Text,Iterable
(2)分类阶段云计算算法NBC
分类阶段的分类结果直接由Reduce函数输出。
①Map 函数(Object,Text),输入:<文件名,各属性值> 输出:<类别,1>,算法如下:
1.把训练结果读入hashMap<属性 属性值 决策属性,P(C|h)>,把P(h)读入List;
2.把每一个流的各属性及属性值组成的字符串做为hash-Map 的key,从中取出对应的P(C|h)及其类别,得到P(C|h);
3.输出类别D=max(P(C|h)×P(h))。
②Reduce 函数(Text,Intwritable),输入:<类别,1>输出:<类别,流条数 字节数>,功能是计算每个类别的流条数。
Hadoop 运行平台是在学院实验室按照表2 的云计算环境搭建16 台PC,其中1 台作为master,剩余15 台作为slave。
表2 实验环境
(1)采集数据集:实验采用两个数据集DS1、DS2,DS1 是在学院网络实验室按照表2 的抓包环境搭建10台PC,在不同时段分别运行各P2P 应用、非P2P 应用,使用Wireshark 在网络出口进行抓包,把各类别纯净的流量组合成DS1。DS2 为布雷西亚大学在该大学校园网出口采集到的网络流量UNIB S 2009 数据集[14],此数据集为P2P 流量分类领域公认的标准数据集。数据集流量结构见表3。
表3 数据集流量结构
(2)格式化数据集:把采集到格式为pcap 的数据集格式化为<序号、到达时间、五元组、包大小>的packet文件,解析此文件组装成流文件,区间化每条流的以下特征:TCP/UDP、平均包大小、包大小方差、最大包大小、最小包大小、最大包位置、最小包位置、包大小中位数、包平均到达时间、包到达时间方差、包速率(个/s)、流大小、流持续时间、有有效载荷包数、无有效载荷包数、流包数。
将DS1 数据集分成相同的两部分DS1_Train 和DS1_Test 用于训练和测试,DS1_Train 加上类别作为决策属性。
5.3.1 DIS 算法的加速比
分别使用改进前后的DIS 算法对DS1_Train 和一半的DS1_Train 进行属性约简,加速比见图2。实验分析:
(1)改进的DIS 算法比DIS 有好的加速比,并且数据集越大效果越明显,这是由于循环次数所致。
(2)数据集较小时,加速比在9 个节点就趋于稳定,这是由于其中的一些节点未参与运算。
(3)加速比随节点增加而减小,这是由于节点越多,因节点间通信、文件分割等造成的时延越大。
图2 改进前后DIS 算法的加速比
改进的DIS 算法属性约简结果见表4。
表4 改进的DIS 算法约简结果
分析表4 得出:
(1)包大小方差比平均包描述的性质更精确,因此后一个被约简。
(2)最大最小包大小可以被包大小中位数表示,所以被约简。
(3)包平均到达时间和到达时间方差与第一种情况类似,也被约简。
(4)包速率是由流包数和持续时间计算所得,所以包速率可以反映后两个属性,因此后两个属性被约简。
(5)由于有效载荷的包与无有效载荷的包相反,因此会被约简掉一个。
5.3.2 属性约简算法的效率分析
单机约简方法选择基于属性核最小约简算法[15]。从DS1_Train 中随机抽取1 000 和5 000 条流组成DS1_Train1 和DS1_Train2 作为数据集,分别使用单机约简方法和改进的DIS 算法进行约简,运行时间见图3,然后使用两种约简算法对整个DS1_Train 进行约简。
图3 属性核最小约简算法实验结果
实验分析:
(1)单机约简方法具有良好的性能,改进的DIS 算法性能较差,这是因为框架本身要进行的初始化、节点通信、任务分配等操作会占据大部分时间,说明Hadoop不适合处理小数据集。
(2)当使用单机方法对DS1_Train 进行约简时,由于数据集太大,会产生内存溢出错误,无法完成约简,见图4,其中VPRS 类的main 方法为程序运行入口;而云环境下改进的DIS 算法可以有效完成约简,5.3.1 小节的实验可以证明。
5.3.3 朴素贝叶斯分类算法识别率和加速比
在5.3.1 小节和5.3.2 小节实验得到了特征属性以及对应的后验概率。在此的基础上,使用NBC 算法分别对对DS1_Test 的各个类别进行识别,实验结果见表5。
图4 属性约简算法效率分析
表5 NBC 算法识别率 %
算法的加速比见图5,由图可知NBT 和NBC 算法具有良好的加速比。
图5 NBT 和NBC 算法的加速比
实验分析:
(1)P2P 流之间会存在交互错误识别,这是由于各类P2P 流之间特征值有交叉造成的。
(2)BT、eMule、迅雷没有误识别为Skype 是因为Skype并非下载类型应用,其流字节数、包速率等特性与下载类型的应用差别较大。
(3)P2P 流中有极少部分被识别为非P2P 流是因为这些软件中有一些Web 流,比如软件中的广告。
(4)非P2P 流被识别为P2P 流是由于FTP、DNS 等流量具有P2P 的某些特征,造成错误识别。
对于上述实验,用全部特征属性代替约简后的属性,然后重新运行,程序运行几乎时间延长1 倍,而识别率并没有太大改变,说明使用约简后的属性集合在不影响识别率的前提下效率更高。
5.3.4 识别标准数据集
对DS2 数据集采用改进的朴素贝叶斯分类算法的分类阶段MapReduce 进行识别,各类型P2P 流量识别率达到了95%以上,实验结果见表6。
表6 DS2 数据集识别结果 %
实验分析如下所示。
(1)有少量BT、eMule、Skype 流未被识别,这是由于:一是P2P 节点为了检索其他节点会与服务器交互信息,这些连接于类似于正常的Web 连接;二是P2P 节点之间创建连接时也会产生一些失败连接,这些连接不符合P2P 特征。因此,这两种流未能被识别。
(2)识别出了少量本不存在的迅雷和PPLive 流量。通过分析这些错误流发现主要是一些数据包较小的BT 和eMule 流,由于这些流特征与迅雷和PPLive 的流特征极为相似,因此被错误识别。
(3)有少量非P2P 流量为被识别。通过分析发现在识别的P2P 流量中有一些端口为80 和21 的流,这些流字节数较大,可能是一些Http 下载和FTP 流,这些流特征与P2P 流特征相似,因此被错误识别。
本文首次在云计算环境下使用改进的朴素贝叶斯分类算法对加密的大数据集P2P 流量进行了细粒度识别,具有很高的识别率;由于识别时使用的是云计算环境下改进的属性约简算法生成的特征属性,使得识别结果具有客观性,并且提升了识别率;由于两种算法都只对包头进行处理并未涉及负载,因此,可以识别加密流量和新的P2P 应用。
提出的两种算法都是对离线数据集进行处理,并没有实现对P2P 流量的实时识别,但是,可以对NBC 算法进行改进来实现实时识别,这一部分内容可以作为下一个研究目标。
[1] 鲁刚,张宏莉,叶麟.P2P流量识别[J].软件学报,2011,22(6):1281-1298.
[2] Soysal M,Schmidt E G.Machine learning algorithms for accurate flow-based network traffic classification:Evaluation and comparison[J].Performance Evaluation,2010,67(6):451-467.
[3] Chu C T,Kim S K,Lin Y A,et al.Map-reduce for machine learning on multicore[J].Advances in Neural Information Processing Systems,2007,19:281-288.
[4] 王海晟,王海晨,桂小林.使用粗糙集与Bayes分类器的P2P网络安全管理机制[J].计算机科学,2012,39(9):28-32.
[5] 王中锋,王志海.基于条件对数似然函数导数的贝叶斯网络分类器优化算法[J].计算机学报,2012,35(2):364-373.
[6] Han J,Kamber M,Pei J.Data mining:Concepts and techniques[M].New York:Morgan Kaufmann,2011.
[7] 李伟卫,赵航,张阳.基于MapReduce 的海量数据挖掘技术研究[J].计算机工程与应用,2013,49(20):112-117.
[8] Dean J,Ghemawat S.MapReduce:Simplified data processing on large clusters[J].Communications of the ACM,2008,51(1):107-113.
[9] Yin J,Liao Y,Baldi M,et al.Efficient analytics on ordered datasets using MapReduce[C]//Proceedings of the 22nd International Symposium on High-Performance Parallel and Distributed Computing.New York:ACM,2013:125-126.
[10] White T.Hadoop:the definitive guide[M].USA:O’Reilly,2012.
[11] 宛婉,周国祥.Hadoop 平台的海量数据并行随机抽样[J].计算机工程与应用,2014,50(20):115-118.
[12] Pawlak Z.Rough sets:Theoretical aspect of reasoning about data[M].[S.l.]:Kluwer Academic Publishers,1991.
[13] 钱进.云计算环境下知识约简算法[J].计算机学报,2011,34(12):2332-2343.
[14] Gringoli F,Salgarelli L,Dusi M,et al.Gt:picking up the truth from the ground for internet traffic[J].ACM SIGCOMM Computer Communication Review,2009,39(5):12-18.
[15] 陈昊,杨俊安,庄镇泉.变精度粗糙集的属性核和最小属性约简算法[J].计算机学报,2012,35(5):1011-1017.