黃志蘭，丁圣勇，楊國(guó)良，羅頌鋒

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

1 前言

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

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

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

（1）閾值法

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

（2）預(yù)測(cè)法

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

（3）分類法

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

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

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

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

2 PCA異常流量檢測(cè)

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

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

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

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

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

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

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

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

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

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

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

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

3 MapReduce分布式計(jì)算方法

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

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

MapReduce過(guò)程主要包括以下幾個(gè)步驟：

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

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

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

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

·輸出reduce結(jié)果。

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

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

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

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

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

·根據(jù)IP地址段定義Region-to-Region的OD流，并將OD流與源IP、目的IP、源端口、目的端口、包數(shù)、字節(jié)數(shù)六個(gè)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過(guò)程，對(duì)輸入的Netflow數(shù)據(jù)文件進(jìn)行統(tǒng)計(jì)分析，形成每個(gè)特征分布的直方圖。Map-Reduce過(guò)程對(duì)每一條Netflow數(shù)據(jù)流進(jìn)行處理，根據(jù)src_ip、dst_ip字段確定數(shù)據(jù)流歸屬于哪一個(gè)OD，然后對(duì)IP特征分布進(jìn)行累加統(tǒng)計(jì)。

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

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

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

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

5 實(shí)驗(yàn)結(jié)果

我們對(duì)基于MapReduce的PCA異常流量檢測(cè)系統(tǒng)進(jìn)行了驗(yàn)證測(cè)試。系統(tǒng)部署在Hadoop分布式處理平臺(tái)上，平臺(tái)由14臺(tái)IBM刀片服務(wù)組成，與中國(guó)電信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í)驗(yàn)使用的數(shù)據(jù)來(lái)源于中國(guó)電信骨干網(wǎng)，路由器Netflow流量的采樣比為1∶5 000，每天可生成10 TB流量數(shù)據(jù)。圖3、圖4顯示了對(duì)網(wǎng)絡(luò)真實(shí)數(shù)據(jù)進(jìn)行PCA異常流量檢測(cè)的結(jié)果，為了便于查看，我們截取了20 min內(nèi)的監(jiān)測(cè)效果圖。圖3顯示的是前5個(gè)PCA主成分取值隨時(shí)間變化的曲線，可以看出，PCA主成分反映了正常流量的穩(wěn)定規(guī)律，隨時(shí)間波動(dòng)較小。圖4顯示了最后5個(gè)次成分取值隨時(shí)間變化的曲線，可以看出，次成分對(duì)網(wǎng)絡(luò)異常敏感，隨時(shí)間波動(dòng)較大，在03:40這個(gè)時(shí)間點(diǎn)5個(gè)次成分均出現(xiàn)不同程度的尖峰，該時(shí)刻網(wǎng)絡(luò)出現(xiàn)異常流量的可能性極大。由此可見，PCA方法能有效發(fā)現(xiàn)網(wǎng)絡(luò)中的異常流量。

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

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

6 結(jié)束語(yǔ)

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

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

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

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

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

5 王敏，李純喜，陳常嘉.淺談基于PC A的網(wǎng)絡(luò)流量分析.微計(jì)算機(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ò)流量異常檢測(cè).計(jì)算機(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