周愛平 朱琛剛

摘 要：持續(xù)流是隱蔽的網(wǎng)絡(luò)攻擊過程中顯現(xiàn)的一種重要特征，它不產(chǎn)生大量流量且在較長(zhǎng)周期內(nèi)有規(guī)律地發(fā)生，給傳統(tǒng)的檢測(cè)方法帶來極大挑戰(zhàn)。針對(duì)網(wǎng)絡(luò)攻擊的隱蔽性、單監(jiān)測(cè)點(diǎn)的重負(fù)荷和信息有限的問題，提出全網(wǎng)絡(luò)持續(xù)流檢測(cè)方法。首先，設(shè)計(jì)一種概要數(shù)據(jù)結(jié)構(gòu)，并將其部署在每個(gè)監(jiān)測(cè)點(diǎn);其次，當(dāng)網(wǎng)絡(luò)流到達(dá)監(jiān)測(cè)點(diǎn)時(shí)，提取流的概要信息并更新概要數(shù)據(jù)結(jié)構(gòu)的一位;然后，在測(cè)量周期結(jié)束時(shí)，主監(jiān)測(cè)點(diǎn)將來自其他監(jiān)測(cè)點(diǎn)的概要信息進(jìn)行綜合;最后，提出流持續(xù)性的近似估計(jì)，通過一些簡(jiǎn)單計(jì)算為每個(gè)流構(gòu)建一個(gè)位向量，利用概率統(tǒng)計(jì)方法估計(jì)流持續(xù)性，使用修正后的持續(xù)性估計(jì)檢測(cè)持續(xù)流。通過真實(shí)的網(wǎng)絡(luò)流量進(jìn)行實(shí)驗(yàn)，結(jié)果表明，與長(zhǎng)持續(xù)時(shí)間流檢測(cè)算法（TLF）相比，所提方法的準(zhǔn)確性提高了50%，誤報(bào)率和漏報(bào)率分別降低了22%和20%，說明全網(wǎng)絡(luò)持續(xù)流檢測(cè)方法能夠有效監(jiān)測(cè)高速網(wǎng)絡(luò)流量。

關(guān)鍵詞：網(wǎng)絡(luò)測(cè)量;持續(xù)流檢測(cè);網(wǎng)絡(luò)攻擊;概要數(shù)據(jù)結(jié)構(gòu);概率統(tǒng)計(jì)方法

中圖分類號(hào)：?TP393.08

文獻(xiàn)標(biāo)志碼：A

Detection method for network-wide persistent flow based on sketch data structure

ZHOU Aiping1，2*， ZHU Chengang3

1.School of Computer Science and Technology， Taizhou University， Taizhou Jiangsu 225300， China ;

2.Key Laboratory of Computer Network and Information Integration of Ministry of Education （Southeast University）， Nanjing Jiangsu 211189， China ;

3.School of Computer Science and Engineering， Southeast University， Nanjing Jiangsu 211189， China

Abstract：?Persistent flow is an important feature of hidden network attack. It does not generate a large amount of traffic and it occurs regularly in a long period， so that it brings a large challenge for traditional detection methods. Network attacks have invisibility， single monitors have heavy load and limited information. Aiming at the above problems， a method to detect network-wide persistent flows was proposed. Firstly， a sketch data structure was designed and was deployed on each monitor. Secondly， when the network flow arrived at a monitor， the summary information was extracted from network data stream and one bit in the sketch data structure was updated. Thirdly， at the end of measurement period， the summary information from other monitors was synthesized by the main monitor. Finally， the approximate estimation of flow persistence was presented. A bit vector was constructed for each flow by some simple computing， flow persistence was estimated by using probability statistical method， and the persistent flows were detected based on revised persistence estimation. The experiments were conducted on real network traffic， and their results show that compared with the algorithm of Tracing Long Duration flows （TLF）， the proposed method increases the accuracy by 50% and reduces the false positive rate， false negative rate by 22%， 20% respectively. The results illustrate that the method of detecting network-wide persistent flows can effectively monitor network traffic in high-speed networks.

Key words：?network measurement; persistent flow detection; network attack; sketch data structure; probabilistic statistical method

0 引言

