基于MapReduce的PCA異常流量檢測系統(tǒng)實現(xiàn)

黃志蘭，丁圣勇，楊國良，羅頌鋒

（中國電信股份有限公司廣東研究院 廣州 510630）

1 前言

隨著計算機(jī)網(wǎng)絡(luò)的飛速發(fā)展和互聯(lián)網(wǎng)應(yīng)用的日漸豐富，互聯(lián)網(wǎng)流量呈指數(shù)增長，運營商網(wǎng)絡(luò)面臨越來越大的壓力。在這些網(wǎng)絡(luò)流量里，有正常的用戶訪問流量，也有形形色色的異常流量。網(wǎng)絡(luò)異常流量是指偏離正常行為的網(wǎng)絡(luò)流量，引起網(wǎng)絡(luò)異常流量的原因有很多，如網(wǎng)絡(luò)設(shè)備的不良運行、網(wǎng)絡(luò)操作異常、突發(fā)訪問、病毒攻擊、網(wǎng)絡(luò)入侵等。異常流量具有發(fā)作突然，先兆特征未知等特點，可以在短時間內(nèi)給網(wǎng)絡(luò)設(shè)備和網(wǎng)絡(luò)中的計算機(jī)帶來極大危害，嚴(yán)重影響網(wǎng)絡(luò)安全和網(wǎng)絡(luò)性能[1]。因此，及時檢測網(wǎng)絡(luò)異常行為，判斷網(wǎng)絡(luò)異常的原因，對于保障網(wǎng)絡(luò)的可靠運行具有重要意義，網(wǎng)絡(luò)異常流量檢測也引起了業(yè)界的廣泛關(guān)注和研究。

有多種途徑檢測網(wǎng)絡(luò)異常行為，具體包括SNMP流量分析、網(wǎng)絡(luò)設(shè)備日志分析、Netflow流量分析等。基于Netflow的網(wǎng)絡(luò)異常流量檢測是目前研究和使用最多的方法。Netflow數(shù)據(jù)描繪了網(wǎng)絡(luò)的真實流量狀況，在網(wǎng)絡(luò)正常的時候，Netflow數(shù)據(jù)具有一定的規(guī)律性。當(dāng)網(wǎng)絡(luò)出現(xiàn)異常時，Netflow數(shù)據(jù)將呈現(xiàn)不同尋常的變化，這種變化隱藏在高維的流量數(shù)據(jù)里，需要專門的方法檢測。

目前，主流的基于Netflow的網(wǎng)絡(luò)異常流量檢測方法大致可以分為以下幾類[2]。

（1）閾值法

根據(jù)歷史數(shù)據(jù)建立一個正常的參數(shù)基線以及一個容忍范圍，一旦網(wǎng)絡(luò)流量超出基線的容忍范圍則認(rèn)為有網(wǎng)絡(luò)異常流量出現(xiàn)。

（2）預(yù)測法

根據(jù)歷史數(shù)據(jù)建立網(wǎng)絡(luò)流量模型，根據(jù)模型預(yù)測下一個采樣點的數(shù)據(jù)，如果采樣點的實際數(shù)據(jù)與預(yù)測模型數(shù)據(jù)有較大的誤差，則認(rèn)為有異常流量存在。常用的預(yù)測模型有自回歸模型（AR）、小波預(yù)測[3]、馬可夫模型等。

（3）分類法

根據(jù)歷史數(shù)據(jù)和已知的特征訓(xùn)練分類器，對新出現(xiàn)的數(shù)據(jù)進(jìn)行分類，如SVM方法[4]。這些方法大都針對字節(jié)、包、IP流、鏈路等一維信號的異常變化來檢測異常。對于復(fù)雜的網(wǎng)絡(luò)異常流量來說，異常特征隱藏在高維的向量空間中，這些分析方法無法有效應(yīng)對。

主成分分析（principal component analysis，PCA）[5]方法是發(fā)現(xiàn)高維數(shù)據(jù)模式的通用統(tǒng)計技術(shù)，它在數(shù)據(jù)空間中找一組向量以盡可能地解釋原數(shù)據(jù)的方差，將數(shù)據(jù)從原來的n維空間降到m維（m<

