李 陽,李 青,張 霞

信息工程大學(xué) 信息系統(tǒng)工程學(xué)院,鄭州 450002)(*通信作者電子郵箱liqing0206@163.com)

基于離散序列報(bào)文的協(xié)議格式特征自動(dòng)提取算法

李 陽,李 青*,張 霞

信息工程大學(xué) 信息系統(tǒng)工程學(xué)院,鄭州 450002)(*通信作者電子郵箱liqing0206@163.com)

針對缺少會話信息的離散序列報(bào)文,提出一種基于離散序列報(bào)文的協(xié)議格式(SPMbFSC)特征自動(dòng)提取算法。SPMbFSC在對離散序列報(bào)文進(jìn)行聚類的基礎(chǔ)上,通過改進(jìn)的頻繁模式挖掘算法提取出協(xié)議關(guān)鍵字,進(jìn)一步對協(xié)議關(guān)鍵字進(jìn)行選擇,篩選出協(xié)議格式特征。仿真結(jié)果表明,SPMbFSC在以單個(gè)報(bào)文為顆粒度的識別中對FTP、HTTP等六種協(xié)議的識別率均能達(dá)到95%以上,在以會話為顆粒度的識別中識別率可達(dá)90%。同等實(shí)驗(yàn)條件下性能優(yōu)于自適應(yīng)特征(AdapSig)提取方法。實(shí)驗(yàn)結(jié)果表明SPMbFSC不依賴會話數(shù)據(jù)的完整性,更符合實(shí)際應(yīng)用中由于接收條件限制導(dǎo)致會話信息不完整的情形。

離散序列報(bào)文;協(xié)議關(guān)鍵字提取;自適應(yīng)特征挖掘;格式特征;協(xié)議識別

0 引言

網(wǎng)絡(luò)流量的準(zhǔn)確識別和分類是提供差異性服務(wù)質(zhì)量保障、入侵檢測、流量監(jiān)控及計(jì)費(fèi)管理等的基礎(chǔ)。隨著網(wǎng)絡(luò)應(yīng)用的快速發(fā)展,傳統(tǒng)的基于端口號[1]的網(wǎng)絡(luò)流量識別方法逐漸失效;基于流(Flow)統(tǒng)計(jì)特性[2]的方法則無法對應(yīng)用協(xié)議進(jìn)行精確識別;而基于深度包檢測[3-4]的方法應(yīng)為應(yīng)用簡單、準(zhǔn)確率高,已經(jīng)成為目前在實(shí)際中廣泛應(yīng)用的方法。

目前已有的研究成果主要是基于完整的會話流來進(jìn)行應(yīng)用協(xié)議的格式特征提取。Wang等[5-6]分別提出以會話流為單位,采用X-means聚類算法及粗糙集算法實(shí)現(xiàn)混合協(xié)議的盲聚類識別,但由于兩人均不采用任何先驗(yàn)信息,故無法保證識別結(jié)果的準(zhǔn)確性；劉興彬等[7]提出基于Apriori算法[8]的報(bào)文載荷協(xié)議關(guān)鍵字提取算法,準(zhǔn)確率較高,但其算法依舊依賴完整會話流且效率較低；王變琴等[9-10]針對其效率低下的問題分別提出基于FP-growth[11]的改進(jìn)算法AdapSig[9]和SPFPA算法來進(jìn)行改進(jìn),算法效率有了很大提高,但協(xié)議關(guān)鍵字提取仍然在完整會話流中進(jìn)行。在實(shí)際應(yīng)用環(huán)境中,由于接收條件的限制,使得具有完整會話流的應(yīng)用協(xié)議數(shù)據(jù)接收較為困難,接收到的數(shù)據(jù)多為離散序列報(bào)文而非完整會話流,在這種較為苛刻的條件下,如何自動(dòng)提取協(xié)議的格式特征是該領(lǐng)域還沒有解決的問題。

為解決上述問題,本文提出一種基于離散序列報(bào)文的協(xié)議格式(Separate Protocol Message based Format Signature Construction, SPMbFSC)特征自動(dòng)提取算法,該算法在挖掘應(yīng)用協(xié)議關(guān)鍵字的基礎(chǔ)上,進(jìn)一步篩選由其組成的格式特征。

本文主要工作有:1)提出SPMbFSC算法,不依賴會話流,更符合實(shí)際應(yīng)用情形,適用條件更廣;2)提出一種改進(jìn)的DBSCAN(Density-Based Spatial Clustering of Applications with Noise)[12]聚類算法,能有效地在報(bào)文層面對應(yīng)用協(xié)議報(bào)文進(jìn)行相似性聚類;3)提出一種基于PrefixSpan[13]的協(xié)議關(guān)鍵字提取算法PositionSpan,能高效地進(jìn)行協(xié)議關(guān)鍵字提取,同時(shí)可以進(jìn)一步挖掘由協(xié)議關(guān)鍵字構(gòu)成的格式特征。

1 問題描述與分析