網(wǎng)絡(luò)流量測(cè)量是流量工程、異常檢測(cè)、用戶行為分析等的基礎(chǔ)。大流挖掘[1]、超點(diǎn)識(shí)別[2]和持續(xù)流檢測(cè)[3-4]一直是網(wǎng)絡(luò)流量測(cè)量的三個(gè)重要問題。大流挖掘指在測(cè)量周期內(nèi)從海量網(wǎng)絡(luò)流量中挖掘流長(zhǎng)超過一定閾值的流，大流也稱為heavy hitters、elephant flows、frequent items等，如流量計(jì)費(fèi)。超點(diǎn)識(shí)別指在測(cè)量周期內(nèi)識(shí)別連接數(shù)超過一定閾值的節(jié)點(diǎn)，如分布式拒絕服務(wù)（Distributed Denial of Service，DDoS）攻擊檢測(cè)。持續(xù)流檢測(cè)指在測(cè)量周期內(nèi)檢測(cè)持續(xù)時(shí)間超過一定閾值的流，如僵尸網(wǎng)絡(luò)檢測(cè)。持續(xù)流不同于大流、超點(diǎn)，可能不產(chǎn)生大量流量或建立大量連接，而是在較長(zhǎng)周期內(nèi)有規(guī)律地建立連接，往往與異常網(wǎng)絡(luò)行為相關(guān)。因此，傳統(tǒng)的網(wǎng)絡(luò)流量測(cè)量方法難以解決持續(xù)流檢測(cè)問題。隨著互聯(lián)網(wǎng)的快速發(fā)展和網(wǎng)絡(luò)應(yīng)用的多樣化，持續(xù)產(chǎn)生的網(wǎng)絡(luò)流給高速網(wǎng)絡(luò)流量測(cè)量帶來了諸多挑戰(zhàn)。

由于網(wǎng)絡(luò)攻擊者故意在某些時(shí)間段內(nèi)不發(fā)送報(bào)文，躲避了傳統(tǒng)的長(zhǎng)持續(xù)時(shí)間流檢測(cè)。長(zhǎng)持續(xù)時(shí)間流檢測(cè)方法只能識(shí)別持續(xù)不間斷的攻擊行為，而無法識(shí)別隱蔽的網(wǎng)絡(luò)攻擊行為。為了能夠檢測(cè)隱藏的網(wǎng)絡(luò)攻擊行為，需要重新定義持續(xù)流測(cè)度。持續(xù)流表示在測(cè)量周期內(nèi)有規(guī)律地發(fā)生，而不一定在連續(xù)的時(shí)間區(qū)間內(nèi)發(fā)送報(bào)文以及產(chǎn)生大量流量。將測(cè)量周期劃分為多個(gè)時(shí)間槽，流的持續(xù)性表示流在測(cè)量周期內(nèi)出現(xiàn)的時(shí)間槽數(shù)量。因此，持續(xù)流定義為持續(xù)性大于一定閾值的流，即令測(cè)量周期為T，時(shí)間槽為Ti（0≤i≤d），閾值為，如果流f的持續(xù)性滿足p（f）>，那么f為持續(xù)流。

持續(xù)流檢測(cè)已經(jīng)引起工業(yè)界和學(xué)術(shù)界的廣泛關(guān)注。對(duì)于網(wǎng)絡(luò)安全，攻擊者可以在較長(zhǎng)周期內(nèi)通過少量的攻擊主機(jī)降低目標(biāo)服務(wù)器的性能而不使目標(biāo)服務(wù)器癱瘓，持續(xù)流檢測(cè)能夠識(shí)別隱蔽的DDoS攻擊;另外，通過監(jiān)測(cè)僵尸主機(jī)與命令控制服務(wù)器之間的通信，持續(xù)流檢測(cè)有助于發(fā)現(xiàn)網(wǎng)絡(luò)僵尸主機(jī)[5];對(duì)于點(diǎn)擊詐騙，廣告發(fā)布商通過自動(dòng)點(diǎn)擊工具周期性地點(diǎn)擊廣告，從而提高廣告發(fā)布商的收入而增加廣告客戶支出，持續(xù)流檢測(cè)有助于識(shí)別點(diǎn)擊欺騙行為。

持續(xù)流檢測(cè)大致劃分為三種類型：1）簡(jiǎn)單檢測(cè)方法存儲(chǔ)每個(gè)流的狀態(tài)信息。雖然簡(jiǎn)單檢測(cè)方法能夠準(zhǔn)確地檢測(cè)持續(xù)流，但需要消耗大量的系統(tǒng)資源，因此該方法缺乏可擴(kuò)展性。2）基于抽樣的流持續(xù)時(shí)間估計(jì)方法通過流時(shí)間間隔分布和流長(zhǎng)分布估計(jì)流持續(xù)時(shí)間分布[6]。長(zhǎng)持續(xù)時(shí)間流跟蹤方法利用兩個(gè)Bloom Filter分別存儲(chǔ)過去和當(dāng)前時(shí)間區(qū)間內(nèi)候選的活躍長(zhǎng)持續(xù)時(shí)間流，使用Hash表存儲(chǔ)識(shí)別的長(zhǎng)持續(xù)時(shí)間流，通過抽樣過濾大部分的短持續(xù)時(shí)間流[3]。抽樣檢測(cè)方法只存儲(chǔ)抽樣流的狀態(tài)信息。雖然抽樣檢測(cè)方法需要較少的系統(tǒng)資源，但由于檢測(cè)準(zhǔn)確性受到抽樣率的影響，降低了檢測(cè)準(zhǔn)確性。

