面向網(wǎng)絡(luò)入侵檢測的串匹配算法優(yōu)化.pdf

1、互聯(lián)網(wǎng)已經(jīng)成為人們?nèi)粘Ｉ钪胁豢苫蛉钡囊粋€部分。伴隨而來的是日趨猖獗的網(wǎng)絡(luò)犯罪對網(wǎng)絡(luò)節(jié)點上主機的信息安全的威脅。出于不同的目的，網(wǎng)絡(luò)使用者可以利用一定的技術(shù)或者社會手段，非法進入個人主機、盜取個人賬戶密碼甚至是對網(wǎng)站進行協(xié)作攻擊。建立一個堅固的預(yù)防、阻斷網(wǎng)絡(luò)犯罪的安全體系至關(guān)重要。入侵檢測系統(tǒng)就是網(wǎng)絡(luò)安全體系中不可或缺的重要組組成部分，其主要處理對象就是來自網(wǎng)絡(luò)的數(shù)據(jù)包。入侵檢測系統(tǒng)會對網(wǎng)絡(luò)數(shù)據(jù)包和已知的數(shù)據(jù)庫進行比對，根據(jù)已掌握的數(shù)據(jù)

2、將數(shù)據(jù)包中的信息歸類為入侵行為或者安全行為。針對入侵檢測系統(tǒng)監(jiān)測到的入侵行為，還可以將這些入侵告警進行分析進一步挖掘告警之間的邏輯聯(lián)系，揭示隱含的攻擊過程用于定位攻擊源或者為后續(xù)檢測提供知識儲備。為了確保能有效地提取網(wǎng)絡(luò)數(shù)據(jù)包中的信息需要高效的串匹配算法提供技術(shù)支持。然而隨著網(wǎng)絡(luò)技術(shù)的發(fā)展，各種新的攻擊類型也層出不窮，這也使得串匹配自動機需要維護的特征集的規(guī)模越來越大，直接降低了入侵檢測系統(tǒng)的性能。
　　基于這樣的背景，本文的研究

3、目標(biāo)是構(gòu)造支持大規(guī)模特征集合的串匹配算法，并且能夠找到對現(xiàn)有串匹配算法進行速度提升的方法。具體地，本文著重從以下幾個方面、不同層次對串匹配的優(yōu)化方法進行了深入的研究：
　　(1)特征集規(guī)模過大導(dǎo)致匹配自動機無法正常構(gòu)建限制了入侵檢測系統(tǒng)能夠識別的有害信息的數(shù)量。本文特別針對大特征集文本匹配問題，提出一種混合匹配自動機模型。該模型旨在通過長度對特征進行分類，構(gòu)造更加緊湊的匹配自動機。通過將具有不同長度范圍的特征分布到不同的自動機中，

4、可以采用不同的方式對文本進行匹配。本文同時依據(jù)混合匹配自動機的結(jié)構(gòu)特點設(shè)計了兩種獨立的文本過濾策略，即逆向狀態(tài)映射狀態(tài)轉(zhuǎn)移方法（SLSPM算法）和二級AVL過濾策略（BCHDFA算法）。兩種技術(shù)分別利用“將‘自動機狀態(tài)-讀入文本信息’的映射關(guān)系進行翻轉(zhuǎn)”和“借助AVL樹對特征段中特定位置上的雙字符文本進行兩次過濾”達到減少將文本塊與特征塊進行驗證的次數(shù)的目的，從而抑制混合自動機匹配速度降低的趨勢。
　　(2)針對URL等長特征，本

5、文結(jié)合SSE指令提出了兩種專門面向16字節(jié)數(shù)據(jù)的匹配算法SSEHash和RTRIE，這兩種算法旨在提高長特征的匹配速度。SSEHash算法中，通過2個指令周期共16個加法運算和一個24比特模運算能夠?qū)?6字節(jié)文本比較均勻地分布到24比特的數(shù)據(jù)中。由于采用SSE指令進行計算，使得SSEHash算法和常規(guī)意義的散列算法相比需要更短的處理時間，能夠更快地過濾文本信息。為了解決大規(guī)模特征集環(huán)境下Wu-Manber類算法的移動距離較短的問題，本文

6、結(jié)合SSE指令提出了一種反轉(zhuǎn)自動機RTRIE。該算法提取每條長特征（長度至少16）的16字節(jié)前綴中的所有后綴子串的逆向串的指紋，并為每個指紋計算其安全移動距離。該算法和通常的Wu-Manber類算法相比在計算文本指針移動距離時考慮的文本字符數(shù)目更多，這樣可以盡量避免由于特征規(guī)模增加而導(dǎo)致的指針移動距離的降低。
　　(3)為了提高表達式匹配性能消除無用表達式對內(nèi)存的占用，本文分析了表達式的各種包含關(guān)系并提出了BitCount算法的優(yōu)

7、化算法MaskVeri以及表達式冗余消除算法KPGEM。為了不遺漏任何可能的表達式的包含關(guān)系，本文借助表達式中出現(xiàn)的各個短關(guān)鍵字的位置以及關(guān)鍵字的長度等信息限定了各關(guān)鍵字的前驅(qū)后繼關(guān)系。借助這種關(guān)系可以定義針對每條表達式的關(guān)鍵字路徑圖。通過對關(guān)鍵字路徑圖的遍歷KPGEM算法可以分析出當(dāng)前表達式中隱含的其它表達式，并正確地刪除表達式中冗余的關(guān)鍵字或者包含其它表達式的表達式。
　　(4)基于串匹配算法的數(shù)據(jù)包檢測部件是入侵檢測系統(tǒng)中的

8、重要功能部件。在此基礎(chǔ)上才能對通過串匹配模塊獲得的網(wǎng)絡(luò)告警日志進行告警關(guān)聯(lián)分析。本文在最后一部分實現(xiàn)了一個入侵告警事件關(guān)聯(lián)系統(tǒng)。該系統(tǒng)通過對告警中的重復(fù)結(jié)構(gòu)進行保持語義的序列最小化處理，使得串匹配算法捕獲的告警得到大幅精簡。系統(tǒng)中采用D-S證據(jù)理論對宏觀分析方法（序列挖掘）和微觀分析方法（權(quán)能提升推理）二者處理的結(jié)果進行融合，并通過信任能量計算公式對經(jīng)過D-S融合后的告警序列進行再處理，從獲得的頻繁序列中得到更能體現(xiàn)前后關(guān)系的攻擊告警序