定義1 離散序列報(bào)文(Discrete Series Protocol Message)是指會話中由于次序錯(cuò)亂或部分缺失而形成的報(bào)文集合,記為MS={m1,m2,…,mJ},其中:mj(1≤j≤J)為報(bào)文。而會話(Session)是指一次通信建立和結(jié)束之間的所有報(bào)文構(gòu)成的序列,記為s=m1m2…mN,其中mi(1≤i≤N)為按照特定次序排列的報(bào)文。在本文中,約定報(bào)文內(nèi)可打印的字節(jié)或字符串用ASCII碼格式表示,不可打印的字節(jié)或字符串用形為“xff”的十六進(jìn)制格式表示,其中ff表示兩位十六進(jìn)制數(shù)字。

實(shí)際環(huán)境中接收到的數(shù)據(jù)多為離散序列報(bào)文,其與傳統(tǒng)的完整會話相比具有兩方面的特點(diǎn)及困難:1)無序性;2)混疊性。無序性是指接收到的報(bào)文只有其到達(dá)接收端的時(shí)間先后順序,由于會話信息的缺失使得無法在接收端按照報(bào)文原有次序進(jìn)行會話重組;混疊性是指報(bào)文在傳輸過程中由于路由選擇、鏈路質(zhì)量等問題造成的損失不可估計(jì),使得接收端接收到的報(bào)文是經(jīng)過重傳、丟失等問題后的混合報(bào)文集合,且無法借助其自身或會話信息進(jìn)行去冗余處理。由于以上困難的存在,使得目前基于完整會話的協(xié)議格式特征提取算法難以適用。

圖1 系統(tǒng)結(jié)構(gòu)

定義2 協(xié)議關(guān)鍵字(Keyword)是指位置和頻度滿足一定要求的字符串。同種應(yīng)用協(xié)議的關(guān)鍵字組成關(guān)鍵字集合,記為K={k1,k2,…,kp-1,kp},其中,kp(1≤p≤P)為關(guān)鍵字,可以是協(xié)議的命令碼、版本號、狀態(tài)碼等。

協(xié)議關(guān)鍵字按其在報(bào)文中出現(xiàn)的位置可分為兩類:固定位置協(xié)議關(guān)鍵字和非固定位置協(xié)議關(guān)鍵字。其中固定位置協(xié)議關(guān)鍵字是指其在報(bào)文中出現(xiàn)的偏移位置固定,多數(shù)是應(yīng)用層協(xié)議報(bào)文頭部中的特征字符串,包括協(xié)議名稱、版本號等,也可以是應(yīng)用層協(xié)議控制信息中的特征字符串,包括命令碼、狀態(tài)碼、定界符等,一般出現(xiàn)在一個(gè)報(bào)文開頭或最后的若干個(gè)字節(jié)處;而非固定位置協(xié)議關(guān)鍵字為出現(xiàn)位置偏移不固定的特征字符串。

定義3 協(xié)議格式特征是指能夠識別應(yīng)用協(xié)議類型的協(xié)議關(guān)鍵字或協(xié)議關(guān)鍵字組合。

通常用固定位置的協(xié)議關(guān)鍵字或其組合就可以對應(yīng)用協(xié)議進(jìn)行精確識別。本文從樣本報(bào)文集中自動(dòng)提取固定位置的協(xié)議關(guān)鍵字,進(jìn)而篩選構(gòu)造只含有固定位置協(xié)議關(guān)鍵字的協(xié)議格式特征。

2 協(xié)議格式特征提取算法

針對第1章介紹的離散序列報(bào)文協(xié)議格式特征提取困難問題,本文提出SPMbFSC算法,重點(diǎn)解決兩大問題:1)離散序列報(bào)文的相似聚類;2)協(xié)議關(guān)鍵字提取及選擇。離散序列報(bào)文由于其無序性及混疊性的特點(diǎn),使其中攜帶控制類信息及業(yè)務(wù)類信息的報(bào)文混合交疊無法區(qū)分,導(dǎo)致協(xié)議格式特征的提取困難,從而如何將兩類報(bào)文彼此區(qū)分,即報(bào)文的相似聚類就成了必須解決的問題;而針對以協(xié)議報(bào)文為顆粒度的協(xié)議格式特征提取算法,如何正確、高效地進(jìn)行協(xié)議關(guān)鍵字提取同時(shí)進(jìn)一步篩選由其構(gòu)成的具有有效識別能力的協(xié)議格式特征,即協(xié)議關(guān)鍵字提取及選擇也是必須要解決的問題。

SPMbFSC算法系統(tǒng)如圖1所示,對要解決的兩大問題,采用四個(gè)主要步驟:1)首先對收集到的報(bào)文進(jìn)行預(yù)處理,初步去除掉只攜帶業(yè)務(wù)類信息的報(bào)文,生成樣本報(bào)文集;2)利用改進(jìn)的DBSCAN聚類算法對報(bào)文集進(jìn)行聚類,使具有相似控制類信息或業(yè)務(wù)類信息的報(bào)文聚類成簇;3)在每一個(gè)報(bào)文簇集合中進(jìn)行協(xié)議關(guān)鍵字提取,挖掘其協(xié)議關(guān)鍵字集合;4)進(jìn)行協(xié)議關(guān)鍵字選擇,篩選出具有有效識別能力的協(xié)議格式特征用于分類識別。

2.1 數(shù)據(jù)預(yù)處理

