程 光 錢德鑫 郭建偉 史海濱 吳 樺 趙玉宇
1(東南大學網絡空間安全學院 南京 211189)
2(教育部計算機網絡和信息集成重點實驗室(東南大學) 南京 211189)
3(江蘇省計算機網絡技術重點實驗室(東南大學) 南京 211189)
4(華為技術有限公司西安研究所 西安 710075)
隨著互聯網的飛速發展,網絡新應用、新協議層出不窮,網絡應用程序越來越復雜;同時網絡中的加密流量比例隨著人們對于隱私的重視而不斷擴大.這些問題使得傳統的流量分類方法面臨巨大的挑戰,逐漸從基于端口和深度包檢測技術(deep packet inspection, DPI)[1]的流量分類方法轉向基于機器學習[2-3]的流量分類方法.基于機器學習的流量分類比較依賴于訓練樣本的環境.由于網絡流量具有高度動態變化性、突發性、不可逆性等特點,因此流量的統計特征和分布會發生動態變化,導致基于流特征的機器學習方法產生概念漂移問題[4-5].網絡流量概念漂移問題使得建立在原始數據集上的分類模型在新樣本上適用性變差,造成分類器分類精度下降.
針對概念漂移問題國內外學者進行了大量的研究,并取得眾多成果.然而這些方法還存在一些不足:1)當前大多數解決概念漂移的方法都是基于分類錯誤率[6]來檢測概念漂移,帶來的問題是獲取樣本標簽需要耗費大量時間和資源,同時基于分類錯誤率的檢測方法無法應對類不平衡[7]的網絡流.2)當檢測到概念漂移時,若只在新流量上訓練分類器會導致歷史知識的丟失[8],若將不同時期獲得的所有流量重新訓練分類器則會帶來較大的性能問題[9].一個理想的網絡流分類模型應該能增量地學習并適應多種網絡流量類型的變化,因此設計出能應對概念漂移的網絡流量分類方法具有重要的意義.
針對上述問題,本文提出了一種基于散度的網絡流概念漂移分類方法(ensemble classification based on divergence detection, ECDD).該方法首先采用雙層窗口機制跟蹤概念漂移,借鑒信息論的思想,通過JS散度來度量新舊窗口之間數據分布的差異,從而有效地檢測概念漂移.本文采用增量集成學習的方法,當檢測到概念漂移時采用新樣本重新訓練分類器,接著通過分類器權值比較的方式保留性能較好的分類器,從而實現對于集成分類模型的有效更新.
近年來,許多學者對于概念漂移問題提出了大量的算法與模型,目前概念漂移檢測方法大體上分為2類:1)依據概念漂移造成的后果進行檢測,例如依據分類準確率下降來檢測概念漂移;2)依據概念漂移產生的原因進行檢測,例如依據數據分布是否發生變化來檢測概念漂移.
對于使用分類錯誤率來檢測概念漂移,相關研究為:Gama等人[10]提出根據當前分類器的分類錯誤率來檢測概念漂移的DDM算法,該方法持續監測分類器的分類錯誤率,對于突變式的概念漂移表現優越,但不能有效地檢測到漸變式的概念漂移;Nishida等人[11]提出了基于伯努利分布檢測概念漂移的算法EDDM,該方法同時依據模型的錯誤率變化與錯誤率之間的距離判斷概念漂移,不僅對突變性的概念漂移檢測良好,同時也提高了對漸變概念漂移的檢測效果;Bifet等人[12]提出了自適應滑動窗口算法ADWIN,該算法用可變的滑動窗口來檢測隨時間變化的數據流,通過比較不同子窗口之間的分類錯誤率均值差異來判斷是否發生概念漂移;Nishida等人[13]提出一種突變式概念漂移檢測方法LID,依據當前模型的信息度和分類精度來檢測概念漂移.
上述方法均基于分類準確率檢測概念漂移,標記樣本需要耗費大量時間和資源,因此很多學者基于概念漂移產生的原因,即數據分布的變化,取得了相應的研究成果:Borchani等人[14]基于半監督學習的方法提出基于距離的漂移檢測,該方法使用滑動窗口將數據流劃分為不同的子集,基于KL散度(Kullback-Leibler divergence,KLD)計算差異性來檢測概念漂移,該方法使用的KL散度取值范圍較大,并存在距離不對稱等問題;Alippi等人[15]利用中心極限定理,設計了不依賴數據分布模型、不需要任何先驗信息的概念漂移檢測算法;Dries等人[16]基于統計學方法,使用對不同概念漂移類型設定不同閾值來檢測漂移,克服了單一標準檢測概念漂移的弊端,提高了對不同類型概念漂移的檢測準確率;潘吳斌等人[17]基于概念漂移發生時屬性信息熵會發生變化來檢測概念漂移,該方法對于不同類型的概念漂移均可以有效檢測并更新分類器,使得分類器具有良好的泛化性能.
由于網絡流量的動態性,例如不同時間、地點、網絡應用更新、新型網絡應用出現等情況,使得網絡業務分布發生變化,即會產生概念漂移問題,概念漂移使得分類模型的分類準確性下降,影響分類器的泛化性能.
將網絡流量統計特征表示為A=(a1,a2,…,an),用B來表示網絡流量所屬類別,根據貝葉斯公式可得,分類器可以定義為期望函數f:A→B:

