基于矢量化加速的網(wǎng)絡(luò)安全應(yīng)用多模式匹配

劉文濤

(安徽師范大學(xué) 計算機與信息學(xué)院,安徽 蕪湖 241000)

現(xiàn)代網(wǎng)絡(luò)科技的普及應(yīng)用給經(jīng)濟及文化等諸多領(lǐng)域造成顯著影響．網(wǎng)絡(luò)空間中流傳著大量數(shù)據(jù)資料，但無法完全規(guī)避信息安全風(fēng)險．根據(jù)金融時報報道，網(wǎng)絡(luò)每隔20秒就會發(fā)生一次入侵現(xiàn)象．信息安全是保障互聯(lián)網(wǎng)繼續(xù)擴大應(yīng)用的關(guān)鍵，一旦信息安全受到威脅，丟失敏感數(shù)據(jù)，可能會損害到國家利益．而如何預(yù)防信息外泄與遭受破壞，避免由此出現(xiàn)利益侵害，應(yīng)當(dāng)成為我國在不可逆轉(zhuǎn)的網(wǎng)絡(luò)和信息環(huán)境中必須面對和解決的重大戰(zhàn)略問題．IDS(入侵檢測系統(tǒng))是一種對網(wǎng)絡(luò)傳輸進行即時監(jiān)視，在發(fā)現(xiàn)可疑傳輸時發(fā)出報警或者采取主動反應(yīng)措施的網(wǎng)絡(luò)安全設(shè)備，它具有維護計算機應(yīng)用安全的功能，其最初開發(fā)設(shè)計就是為保障安全，可以支持不間斷檢測及反饋系統(tǒng)中出現(xiàn)的無權(quán)限操作與其他異常指令．其配備的多模式匹配算法在檢測過程中發(fā)揮關(guān)鍵性作用，在自適應(yīng)計算網(wǎng)絡(luò)中、持續(xù)擴大的數(shù)據(jù)規(guī)模的情況下，保障模式匹配組合的準(zhǔn)確性．

針對大型模式庫中的模式集檢測問題，提出一種快速高效的模式集檢測機制，以避免模式集重復(fù)組合的情況．另外，對于數(shù)據(jù)包，可能會因為計算時效和系統(tǒng)連接的存儲器使用情況，導(dǎo)致處理效率不高．所以應(yīng)用模式匹配方法解決網(wǎng)絡(luò)安全問題是當(dāng)前迫切需要研究的．為解決當(dāng)前網(wǎng)絡(luò)安全中存在的問題，提出一種基于矢量化技術(shù)的網(wǎng)絡(luò)安全多模式匹配方法，以解決目前存在的問題．

1 多模式匹配預(yù)處理階段

在預(yù)處理階段對模式集中的所有模式進行預(yù)處理，從而形成有限狀態(tài)機，將每個狀態(tài)轉(zhuǎn)換為狀態(tài)機，表示模式串字符的跳躍，得到模式串的偏移．該算法在預(yù)處理階段，可同步運用多級散列與動態(tài)裁剪處理，形成移位表以及PMT表[1]．在網(wǎng)絡(luò)安全的預(yù)處理時期，系統(tǒng)運行流程為：

(1)基于對模式字符串的準(zhǔn)確讀取后，按照一定規(guī)則保存于數(shù)據(jù)庫內(nèi)．保留集合內(nèi)各模式串的最小字符長度，即m；

(2)將SHIFT表以及PMT表進行初始化處理，全部跳轉(zhuǎn)值均調(diào)整至m-B+1，把后一個表內(nèi)的模式數(shù)直接調(diào)成“0”，并把模式鏈表調(diào)整成NULL；

(3)在首個模式串運行后，把大小是“1”的滑動窗，插到模式串開頭，而根據(jù)動態(tài)切割處理，逐一篩選各模式串上的窗口，得出匹配效率最高的位置．

同時，在 PMT表中添加與窗口長度最佳的后綴字符塊相對應(yīng)的跳轉(zhuǎn)值，在 PMT表條目的模式鏈表中添加跳轉(zhuǎn)值為零的模式串；

(4)為 SHIFT表和 PMT表(除(3)中處理的后綴字符塊外)添加最佳窗口中的每個模式串的字符塊，修改相應(yīng)跳轉(zhuǎn)值，最終得到匹配過程中使用的 PMT表和 PMT表．

在此基礎(chǔ)上，確定最有利的m窗口．相應(yīng)計算流程為：

