改進Boyer匹配算法在Snort入侵檢測中的應用

馬小雨， 劉雙紅

(1. 河南工程學院 計算機學院， 河南 鄭州 451191；

2. 鄭州航空工業(yè)管理學院 計算機科學與應用系， 河南 鄭州 450046)

?

改進Boyer匹配算法在Snort入侵檢測中的應用

馬小雨1， 劉雙紅2

(1. 河南工程學院 計算機學院， 河南 鄭州 451191；

2. 鄭州航空工業(yè)管理學院 計算機科學與應用系， 河南 鄭州 450046)

摘要：以Snort入侵檢測系統(tǒng)為研究對象，探討其規(guī)則匹配環(huán)節(jié)的適用算法，并在Boyer算法的基礎上設計一種改進方法.此方法首先設計了一個統(tǒng)計數(shù)組，然后以兩個相鄰字符為組合執(zhí)行匹配，并分為3種策略判斷如何確定最大移動長度.實驗結果表明：這種改進措施，使得最大移動長度更加合理，相比于Boyer方法，改進方法的字符比較次數(shù)明顯降低，窗口移動次數(shù)明顯降低，執(zhí)行時間明顯減少.

關鍵詞：網(wǎng)絡安全； 入侵檢測； Snort系統(tǒng)； Boyer算法

為了應對黑客攻擊風險、協(xié)議漏洞風險、防御缺陷風險等一系列網(wǎng)絡間的安全隱患[1-2]，信息安全、密碼理論、入侵檢測等領域的研究被大量開展[3-5].Snort入侵檢測系統(tǒng)是一個非常成功的網(wǎng)絡安全檢測系統(tǒng)，具有免費開源、精準匹配的諸多優(yōu)點[6-7]，且在大多數(shù)操作系統(tǒng)上都可以運行，這對國內普遍使用的Windows系統(tǒng)具有重要意義.從執(zhí)行流程上看，Snort入侵檢測系統(tǒng)以字符為單位對網(wǎng)絡信息進行解讀，分為捕獲數(shù)據(jù)、解碼數(shù)據(jù)、預處理數(shù)據(jù)、規(guī)則匹配、判斷輸出等環(huán)節(jié)[7-8].規(guī)則匹配是用于判斷信息是否為安全的核心環(huán)節(jié)，在這個階段中，很多字符匹配算法被成功應用，而Boyer匹配算法是一種最常見的方法[9].Boyer匹配算法原理簡單，便于實現(xiàn)，但也存在重復比較等問題.為此，很多基于Boyer算法的改進算法被構建出來，如BMH算法、BMHS算法等[10-11].本文在Boyer算法的基礎上進行改進，提出更適合Snort入侵檢測系統(tǒng)使用的規(guī)則匹配算法.

1改進Boyer匹配算法

從實現(xiàn)原理上看，經(jīng)典的Boyer匹配算法屬于典型的后綴匹配方法.在字符串匹配執(zhí)行的過程中，設置一個標準串，將標準串和待匹配的字符串，按照由右及左的順序執(zhí)行比較.匹配過程是否結束的判斷依據(jù)有2個：第1種是達到預先設定的，確定為匹配失??；第2種是確定為匹配成功.整個匹配過程，都需要根據(jù)兩個重要的特征字符指引，一個稱為“優(yōu)良后綴”，一個稱為“不良字符”.

在實際運用中，為了減少帶匹配字符串和標準串的比較次數(shù)，Boyer匹配算法增大了移動距離.據(jù)此，在經(jīng)典Boyer匹配算法的基礎上進行改進，以期獲得更大的移動距離.

首先，根據(jù)經(jīng)典的Boyer匹配算法獲得一個移動距離L1.然后，把T[k+1]和T[k+2]組合起來，再計算出一個移動距離L2.最后，比較這兩個移動距離的大小，選取最大的那個作為匹配過程執(zhí)行時的移動距離.其中：T為表示待匹配字符串;k為一個以i為邊界,同標準串后綴能夠匹配上的最大長度;B為標準字符串.算法有如下4個實際的執(zhí)行過程.

