前言
 

    在當今高速大容量的Internet環境中，內容安全是網絡安全的重要組成部分。對于網絡管理來說，最重要的就是識別和區分網絡流量，通過協議識別可以對網絡進行流量控制、網絡計費、內容過濾、以及流量管理。
 

    傳統的協議識別采用的是端口識別，這種識別能達到較高的速率，但是現在大量的應用層協議為了避免識別，逃避防火墻的檢查，不使用固定的端口進行通信.這不僅包括眾多近年新出現的P2P協議，而且包括了越來越多的傳統協議，比如BitTorrent、eMule等P2P協議，其采用動態端口進行通信；Skype、QQ等協議則共用80端口。越來越多諸如此類協議的產生，使得端口識別已無能無力，因此近年來很多的研究工作都致力于開發新的方法來識別應用層協議。
 

    DPI（Deep Packet Inspection，深度包檢測）技術是近年來出現的一種協議識別技術， DPI技術在分析包頭的基礎上，增加了對應用層的分析，是一種基于應用層的流量檢測和控制技術，當IP數據包、TCP或UDP數據流經過基于DPI技術的網絡設備時，DPI引擎通過深入讀取IP包載荷的內容來對OSI 7層協議中的應用層信息進行重組，從識別出IP包的應用層協議。
 

DPI技術
 

    傳統的IP包流量識別和QoS控制技術，僅對IP包頭中的“5Tuples”,即“五元組”信息進行分析，來確定當前流量的基本信息，傳統IP路由器也正是通過這一系列信息來實現一定程度的流量識別和QoS保障的，但其僅僅分析IP包的四層以下的內容，包括源地址、目的地址、源端口、目的端口以及協議類型，隨著網上應用類型的不斷豐富，僅通過第四層端口信息已經不能真正判斷流量中的應用類型，更不能應對基于開放端口、隨機端口甚至采用加密方式進行傳輸的應用類型。
 

    DPI技術技術在分析包頭的基礎上，增加了對應用層的分析，是一種基于應用層的流量檢測和控制技術，當IP數據包、TCP或UDP數據流經過基于DPI技術的帶寬管理系統時，該系統通過深入讀取IP包載荷的內容來對OSI7層協議中的應用層信息進行重組，從而得到整個應用程序的內容，然后按照系統定義的管理策略對流量進行整形操作。
 

    不同的應用通常會采用不同的協議，而各種協議都有其特殊的指紋，這些指紋可能是特定的端口、特定的字符串或者特定的Bit序列。基于特征字的識別技術，正是通過識別數據報文中的指紋信息來確定業務所承載的應用。根據具體檢測方式的不同，基于特征字的識別技術又可細分為固定特征位置匹配、變動特征位置匹配和狀態特征字匹配三種分支技術。通過對指紋信息的升級，基于特征字的識別技術可以方便的擴展到對新協議的檢測。
針對不同的識別技術，DPI可以分為以下兩大類：
 

    •使用特征字與掩碼相結合的協議識別
 

    •使用正則表達式庫的協議識別
 

使用特征字與掩碼相結合的協議識別

    使用特征字符串進行協議識別，先統計協議實際交互過程中出現頻率高的字符作為匹配串，DPI引擎在線檢查全報文以匹配多個串，往往適用于少量協議，效率一般，但其正確性有待提高，并且，對于一些變長填充的協議這種方式會顯得無能為力。
 

    使用特征字與掩碼相結合的字符串匹配方式實現比較簡單，往往可以采用硬件的方式來實現，例如某DPI廠商就采用交換機的ACL芯片來實現基于特征字與掩碼相結合的DPI識別引擎。
 

