盧來，鄧文，吳紹軍，黃錦煥

（廣東海洋大學(xué)寸金學(xué)院，湛江 524094）

0 引言

所謂高速網(wǎng)絡(luò)流的頻繁項數(shù)據(jù)挖掘是指在當前網(wǎng)絡(luò)中海量的數(shù)據(jù)流中找出頻率超出特定閾值的數(shù)據(jù)項。作為數(shù)據(jù)挖掘和數(shù)據(jù)流研究的重點工作，頻繁項挖掘不僅關(guān)系到計算機專家對網(wǎng)絡(luò)的管理，而且對于保障網(wǎng)絡(luò)安全也具有重要影響[1]。數(shù)據(jù)流中最為典型的模型為網(wǎng)絡(luò)流，對網(wǎng)絡(luò)流進行分析可知，其除了具有一般數(shù)據(jù)流的動態(tài)流動且無法重演以及因數(shù)據(jù)量過多而無法全部保存等特點外，還具有報文的傳輸速率極高以及以少數(shù)的流項便可承擔當前網(wǎng)絡(luò)中絕大多數(shù)荷載的特點?；谏鲜鎏攸c，對網(wǎng)絡(luò)流頻繁項進行挖掘?qū)τ诒Ｕ暇W(wǎng)絡(luò)安全、規(guī)范網(wǎng)絡(luò)管理具有重要的作用和意義。

本文通過提出一種基于時間與流長因素的網(wǎng)絡(luò)流頻繁項數(shù)據(jù)挖掘算法，即IWFIM，通過分析該方法的原理，進而提出了基于散列方法與計數(shù)方法二者優(yōu)點的CBF-IWFIM算法，進而對兩種算法對網(wǎng)絡(luò)流頻繁項的識別展開深入研究。

1 網(wǎng)絡(luò)流的特性分析

由于頻繁項算法的性能是由數(shù)據(jù)流的分布來直接決定的，而網(wǎng)絡(luò)流又是數(shù)據(jù)流的一種典型表現(xiàn)形式，故在進行頻繁項算法設(shè)計前，有必要對網(wǎng)絡(luò)流的特性展開分析。為了使所得網(wǎng)絡(luò)流的特性具有一般數(shù)據(jù)流的特點，將研究對象確定為選取骨干鏈路1999-03-21以及2009-03-30和2011-08-013組流量數(shù)據(jù)集，并以5元組方式將3組流量數(shù)據(jù)集的IP報文歸并成數(shù)據(jù)流，在各組中隨機選出10000條網(wǎng)絡(luò)流作為分析對象，研究其相關(guān)特性[2]。經(jīng)分析可知，網(wǎng)絡(luò)流的持續(xù)時間t與流長l無明顯現(xiàn)線性關(guān)系，而對于不同流長而言，其流的持續(xù)時間在分布上也較為分散。例如，橢圓區(qū)內(nèi)網(wǎng)絡(luò)流的持續(xù)時間不到整個網(wǎng)絡(luò)流測量周期的1/2，而處于橢圓區(qū)內(nèi)的網(wǎng)絡(luò)流在處于1/2以上測量周期中并未接收到相關(guān)的數(shù)據(jù)報文。而對于矩形區(qū)的網(wǎng)絡(luò)流而言，其流速雖然比較緩慢，但由于該部分流具有較長的持續(xù)時間，使得矩形區(qū)的網(wǎng)絡(luò)流會隨著持續(xù)時間的增加而逐漸成為大流。對上述橢圓區(qū)和矩形區(qū)的網(wǎng)絡(luò)流進行分析可知，雖然二者在整個測量周期中都具有相近的流長，但若設(shè)定具體的時間段，研究2中IP流在特定時間段內(nèi)的流長，將可能出現(xiàn)較大差異。由此可知，在對網(wǎng)絡(luò)流頻繁項的挖掘算法進行計算時，需要將流長、流的時間以及流速等方面因素進行綜合考慮。

2 IWFIM算法設(shè)計與分析

2.1 原理分析

對網(wǎng)絡(luò)流的特點進行分析可知，流長越大，則此流流長超過閾值進而成為網(wǎng)絡(luò)流頻繁項的可能性就越大。此外，區(qū)域內(nèi)，流的時間越新，在該流的最近一段時間中，其獲得網(wǎng)絡(luò)數(shù)據(jù)報文的可能性就越大[3]。以此為基礎(chǔ)，IWFIM將利用時時間與流長組合賦權(quán)的方法將每一個具體的流項賦權(quán)，而當當前網(wǎng)絡(luò)流中的緩存為100%并此時有新流進入時，IWFIM算法總是將當前具有最小權(quán)值的網(wǎng)絡(luò)流項。由于此時，數(shù)據(jù)流對計算機和當前網(wǎng)絡(luò)的緩存占用同收到報文的數(shù)量極為緊密，故本算法以達到的報文在整個網(wǎng)絡(luò)中的序號對網(wǎng)絡(luò)流的時間因素進行描述。

