基于NP模式的報文檢測方法*

唐湘滟，程杰仁， 殷建平，龔德良

(1.海南大學信息科學技術學院,海南 海口 571101；2.國防科學技術大學計算機學院,湖南 長沙 410073；3.湘南學院,湖南 郴州 423000)

基于NP模式的報文檢測方法*

唐湘滟1，程杰仁1， 殷建平2，龔德良3

(1.海南大學信息科學技術學院,海南 海口 571101；2.國防科學技術大學計算機學院,湖南 長沙 410073；3.湘南學院,湖南 郴州 423000)

針對現有網絡入侵檢測方法中存在的不足，引入否定模式(NP)匹配的策略，提出了基于NP模式的報文檢測方法。該方法先從待測報文內容模式集合中找出NP模式，根據NP模式將待測數據流分段；然后通過模式匹配引擎對分段內容進行模式匹配。實驗結果表明，該方法能降低誤報率，減少報文匹配次數，提高檢測效率。

否定模式；模式匹配；入侵檢測；網絡安全

1 引言

隨著物聯網、云計算、大數據等新興技術的出現，對高速檢測海量網絡數據流的需求日益增加。模式匹配在入侵檢測系統各個關鍵環節中起著非常重要的作用[1～3]，其分為單模式匹配和多模式匹配兩類。模式匹配由最初的Boyer-Moore 算法[4]、KMP 算法[5]以及Commentz-Walter 算法[6]等發展到復雜、效率更高的多模式匹配[7～9]。由于單純的軟件實現方法已經不能滿足數以千計的模式匹配的實際要求，FPGA[10]、ASIC[11]、TCAM等支持并行處理的專用硬件設備被大量應用，以提高模式匹配速度[12]，當然這也增加了相應模塊的設計復雜性。盡管多模式匹配技術得到了廣泛的應用，其匹配速度比單模式匹配的速度快得多，但是仍然需要依賴硬件和一些輔助的軟件策略方式實現報文檢測[13,14]，而且目前基于FPGA 等器件和Snort 規則集實現報文檢測的方法，通常吞吐量不超過10 GBps[15]。為提高報文檢測的吞吐量，滿足用戶的更高需求，本文基于否定匹配的思想提出了基于NP模式的報文檢測方法。

2 否定模式匹配

傳統的入侵檢測模式匹配方法是根據給定的模式集合，在待檢網絡流中找出相同的字符串子鏈，這種檢測方法消耗的計算資源和時間較多。因此，本文結合傳統的入侵檢測模式匹配方法，基于否定模式NP(Negative Pattern)檢測方法來實現報文檢測，以減少匹配的次數，降低成本，提高效率。

定義1假定模式集合P={V1,V2,…,Vn}，否定模式NP是P的一個NP,當且僅當NP的任何K(K>1)字節后綴不是Vi的子集，其中Vi∈P,i=1,2,…,n。

假定模式集合P={virus，worm}，根據否定模式定義，字符串模式“free”是P一個否定模式。因為“free”的任何K(K>1)字節后綴集合T={ee,ree,free}，P的K(K>1) 字節子集S={vi,ir,ru,us,wo,or,rm,vir,iru,rus,wor,orm, viru,irus,worm, virus}，有?x∈T,則x?S。

定理1假定模式NP={P1,P2,…,Pn}是某待檢測的數據流F的一個否定模式，則根據Pi(Pi∈NP,i=1,2,…,n)的最后兩個字節將F分段后生成的字符串模式不會橫跨兩個相鄰的數據段。

證明假設NP為待檢數據流F的一個否定模式， Pi∈NP,i=1,2,…,n。(1)當n=1時，定理1顯然成立；(2)當n>1時，假設存在一個模式 Vi∈F(其中i=1,2,…,k)橫跨兩個相鄰的數據段，那么Vi至少有兩個字節長，也就是Vi的最后兩個字節，所以Vi一定包含一個NP的K(K>1)字節后綴，而根據否定模式定義，Vi不能夠包含NP的后綴，所以這樣的Vi是不存在的，定理1成立。綜合(1)和(2)可知，定理1成立。