大多數(shù)應(yīng)用協(xié)議都具有控制類信息和業(yè)務(wù)類信息兩種協(xié)議內(nèi)容,且其在報(bào)文中的分布有如下特點(diǎn):攜帶控制類信息的報(bào)文長度相對較短,內(nèi)容種類相對固定;攜帶業(yè)務(wù)類信息的報(bào)文長度相對較長,內(nèi)容分布隨機(jī)性強(qiáng),存在分片傳輸?shù)目赡?且通常出現(xiàn)在攜帶控制類信息的報(bào)文之后。

基于上述報(bào)文分布的特點(diǎn),在離散序列報(bào)文的條件下提出一種基于報(bào)文長度截取的數(shù)據(jù)預(yù)處理算法,初步剔除只含有業(yè)務(wù)類信息的報(bào)文。具體做法為首先將報(bào)文按照方向分成兩類,對同一方向上的報(bào)文按照長度進(jìn)行排列,之后依據(jù)長度閾值L的設(shè)定,假定長度小于L的報(bào)文攜帶控制類信息而予以保留進(jìn)行下一步驟的協(xié)議關(guān)鍵字提取,而假定長度大于L的報(bào)文不攜帶控制類信息而只攜帶業(yè)務(wù)類信息予以舍棄。對于保留的報(bào)文,采用目前常用的方法對每個(gè)報(bào)文提取前后各k個(gè)字節(jié)[9，14]的數(shù)據(jù)來代替原有報(bào)文,用以提高協(xié)議關(guān)鍵字提取的準(zhǔn)確性和效率。

2.2 改進(jìn)的DBSCAN聚類算法

針對離散序列報(bào)文的特點(diǎn),本文對經(jīng)過數(shù)據(jù)預(yù)處理的報(bào)文提出一種改進(jìn)的搜索半徑自適應(yīng)的DBSCAN算法來進(jìn)行聚類,使得攜帶有相似信息的報(bào)文聚類成簇。算法步驟為:1)設(shè)定輸入報(bào)文距離中位數(shù)的1/8為初始搜索半徑rs;2)每次迭代時(shí)增加一倍的rs為新的搜索半徑rs′。重復(fù)步驟2)直至滿足終止條件。報(bào)文之間的距離采用歐幾里得距離來衡量:

(1)

其中:l為報(bào)文長度。為最大限度地利用每一個(gè)報(bào)文,同時(shí)減少聚類過程中過擬合現(xiàn)象的影響,本文聚類算法的終止條件設(shè)定如下:1)設(shè)定聚類過程中不屬于任何一簇的噪點(diǎn)報(bào)文數(shù)不得超過總報(bào)文數(shù)的5%;2)設(shè)定聚類簇?cái)?shù)的最大值Nmax,避免過多的過擬合簇產(chǎn)生。

較之傳統(tǒng)的DBSCAN算法,本文的聚類算法只用預(yù)先給出代表搜索精細(xì)程度的每一簇最小樣本數(shù)目n,而搜索半徑及聚類簇?cái)?shù)自適應(yīng)確定,從而減少人工參與,克服了傳統(tǒng)DBSCAN算法參數(shù)設(shè)定需要人工經(jīng)驗(yàn)的弊端。

2.3 協(xié)議關(guān)鍵字提取

在報(bào)文聚類的基礎(chǔ)上,對每一簇報(bào)文集中協(xié)議關(guān)鍵字的提取主要由頻繁模式挖掘算法來完成,主要用到支持度測度。

定義5 頻繁字符串。給定報(bào)文集M,字符串str及最小支持度minsup∈(0,1),當(dāng)sup(str)≥minsup時(shí),稱該str為M中的頻繁字符串。M中的所有頻繁字符串組成頻繁字符串集F。

性質(zhì)1 如果字符串x屬于頻繁字符串集F,即x∈F,則x的所有子集字符串都屬于F;反之若x?F,則x的所有超集字符串都不屬于F。

文獻(xiàn)[15]表明,PrefixSpan算法是比Apriori及FP-growth算法效率更高的頻繁模式挖掘算法,結(jié)合本文要挖掘的只含有固定位置協(xié)議關(guān)鍵字的協(xié)議格式特征目標(biāo),本文提出一種基于PrefixSpan的PositionSpan算法。其基本思想為:以報(bào)文中字節(jié)位置為依據(jù),首先按照偏移(字節(jié)距離報(bào)文首字節(jié)的位置,規(guī)定首字節(jié)的偏移量為零)依次挖掘出報(bào)文不同位置上的1-位置頻繁字節(jié)項(xiàng);然后依據(jù)PrefixSpan算法的映射思想將1-位置頻繁字節(jié)項(xiàng)依據(jù)位置的先后次序進(jìn)行映射拼接得到頻繁字符串集。下面給出1-位置頻繁字節(jié)項(xiàng)的定義及PositionSpan算法的詳細(xì)步驟。