使用正則表達式庫的協議識別
 

    最近業界越來越趨向采用正則表達式來進行匹配，實踐表明，相對于傳統的五元組識別和字符串識別，使用正則表達式對應用層協議進行識別的正確性有很大提高。
 

    正則表達式(Regular Expression)描述了一種字符串匹配的模式，可以用來檢查一個串是否含有某種子串、將匹配的子串做替換或者從某個串中取出符合某個條件的子串等。
 

    一些DPI廠商采用只檢測包頭16字節或固定長度的特征值來實現DPI，但是我們認為這種模式不夠靈活，特別是一些協議的特征值在包的尾部，或者特征值之間間雜著動態長度的隨機填充字節，這些協議，用固定的DPI檢測就無法識別。
 

    經過對主流協議的研究，我們認為采用正則表達式（regular expression）的方式進行協議特征值的匹配是效果最好的，因為基于正則表達式的DPI識別引擎從原理上來說可以識別絕大部分協議。但是由于正則表達式的復雜性，常規的正則表達式引擎相當消耗系統資源，效率比較低，故而直接采用通用的正則表達式算法會嚴重的影響設備的性能。因此對于采用基于正則表達式的DPI引擎的廠商來說，如何解決DPI引擎的性能問題，是一件非常重要的工作。
 

    經過我們研發人員的努力，我們開發了一套高性能的正則表達式算法，該算法采用以空間換時間的方式大大的提高了正則表達式匹配的性能，根據我們設計的算法的原理與我們實際測試的數據，該算法實現了性能與正則表達式的長度和數目無關，這也就代表設備的性能與設備所加載的協議特征碼（實際上是一系列的正則表達式）的數量無關。
 

    我們在此正則表達式算法的基礎上實現了我們的DPI算法，從性能上來說基本上與固定長度的DPI算法相差無幾，但是卻大大提高了其靈活性。
 

DPI引擎

    我們采用了基于正則表達式的DPI引擎，在最初的版本中，DPI引擎中的正則表達式算法采用的是NFA算法，在最近的版本中，為了提高整個DPI引擎的性能，我們采用DFA算法代替了NFA算法。
 

NFA與DFA的區別
 

    NFA（Non-deterministic finite automaton，不確定有窮自動機），是基于表達式的（Regex-Directed）；而DFA（Deterministic finite automaton，確定的有窮自動機）是基于文本的（Text-Directed）。
 

    舉例來說，對于正則表達式 to(nite|knight|night)，NFA在匹配最開始兩個字符（to）之后，剩下的三個組件（component）是 nite, knight 和 night，于是正則算法會依次嘗試這三個選擇分支（每次嘗試一個）；而DFA在匹配最開始兩個字符之后，會將剩下的三個選擇拆分作字符，并行嘗試，也就是說，匹配 to 之后，先匹配 k 或者 n ，如果 k 不能匹配，則放棄knigth 所在的分支，再匹配 i ，再匹配 t 或 g ……這樣繼續下去，直到匹配結束。
 

    DFA 引擎在任意時刻必定處于某個確定的狀態，而NFA引擎可能處于一組狀態之中的任何一個，所以，NFA引擎必須記錄所有的可能路徑（trace multiple possible routes through the NFA），NFA之所以能夠提供Backtrack的功能，原因就在這里。從理論上說，如果我們不需要Backtrack，或者僅僅需要很小級別的Backtrack，完全可以從NFA構造出等價的DFA，再進行匹配，這樣能大大提高速度——代價是，DFA需要更多的空間。
 

    NFA 因為不確定，所以限制比DFA要少，構造起來也比較方便一點，但匹配速度較慢.而DFA依次匹配并記錄匹配過程中每個字符的位置，因此每個字符最多被匹配一次，其匹配速度比NFA要高許多。雖然要把正則表達式先轉化為NFA，再把NFA轉換為DFA，其轉換時間相對要長，但是只需在匹配報文前對正則表達式編譯一次，因此匹配報文的總體時間要比NFA的匹配引擎快很多。
 

正則表達式特征庫至DFA的轉換
 

    我們采用擴展的正則表達式對應用層協議的特征進行描述，這個協議特征描述的集合被稱之為特征庫。
 

    特征庫到DFA的轉換過程需要通過以下步驟：
 

