基于數據流前端檢測的快速協議識別

詹成,張偉

摘? 要： 信息戰(zhàn)都追求高速反應機動，對網絡協議識別提出了高效快速的要求。基于深度包檢測DPI的協議識別方法識別準確率高，但是由于要對所有數據包進行檢測，計算量很大。基于端口號的協議識別方法速度快，但識別準確率低。提出一種新的基于數據流前端檢測的協議識別方法并進行了系統(tǒng)實現，結合了基于端口方法的快速簡單和基于DPI的準確性的優(yōu)點。實驗表明，這種綜合快速協議識別方法識別準確率高，與基于DPI的方法相比，識別時間減少將近80%。

關鍵詞： 協議識別； 正則表達式； 數據流前端檢測； DPI

中圖分類號： TN911.7?34； TP393?????????? 文獻標識碼： A??????????????????????? 文章編號： 1004?373X（2014）23?0058?04

Abstract： With the demand of quick response capability in the information war， the network protocol identification needs to be efficient and quick. The protocol identification method based on deep packet inspection （DPI） can achieve high accuracy， however it brings about mass calculation because of inspection of all packets. The protocol identification method based on port inspection is fast， but its accuracy is low. A new protocol identification method based on data?flow front?end detection is proposed and the system implementation way is given in this paper. The simple fast advantage of port?based method and the accuracy advantage of DPI method are combined in this method. The experimental results show that the new protocol identification method can achieve high accuracy， and decrease the identification time by nearly 80% in comparison with the DPI methods.

Keywords： protocol identification； regular expression； data?flow front?end detection； DPI

0? 引? 言

現在信息戰(zhàn)都追求高速反應，高速機動，要求對協議進行高效快速識別，以盡快達到對協議識別的高準確性。傳統(tǒng)的協議識別技術是端口識別[1]，這種識別具有較高的效率。但是隨著網絡協議的發(fā)展，原有的基于端口映射的協議識別技術局限性越來越明顯。特別是在信息化軍事戰(zhàn)場上，這種識別方式的應用性幾乎為零。一種基于深度報文檢測（Deep Payload Inspection，DPI）的方法[2]，可以通過分析報文中的內容，根據預先定義的大量模式（域值、關鍵字或者正則表達式），對報文中的內容進行匹配，尋找匹配項，并確定報文所屬的應用層協議，從而判定整個數據流所屬的協議類型。雖然DPI方法可以達到很高的識別準確性，但是也存在以下問題：計算量大，需要對數據流的所有數據包內容進行檢測，從而使得采用DPI方法困難且價格昂貴；用戶的隱私保護，由于DPI需要檢測數據包的全部負載，導致用戶的隱私數據內容泄露。

本文創(chuàng)新地結合兩種方法提出一種綜合快速協議識別算法并進行了系統(tǒng)實現，通過對數據流的前端數據包進行深度包檢測來進行協議識別，不僅具有基于端口方法快速執(zhí)行的特點，同時又具有DPI方法識別準確性的優(yōu)勢。在真實數據流上的實驗結果表明，相比較完全基于深度包檢測的方法，該方法可以達到類似的識別精度，而且識別時間減少了將近80%。

1? 系統(tǒng)采用的識別方法

在基于深度包檢測的方法中，數據流的所有數據包都要進行模式匹配，但協議匹配并非總發(fā)生在數據流的末端。通過一個實驗分析來探測到底在一段數據流中檢測深度需要多大，即需要檢測多少個數據包才能識別應用層協議。實驗采用從互聯網下載的真實數據流負載，其中包括典型協議HTTP，FTP，POP3，DHCP，SMTP，MSN，BitTorrent等協議的數據包。協議識別系統(tǒng)采用基于深度包檢測的協議識別方法[3?4]，添加一些調試語句來收集以下信息：數據包的協議匹配在什么地方發(fā)生，即匹配發(fā)生在數據流的哪個數據包上。通過實驗分析得到了如圖1所示的結果。其中橫軸表示協議匹配成功完成時匹配數據包在數據流中的位置，縱軸表示所有的數據流上發(fā)生協議匹配的次數。

<；E：＼LIHUI＼12月＼12.4＼現代電子技術201423＼Image＼03t1.tif>；

圖1 數據包匹配深度圖