定義6 1-位置頻繁字節(jié)項(xiàng)。依據(jù)報(bào)文中各字節(jié)距離首字節(jié)偏移的位置,依次挖掘出不同位置上的頻繁字節(jié),使字節(jié)值與字節(jié)位置相關(guān)聯(lián),其結(jié)果稱為1-位置頻繁字節(jié)項(xiàng),表示為:Byte=(Byte.loc,Byte.val),其中Byte.loc為字節(jié)所在報(bào)文的偏移位置,Byte.val為字節(jié)內(nèi)二進(jìn)制數(shù)的值。所有1-位置頻繁字節(jié)項(xiàng)構(gòu)成1-位置頻繁字節(jié)項(xiàng)集B1={Byte1,Byte2,…,Byten-1,Byten},其中Byten(1≤n≤N)為1-位置頻繁字節(jié)項(xiàng)。

PositionSpan算法的算法步驟為:1)首先在第一次掃描數(shù)據(jù)庫時(shí)挖掘出所有的1-位置頻繁字節(jié)項(xiàng),并構(gòu)成1-位置頻繁字節(jié)項(xiàng)集B1。2)將B1中的1-位置頻繁字節(jié)項(xiàng)按照位置的先后順序進(jìn)行排序,將位置最前面的兩個(gè)不同位置的1-位置頻繁字節(jié)項(xiàng)組合構(gòu)成2-位置頻繁字節(jié)項(xiàng)B2。3)計(jì)算B2的支持度,若為頻繁,則繼續(xù)加入第三個(gè)位置的1-位置頻繁字節(jié)項(xiàng)構(gòu)成3-位置頻繁字節(jié)項(xiàng)B3;若為不頻繁,由性質(zhì)1知此B2為一個(gè)頻繁字符串同時(shí)停止拼接。4)若此頻繁字符串為全新的字符串則加入F否則予以舍棄。迭代步驟2)～4)直至算法結(jié)束得到最終的協(xié)議頻繁字符串集合F。

2.4 協(xié)議關(guān)鍵字選擇

協(xié)議關(guān)鍵字提取得到的關(guān)鍵字還包含很多冗余,不能作為最后的分類依據(jù)。協(xié)議關(guān)鍵字只有在滿足一定的約束條件下才能構(gòu)成協(xié)議的格式特征:1)協(xié)議格式特征必須是存在于同一個(gè)報(bào)文中且位置互不重疊的協(xié)議關(guān)鍵字組合;2)協(xié)議格式特征必須具備有效的識別區(qū)分能力。針對上述條件1,由本文PositionSpan算法的設(shè)計(jì)特性予以滿足;而對條件2,本文給出如下規(guī)則對協(xié)議關(guān)鍵字進(jìn)行初步篩選。

規(guī)則1 構(gòu)成協(xié)議格式特征的協(xié)議關(guān)鍵字組合必須包含三個(gè)或三個(gè)以上的不同位置1-位置頻繁字節(jié)項(xiàng),且位置最前的1-位置頻繁字節(jié)項(xiàng)必須位于報(bào)文的前三個(gè)字節(jié)內(nèi)。

經(jīng)過規(guī)則1篩選的協(xié)議關(guān)鍵字只是剔除了大量的無用關(guān)鍵字,例如報(bào)文中廣泛存在的空格或回車換行符或者單純由這些字符串構(gòu)成的不具備區(qū)分協(xié)議能力的協(xié)議關(guān)鍵字組合,但其作為最后的協(xié)議格式特征還主要面臨兩方面問題:1)同一類協(xié)議F中的關(guān)鍵字選擇;2)不同類協(xié)議F間的關(guān)鍵字選擇。同一類協(xié)議關(guān)鍵字選擇主要為剔除關(guān)鍵字組合間的包含關(guān)系;而不同協(xié)議間關(guān)鍵字選擇主要為剔除關(guān)鍵字組合間的重復(fù)關(guān)系。為最大限度保留提取出的協(xié)議格式特征完整性,本文提出對同一類協(xié)議關(guān)鍵字選擇采用規(guī)則2進(jìn)行,對不同類協(xié)議關(guān)鍵字選擇采用規(guī)則3進(jìn)行。

規(guī)則2 給定字符串x?y,若sup(x)≤sup(y),則保留y；否則x、y都保留。

規(guī)則3 兩類協(xié)議的F1及F2,若字符串x?F1且x?F2,則從F1及F2中同時(shí)刪除x；否則保留x。

表1 樣本會話集

3 測試分析

實(shí)驗(yàn)環(huán)境為一臺PC(CPUi5-4430S,內(nèi)存2GB),操作系統(tǒng)為Windows7,利用編程軟件Matlab7.14.0進(jìn)行程序編寫測試。為了驗(yàn)證算法的性能,利用Wireshark在校園骨干網(wǎng)上采集包含載荷的真實(shí)流量,采集時(shí)間為2014年12月8日—13日。隨機(jī)選取了6個(gè)時(shí)間段(每個(gè)時(shí)間段持續(xù)5min)的數(shù)據(jù),其中3個(gè)作為訓(xùn)練數(shù)據(jù)集,3個(gè)作為測數(shù)據(jù)集,提取其中域名系統(tǒng)(DomainNameSystem,DNS)、文件傳送協(xié)議(FileTransferProtocol,FTP)、超文本傳送協(xié)議(HyperTextTransferProtocol,HTTP)、網(wǎng)際報(bào)文存取協(xié)議(InternetMessageAccessProtocol,IMAP)、郵局協(xié)議版本3(PostOfficeProtocol,POP3)、簡單郵件傳送協(xié)議(SimpleMailTransferProtocol,SMTP)六種協(xié)議進(jìn)行測試,如表1所示。本文將進(jìn)行5個(gè)實(shí)驗(yàn)來測試SPMbFSC算法的性能,其中：實(shí)驗(yàn)1為算法參數(shù)的確定；實(shí)驗(yàn)2為算法格式特征提取功能性驗(yàn)證；實(shí)驗(yàn)3為算法在報(bào)文顆粒度上的性能評估；實(shí)驗(yàn)4為算法與AdapSig算法在會話流顆粒度上的性能比較；實(shí)驗(yàn)5為算法與AdapSig算法時(shí)間復(fù)雜度的比較。