PCA異常流量檢測方法在處理大規(guī)模高維數(shù)據(jù)，尤其是運營商全網(wǎng)流量數(shù)據(jù)時，面臨海量數(shù)據(jù)處理帶來的性能挑戰(zhàn)。MapReduce分布式計算方法綜合利用計算機(jī)集群的處理能力，能高效解決海量數(shù)據(jù)分析任務(wù)。MapReduce應(yīng)用在PCA異常流量檢測上，能顯著提高PCA方法的擴(kuò)展性，使得PCA算法能高效地在運營商全網(wǎng)范圍內(nèi)實時檢測異常流量。

本文對PCA異常流量檢測方法和MapReduce進(jìn)行了簡單介紹，并介紹了基于MapReduce的PCA異常流量檢測系統(tǒng)實現(xiàn)，最后給出了實驗結(jié)果。

2 PCA異常流量檢測

PCA是一種處理高維隨機(jī)變量的方法，通過對數(shù)據(jù)進(jìn)行線性變換，使得變換后的數(shù)據(jù)能量主要集中在主成分方向，從而使得原本基于高維處理的很多問題能夠在低維空間解決[6]。應(yīng)用在網(wǎng)絡(luò)異常監(jiān)測中，PCA的次成分充當(dāng)了異常顯微放大功能。對很多異常，在通常情況下，并不能簡單地通過閥值比較來進(jìn)行判斷，如流量矩陣結(jié)構(gòu)的變化等，但這些變化經(jīng)過PCA變換后，通常會在次成分產(chǎn)生較大波動，從而提供一種有效異常監(jiān)測功能。

對于一個多維數(shù)據(jù)集，將其化成矩陣A。Ai表示A的第i列，代表原數(shù)據(jù)的一維數(shù)據(jù)序列。PCA的一般步驟描述如下[7]：

·將矩陣A零均值化，即求Ai所有數(shù)據(jù)的平均值，再用Ai中的每個數(shù)據(jù)減去這個平均值，得到各列平均值都為0的矩陣B；

·計算矩陣B的協(xié)方差，得到協(xié)方差矩陣C，C=BTB；

·求解矩陣C的特征值和特征向量，每個特征向量vi就是 C 的主成分或次成分，即：Cvi=λivi，i=1,…,p，其 中 ，λi是vi對應(yīng)的特征值，對特征向量進(jìn)行歸一化處理；

·把特征值從大到小排列，即 λ1≥λ2≥…≥λp，并把特征向量按照對應(yīng)的特征值進(jìn)行重新排序，得到一個特征向量序列（v1，v2，…，vp）；

·選取前r個特征向量作為主成分，剩余的p-r個特征向量作為次成分，r為可調(diào)參數(shù)；

·每個特征向量的轉(zhuǎn)置與矩陣B的轉(zhuǎn)置的內(nèi)積就是所求的主成分的值。

將PCA應(yīng)用在全網(wǎng)異常流量檢測時，首先需要將Netflow流量數(shù)據(jù)轉(zhuǎn)化成PCA可處理的高維矩陣。根據(jù)流量聚集程度的不同，可以從路由器、鏈路、OD（origindestination）流等層面定義PCA輸入矩陣[8]。如以鏈路為單位進(jìn)行PCA異常流量檢測時，把輸入矩陣A定義為t×p矩陣，其中p代表網(wǎng)絡(luò)中的鏈路數(shù)量，t代表采樣的點數(shù)，這樣A的每列i代表第i條鏈路的時間序列，每行j代表所有鏈路流在j時刻的采樣值。研究表明，流量聚集程度對PCA檢測結(jié)果的影響很大，過分聚合將隱藏異常流量的特性，聚合不足則會導(dǎo)致PCA被波動過大的小流量干擾而無法正常檢測。

本文對中國電信全網(wǎng)異常流量進(jìn)行檢測，流量聚集在Region-to-Region級別的OD流層面。我們把中國電信城域網(wǎng)按地理位置劃分成十大區(qū)域，每個區(qū)域稱為一個Region，每個Netflow數(shù)據(jù)流根據(jù)源IP和目的IP歸屬到某個Region-to-Region OD流，Region的區(qū)間由 IP地址段決定。系統(tǒng)采用基于IP特征的信息熵時間序列構(gòu)建PCA輸入矩陣，信息熵提供了一個可計算的高效機(jī)制，用于評估分布的離散和聚合程度，而各種異常都將影響一個或多個IP特征的分布，因此基于IP特征的信息熵時間序列可以有效地捕獲網(wǎng)絡(luò)流量的異常變化[8]。