(1)
由式(1)可得,流統計特征ai的變化會影響類條件概率密度P(ai/b),從而影響到P(b/A);同時類別先驗概率P(b)的變化也會影響到P(b/A),從而影響分類結果.
本文提出了一種基于散度的概念漂移流量分類方法ECDD,該方法基于雙層窗口檢測機制,依據特征屬性的JS散度差異來判斷數據分布的變化,從而檢測概念漂移;檢測到概念漂移時需要更新分類器,本文采用增量集成學習的方式引入漂移流量更新分類器,在保留之前分類器的基礎上剔除性能下降的分類器,從而使得分類器得到有效地更新,有效地應對網絡流量概念漂移問題.
本節將首先介紹基于散度的網絡流概念漂移檢測算法,然后描述在概念漂移點采用增量集成學習的方式更新分類器的方法.
概念漂移問題使得分類模型對新流量的適用性變差,難以保持穩定的識別準確性.僅依靠經驗定期更新分類器會浪費大量的時間和人力,及時準確地檢測到概念漂移,從而對分類器進行更新至關重要.基于分類錯誤率的概念漂移檢測算法需要獲得檢測樣本的真實標簽,浪費大量人力資源,同時不能很好地適用于類不平衡的網絡流.
本文提出了一種基于JS散度的概念漂移檢測算法ECDD.在信息論中,相對熵(relative entropy)又稱為KL散度,是衡量2個概率分布之間的差異性的指標,假設用X表示某隨機變量,該隨機變量上的2個概率分布為P(x)和Q(x),則它們的KLD(P‖Q)定義為
(2)
可以得出,KLD的取值范圍為[0,+∞],當2個隨機分布相同時,它們的相對熵為0,當2個隨機分布的差別增大時,它們的相對熵也會增大.由于KLD取值范圍為[0,+∞],對于2組隨機分布數據,無法準確地用KLD來度量2組數據分布的差異,對相似度的判別較為粗略.
盡管KLD從直觀上是一個度量或距離函數,但它并不是一個真正的度量或距離,因為它不具有對稱性,即:
KLD(P‖Q)≠KLD(Q‖P),
(3)
KLD的非對稱性對求解2組數據分布是否相似存在一定偏差.
JS散度是KL散度的一種變形,它解決了KL散度的不對稱問題,對相似度的判別更確切,對于2個概率分布P(x)和Q(x),JSD(P‖Q)的計算公式為

(4)
由式(4)可得JSD是2個KLD的累加,將式(4)中KLD展開得:

(5)
JSD的取值范圍為[0,1],即對于2組隨機分布變量,分布相同則是0,分布完全不同則為1.相較于KLD,JSD對相似性度量的判別更加確切.同時,JSD解決了KLD的非對稱問題,即JSD滿足對稱性:
JSD(P‖Q)=JSD(Q‖P),
(6)
JSD的對稱性使得在計算2組數據分布間差異時不會產生偏差.
基于JS散度的取值范圍更準確以及其滿足對稱性,本文引入JS散度來度量特征分布的變化,從而檢測概念漂移.
本文采用雙層滑動窗口的方式,在概念漂移檢測流程中一直維護2個滑動窗口,分別表示較舊概念的數據和新概念的數據.考慮到由于類不平衡會使得特征分布發生變化,從而對概念漂移檢測結果產生影響,本文先對2個窗口內樣本進行分類,依據分類結果計算2個窗口中樣本特征分布之間的JS散度,根據JS散度判斷概率分布是否發生變化,從而檢測是否發生了概念漂移.
定義時刻ti,用Winold,i表示最近一次檢測到概念漂移時的窗口,Winnew,i代表當前檢測窗口,包含最新的樣本實例.用JSD(Winold,i‖Winnew,i)表示2個窗口內數據分布的距離,定義漂移檢測閾值τ,若存在某特征對應的2組數據分布的JSD(Winold,i‖Winnew,i)>τ,則判斷發生概念漂移,稱ti為概念漂移點.當新樣本加入時,窗口Winnew,i向前滑動,每次更新,檢測是否存在JSD(Winold,i‖Winnew,i)>τ,如果是,報告發生概念漂移,重復整個過程.算法1描述了概念漂移檢測算法的流程:行①~⑦使用分類器對滑動窗口內樣本進行分類,獲得樣本特征向量和分類結果;行⑧到結尾計算2個窗口內每類樣本對應特征的JS散度,與漂移檢測閾值τ比較,若大于閾值,則判斷發生概念漂移,否則窗口向前滑動,重復整個流程直到數據流結尾.
算法1.概念漂移檢測算法.
輸入:分類器C、滑動窗口大小δ、特征向量Rd、漂移檢測閾值τ;
輸出:概念漂移檢測結果.
①Winold,i表示在時刻ti的δ個樣本;
②Winnew,i表示在Winold,i后的δ個樣本;
③ 當滑動窗口未到達數據流尾部時
④ 用C對Winold,i,Winnew,i樣本分類;
⑤Sold,i表示Winold,i的分類結果;
⑥Snew,i表示Winnew,i的分類結果;
⑦ 計算共有的類別yintersection,i;
⑧ 遍歷yintersection,i
⑨ 遍歷特征向量Rd
⑩ 若存在2組樣本的JS散度大于τ
本文借鑒集成學習里bagging[18]的思想構建集成學習初始分類器:假設集成分類器要構建k個基分類器,給定包含m個樣本的原始訓練樣本集,通過k次隨機采樣,得到k個大小均為m的采樣集S1,S2,…,Sk,對于這k個采樣集,訓練出k個基分類器,使用集成策略將這k個基分類器結合起來,形成最終的集成分類器.
借鑒自助采樣法(bootstrap sampling)[19]來進行隨機采樣:給定包含m個樣本的數據集,有放回地進行m次樣本的隨機抽取,經過m次隨機采樣操作,將得到含m個樣本的采樣集,初始訓練集中有的樣本在采樣集里多次出現,有的則從未出現.重復上述操作k次,這樣可以得到k個相互獨立的樣本集,從而使得集成中的個體學習器盡可能相互獨立,獲得泛化性能強的集成.
選取C4.5決策樹作為集成學習的基分類器,C4.5決策樹的分類模型易于理解,且具有較好的分類效果和效率[20-21].同時,C4.5決策樹在模型構建過程中不依賴于網絡流分布,具有較好的分類穩定性.
考慮到基分類器性能不同對于其分類結果應持有不同的信心,因此本文根據基分類器的分類性能賦予其權重.用Ci(1≤i≤k)表示基分類器,Wi(1≤i≤k)表示分類器Ci的權重,權重Wi與分類器Ci在其訓練集Si上的分類準確率成正比,定義Acci為基分類器Ci在其訓練集Si上的分類準確率,則該分類器對應的權重Wi計算為
Wi=α×Acci,
(7)
其中,α>0為正相關系數.算法2描述了集成學習分類器的構造方法.行①~⑧描述了初始集成分類器構造的整體流程,行②~④為獲取每個基分類器的訓練樣本集并訓練基分類器,行⑤~⑦為計算基分類器權重并將基分類器加入到集成分類器C中.
算法2.集成學習初始分類器構造算法.
輸入:基分類器數目k、初始訓練樣本集S;
輸出:k個帶權重的基分類器集合C.
① 遍歷基分類器集合
② 從S中隨機采樣得到訓練集Si;
③ 根據Si訓練基分類器Ci;
④ 計算Ci的分類準確率Acci;
⑤ 根據Acci計算Ci的權重Wi;
⑥ 將Ci加入到集成學習分類器中;
⑦ 完成加權集成分類器的構建;
⑧ 返回加權集成分類器.

