利用抽樣技術(shù)和分層多哈希方法實(shí)現(xiàn)長(zhǎng)流的識(shí)別

景泉

摘要：本文提出了一種利用抽樣技術(shù)和分層多哈希的方法來(lái)識(shí)別長(zhǎng)流，選取合適的哈希函數(shù)，能夠方便還原出五元組信息，減少了資源的開(kāi)銷(xiāo);使用多哈希函數(shù)，可以極大的降低哈希沖突，保證數(shù)據(jù)的準(zhǔn)確性。

關(guān)鍵詞：抽樣技術(shù);分層多哈希

中圖分類(lèi)號(hào)：TP393.08 文獻(xiàn)識(shí)別碼：A 文章編號(hào)：1001-828X（2016）005-000-01

隨著互聯(lián)網(wǎng)規(guī)模和用戶(hù)數(shù)量的迅速擴(kuò)大，導(dǎo)致網(wǎng)絡(luò)流量不斷增大，網(wǎng)絡(luò)行為越劇復(fù)雜，安全攻擊的頻率和對(duì)網(wǎng)絡(luò)造成的破壞性也在急劇的增長(zhǎng)。為了更好的保障網(wǎng)絡(luò)安全，需要對(duì)網(wǎng)絡(luò)流量進(jìn)行有效的監(jiān)測(cè)和分析。現(xiàn)代網(wǎng)絡(luò)面臨的又一緊迫任務(wù)是為用戶(hù)提供可靠的業(yè)務(wù)質(zhì)量保障。而用戶(hù)獲得的服務(wù)質(zhì)量以及網(wǎng)絡(luò)供應(yīng)商可提供的服務(wù)能力都必須通過(guò)流量數(shù)據(jù)分析獲得。因此，研究網(wǎng)絡(luò)流量特性是改善網(wǎng)絡(luò)服務(wù)質(zhì)量問(wèn)題的一個(gè)關(guān)鍵。而網(wǎng)絡(luò)流量測(cè)量技術(shù)是目前唯一能用于分析網(wǎng)絡(luò)狀況、掌握流量特性的有效方法。

一、國(guó)內(nèi)外研究概況、水平和發(fā)展趨勢(shì)

Cristian Estan在長(zhǎng)流識(shí)別的過(guò)程中就提出了一種抽樣技術(shù)和哈希技術(shù)結(jié)合的算法——sample and hold算法。sample and hold 算法是按照一定的概率對(duì)字節(jié)進(jìn)行抽樣，如果一個(gè)報(bào)文被抽到，且其所屬的流標(biāo)識(shí)未被創(chuàng)建，則以概率P創(chuàng)建這個(gè)流標(biāo)識(shí);而一個(gè)流的標(biāo)識(shí)在內(nèi)存中已經(jīng)存在，則更新屬于該流標(biāo)識(shí)的報(bào)文的記錄。這種方法可以較精確地識(shí)別長(zhǎng)流，所用的內(nèi)存空間也較小，但它對(duì)每個(gè)報(bào)文進(jìn)行處理的同時(shí)都要訪(fǎng)問(wèn)內(nèi)存，因此要求內(nèi)存的速度達(dá)到線(xiàn)速，給測(cè)量系統(tǒng)帶來(lái)很大的壓力。同時(shí)哈希的過(guò)程中也會(huì)造成一定的沖突，導(dǎo)致一定的誤差。并且在哈希的過(guò)程中還要記錄流標(biāo)識(shí)的信息，會(huì)帶來(lái)存儲(chǔ)空間的增加。

國(guó)內(nèi)的網(wǎng)絡(luò)測(cè)量研究起步較晚，近年研究網(wǎng)絡(luò)行為學(xué)逐步增加。長(zhǎng)流占據(jù)了大部分的網(wǎng)絡(luò)通信量，了解長(zhǎng)流的信息就能對(duì)一次通信行為有著很好的描述。長(zhǎng)流識(shí)別在網(wǎng)絡(luò)測(cè)量領(lǐng)域也有很大的研究，提出了多種識(shí)別長(zhǎng)流的方法。

