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

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

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

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

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