Snort規(guī)則建模及有窮自動機的轉(zhuǎn)化與合并算法研究.pdf

1、隨著計算機和網(wǎng)絡(luò)技術(shù)的快速發(fā)展,網(wǎng)絡(luò)安全問題日益突出。由于防火墻只是一種被動防御性的網(wǎng)絡(luò)安全工具,不能滿足如今復(fù)雜多變的網(wǎng)絡(luò)安全需求。因此作為防火墻的補充,入侵檢測系統(tǒng)在網(wǎng)絡(luò)安全領(lǐng)域發(fā)揮著越來越重要的作用。Snort是目前最為典型的輕量級網(wǎng)絡(luò)入侵檢測系統(tǒng),該系統(tǒng)通過將捕獲到的數(shù)據(jù)包與規(guī)則庫中的規(guī)則進行匹配以過濾有危害的數(shù)據(jù)包,從而達到提高網(wǎng)絡(luò)安全的目的。
　　在將Snort與有窮自動機理論結(jié)合起來進行網(wǎng)絡(luò)入侵檢測的過程中,有以下幾

2、個關(guān)鍵問題需要解決:
　　1)如何將Snort規(guī)則選項轉(zhuǎn)化成PCRE,以便進一步轉(zhuǎn)化成有窮自動機;
　　2)如何將Snort規(guī)則使用統(tǒng)一的規(guī)范進行表示以便減小Snort規(guī)則處理的復(fù)雜度;
　　3)如何減少將非確定有窮自動機(Nondeterministic Finite Automaton, NFA)轉(zhuǎn)化為確定有窮自動機(Deterministic Finite Automaton, DFA)過程中的重復(fù)計算,以便提高

3、NFA到DFA的轉(zhuǎn)化效率;
　　4)如何高效地將多個DFA合并成一個DFA以便加快數(shù)據(jù)包的過濾速度。
　　針對以上四個問題,本文的主要工作如下:
　　(1)根據(jù) Snort規(guī)則選項對于數(shù)據(jù)包的匹配順序,建立了選項鏈模型,并進一步通過將規(guī)則選項轉(zhuǎn)化成PCRE從而將選項鏈模型歸一化為PCRE鏈模型。
　　(2)提出了將NFA轉(zhuǎn)化為DFA的一種新的高效算法以提高數(shù)據(jù)包與Snort規(guī)則的匹配速度。該算法首先使用哈希算法將

4、NFA字符集上的字符進行分組,再使用改進的子集構(gòu)造法將NFA轉(zhuǎn)化成DFA。
　　(3)提出了合并多個DFA的一種新的高效算法。該算法既不用將多個DFA構(gòu)造成一個NFA也不用計算ε-closure就能將多個DFA合并成了一個DFA。
　　實驗結(jié)果表明,本文提出的有窮自動機轉(zhuǎn)化算法和有窮自動機合并算法都是正確和高效的。其中有窮自動機轉(zhuǎn)化算法可以有效避免子集構(gòu)造法的重復(fù)計算,提高了轉(zhuǎn)化效率,且得到的DFA的狀態(tài)轉(zhuǎn)換矩陣的存儲空間比