把字符長度是m的窗口直接放于首個模式串開頭，讓相應(yīng)窗口位置的末尾B個字符構(gòu)成的字符塊運行哈希H1．如果對應(yīng)項的移位值不為零，則檢索移位表時所得到的散列值，將窗口中的一個字符移到模式字符串的結(jié)尾．依舊按照以上流程進行，假設(shè)移位值是“0”，字符塊需啟動哈希H2，能得到PMT表散列數(shù)據(jù)．在模式串?dāng)?shù)不是0，需把對應(yīng)窗口內(nèi)某個字符放置在末尾，依舊根據(jù)以上流程進行．假設(shè)此時串?dāng)?shù)變成0[2-6]，說明該窗口是最有利的位置，而后將其與模式串相應(yīng)的開始位置之間的偏移p保存下來．PAT的值等于窗口移動的次數(shù)，它記錄在模式庫 PAT的p偏移域中，該域位于模式庫 PAT中．當(dāng)模式字符串末尾未篩選出最優(yōu)m，系統(tǒng)會把模式串中首個m當(dāng)成最優(yōu)m窗口，此時保存的偏移值是0．

再次執(zhí)行以上步驟，能得到集合內(nèi)各模式串相應(yīng)的最優(yōu)m與偏移值．另外，該類窗口內(nèi)字符是B字符塊，相應(yīng)跳轉(zhuǎn)值會直接調(diào)至0，在PMT模式鏈表上，添加模式串，并將 PMT entry skip值 SHIFT設(shè)置為零，將模式串的 pnodenum數(shù)增加1．

2 網(wǎng)絡(luò)安全應(yīng)用多模式匹配實現(xiàn)

在上述多模式匹配基礎(chǔ)上，對網(wǎng)絡(luò)安全應(yīng)用多模式匹配．在算法的匹配階段，將匹配的文字作為一組字符流依次掃描，當(dāng)此流中的每個字符進入狀態(tài)機后，自動機會自動地改變狀態(tài)[7-11]，如果匹配成功，就會輸出．

為避免匹配失敗時不必要的回溯，引入下一個數(shù)組，該算法在預(yù)處理階段，根據(jù)模式串的特征計算下一個序列，若模式串無法匹配文字字串，則將刪除下一個數(shù)組的值，下一個序列表達式如下所示：

(1)

式(1)中，j代表文本串的字符.除發(fā)生匹配不成功情況外，基本的匹配過程見圖1.

圖1 基本的匹配過程

匹配過程的具體流程如下：

1)掃描模式集合，基于在匹配過程中用于在窗口中掃描和匹配測試的文本字符串長度不能超過最長模式字符串長度，所以確定模式集中的最長模式字．以下述模式集為例p={he，she，his，hers}，將p中的所有模式添加在狀態(tài)轉(zhuǎn)移函數(shù)圖內(nèi)，整個運行步驟為：其一，確定收割模式串he，添加到相應(yīng)圖表內(nèi)，基于當(dāng)下情形編輯字符，而后實現(xiàn)狀態(tài)轉(zhuǎn)化[12-15]．圖2中顯示了從0到2的所有狀態(tài)；

2)每一個處理器核心依次讀取被匹配的文本并提取第二個模式串she，將它添加到狀態(tài)轉(zhuǎn)移函數(shù)圖(圖3)；

3)接著輸入第三個模式串his，將其加入到狀態(tài)轉(zhuǎn)移函數(shù)圖(圖4)；

以上各節(jié)的主要意義是，繼續(xù)向后讀待測文本，并在2)中選中的自動機中完成跳轉(zhuǎn)；

4)輸入第四個模式串hers，將其加入到狀態(tài)轉(zhuǎn)移函數(shù)圖(圖5)；

5)除上述外，循環(huán)結(jié)束時應(yīng)該添加狀態(tài)0，這意味著除了狀態(tài)h和s之外，沒有任何模式字符串以s或h開頭，其他所有狀態(tài)都與狀態(tài)0連接．狀態(tài)從故障函數(shù)0到狀態(tài)0省略了連接，圖6為完全狀態(tài)轉(zhuǎn)換功能圖；

圖3 輸入she 的狀態(tài)轉(zhuǎn)移函數(shù)

圖4 輸入his的狀態(tài)轉(zhuǎn)移函數(shù)

每一種狀態(tài)達到一個新狀態(tài)，就需要對其進行狀態(tài)檢查，如有，表示模式匹配發(fā)生，匹配結(jié)果需要記錄；

6)閱讀最后的文本字符，依次返回步驟2)，直到閱讀到待測試的字符串的末尾，或閱讀到窗口字符串超出了最長模式字符串，即完成網(wǎng)絡(luò)安全應(yīng)用程序的多模式匹配．

3 實驗對比

為驗證所研究的基于矢量化加速的網(wǎng)絡(luò)安全應(yīng)用多模式匹配方法的有效性，進行實驗，并將傳統(tǒng)匹配方法與所研究方法做對比．

圖5 輸入hers 的狀態(tài)轉(zhuǎn)移函數(shù)

