基于FM Sketch的超點(diǎn)檢測(cè)算法的研究.pdf

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

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

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