3）長(zhǎng)持續(xù)時(shí)間流檢測(cè)的數(shù)據(jù)流方法利用兩種數(shù)據(jù)結(jié)構(gòu)：計(jì)數(shù)Bloom Filter和Bloom Filter，

不產(chǎn)生漏報(bào)且節(jié)省內(nèi)存空間[4]。研究表明傳統(tǒng)的長(zhǎng)持續(xù)時(shí)間流檢測(cè)在安全監(jiān)控方面存在嚴(yán)重的不足，攻擊者能夠輕易躲避檢測(cè)[7-8]。因此，Shin等[9]提出躲避的長(zhǎng)持續(xù)時(shí)間流檢測(cè)數(shù)據(jù)流方法，利用持續(xù)性識(shí)別躲避的長(zhǎng)持續(xù)時(shí)間流。Lahiri等[10]研究表明持續(xù)項(xiàng)的在線檢測(cè)方法需要大內(nèi)存，不能運(yùn)行在單流量監(jiān)測(cè)點(diǎn)上，所以在固定窗口和滑動(dòng)窗口場(chǎng)景下提出了空間有效的持續(xù)項(xiàng)近似跟蹤方法。持續(xù)項(xiàng)跟蹤的分布式方法在無限窗口和滑動(dòng)窗口場(chǎng)景下能夠近似地跟蹤持續(xù)項(xiàng)，具有低通信開銷、低漏報(bào)率和低誤報(bào)率[11]。持續(xù)項(xiàng)識(shí)別方法首先利用Raptor Code存儲(chǔ)每項(xiàng)的標(biāo)識(shí)，然后恢復(fù)持續(xù)項(xiàng)的標(biāo)識(shí)。該方法利用少量的內(nèi)存以一定的誤報(bào)率識(shí)別持續(xù)項(xiàng)[12]。網(wǎng)絡(luò)數(shù)據(jù)流檢測(cè)方法能夠存儲(chǔ)每個(gè)流的概要信息，保證檢測(cè)準(zhǔn)確性，同時(shí)滿足存儲(chǔ)空間和處理速度的要求。

目前，大部分檢測(cè)方法通過單監(jiān)測(cè)點(diǎn)分析用戶行為，這些分析結(jié)論往往具有一定的局限性。而且持續(xù)產(chǎn)生的網(wǎng)絡(luò)流導(dǎo)致單監(jiān)測(cè)點(diǎn)負(fù)荷較重，無法及時(shí)處理。通常攻擊者通過多條路徑實(shí)施網(wǎng)絡(luò)攻擊，單監(jiān)測(cè)點(diǎn)難以及時(shí)準(zhǔn)確地識(shí)別一些異常行為。

一些攻擊者正是利用單監(jiān)測(cè)點(diǎn)的局限性，才能夠成功躲避網(wǎng)絡(luò)安全檢測(cè)。

因此，只有將多個(gè)監(jiān)測(cè)點(diǎn)的分析結(jié)果進(jìn)行綜合，才能準(zhǔn)確有效地識(shí)別異常用戶行為。為了能夠有效識(shí)別異常用戶行為，提出了全網(wǎng)絡(luò)持續(xù)流概念。令監(jiān)測(cè)點(diǎn)的數(shù)量為k，每個(gè)監(jiān)測(cè)點(diǎn)i處理網(wǎng)絡(luò)流為Si（0 ≤ i ≤ k），網(wǎng)絡(luò)總流量為S= ∪ ?k i=0 Si。如果流f在S中出現(xiàn)的時(shí)間槽總數(shù)高于閾值，那么流f認(rèn)為是全網(wǎng)絡(luò)持續(xù)流。即使同一個(gè)流f多次出現(xiàn)在相同的時(shí)間槽，流f的持續(xù)性只能增加1。

此外，數(shù)據(jù)流方法能夠?qū)⒑Ａ烤W(wǎng)絡(luò)流量壓縮到較小的存儲(chǔ)空間并保持一定的精確度，同時(shí)具有在線實(shí)時(shí)處理和有限存儲(chǔ)空間的特性。數(shù)據(jù)流方法通過概要數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)報(bào)文的概要信息，如Bitmap[13]、Bloom Filter[14]、Count-Min Sketch[15]、HyperLogLog[6， 16]，廣泛使用于流長(zhǎng)估計(jì)[15]、大流識(shí)別[17]、流長(zhǎng)分布估計(jì)[18]、連接度估計(jì)[2]等。

