一種基于fpga的報(bào)文內(nèi)容過濾算法

《一種基于fpga的報(bào)文內(nèi)容過濾算法》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。

1、一種基于FPGA的報(bào)文內(nèi)容過濾算法摘要報(bào)文內(nèi)容過濾技術(shù)是防火墻、入侵檢測(cè)系統(tǒng)和情報(bào)信息綜合系統(tǒng)的重要技術(shù)之一。本文提出的算法充分發(fā)揮了硬件并行運(yùn)算和流水線的優(yōu)勢(shì)，采用并行移位的匹配模塊結(jié)構(gòu)展寬了處理帶寬，使用BloomFilter技術(shù)加速自動(dòng)狀態(tài)機(jī)轉(zhuǎn)換，同時(shí)設(shè)計(jì)了高效的Hash硬件電路，提高了算法性能。實(shí)驗(yàn)證明該算法可以穩(wěn)定的過濾2.5Gbps的IP報(bào)文數(shù)據(jù)。關(guān)鍵字報(bào)文內(nèi)容過濾；FPGA；BloomFilter；自動(dòng)狀態(tài)機(jī)所謂報(bào)文內(nèi)容過濾，顧名思義是對(duì)IP包數(shù)據(jù)段的載荷進(jìn)行過濾，過濾規(guī)則是字符串形式的數(shù)據(jù)內(nèi)容。以ID

2、S系統(tǒng)為例，管理員根據(jù)所掌握的入侵情況事先為系統(tǒng)設(shè)定入侵規(guī)則，這些規(guī)則的一個(gè)重要組成部分就是IP數(shù)據(jù)載荷的某些內(nèi)容，具體表現(xiàn)為字符串。當(dāng)系統(tǒng)接收到一個(gè)IP包后，IDS的內(nèi)容過濾部分就會(huì)用自身的系統(tǒng)算法將規(guī)則庫中的字符串逐一和包的內(nèi)容匹配，一旦匹配了某個(gè)字符串，則證明匹配了相應(yīng)的規(guī)則。隨著網(wǎng)絡(luò)信息復(fù)雜化以及安全需求多樣化，對(duì)報(bào)文內(nèi)容過濾的需求也更加迫切。首先從安全角度來看，防火墻和入侵監(jiān)測(cè)系統(tǒng)急需高效率的報(bào)文內(nèi)容過濾算法。由于當(dāng)今的入侵行為和攻擊方式更具有復(fù)雜性，主要表現(xiàn)在數(shù)據(jù)載荷的內(nèi)容中出現(xiàn)特征字符串，例如蠕蟲病毒“

3、Nimda”、“CodeRed”、“Slammer”都包含特殊的字符串；從網(wǎng)絡(luò)應(yīng)用來看，應(yīng)用于深度報(bào)文分類的路由設(shè)備、流量控制等同樣需要獲得并且對(duì)IP數(shù)據(jù)內(nèi)容分類，例如一些多媒體數(shù)據(jù)、P2P數(shù)據(jù)都含有特定的字符串信息作為本身的標(biāo)識(shí)；另外從信息獲取的角度來看，技偵領(lǐng)域和數(shù)據(jù)挖掘如何從海量數(shù)據(jù)中發(fā)掘有用信息和情報(bào)資源，同樣需要內(nèi)容過濾。1內(nèi)容過濾的代表算法1.1AC算法AC算法即由Aho和Corasick提出的多模式匹配算法（即一次搜索查找可以判定多個(gè)字符串匹配問題）。簡(jiǎn)單地說，AC算法使用了有限自動(dòng)機(jī)的結(jié)構(gòu)來接收并存儲(chǔ)

4、規(guī)則庫中所有的字符串。自動(dòng)機(jī)是結(jié)構(gòu)化的，這樣每個(gè)前綴都可用唯一的狀態(tài)來標(biāo)識(shí)，甚至是那些多個(gè)模式的前綴，這樣復(fù)雜的前綴就可以簡(jiǎn)單的轉(zhuǎn)化為狀態(tài)機(jī)中的一個(gè)狀態(tài)。當(dāng)文本T中下一個(gè)字符不是模式中預(yù)期的下個(gè)字符中的一個(gè)時(shí)，會(huì)有一條失敗鏈指向那個(gè)狀態(tài)，代表最長的模式前綴，同時(shí)也是當(dāng)前狀態(tài)的相應(yīng)后綴。在實(shí)踐中，我們?cè)O(shè)定三個(gè)函數(shù)：狀態(tài)轉(zhuǎn)移函數(shù)goto（）、成功匹配輸出函數(shù)output（）、匹配失敗跳轉(zhuǎn)函數(shù)failure（）。1.2王的多模式匹配算法王永成教授等人設(shè)計(jì)了更多關(guān)注了多模式匹配過程中字串之間的相互關(guān)系，對(duì)AC算法進(jìn)行了改進(jìn)0

