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

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

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

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

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