圖6 完整的狀態(tài)轉(zhuǎn)移函數(shù)

3.1 實驗數(shù)據(jù)準(zhǔn)備

在程序中，隨機生成字符串 T. txt和 p. txt．在這種情況下，匹配數(shù)據(jù) T. txt是固定的字符串， p. txt是要匹配的模式字符串， p通過程序進一步處理，得到一個具有不同長度和編號的文件．本仿真實驗包括實驗一和實驗二兩組實驗，其數(shù)據(jù)分別如表1、表2所示.

表1 實驗一的模式串?dāng)?shù)據(jù)

表2 實驗二的模式串?dāng)?shù)據(jù)

3.2 實驗一結(jié)果分析

以表1中不同數(shù)字和隨機長度的模式字符串作為模式字符串集合的數(shù)據(jù)源，隨機生成40 000字符的 T字串，作為文本字符串．schema字符串被分成5個文件，分別是1 000,2 000,3 000,4 000和5 000．使用同一實驗環(huán)境，測試了五個不同模式的字符串文件，并將其與文本字符串文件 T匹配．研究方法和傳統(tǒng)方法的實際匹配時間見圖7.

圖7 運行時間測試結(jié)果對比

從實驗結(jié)果的對比可以得出：

在同一實驗環(huán)境中模式串?dāng)?shù)量比較少的情況下，此次研究算法與傳統(tǒng)算法時間消耗相差不大，但是對于此次研究算法來說，其匹配時間始終比其他兩個算法的匹配時間低．隨著模式串?dāng)?shù)量不斷增加，所測試的兩個算法的時間消耗都隨之增大，但所研究算法的時間增加幅度比傳統(tǒng)算法要小．隨著模式串?dāng)?shù)量的不斷增多，改進算法的匹配時間與傳統(tǒng)方法的匹配時間消耗相差越大，從中可看出所研究算法在匹配時間上的優(yōu)越性.表3為三種算法測試時間與成功匹配次數(shù)結(jié)果對比情況．

表3 三種算法測試時間與成功匹配次數(shù)結(jié)果對比

表3為兩種方法分別在不同模式串個數(shù)情況下的匹配結(jié)果，本次研究方法能成功匹配，成功匹配次數(shù)與從文本串中隨機抽取的模式串個數(shù)相等，這表明所研究方法具有較高的檢測準(zhǔn)確率，而傳統(tǒng)的匹配方法成功次數(shù)相對較低，沒有本研究方法應(yīng)用效果好．

3.3 實驗二結(jié)果分析

實驗一中算法的運行時間測試是根據(jù)模式串的長度和個數(shù)隨機進行的，為更全面地比較和分析這兩種算法的性能，在第二個實驗中，改變了模式串的特征，即當(dāng)模式串的長度和數(shù)目是固定的時候，進一步測試算法的性能．

(1)確定模式字符串的數(shù)目，改變模式字符串的長度，用5 000個文件中的模式字符串進行測試，并將長度分別設(shè)置為4、7、10、13和20．兩種方法的匹配時間如圖8所示.

圖8 模式串長度不同情況時的匹配時間

圖9 模式串?dāng)?shù)量不同情況時的匹配時間

實驗結(jié)果表明，當(dāng)模式串長度不同且數(shù)目固定時，兩種方法的匹配時間都隨模式串長度的增加而增大，但幅度不大．從以上數(shù)據(jù)可以看出，無論模式串的長度如何變化，所研究方法的所需匹配時間最少，匹配效率最高．

(2)定出模式字符串的長度，改變模式字符串?dāng)?shù)目．其中，固定模塊串個數(shù)分為5種，分別為1 000、2 000、3 000、4 000和5 000．圖9中顯示了不同模式串長度與匹配時間的關(guān)系.

由本次實驗結(jié)果可知，當(dāng)模式串長度或模式串?dāng)?shù)量固定時，傳統(tǒng)算法與所研究方法隨著模式串?dāng)?shù)量的增加，算法匹配消耗的時間也都隨之增長，而本文提出的改進算法的匹配時間隨著模式串?dāng)?shù)量的增加其增長的幅度最小，表明相比于傳統(tǒng)算法，所研究方法對模式串?dāng)?shù)量或長度變化的敏感度較低，匹配效率最高．

4 結(jié)束語

針對網(wǎng)絡(luò)數(shù)據(jù)量的不斷增大，對模式匹配算法性能的要求更高的問題，設(shè)計了一個基于矢量化加速的網(wǎng)絡(luò)安全應(yīng)用多模式匹配方法，并通過實驗證明，該系統(tǒng)提高了匹配效率．本文在研究方法上進行兩方面改進，取得了較好的效果．同時本文提出的改進算法還存在很多不足，后續(xù)還需進一步優(yōu)化．