二、識(shí)別過(guò)程

（一）分層隨機(jī)抽樣

分層隨機(jī)抽樣：如果每層中的抽樣都是獨(dú)立地按照簡(jiǎn)單隨機(jī)抽樣進(jìn)行的，那么這樣的抽樣稱(chēng)為分層隨機(jī)抽樣，所得的樣本稱(chēng)為分層隨機(jī)樣本。

分層隨機(jī)抽樣由于抽樣在每一層中獨(dú)立進(jìn)行，所以各層的數(shù)據(jù)可以用于對(duì)本層（子總體）進(jìn)行較精確的參數(shù)估計(jì)，然后將這些總和全部累加，就能得到對(duì)總體的一個(gè)較精確的參數(shù)估計(jì)。使用分層隨機(jī)抽樣可使樣本中分布更加均勻，從而具有更好的代表性。這樣就避免了樣本分布不平衡的現(xiàn)象。

（二）Bloom Filter的使用

Bloom Filter最早由Burton Bloom提出，并開(kāi)始廣泛的應(yīng)用到數(shù)據(jù)庫(kù)領(lǐng)域中，最近在網(wǎng)絡(luò)研究中得到了廣泛的應(yīng)用，并取得了一些進(jìn)展。如在高速網(wǎng)絡(luò)測(cè)量方面。

Bloom Filter是一個(gè)基于多個(gè)哈希函數(shù)映射來(lái)壓縮參數(shù)空間的數(shù)據(jù)結(jié)構(gòu)，它支持成員查詢(xún)、隨機(jī)存儲(chǔ)。其具體的工作原理是，它描述了一個(gè)源串的集合S={x1， x2…， xn}，我們把xi稱(chēng)作是一個(gè)源串。申請(qǐng)一個(gè)內(nèi)存大小為m比特位的存儲(chǔ)空間A，并定義一個(gè)哈希函數(shù)集合H={H1， H2，…， Hk}，我們把Hi稱(chēng)作是一個(gè)哈希函數(shù)。對(duì)于源串集合S中的任何一個(gè)元素xi來(lái)說(shuō)，通過(guò)集合H中的K個(gè)獨(dú)立的哈希函數(shù)映射到存儲(chǔ)空間A中，得到K個(gè)[1…m]之間的數(shù)，并把存儲(chǔ)空間A中的這K個(gè)對(duì)應(yīng)比特位置1。也可以利用哈希函數(shù)集合H的映射過(guò)程來(lái)檢驗(yàn) 是否屬于集合S。下面的兩個(gè)算法分別描述了源串集合S中的元素被哈希到存儲(chǔ)空間的過(guò)程和驗(yàn)證給定元素 是否屬于源串集合S的過(guò)程。

（三） 閾值的確定

識(shí)別長(zhǎng)流的第一步就是要確定閾值。中給出了兩種確定閾值的辦法。第一種方法是考慮到收集的數(shù)據(jù)集合存在著重尾分布的特征。第二種方法更加的直接。閾值的確定會(huì)考慮到操作的環(huán)境。它要求計(jì)算一個(gè)參數(shù)，這個(gè)參數(shù)與總通信量有著密切的關(guān)系。利用這一參數(shù)可以把流分為兩類(lèi)：一類(lèi)就是超出了這個(gè)參數(shù)值，我們這一類(lèi)的流定義為長(zhǎng)流。另一類(lèi)是沒(méi)有超過(guò)這個(gè)參數(shù)值，就把它們定義為短流。

本文采用的確定閾值的方法類(lèi)似第二種辦法。即在測(cè)量的過(guò)程中利用一個(gè)計(jì)數(shù)器記錄總的報(bào)文數(shù)，設(shè)為M。我們約定把占據(jù)報(bào)文總數(shù)1%以上的流記為長(zhǎng)流，則閾值T=M/100。在測(cè)量結(jié)束后，Bloom Filter中具有相同流標(biāo)識(shí)的報(bào)文的命中次數(shù)如果超出了T值，就把這個(gè)流識(shí)別出來(lái)。