傳統(tǒng)持續(xù)流檢測(cè)方法一定程度上改善了檢測(cè)性能，但仍存在不足之處。其一，高速鏈路上通過大量存儲(chǔ)空間維護(hù)所有流是不可行的，雖然抽樣能夠降低存儲(chǔ)空間，但持續(xù)流估計(jì)的準(zhǔn)確性依賴于抽樣率;其二，網(wǎng)絡(luò)攻擊往往利用大量節(jié)點(diǎn)向目標(biāo)節(jié)點(diǎn)發(fā)送大量鏈接，集中式檢測(cè)方法難以發(fā)現(xiàn)此類攻擊;其三，為了躲避檢測(cè)，網(wǎng)絡(luò)攻擊通常不發(fā)送大量流量，而是在相當(dāng)長(zhǎng)的時(shí)間內(nèi)間斷地發(fā)送少量流量，現(xiàn)有檢測(cè)方法存在較高的誤報(bào)和漏報(bào)。因此，針對(duì)傳統(tǒng)檢測(cè)方法的局限性和網(wǎng)絡(luò)攻擊的特點(diǎn)，提出基于概要數(shù)據(jù)結(jié)構(gòu)的全網(wǎng)絡(luò)持續(xù)流檢測(cè)方法。多個(gè)監(jiān)測(cè)點(diǎn)使用相同的數(shù)據(jù)結(jié)構(gòu)，對(duì)到達(dá)的網(wǎng)絡(luò)流進(jìn)行信息提取，然后對(duì)概要數(shù)據(jù)結(jié)構(gòu)進(jìn)行更新。當(dāng)測(cè)量周期結(jié)束時(shí)，主監(jiān)測(cè)點(diǎn)將來自其他所有監(jiān)測(cè)點(diǎn)的概要信息進(jìn)行綜合。當(dāng)用戶提出查詢請(qǐng)求時(shí)，估計(jì)流的持續(xù)性，如果持續(xù)性超過設(shè)定閾值，進(jìn)行相應(yīng)的響應(yīng)，顯示持續(xù)流信息。實(shí)驗(yàn)利用中國(guó)教育和科研計(jì)算機(jī)網(wǎng)的實(shí)際網(wǎng)絡(luò)流量traces，結(jié)果表明本文方法具有良好的檢測(cè)性能。

1 全網(wǎng)絡(luò)持續(xù)流檢測(cè)算法

1.1 算法描述

全網(wǎng)絡(luò)持續(xù)流檢測(cè)（Detect Network-wide Persistent Flows，DPF）包括流處理模塊和持續(xù)流檢測(cè)模塊：流處理模塊主要負(fù)責(zé)流信息的提取和數(shù)據(jù)更新，持續(xù)流檢測(cè)模塊主要負(fù)責(zé)持續(xù)性估計(jì)和持續(xù)流檢測(cè)。當(dāng)報(bào)文流到達(dá)監(jiān)測(cè)點(diǎn)時(shí)，提取流的相關(guān)信息，如源IP地址、目的IP地址、源端口、目的端口、協(xié)議類型、時(shí)間戳，然后利用流的標(biāo)識(shí)信息更新數(shù)據(jù)結(jié)構(gòu)。當(dāng)測(cè)量周期結(jié)束時(shí)，將來自多個(gè)監(jiān)測(cè)點(diǎn)的概要信息進(jìn)行綜合，更新主監(jiān)測(cè)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)。當(dāng)用戶發(fā)送查詢請(qǐng)求時(shí)，進(jìn)行流的持續(xù)性估計(jì)，顯示持續(xù)流信息。首先，為每個(gè)流建立一個(gè)位向量，統(tǒng)計(jì)位向量中0的位數(shù)，根據(jù)概率統(tǒng)計(jì)方法推斷流的持續(xù)性估計(jì);然后，將持續(xù)性估計(jì)超過閾值的流識(shí)別為持續(xù)流。算法的相關(guān)定義如下：

定義1

報(bào)文流表示順序到達(dá)的報(bào)文序列，記為S=p1， p2， …， pi， …，其中pi表示第i個(gè)報(bào)文，由多個(gè)字段構(gòu)成，如源IP地址、目的IP地址、源端口、目的端口、協(xié)議類型、時(shí)間戳。

定義2

流f表示具有相同源IP地址、目的IP地址的報(bào)文序列，記為P=pi1，pi2，…，pii，…，其中pii表示第i個(gè)報(bào)文，同樣由多個(gè)字段構(gòu)成，也稱pii∈f。

定義3

持續(xù)性表示流f出現(xiàn)的時(shí)間槽數(shù)，將測(cè)量周期T等分為多個(gè)時(shí)間槽Ti（0 ≤i≤ d-1），記為p（f）。

定義4

持續(xù)流表示在測(cè)量周期內(nèi)持續(xù)性大于一定閾值的流集合，即：

F1={f | p（f）>1，pi∈S∩pi∈f}

定義5

假設(shè)網(wǎng)絡(luò)中k個(gè)監(jiān)測(cè)點(diǎn)，監(jiān)測(cè)節(jié)點(diǎn)i處理報(bào)文流Si（0≤i≤k-1），全網(wǎng)絡(luò)持續(xù)流表示在測(cè)量周期內(nèi)持續(xù)性大于一定閾值的流集合，即

F2= { f | p（f）>2，pi∈ ∪? k-1 i=0 Si∩pi∈f }

1.2 數(shù)據(jù)結(jié)構(gòu)

