資源描述：
《基于正則表達式多模式匹配算法的研究》由會員上傳分享，免費在線閱讀，更多相關內容在學術論文-天天文庫。
1、抗州電子科技大學碩士學位論文摘要隨著計算機和Intemet技術的普及與發(fā)展，網絡在人們日常生活中發(fā)揮越來越重要的作用，但是隨之藤來的網絡安全問題也隧益突戰(zhàn)。入侵檢測系統(tǒng)作為保障瓣終安全的重要防護措施得到了廣泛應用，模式匹配作為入侵檢測系統(tǒng)中的一頊關鍵技術，其性能優(yōu)劣關系到整個入侵檢測系統(tǒng)的效率，提高模式匹配的效率是提高這類系統(tǒng)檢測能力的關鍵所在。本文簡單介紹了入侵檢測系統(tǒng)，分析了多模式匹配算法在其中的應用，并對AC、ACBM和WM算法徽了詳細說明。但是，隨著闞絡技術的發(fā)愛穰規(guī)翼
2、j集復雜性的增加，這些傳統(tǒng)翡字符串匹配弓l擎正逐漸被先進的正則表達式引擎所替代
3、。正則表達式匹配引擎一般是基于非確定的有限自動機(NondeterministicFiniteAutomaton,M’A)和確定的有限自動機(DeterministicFiniteAutomaton,D融)的。基予NFA的隨配引擎匹配速度慢，但存儲空闐相對較小?；贒FA的匹配引擎具有先天的速度優(yōu)勢，但是消耗的存儲空間過大，并且隨著規(guī)則集規(guī)模的增大，其對存儲空間的需求更大。本文從減少構造的自動機的狀態(tài)數出發(fā)，提出了一種有效的DFA合并算法(稱為COMDFA算法)。在自動機構造過程中，將各個正則表達式分開處理，避免合并自動機時狀態(tài)翻遷移邊之聞的交互重疊情況的
4、嫩現，能夠大大地減少自動楓的狀態(tài)數。并且，通過引入空轉移合并DFA，構造～個具有最小狀態(tài)數的自動機，從麗減少存儲空間需求。最后，引入壓縮率CR(CompressedRate)的概念來描述合并算法對自動機狀態(tài)數的壓縮比率。實驗結果表明算法對DFA狀態(tài)數具有較好的壓縮效果。針對NFA和DFA的匹配速度秘內存需求之間的矛盾，提出一種基于DFA制淞結構有限自動機的芷則表達式匹配算法(稱為13lN算法)。算法采用DFA-NFA結構實現自動機的構造，分開處理弓
5、起DFA空閩爆炸的狀態(tài)，以降低存儲需求。由于網絡中的數據只有很少一部分是惡意數據，而大部分是正常數據，DFA
6、部分在NFA部分之前的設計可以實現數據過濾功能，能夠加快算法的匹配速度。同時，在自動機的構造過程中，針對DFA-NFA邊秀上的關鍵狀態(tài)，對同樣的輸入字符，設置相應遷移邊的優(yōu)先級。匹配過程采用基于優(yōu)先級的查找算法，檢查優(yōu)先級來確定當前狀態(tài)在讀入字符下可以跳轉到的下一狀態(tài)，從1愆加快匹配過程。DN算法的測試結果表明其匹配效率和在狀態(tài)方面的存儲需求比傳統(tǒng)算法有較大提離。關鍵訶：模式殛配，入侵檢測系統(tǒng)，正則表達式，有限狀態(tài)自動機杭州電子科技大學碩士學位論文ABSTRACTWiththepopularityanddevelopmentofcomputerandInt
7、eracttechnology,networkplaysa11increasinglyimportantrolein0111"dailylife，butthefollowingproblemsofnetworksecurityareoutstandingdaybydaytoo。Asanimportantprotectionmeasuretoguaranteenetworksecurity,intrusiondetectionsystemhasbeenlargelypopularizedandapplied．Asoneofthekeytechnologies
8、ofintrusiondetectionsystem，theimprovementoftheefficiencyofpatternmatchingalgorithmisessentialtoincreasethetestingabilityofthesystembecausethattheperformanceofpatternmatchingrelatestotheefficiencyofintrusiondetectionsystem．Inthispaper,theintrusiondetectionsystemisintroducedandtheap
9、plicationofpatternmatchingalgorithmsinthesystemisanalyzed．Meanwhile,ACalgorithm，AC—BMalgorithmandWMalgorithmarealsodiscussedindetail．However,alongw{1Illthedevelopmentofnetworktechnologyandtheincrementofcomplexityofrulesets，thetraditionalstringmatchingenginesalegraduallyreplacedbym
10、oreadvancedregularexpressionengin
