基于確定有限狀態(tài)自動機的正則表達式引擎的設計與實現(xiàn).pdf

1、伴隨著網(wǎng)絡安全審計技術的發(fā)展，針對應用層的攻擊現(xiàn)象越來越多，因為應用層的協(xié)議種類繁多，基于正則表達式的審計技術擁有基于字符串匹配的審計技術所不具有的強大表達能力和靈活的擴展性能，越來越多的網(wǎng)絡審計技術已經(jīng)使用正則表達式來進行描述和支持。傳統(tǒng)的正則表達式匹配引擎主要分為基于NFA和基于DFA等兩種正則表達式匹配引擎，由于DFA在某些領域例如網(wǎng)絡監(jiān)測中的應用越來越廣泛，其在詞法分析技術當中研究的焦點地位越來越突出。
　　本論文在針對現(xiàn)

2、有的構造 DFA引擎優(yōu)化技術的研究和分析的基礎上，從兩個方面來研究 DFA引擎的優(yōu)化技術和實現(xiàn)方案：第一、基于單個DFA引擎的構造和優(yōu)化；第二、基于分組算法構造 DFA引擎的構造和優(yōu)化。在第一種優(yōu)化技術和實現(xiàn)方案中，研究了正則表達式中特殊的ASCII字符匹配的情況，在研究使用子集構造法構造 DFA引擎的過程中，優(yōu)化了原有的子集構造過程，使單個DFA引擎的生成效率大大提高了，并在此基礎上實現(xiàn)了相關的單一 DFA正則表達式匹配引擎；在第二種

3、優(yōu)化技術和實現(xiàn)方案中，研究了正則表達式或者 DFA結構之間的相似關系，在研究使用分組方法構造 DFA引擎的過程中，收集了大量的測試數(shù)據(jù)，提出了正則表達式相似度的概念和公式，并在此基礎上實現(xiàn)了基于分組算法的分組DFA正則表達式引擎。
　　針對實現(xiàn)的兩種正則表達式引擎，制定了詳細的測試計劃，從時間消耗和空間占用的角度對兩個引擎分別做了有針對性的性能測試，實驗結果表明，無論是在時間消耗方面還是在空間占用方面，優(yōu)化后的DFA引擎都比沒有引