Fig. 1 Capturing traffic at different locations圖1 不同地點采集流量

(8)
本文采用增量集成學習的方法來進行分類器的更新,從而在檢測到概念漂移時有效地更新分類器.檢測到概念漂移時,對于新樣本重新訓練出新的分類器,在保留原先集成分類器的基礎上,通過權值比較選取性能最優的分類器,從而提高集成分類器的泛化能力.
定義Snew為檢測到的概念漂移樣本集合,在Snew上學習出一個新的分類器Cnew,分類器Cnew的權重Wnew采用與式(7)相同的方法獲得.對于每個基分類器Ci(1≤i≤k),根據其在Snew上的分類準確率更新各自的權重.對于Cnew和基分類器Ci(1≤i≤k),按照分類器權重排序選取前k個分類器構成新的集成分類器.算法3描述了增量集成學習算法流程.
算法3.增量集成學習算法.
輸入:k個預先訓練的基分類器集合C、概念漂移樣本集S;
輸出:更新權重的k個基分類器集合C.
① 在S上訓練出新的分類器Cnew;
② 計算Cnew的權重Wnew;
③ 遍歷預先的基分類器集合C
④ 計算基分類器Ci的分類準確率Acci;
⑤ 根據分類準確率計算各自的權重Wi;
⑥ 根據權重排序選取前k個分類器;
⑦ 返回更新后的加權集成分類器.
網絡應用層出不窮,相同網絡業務下的不同應用可能會存在特征方面的差異,即產生概念漂移問題,這對網絡業務識別帶來極大的挑戰,造成網絡業務識別準確率下降.
本文對常見的8種網絡業務:視頻(video)、音頻(music)、網頁瀏覽(Web)、發送接收圖片語音(picture&voice)、上傳下載大文件(file)、文本聊天(chat)、視頻通話(video call over IP)、語音通話(voice call over IP)進行流量抓取,每種網絡業務根據該業務下應用的下載量,選擇3種不同的應用分別進行流量采集.
考慮到終端抓取的流量可能無法完全反映網絡的真實情況,本文使用tcpdump在VPN服務器上進行流量的抓取,抓取到的流量更遠離終端,也更能實際反映出業務過程中的網絡情況.
同時,考慮到CDN對流量特征的影響,采集流量時通過部署不同地點的服務器共同采集,從而盡可能地使采集到每種應用的流量能較真實地反應該應用整體的流量特征.
樣本采集示意圖如圖1所示,分別選取不同服務器地址進行流量采集,從而使采集到的樣本較好地反映該類網絡應用的特征情況.
樣本集具體構成情況如表1所示,對于每類網絡業務,各進行300次獨立撥測,根據組流后的結果構造出300條網絡流量樣本.其中每類網絡業務由3種網絡應用組成,每種網絡應用各獨立撥測100次,從而對于每類網絡應用均獲得互相獨立的100條網絡流量樣本.

Table 1 Experimental Data Set Composition表1 實驗數據集組成情況
本文實驗平臺為Windows 10,CPU為酷睿i5,內存為12 GB,開發環境為python 3.0.
對于如表1所示數據經過組流、流統計特征處理后,每條樣本均提取出81維特征.為了提高分類模型的分類性能和簡化分類模型,需要進行特征選擇,刪除冗余、無效的特征.例如實際接收到的字節數等特征針對某些網絡業務可能區分性不足,而平均碼率、平均包大小等對不同的網絡業務可能區分較明顯.
本文結合常見的特征選擇方法,充分考慮特征間的相關性、信息增益、信息增益率,綜合各特征選擇算法(InfoGain,GainRatio等)選取最優特征,最終選擇出了11維特征,如表2所示:

Table 2 Feature Selection Result表2 特征選擇結果
本文采用基于散度的方法解決流量識別中的概念漂移問題,在使用機器學習算法進行流量識別的過程中,準確率是算法性能評估常用的指標,真正例TP表示將正類正確預測為正類數,假正例FP表示將負類錯誤預測為正類數,假負例FN表示將正類錯誤預測為負類數,真負例TN表示將負類正確預測為負類數.根據這4個指標,可以得到準確率(Accuracy)、精確率(Precision)、召回率(Recall)和綜合評價(F1_score)的計算方法:

(9)

(10)

(11)

(12)
同時,為了評估概念漂移檢測方法的準確性及有效性,本文采用誤報率(FPR)和漏報率(FNR)來評估.誤報率和漏報率越高,表示概念漂移檢測性能越差,誤報率、漏報率分別計算為

(13)

(14)
3.4.1 概念漂移樣本集構造
對于網絡業務識別,由于同類網絡業務下可能會包含不同的網絡應用,各應用間可能會存在特征分布上的差異,從而使得該業務產生概念漂移問題,導致對于網絡業務的識別準確率下降.
對表1所示的網絡流量進行特征分析,尋找同類業務不同應用之間是否存在特征分布的差異.如圖2所示為視頻業務中,愛奇藝視頻IQIYI與騰訊視頻QQLive在平均速率特征上的分布直方圖.

Fig. 2 Video app distribution differences in flow_rate圖2 視頻應用在平均速率上的分布差異
由圖2可以看出愛奇藝視頻與騰訊視頻在平均速率這一特征上的分布差異.基于此方法,尋找表1所示網絡業務不同應用間存在的特征分布差異,根據應用間特征的差異構造概念漂移數據集,表3所示為構造出的5種概念漂移數據集.

Table 3 Concept Drift Data Set表3 概念漂移數據集構成
如表3所示,通過更換某類網絡業務下的應用構造出不同的概念漂移數據集,為了模擬真實網絡環境中樣本的情況,上述每個概念中的樣本均隨機打亂.
3.4.2 基于散度的概念漂移檢測結果
本文依據2個窗口內數據的分類結果,使用JS散度度量特征間數據分布的差異,從而檢測概念漂移.為了驗證基于JS散度的概念漂移檢測算法的有效性,本文做了2組對比實驗.
以Concept_1樣本集為例,將Concept_1樣本集劃分為大小相同的2個樣本集,分別為Concept_1_a與Concept_1_b,2個樣本集來自于同一個概念,依據分類結果對每個特征計算JS散度,結果如圖3所示:

Fig. 3 JS divergence results for the same concept data set圖3 相同概念數據集的JS散度計算結果
如圖3所示,相同概念的樣本集的特征計算出的JS散度值均較小(均小于0.2),表示2個樣本集特征分布差異較小,即可以判斷沒有發生概念漂移.
對比實驗為Concept_1數據集和Concept_2數據集,由表3可以得出Concept_1與Concept_2數據集視頻類業務存在特征差異,對這2個不同概念的數據進行JS散度計算,結果如圖4所示:

Fig. 4 JS divergence results for different concept data sets圖4 不同概念數據集JS散度計算結果
如圖4所示,Video樣本計算出的JS散度值較大(圖4中矩形標志的折線),表明Video類業務特征分布的差異較大,即可能發生了概念漂移.
上述實驗窗口大小均取待檢測數據集大小,并且沒有定義漂移檢測閾值,實驗的目的是依據JS散度的檢測結果與原始數據本身是否含有概念漂移進行比對,從而驗證基于JS散度檢測概念漂移的有效性.
3.4.3 檢測窗口大小與檢測閾值
本文采用滑動窗口的方式檢測概念漂移,滑動窗口過大可能會造成概念漂移檢測時漏報率增加,窗口過小可能會造成概念漂移檢測時誤報率增加,同時本文根據特征分布的JS散度衡量特征分布之間是否存在明顯差異,從而判斷是否發生概念漂移,JS散度的閾值大小也影響著檢測算法的性能.
為了確定合適的窗口大小與檢測閾值,采用誤報率與漏報率來評估不同窗口大小與閾值的檢測性能,設置窗口大小為100~250,閾值為0.4~0.6,在不同的窗口與閾值情況下測試誤報率與漏報率,結果如表4所示.
如表4所示,當檢測閾值不變時,隨著檢測窗口變大,誤報率呈現降低的趨勢,漏報率呈現增加的趨勢;同時當檢測窗口大小不變時,隨著檢測閾值增大時,誤報率也呈現降低趨勢,漏報率呈現增加趨勢.
綜合誤報率與漏報率的綜合表現,選擇窗口大小為150,檢測閾值為0.5,從而實現較低的誤報率與漏報率.
3.4.4 檢測方法比較
DDM和STEPT是2種常見的概念漂移檢測方法[10].這里將這2種常見的概念漂移檢測方法與ECDD方法進行對比,測試各算法的概念漂移檢測性能.

