[發(fā)明專利]一種索引拆分布魯姆過濾器及其插入、刪除和查詢方法

無效

• 申請?zhí)枺?/td>: 200910138248.3
• 申請日: 2009-05-08
• 公開（公告）號: CN101577721A
• 公開（公告）日: 2009-11-11
• 發(fā)明（設(shè)計）人: 張大方;黃昆
• 申請（專利權(quán)）人: 湖南大學
• 主分類號: H04L29/06
• 分類號: H04L29/06;H04L9/36
• 代理公司: 長沙正奇專利事務(wù)所有限責任公司
• 代理人: 馬 強

技術(shù)領(lǐng)域

本發(fā)明屬于高性能計算技術(shù)領(lǐng)域，具體是一種面向快速深度數(shù)據(jù)包檢測的索引拆分布魯姆過濾器及其插入、刪除和查詢方法。

背景技術(shù)

近年來，網(wǎng)絡(luò)蠕蟲、分布式拒絕服務(wù)、間諜軟件和計算機病毒等新型網(wǎng)絡(luò)攻擊不斷涌現(xiàn)，入侵計算機系統(tǒng)，竊取敏感信息，以及阻斷網(wǎng)絡(luò)關(guān)鍵服務(wù)等，從而威脅和破壞互聯(lián)網(wǎng)絡(luò)基礎(chǔ)設(shè)施。網(wǎng)絡(luò)入侵檢測系統(tǒng)(Network?IntrusionDetection?System，NIDS)和網(wǎng)絡(luò)入侵阻止系統(tǒng)(Nework?Intrusion?PreventionSystem，NIPS)是網(wǎng)絡(luò)攻擊防范的關(guān)鍵方法之一，即實時監(jiān)測網(wǎng)絡(luò)流量，檢查網(wǎng)絡(luò)可疑行為，并向系統(tǒng)管理員告警。深度數(shù)據(jù)包檢測(Deep?Packet?Inspection，DPI)是NIDS/NIPS的核心部件。與防火墻不同，DPI不僅檢查數(shù)據(jù)包頭部信息，而且檢查數(shù)據(jù)包有效載荷(即數(shù)據(jù)包內(nèi)容)。DPI采用特征匹配方法，將每個數(shù)據(jù)包內(nèi)容與一組預(yù)定義的攻擊特征進行匹配，從而識別出可疑行為。為了定義可疑行為，DPI采用一組規(guī)則描述攻擊特征，即每條規(guī)則包括數(shù)據(jù)包類型、特征字符串、搜索起始位置、以及匹配后的響應(yīng)操作等信息。因此，DPI是一種數(shù)據(jù)包內(nèi)容過濾技術(shù)，不僅應(yīng)用于NIDS/NIPS，而且應(yīng)用于Linux系統(tǒng)的應(yīng)用層數(shù)據(jù)包分類、P2P流量識別以及基于上下文的流量計費等。

隨著網(wǎng)絡(luò)帶寬和流量的迅猛增長，DPI將面臨高性能挑戰(zhàn)，即如何滿足數(shù)據(jù)包內(nèi)容過濾的時間需求和空間需求。首先，DPI是計算密集型操作，已成為NIDS/NIPS的性能瓶頸。通常，DPI應(yīng)用于互聯(lián)網(wǎng)絡(luò)的數(shù)據(jù)路徑上(例如出口鏈路上)，需要檢查海量數(shù)據(jù)包內(nèi)容的每個字節(jié)，并與成千上萬條規(guī)則進行特征匹配。例如，在Snort中，DPI占約70％的總執(zhí)行時間和約80％的總操作指令。因此，為了適應(yīng)高速網(wǎng)絡(luò)應(yīng)用，DPI必須滿足數(shù)據(jù)包內(nèi)容過濾的線速處理時間需求，即其吞吐量為10～40Gbps。其次，基于硬件的DPI面臨存儲空間受限的挑戰(zhàn)。由于基于軟件的DPI難以適應(yīng)高速數(shù)據(jù)包內(nèi)容過濾，研究者利用現(xiàn)代嵌入式存儲器技術(shù)，例如靜態(tài)隨機訪問存儲器(SRAM)、專用集成電路(ASIC)、現(xiàn)場可編程門陣列(FPGA)和三重內(nèi)容可尋址存儲器(TCAM)等，提出了基于硬件的DPI，支持線速的數(shù)據(jù)包內(nèi)容過濾，從而提高DPI的吞吐量。但是，隨著攻擊特征規(guī)則日益龐大，高速率、小容量的嵌入式存儲器難以滿足基于硬件的DPI的存儲空間需求。例如，Snort?2.7包含7840條特征規(guī)則，其存儲空間大小約為50MB；而Xilinx?Vertex-5FPGA最多包含288個片上存儲塊(每個存儲塊大小為36Kb)，僅提供約10Mb的片上存儲空間，難以存儲這些特征規(guī)則。因此，如何在存儲空間受限的條件下設(shè)計一種快速DPI是基于硬件的數(shù)據(jù)包內(nèi)容過濾技術(shù)的關(guān)鍵問題。

為了提高DPI的吞吐量和可伸縮性，Artan等人提出了一種特里位圖內(nèi)容分析器(Trie?Bitmap?Content?Analyzer，TriBiCa)，即在特里樹的每一層中，每個節(jié)點采用一個哈希函數(shù)將特征規(guī)則集均勻劃分成大小相等的兩個子集。實質(zhì)上，TriBiCa為特征規(guī)則集構(gòu)建一個最小完美哈希函數(shù)：當存儲特征規(guī)則x時，TriBiCa將x哈希映射到一個唯一的存儲位置，且不存在哈希沖突(Collision)，即多個特征規(guī)則哈希映射到同一個存儲位置；當查詢數(shù)據(jù)包內(nèi)容y時，TriBiCa檢查y是否在特征規(guī)則集中，并指出與y匹配的候選特征規(guī)則的存儲位置。為了提高DPI的吞吐量，TriBiCa的特里樹部署在高速率、小容量的片上存儲器上，而特征規(guī)則集存儲在低速率、大容量的片外存儲器上；在特征匹配之前，TriBiCa過濾掉大量不相關(guān)的數(shù)據(jù)包，并提供候選特征規(guī)則的存儲位置，從而減少片外存儲器訪問次數(shù)和特征匹配操作次數(shù)。但是，TriBiCa存在最小完美哈希函數(shù)構(gòu)建和更新開銷高以及假陽性存儲器訪問次數(shù)多等問題。首先，TriBica是計算密集型操作，即采用啟發(fā)式Blackjack算法和貪婪算法來構(gòu)建一個最小完美哈希函數(shù)。當特征規(guī)則不斷增多時，這些啟發(fā)式算法將導(dǎo)致TriBiCa的最小完美哈希函數(shù)構(gòu)建開銷高。其次，當插入或刪除特征規(guī)則時，TriBiCa離線地重新構(gòu)建一個最小完美哈希函數(shù)，難以適應(yīng)動態(tài)變化的特征規(guī)則集，從而導(dǎo)致其最小完美哈希函數(shù)更新開銷高；最后，在TriBiCa中，特里樹的每一層采用同一個哈希函數(shù)，導(dǎo)致其假陽性存儲器訪問次數(shù)多，即需要額外的片外存儲器訪問和特征匹配操作，從而限制了TriBiCa的吞吐量。