DPF使用的數(shù)據(jù)結(jié)構(gòu)為位向量 A i（0≤i≤k-1），其大小為m， A i[j]（0≤i≤k-1，0≤j≤m-1）是一個(gè)比特位，如圖1所示。位向量 A i（0≤i≤k-1）共享Hash函數(shù)hi（0≤i≤s-1），它將流f映射到 A i（0≤i≤k-1）的某個(gè)位置。Hash函數(shù)hi（0≤i≤s-1）的定義如式（1）：

hi：{0，1，…，N-1}→{0，1，…，m-1}

（1）

其中，N表示地址空間的大小。

測(cè)量周期結(jié)束后，將來自每個(gè)監(jiān)測(cè)點(diǎn)的概要信息進(jìn)行綜合，形成位向量 A ，為每個(gè)流f構(gòu)造一個(gè)位向量 B （f），其大小為s， B （f）由隨機(jī)地選擇位向量 A 的s位構(gòu)成。位向量 B （f）的定義如式（2）：

B （f）=（?? A[h0（f）]，? A [h1（f）]， …，? A [hs-1（f）]）

（2）

數(shù)據(jù)結(jié)構(gòu)由位向量 A i構(gòu)成，其大小為m比特，測(cè)量周期內(nèi)所有流共享位向量 A i。估計(jì)流持續(xù)性時(shí)為每個(gè)流f構(gòu)造一個(gè)虛擬位向量，構(gòu)造s個(gè)Hash函數(shù)，從位向量 A i中隨機(jī)均勻地選擇s位構(gòu)成虛擬位向量。因此，不需要為虛擬位向量分配額外存儲(chǔ)空間，相同時(shí)間槽內(nèi)屬于同一流的所有報(bào)文僅需更新位向量 A i中的一位。另外，兩個(gè)流的虛擬位向量可能共享位向量 A i中相同位，Hash沖突可能產(chǎn)生。然而，因?yàn)槊總€(gè)流的虛擬位向量中位是隨機(jī)選擇的，所以選擇不同位向量中任意兩位的概率是相同的。因此，通過概率統(tǒng)計(jì)方法可以估計(jì)產(chǎn)生的誤差，配置參數(shù)降低誤差，如m、s。

1.3 流處理

測(cè)量周期開始時(shí)，對(duì)位向量 A 、 A i（0 ≤ i ≤ k-1）進(jìn)行初始化。當(dāng)報(bào)文流Si到達(dá)監(jiān)測(cè)點(diǎn)i時(shí)，提取報(bào)文的源IP地址、目的IP地址、時(shí)間戳，分別表示為s、d、t，將時(shí)間戳轉(zhuǎn)換成相應(yīng)的時(shí)間槽，流標(biāo)識(shí)f表示（s， d），構(gòu)造向量（f， t），這里時(shí)間槽也用t表示。然后，計(jì)算哈希值h0（t），將位向量中第h0（t） mod s位設(shè)置為1，即：

A i[hh0（t） mod s（f）]=1; 0≤i≤k-1

當(dāng)測(cè)量周期結(jié)束時(shí)，主監(jiān)測(cè)點(diǎn)對(duì)來自其他監(jiān)測(cè)點(diǎn)的位向量 A i（0 ≤ i ≤ k-1）進(jìn)行按位或運(yùn)算，更新位向量 A ，即：

A [i]= A 0[i] ?|?? A 1[i] ?|? … ?|?? A k-1[i]; 0 ≤ i ≤ m-1

1.4 持續(xù)流檢測(cè)

當(dāng)用戶發(fā)送查詢請(qǐng)求時(shí)，首先需要估計(jì)流的持續(xù)性，然后進(jìn)行持續(xù)流檢測(cè)，對(duì)查詢請(qǐng)求進(jìn)行響應(yīng)。令Ci表示位向量 B （f）的第i位仍為0的隨機(jī)事件，當(dāng)Ci發(fā)生時(shí)，隨機(jī)變量1Ci的值為1，否則為0。Ci的發(fā)生由兩個(gè)因素決定：1）流f映射到位向量 B （f）的任意位的概率1/m;2）其他流映射到位向量 B （f）的任意位的概率1/s。因此，Ci發(fā)生的概率表示如式（3）：

P（Ci）=（1-1/m）n-k·（1-1/s）k; 0 ≤i≤s-1

（3）

其中：n表示測(cè)量周期內(nèi)所有流的持續(xù)性總和，k表示流f的持續(xù)性真實(shí)值。

令Vs表示位向量 B （f）中0的比例，Vs的數(shù)學(xué)期望表示如式（4）：

E[Vs]=E ∑ s-1 i=0? 1Ci s? = 1 s ·E [ ∑ s-1 i=0 P（Ci） ]

（4）

將式（3）代入式（4），得到式（5）：

E[Vs]≈e-n/m-k/s

（5）

因此，持續(xù)性的真實(shí)值k近似表示為式（6）：

