隨著正則表達式在網絡安全系統(tǒng)和各種服務中的應用越來越廣泛,這些系統(tǒng)采用正則表達式匹配算法作為他們的核心,檢測數據包有效載荷中的攻擊特征。最近幾年的研究大多集中在大規(guī)模的正則表達式規(guī)則集下,如何有效地減少DFA存儲空間的開銷。在現代網絡入侵檢測系統(tǒng)中,如何從海量數據中甄別出有害信息,對阻止和遏制潛在的危險行為,對維護網絡中數據的傳輸安全與穩(wěn)定,對促進互聯(lián)網產業(yè)健康發(fā)展,都具有十分重要的現實意義。為了檢測數據包有效載荷中的危險模式,需要在線速度內完成正則表達式匹配。雖然確定性有限狀態(tài)機（DFAs）允許此操作在線性時間內完成,但他們在內存中的存儲可能會需要過高的需求。在內存存儲空間中,DFA的開銷主要用于存儲其狀態(tài)轉移表,表的行寬對應DFA的狀態(tài)數目,而表的列寬對應著每個狀態(tài)的轉移邊數目|Σ|（Σ是輸入字符的字母表）。對正則表達式規(guī)則集進行分組是一種用于解決DFA狀態(tài)膨脹問題的重要方法。目前為止,對于DFA在內存中存儲開銷過大問題的解決思路,可以分為兩種,即減少DFA的狀態(tài)數目和壓縮DFA的轉移邊,通過正則表達式規(guī)則集分組算法來壓縮DFA的存儲空間屬于上述中的第一種解決思路。本文在對目前狀態(tài)... 

【文章來源】：杭州電子科技大學浙江省

【文章頁數】：60 頁

【學位級別】：碩士

【文章目錄】：
摘要
ABSTRACT
第1章 緒論
    1.1 課題研究背景及意義
    1.2 國內外研究現狀
    1.3 論文研究內容安排
第2章 正則表達式匹配原理
    2.1 正則表達式介紹
    2.2 正則表達式匹配
        2.2.1 匹配算法
        2.2.2 匹配系統(tǒng)
    2.3 自動機選擇
    2.4 基于規(guī)則集的分組算法
        2.4.1 分組算法背景知識
        2.4.2 分組算法介紹
        2.4.3 改進的分組算法介紹
    2.5 實驗結果
    2.6 本章小結
第3章 DFA優(yōu)化技術
    3.1 背景知識介紹
    3.2 壓縮算法介紹
    3.3 改進的壓縮算法介紹
    3.4 壓縮算法比較
        3.4.1 最差時間邊界和內存減少量
        3.4.2 算法復雜度比較和實際情況中的細節(jié)
        3.4.3 額外的方面
    3.5 字母表減少算法
        3.5.1 思想
        3.5.2 算法
    3.6 內存編碼方式
        3.6.1 無壓縮布局
        3.6.2 線性編碼
        3.6.3 位圖編碼
        3.6.4 小結
    3.7 多步長DFAs
        3.7.1 多步長DFAs的尋址
        3.7.2 多步長DFA生成算法
    3.8 實驗評估
    3.9 本章小結
第4章 基于規(guī)則集的最優(yōu)匹配算法配置方法
    4.1 輸入介紹
    4.2 實驗評估
        4.2.1 參數
        4.2.2 度量
    4.3 處理器模擬器結果
        4.3.1 cache大小
        4.3.2 內存帶寬和并行執(zhí)行
    4.4 最佳正則表達式匹配配置
        4.4.1 最佳配置
        4.4.2 最優(yōu)化指導
    4.5 本章小結
第5章 總結與展望
    5.1 論文總結
    5.2 研究方向展望
致謝
參考文獻
附錄


【參考文獻】：
期刊論文
[1]正則表達式分組的1/（1-1/k）-近似算法[J]. 柳廳文,孫永,卜東波,郭莉,方濱興.  軟件學報. 2012(09)
[2]深度包檢測中一種高效的正則表達式壓縮算法[J]. 徐乾,鄂躍鵬,葛敬國,錢華林.  軟件學報. 2009(08)
[3]基于GPU的串匹配算法研究[J]. 張慶丹,戴正華,馮圣中,孫凝暉.  計算機應用. 2006(07)



本文編號：3488594