單 凱，高仲合，李鳳銀

SHAN Kai,GAO Zhonghe,LI Fengyin

曲阜師范大學 計算機科學學院，山東 日照276826

School of Computer Science College,Qufu Normal University,Rizhao,Shandong 276826,China

1 引言

在單機環(huán)境下使用樸素貝葉斯分類方法對P2P流量進行識別時會把數(shù)據(jù)集一次性讀入內(nèi)存[1]，顯然這已經(jīng)不再適合大規(guī)模的數(shù)據(jù)集，然而，使用大數(shù)據(jù)訓練出來的分類器會提高識別率[2]，這就使了單機環(huán)境下的流量識別受到了限制；樸素貝葉斯分類[3-4]使用的特征屬性傳統(tǒng)的做法是依據(jù)人為經(jīng)驗[5]進行選擇，使得特征屬性缺乏客觀性[6]，進一步降低了流量的識別率；當前大部分P2P 流量識別只能對非加密流量進行粗粒度的識別，缺乏實用性。

本文改進了云計算環(huán)境下的屬性約簡算法并提出了云計算環(huán)境下的樸素貝葉斯分類算法，使用改進后的屬性約簡算法獲取了約簡屬性集合，并將該集合應用到了樸素貝葉斯分類算法中，再使用大數(shù)據(jù)集P2P 流量對分類器進行訓練，最后，使用該分類器對流量進行識別。實驗表明，算法具有很好的加速比，對各類P2P 流量的識別率均達到了95%以上，也可以識別加密流量，并且結(jié)果具有客觀性。

2 Map/Reduce 云計算模型

Map/Reduce[7]是Google 提出的云計算模型，用戶無需考慮數(shù)據(jù)分塊、節(jié)點通信等問題，只需實現(xiàn)Map和Reduce函數(shù)[8]來完成計算。Map 函數(shù)接受鍵值對＜key,value＞作為參數(shù)生成鍵值對＜key,listofvalues＞集合，把該集合傳給Reduce 函數(shù)，Reduce 會按照key對數(shù)據(jù)進行規(guī)約操作，得出最后的結(jié)果＜key′,value′＞集合[9]。

Google 和Apache 都實現(xiàn) 了Map/Reduce 模型，本文使用Apache 的Hadoop[10]開源框架。Hadoop 框架中有一個master 節(jié)點和多個slave 組成，master 負責調(diào)度構(gòu)成一個作業(yè)的所有任務，這些任務分布在不同的slave上。master 對slave 監(jiān)控，slave 僅負 責執(zhí)行由master 指派的任務[11]。

3 改進的屬性約簡算法

粗糙集理論是在不破壞現(xiàn)有知識決策能力的條件下，對知識系統(tǒng)進行降噪排除冗余信息，使知識空間更簡練。

3.1 粗糙集相關(guān)概念

定義1[12]稱S=(U,A,V(a),f)為一個決策系統(tǒng)，其中U是非空集合，稱為論域；A為非空集合，稱為屬性集合，A=C∪D，C∩D=Φ，C為條件屬性集合，D為決策屬性集合；V(a) 為屬性a∈A的值域；f(x,a) 為U→V(a)的單一映射函數(shù)，使得x∈U對應的屬性a在值域V(a)中有唯一值。一般的S=(U,C∪2mweqmi)表示只有一個決策屬性的決策系統(tǒng)。

定義2[12]在決策系統(tǒng)S=(U,C∪4kgcys0)中，稱ind(A)={(x,y)∈2U|?a∈A,f(x,a)=f(y,a)}為S的一個等價關(guān)系，其中A?C∪guuwuok。用[X]A={x∈X,y∈X|?a∈A,f(x,a)=f(y,a)}表示由等價關(guān)系ind(A)劃分的等價類。

定義3[12]對于決策系統(tǒng)S=(U,C∪scoccsa)，若ind(A-{a})=ind(A)則稱屬性a為可去除的。當?a∈C′，a不可去除時，C′?C稱為C約簡，記作SRED(C)。

推廣到P2P 識別上來就是，P2P 流量的特征屬性C，與P2P 流量的類別0aki0ii，及其每條流對應的屬性值組成決策表S，通過約簡去除冗余特征屬性，得到最簡屬性集合。

