基于正則表達式的多模式匹配算法研究.pdf

1、隨著計算機和Intemet技術的普及與發(fā)展,網絡在人們日常生活中發(fā)揮越來越重要的作用,但是隨之而來的網絡安全問題也日益突出。入侵檢測系統(tǒng)作為保障網絡安全的重要防護措施得到了廣泛應用,模式匹配作為入侵檢測系統(tǒng)中的一項關鍵技術,其性能優(yōu)劣關系到整個入侵檢測系統(tǒng)的效率,提高模式匹配的效率是提高這類系統(tǒng)檢測能力的關鍵所在。
　　 本文簡單介紹了入侵檢測系統(tǒng),分析了多模式匹配算法在其中的應用,并對AC、AC_BM和WM算法做了詳細說明。但

2、是,隨著網絡技術的發(fā)展和規(guī)則集復雜性的增加,這些傳統(tǒng)的字符串匹配引擎正逐漸被先進的正則表達式引擎所替代。
　　 正則表達式匹配引擎一般是基于非確定的有限自動機(Nondetenninistic Finite Automaton，NFA)和確定的有限自動機(Deterministic Finite Automaton,DFA)的?；贜FA的匹配引擎匹配速度慢,但存儲空間相對較小?；贒FA的匹配引擎具有先天的速度優(yōu)勢,但是消耗的

3、存儲空間過大,并且隨著規(guī)則集規(guī)模的增大,其對存儲空間的需求更大。本文從減少構造的自動機的狀態(tài)數出發(fā),提出了一種有效的DFA合并算法(稱為COM DFA算法)。在自動機構造過程中,將各個正則表達式分開處理,避免合并自動機時狀態(tài)和遷移邊之間的交互重疊情況的出現,能夠大大地減少自動機的狀態(tài)數。并且,通過引入空轉移合并DFA,構造一個具有最小狀態(tài)數的自動機,從而減少存儲空間需求。最后,引入壓縮率CR(Compressed Rate)的概念來描述

4、合并算法對自動機狀態(tài)數的壓縮比率。實驗結果表明算法對DFA狀態(tài)數具有較好的壓縮效果。
　　 針對NFA和DFA的匹配速度和內存需求之間的矛盾,提出一種基于DFA-NFA結構有限自動機的正則表達式匹配算法(稱為D N算法)。算法采用DFA-NFA結構實現自動機的構造,分開處理引起DFA空間爆炸的狀態(tài),以降低存儲需求。由于網絡中的數據只有很少一部分是惡意數據,而大部分是正常數據,DFA部分在NFA部分之前的設計可以實現數據過濾功能,