k≈-s·n/m-s·lnE[Vs]

（6）

令Vm表示位向量 A 中0的比例，Vm的數(shù)學(xué)期望表示為式（7）：

E[Vm]= 1- 1 m? n≈e -n m

（7）

式（7）經(jīng)變換得到式（8）：

- n m =ln E[Vm]

（8）

將式（8）代入式（6），得到式（9）：

k=s·ln E[Vm]-s·E[ln Vs]

（9）

因此，持續(xù)性估計(jì)量表示為式（10）：

k?? ^?? =s·ln Vm-s·ln Vs

（10）

為了估計(jì)流f的持續(xù)性，根據(jù)式（10），需要統(tǒng)計(jì)位向量 A 、 B （f）中0的位數(shù)比例Vm、Vs。在此基礎(chǔ)上，進(jìn)行持續(xù)流的檢測(cè)。為了降低持續(xù)流的漏報(bào)率，即真實(shí)的持續(xù)流沒有被識(shí)別，持續(xù)性閾值設(shè)定為（1-ε），其中ε為誤差因子。如果流的持續(xù)性估計(jì)值大于（1-ε），那么該流被識(shí)別為持續(xù)流。

由于高速鏈路上海量網(wǎng)絡(luò)流量存在，需要大量存儲(chǔ)空間維護(hù)所有流。另一方面，通常流量流經(jīng)多個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)到達(dá)目的節(jié)點(diǎn)。為了能夠在網(wǎng)絡(luò)設(shè)備上及時(shí)準(zhǔn)確地檢測(cè)網(wǎng)絡(luò)攻擊行為，提出基于概要數(shù)據(jù)結(jié)構(gòu)的全網(wǎng)絡(luò)持續(xù)流檢測(cè)算法。該算法主要包括流處理和流持續(xù)性估計(jì)，僅涉及一些Hash計(jì)算和多次內(nèi)存訪問，計(jì)算復(fù)雜度為O（1）。概要數(shù)據(jù)結(jié)構(gòu)由一個(gè)大小為m的位向量構(gòu)成，為每個(gè)流構(gòu)造的虛擬位向量不占用存儲(chǔ)空間，空間復(fù)雜度為O（m）。通過分析發(fā)現(xiàn)持續(xù)性估計(jì)量是極大似然估計(jì)。因此，該算法能夠有效提取流的概要信息，同時(shí)保證一定的流持續(xù)性估計(jì)精度，滿足高速網(wǎng)絡(luò)流量監(jiān)測(cè)應(yīng)用需求。

2 實(shí)驗(yàn)分析

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

為了驗(yàn)證DPF方法的有效性，實(shí)驗(yàn)使用真實(shí)流量traces[19]，其采集于中國(guó)教育和科研計(jì)算機(jī)網(wǎng)的邊界路由器。所有報(bào)文經(jīng)過匿名化處理，僅包含首部信息。該流量traces持續(xù)3min，包含3102550個(gè)報(bào)文，41957個(gè)不同的源IP地址，45432個(gè)不同的目的IP地址，111958個(gè)不同流。實(shí)驗(yàn)通過多線程技術(shù)模擬多個(gè)監(jiān)測(cè)點(diǎn)，其中一個(gè)擔(dān)當(dāng)主監(jiān)測(cè)點(diǎn);時(shí)間槽為1s。圖2顯示了流持續(xù)性的分布，大約87%流的持續(xù)性小于10，大約0.5%流的持續(xù)性大于100，表明大部分流的持續(xù)性較小，少部分流的持續(xù)性較大。

從估計(jì)準(zhǔn)確性、檢測(cè)精度方面將DPF方法與相關(guān)方法TLF（Trace Long Flows）[3]、DLF（Detect Long Flows）[4]進(jìn)行比較。TLF算法使用兩個(gè)Bloom Filter數(shù)據(jù)結(jié)構(gòu)分別存儲(chǔ)過去和當(dāng)前時(shí)間區(qū)間內(nèi)候選的活躍長(zhǎng)持續(xù)時(shí)間流，使用Hash表存儲(chǔ)識(shí)別的長(zhǎng)持續(xù)時(shí)間流，通過抽樣過濾大部分短持續(xù)時(shí)間流，降低了存儲(chǔ)開銷，提高了識(shí)別精度。DLF算法使用計(jì)數(shù)Bloom Filter和Bloom Filter數(shù)據(jù)結(jié)構(gòu)，在測(cè)量時(shí)間周期內(nèi)更新計(jì)數(shù)Bloom Filter，測(cè)量時(shí)間周期結(jié)束后更新Bloom Filter，進(jìn)一步提高了識(shí)別精度。通過相對(duì)誤差評(píng)價(jià)持續(xù)性估計(jì)的準(zhǔn)確性，通過漏報(bào)率和誤報(bào)率評(píng)價(jià)持續(xù)流的檢測(cè)精度。在實(shí)驗(yàn)對(duì)比過程中，需要知道實(shí)際的持續(xù)流，表1顯示了不同閾值下實(shí)際的持續(xù)流，其中SIP（Source Internet Address）表示源IP地址，DIP（Destination Internet Address）表示目的IP地址。