3.2 DIS 屬性約簡算法

3.3 改進的DIS 屬性約簡算法

本文對DIS算法[13]進行了改進，設計了適合P2P流量特征屬性約簡的算法。由于采用P2P應用的類別作為決策屬性d，而對于相同數(shù)據(jù)集屬性d的辨別能力DISd是固定的；再次采用比較辨別能力大小的方法來選擇屬性，在比較時計算DISd會浪費一定時空復雜度，因此可以去掉DISd，改進后的公式為，顯然使用改進后的公式效率會有所提升。改進后的算法的思想是找到一個約簡的屬性集合SRED使其辨識能力與待約簡集合的辨別能力相同，即。

改進后的算法如下：

Map1、Reduce1、Map2、Reduce2 四個函數(shù)實現(xiàn)一個Job，通過這個Job 來計算屬性的辨別能力。

（1）Map1 函數(shù)（Object，Text），輸入：<文件名，類別各屬性值>，輸出：<屬性 屬性值，1>，功能是分割各屬性及其值為Reduce階段做準備。

（2）Reduce1 函數(shù)（Text，Intwritable），輸入：<屬性屬性值，1>，輸出<屬性 屬性值，總數(shù)>，功能是計算具有相同屬性屬性值對象個數(shù)。

（3）Map2 函數(shù)（Object，Text），輸入：<屬性 屬性值，總數(shù)>，輸出：<屬性，總數(shù)>，功能是去掉屬性值，為Reduce階段做準備。

（4）Reduce2 函數(shù)（Text，Intwritable），輸入：<屬性，總數(shù)>，輸出<屬性，DIS>，功能是計算屬性的DIS。

下面是四個函數(shù)的實例分析，Map1 和Reduce1 的算法實例如圖1 所示，然后由Map2 和Reduce2 函數(shù)計算得出：。

圖1 約簡算法實例分析

表1 樸素貝葉斯分類實例

4 云計算環(huán)境下的樸素貝葉斯分類算法

通過貝葉斯分類P2P 流量的思想：首先對數(shù)據(jù)集進行訓練獲得類別的初始概率和特征屬性在各屬性之下的概率，生成分類策略；然后在流進行識別時比較各特征屬性對于屬性值的極大后驗概率來確定分類。

4.1 樸素貝葉斯分類方法

4.2 云計算環(huán)境下的樸素貝葉斯分類算法

在云計算環(huán)境下的樸素貝葉斯分類算法包括訓練階段和分類階段，訓練階段用來訓練分類器，分類階段用來分類P2P 流量。

（1）訓練階段云計算算法NBT

訓練階段算法如下：

1.統(tǒng)計各類別的流條數(shù)計算P(h)；

2.調(diào)用MapReduce結(jié)果計算每Nh和nij；

3.根據(jù)改進的公式計算P(c|h)；

4.輸出P(c|h)和P(h)到文件。

①Map函數(shù)（Object，Text），輸入<文件名，類別 各屬性值>，輸出<決策屬性值 屬性 屬性值，1>，功能是分割決策屬性值、每個條件屬性及其值。

②Reducer 函數(shù)（Text，Iterable），輸入<決策屬性值 屬性 屬性值，1>，輸出<決策屬性值 屬性 屬性值，總數(shù)>，功能是計算具有相同決策屬性值、條件屬性及其屬性值的累加和。

（2）分類階段云計算算法NBC

分類階段的分類結(jié)果直接由Reduce函數(shù)輸出。

①Map 函數(shù)（Object，Text），輸入：<文件名，各屬性值> 輸出：<類別，1>，算法如下：

1.把訓練結(jié)果讀入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 函數(shù)（Text，Intwritable），輸入：<類別，1>輸出：<類別，流條數(shù) 字節(jié)數(shù)>，功能是計算每個類別的流條數(shù)。

5 實驗與結(jié)果分析

5.1 實驗環(huán)境

Hadoop 運行平臺是在學院實驗室按照表2 的云計算環(huán)境搭建16 臺PC，其中1 臺作為master，剩余15 臺作為slave。

表2 實驗環(huán)境

5.2 數(shù)據(jù)集