然后，我們要在測(cè)量的時(shí)間內(nèi)選用簡(jiǎn)單的哈希函數(shù)對(duì)到來(lái)的報(bào)文按照?qǐng)?bào)文頭中的流標(biāo)識(shí)分組，并對(duì)分組后的流標(biāo)識(shí)進(jìn)行Counting Bloom Filter變換。測(cè)量結(jié)束后，利用第二部分中所介紹的長(zhǎng)流的定義，對(duì)每個(gè)哈?？臻g中的命中次數(shù)加以統(tǒng)計(jì)，把超出閾值的流識(shí)別出來(lái)，并存儲(chǔ)在存儲(chǔ)器中。我們利用段地址重疊的比特還原出主機(jī)的原始信息。中指出活躍IP分布是非常不均勻的重尾分布，相鄰網(wǎng)段或者IP活躍度較大。但是他們的活躍度相差較大不會(huì)影響我們分析的結(jié)論，我們可以用短標(biāo)簽重疊的比特進(jìn)行糾正。

（四）識(shí)別的基本步驟

1.構(gòu)建一個(gè)多哈希站的模塊，每個(gè)哈希站都存放一個(gè)獨(dú)立的哈希函數(shù)

2.利用分層哈希方法依次哈希到對(duì)應(yīng)的存儲(chǔ)空間

3.統(tǒng)計(jì)在某一時(shí)間粒度下總的報(bào)文數(shù)，并計(jì)算閾值。

4.對(duì)TCP的五元組進(jìn)行Counting Bloom Filter變換。

5.統(tǒng)計(jì)每個(gè)流的報(bào)文數(shù)，把超過(guò)閾值的流記錄下來(lái)。

6.對(duì)記錄下的長(zhǎng)流進(jìn)行原始信息的還原。

圖1利用Counting Bloom Filter進(jìn)行長(zhǎng)流識(shí)別的過(guò)程。結(jié)構(gòu)體BF由兩個(gè)成員組成。分別攜帶了主機(jī)原始信息和經(jīng)過(guò)哈希函數(shù)作用后所命中該存儲(chǔ)空間中的報(bào)文數(shù)。圖中把IP地址分為三段，每一段都維護(hù)一個(gè)相應(yīng)的Bloom Filter數(shù)據(jù)結(jié)構(gòu)。把超出閾值的信息存儲(chǔ)在存儲(chǔ)器中。

圖1 ?利用Counting Bloom Filter進(jìn)行長(zhǎng)流識(shí)別的過(guò)程

三、結(jié)論

本文使用抽樣技術(shù)和分層多哈希方法實(shí)現(xiàn)了長(zhǎng)流的識(shí)別，利用Bloom Filter這種數(shù)據(jù)結(jié)構(gòu)在識(shí)別長(zhǎng)流的過(guò)程中可以不用維護(hù)五元組信息，降低了在維護(hù)五元組信息的過(guò)程中帶來(lái)的資源的開(kāi)銷(xiāo)。經(jīng)數(shù)據(jù)測(cè)試，本文提出的識(shí)別長(zhǎng)流的算法在識(shí)別長(zhǎng)流的同時(shí)，可以還原成五元組信息，使用多哈?？梢越档蜎_突，保證數(shù)據(jù)的準(zhǔn)確性。

參考文獻(xiàn)：

[1] Veru Paxson，Jamshid Mahdavi. Scale Internet measurement[J].IEEE Communications，1998， 36（8）：48-54.

[2]彭艷兵，龔儉，劉衛(wèi)江，等. Bloom Filter哈?？臻g的元素還原[J]. 電子學(xué)報(bào)，2006，34（5）：822-827.

[3]龔儉，彭艷兵，楊望，等.基于Bloom Filter的大規(guī)模異常TCP連接參數(shù)再現(xiàn)方法[J].軟件學(xué)報(bào)， 2006，17（3）：434-444.