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

(1.海南大學(xué)信息科學(xué)技術(shù)學(xué)院,海南 ?？?571101；2.國防科學(xué)技術(shù)大學(xué)計(jì)算機(jī)學(xué)院,湖南 長沙 410073；3.湘南學(xué)院,湖南 郴州 423000)

基于NP模式的報(bào)文檢測方法*

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

(1.海南大學(xué)信息科學(xué)技術(shù)學(xué)院,海南 ?？?571101；2.國防科學(xué)技術(shù)大學(xué)計(jì)算機(jī)學(xué)院,湖南 長沙 410073；3.湘南學(xué)院,湖南 郴州 423000)

針對現(xiàn)有網(wǎng)絡(luò)入侵檢測方法中存在的不足，引入否定模式(NP)匹配的策略，提出了基于NP模式的報(bào)文檢測方法。該方法先從待測報(bào)文內(nèi)容模式集合中找出NP模式，根據(jù)NP模式將待測數(shù)據(jù)流分段；然后通過模式匹配引擎對分段內(nèi)容進(jìn)行模式匹配。實(shí)驗(yàn)結(jié)果表明，該方法能降低誤報(bào)率，減少報(bào)文匹配次數(shù)，提高檢測效率。

否定模式；模式匹配；入侵檢測；網(wǎng)絡(luò)安全

1 引言

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

2 否定模式匹配

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

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

假定模式集合P={virus，worm}，根據(jù)否定模式定義，字符串模式“free”是P一個(gè)否定模式。因?yàn)椤癴ree”的任何K(K>1)字節(jié)后綴集合T={ee,ree,free}，P的K(K>1) 字節(jié)子集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}是某待檢測的數(shù)據(jù)流F的一個(gè)否定模式，則根據(jù)Pi(Pi∈NP,i=1,2,…,n)的最后兩個(gè)字節(jié)將F分段后生成的字符串模式不會(huì)橫跨兩個(gè)相鄰的數(shù)據(jù)段。

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

□

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

3 基于NP模式的報(bào)文檢測方法

3.1 基于模式匹配的內(nèi)容檢測機(jī)制的體系結(jié)構(gòu)

圖1是基于模式匹配的內(nèi)容檢測機(jī)制的體系結(jié)構(gòu)。從圖1中可以看出系統(tǒng)檢測的主要流程，系統(tǒng)捕獲的數(shù)據(jù)包通過“網(wǎng)絡(luò)協(xié)議分析”把報(bào)文的頭部和內(nèi)容分離開，根據(jù)一定的規(guī)則把可能含有入侵信號(hào)的報(bào)文內(nèi)容送到“報(bào)文內(nèi)容檢測”中，利用“模式匹配引擎”對報(bào)文內(nèi)容做檢測，即根據(jù)NP模式把待測數(shù)據(jù)流分段，然后再對段內(nèi)容進(jìn)行模式匹配，檢測出可疑的數(shù)據(jù)包，以有效地提高入侵檢測的工作效率。

Figure 1 Content Detectingarchitecture based on pattern matching圖1 基于模式匹配的內(nèi)容檢測機(jī)制的體系結(jié)構(gòu)

3.2 報(bào)文內(nèi)容檢測中否定模式的數(shù)據(jù)結(jié)構(gòu)

圖1中系統(tǒng)送到“報(bào)文內(nèi)容檢測”中的是報(bào)文內(nèi)容的字節(jié)流，通過“模式匹配引擎”基于NP模式對待測字節(jié)流進(jìn)行分段和匹配，根據(jù)檢測結(jié)果丟棄無入侵信號(hào)的數(shù)據(jù)包，將可疑的數(shù)據(jù)包傳送到入侵檢測的下一環(huán)節(jié)。

表1是關(guān)于報(bào)文內(nèi)容檢測機(jī)制的NP表數(shù)據(jù)結(jié)構(gòu)。對于一個(gè)待匹配的模式集合，從相應(yīng)的NP表可以確定是否組成NP模式。綜合考慮匹配次數(shù)、時(shí)間、計(jì)算資源等各方面的因素，表1中否定模式的長度設(shè)為兩個(gè)字節(jié)，實(shí)驗(yàn)結(jié)果也表明兩個(gè)字節(jié)比較好。