設(shè) IWFIM 中 F=＜ID，f，weight＞，其中 5 元組用 ID 來表示，f為網(wǎng)絡(luò)流F的長度，流的權(quán)值表示為weight[4]。需要說明的是weight為流長、時間分別為權(quán)重系數(shù)α與β的多項式之和，表示為weight=αf+βiF，式中，達到的報文在整個網(wǎng)絡(luò)中的序號為達到的報文在整個網(wǎng)絡(luò)中的序號為iF。若某一網(wǎng)絡(luò)流Fhit中已有報文Xhit抵達，則Fhit的流長與權(quán)重經(jīng)更新后表示如下：fhit=fhit+1，weight=αf+βi，（f=fhit）值得注意的是如果所抵達的報文Xhit并未命中網(wǎng)絡(luò)流頻繁項數(shù)據(jù)挖掘算法即IWFIM算法中的任何流，則應(yīng)新建流項 Fnew=＜IDhit，1，αf+βi＞。由于網(wǎng)絡(luò)流中的短流占據(jù)全部網(wǎng)絡(luò)流數(shù)的半數(shù)以上，故為了盡量避免后期所出現(xiàn)的某一單報文流便可將前期一個較大的流項淘汰的情況，有且僅有新流Fnew的權(quán)值超過IWFIM算法中緩存流的最小權(quán)值時，采用Fnew替換原IWFIM算法中緩存的最小權(quán)值流項[5]。

由于網(wǎng)絡(luò)流頻繁項的另一特點為不同流的持續(xù)時間也具有較大差異，且多半大流的持續(xù)時間較少（未達到整個測量周期的1/2），故此類流若在小于半個測量周期內(nèi)便結(jié)束，則在后半個測量周期內(nèi)，其權(quán)值始終保持不變。又由于后到達的新流Fnew初始權(quán)重的變化與其時間的變化呈現(xiàn)出顯著的正相關(guān)，即新流權(quán)重歲時間的延長而不斷增加[6]。因此，即便后期到達的新流流長較小，若流到達的時間間隔足夠大，后期到達的新流權(quán)值也將超過前半個測量周期中大流的權(quán)值，進而將其淘汰出流的緩存空間，故在利用IWFIM算法時，需要先對前期所識別出的大流進行保護。

2.2 算法分析

IWFIM將網(wǎng)絡(luò)中的全部緩存空間劃分為P與M，其中算法所識別出的頻繁項流以緩存P進行保存（初始值為0）。當緩存M中出現(xiàn)大于閾值的大流T流時，緩存P+1，M-1，并將T由M轉(zhuǎn)移到P中[7]。M緩存以時間與流長組合賦權(quán)的方式將網(wǎng)絡(luò)流中的頻繁項進行挖掘，緩存M每進行1次剪枝操作，便將權(quán)值最小的流項刪除。

對IWFIM算法的參數(shù)進行選擇如下：由于權(quán)值weight=αf+βi，對于同一個網(wǎng)絡(luò)流項而言，若α與β的取值不同，則該流的權(quán)值也有所不同，且IWFIM剪枝操作的順序也不完全相同。具體來說就是，α與β的取值會對IWFIM算法的性能產(chǎn)生直接影響，且此算法下剪枝操作的順序與各個流項的權(quán)值大小的排列次序相關(guān)聯(lián)，且與各流項的具體權(quán)值大小無關(guān)，這表示在IWFIM算法中，剪枝操作并不受α與β同時擴大或縮小相應(yīng)的倍數(shù)的影響[8]。由于在并不知曉網(wǎng)絡(luò)流量具體分布的前提下很難找到一個β值進而保證IWFIM算法所提取的網(wǎng)絡(luò)流頻繁項效果最好，故本文在確定β值方面采取一種啟發(fā)式的原理，利用網(wǎng)絡(luò)中新到流的權(quán)值要略大于各流項的平均權(quán)值。因此，新到的流總是可以替換出緩存內(nèi)具有較小平均流長的流。以l表示該算法的表項數(shù)量，若β=1/l，則新到流權(quán)值表示為weightnew=1+1/l，由此可知，新到流Fnew的權(quán)值weightnew要比平均流大，故能夠滿足要求，進而將參數(shù)β確定為β=1/l。