5、。算法在自動(dòng)狀態(tài)機(jī)思想的基礎(chǔ)上，應(yīng)用了BM算法0的跳轉(zhuǎn)思想，即利用了匹配過程中匹配失敗的信息，跳過盡可能多的字符。實(shí)現(xiàn)了快速的多模式匹配算法。在匹配的過程中，同樣使用goto（）函數(shù)轉(zhuǎn)移當(dāng)前狀態(tài)，在找到匹配結(jié)果之后output（）函數(shù)輸出成功信息。而在匹配失敗的時(shí)候，使用skip函數(shù)大幅度劃文本T，減少goto（）函數(shù)的調(diào)用次數(shù)，從而提高過濾效率。1.3BloomFilter算法BloomFilter法最初多用于數(shù)據(jù)庫存儲(chǔ)和查詢結(jié)構(gòu)，近年來也應(yīng)用于IP包內(nèi)容過濾等領(lǐng)域。BloomFilter算法的原理是找到k個(gè)has

6、h函數(shù)，其值域都是{1，2，…，m}同時(shí)設(shè)定一個(gè)模式矢量M，其長度為m。對(duì)于規(guī)則庫P中的每個(gè)模式，計(jì)算hash1（p）、……、hashk（p），每次計(jì)算所得的hashx（p）根據(jù)其數(shù)值對(duì)應(yīng)到模式矢量的相應(yīng)位置。這樣，一個(gè)模式經(jīng)過k個(gè)hash函數(shù)計(jì)算所得k個(gè)值，進(jìn)而對(duì)應(yīng)到模式矢量的k個(gè)位置，形成一個(gè)模式矢量。在查找的過程中，在文本中取出同p相同長度的字符串，經(jīng)過k個(gè)hash函數(shù)計(jì)算后生成其相應(yīng)的模式矢量，用這個(gè)模式矢量和庫中的各個(gè)模式矢量比較，可以確定是否匹配。1.4Dharmapurikar的算法Dharmapuri

7、kar等人修改了基本的AC算法，并引入了Bloomfilter，設(shè)計(jì)了基于硬件的匹配方案。該算法拓展了AC狀態(tài)機(jī)的輸入帶寬，從1byte擴(kuò)展到Gbyte。相應(yīng)的狀態(tài)機(jī)內(nèi)部對(duì)一個(gè)狀態(tài)變化也要判斷一組Gbyte的數(shù)據(jù)。而對(duì)于文本T尾部不足Gbyte的部分，采用并行的G-1個(gè)過濾單元，專用于過濾剩余長度為1、2、……、G-1的部分。而在狀態(tài)轉(zhuǎn)移的過程中，使用了BloomFilter過濾掉了不可能產(chǎn)生狀態(tài)轉(zhuǎn)移的輸入，極大地提高了匹配效率。而對(duì)于數(shù)量很少的狀態(tài)轉(zhuǎn)移操作，通過查找off-chip的存儲(chǔ)單元中的hash表來確定狀態(tài)

8、轉(zhuǎn)移和相應(yīng)的匹配結(jié)果。本文在此基礎(chǔ)上作進(jìn)一步研究。2內(nèi)容過濾算法描述2.1算法的并行結(jié)構(gòu)對(duì)于字符串匹配而言，一個(gè)匹配單元是1-byte，這樣一個(gè)匹配模塊一次的輸入為1byte。如果可以將輸入帶寬從1-byte拓展到G-byte的話那么過濾速率顯然也相應(yīng)的提高了G倍。圖1一個(gè)G=4的內(nèi)容過濾器圖1以一個(gè)G=4的實(shí)例說明了并行內(nèi)容過濾器的算法結(jié)構(gòu)。