Table 4 Detection Window and Threshold表4 檢測窗口與檢測閾值
DDM方法根據分類錯誤率檢測概念漂移,根據默認配置設置其警告級別為2.0,漂移級別為3.0;STEPT方法采用統計檢驗來檢測概念漂移,根據默認配置設置檢測窗口大小為30,警告顯著性水平為0.05,漂移顯著性水平為0.03.ECDD方法則使用上述實驗確定的滑動窗口大小為150,漂移檢測閾值為0.5.
如表5所示為ECDD方法與DDM,STEPT方法在檢測概念漂移的實驗對比結果.

Table 5 Comparison of Detection Methods表5 檢測方法比較
ECDD方法相比較DDM和STEPT方法可以較有效地檢測到概念漂移,綜合誤報率和漏報率,ECDD在概念漂移檢測性能上優于DDM和STEPT方法.
3.5.1 基分類器數目選擇
對于給定的初始訓練集,基分類器數目可能會對分類準確率產生影響.本文采用C4.5作為基分類器,以Concept_1為測試集,圖5描述了在不同的基分類器數目下集成學習模型分類性能的變化情況.

Fig. 5 The effect of the number of base classifiers圖5 基分類器數目對分類效果影響
由圖5可見,當分類器數目為4時,分類器的準確率、精確率、召回率和綜合評價均達到最高,分類效果最優.減小或增加分類器數目時,各項評價指標都會出現相應的下降,因此本文集成學習基分類器數目選擇4,使分類模型性能最優.
3.5.2 分類準確率
本文根據準確率和綜合評價評估算法的分類性能.在單分類器中決策樹C4.5的分類效果較好,本文將同時與C4.5分類器進行對比,如圖6所示為4種方法(ECDD,C4.5,DDM,STEPT)的分類準確率對比.

Fig. 6 Comparison of classification accuracy圖6 4種方法分類準確率對比
如圖6所示,在檢測到概念漂移時,ECDD方法可以快速地更新分類器,根據檢測到的概念漂移點引入新流量重新學習,更新分類器使分類精度回升.C4.5方法由于沒有概念漂移檢測機制,在發生概念漂移時無法引入新流量更新分類器.DDM與STEPT基于分類準確率判斷概念漂移的產生,由于流量不同類別的識別率存在差異,因此對于總體的識別準確率有較大差異,導致這2種方法可能無法有效地檢測概念漂移,最終影響分類準確率.
如圖7所示為4種分類方法(ECDD,C4.5,DDM,STEPT)的綜合評價對比.

Fig. 7 Comparison of F1_score圖7 4種方法綜合評價對比
由圖7可見,ECDD方法在F1_score上總體優于C4.5,DDM,STEPT等方法.
綜上,ECDD方法的分類效果明顯好于C4.5,DDM,EDDM等方法,ECDD方法可以及時有效地更新分類模型,使得分類器保持良好的分類性能.
網絡應用層出不窮,不同網絡應用可能具有不同的特征分布,導致包含這些應用的網絡業務流特征和分布隨之發生改變,產生概念漂移問題,概念漂移導致分類模型分類精度降低,性能下降.本文提出一種基于散度的網絡流概念漂移分類方法ECDD,該方法首先根據網絡流量特征的JS散度變化檢測概念漂移,在檢測到概念漂移后根據增量集成學習策略引入新樣本建立的分類器;接著根據權值比較替換性能下降的分類器;最后,將更新后的集成分類器用于之后的流量分類中.實驗結果表明該方法可以有效地檢測概念漂移,并在概念漂移點更新分類器,達到良好的分類性能.下一步工作將研究如何處理含噪聲的概念漂移網絡流.