對此算法進行復(fù)雜度的分析如下：在IWFIM算法中如以散列的方法對報文的位置進行查找，則所查找報文的時間的復(fù)雜度和緩存P中網(wǎng)絡(luò)流更新的復(fù)雜度均為O（l）。此外，緩存M中命中流項權(quán)值時間及流長的復(fù)雜度也為O（l）。當緩存P與M中均未命中新到流項Fnew時，則需要從M中找出當前具有最小權(quán)值weightmin的流項，其時間的復(fù)雜度為 O（l2）[9]。由此可知，在IWFIM算法中，報文時間復(fù)雜度最差，即最復(fù)雜時為 O（l2），最優(yōu)為 O（1）。

3 CBF-IWFIM算法設(shè)計與分析

3.1 原理分析

由第2節(jié)可知，與流相比，網(wǎng)絡(luò)中的短流在總體的網(wǎng)絡(luò)流中占有極高的比例，而需要說明的是當網(wǎng)絡(luò)遭遇DDoS攻擊即分布式拒絕服務(wù)攻擊時，在較短的時間內(nèi)網(wǎng)絡(luò)中所出現(xiàn)的短流以急劇的速度增長，又由于以技術(shù)算法為主的頻繁項挖掘算法的每一個流項所占據(jù)的網(wǎng)絡(luò)緩存流量相同，故計數(shù)算法下的大部分流量都會被網(wǎng)絡(luò)中的短流占據(jù)[10]。因此，在大量短流存在于緩存區(qū)的情況下，將會對頻繁項挖掘算法的識別產(chǎn)生較大阻礙。綜上所述，在有限的緩存區(qū)中將網(wǎng)絡(luò)中的部分短流進行過濾，進而減少進入計數(shù)算法的流數(shù)，將會有效提高頻繁項挖掘效果。為此，本文引入CBFIWFIM算法，即基于計數(shù)型布魯姆過濾（CBF）的網(wǎng)絡(luò)流頻繁項挖掘算法（IWFIM）進而實現(xiàn)對網(wǎng)絡(luò)流頻繁項的挖掘工作。在將散列算法與計數(shù)算法各自優(yōu)勢進行有機結(jié)合的基礎(chǔ)上，通過借助散列的方法將當前網(wǎng)絡(luò)中需要進行頻繁挖掘的流項數(shù)目盡可能地減少，并以計數(shù)算法將IP流信息進行有效保存，從而使當前網(wǎng)絡(luò)中的部分短流因受到散列沖突而進入布魯姆過濾器CBF，并由IWFIM算法將其淘汰。CBF-IWFIM算法的原理圖如圖1所示。

圖1 CBF-IWFIM算法的原理圖

在應(yīng)用CBF-IWFIM算法時需要注意的是，因為網(wǎng)絡(luò)中的短流（流長小于16）占據(jù)總體流數(shù)量的半數(shù)以上的比例，故基于計數(shù)型的CBF中的每個計數(shù)器的閾值TCBF設(shè)置為15即可。當CBF中每個計數(shù)器的值L=TCBF時，則判定為該流項已經(jīng)通過CBF。又由于網(wǎng)絡(luò)流中存在相應(yīng)的散列沖突，故CBF的人過濾效果與其自身計數(shù)器的顯示值呈現(xiàn)出顯著的負相關(guān)關(guān)系，即過濾效果隨著計數(shù)器數(shù)值的增加而逐漸減少，當CBF中所顯示的計數(shù)器的值等于TCBF的NCBF的數(shù)量超過網(wǎng)絡(luò)中短流數(shù)量N0時，布魯姆過濾器將執(zhí)行剪枝操作，即過濾器中的全部非0值均在原有的基礎(chǔ)上減1。對于隨新到流項Fnew而抵達的新報文Xi而言，首先需對其位置進行判斷，并判斷Xi是否在IWFIM中，若是，則繼續(xù)利用IWFIM算法對Xi進行處理，若否，則通過CBF即布魯姆過濾器對Xi進行處理。

3.2 算法分析

對CBF進行分析可知，由于其無需將IP流的5元組進行保存，且對與其相關(guān)的指針信息也無需保存，又由于每個計數(shù)器設(shè)置為4b即可，故基于CBF的網(wǎng)絡(luò)流頻繁項具有較高的空間利用率。對其挖掘網(wǎng)絡(luò)頻繁項的時間復(fù)雜度進行分析可知，相較于單一的IWFIM算法，CBF-IWFIM算法對于網(wǎng)絡(luò)中不在IWFM的流項，還需添加計數(shù)器更新以及新的散列運算等相關(guān)操作，且操作時間的復(fù)雜度也大都為O（1），故在時間復(fù)雜度方面，兩種算法對于網(wǎng)絡(luò)頻繁項的數(shù)據(jù)挖掘較為相似。

