《基於非標準模式匹配及圖形處理單元的深度包檢測研究》是依託吉林大學，由張猛擔任項目負責人的面上項目。
基本介紹
- 中文名：基於非標準模式匹配及圖形處理單元的深度包檢測研究
- 項目類別：面上項目
- 項目負責人：張猛
- 依託單位：吉林大學
項目摘要,結題摘要,
項目摘要
深度包檢測（DPI）是網路入侵檢測/防禦系統、防病毒系統等安全套用的核心功能模組。字元串/正則表達式匹配算法是其關鍵技術。由於攻擊的日益複雜以及網路速度的不斷提高，現有方法暴露出性能不足，空間爆炸等問題。因此有必要對高性能、可擴展性好的匹配算法展開更深入的研究。.本項目首先建立圖形處理單元上的基於比特並行的非確定性自動機模型，由此實現在空間和時間兩方面都高效的多正則表達式匹配。其次，引入快速傅立葉變換及比特並行等非標準模式匹配技術，提出不同於有限狀態自動機的新型正則表達式匹配方法，提高匹配算法的記憶體頻寬、避免空間爆炸。另外，首次從檢測和回響的角度研究針對DPI的算法複雜攻擊。最後，基於上述結果實現一個能抵抗算法攻擊的高性能入侵檢測(預防)系統原型並對其進行評價。
結題摘要
深入到網路包套用層載荷的檢查和處理被稱為深度包檢測(DPI)。DPI是網路入侵檢測系統、防病毒系統等安全套用的核心模組。DPI需要較大的處理開銷和空間占用，提高性能一直是DPI研究的關鍵問題。隨著網路速度的提高，研究高性能DPI算法具有重要的意義。本項目以DPI系統中的高性能模式匹配算法與數據結構為中心開展了如下幾方面的研究。 項目針對正則表達式匹配空間占用大的問題，提出了基於最小完美哈希函式和比特並行Glushkov自動機的混合狀態轉移方法。實現了低空間高性能的正則表達式匹配。將現有方法的O(m2^m)比特空間複雜降低到O(m2^k)比特，狀態轉移時間複雜為O(m/w)(m為正則表達式長度，k為其中的字元串數量，w為機器字長)。其次，為了降低多模式匹配的空間占用，引入了緊湊數據結構技術構造Aho-Corasick自動機。降低了空間占用，將狀態轉移的時間複雜從O(logσ)降低到O(loglogσ)和O(1)(σ為字母表長度)，還實現了時間和空間的調節。另外，提出了確定性有限狀態自動機（DFA）的通用最佳化方法。僅增加很少的空間，實現了時間複雜為 O(loglogσ) 的狀態轉移函式。提出了實現DFA的重疊狀態轉移表方法，在保持O(1)時間狀態轉移的同時降低了空間占用。 項目首次研究了針對緊湊輸入的卷積算法。利用輸入的緊湊存儲特徵，基於機器指令的比特並行性來加速卷積運算。提出了兩種快速卷積算法，均具有優於現有方法的時間複雜度。基於新型卷積算法實現了帶通配符的模式匹配算法，新算法的時間複雜優於現有算法。實際測試表明算法具有較高的性能。由於離散卷積的通用性，此工作為高效算法設計與實現提供了有力工具。 項目提出一種對算法複雜攻擊免疫的壓縮數據內容檢測算法，無需解壓即可在壓縮數據中進行模式搜尋。新算法的貢獻在於處理開銷與輸入內容無關，實現了對算法複雜攻擊的免疫。本項目研究了收集DPI負載信息的圖搜尋算法，可用於算法複雜攻擊的檢測。提出了基於標記的一般圖搜尋算法，支持標記數量的調節。移動代理無需掌握系統信息就可在標記引導下以極小開銷實現圖搜尋。 項目在GPU和CPU平台上實現了項目提出的新算法，並開發了一個用於DPI的軟體庫和測試系統。針對GPU平台的特徵，改進並實現了部分項目提出的技術。
