基于MapReduce的PCA異常流量檢測系統實現

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

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

1 前言

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

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

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

（1）閾值法

根據歷史數據建立一個正常的參數基線以及一個容忍范圍，一旦網絡流量超出基線的容忍范圍則認為有網絡異常流量出現。

（2）預測法

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

（3）分類法

根據歷史數據和已知的特征訓練分類器，對新出現的數據進行分類，如SVM方法[4]。這些方法大都針對字節、包、IP流、鏈路等一維信號的異常變化來檢測異常。對于復雜的網絡異常流量來說，異常特征隱藏在高維的向量空間中，這些分析方法無法有效應對。

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

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

本文對PCA異常流量檢測方法和MapReduce進行了簡單介紹，并介紹了基于MapReduce的PCA異常流量檢測系統實現，最后給出了實驗結果。

2 PCA異常流量檢測

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

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

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

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

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

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

·選取前r個特征向量作為主成分，剩余的p-r個特征向量作為次成分，r為可調參數；

·每個特征向量的轉置與矩陣B的轉置的內積就是所求的主成分的值。

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

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

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

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

3 MapReduce分布式計算方法

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

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

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

·將輸入的海量數據切成小片分給不同的機器處理；

·Map任務將輸入數據解析成key/value對，執行用戶定義的map函數，把輸入的key/value對轉成中間形式的key/value對；

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

·把不同的key和相應的value集分配給不同的機器，完成reduce運算；

·輸出reduce結果。

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

4 基于MapReduce的PCA異常流量檢測系統

為驗證MapReduc的可行性，我們基于Hadoop分布式軟件架構，實現了PCA網絡異常流量檢測系統，系統部署在與電信骨干網互通的Hadoop服務器集群上。系統由數據采集模塊、統計分析模塊、PCA異常流量檢測模塊、監控模塊4部分組成，系統架構如圖1所示。

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

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

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

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

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

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

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

異常流量監控模塊通過曲線圖顯示Δt×k時間段內各采樣點的主成分和次成分值。當次成分曲線變化圖出現明顯的尖峰時，說明網絡中有異常流量出現，系統發出告警。

5 實驗結果

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

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

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

實驗結果表明，PCA方法能有效檢測網絡中的異常流量，將MapReduce應用在PCA異常流量檢測上，能有效提高系統的運行效率和擴展性，使得PCA方法能夠有效應對運營商超大規模的網絡數據。

6 結束語

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

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

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

3 肖志新，楊岳湘，楊霖.基于小波技術的網絡異常流量檢測與實現.計算機科學，2006,33(10)

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

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

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

7 王海龍，楊岳湘，李強.基于子空間方法的大規模網絡流量異常檢測.計算機工程與應用,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