3.1 參數(shù)確定

本文算法參數(shù)包括每個(gè)報(bào)文的字節(jié)數(shù)k,截?cái)嚅L度閾值L,聚類算法每一簇最小的樣本數(shù)n,聚類最大簇?cái)?shù)Nmax以及支持度閾值minsup。目前比較常用的做法是截取報(bào)文前后各20字節(jié)[9]的數(shù)據(jù),所以本文選擇k=20;截?cái)嚅L度L及聚類最大簇?cái)?shù)Nmax的選擇目前沒有確定的標(biāo)準(zhǔn),所以采用實(shí)驗(yàn)的方法確定;依據(jù)本文挖掘精度的需要,設(shè)定最小樣本數(shù)n=10,以求最大限度地挖掘出所有格式特征;經(jīng)過多次實(shí)驗(yàn)發(fā)現(xiàn),取minsup=0.7適合每一個(gè)聚類簇中報(bào)文的頻繁字符串挖掘。

實(shí)驗(yàn)1 截?cái)嚅L度L及聚類最大簇?cái)?shù)Nmax的確定。本文采用自適應(yīng)的確定方法,具體做法為將每種協(xié)議的訓(xùn)練集報(bào)文平均分成兩份：一份作為訓(xùn)練報(bào)文；另一份作為測試報(bào)文。對L的確定為將訓(xùn)練報(bào)文按照長度進(jìn)行排列,按照人為給出的截取總報(bào)文數(shù)量的百分比來自適應(yīng)確定每一類協(xié)議的最佳截?cái)嚅L度L;對Nmax的確定為不斷變換人為給出的聚類簇?cái)?shù)值來確定最佳的聚類最大簇?cái)?shù)Nmax。

本文采用識別率和召回率測度指標(biāo)[9]來評估提取出的協(xié)議格式特征質(zhì)量。采用本文第2章介紹的SPMbFSC算法,在訓(xùn)練報(bào)文中提取出格式特征,在測試報(bào)文中的識別結(jié)果分別如圖2～3所示(其中圖2中Nmax設(shè)定為20, 圖3中L設(shè)定為60%)。

圖2 截?cái)嚅L度L的確定(Nmax=20)

圖3 聚類最大簇?cái)?shù)Nmax的確定(L=60%)

由于采用的是報(bào)文的識別率,所以提取出的協(xié)議格式特征識別率普遍較低。但從圖2可看出,協(xié)議格式特征的識別率都具有先上升到峰點(diǎn)然后再下降的特點(diǎn)。其原因在于當(dāng)截?cái)嚅L度L較小時(shí),得到的報(bào)文數(shù)過少,其包含的格式特征少導(dǎo)致識別率低;當(dāng)L過大時(shí),混入了過多的純業(yè)務(wù)類信息報(bào)文,導(dǎo)致在已有支持度設(shè)定的條件下有效特征被淹沒,其識別率降低。

從圖3中則可看出格式特征的識別率都經(jīng)歷了先上升后穩(wěn)定的特點(diǎn)。其原因在于當(dāng)Nmax較小時(shí),聚類簇?cái)?shù)少于樣本中真實(shí)的類別數(shù),簇內(nèi)混雜程度高,在高支持度條件下提取出的格式特征較少使得識別率較低;當(dāng)Nmax較大時(shí),聚類簇?cái)?shù)大于樣本中的真實(shí)類別數(shù),使得提取出的格式特征完備從而識別率穩(wěn)定。但同時(shí)過大的Nmax設(shè)定會使樣本的聚類出現(xiàn)過擬合傾向。

從圖2～3中可看出當(dāng)截?cái)嚅L度L為全部報(bào)文數(shù)量的60%及Nmax為20時(shí),絕大多數(shù)協(xié)議的識別率都達(dá)到最大值,所以設(shè)定每一類協(xié)議報(bào)文數(shù)60%所對應(yīng)的長度為截?cái)嚅L度L,選取聚類最大簇?cái)?shù)Nmax的值為20。

3.2 性能分析