2.2 估計(jì)準(zhǔn)確性

首先，分析持續(xù)性的估計(jì)誤差。通過相對(duì)誤差分析參數(shù)s對(duì)估計(jì)精度的影響。相對(duì)誤差定義如式（11）：

δ= ?| k?? ^?? -k | ?k ×100%

（11）

將式（10）代入式（11），并用E[Vm]、E[Vs]分別代替Vm、Vs，得到式（12）。

δ= | ln 1- 1 s? ·s-ln 1- 1 m? ·s-1 | ×100%

（12）

由圖3可知，當(dāng)m一定時(shí)，持續(xù)性估計(jì)的相對(duì)誤差隨著參數(shù)s的增加而降低，當(dāng)s > 50時(shí)，持續(xù)性估計(jì)的相對(duì)誤差δ小于1.0%。因此，通過調(diào)整參數(shù)s可以提高持續(xù)性估計(jì)的準(zhǔn)確性。

其次，比較三種方法的持續(xù)性估計(jì)值。由圖4可知，橫坐標(biāo)表示持續(xù)性的真實(shí)值，縱坐標(biāo)表示持續(xù)性的估計(jì)值，持續(xù)性估計(jì)值分布于對(duì)角線兩側(cè)。與其他兩種方法相比，通過DPF方法得到持續(xù)性估計(jì)值更接近對(duì)角線，表明DPF方法具有更高的估計(jì)準(zhǔn)確性，歸因于相等內(nèi)存下DPF方法的沖突率明顯低于其他兩種方法。

2.3 檢測(cè)精度

從誤報(bào)率和漏報(bào)率兩方面評(píng)價(jià)方法的檢測(cè)精度：誤報(bào)率fpr（false positive rate）指錯(cuò)誤識(shí)別的持續(xù)流在總識(shí)別的持續(xù)流中的比例;漏報(bào)率fnr（false negative rate）指沒有識(shí)別的持續(xù)流在實(shí)際持續(xù)流中的比例。因此，誤報(bào)率和漏報(bào)率定義如式（13）、式（14）：

fpr= | B-A | / | B |

（13）

fnr= | A-B | / | A |

（14）

其中：實(shí)際的持續(xù)流集合為A，總識(shí)別的持續(xù)流集合為B。

圖5顯示了三種方法在不同閾值下的誤報(bào)率和漏報(bào)率。由圖5可知，隨著閾值的增加，三種方法的誤報(bào)率和漏報(bào)率逐漸下降。然而，與其他兩種方法相比，DPF方法具有更低的誤報(bào)率和漏報(bào)率，表明它具有良好的檢測(cè)精度。

2.4 參數(shù)影響

從上述分析可知，位向量 B 的大小s是持續(xù)性估計(jì)的重要影響因素，因此，分析s對(duì)檢測(cè)精度的影響。圖6顯示了參數(shù)s與誤報(bào)率、漏報(bào)率之間的關(guān)系。由圖6可知，隨著s增加，誤報(bào)率、漏報(bào)率逐漸降低，表明s也是影響DPF方法檢測(cè)精度的重要參數(shù)。理論上，隨著參數(shù)s增加，DPF方法的檢測(cè)精度逐漸提高，可能導(dǎo)致時(shí)間復(fù)雜性增加和沖突率提高。在內(nèi)存一定的條件下，調(diào)整參數(shù)s，使得滿足持續(xù)流檢測(cè)精度要求。

Fig. 6 Influence of size s of bit vector ?B? on detection accuracy

3 結(jié)語

為了躲避檢測(cè)，網(wǎng)絡(luò)攻擊者在較長(zhǎng)周期內(nèi)有規(guī)律地發(fā)動(dòng)攻擊，導(dǎo)致傳統(tǒng)的檢測(cè)方法失效。針對(duì)負(fù)荷重、信息局限性以及網(wǎng)絡(luò)攻擊的隱蔽性，提出基于概要數(shù)據(jù)結(jié)構(gòu)的全網(wǎng)絡(luò)持續(xù)流檢測(cè)方法。首先，監(jiān)測(cè)點(diǎn)通過概要數(shù)據(jù)結(jié)構(gòu)提取網(wǎng)絡(luò)流的概要信息，測(cè)量周期結(jié)束時(shí)，主監(jiān)測(cè)點(diǎn)對(duì)來自其他監(jiān)測(cè)點(diǎn)的概要信息進(jìn)行綜合。然后，當(dāng)用戶發(fā)送查詢請(qǐng)求時(shí)，通過概率統(tǒng)計(jì)方法估計(jì)流的持續(xù)性，依據(jù)持續(xù)性估計(jì)檢測(cè)持續(xù)流。然而，全網(wǎng)絡(luò)持續(xù)流檢測(cè)方法只進(jìn)行了一些簡(jiǎn)單計(jì)算和內(nèi)存訪問操作。實(shí)驗(yàn)結(jié)果表明，與相關(guān)檢測(cè)方法相比，本文方法能夠有效地識(shí)別持續(xù)流，有助于檢測(cè)隱蔽的網(wǎng)絡(luò)攻擊。