1) 設置一個統(tǒng)計數(shù)組，用于統(tǒng)計各個字符在標準串中出現(xiàn)的次數(shù)，即

(1)

式(1)中:Btime(Char)為字符Char在標準串中出現(xiàn)的次數(shù).如果字符Char在標準串B中只出現(xiàn)1次，統(tǒng)計數(shù)組紀錄為1；如果字符Char在標準串B中出現(xiàn)的次數(shù)大于1，統(tǒng)計數(shù)據(jù)紀錄為0.

2) 從待匹配字符串中按照T[k+1]和T[k+2]的順序提取相鄰的字符組合，并紀錄為Char(1，2)，并用Char(1，2)和標準串B進行匹配.

3) 若標準串B沒有字符組合和Char(1，2)相同，需要進一步比較Char(1，2)和標準串的第1個字符B[1].如果Char(1，2)不含字符B[1]，L2的值就是m+2；如果Char(1，2)中的第1個字符和B[1]相等，那么L2的值是m+2；如果Char(1，2)中的第2個字符和B[1]相等，那么L2的值是m+1.

4) 若標準串B中有字符組合和Char(1，2)相同，且Char(1，2)中不含字符B[1]，Dtime(Char)=1，那么L2的值是m+2；若標準串B中有字符組合和Char(1，2)相同，且Char(1，2)中不含字符B[1]，Dtime(Char)=0，那么L2和L1相同.L1的表達式為

2實驗結果與分析

從執(zhí)行先后順序的邏輯關系上看，Snort入侵檢測系統(tǒng)從主函數(shù)Main()開始，然后調用并執(zhí)行Detect()函數(shù)完成入侵檢測.實驗中，需要將各種字符匹配算法編制成函數(shù)，并用Detect()函數(shù)調用.為了和改進算法形成對比，選擇了經(jīng)典的Boyer匹配算法，通過程序實現(xiàn)后封裝在Boyer()函數(shù)中.對于提出的改進算法，通過程序實現(xiàn)后封裝在ImBoyer()函數(shù)中.在驗證實驗的過程中，Boyer()函數(shù)和ImBoyer()函數(shù)都可以供Detect()函數(shù)調用.

實驗所用的計算機配置：酷睿雙核主頻為2.0 GHz的CPU，8 GB的內存，500 GB的硬盤；Windows 7.0操作系統(tǒng)；Snort入侵檢測系統(tǒng).實驗針對50個隨機長度的待匹配字符串，并以不同長度標準串完成匹配.50個待匹配字符串的部分樣本及全部不同長度的標準串，如表1所示.

表1　待匹配字符串樣本和標準串

隨著標準串長度的改變，比較經(jīng)典Boyer算法和提出的ImBoyer算法完成匹配的字符比較次數(shù)、窗口移動次數(shù)和執(zhí)行時間，結果如圖1所示.圖1中：n1為字符比較次數(shù)；n2為窗口移動次數(shù)；t為執(zhí)行時間；l為標準串長度；s為數(shù)據(jù)包大小.由圖1(a)可知:提出的ImBoyer算法的字符比較次數(shù)明顯低于Boyer算法;同時，隨著標準串長度的增加，兩種算法的字符比較次數(shù)都開始下降，但ImBoyer算法下降的速度明顯更快.這充分說明，所提出的ImBoyer算法性能更加優(yōu)秀.由圖1(b)知：提出的ImBoyer算法的移動次數(shù)明顯低于Boyer算法；同時，隨著標準串長度的增加，兩種算法的移動次數(shù)都開始下降，但ImBoyer算法下降的速度明顯更快.這充分說明，所提出的ImBoyer算法性能更加優(yōu)秀.由圖1(c)可知：提出的ImBoyer算法的執(zhí)行時間明顯低于Boyer算法；同時，隨著數(shù)據(jù)包大小的增加，兩種算法的執(zhí)行時間都開始增加，但ImBoyer算法增加的速度明顯更慢.這充分說明，所提出的ImBoyer算法性能更加優(yōu)秀.

(a) 字符比較次數(shù)　　　　　　　　(b) 窗口移動次數(shù)　　　　　　　　　　(c) 執(zhí)行時間　　　　圖1　經(jīng)典Boyer算法和ImBoyer算法的比較Fig.1　Comparision between Boyer algorithm and ImBoyer algorithm