從圖1中可以看到大部分協議匹配的完成只需檢測數據流的前幾個數據包就可以實現。這是因為協議運行的初期通常需要進行控制報文的交換，而這些交換報文通常是這種協議特有的，可以成為進行協議識別的特征。這個實驗提出了一種新的協議識別方法，即通過檢測網絡應用中數據流最有意義的數據包，通常為數據流的前N個數據包，就可以成功地完成協議識別，在第3節(jié)討論[N]的具體取值。對數據流的前端數據包進行深度包檢測，具有以下優(yōu)點：達到接近于基于端口號方法的快速協議識別速度；盡量保護隱私數據。

2? 系統(tǒng)實現

2.1? 數據流前端數據包檢測

在協議識別系統(tǒng)實現中，只對數據流的前[N]個數據包進行深度包檢測。由于在網絡傳輸層以上的數據傳輸都是以數據流為單位，因此在網絡數據流的基礎上進行協議識別。在本系統(tǒng)中采用<；源IP，目的IP，端口號>；所定義的一組報文來描述數據流。協議識別在<；源IP，目的IP，端口號>；三元組所定義的數據流上進行，一條數據流屬于某個協議或者不屬于某個協議，協議識別采用基于正則表達式的字符串匹配來進行深度包檢測，在第3節(jié)中會詳細介紹。

當新的數據流報文出現時，協議識別系統(tǒng)將產生新的流標志來標識此數據流，完成對此數據流數據包檢測后，記錄該數據流識別狀態(tài)，如已識別或尚未識別。當發(fā)現新的數據包屬于舊有數據流，則判斷數據流的識別標識，若該數據流已識別，則識別系統(tǒng)跳過后續(xù)報文；若尚未識別，識別系統(tǒng)將該數據流送至匹配引擎匹配，根據匹配結果確定協議分類；尚不能分類的數據流則需保留協議識別狀態(tài)，以便后續(xù)報文到來時繼續(xù)進行識別。對于暫時不能識別的數據流，可以保存識別狀態(tài)，即記錄當前數據流識別過程進行狀態(tài)轉移時轉移到了哪個狀態(tài)；當再次遇到該數據流的數據包時，可以將保存的狀態(tài)恢復，繼續(xù)進行識別。采用這種方法不必對數據流重新進行識別，可以節(jié)省協議識別時間。

數據流協議識別算法如下所示，其中對每段數據流，只檢測前[N]個數據包。

1. while （新的數據包p到達）

2.? if <；p（源IP），p（目的IP），p（端口號）>；未知

3.???? Con_id =? 為<；p（源IP），p（目的IP），p（端口號）>；分配的連接號

4.???? if? （能識別Con_id）

5.?????? return 協議類型

6.???? else

7.?????? 保存Con_id協議識別最新狀態(tài)

8.? else

9.??? Con_id =? 已保存的<；p（源IP），p（目的IP），p（端口號）>；連接號

10.?? 恢復最新識別狀態(tài)

11.?? if? （能識別Con_id）

12.????? return 協議類型

13.?? else

14.???? 保存Con_id協議識別最新狀態(tài)

數據流匹配算法只掃描一次數據流，隨著數據包的輸入，可以在輸入的任何位置完成識別，而無需重復掃描數據包；對未識別的數據流，從當前識別狀態(tài)而不是初始狀態(tài)繼續(xù)進行匹配，提高了整個協議識別速度。

2.2? 基于正則表達式的數據包檢測

協議特征提取可以通過對協議的相關文檔的研究，找出協議交互過程中特有的且必定出現的固定字段。若協議中只有惟一的固定字段，就選取該字段作為協議的特征串；若存在多個固定字段，則對協議的實際報文進行統(tǒng)計，選取出現頻率最高的字段作為協議的特征串。

正則表達式[5]是采用某種模式去匹配一類字符串的公式，主要用于文本搜索、程序語言編譯器等領域。作為一種形式語言，正則表達式定義了一套自己的描述方式：完整的正則表達式是由兩種字符構成的字符模式，其中特殊字符稱為“元字符”，其他的普通ASCII字符稱為“文字”。描述一組可匹配的字符串時不用明確地列舉出所有的確切形式，而是通過元字符描述子串或者單個字節(jié)的特征。在正則表達式中，既可以使用ASCII字符，也可以使用十六進制數。基于正則表達式的模式匹配就是將這一字符模式與所搜索的字符串進行匹配。正則表達式比固定字符串具有更強的表達能力和更好的靈活性，因此采用正則表達式代替固定字符串表示協議的特征。

例如對于文件傳輸協議FTP，通常服務器會傳輸字符串“220”表示服務器已準備好，接下來會傳輸一段數據，其中包含字符串“FTP”，在“220”和“FTP”之間會有一些ASCII字符串。根據這些特性，可以將協議FTP的協議特征用正則表達式“^220*FTP”來表示。

