發(fā)布時間：2019-07-11 16:18

【摘要】：隨著網(wǎng)絡(luò)的迅猛發(fā)展，網(wǎng)絡(luò)安全的重要性也日益凸顯，對網(wǎng)絡(luò)內(nèi)容的檢測成為網(wǎng)絡(luò)安全體系中不可或缺的一部分。海量數(shù)據(jù)的處理和層出不窮的應(yīng)用需求使網(wǎng)絡(luò)內(nèi)容檢測技術(shù)面臨著嚴(yán)峻的挑戰(zhàn)，而字符串匹配算法正是網(wǎng)絡(luò)內(nèi)容檢測的核心技術(shù)，因此，提高串匹配算法的性能至關(guān)重要。而傳統(tǒng)的以串行方式執(zhí)行的串匹配算法的性能難以滿足日益增長的網(wǎng)絡(luò)需求，用并行代替串行成為解決問題的關(guān)鍵。隨著GPU (Graphic Processing Unit?圖形處理單兀）、TCAM (TernaryContent Addressable Memory，三元內(nèi)容可尋址存儲器）、FPGA (FieldProgrammable Gate Array*現(xiàn)場可編程門陣列）和Bloom filter等硬件的興起和發(fā)展，基于硬件的并行算法成為了研究的熱點。同時，由于NVIDIAGPU具有成本低和高吞吐量的特點，成為了高性能并行計算的新生力量。 本文分別介紹了基于軟件和硬件實現(xiàn)的并行串匹配算法，深入分析了基于GPU、TCAM、FPGA和Bloomfilter等硬件的并行串匹配算法的基本理論�；贕PU的高性能并行架構(gòu)，把經(jīng)典的AC (Aho-Corasick)算法移植到GPU平臺上進(jìn)行加速，設(shè)計并實現(xiàn)了數(shù)據(jù)并行的PAC (Parallel Algorithm based on AC)算法。PAC算法的預(yù)處理部分在CPU上串行執(zhí)行，模式匹配部分交由GPU并行處理，將數(shù)據(jù)集分塊，GPU的每個線程處理一個數(shù)據(jù)塊，進(jìn)行模式匹配。但是，PAC算法需要進(jìn)行“邊界檢測”，降低了算法的性能。 為了消除PAC算法在內(nèi)的數(shù)據(jù)并行算法存在的“邊界檢測”問題，本文提出了一種新穎的并行串匹配算法PAT (Parallel Algorithm based on Trie),該算法的設(shè)計也是本文的創(chuàng)新點。移除AC自動機(jī)的所有失效轉(zhuǎn)移和初始狀態(tài)的自循環(huán)轉(zhuǎn)移，得到一棵Trie樹，稱之為PAT自動機(jī)，為輸入數(shù)據(jù)的每個字符分配一個線程，搜索PAT自動機(jī)完成模式匹配。重點研究了PAT算法的實現(xiàn)以及GPU實現(xiàn)上的優(yōu)勢，并提出了算法的優(yōu)化策略，包括減少GPU全局存儲器的內(nèi)存處理、消除輸出表的訪問和減小狀態(tài)轉(zhuǎn)移表查找的延遲。 通過實驗得出，在NVIDIA GPU G94上實現(xiàn)的PAC和PAT算法與AC算法相比，分別達(dá)到了4.75和8.43的加速比。通過GPU的加速技術(shù)，大大提高了字符串匹配算法的性能，并且PAT算法在GPU實現(xiàn)上獲得了更優(yōu)的性能。
文內(nèi)圖片：
圖片說明： 對于串匹配問題的實現(xiàn)也可分為兩個方面，單純基于軟件的實現(xiàn)和基于的實現(xiàn)。絕大多數(shù)的串匹配算法采用串行方式執(zhí)行，稱為串行的串匹配算法于算法本身的特性，如位并行算法，或者借助硬件實現(xiàn)，，如多核或基于 G實現(xiàn)，這種以并行方式執(zhí)行的算法，稱為并行的串匹配算法。字符串匹配問分類如圖 1-1 所示，該圖主要體現(xiàn)了精確匹配的部分。
文內(nèi)圖片：
圖片說明： 最簡單的字符串匹配算法。首先比較文本串的第一個字符與模式串的第一個字符，如果相等，繼續(xù)比較文本串的第二個字符和模式串的第二個字符，否則，比較文本串的第二個字符與模式串的第一個字符是否相等，以此類推，直到得出最后的匹配結(jié)果。圖 1-2 用一個例子展示了 BF 算法的匹配過程。其中文本為“ababcabcac”，模式串為“abcac”，“X”代表不匹配。
【學(xué)位授予單位】：哈爾濱工業(yè)大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2014
【分類號】：TP393.08

【共引文獻(xiàn)】

相關(guān)期刊論文 前10條

1 艾鑫;田志宏;張宏莉;;深度包檢測技術(shù)中多模式匹配算法研究[J];智能計算機(jī)與應(yīng)用;2013年05期

2 石金龍;孫翼;;基于Libnids庫的Internet網(wǎng)絡(luò)協(xié)議還原系統(tǒng)研究[J];電子技術(shù);2014年03期

3 劉鷹;;基于局部最大相似設(shè)想的串匹配算法[J];電子設(shè)計工程;2014年14期

4 蔡恒;張帥;;基于BF算法改進(jìn)的字符串模式匹配算法[J];電腦編程技巧與維護(hù);2014年22期

5 王開云;孔思淇;付云生;潘澤友;馬衛(wèi)東;趙強(qiáng);;兩種基于雙向比較的最長公共子串算法[J];計算機(jī)研究與發(fā)展;2013年11期

6 楊子江;聶瑞華;;一種快速的單模式匹配算法[J];華南師范大學(xué)學(xué)報(自然科學(xué)版);2013年05期

7 侯整風(fēng);楊波;朱曉玲;;一種適合中文的多模式匹配算法[J];計算機(jī)科學(xué);2013年11期

8 李志文;張偉;;一種面向大規(guī)模短特征集的字符串匹配技術(shù)[J];計算機(jī)工程與應(yīng)用;2014年01期

9 燕紅文;楊懷卿;;WM與MWM算法分析[J];農(nóng)業(yè)網(wǎng)絡(luò)信息;2013年12期

10 馬占飛;楊樹英;郭廣豐;;一種快速的基于BM模式匹配的改進(jìn)算法[J];控制與決策;2013年12期

相關(guān)會議論文 前1條

1 李天磊;馬兆豐;;應(yīng)用層協(xié)議識別中AC算法的改進(jìn)[A];第十九屆全國青年通信學(xué)術(shù)年會論文集[C];2014年

相關(guān)博士學(xué)位論文 前5條

1 李丹;基于流聚類的網(wǎng)絡(luò)業(yè)務(wù)識別關(guān)鍵技術(shù)研究[D];北京郵電大學(xué);2013年

2 劉應(yīng)玲;帶可變長度通配符的模式匹配算法研究[D];合肥工業(yè)大學(xué);2014年

3 馬冬;網(wǎng)絡(luò)威脅檢測與態(tài)勢預(yù)測關(guān)鍵技術(shù)研究[D];國防科學(xué)技術(shù)大學(xué);2013年

4 張麗果;路由器SoC系統(tǒng)架構(gòu)的研究與設(shè)計[D];西安電子科技大學(xué);2014年

5 楊天龍;面向網(wǎng)絡(luò)入侵檢測的串匹配算法優(yōu)化[D];哈爾濱工業(yè)大學(xué);2014年

相關(guān)碩士學(xué)位論文 前10條

1 潘冠樺;單模式字符串匹配算法效率的研究[D];太原理工大學(xué);2013年

2 馬曉文;帶通配符的多序列模式挖掘研究[D];合肥工業(yè)大學(xué);2013年

3 楊波;基于有限狀態(tài)自動機(jī)的中文多模式匹配算法研究[D];合肥工業(yè)大學(xué);2013年

4 范宇健;大流量網(wǎng)絡(luò)下串匹配算法的優(yōu)化研究[D];哈爾濱工業(yè)大學(xué);2013年

5 胡浩南;基于入侵檢測系統(tǒng)的單模式匹配算法的研究[D];江西理工大學(xué);2013年

6 曹曉龍;千萬模式集高效匹配算法的研究與實現(xiàn)[D];哈爾濱工業(yè)大學(xué);2012年

7 劉益銘;基于網(wǎng)關(guān)的統(tǒng)計波形數(shù)據(jù)包分類研究[D];哈爾濱工業(yè)大學(xué);2012年

8 王海強(qiáng);非精確深度包檢測技術(shù)研究[D];哈爾濱工業(yè)大學(xué);2013年

9 艾鑫;眾核環(huán)境下深度包檢測系統(tǒng)的設(shè)計與優(yōu)化[D];哈爾濱工業(yè)大學(xué);2013年

10 張興彪;海量多模式串匹配算法關(guān)鍵技術(shù)研究[D];哈爾濱工程大學(xué);2013年

本文編號：2513295