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

1、隱超點(diǎn)是在一個(gè)測(cè)量區(qū)間內(nèi)鏈接了一定數(shù)量的源IP（宿IP）的宿IP（源IP）。在實(shí)際網(wǎng)絡(luò)中，對(duì)于隱超點(diǎn)的檢測(cè)往往很困難，因?yàn)槠鋳A雜在正常的流中，很容易避開(kāi)檢測(cè)系統(tǒng)。網(wǎng)絡(luò)中的一些安全事件，如溫和蠕蟲(chóng)病毒傳播、僵尸網(wǎng)絡(luò)掃描等都具有類似的行為特征，這些潛在的攻擊者在測(cè)量區(qū)間內(nèi)緩慢的向目的主機(jī)發(fā)送報(bào)文，這都屬于隱超點(diǎn)檢測(cè)問(wèn)題。
　　 盡管超點(diǎn)檢測(cè)技術(shù)已經(jīng)很成熟，但是這些算法對(duì)于隱超點(diǎn)的檢測(cè)很困難，因?yàn)槌c(diǎn)檢測(cè)技術(shù)關(guān)注的是大流。本文提出了兩

2、種隱超點(diǎn)檢測(cè)算法，均是基于Bitmap二維位數(shù)組，避開(kāi)了傳統(tǒng)超點(diǎn)檢測(cè)技術(shù)的弊端，其最主要優(yōu)點(diǎn)是:輕量級(jí)，可以運(yùn)行在速度快容量小的內(nèi)存中（如SRAM）。
　　 第一種檢測(cè)算法CBS算法的提出是為了使檢測(cè)算法應(yīng)用于實(shí)時(shí)網(wǎng)絡(luò)流檢測(cè)。該算法的核心是三個(gè)存儲(chǔ)主機(jī)流數(shù)的Bitmap二維位數(shù)組，在位數(shù)組的每一行加入一個(gè)行計(jì)數(shù)器，用于記錄本行中1的個(gè)數(shù)。算法包含4個(gè)哈希函數(shù)，將源IP及宿IP哈希映射到位數(shù)組中相應(yīng)的行列，進(jìn)行定位。對(duì)于每個(gè)到達(dá)的

3、報(bào)文，都要進(jìn)行更新位數(shù)組及行計(jì)數(shù)器操作，當(dāng)代表行的行計(jì)數(shù)器均大于給定閾值，則進(jìn)行統(tǒng)計(jì)處理。此算法簡(jiǎn)單且占用存儲(chǔ)空間較小，但是其準(zhǔn)確度有待提高。
　　 為了進(jìn)一步提高準(zhǔn)確度，本文又提出另一種檢測(cè)算法BS算法，用于離線統(tǒng)計(jì)隱超點(diǎn)，其核心是三個(gè)存儲(chǔ)主機(jī)流數(shù)的Bitmap二維位數(shù)組、以及存儲(chǔ)源IP及其基數(shù)的數(shù)組Cache。相比于CBS算法，BS算法準(zhǔn)確率較高但處理速度比較慢。
　　 本文對(duì)這兩種算法采用不同數(shù)據(jù)源的Trace進(jìn)行