對CBF過濾器對網(wǎng)絡(luò)中大流的影響做出如下分析。若在t時刻，CBF過濾器中有流項F通過，對于繼F后到達的報文Xi，只要其與流項F中的前一報文Xi-1到達的時間間隔處于CBF-IWFIM兩次剪枝操作的時間間隔之間，則對F本身進行分析可知，其存在著減1或不變兩種可能。值得注意的是，無論流項F自減1還是保持不變，在CBF過濾器執(zhí)行過濾操作后，均能夠使F所影射的CBF過濾器中的k個計數(shù)器的值為TCBF，而過濾操作被執(zhí)行的過程中，將不會對流項F的通過產(chǎn)生影響。由此可知，CBF-IWFIM算法對于網(wǎng)絡(luò)中大流通過所造成的影響是較為有限的。

對CBF過濾器對網(wǎng)絡(luò)中短流的影響做出如下分析。在忽略網(wǎng)絡(luò)流項的散列沖突的前提下，流長l＜TCBF的流項并不能通過CBF過濾器。而由3.1中CBFIWFIM的原理可知，即便在存在散列沖突的情況下，高速網(wǎng)絡(luò)中的短流通過了CBF過濾器，在IWFIM的作用下，其也會被立即淘汰，這也是CBF-IWFIM為什么不要求CBF過濾器將全部短流進行過濾的原因。而在網(wǎng)絡(luò)中短流未通過CBF過濾器或已通過過濾器的短流被IWFIM算法淘汰時，CBF-IWFIM通過對CBF過濾器中計數(shù)器值為TCBF的計數(shù)器數(shù)量NCBF進行限制，進而確保過濾器中所產(chǎn)生散列沖突的概率可以被限定在有限區(qū)間內(nèi)。由此可見，基于CBF-IWFIM的高速網(wǎng)絡(luò)的頻繁項數(shù)據(jù)挖掘算法可以即時過濾掉網(wǎng)絡(luò)中的短流。具體算法如下：

輸入：網(wǎng)絡(luò)報文{X1，X2...Xn}，Xi=＜IDx，i＞。輸入式中，報文Xi的5元組用IDx來表示，且Xi的序號用i來表示。

輸出：IWFIM算法中緩存P的所有流項。具體步驟為：（1）當Xi到達時，對5元組進行查找，并確定IWFIM中是否存在IDx、，若存在，則調(diào)用IWFIM算法對此報文進行處理，若不存在，則跳轉(zhuǎn)到下一步；（2）以散列算法將與5元組相對應(yīng)的布魯姆過濾器中的k個計數(shù)器計算出來，并對其中未達到TCBF的計數(shù)器加1，并對CBF中k個計數(shù)器的值是否均達到TCBF進行判斷，若為True，則CBF允許Xi通過，若為false，則轉(zhuǎn)入下一步；（3）對CBF中計數(shù)器的值為TCBF的數(shù)量NCBF進行統(tǒng)計，若其大于等于N0，則過濾器計數(shù)器的非0值均做減1操作，隨機結(jié)束此次循環(huán)并等待下一個報文Xi+1到來。

4 實驗分析與評價

4.1 實驗材料

本次實驗主要分為對數(shù)據(jù)的預(yù)處理以及頻繁項的挖掘兩方面。在數(shù)據(jù)的預(yù)處理方面，通過借助Plab開發(fā)包對網(wǎng)絡(luò)流長、網(wǎng)絡(luò)流的持續(xù)時間以及IP報文5元組等相關(guān)信息進行采集并記錄，進而將此階段所采集到的頻繁項與網(wǎng)絡(luò)流的流長共同作為算法效果的評估標準。在網(wǎng)絡(luò)流頻繁項的挖掘階段，通過利用數(shù)學(xué)軟件MATLAB在windows XP系統(tǒng)實現(xiàn)IWFIM與CBFIWFIM兩種算法。本次實驗所選取的網(wǎng)絡(luò)流數(shù)據(jù)集為CAIDA所提供的一條型號為OC48鏈路的網(wǎng)絡(luò)流量trace-2013與trace-2011。

4.2 基于IWFIM算法的參數(shù)設(shè)置