參考文獻(xiàn)

[1]?趙小歡，夏靖波，付凱，等.高速網(wǎng)絡(luò)流頻繁項(xiàng)挖掘算法[J].計(jì)算機(jī)研究與發(fā)展，2014，51（11）：2458-2469. （ZHAO X H， XIA J B， FU K， et al. Frequent items mining algorithm over network flows at high-speed network [J]. Journal of Computer Research and Development， 2014， 51（11）： 2458-2469.）

[2]?LIU W， QU W， GONG J， et al. Detection of superpoints using a vector bloom filter [J]. IEEE Transactions on Information Forensics and Security， 2016， 11（3）： 514-527.

[3]?CHEN A， JIN Y， CAO J， et al. Tracking long duration flows in network traffic [C]// Proceedings of the 2010 International Conference on Information Communications. Piscataway， NJ： IEEE， 2010： 206-210.

[4]?LEE S， SHIN S， YOON M. Detecting long duration flows without false negatives [J]. IEICE Transactions on Communications， 2011， 94（5）： 1460-1462.

[5]?GIROIRE F， CHANDRASHEKAR J， TAFT N， et al. Exploiting temporal persistence to detect covert botnet channels [C]// Proceedings of the 2009 International Workshop on Recent Advances in Intrusion Detection， LNCS 5758. Berlin： Springer， 2009： 326-345.

[6]?HEULE S， NUNKESSER M， HALL A. HyperLogLog in practice： algorithmic engineering of a state of the art cardinality estimation algorithm [C]// Proceedings of the 16th International Conference on Extending Database Technology. New York： ACM， 2013： 683-692.

[7]??ZHOU Y， ZHOU Y， CHEN M， et al. Persistent spread measurement for big network data based on register intersection [J]. Proceedings of the ACM on Measurement and Analysis of Computing Systems， 2017， 1（1）： No.15.

[8]??XIAO Q， QIAO Y， ZHEN M， et al. Estimating the persistent? spreads in high-speed networks [C]// Proceedings of the 22nd IEEE International Conference on Network Protocols. Piscataway： IEEE， 2014： 131-142.

[9]?SHIN S， YOON M. Virtual vectors and network traffic analysis [J]. IEEE Network， 2012， 26（1）： 22-26.

[10]?LAHIRI B， CHANDRASHEKAR J， TIRTHAPURA S. Space-efficient tracking of persistent items in a massive data stream [C]// Proceedings of the 5th International Conference on Distributed Event-based System. New York： ACM， 2011： 255-266.

[11]?SINGH S A， TIRTHAPURA S. Monitoring persistent items in the union of distributed streams [J]. Journal of Parallel and Distributed Computing， 2014， 74（11）： 3115-3127.

[12]?DAI H， SHAHZAD M， LIU A X， et al. Finding persistent items in data streams [J]. Proceedings of the VLDB Endowment， 2016， 10（4）： 289-300.

[13]?STAN C， VARGHESE G， FISK M. Bitmap algorithms for counting active flows on high-speed links [J]. IEEE/ACM Transactions on Networking， 2006， 14（5）： 925-937.

[14]?KUMAR A， XU J， WANG J. Space-code bloom filter for efficient per-flow traffic measurement [J]. IEEE Journal on Selected Areas in Communications， 2006， 24（12）： 2327-2339.

[15]?CORMODE G， MUTHUKRISHNAN S. An improved data stream summary： the count-min sketch and its applications [J]. Journal of Algorithms， 2005， 55（1）： 58-75.

[16]?FLAJOLET P， FUSY ， GANDOUET O， et al. HyperLogLog： the analysis of a near-optimal cardinality estimation algorithm [J]. Discrete Mathematics and Theoretical Computer Science， 2007， 28（3）： 127-146.

http：//pdfs.semanticscholar.org/75ba/51ffd9d2bed8a65029c9340d058f587059da.pdf

[17]?HUANG Q， LEE P P C. A hybrid local and distributed sketching design for accurate scalable heavy key detection in network data streams [J]. Computer Networks： The International Journal of Computer and Telecommunications Networking， 2015， 91（C）： 298-315.

[18]?ANTUNES N， PIPIRAS V. Estimation of flow distributions from sampled traffic [J]. ACM Transactions on Modeling and Performance Evaluation of Computing Systems， 2016， 1（3）： No.17.

[19]?IP Trace And Service [DS/OL]. [2018-11-20]. http：//iptas.edu.cn/src/system.php.