2.3? 基于正則表達式的字符串匹配

字符串匹配問題，就是在一個文本[T=t1t2…tn]中找出某個特定模式串[p=p1p2…pn]的所有出現位置。其中[T]和[p]都是有限字母表[Σ]上的字符序列。匹配算法使用一個固定長度的窗口來搜索模式串，在窗口內檢驗模式是否匹配，然后從左向右不斷地移動窗口，直到掃描完整個文本。利用自動機進行字符串匹配[6]只需對每個文本字符檢查一次，并且檢查每個文本字符的時間為常數。因此對長度為[n]的文本，建立自動機后匹配算法的時間為[Θ（n）。]

圖2為一個簡單的兩狀態(tài)自動機，其狀態(tài)集Q={0，1}，開始狀態(tài)q0=0，輸入字母表[Σ]={a，b}。狀態(tài)1是僅有的接受狀態(tài)，有向邊表示轉移。如從狀態(tài)1到狀態(tài)0，標有b的有向邊表示狀態(tài)轉移函數δ（1，b）=0。輸入abaaa，此狀態(tài)機的狀態(tài)序列（包括初始狀態(tài)）為<；0，1，0，1，0，1>；，表示它接受了這個輸入；輸入abbaa，狀態(tài)序列是<；0，1，0，0，1，0>；，表示它拒絕了這個輸入。

<；E：＼LIHUI＼12月＼12.4＼現代電子技術201423＼Image＼03t2.tif>；

圖2 簡單的兩狀態(tài)自動機

每個模式[P]都存在一個字符串匹配自動機，必須在預處理階段，根據模式構造出相應的自動機后，才能利用它來搜尋文本字符串。給定輸入文本T[1，2，…，n]，尋找長度為m的模式[P]的出現位置，可以用下面的基于自動機的匹配算法進行求解。對于長度為[m]的模式[p]的字符串匹配自動機來說，假定狀態(tài)集Q為{0，1，…，m}，初始狀態(tài)為0，惟一的接收態(tài)是狀態(tài)m。

自動機字符串匹配算法 （T， δ， m）如下：

1. [n← ] lengthT

2. [q← 0]

3. [for i← 1 to n]

4.?? [do q← δ[q，T（i）]]

5.????? [if q=m]

6.???????? [then 字符串匹配 ]

由匹配算法的簡單循環(huán)結構可以看出，對于一個長度為[n]的文本字符串，它的匹配時間為Θ（n）。這一匹配時間沒有包括計算變遷函數[δ]所需要的預處理時間。下面將給出如何生成有限狀態(tài)機的預處理過程。

2.4? 基于正則表達式的有限自動機DFA構造

有限自動機是正則表達式的自然形式表示，它分為確定型有限自動機（DFA）和非確定型有限自動機（NFA）兩種。NFA和DFA的主要區(qū)別是NFA對同一個字符串輸入完全有可能有多種理解方式，而DFA則只有惟一的一種理解方式；即DFA對每個輸入只產生一個狀態(tài)轉移，而NFA對每個輸入可能產生多個狀態(tài)轉移，并且有空轉化邊ε。

傳統(tǒng)的正則表達式匹配技術主要是基于非確定型有限自動機（NFA）實現的，其匹配速度較慢。隨著表達式規(guī)模不斷擴大，基于NFA 的匹配技術性能急劇下降，已經不能滿足應用的需求，因此通常使用匹配速度更快的基于DFA 的匹配技術[7]。正則表達式轉換成DFA的過程，首先通過Thompson構造算法[8]將正則表達式轉換成NFA，然后采用子集構造法[9]將NFA編譯成DFA，最后將DFA最小化。

Thompson算法根據確定的規(guī)則將正則表達式的NFA片段連接在一起，以構成與整個正則式對應的NFA，其主要方法是將各個片段根據規(guī)則進行連接。利用Thompson算法構造NFA時，只需掃描一次正則表達式，其構造復雜性為O（l），其中l(wèi)為正則表達式的長度。給定NFA，我們可以采用子集構造算法來構造有限狀態(tài)自動機DFA。

最小子集構造算法如下，假定NFA=（S，[Σ，]δ，S0，A）：

（1） 定義狀態(tài)集合I的ε?閉包[ε?clousure（I）]，為狀態(tài)集合I中的任何狀態(tài)S經過任意多條ε弧而能到達的狀態(tài)集合；