Table 1 NP table of packet content filtering表1 報(bào)文內(nèi)容過濾的NP表

3.3 基于NP匹配的報(bào)文內(nèi)容檢測的原理

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

查找NP可以從某一特定位置開始不停地查找直到找到NP位置，然后跳過檢測窗口大小w字節(jié)再重復(fù)進(jìn)行下一次查找。該查找方法需要解決兩個(gè)主要問題：(1)循環(huán)次數(shù)不確定性和不可控性，盡管已經(jīng)證明在實(shí)際例子中NP是經(jīng)常出現(xiàn)的，但對一些特殊情況找到NP的概率仍然是不確定的；(2)關(guān)于內(nèi)容檢測的并行性問題。為了解決這兩個(gè)問題，本文采用多層次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 實(shí)驗(yàn)結(jié)果與分析

4.1 NP查找匹配次數(shù)的評(píng)估

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

(1)

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

(2)

4.2 檢測次數(shù)分析

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

(3)

因此，降低的檢查次數(shù)為：

(4)

當(dāng)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,則降低檢測次數(shù)的概率為：

(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可見，當(dāng)檢測窗口值越大，降低檢測次數(shù)的概率的增長速度就越快，而且收斂速度越快；當(dāng)NP匹配的概率小于30%時(shí)，降低檢測次數(shù)的概率的收斂速度由Rh決定。

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

4.3 實(shí)驗(yàn)結(jié)果

本節(jié)實(shí)驗(yàn)所用的模式集合是來自Snort模式集合，該模式集合長度分布狀態(tài)如圖4所示，數(shù)據(jù)流集合是來自MIT的數(shù)據(jù)集[12]。本節(jié)將分析4.2節(jié)中Rh、Dr、w等各個(gè)參數(shù)的關(guān)系。經(jīng)測試，Snort模式集合有62 647個(gè)兩字節(jié)NP，因此NP匹配的概率為：Rh=62674/216=95.63%。在處理的1 376 598個(gè)報(bào)文中，大約52%報(bào)文含有內(nèi)容(總長度是242 576 387B)，所以平均報(bào)文流大小是337B。當(dāng)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模式集合長度分布狀態(tài)

5 結(jié)束語

大規(guī)模網(wǎng)絡(luò)流量環(huán)境中檢測報(bào)文內(nèi)容需要消耗大量計(jì)算資源和時(shí)間。本文基于否定模式匹配的思想，提出了基于NP模式的報(bào)文檢測方法。該方法根據(jù)NP模式把待測數(shù)據(jù)流分段，然后再對段內(nèi)容進(jìn)行模式匹配，根據(jù)匹配結(jié)果檢測出可疑的數(shù)據(jù)報(bào)文。實(shí)驗(yàn)結(jié)果表明該方法能避免降低誤報(bào)，減少檢測次數(shù)，提高報(bào)文檢測效率。

[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.

附中文參考文獻(xiàn)：

[7] 劉燕兵,邵妍,王勇,等. 一種面向大規(guī)模URL過濾的多模式串匹配算法[J]. 計(jì)算機(jī)學(xué)報(bào),2014,5:1159-1169.

[8] 褚衍杰,李云照,魏強(qiáng). SWM:一種改進(jìn)的多模式匹配算法及應(yīng)用[J]. 西安電子科技大學(xué)學(xué)報(bào),2014,6:197-203.

[9] 嵩天,李冬妮,汪東升,等. 存儲(chǔ)有效的多模式匹配算法和體系結(jié)構(gòu)[J]. 軟件學(xué)報(bào),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

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

TP393.08

：A

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

唐湘滟(1981),女,湖南邵陽人，碩士，研究方向?yàn)榫W(wǎng)絡(luò)安全和圖書情報(bào)挖掘。E-mail:Tangxy36@163.com

通信地址：571101 海南省?？谑袑W(xué)院路4號(hào)1棟102

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