本次研究將網(wǎng)絡(luò)流頻繁項定義為出現(xiàn)頻次大于1000的IP流。設(shè)Nt與Nf分別為正確檢測出的大流數(shù)量與網(wǎng)絡(luò)中誤檢測的大流數(shù)量，由IWFIM算法所檢測出的大流流長于網(wǎng)絡(luò)中原流長之間差的絕對值同原流長之比的平均值為本次實驗的頻數(shù)均差率E。由3.1中所述的IWFIM原理可知，IWFIM算法并不會出現(xiàn)將網(wǎng)絡(luò)大流進行誤報的情況，故參數(shù)Nf=0。通過實驗可知，當表項數(shù)目l固定時，頻數(shù)均差率E與大流數(shù)量Nt則分別存在著極小值與極大值，以Nt為例，當表項數(shù)目l分別為 6000、8000、10000 時，Nt的極大值分別位于β=1/l、β=1/10000（但與（Nt1/l）相差僅為 5）和β=1/11000（但與（Nt1/l）相差僅為3）。而對于頻數(shù)均差率E而言，當l固定時，其具有較小的變化幅度，可忽略不計。由此可知，當表項數(shù)l固定時，IWFIM算法較為適合參數(shù)β=1/l的網(wǎng)絡(luò)流頻繁項的數(shù)據(jù)處理。

4.3 CBF-IWFIM算法的過濾效果分析

當利用CBF-IWFIM算法進行網(wǎng)絡(luò)流頻繁項挖掘時，將CBF中計數(shù)器的數(shù)量設(shè)置為N=214，并將4b設(shè)置成CBF計數(shù)器的位寬，設(shè)置散列函數(shù)數(shù)目k=3，N0=N/4，TCBF=15。將 CBF-IWFIM的表項數(shù)目l設(shè)置為10000，β=1/l。需要說明的是，由于在IWFIM算法中，每個網(wǎng)絡(luò)流表項需要對流技術(shù)器、流指針以及IP5元組等信息進行保存。將每個流表項位寬設(shè)置為200b，則對CBF過濾器進行分析可知，過濾器占用的位寬不足500b。由此可知，CBF具有較高的空間利用率。

表1給出了CBF算法的原始流量信息以及到達IWFIM信息模塊中的流量信息對比情況。

在實驗過程中，通過對CBF-IWFIM算法的頻繁項挖掘信息與IWFM算法的模塊流量信息進行比較，進而得出CBF具有較好過濾效果的結(jié)論，進而說明了基于CBF-IWFIM的高速網(wǎng)絡(luò)流頻繁項數(shù)據(jù)挖掘算法可以在確保大多數(shù)網(wǎng)絡(luò)報文得以正常通過的前提下，使IWFIM的表項數(shù)發(fā)生變化，即降低一個數(shù)量級，表明CBF可將網(wǎng)絡(luò)中絕大多數(shù)的短流進行過濾，從而降低對計數(shù)算法處理的壓力，并提高CBF-IWFIM中計數(shù)算法的頻繁項挖掘效果。

5 結(jié)語

本文通過對高速網(wǎng)絡(luò)流頻繁項數(shù)據(jù)挖掘的概念進行闡述，在結(jié)合網(wǎng)絡(luò)流的特性進行分析的基礎(chǔ)上，從網(wǎng)絡(luò)流頻繁項數(shù)據(jù)挖掘的IWFIM算法與CBF-IWFIM算法兩方面對其在高速網(wǎng)絡(luò)流頻繁項數(shù)據(jù)挖掘中的應(yīng)用展開了實驗分析。由本次實驗可知，IWFIM所采用的流長與時間組合賦權(quán)值的方式實際上是對網(wǎng)絡(luò)中的每個流項賦權(quán)，且在此算法下每次進行剪枝操作時，總是將具有最小權(quán)值的流項進行刪除。而CBF-IWFIM算法所改進的布魯姆過濾器將網(wǎng)絡(luò)中的絕大多數(shù)的短流進行過濾，隨后再采用IWFIM算法實現(xiàn)頻繁項的數(shù)據(jù)挖掘。通過本次實驗表明，IWFIM與CBF-IWFIM算法在告訴網(wǎng)絡(luò)流頻繁項數(shù)據(jù)挖掘計算方面均具有良好效果，且與IWFIM算法相比，CBF-IWFIM算法的空間利用率更高?？梢?，未來加強對挖掘算法在高速網(wǎng)絡(luò)流頻繁項計算中的應(yīng)用研究對于保障網(wǎng)絡(luò)安全提高網(wǎng)絡(luò)管理效率具有重要的歷史作用和現(xiàn)實意義。

表1 CBF-IWFIM過濾算法中CBF的過濾效果