（2） 狀態(tài)集合I的a弧轉換（move（I，a））：定義為狀態(tài)集合J，其中J是所有可以從I的某一狀態(tài)經過一條a弧而到達的狀態(tài)的全體；

（3） 定義Ia=ε-clousure（J）：其中I為某個狀態(tài)集合，J為狀態(tài)集合I的a弧轉換move（I，a），也就是說，從某一個狀態(tài)集合中的任何一個狀態(tài)S，經過一條a弧再經過任意多條[ε]弧所能到達的狀態(tài)的全體為Ia；

（4） 由初始結點出發(fā)，找出其閉包構成的集合ε?clousure（S0）作為初始集合作為矩陣的第一行第一列，集合Ia作為第一行第二列，有窮輸入集[Σ]中的每一個輸入字符的Ix依次對應一列。如果這些集合未出現過，則把這些集合作為下一個初始集合，即下一行的第一列，Ia作為第二列，依次類推得出一個狀態(tài)轉換矩陣。對矩陣中的所有狀態(tài)子集重新命名后，即得出DFA的狀態(tài)轉換矩陣。

3? 性能評價

通過系統(tǒng)實驗來比較綜合協議識別方法和基于深度包檢測方法的性能差異，系統(tǒng)由C++語言實現，運行在Inter Core 2 Duo CPU @3.16 GHz的計算機上。實驗采用互聯網中下載的真實數據流數據，其中包括HTTP，FTP，POP3，DHCP，SMTP，MSN，BitTorrent等協議的數據包。采用完全深度包檢測的協議識別結果作為協議識別正確的判斷標準，實驗結果為200次實驗求平均的結果。

圖3（a）給出了協議識別時間隨著數據流前端檢測參數N的變化圖，可以看到隨著N的增大，系統(tǒng)識別時間增大，這是由于檢測參數N反映了系統(tǒng)進行數據包的檢測深度，N越大，系統(tǒng)需檢測的數據包越多。完全的深度包檢測需要時間5.453 s，而當N=15時，只需要1.17 s的檢測時間，識別時間減少了78%。

<；E：＼LIHUI＼12月＼12.4＼現代電子技術201423＼Image＼03t3.tif>；

圖3 數據流前端檢測參數N對系統(tǒng)性能的變化

圖3（b）反映了系統(tǒng)協議識別正確性隨著數據流前端檢測參數N的變化，隨著N的增大，協議識別正確率增大。當N>；14后，系統(tǒng)的協議識別正確率維持為100%。這是由于協議特征通常通過數據流前端的一些控制數據包就可以確定，而不必對全部負載信息進行檢測。在系統(tǒng)中，通常設置N=15。與深度包檢測的方法相比，不但可以達到相同的協議識別正確率，識別時間也減少了78%。

4?? 結? 論

本文提出一種基于數據流前端檢測的協議識別方法并進行了系統(tǒng)實現，結合了基于端口方法的快速簡單和基于DPI的準確性的優(yōu)點。系統(tǒng)實驗表明此種方法識別準確率高，相比傳統(tǒng)方法識別時間減少將近80%。

參考文獻

[1] KARAGIANNIS T， BROIDO A， BROWNLEE N， et al. Is p2p dying or just hiding？ [C]// Proceedings of IEEE Globecom. [S.l.]： IEEE， 2004， 3： 1532?1538.

[2] RISSO F， MORANDI O， BALDI M， et al. Lightweight， Payload?based traffic classification： An experimental evaluation [C]// Proceedings of ICC08. [S.l.]： IEEE， 2008： 5869?5875.

[3] CROTTI M， DUSI M， GRINGOLI F， et al. Traffic classification through simple statistical fingerprinting [J]. ACM SIGCOMM CCR， 2007， 37（1）： 7?16.

[4] LI Zhu， YUAN Rui?xi， GUAN Xiao?hong. Accurate classification of the internet traffic based on the svm method [C]// Proceedings of ICC. [S.l.]： [s.n.]， 2007： 1373?1378.

[5] GREGER H， FELDMANN A， MAL M， et al. Dynamic application?layer protocol analysis for network intrusion detection [C]// Proceedings of USENIX Security Symposium. [S.l.]： [s.n.]， 2006： 1125?1130.

[6] CORMEN T H， LEISERSON C E， RIVEST R L， et al. Introduction to algorithms [M]. 2 ed. [S.l.]： [s.n.]， 2002.