（1）采集數(shù)據(jù)集：實驗采用兩個數(shù)據(jù)集DS1、DS2，DS1 是在學院網(wǎng)絡實驗室按照表2 的抓包環(huán)境搭建10臺PC，在不同時段分別運行各P2P 應用、非P2P 應用，使用Wireshark 在網(wǎng)絡出口進行抓包，把各類別純凈的流量組合成DS1。DS2 為布雷西亞大學在該大學校園網(wǎng)出口采集到的網(wǎng)絡流量UNIB S 2009 數(shù)據(jù)集[14]，此數(shù)據(jù)集為P2P 流量分類領(lǐng)域公認的標準數(shù)據(jù)集。數(shù)據(jù)集流量結(jié)構(gòu)見表3。

表3 數(shù)據(jù)集流量結(jié)構(gòu)

（2）格式化數(shù)據(jù)集：把采集到格式為pcap 的數(shù)據(jù)集格式化為<序號、到達時間、五元組、包大小>的packet文件，解析此文件組裝成流文件，區(qū)間化每條流的以下特征：TCP/UDP、平均包大小、包大小方差、最大包大小、最小包大小、最大包位置、最小包位置、包大小中位數(shù)、包平均到達時間、包到達時間方差、包速率（個/s）、流大小、流持續(xù)時間、有有效載荷包數(shù)、無有效載荷包數(shù)、流包數(shù)。

將DS1 數(shù)據(jù)集分成相同的兩部分DS1_Train 和DS1_Test 用于訓練和測試，DS1_Train 加上類別作為決策屬性。

5.3 結(jié)果分析

5.3.1 DIS 算法的加速比

分別使用改進前后的DIS 算法對DS1_Train 和一半的DS1_Train 進行屬性約簡，加速比見圖2。實驗分析：

（1）改進的DIS 算法比DIS 有好的加速比，并且數(shù)據(jù)集越大效果越明顯，這是由于循環(huán)次數(shù)所致。

（2）數(shù)據(jù)集較小時，加速比在9 個節(jié)點就趨于穩(wěn)定，這是由于其中的一些節(jié)點未參與運算。

（3）加速比隨節(jié)點增加而減小，這是由于節(jié)點越多，因節(jié)點間通信、文件分割等造成的時延越大。

圖2 改進前后DIS 算法的加速比

改進的DIS 算法屬性約簡結(jié)果見表4。

表4 改進的DIS 算法約簡結(jié)果

分析表4 得出：

（1）包大小方差比平均包描述的性質(zhì)更精確，因此后一個被約簡。

（2）最大最小包大小可以被包大小中位數(shù)表示，所以被約簡。

（3）包平均到達時間和到達時間方差與第一種情況類似，也被約簡。

（4）包速率是由流包數(shù)和持續(xù)時間計算所得，所以包速率可以反映后兩個屬性，因此后兩個屬性被約簡。

（5）由于有效載荷的包與無有效載荷的包相反，因此會被約簡掉一個。

5.3.2 屬性約簡算法的效率分析

單機約簡方法選擇基于屬性核最小約簡算法[15]。從DS1_Train 中隨機抽取1 000 和5 000 條流組成DS1_Train1 和DS1_Train2 作為數(shù)據(jù)集，分別使用單機約簡方法和改進的DIS 算法進行約簡，運行時間見圖3，然后使用兩種約簡算法對整個DS1_Train 進行約簡。

圖3 屬性核最小約簡算法實驗結(jié)果

實驗分析：

（1）單機約簡方法具有良好的性能，改進的DIS 算法性能較差，這是因為框架本身要進行的初始化、節(jié)點通信、任務分配等操作會占據(jù)大部分時間，說明Hadoop不適合處理小數(shù)據(jù)集。

（2）當使用單機方法對DS1_Train 進行約簡時，由于數(shù)據(jù)集太大，會產(chǎn)生內(nèi)存溢出錯誤，無法完成約簡，見圖4，其中VPRS 類的main 方法為程序運行入口；而云環(huán)境下改進的DIS 算法可以有效完成約簡，5.3.1 小節(jié)的實驗可以證明。

5.3.3 樸素貝葉斯分類算法識別率和加速比

