基于ＦＳＭ的高速網絡協議識別研究

摘要：提出的高速網絡協議識別方案用FSM表示RegExp，用硬件完成模式匹配，實現了高速的網絡協議識別，解決了基于軟件的字符串匹配不能適應高速網絡發展的問題。測試表明其模式匹配速度可達到Gbps以上性能。

關鍵詞：網絡入侵檢測系統； 協議識別； 正則表達式； 模式匹配

中圖分類號：TP393

文獻標志碼：A

文章編號：1001－3695(2008)06－1877－02

當前，許多關鍵的網絡服務均基于報文內容，或報文頭部的結構信息對報文進行處理。例如，主流IDS/IPS產品廣泛采用應用層協議深層解析技術實現基于協議攻擊特征和協議異常的入侵檢測。目前，多數產品都是基于端口映射機制來判別數據流所屬的協議類型，如發現捕獲的報文中源端口或目的端口為80，則認為是HTTP相關報文，經過重組處理，直接交由HTTP報文分析模塊處理。隨著網絡中大量出現使用動態端口和不可預知端口的網絡軟件以及各種惡意軟件，基于端口映射的方法已經不能有效地識別報文。例如P2P和SIP（VoIP）的應用，并不采用固定協議端口，而是在運行過程中使用動態協商端口。一些應用使用非標準端口代替其標準端口。各種惡意軟件為了躲避IDS/IPS產品的檢測而采用一些熟知端口（如80端口）進行私有協議通信。

由此可見，基于端口的協議識別已經不可靠，需要一種能快速、準確識別報文的機制。陳亮等人[1]通過對實際應用的流量分析，總結出一些特征串，進行應用層協議識別，但該方法只能識別出廣義上的HTTP，即使用了HTTP規范的協議，而不能區分那些使用了HTTP規范的協議。本文提出的方案使用的是現在應用最廣的模式描述語言——RegExp與報文內容進行匹配。

L7－filter[2，3]是一個Linux內核Netfilter子系統的協議分類器，可以識別應用層的數據包。當全部開啟七十多種協議時，系統的吞吐量迅速下降到不及10 Mbps，遠低于當前LAN的速度。統計表明超過90%的CPU資源用于RegExp匹配，已無法完成其他工作[4]。本文提出的硬件體系結構能實現高速的網絡協議識別，達到Gbps以上的性能。

Sidhu等人[5]和Clark等人[6]采用FPGA器件構造NFA，達到了較高的存儲空間利用率。Moscola等人[7]用DFA代替NFA，提高了性能。很高的并行度和豐富的器件資源，使得基于FPGA的方法可達到很高的吞吐率，但該方法不適合RegExp經常更新的應用。對于正在使用的設備，快速地重新綜合、修改RegExp電路相對困難。本文提出的基于存儲器的硬件結構，更新時只需更改存儲器的內容，方便簡單。

本文提出的結構和方法適用于網絡數據包識別與分類的各種應用，軟硬件相結合的方法達到了很高的性能。主要提出和解決了三個問題：提出并實現了一種基于FSM的高速網絡協議識別設備；運用相關算法對DFA對應的狀態轉移表進行了壓縮優化；提出了對應的硬件匹配算法。

1背景及相關工作

1．1正則表達式

正則表達式（regular expression，RegExp）是由普通字符（如字符a~z）以及特殊字符（即元字符）組成的文字模式，應用時作為一個模式與所搜索的字符串進行匹配。例如，“^.?\\x02.+\\x03$”用來識別網絡中QQ的數據包，它用來匹配第一個或第二個字符ASCII碼值為0x02（若不滿足，很快即可確定匹配不成功），隨后接一個或多個任意字符，最后一個字符ASCII碼值對應的十六進制是0x03的報文內容。例如，“\\x02sa\\x03”“k\\x02ajask\\x03”就是匹配的數據包內容，“dsa\\x02js\\x03”則不匹配。詳細的語法知識參考文獻[8]。

1．2FSM

FSM是為研究有限內存的計算過程和某些語言類而抽象出來的一種計算模型。它擁有有限數量的狀態，每個狀態可以遷移到零個或多個狀態，根據輸入的字符決定執行哪個狀態的遷移。FSM可以表示為一個有向圖，在數字電路設計、詞法分析、文本編輯器等方面均得到了應用。FSM可以分為NFA和DFA兩種。其中，NFA可以轉換成DFA。