[7] 陳曙暉.基于內容分析的高速網絡協議識別技術研究[D].長沙：國防科技大學，2007.

[8] THOMPSON K. Regular expression search algorithm. [J]. Communications of the ACM， 1968， 11（6）： 410?422.

[9] HOPCROFT J E. ULLMAN J D. Introduction to automata theory， languages，and computation.? second edition [M]. Boston. Addison?Wesley， 2002.

4?? 結? 論

本文提出一種基于數據流前端檢測的協議識別方法并進行了系統(tǒng)實現，結合了基于端口方法的快速簡單和基于DPI的準確性的優(yōu)點。系統(tǒng)實驗表明此種方法識別準確率高，相比傳統(tǒng)方法識別時間減少將近80%。

參考文獻

[1] KARAGIANNIS T， BROIDO A， BROWNLEE N， et al. Is p2p dying or just hiding？ [C]// Proceedings of IEEE Globecom. [S.l.]： IEEE， 2004， 3： 1532?1538.

[2] RISSO F， MORANDI O， BALDI M， et al. Lightweight， Payload?based traffic classification： An experimental evaluation [C]// Proceedings of ICC08. [S.l.]： IEEE， 2008： 5869?5875.

[3] CROTTI M， DUSI M， GRINGOLI F， et al. Traffic classification through simple statistical fingerprinting [J]. ACM SIGCOMM CCR， 2007， 37（1）： 7?16.

[4] LI Zhu， YUAN Rui?xi， GUAN Xiao?hong. Accurate classification of the internet traffic based on the svm method [C]// Proceedings of ICC. [S.l.]： [s.n.]， 2007： 1373?1378.

[5] GREGER H， FELDMANN A， MAL M， et al. Dynamic application?layer protocol analysis for network intrusion detection [C]// Proceedings of USENIX Security Symposium. [S.l.]： [s.n.]， 2006： 1125?1130.

[6] CORMEN T H， LEISERSON C E， RIVEST R L， et al. Introduction to algorithms [M]. 2 ed. [S.l.]： [s.n.]， 2002.

[7] 陳曙暉.基于內容分析的高速網絡協議識別技術研究[D].長沙：國防科技大學，2007.

[8] THOMPSON K. Regular expression search algorithm. [J]. Communications of the ACM， 1968， 11（6）： 410?422.

[9] HOPCROFT J E. ULLMAN J D. Introduction to automata theory， languages，and computation.? second edition [M]. Boston. Addison?Wesley， 2002.

4?? 結? 論

本文提出一種基于數據流前端檢測的協議識別方法并進行了系統(tǒng)實現，結合了基于端口方法的快速簡單和基于DPI的準確性的優(yōu)點。系統(tǒng)實驗表明此種方法識別準確率高，相比傳統(tǒng)方法識別時間減少將近80%。

參考文獻

[1] KARAGIANNIS T， BROIDO A， BROWNLEE N， et al. Is p2p dying or just hiding？ [C]// Proceedings of IEEE Globecom. [S.l.]： IEEE， 2004， 3： 1532?1538.

[2] RISSO F， MORANDI O， BALDI M， et al. Lightweight， Payload?based traffic classification： An experimental evaluation [C]// Proceedings of ICC08. [S.l.]： IEEE， 2008： 5869?5875.

[3] CROTTI M， DUSI M， GRINGOLI F， et al. Traffic classification through simple statistical fingerprinting [J]. ACM SIGCOMM CCR， 2007， 37（1）： 7?16.

[4] LI Zhu， YUAN Rui?xi， GUAN Xiao?hong. Accurate classification of the internet traffic based on the svm method [C]// Proceedings of ICC. [S.l.]： [s.n.]， 2007： 1373?1378.

[5] GREGER H， FELDMANN A， MAL M， et al. Dynamic application?layer protocol analysis for network intrusion detection [C]// Proceedings of USENIX Security Symposium. [S.l.]： [s.n.]， 2006： 1125?1130.

[6] CORMEN T H， LEISERSON C E， RIVEST R L， et al. Introduction to algorithms [M]. 2 ed. [S.l.]： [s.n.]， 2002.

[7] 陳曙暉.基于內容分析的高速網絡協議識別技術研究[D].長沙：國防科技大學，2007.

[8] THOMPSON K. Regular expression search algorithm. [J]. Communications of the ACM， 1968， 11（6）： 410?422.

[9] HOPCROFT J E. ULLMAN J D. Introduction to automata theory， languages，and computation.? second edition [M]. Boston. Addison?Wesley， 2002.