格式特征提取得到的結(jié)果如表2所示,為便于比較,表中也列出了AdapSig[9]和L7-Filte[16]獲得的格式特征。其中AdapSig算法為目前已知最先進(jìn)的協(xié)議格式特征自動(dòng)提取算法,其與本文SPMbFSC算法的區(qū)別為AdapSig算法以完整會話為單位進(jìn)行格式特征提取,從每個(gè)會話相同位置偏移的報(bào)文中挖掘協(xié)議的格式特征;L7-Filter為一款主要依靠人工分析來制定識別特征規(guī)則的網(wǎng)絡(luò)流量分類識別軟件,其識別單位為完整會話,利用端口號、用戶行為特征等會話流信息及少量的報(bào)文載荷中協(xié)議關(guān)鍵字的匹配實(shí)現(xiàn)了非常高的識別率[17],被認(rèn)為是最精確的。為保證實(shí)驗(yàn)條件的公平性,本文不使用L7-Filter中任何會話流特征來進(jìn)行輔助識別,僅使用其報(bào)文載荷中提取出的協(xié)議格式特征進(jìn)行實(shí)驗(yàn),其特征用正則表達(dá)式(RegularExpression,RegExp)表示。

實(shí)驗(yàn)2 格式特征提取功能性驗(yàn)證。用本文提出的SPMbFSC算法與AdapSig算法對訓(xùn)練集協(xié)議數(shù)據(jù)進(jìn)行特征提取后,結(jié)果如表2所示(其中AdapSig算法支持度設(shè)置為與文獻(xiàn)[9]中一致的0.02)。

從表2可以看出,本文SPMbFSC算法和AdapSig算法提取出的協(xié)議格式特征均達(dá)到了對L7-Filter特征的覆蓋,即證明了本文算法功能的正確性,其中表2中三條特征:“220x20,x0dx0a”“USERx20,x0dx0a”和“PASSx20,x0dx0a”由關(guān)鍵字選擇規(guī)則3不予添加,其原因在于FTP和SMTP協(xié)議中均挖掘出了“220x20,x0dx0a”特征而FTP和POP3協(xié)議中均挖掘出了后兩條特征。

除IMAP及SMTP協(xié)議本文SPMbFSC算法和AdapSig算法提取出的格式特征差別較大,其他四種協(xié)議本文提取的協(xié)議格式特征實(shí)現(xiàn)了對AdapSig算法提取特征的全覆蓋。深入查看數(shù)據(jù),發(fā)現(xiàn)IMAP及SMTP協(xié)議提取的格式特征差別較大的原因在于實(shí)驗(yàn)中收集到的IMAP及SMTP協(xié)議報(bào)文數(shù)量相對較少,但格式種類相對較多,使本文聚類算法在小搜索半徑時(shí)的聚類簇?cái)?shù)超出了Nmax的上限設(shè)置,從而導(dǎo)致搜索半徑過大，同時(shí)較高支持度閾值的設(shè)置又使得提取出的協(xié)議格式特征少,而AdapSig算法則由于非常低的支持度閾值及缺少聚類算法的限制,所以提取出的協(xié)議格式特征較多。后期進(jìn)行了降低支持度閾值及提高Nmax閾值設(shè)定的實(shí)驗(yàn),實(shí)現(xiàn)了對AdapSig算法協(xié)議格式特征的提取。

實(shí)驗(yàn)3 性能評估。將六種協(xié)議的測試數(shù)據(jù)集合并成為最終的測試數(shù)據(jù)集,用本文SPMbFSC算法提取的協(xié)議格式特征與L7-filter的特征在報(bào)文顆粒度上進(jìn)行性能評估,由于AdapSig算法無法在非完整會話基礎(chǔ)上挖掘協(xié)議格式特征所以不參與對比,以識別率與召回率為指標(biāo)進(jìn)行評估,其結(jié)果分別如圖4～5所示。

表2 訓(xùn)練報(bào)文集格式特征提取結(jié)果

注:特征之間用“|”分隔；特征內(nèi)的元素之間用“,”分隔。

圖4 報(bào)文識別率對比

圖5 報(bào)文召回率對比

從圖4中看出本文提取的協(xié)議格式特征的識別率普遍較高且均不低于L7-filter,即提取的協(xié)議格式特征是正確的,其中L7-filter對FTP及SMTP協(xié)議識別率較低的原因在于兩協(xié)議均含有“220x20,x0dx0a”特征,從而彼此產(chǎn)生誤判。而從圖5中看出本文及L7-filter特征的召回率普遍較低其原因有兩點(diǎn):1)協(xié)議產(chǎn)生的會話中帶有業(yè)務(wù)類信息的報(bào)文數(shù)量較多而帶有控制類信息的報(bào)文數(shù)量較少,在以報(bào)文為顆粒度的計(jì)算中召回率低下,例如HTTP及POP3協(xié)議;2)本文算法提取出的協(xié)議格式特征及L7-filter的特征較少,不足以充分覆蓋協(xié)議報(bào)文,使得召回率較低。

實(shí)驗(yàn)4 與AdapSig算法性能比較。分別利用本文SPMbFSC算法提取出的協(xié)議格式特征,AdapSig算法提取出的協(xié)議格式特征及L7-filter的特征進(jìn)行分類識別來進(jìn)行算法性能的比較,結(jié)果以識別率與召回率為指標(biāo)進(jìn)行評估。為統(tǒng)一指標(biāo)的可比性,計(jì)算都以會話為單位進(jìn)行。實(shí)驗(yàn)結(jié)果分別如圖6～7所示。

圖7 會話召回率對比

