基于FM Sketch的超點檢測算法的研究.pdf

1、隨著計算機互聯(lián)網(wǎng)的蓬勃發(fā)展，網(wǎng)絡(luò)攻擊頻繁發(fā)生，如蠕蟲病毒、分布式拒絕服務(wù)攻擊(DDoS)、端口掃描等。這些攻擊事件在短時間內(nèi)產(chǎn)生大量的網(wǎng)絡(luò)鏈接，導(dǎo)致網(wǎng)絡(luò)堵塞甚至癱瘓。如掃描式蠕蟲在進行傳播時，其被感染主機通常在短時間內(nèi)向大量的其它主機發(fā)送報文。DDoS則是在短時間內(nèi)大量不同的主機向同一被攻擊主機發(fā)送報文。超點是在一段測量時間內(nèi)鏈接了大量不同目的主機的源主機。因此，實時識別超點對于網(wǎng)絡(luò)安全和管理有重要的意義。
　　本文將Flajol

2、et-Martin(FM)Sketch和IP地址搗碎技術(shù)應(yīng)用于超點檢測。FMSketch是一隨機化計數(shù)結(jié)構(gòu)，而IP地址搗碎使用一個哈希函數(shù)將32位的IP地址映射到長度為32位的比特位串中，并且該哈希函數(shù)是可逆的。以此為基礎(chǔ)提出了兩種超點檢測算法。第一種檢測算法使用5個二維位數(shù)組和6個哈希函數(shù)，前四個哈希函數(shù)選取源IP字符串的部分比特位作為哈希值，根據(jù)哈希函數(shù)的映射特性，利用選擇的哈希短串的重疊比特位還原出源IP字符串，不需要單獨的空間存

3、儲源IP，減少了讀取內(nèi)存的次數(shù)。該算法分為在線報文處理模塊和離線統(tǒng)計模塊。在線報文處理模塊使用哈希函數(shù)處理報文并更新位數(shù)組，離線統(tǒng)計模塊重建源IP字符串，使用FM Sketch估計超點基數(shù)并輸出超點信息。第二種超點檢測算法在第一種算法的基礎(chǔ)上加入IP地址搗碎技術(shù)，該算法的在線報文處理模塊首先搗碎報文的源IP地址，離線統(tǒng)計模塊使用搗碎技術(shù)將重建的源IP進行可逆變換。
　　在實驗中，使用從不同網(wǎng)絡(luò)中收集到的報文Trace進行實驗，使用