PCA輸入矩陣或稱流量矩陣A由一系列時間序列向量構(gòu)成，每個時間序列向量有m個特征，這m個特征為OD流與 IP流量特征（源IP、目的 IP、源端口、目的端口、包數(shù)量、字節(jié)數(shù)）的組合。即：A為n×m矩陣，n代表采樣點數(shù)，m代表特征數(shù)目，A的每列i代表第i個特征的時間序列，每行j代表所有特征在j時刻采樣的信息熵。特征名為ODk_IP_Feature，如ODk_SRCIP表示第k個OD流的源IP統(tǒng)計值的信息熵。

對于PCA異常流量檢測而言，PCA過程相對簡單，只對輸入矩陣進(jìn)行簡單的數(shù)學(xué)變換，然后計算特征值和特征向量即可，對機(jī)器性能和運算效率要求不高。對全網(wǎng)流量進(jìn)行分析統(tǒng)計，得出一個可供PCA有效運算的輸入數(shù)據(jù)矩陣，卻是一個相當(dāng)艱巨的任務(wù)。為此，需要引入高性能的分布式計算方法，借用計算機(jī)集群的大規(guī)模處理能力解決海量數(shù)據(jù)分析問題。通過分析，我們發(fā)現(xiàn)MapReduce分布式計算模型天然適應(yīng)對流量數(shù)據(jù)的統(tǒng)計分析，可在大規(guī)模流量數(shù)據(jù)中快速生成PCA算法所需的輸入矩陣。我們也通過真實數(shù)據(jù)驗證了基于MapReduce的PCA異常流量檢測的可行性。

3 MapReduce分布式計算方法

MapReduce[9]是一種有效的分布式編程模型，它提供了泛函編程的一個簡化版本，與傳統(tǒng)編程模型中函數(shù)參數(shù)只能代表明確的一個數(shù)或數(shù)的集合不同，泛函編程模型中函數(shù)參數(shù)能夠代表一個函數(shù)，這使得泛函編程模型的表達(dá)能力和抽象能力更高。Google云計算系統(tǒng)以及開源的Hadoop分布式軟件架構(gòu)都提供了對MapReduce編程模型的實現(xiàn)，這些系統(tǒng)隱藏了并行化、容錯、數(shù)據(jù)分布、負(fù)載均衡等復(fù)雜的分布式處理細(xì)節(jié)，提供了簡單有力的接口來實現(xiàn)自動的并行化和大規(guī)模分布式計算，從而能在大量普通PC機(jī)上實現(xiàn)高性能計算。

在MapReduce模型中，輸入數(shù)據(jù)和輸出結(jié)果都被視作由一系列key/value對組成的集合。用戶指定map函數(shù)對輸入key/value集進(jìn)行處理，形成中間形式的key/value集；MapReduce庫按照key值把中間形式的value集中起來，傳給用戶指定的reduce函數(shù)；reduce函數(shù)把具有相同key的value合并在一起，最終輸出一系列key/value對。

MapReduce過程主要包括以下幾個步驟：

·將輸入的海量數(shù)據(jù)切成小片分給不同的機(jī)器處理；

·Map任務(wù)將輸入數(shù)據(jù)解析成key/value對，執(zhí)行用戶定義的map函數(shù)，把輸入的key/value對轉(zhuǎn)成中間形式的key/value對；

·按照key值對中間形式的key/value進(jìn)行排序、聚集；

·把不同的key和相應(yīng)的value集分配給不同的機(jī)器，完成reduce運算；

·輸出reduce結(jié)果。

在Hadoop分布式軟件架構(gòu)中，數(shù)據(jù)的分片、任務(wù)的分配及調(diào)度、中間結(jié)果的排序匯總、運算結(jié)果的輸出都是由框架實現(xiàn)的，用戶只需編寫自己的Map函數(shù)和Reduce函數(shù)。Hadoop MapReduce模型具有很強(qiáng)的容錯性，已被許多系統(tǒng)成功運用。本文提出的基于MapReduce的PCA異常流量檢測系統(tǒng)，也架構(gòu)在Hadoop平臺之上。

4 基于MapReduce的PCA異常流量檢測系統(tǒng)