一個FSM是由下述元素構成的五元組(Q，∑，q0，δ，A)。其中：有窮狀態集合Q；有窮輸入字母表∑；初始狀態q0；轉移函數δ：Q×∑→Q；接受狀態A。FSM從初始狀態q0起，逐一讀入由輸入字母表∑中字母構成的輸入串的每個字母，根據當前狀態、輸入字母和轉移函數δ決定自動機的下一個狀態。當輸入的字符串結束時，若自動機處于接收狀態集合A中的某一個狀態，則表示自動機接收該字符串；否則不接收。DFA對每個輸入只產生一個狀態轉移，而NFA對每個輸入可能產生多個狀態轉移，并且有空轉換邊ε。QQ對應的非確定性和確定性有限狀態自動機分別如圖1、2所示。

對于一個長度為n的RegExp，NFA的狀態數為O(n)，而DFA的狀態數最大可為O(∑n），匹配過程的復雜性DFA為O(1)，NFA最大可為O(n2)[9]。兩者的比較如表1所示。

1．3L7－filter

從Linux 2.4開始，Netfilter和Iptables作為一個新的網絡包過濾框架替代了原來的Ipchains/Ipfwadm，成為內核網絡協議堆的一個擴展子集。Netfilter是嵌入內核IP協議棧的一系列調用入口，設置在報文處理的路徑上。其中的hook函數通過訪問Iptables中的規則來判斷應該返回什么值給Netfilter框架。Iptables是Linux最著名的內建防火墻軟件，內建NAT、簡單的規則設定，可擴充地掛載其他模塊，但是工作在IP層的Iptables不能實現基于報文內容的過濾。針對Iptables的子系統L7－filter，掛在Iptables extended packet matching modules上，可以做到應用層的包過濾。

2實現與分析

2．1算法

2．1．1RegExp轉換成NFA，NFA轉換成DFA

運用經典的Thompson算法[10]，根據RegExp的語法元素來構造不同的NFA，最后連接構成完整的NFA，接著運用經典的子集構造算法[10]，將NFA轉換成DFA，生成狀態轉移表。

2．1．2相關優化算法

狀態轉移表的大小直接制約著硬件匹配速度的提高，而它由狀態和轉換邊組成，轉換邊最多有256種可能。因此，對于它的優化，主要是基于狀態和轉換邊的壓縮。

1）壓縮狀態在將DFA最小化[10]的基礎上，通過重寫RegExp將其分組，可以壓縮DFA狀態。對于任何RegExp集合，其對應的DFA狀態數均有最小值，因此本文主要基于壓縮轉換邊優化。

2）壓縮轉換邊采用預編碼技術，大量減少無用轉換邊的數量。未進行優化的狀態轉移表將字符對應的ASCII碼值作為其在表中的偏移量，放入N MB的存儲器中。考慮到每個RegExp中出現的字符數目有限，可以對其進行一次預處理，例如QQ數據包對應的RegExp中的字符分別為\\x02、\\x03、^\\x02^\\x03（即除了ASCII碼值為0x02和0x03的任意字符），可設定\\x02對應的偏移量為0，\\x03對應的偏移量為1，^\\x02^\\x03對應的偏移量為2，即產生三種編碼：0（\\x02）、1（\\x03）、2（^\\x02^\\x03）。這樣每個狀態對應的表項只有三項，明顯壓縮了狀態轉移表。

2．2體系結構

本文提出并實現的高速網絡協議識別設備的框架結構如圖3所示。

各模塊的功能歸納如下：

a）流查表模塊實現對報文的緩沖，以及對報文是否屬于某條已識別的流進行判別，實現流管理。

b）預編碼（Pre_code）模塊根據正則表達式中出現的字符，依其對應的ASCII碼值的大小順序進行編碼；對于正則表達式中未出現的字符，統一編成已編碼值的下一個數值。通過預編碼表實現字符對應的ASCII碼值向預編碼值的轉換對應。

c）編譯器中完成RegExp到NFA、DFA的轉換，狀態轉移表存放在一個N MB的存儲器中。

d）匹配引擎用硬件實現，對存儲器中狀態轉移表的讀取。

2．3硬件匹配算法

硬件匹配過程中，硬件邏輯需要保存三個變量，即報文當前字節（對應的ASCII碼值做偏移量）、活躍地址、是否為最后一個字節。

規則：

下一地址＝當前活躍地址＋報文當前字節對應的ASCII碼值

初始狀態：初始化活躍地址為0，報文位置為0。

算法如下：

while（報文未結束）

If 報文位置不是最后一個字節，對應的表項“是否最后一個字節”為0

if 是否識別==FAILreturn FAIL

if 是否識別==OK return OK

if 是否識別==CONTINUE

改變當前活躍地址

移動報文一個字節

Continue;

if 報文位置不是最后一個字節，對應的表項“是否最后一個字節”為1

改變當前活躍地址

移動報文一個字節

Continue;

if 報文位置是最后一個字節，對應的表項“是否最后一個字節”為0

if 是否識別==OKreturn OK

elsereturn FAIL

if 報文位置是最后一個字節，對應的表項“是否最后一個字節”為1

if是否識別==OKreturn OK

else return FAIL

2．4性能分析

實現基于FSM的高速網絡協議識別設備，主要難點在用軟件實現編譯器的設計與優化，硬件實現部分相對簡單。軟件優化算法可以加速從RegExp轉換成DFA的過程，壓縮狀態轉換表，提高硬件匹配引擎的速度。編譯完成QQ、POP3、SMTP、HTTP、Telnet和FTP常見的六種應用產生的狀態轉換表大小為19 630 Byte。所使用RAM的訪問頻率為166 MHz，兩個時鐘周期可以完成一次狀態轉移，通過對報文進行二分流，偶數時鐘輸入一路報文，奇數時鐘輸入另一路報文，流水處理后吞吐量可以達到1.32 Gbps=166×8。

3結束語

本文介紹了軟/硬件結合實現的基于FSM的高速網絡協議識別設備，用FSM表示RegExp，將狀態轉移表存放在存儲器中，實現高速的網絡協議識別，達到Gbps以上的性能。

當多個模式同時運行時，存儲器將成為系統的瓶頸。對于該設備吞吐率以及處理速度的提高，下一步將繼續研究并實現優化算法，壓縮狀態轉移表，并將嘗試運用合成的FSM解決多模式的問題。

參考文獻：

[1]陳亮，龔儉，徐選. 基于特征串的應用層協議識別[J]. 計算機工程與應用，2006，42(24):16－19.

[2][EB/OL]. http://l7－filter.sourceforge.net/technicaldetails.

[3]LEVANDOSKI J，SOMMER E，STRAIT M. Application layer packet classifier for Linux[EB/OL]. http://l7－filter.sourceforge.net/.

[4]YU F，CHEN Z. Fast and memory－efficient regular expression mat－ching for deep packet inspection， Tech Rep:UCB/EECS－2006－76[R]. [s.l.]: University of California Berkeley，2006.

[5]SIDHU R，PRASANNA V K. Fast regular expression matching using FPGAs[C] //Proc of the 9th IEEE Symposium on Field－Programmable Custom Computing Machines. Rohnert Park， CA: [s.n.]， 2001.

[6]CLARK C R，SCHIMMEL D E. Efficient reconfigurable logic circuit for matching complex network intrusion detection patterns[C] //Proc of International Conference on Field－Programmable Logic and Applications（FPL’03）. Lisbon， Portugal: [s.n.]， 2003.

[7]MOSCOLA J， LOCKWOOD J， LOUI R P， et. al. Implementation of a content－scanning module for an Internet firewall[C] //Proc of IEEE Workshop on FPGAs for Custom Comp Machines. Napa: [s.n.]， 2003.

[8][EB/OL]. http://www.regular－expressions.info/.

[9]HOPCROFT J E，ULLMAN J D. Introduction to automata theory， languages， and computation[M].[S.l.]: Addison Wesley，1979.

[10]AHO A V，SETHI R， ULLMAN J D. Compilers:principles， techniques， and tools[M]. [S.l.]: Addison Wesley/PEARSON，2001.

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文