正則表達式->NFA
 

    給出一個正則串的輸入，得到一個NFA的輸出。被廣泛采用的是Thompson Algorithm，也就是所謂的子集算法。該算法的實現和算術表達式的求值非常的類似，需要一個符號棧存放操作符，一個自動機棧存放生成的自動機。算法結束后，可以從自動機棧中得到一個最終的結果。
 

    我們給出右線性文法：
 

    S 0S | 1S | 1A | 0B
    A 1C | 1
    B 0C | 0
    C 0C | 1C | 0 | 1
 

    右線性文法特點：終結符＋非終結符， 通過右線性文法構造NFA：
 

    1）  每個非終結符在圖中對應一個結點，文法開始符號表示圖中的初態結點，添加一終態結點 Z 。
 

    2）  對形如 A cB 的產生式，畫一 A 到 C 的弧，標記為 c 。
 

    3）  對形如 A c 的產生式，畫一 A 到 Z 的弧，標記為 c 。

NFA->DFA

    一個 NFA 在讀入符號串之后，并不確切地知道自動機的下一個狀態是什么。但可以肯定的是，下一個狀態一定處于某個狀態集中。不妨該狀態集記做  {q1,q2,…qk} 。而一個等價的DFA 讀入同樣的符號串一定處于某個確定的狀態上。
 

    這樣，都是讀入同樣的w，  DFA  到達某一個狀態，而  NFA  到達某一個狀態集。由  w  的任意性，可將  NFA  的所有的狀態集和  DFA  的狀態一一對應起來。這種對應的前提就是能識別同樣的輸入串。即  L(M1)=L(M2)  。
 

    所以可以看出，我們要做的就是將 NFA 狀態集歸并為 DFA 中的狀態。其實質是將結點的跳轉轉化為結點集之間的跳轉。由初始結點 S 出發，找出其閉包構成的集合，在本例中， 由于不含ε路徑，S的閉包集合就是 {S}。然后由{S}出發，找出通過不同的路徑所能到達的集合。
 

    為清晰起見，將選擇圖中一個集合跳轉，重新標上顏色，和下表對應。

最小化DFA
 

    有窮自動機分為確定的有窮自動機DFA和不確定的有窮自動機NFA兩種。
 

    定義1DFA ：一個確定的有窮自動機，M是一個五元組，M=( K,Σ, f , S , Z)，其中:K是一個有窮集,其元素稱為狀態；Σ是一個有窮字母表,其元素稱為輸入符號；S∈K,稱為初態;ZÌ K，是終態集；f是轉換函數，是K×Σ→K上的映射，f(ki,a)=kj,(ki∈K,kj∈K)表示狀態ki，輸入符為a時，轉換為狀態kj。
 

    定義2無用狀態：從自動機的開始狀態出發,任何輸入串也不能到達的那個狀態;或者從這個狀態沒有通路到達終態的狀態。
 

    定義3等價狀態：如果說兩個狀態s 和t 是等價的, 應滿足如下條件:(a) 一致性條件：s 和t 必須同時為終態或為非終態;(b) 蔓延性條件：對于所有輸入符號，狀態s 和t 必須轉換到等價的狀態里。
 

    一個DFAM可以通過消除無用狀態和合并等價狀態而轉化為一個最小化的與之等價的DFAM’。該過程稱為DFA的最小化。最小化的思想是在不改變 DFA 識別的語言的前提下，合并相應的結點，使合并后的 DFA 與合并前的 DFA 等效，而結點數目減少。
 

    但在實現上，采用是從合到分的方法。先從最精簡的結構出發，即，整個系統就兩個集合，所有的終態結點并為一個結點，所有的非綜態結點合并為一個結點 。
 

    然后看這種劃分是否可行，如不可行，再分解出更多的集合。而合并可行的依據就是集合中的每個元素通過同一條弧到達同一個目標集合。 

    如上圖，首先將所有的非綜態結點合并為 I0 ，。將綜態結點合并為 I1 。分別考察兩個集合。對于 I0 ，通過 0 弧，有如下跳轉： S0 S1 ， S2 S1 ， S1 S3 。而 S1 ∈ I0 ， S3 ∈ I1 ，據此， S1 和 S0 、 S2 要分開位于不同集合。
 

    現假定 I0={ S0 ,S2} ， I1={ S3 ,S4} ， I2 ＝ { S1 } 。考察 I0 ，同樣是通過 1 弧，則有如下跳轉：