從圖6～7中可看出，從以會話為單位的識別率和召回率來看，本文提出的SPMbFSC算法均為最高,且所有協(xié)議的識別率及召回率均達(dá)到了90%以上,從而驗(yàn)證了本文算法在會話為單位的協(xié)議識別上的有效性。其中：圖6中FTP協(xié)議本文的識別率略高于AdapSig算法,原因在于本文提取的協(xié)議格式特征多于AdapSig算法;而L7-filter對FTP及SMTP協(xié)議識別率較低的原因?yàn)槿鄙倭藭捔餍畔⒌妮o助，同時(shí)兩協(xié)議均含有“220x20,x0dx0a”特征而引起誤判。圖7中L7-filter對FTP及HTTP協(xié)議召回率較低則是由于其特征較少,無法覆蓋協(xié)議會話;IMAP及SMTP協(xié)議本文與AdapSig算法召回率一致則是由于相同會話中帶有控制字段的報(bào)文數(shù)較少但類別較多,從而導(dǎo)致AdapSig算法雖然提取出了較多的協(xié)議格式特征但兩算法的召回率一致。

實(shí)驗(yàn)5 與AdapSig算法時(shí)間復(fù)雜度對比。在minsup相同的條件下,通過本文SPMbFSC算法與AdapSig算法挖掘出協(xié)議關(guān)鍵字所耗費(fèi)的時(shí)間為指標(biāo)評估本文算法的效率。實(shí)驗(yàn)結(jié)果如圖8所示。

圖8 效率比較

從圖8中看出,除了FTP和HTTP協(xié)議外,本文SPMbFSC算法效率均高于AdapSig算法,同時(shí)在FTP及HTTP協(xié)議中當(dāng)minsup較高時(shí)(大于0.1),本文算法的效率也高于AdapSig算法。其原因在于FTP及HTTP協(xié)議的報(bào)文不僅數(shù)量龐大,同時(shí)攜帶的內(nèi)容種類也多,使SPMbFSC算法運(yùn)算的報(bào)文集規(guī)模比AdapSig算法大,同時(shí)在minsup較低時(shí),SPMbFSC算法的運(yùn)算次數(shù)十分巨大,導(dǎo)致效率較低,但當(dāng)minsup增大到一定程度后,其運(yùn)算次數(shù)急劇減小,從而使算法在較高支持度時(shí)效率高于AdapSig算法。但在其他條件下本文算法效率均高于AdapSig算法也證明了本文算法的高效性。

4 結(jié)語

本文提出的SPMbFSC算法能夠在離散序列報(bào)文的條件下自動(dòng)發(fā)現(xiàn)協(xié)議關(guān)鍵字同時(shí)篩選出格式特征,其前提條件更寬泛，更貼近實(shí)際的網(wǎng)絡(luò)環(huán)境,同時(shí)減少了人工參與,提高了自動(dòng)化程度。選擇目前較流行的應(yīng)用協(xié)議流量進(jìn)行測試取得了不錯(cuò)的效果。然而本文方法是否適用于其他的協(xié)議,尤其是目前增長十分迅速的P2P類應(yīng)用協(xié)議及某些領(lǐng)域內(nèi)的私有類型協(xié)議仍需要廣泛的驗(yàn)證。同時(shí)由于協(xié)議關(guān)鍵字選擇規(guī)則方面研究較少,本文實(shí)際操作中也出現(xiàn)了選擇規(guī)則過于簡單的現(xiàn)象,如何在已有協(xié)議關(guān)鍵字提取的基礎(chǔ)上充分利用其識別性能而產(chǎn)生更高效嚴(yán)謹(jǐn)?shù)膮f(xié)議關(guān)鍵字選擇規(guī)則也是下一步的研究目標(biāo)。

References)

[1] VOLZ B, CAIN E, KOHLER E, et al. Service name and transport protocol port number registry [EB/OL]. [2012- 06- 06]. http://www.iana.org/assignments/port-numbers.

[2] HUANG S, CHEN K, LIU C. A statistical-feature-based approach to Internet traffic classification using machine learning [C]// ICUMT 2009: Proceedings of the 2009 International Conference on Ultra Modern Telecommunications & Workshops. Piscataway, NJ: IEEE, 2009: 1-6.

[3] KARAGIANNIS T, PAPAGIANNAKI K, FALOUTSOS M. BLINC: multilevel traffic classification in the dark [C]// SIGCOMM 2005: Proceedings of the 2005 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications. New York: ACM, 2005: 229-240.

[4] MOORE A W, PAPAGIANNAKI K. Toward the accurate identification of network applications [C]// PAM 2005: Proceedings of the 6th International Conference on Passive and Active Network Measurement. Berlin: Springer, 2005: 41-54.

[5] WANG Y, XIANG Y, YU S-Z. Automatic application signature construction from unknown traffic [C]// Proceedings of the 2010 24th IEEE International Conference on Advanced Information Networking and Applications. Piscataway, NJ: IEEE, 2010: 1115-1120.

[6] LUO J Z, YU S Z, CAI J. Capturing uncertainty information and categorical characteristics for network payload grouping in protocol reverse engineering [J]. Mathematical Problems in Engineering, 2015, 2015(6): 1-9.