□

假定S={virus，worm}，某待檢測的數據流F為 “…using computervirustorefertoaworm…”，通過否定模式定義可以得知{…ngc,erv, ust, ert, tow…}是S的NP模式，所以根據NP模式{…ngc,erv, ust, ert, tow…}中各元素最后兩個字節將F分段后生成的字符串模式為“…using”, “computer”, “virus”, “toa”, “refer”, “to” , “worm…”。該數據流F采用NP模式分段后沒有丟失特征，即所有的模式都可以檢測出來。因此，解決問題的關鍵是在報文內容中精確地找到NP,以確保正確分段和降低錯誤率。

3 基于NP模式的報文檢測方法

3.1 基于模式匹配的內容檢測機制的體系結構

圖1是基于模式匹配的內容檢測機制的體系結構。從圖1中可以看出系統檢測的主要流程，系統捕獲的數據包通過“網絡協議分析”把報文的頭部和內容分離開，根據一定的規則把可能含有入侵信號的報文內容送到“報文內容檢測”中，利用“模式匹配引擎”對報文內容做檢測，即根據NP模式把待測數據流分段，然后再對段內容進行模式匹配，檢測出可疑的數據包，以有效地提高入侵檢測的工作效率。

Figure 1 Content Detectingarchitecture based on pattern matching圖1 基于模式匹配的內容檢測機制的體系結構

3.2 報文內容檢測中否定模式的數據結構

圖1中系統送到“報文內容檢測”中的是報文內容的字節流，通過“模式匹配引擎”基于NP模式對待測字節流進行分段和匹配，根據檢測結果丟棄無入侵信號的數據包，將可疑的數據包傳送到入侵檢測的下一環節。

表1是關于報文內容檢測機制的NP表數據結構。對于一個待匹配的模式集合，從相應的NP表可以確定是否組成NP模式。綜合考慮匹配次數、時間、計算資源等各方面的因素，表1中否定模式的長度設為兩個字節，實驗結果也表明兩個字節比較好。

Table 1 NP table of packet content filtering表1 報文內容過濾的NP表

3.3 基于NP匹配的報文內容檢測的原理

“報文內容檢測”主要是基于NP模式匹配結果來檢測不含入侵信號的報文，以便排除正常流的干擾，提高報文檢測效率。由于NP匹配是一個否定模式，而且找出所有的NP模式也許需要花費很多的時間，所以不需要找出所有的NP模式。