3結束語

通過在規(guī)則匹配環(huán)節(jié)算法設計，對Boyer字符匹配算法進行了改進.通過對字符比較次數(shù)、窗口移動次數(shù)、執(zhí)行時間3個方面進行實驗研究，證實了改進工作的有效性.

參考文獻：

[1]SRIDHAR M，VAIDYA S，YAWAKJAR P.Intrusion detection using keystroke dynamics and fuzzy logic membership functions[C]∥Proceedings International Conference on Technologies for Sustainable Development.Switzerland：Bridges Press,2015，27(4):444-458.

[2]李杰.基于Snort的入侵檢測系統(tǒng)規(guī)則解析及改進研究[J].電子技術與軟件工程，2014，19(8):240.

[3]PARVAT T J，CHANDRA P.Performance improvement of deep packet inspection for intrusion detection[C]∥Proceedings 2014 IEEE Global Conference on Wireless Computing and Networking.[S.l.]:IEEE Press,2014:224-228.

[4]PASTRANA S，TAPIADOR J E，ORFILA A.Defidnet: A framework for optimal allocation of cyberdefenses in intrusion detection networks[J].Computer Networks，2015，80:66-88.

[5]譚笑，柯澤賢.基于混合高斯和幀間差分的機場安全入侵檢測[J].計算機仿真，2014，31(11):38-41.

[6]陳柏生，吳可沾，楊育輝.互聯(lián)網(wǎng)用戶安全登陸平臺設計[J].華僑大學學報(自然科學版)，2011，32(6):638-640.

[7]儲澤楠，李世揚.基于節(jié)點生長馬氏距離K均值和HMM的網(wǎng)絡入侵檢測方法設計[J].計算機測量與控制，2014，22(10):3406-3409.

[8]MACDERMOTT A，SHI Q，KIFAYAT K.Collaborative intrusion detection in a federated cloud environment using the Dempster Shafer theory of evidence[C]∥European Conference on Information Warfare and Security.[S.l.]:Earlybird Press,2015，195-203.

[9]PAN Zhiwen，HARIRI S,AI-NASHIF Y.Anomaly based intrusion detection for building automation and control networks[C]∥Proceedings of IEEE/ACS International Conference on Computer Systems and Applications.Morocco:EasyChair Press,2015:72-77.

[10]袁其帥，劉云朋.基于人工免疫原理的網(wǎng)絡入侵檢測系統(tǒng)的應用與研究[J].科技通報，2014，30(11):131-135.

[11]錢勤，張減，張坤，等.用于入侵檢測及取證的冗余數(shù)據(jù)刪減技術研究[J].計算機科學，2014，41(11):252-258.

(責任編輯： 陳志賢 英文審校： 吳逢鐵)

Application of Improved Boyer Matching Algorithm in Snort Intrusion Detection

MA Xiaoyu1， LIU Shuanghong

(1. School of Science， Henan University of Engineering， Zhengzhou 451191， China；2. Department of Computer Science and Application， Zhengzhou University of Aeronautics， Zhengzhou 450046， China)

Abstract：In this paper， the application of Snort intrusion detection system is studied. An improved method based on Boyer algorithm is designed. This method first designs a statistical array， then executes the matching with two adjacent characters， and divides into three strategies to determine the maximum movement length. Experimental results show this improvement makes the maximum movement length more reasonable. Compared with the Boyer method， the proposed method is significantly lower than the number of characters method， the number of windows mobile number is significantly reduced， the execution time is significantly reduced.

Keywords：network security； intrusion detection； Snort system； Boyer algorithm

中圖分類號：TP 393.08

文獻標志碼：A

基金項目：河南省科技廳科研項目(102102310261)

通信作者：馬小雨(1978-)，男，講師，博士研究生，主要從事計算機網(wǎng)絡與安全的研究.E-mail:2622810975@qq.com.

收稿日期：2015-12-22

doi:10.11830/ISSN.1000-5013.2016.02.0168

文章編號：1000-5013(2016)02-0168-03