高速硬件字符串匹配算法的研究與實(shí)現(xiàn)

《高速硬件字符串匹配算法的研究與實(shí)現(xiàn)》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、分類號(hào)學(xué)校代碼10487學(xué)號(hào)611810200671379密級(jí)碩士學(xué)位論文高速硬件字符串匹配算法的研究與實(shí)現(xiàn)學(xué)位申請(qǐng)人：諶彤學(xué)科專業(yè)：通信與信息系統(tǒng)指導(dǎo)教師：劉威副教授答辯日期：2008年5月29日ADissertationSubmittedinPartialFulfillmentoftheRequirementsfortheDegreeofMasterofEngineeringResearchandImplementationofHighSpeedHardwareStringMatchingCandidate:ShenTongM

2、ajor:Communication&InformationSystemSupervisor:AssociateProf.LiuWeiHuazhongUniversityofScienceandTechnologyWuhan,Hubei430074,P.R.ChinaMay,2008獨(dú)創(chuàng)性聲明本人聲明所呈交的學(xué)位論文是我個(gè)人在導(dǎo)師的指導(dǎo)下進(jìn)行的研究工作及取得的研究成果。盡我所知，除文中已標(biāo)明引用的內(nèi)容外，本論文不包含任何其他人或集體已經(jīng)發(fā)表或撰寫過的研究成果。對(duì)本文的研究做出貢獻(xiàn)的個(gè)人和集體，均已在文中以明確方式標(biāo)明。本人完全意識(shí)

3、到本聲明的法律結(jié)果由本人承擔(dān)。學(xué)位論文作者簽名：日期：年月日學(xué)位論文版權(quán)使用授權(quán)書本學(xué)位論文作者完全了解學(xué)校有關(guān)保留、使用學(xué)位論文的規(guī)定，即：學(xué)校有權(quán)保留并向國(guó)家有關(guān)部門或機(jī)構(gòu)送交論文的復(fù)印件和電子版，允許論文被查閱和借閱。本人授權(quán)華中科技大學(xué)可以將本學(xué)位論文的全部或部分內(nèi)容編入有關(guān)數(shù)據(jù)庫(kù)進(jìn)行檢索，可以采用影印、縮印或掃描等復(fù)制手段保存和匯編本學(xué)位論文。保密□，在______年解密后適用本授權(quán)書。本論文屬于不保密√。（請(qǐng)?jiān)谝陨戏娇騼?nèi)打“√”）學(xué)位論文作者簽名：指導(dǎo)教師簽名：日期：年月日日期：年月日摘要字符串匹配

4、技術(shù)廣泛的應(yīng)用于各種網(wǎng)絡(luò)設(shè)備中，如基于策略的路由器、入侵檢測(cè)系統(tǒng)、網(wǎng)絡(luò)監(jiān)控系統(tǒng)、有質(zhì)量差別的服務(wù)和流分類計(jì)費(fèi)系統(tǒng)等。但是隨著互聯(lián)網(wǎng)的飛速發(fā)展和寬帶技術(shù)的不斷更新，目前的字符串匹配方式存在的不足暴露了出來，傳統(tǒng)設(shè)備多用軟件實(shí)現(xiàn)，處理能力有限，無法應(yīng)用在千兆、萬兆網(wǎng)絡(luò)中。字符串匹配的速度已經(jīng)成為諸如入侵檢測(cè)、流分類等設(shè)備發(fā)展的瓶頸。針對(duì)這些設(shè)備的高速字符串匹配硬件實(shí)現(xiàn)法已成為必要。本文針對(duì)入侵檢測(cè)和流分類兩類網(wǎng)絡(luò)設(shè)備提出各自適用的硬件字符串匹配算法。采取的研究方法：(1)分析入侵檢測(cè)系統(tǒng)和流分類系統(tǒng)的特征和需求；(2)針對(duì)這兩種應(yīng)用分別

5、提取對(duì)字符串匹配算法的要求；(3)針對(duì)算法要求和硬件特性設(shè)計(jì)兩種字符串匹配算法并實(shí)現(xiàn)；(4)在一個(gè)通用驗(yàn)證平臺(tái)上對(duì)這兩種實(shí)現(xiàn)進(jìn)行驗(yàn)證并跟現(xiàn)有設(shè)計(jì)進(jìn)行比較，體現(xiàn)這兩種算法的優(yōu)勢(shì)。在入侵檢測(cè)方面，本文提出了基于AC改進(jìn)算法的字符串匹配算法，可以對(duì)數(shù)據(jù)包進(jìn)行深度檢測(cè)。在流分類應(yīng)用方面，本文提出了一種BloomFilter的改進(jìn)算法，可以對(duì)應(yīng)用層協(xié)議進(jìn)行分類。前一種算法能夠在2.5G網(wǎng)絡(luò)環(huán)境下線速處理數(shù)據(jù)包，后一種算法能夠在10G網(wǎng)絡(luò)環(huán)境下線速的處理數(shù)據(jù)包，與傳統(tǒng)的軟件方法或者已有的硬件實(shí)現(xiàn)相比，提高了網(wǎng)絡(luò)設(shè)備的處理能力。本文的研究成果在F

6、PGA上進(jìn)行了實(shí)現(xiàn)，還可以很方便地集成到ASIC中。參考設(shè)計(jì)能夠處理相應(yīng)輸入帶寬下的網(wǎng)絡(luò)數(shù)據(jù)。關(guān)鍵詞：入侵檢測(cè)，數(shù)據(jù)包分類，字符串匹配，現(xiàn)場(chǎng)可編程邏輯陣列IAbstractStringMatchingMechanismiswidelyusedtovarietynetworkdevice,suchaspolicy-basedrouting,networkintrusiondetectionsystems(NIDS),networkmonitoringsystems,differentiatedqualitiesofserviceand

7、packetsclassificationandtrafficbillingsystems.WithfastdevelopmentoftheInternet,theweaknessofthepresentStringMatchingMechanismhasbeenexposed.Traditionaldevicesareusingsoftwarestringmatchingwhichhasalowmatchingability.AndtheycannotbeusedinGigabyteor10-Gigabytenetwork.The

8、speedofstringmatchhasbecomethefurtherdevelopmentbottleneckofthenetworkdevices,suchasintrusiondetectionandpacketclassi