查找NP可以從某一特定位置開始不停地查找直到找到NP位置，然后跳過檢測窗口大小w字節再重復進行下一次查找。該查找方法需要解決兩個主要問題：(1)循環次數不確定性和不可控性，盡管已經證明在實際例子中NP是經常出現的，但對一些特殊情況找到NP的概率仍然是不確定的；(2)關于內容檢測的并行性問題。為了解決這兩個問題，本文采用多層次NP匹配算法，利用遞歸方式查找NP。即M(M

算法1多層次NP匹配算法

NPSeek(byte*C,intiSL,intw,intiR,intN){

/*C:thebufferofcontent; C[i,k]:thek-bytesbufferstartingfromi;iSL:thelengthofthesegment;w:thewidthofslidingwindows;iR:theroundoflooking；N:thewidthoftheNPs,inthisprototype, N=2*/

if (iR>w-1 oriSL<2*w)

EPM_Seek(C,iSL); //EPM the segment directly

formfrom 1 toMparallel_do {

ifIsNP(C[iR+m*w-1,N])

NPMatch[m]=TRUE;

}

lastNP=0;

forifrom 1 toMdo {

if (NPMatch[i]==TRUE) { /*the following can be done in a new thread*/

NPSeek(C+lastNP*w, (i-lastNP)*w,w,iR+1,N);

lastNP=i;

}

}

Recursion_NP(byte*C,intLen,intw,intN){

/*C:bufferofcontent; C[i,k]:thek-bytesbufferstartingfromi;Len:lengthofcontent,i.e. Len=|C|；N:thewidthoftheNPs;w:thewidthoftheslidingwindowoftheEPMengine*/

NPSeek(C,Len,w, 0,N);

}

4 實驗結果與分析

4.1 NP查找匹配次數的評估

NP匹配次數是由多層次NP匹配算法的遞歸深度決定的。設數據流的總長度為L，檢測窗口的大小為w，遞歸深度為Dr。假設每次查找都可以找到NP，則需要L/w次NP匹配。假設NP匹配的概率是Rh，0≤Rh<1，則NP查找次數的最大值為：

(1)

在最壞情況下Rh→0，則有:

(2)

4.2 檢測次數分析

由4.1節可知，報文檢測次數共計(n-1)(w-1)，其中n為報文基于NP模式分割的段數，w為窗口的大小，則有：

(3)

因此，降低的檢查次數為：

(4)

當Dr=w-1(Dr

(5)

若L?w,n?1,即有L-w+1≈L，[1-(1-Rh)w-1]×L/w-1≈[1-(1-Rh)w-1]×L/w,則降低檢測次數的概率為：

(6)

基于公式(6)有:

(1)明顯有dRsave/dRh≥0，因此隨著NP匹配概率(Rh)的增大，Rsave也增大。

(2)由d[1-(1-Rh)w-1]/dw≥0，d[(w-1)/w]/dw≥0,可得dRsave/dw≥0，則w越大，Rsave也越大。

由圖2可見，當檢測窗口值越大，降低檢測次數的概率的增長速度就越快，而且收斂速度越快；當NP匹配的概率小于30%時，降低檢測次數的概率的收斂速度由Rh決定。

Figure 2 Linear relationship between the probability of NP matching and the size of the window圖2 檢測窗口的大小與NP匹配的概率關系

4.3 實驗結果

本節實驗所用的模式集合是來自Snort模式集合，該模式集合長度分布狀態如圖4所示，數據流集合是來自MIT的數據集[12]。本節將分析4.2節中Rh、Dr、w等各個參數的關系。經測試，Snort模式集合有62 647個兩字節NP，因此NP匹配的概率為：Rh=62674/216=95.63%。在處理的1 376 598個報文中，大約52%報文含有內容(總長度是242 576 387B)，所以平均報文流大小是337B。當w=4,8,12,16,遞歸深度Dr為w-1，則Rsave分別約為74.77%、87.23%、91.39%、93.46%。

Figure 3 Length distribution state of Snort mode set圖3 Snort模式集合長度分布狀態

5 結束語

大規模網絡流量環境中檢測報文內容需要消耗大量計算資源和時間。本文基于否定模式匹配的思想，提出了基于NP模式的報文檢測方法。該方法根據NP模式把待測數據流分段，然后再對段內容進行模式匹配，根據匹配結果檢測出可疑的數據報文。實驗結果表明該方法能避免降低誤報，減少檢測次數，提高報文檢測效率。

[1] Artan N S,Chao H J. TriBiCa:Trie bitmap content analyzer for high-speed network intrusion detection[C]∥Proc of IEEE INFOCOM’07, 2007:125-133.

[2] Chang Y, Tsai M, Chung Y. Multi-character processor array for pattern matching in network intrusion detection system[C]∥Proc of the 22nd International Conference on Advanced Information Networking and Applications, 2008:1.

[3] Artan N S, Chao H J. Design and analysis of a multipacket signature detection system[J]. International Journal of Security and Network, 2007,2(1):122-136.

[4] Boyer R S, Moore J S. A fast string searching algorithm[J]. Communications of the ACM, 1977,20(10):762-772.

[5] Dharmapurikar S,Lockwood J.Fast and scalable pattern matching for network intrusion detection systems[J]. IEEE Journal on Selected Areas in Communications, 2006,24(10):1781-1792.

[6] Ramaswamy R, Kencl L, Iannaccone G. Approximate fingerprinting to accelerate pattern matching[C]∥Proc of the 6the ACM SIGCOMM Conference on Internet Measurement, 2006:1.

[7] Liu Yan-bing, Shao Yan, Wang Yong, et al. A multiple string matching algorithms for large-scale URL filtering[J]. Chinese Journal of Computer,2014,5:1159-1169.(in Chinese)

[8] Chu Yan-jie,Li Yun-zhao,Wei Qiang. Swm: An improved multi-pattern matching algorithm and application[J]. Journal of Xidian University,2014,6:197-203.(in Chinese)

[9] Song Tian, Li Dong-ni, Wang Dong-sheng, et al. Journal of software[J]. Memory Efficient Algorithm and Architecture for Multi-Pattern Matching, 2013,7:1650-1665.(in Chinese)

[10] Dharmapurikar S, Krishnamurthy P, Sproull T S, et al. Deep packet inspection using parallel bloom filters[J]. IEEE Micro, 2004,24(1):52-61.

[11] Lunteren J V. High-performance pattern-matching engine for intrusion detection[C]∥Proc of IEEE INFOCOM’06, 2006:1.

[12] Yu F,Katz R H,Lakshman T V.Igabit rate packet pattern-matching using TCAM[C]∥Proc of the 12th IEEE International Conference on Network Protocols, 2004:174-183.

[13] Juniper networks intrusion prevention solutions[EB/OL].[2013-11-12].http://www.juniper.net/products_and_services/intrusion_prevention_solutions/index.html.

[14] Fortinet-Muti-threat security systems for real time network protection[EB/OL].[2013-12-25].http://www.fortinet.com/.

[15] Snor intrusion detection system[EB/OL].[2014-03-16].http://www.snort.org.

附中文參考文獻：

[7] 劉燕兵,邵妍,王勇,等. 一種面向大規模URL過濾的多模式串匹配算法[J]. 計算機學報,2014,5:1159-1169.

[8] 褚衍杰,李云照,魏強. SWM:一種改進的多模式匹配算法及應用[J]. 西安電子科技大學學報,2014,6:197-203.

[9] 嵩天,李冬妮,汪東升,等. 存儲有效的多模式匹配算法和體系結構[J]. 軟件學報,2013,7:1650-1665.

TANGXiang-yan,born in 1981,MS,her research interests include network security, library and information mining.

ApacketdetectionmethodbasedonNegativePattern

TANG Xiang-yan1,CHENG Jie-ren1,YIN Jian-ping2,GONG De-liang3

(1.College of Information Science & Technology,Hainan University,Haikou 571101;2.College of Computer Science,National University of Defense Technology,Changsha 410037;3.Xiangnan University,Chenzhou 423000,China)

To solve the problems in intrusion detection based on pattern matching, we present a packet detection method based on negative pattern,which uses the negative pattern matching strategy.Firstly,the method detects the NP pattern in the to-be-detected packets and divides the data into segments according to NP pattern.Secondly,the system detects the data segments by NP pattern.The experimental results show that the method can reduce the false alarm rate and improve the detection efficiency of the system.

negative Pattern；pattern match；intrusion detection；network security

1007-130X(2014)11-2128-04

2014-05-20;

：2014-07-20

國家自然科學基金資助項目(61363071,61100194,61232016,60970034);海南省自然科學基金資助項目(614220);湖南省教育科學十二五規劃課題資助項目(XJK011BXJ004);海南大學D類人才啟動基金(kyqd1328);海南大學青年基金資助項目(qnjj1444)

TP393.08

：A

10.3969/j.issn.1007-130X.2014.11.012

唐湘滟(1981),女,湖南邵陽人，碩士，研究方向為網絡安全和圖書情報挖掘。E-mail:Tangxy36@163.com

通信地址：571101 海南省海口市學院路4號1棟102

Address:Room 102,Building 1,4 Xueyuan Rd,Haikou 571101,Hainan,P.R.China