在5.3.1 小節(jié)和5.3.2 小節(jié)實驗得到了特征屬性以及對應的后驗概率。在此的基礎(chǔ)上，使用NBC 算法分別對對DS1_Test 的各個類別進行識別，實驗結(jié)果見表5。

圖4 屬性約簡算法效率分析

表5 NBC 算法識別率 %

算法的加速比見圖5，由圖可知NBT 和NBC 算法具有良好的加速比。

圖5 NBT 和NBC 算法的加速比

實驗分析：

（1）P2P 流之間會存在交互錯誤識別，這是由于各類P2P 流之間特征值有交叉造成的。

（2）BT、eMule、迅雷沒有誤識別為Skype 是因為Skype并非下載類型應用，其流字節(jié)數(shù)、包速率等特性與下載類型的應用差別較大。

（3）P2P 流中有極少部分被識別為非P2P 流是因為這些軟件中有一些Web 流，比如軟件中的廣告。

（4）非P2P 流被識別為P2P 流是由于FTP、DNS 等流量具有P2P 的某些特征，造成錯誤識別。

對于上述實驗，用全部特征屬性代替約簡后的屬性，然后重新運行，程序運行幾乎時間延長1 倍，而識別率并沒有太大改變，說明使用約簡后的屬性集合在不影響識別率的前提下效率更高。

5.3.4 識別標準數(shù)據(jù)集

對DS2 數(shù)據(jù)集采用改進的樸素貝葉斯分類算法的分類階段MapReduce 進行識別，各類型P2P 流量識別率達到了95%以上，實驗結(jié)果見表6。

表6 DS2 數(shù)據(jù)集識別結(jié)果 %

實驗分析如下所示。

（1）有少量BT、eMule、Skype 流未被識別，這是由于：一是P2P 節(jié)點為了檢索其他節(jié)點會與服務器交互信息，這些連接于類似于正常的Web 連接；二是P2P 節(jié)點之間創(chuàng)建連接時也會產(chǎn)生一些失敗連接，這些連接不符合P2P 特征。因此，這兩種流未能被識別。

（2）識別出了少量本不存在的迅雷和PPLive 流量。通過分析這些錯誤流發(fā)現(xiàn)主要是一些數(shù)據(jù)包較小的BT 和eMule 流，由于這些流特征與迅雷和PPLive 的流特征極為相似，因此被錯誤識別。

（3）有少量非P2P 流量為被識別。通過分析發(fā)現(xiàn)在識別的P2P 流量中有一些端口為80 和21 的流，這些流字節(jié)數(shù)較大，可能是一些Http 下載和FTP 流，這些流特征與P2P 流特征相似，因此被錯誤識別。

6 結(jié)束語

本文首次在云計算環(huán)境下使用改進的樸素貝葉斯分類算法對加密的大數(shù)據(jù)集P2P 流量進行了細粒度識別，具有很高的識別率；由于識別時使用的是云計算環(huán)境下改進的屬性約簡算法生成的特征屬性，使得識別結(jié)果具有客觀性，并且提升了識別率；由于兩種算法都只對包頭進行處理并未涉及負載，因此，可以識別加密流量和新的P2P 應用。

提出的兩種算法都是對離線數(shù)據(jù)集進行處理，并沒有實現(xiàn)對P2P 流量的實時識別，但是，可以對NBC 算法進行改進來實現(xiàn)實時識別，這一部分內(nèi)容可以作為下一個研究目標。

[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網(wǎng)絡安全管理機制[J].計算機科學，2012，39（9）：28-32.

[5] 王中鋒，王志海.基于條件對數(shù)似然函數(shù)導數(shù)的貝葉斯網(wǎng)絡分類器優(yōu)化算法[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] 李偉衛(wèi)，趙航，張陽.基于MapReduce 的海量數(shù)據(jù)挖掘技術(shù)研究[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 平臺的海量數(shù)據(jù)并行隨機抽樣[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] 錢進.云計算環(huán)境下知識約簡算法[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] 陳昊，楊俊安，莊鎮(zhèn)泉.變精度粗糙集的屬性核和最小屬性約簡算法[J].計算機學報，2012，35（5）：1011-1017.