為驗證MapReduc的可行性，我們基于Hadoop分布式軟件架構(gòu)，實現(xiàn)了PCA網(wǎng)絡(luò)異常流量檢測系統(tǒng)，系統(tǒng)部署在與電信骨干網(wǎng)互通的Hadoop服務(wù)器集群上。系統(tǒng)由數(shù)據(jù)采集模塊、統(tǒng)計分析模塊、PCA異常流量檢測模塊、監(jiān)控模塊4部分組成，系統(tǒng)架構(gòu)如圖1所示。

流量采集模塊基于Cisco開源的Netflow流量采集器NFC組件實現(xiàn)，收集來自中國電信骨干網(wǎng)全網(wǎng)路由器的Netflow流量。為應(yīng)對海量Netflow數(shù)據(jù)的存儲需求，我們對NFC模塊進(jìn)行了修改，使其將收集到的Netflow數(shù)據(jù)以二進(jìn)制文件的形式存儲在Hadoop分布式文件系統(tǒng)HDFS中。流量采集模塊每Δt時間內(nèi)生成一個HDFS文件，每個HDFS文件產(chǎn)生一個熵時間序列。

MapReduce統(tǒng)計分析模塊是系統(tǒng)的核心，它基于Hadoop MapReduce編程模型對Netflow流量數(shù)據(jù)文件進(jìn)行統(tǒng)計分析，最終輸出供PCA異常流量檢測模塊處理的熵矩陣。統(tǒng)計分析模塊的數(shù)據(jù)處理過程如下。

·根據(jù)IP地址段定義Region-to-Region的OD流，并將OD流與源IP、目的IP、源端口、目的端口、包數(shù)、字節(jié)數(shù)六個IP特征進(jìn)行組合，形成形如ODk_SRC_IP、ODk_DST_IP、ODk_SRC_PORT、ODk_DST_PORT、ODk_Packet、ODk_Bytes（k=1,…,100）的特征。按照特征的取值范圍定義不同的區(qū)間，構(gòu)建特征分布直方圖。

·定義Map-Reduce過程，對輸入的Netflow數(shù)據(jù)文件進(jìn)行統(tǒng)計分析，形成每個特征分布的直方圖。Map-Reduce過程對每一條Netflow數(shù)據(jù)流進(jìn)行處理，根據(jù)src_ip、dst_ip字段確定數(shù)據(jù)流歸屬于哪一個OD，然后對IP特征分布進(jìn)行累加統(tǒng)計。

·根據(jù)特征分布直方圖，計算每個特征ODk_IP_Feature的信息熵 Entropy（pi）=-Σpilog pi，其中pi為落入第i個取值區(qū)間的概率。

·所有特征的熵值組成一個熵時間序列，將該序列存儲在MySql數(shù)據(jù)庫中，供PCA異常流量檢測模塊處理。

PCA異常流量檢測模塊對MySql數(shù)據(jù)庫中的熵時間序列進(jìn)行處理，每次選取k條記錄，形成600×k矩陣，其中k為可調(diào)參數(shù)。PCA異常流量檢測模塊依次對熵矩陣進(jìn)行零均值化、協(xié)方差矩陣計算、特征值和特征向量計算等步驟后形成主成分和次成分。新的熵時間序列在主成分、次成分方向通過內(nèi)積投影，即可形成相應(yīng)的主成分/次成分值，供異常流量監(jiān)控模塊使用。

異常流量監(jiān)控模塊通過曲線圖顯示Δt×k時間段內(nèi)各采樣點的主成分和次成分值。當(dāng)次成分曲線變化圖出現(xiàn)明顯的尖峰時，說明網(wǎng)絡(luò)中有異常流量出現(xiàn)，系統(tǒng)發(fā)出告警。

5 實驗結(jié)果

我們對基于MapReduce的PCA異常流量檢測系統(tǒng)進(jìn)行了驗證測試。系統(tǒng)部署在Hadoop分布式處理平臺上，平臺由14臺IBM刀片服務(wù)組成，與中國電信ChinaNet骨干網(wǎng)互通。服務(wù)器的硬件配置為：2路8核2.5 GHz CPU，8 GB內(nèi)存，280 GB硬盤。配置的操作系統(tǒng)為Ubuntu 8.10 Server，Hadoop版本為0.19.1,網(wǎng)絡(luò)結(jié)構(gòu)如圖2所示。