[7] 劉興彬, 楊建華, 謝高崗, 等. 基于 Apriori 算法的流量識別特征自動(dòng)提取方法[J]. 通信學(xué)報(bào), 2008, 29(12): 51-59.(LIU X B, YANG J H, XIE G G, et al. Automated mining of packet signatures for traffic identification at application layer with Apriori algorithm [J]. Journal on Communications, 2008, 29(12): 51-59.)

[8] AGRAWAL R, SRIKANT R. Fast algorithms for mining association rules in large databases [C]// VLDB 1994: Proceedings of the 20th International Conference on Very Large Data Bases. San Francisco: Morgan Kaufmann Publishers, 1994: 487-499.

[9] 王變琴, 余順爭. 自適應(yīng)網(wǎng)絡(luò)應(yīng)用特征發(fā)現(xiàn)方法[J]. 通信學(xué)報(bào), 2013, 34(4): 127-137.(WANG B Q, YU S Z. Adaptive extraction method of network application signatures [J]. Journal on Communications, 2013, 34(4): 127-137.)

[10] 朱玉娜, 韓繼紅, 袁霖, 等. SPFPA: 一種面向未知安全協(xié)議的格式解析方法[J]. 計(jì)算機(jī)研究與發(fā)展, 2015, 52(10): 2200-2211.(ZHU Y N, HAN J H, YUAN L, et al. SPFPA: a format parsing approach for unknown security protocols [J]. Journal of Computer Research and Development, 2015, 52(10): 2200-2211.)[11] HAN J, PEI J, YIN Y, et al. Mining frequent patterns without candidate generation: a frequent-pattern tree approach [J]. Data Mining & Knowledge Discovery, 2004, 8(1): 53-87.

[12] ESTER M, KRIEGEL H P, SANDER J, et al. A density-based algorithm for discovering clusters in large spatial databases with noise [C]// Proceedings of the Second International Conference on Knowledge Discovery and Data Mining. Menlo Park, CA: AAAI Press, 1996: 226-231.

[13] PEI J, HAN J, MORTAZAVI-ASL B, et al. Mining sequential patterns by pattern-growth: the PrefixSpan approach [J]. IEEE Transactions on Knowledge and Data Engineering, 2004, 16(11): 1424-1440.

[14] HAFFNER P, SEN S, SPATSCHECK O, et al. ACAS: automated construction of application signatures [C]// MineNet 2005: Proceedings of the 2005 ACM SIGCOMM Workshop on Mining Network Data. New York: ACM, 2005: 197-202.

[15] ERMAN J, ARLITT M, MAHANTI A. Traffic classification using clustering algorithms [C]// MineNet 2006: Proceedings of the 2006 SIGCOMM Workshop on Mining Network Data. New York: ACM, 2006: 281-286.

[16] Application layer packet classifier for Linux[EB/OL]. [2012- 06- 02]. http://l7-filter.sourceforge.net/.

[17] Application layer packet classifier for Linux-HOWTO[EB/OL]. [2012- 06- 03]. http://17-filter.sourceforge.net/documents.

LI Yang, born in 1991, M. S. candidate. His research interests include data mining, traffic classification.

LI Qing, born in 1976, Ph. D., associate professor. Her research interests include network data reverse processing, visible-light communication, wireless self-organizing network, sensor network.

ZHANG Xia, born in 1979, Ph. D., lecturer. Her research interests include machine learning, network protocol analysis.

Automatic protocol format signature construction algorithm based on discrete series protocol message

LI Yang, LI Qing*, ZHANG Xia

(College of Information System Engineering, Information Engineering University, Zhengzhou Henan 45002, China)

To deal with the discrete series protocol message without session information, a new Separate Protocol Message based Format Signature Construction (SPMbFSC) algorithm was proposed. First, separate protocol message was clustered, then the keywords of the protocol were extracted by improved frequent pattern mining algorithm. At last, the format signature was acquired by filtering and choosing the keywords. Simulation results show that SPMbFSC is quite accurate and reliable, the recognition rate of SPMbFSC for six protocols (DNS, FTP, HTTP, IMAP, POP3 and IMAP) achieves above 95% when using single message as identification unit, and the recognition rate achieves above 90% when using session as identification unit. SPMbFSC has better performance than Adaptive Application Signature (AdapSig) extraction algorithm under the same experimental conditions. Experimental results indicate that the proposed SPMbFSC does not depend on the integrity of session data, and it is more suitable for processing incomplete discrete seriesprotocol message due to the reception limitation.

discrete series protocol message; protocol keyword extraction; dadptive format signature mining; format signature; protocol identification

2016- 09- 28;

2016- 10- 09。

李陽(1991—),男,河南柘城人,碩士研究生,主要研究方向:數(shù)據(jù)挖掘、流量分類; 李青(1976—),女,河北正定人,副教授,博士,主要研究方向:網(wǎng)絡(luò)數(shù)據(jù)逆向處理、可見光通信、無線自組織網(wǎng)、傳感網(wǎng); 張霞(1979—),女,山東濟(jì)南人,講師,博士,主要研究方向:機(jī)器學(xué)習(xí)、網(wǎng)絡(luò)協(xié)議分析。

1001- 9081(2017)04- 0954- 06

10.11772/j.issn.1001- 9081.2017.04.0954

TP393.8

A