正則表達(dá)式匹配是網(wǎng)絡(luò)內(nèi)容分析與過濾系統(tǒng)中的核心關(guān)鍵技術(shù)。隨著互聯(lián)網(wǎng)技術(shù)的快速發(fā)展,新型網(wǎng)絡(luò)應(yīng)用和協(xié)議不斷涌現(xiàn),待檢測數(shù)據(jù)量急遽增長,檢測規(guī)則數(shù)量龐大且語法日益復(fù)雜,這對正則表達(dá)式匹配技術(shù)在匹配速度和存儲空間方面提出了雙重挑戰(zhàn)。新型并行化硬件發(fā)展迅速,但由于傳統(tǒng)的正則表達(dá)式匹配技術(shù)基于串行處理,無法直接利用并行硬件提升正則表達(dá)式匹配的性能。 本文對正則表達(dá)式匹配算法的并行化技術(shù)展開研究,具體研究內(nèi)容包括：DFA構(gòu)建并行加速技術(shù)、DFA并行分解技術(shù)和DFA最小化并行加速技術(shù)。本文的主要研究成果總結(jié)如下： (1)DFA并行構(gòu)建算法：本文在沿用k-Reduction算法對DFA的組織方法的基礎(chǔ)上,研究經(jīng)典的子集構(gòu)造法的多線程并行加速技術(shù)。本文提出兩種DFA并行構(gòu)建算法：基于并行讀寫的DFA構(gòu)建算法PRW通過對狀態(tài)映射表的加鎖和解鎖操作,保證公共數(shù)據(jù)的多線程安全性,該算法的DFA構(gòu)建速度最快達(dá)到k-Reduction算法的1.716倍；基于多線程和單線程循環(huán)交替的DFA構(gòu)建算法SMA從狀態(tài)映射表讀取頻率顯著高于寫入頻率這一現(xiàn)象入手,拆分狀態(tài)映射表的讀寫權(quán)限,該算法的DFA構(gòu)建速度最快達(dá)到k-Re...

【文章頁數(shù)】：80 頁

【學(xué)位級別】：碩士

【文章目錄】：
摘要
ABSTRACT
第一章 引言
    1.1 研究背景與意義
    1.2 研究內(nèi)容
    1.3 論文的組織結(jié)構(gòu)
第二章 正則表達(dá)式匹配技術(shù)綜述
    2.1 正則表達(dá)式的基本概念
    2.2 經(jīng)典的正則表達(dá)式匹配方法
        2.2.1 正則表達(dá)式匹配的一般流程
        2.2.2 NFA和DFA的基本概念與比較
    2.3 基于確定型有限狀態(tài)自動機(jī)的正則表達(dá)式匹配的研究現(xiàn)狀
        2.3.1 DFA的空間壓縮技術(shù)
        2.3.2 DFA構(gòu)建加速技術(shù)
        2.3.3 DFA最小化及其并行技術(shù)
        2.3.4 基于硬件加速的匹配技術(shù)
    2.4 本章小結(jié)
第三章 DFA構(gòu)建的并行加速技術(shù)
    3.1 問題的提出
    3.2 經(jīng)典的DFA構(gòu)建算法：子集構(gòu)造法
    3.3 基于多線程并行讀寫的DFA并行構(gòu)建算法：PRW
        3.3.1 PRW算法的基本思想
        3.3.2 PRW算法的設(shè)計(jì)與實(shí)現(xiàn)
    3.4 基于單線程和多線程循環(huán)交替的DFA并行構(gòu)建算法：SMA
        3.4.1 SMA算法的基本思想
        3.4.2 SMA算法的設(shè)計(jì)與實(shí)現(xiàn)
    3.5 實(shí)驗(yàn)評估
        3.5.1 實(shí)驗(yàn)環(huán)境與實(shí)驗(yàn)數(shù)據(jù)
        3.5.2 PRW算法與k-Reduction算法的比較
        3.5.3 線程數(shù)量對PRW算法的影響
        3.5.4 SMA算法與k-Reduction算法的比較
        3.5.5 線程數(shù)量對SMA算法的影響
        3.5.6 切換閾值對SMA算法的影響
    3.6 本章小結(jié)
第四章 DFA并行分解技術(shù)
    4.1 問題的提出
    4.2 基于字符集分解的DFA并行分解算法PDFA
        4.2.1 PDFA算法的基本思想
        4.2.2 PDFA算法的形式化定義與正確性證明
        4.2.3 PDFA算法的整體流程
        4.2.4 PDFA算法的預(yù)處理階段
        4.2.5 PDFA算法的過濾與校驗(yàn)階段
        4.2.6 PDFA算法對狀態(tài)轉(zhuǎn)移表大小的影響
    4.3 實(shí)驗(yàn)評估
        4.3.1 實(shí)驗(yàn)環(huán)境與實(shí)驗(yàn)數(shù)據(jù)
        4.3.2 實(shí)驗(yàn)一：PDFA算法的空間壓縮效果
        4.3.3 實(shí)驗(yàn)二：PDFA算法的壓縮效果與相關(guān)壓縮算法的比較
        4.3.4 實(shí)驗(yàn)三：PDFA算法的過濾效果
        4.3.5 實(shí)驗(yàn)四：PDFA算法的匹配用時(shí)
    4.4 本章小結(jié)
第五章 DFA最小化的并行加速技術(shù)
    5.1 問題的提出
    5.2 經(jīng)典的DFA最小化算法Hopcroft
    5.3 基于多線程并行的DFA最小化算法P-Hopcroft
        5.3.1 P-Hopcroft算法的基本思想
        5.3.2 P-Hopcroft算法的設(shè)計(jì)與實(shí)現(xiàn)
    5.4 實(shí)驗(yàn)評估
        5.4.1 實(shí)驗(yàn)環(huán)境與實(shí)驗(yàn)數(shù)據(jù)
        5.4.2 實(shí)驗(yàn)一：P-Hopcroft算法與原始Hopcroft算法的比較
        5.4.3 8實(shí)驗(yàn)二：線程數(shù)量對P-Hopcroft算法性能的影響
    5.5 本章小結(jié)
第六章 總結(jié)與展望
    6.1 本文工作總結(jié)
    6.2 下一步的研究工作
參考文獻(xiàn)
致謝
攻讀學(xué)位期間發(fā)表或已錄用的學(xué)術(shù)論文



本文編號：3931099