S0 S2 、 S2 S4 ，而 S2 ∈I 0 ,S4∈I 1 。故， S2 與 S4 分開。可以看出，只要發現一條弧不滿足上述條件，就可以將其分離。并非要考察完每條弧。
 

    再來考察 I1 ，通過 0 弧可得： S3 S3 ∈ I1 ， S4 S3 ∈ I1 。通過 1 弧可得： S3 S4 ∈ I1 ， S3 S4 ∈ I1 。顯然， I1 不可再分。
 

    如此重復，直到每個集合 Ii ( I=0,1,…) 均不可再分為止。
 

最小化后的狀態轉換圖如下：

 

數據包匹配模式

單包匹配方式
 

    當一個會話的每個報文到達時都進行DPI引擎匹配，直到匹配成功或者達到每個會話的最大匹配包數（特征值基本上都出現在一個會話的最初幾個包中，后續的包中的特征不明顯，甚至會導致協議的誤判），則后續的報文不再進行匹配。
 

    匹配成功的會話會被打上協議標簽，未匹配成功的會話則被打上Others的標簽。
 

    單報文匹配方式匹配速度快，而且準確性高，基本不存在誤判。
 

有選擇的多包匹配方式
 

    當DPI引擎發現某個報文符合一定的特征，則自動進入多包匹配方式，這種模式在針對類HTTP協議會很有幫助，DPI引擎會匹配某個會話的多個報文，進行更準確的協議識別。

    這兩種數據包匹配技術分別適用于不同類型的協議，相互之間無法替代，只有綜合的運用這兩大技術，才能有效的靈活的識別網絡上的各類應用，從而實現有效的控制。

DFA匹配方式
 

    在DFA下有兩種匹配掃描算法：
 

    One-Pass Scan算法（單遍掃描算法）
 

    Repeated Scan算法（多遍掃描算法）
 

    One-Pass算法只掃描一次，從一個位置開始掃描，如果有匹配，則結束搜索，返回結果，直至掃描結束；Repeated Scan算法從一個位置開始掃描，如果沒有匹配，則從下一個位置重新開始掃描，匹配過程中，需要對輸入進行重復搜索。
 

    我們首先采用One-Pass Scan算法對有Leading標記的特征值進行匹配，若匹配成功則結束匹配，若匹配不成功，則用Repeated Scan對非Leading的特征值進行匹配。
 

綜述
 

    通過DPI對網絡數據的快速識別與分類，不僅為用戶提高服務質量(QoS)、分層服務等提供技術支持，也可以為網絡數據上的內容監管(如惡意代碼識別、病毒防御)提供技術保障。
 

    深層包檢測DPI技術易于理解、升級方便、維護簡單，是目前運用較為有效的流量識別方法。目前，產品支持600多種協議和應用的自動識別，涵蓋了P2P、IM（即時通訊）、視頻/流媒體、VoIP協議、網絡游戲、炒股軟件、企業內部核心應用等應用和協議，基本覆蓋了目前主流的網絡協議和應用類型，可為用戶提供廣泛的、有效的協議支持。
 

    采用DPI技術的優點包括：準確性高、健壯性好、具有分類功能等。準確性高是由于該方法執行精確特征匹配，因此很少存在誤判問題。健壯性好是由于可以處理數據包丟失、重組等，因此能適應如今復雜的網絡應用。具有分類功能是由于深層數據包檢測技術可以依據不同應用的載荷特征來準確分類各網絡應用，因此可以為實施流量監管策略提供準確的信息。