實驗使用的數(shù)據(jù)來源于中國電信骨干網(wǎng)，路由器Netflow流量的采樣比為1∶5 000，每天可生成10 TB流量數(shù)據(jù)。圖3、圖4顯示了對網(wǎng)絡(luò)真實數(shù)據(jù)進(jìn)行PCA異常流量檢測的結(jié)果，為了便于查看，我們截取了20 min內(nèi)的監(jiān)測效果圖。圖3顯示的是前5個PCA主成分取值隨時間變化的曲線，可以看出，PCA主成分反映了正常流量的穩(wěn)定規(guī)律，隨時間波動較小。圖4顯示了最后5個次成分取值隨時間變化的曲線，可以看出，次成分對網(wǎng)絡(luò)異常敏感，隨時間波動較大，在03:40這個時間點5個次成分均出現(xiàn)不同程度的尖峰，該時刻網(wǎng)絡(luò)出現(xiàn)異常流量的可能性極大。由此可見，PCA方法能有效發(fā)現(xiàn)網(wǎng)絡(luò)中的異常流量。

MapReduce具有良好的可擴(kuò)展性，能夠有效應(yīng)對大規(guī)模PCA異常流量檢測對計算能力的需求。當(dāng)需要處理的數(shù)據(jù)量增大時，通過在Hadoop集群中添加更多的計算機(jī)可以有效提高PCA異常流量檢測方法的處理效率。圖5反映了基于MapReduce的PCA異常流量檢測系統(tǒng)的擴(kuò)展能力，可以看出，對于單機(jī)系統(tǒng)而言，隨著數(shù)據(jù)量增大，運行時間呈線性增長。在多機(jī)情況下，如5臺機(jī)、10臺機(jī)時，隨著流量數(shù)據(jù)增加，PCA運行時間增長緩慢。隨著集群機(jī)器增多，基于MapReduce的PCA異常流量檢測方法運行效率得到提升。

實驗結(jié)果表明，PCA方法能有效檢測網(wǎng)絡(luò)中的異常流量，將MapReduce應(yīng)用在PCA異常流量檢測上，能有效提高系統(tǒng)的運行效率和擴(kuò)展性，使得PCA方法能夠有效應(yīng)對運營商超大規(guī)模的網(wǎng)絡(luò)數(shù)據(jù)。

6 結(jié)束語

實驗表明，MapReduce分布式編程模型天然適應(yīng)Netflow網(wǎng)絡(luò)流量數(shù)據(jù)分析。利用MapReduce方法對Netflow流量數(shù)據(jù)進(jìn)行處理，生成熵時間序列矩陣供PCA算法檢測分析，可有效提高PCA異常流量檢測系統(tǒng)的處理能力和性能。未來，我們將嘗試把MapReduce分布式編程思想應(yīng)用到其他流量分析方法，以提高現(xiàn)有流量分析工具的工作性能和處理能力，從而應(yīng)對全網(wǎng)大規(guī)模流量數(shù)據(jù)的分析處理需求。

1 楊丹，胡光岷，李宗林，姚興苗.全局的多流量相關(guān)異常檢測算法.電子科技大學(xué)學(xué)報，2008,37(6)

2 賈冠昕，楊波，陳貞翔，彭立志.基于NetFlow時間序列的網(wǎng)絡(luò)異常檢測.計算機(jī)工程與應(yīng)用，2008,44(24)

3 肖志新，楊岳湘，楊霖.基于小波技術(shù)的網(wǎng)絡(luò)異常流量檢測與實現(xiàn).計算機(jī)科學(xué)，2006,33(10)

4 柴志成.一種基于SVM的網(wǎng)絡(luò)異常流量檢測新方法.貴陽學(xué)院學(xué)報，2008,3(1)

5 王敏，李純喜，陳常嘉.淺談基于PC A的網(wǎng)絡(luò)流量分析.微計算機(jī)信息，2006，22(6)

6 Lakhina A,Crovella M,Diot C.Diagnosing network-wide traffic anomalies.ACM SIGCOMM,Portland,August 2004

7 王海龍，楊岳湘，李強(qiáng).基于子空間方法的大規(guī)模網(wǎng)絡(luò)流量異常檢測.計算機(jī)工程與應(yīng)用,2007，43(11)

8 Haakon Ringberg,Augustin Soule,Jennifer Rexford,Christophe Diot.Sensitivity of PCA for traffic anomaly detection.In:Proc of SIGMETRICS'07,2007

9 Dean Jeffrey,Sanjay Ghemawat.MapReduce:simplified data processing on large clusters.In:Proc of Symposium on Operating System Design and Implementation,2004