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

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

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

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