[發明專利]基于TCAM的確定性有窮狀態自動機DFA的匹配方法和裝置

有效

• 申請號: 201210071502.4
• 申請日: 2012-03-16
• 公開（公告）號: CN103294735A
• 公開（公告）日: 2013-09-11
• 發明（設計）人: 董群峰;彭坤楊
• 申請（專利權）人: 中國科學技術大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京凱特來知識產權代理有限公司 11260
• 代理人: 鄭立明;黃曉軍

技術領域

本發明涉及計算機應用技術領域，尤其涉及一種基于TCAM(ternary?content?addressable?memory，三態內容尋址存儲器)的DFA的匹配方法和裝置。

背景技術

正則表達式技術是計算機網絡系統的一項核心基礎技術，被廣泛應用于入侵檢測和防護、簽名匹配、蠕蟲檢測、包內容過濾、流量分析、協議識別等領域。正則表達式具有靈活、強大的描述字符串模式的能力，正則表達式的匹配通過有限自動機實現，該有限自動機包括NFA(non-deterministic?finite?automaton，非確定性有限自動機)和DFA(deterministic?finite?automaton，確定性有限自動機)。即可將正則表達式編譯為一個NFA，然后可以將此NFA轉化為一個與之等價的DFA，通過NFA或者DFA的狀態轉換檢查輸入字符串中是否存在給定的正則表達式模式。NFA和DFA在存儲空間和匹配速度兩個方面擁有各自的優點和缺點。

有限自動機存儲的是一個狀態轉換表，給定一個當前活躍狀態和一個輸入字符，通過在狀態轉換表中查詢，可得到下一時刻活躍的狀態。自動機的存儲空間取決于這個狀態轉換表的大小，由于字符表的大小通常是確定的(如ASCII表)，所以自動機的存儲空間主要取決于狀態的個數。

NFA所需存儲空間小，其狀態數與正則表達式的規則集大小(即規則集中字符數)成線性增長關系。但NFA的匹配速度很慢。由于NFA的不確定性，對于每個字符，NFA中的狀態都有可能同時轉移到多個目的狀態，導致一次狀態轉換需要多次內存訪問。對于這些同時激活的目的狀態，在處理下一個輸入字符時，它們又會同時激活更多的目的狀態。因此，NFA的匹配速度是不可預測的，實際應用中，通常需要幾十次內存訪問才能完成一次NFA狀態轉換，遠不能滿足網絡線速(line?rate)。

DFA具有確定性的匹配速度，由于對于每個輸入字符，每個DFA狀態有且僅有唯一的目的狀態，因此每次DFA狀態轉換僅需一次內存訪問。但DFA的狀態數可能與正則表達式的規則集大小成指數增長關系，導致正則表達式規則通常無法用DFA存儲。目前的基于DFA的方法都無法突破一個存儲體積的瓶頸，即所存儲的DFA轉移邊的數目總是大于DFA狀態數，因此也就無法存儲狀態數成指數膨脹的DFA。

目前，由于上述有限狀態自動機的體量非常大，導致上述基于DFA的正則表達式匹配方法亟待改進。

【發明內容】

本發明的實施例提供了一種基于TCAM的DFA的匹配方法和裝置，以實現解決同時兼顧存儲空間和匹配速度的難題。

為實現上述的發明目的，本發明采用下述的技術方案：

一種基于TCAM的確定性有窮狀態自動機DFA的匹配方法，包括：

將確定性有窮狀態自動機DFA的每個狀態用若干三態內容尋址存儲器TCAM條目表示，每個TCAM條目由源狀態域、輸入字符域和目的狀態域三個域組成，基于生成所述DFA的非確定性有窮狀態自動機NFA中的鏈式結構，以及所述NFA和所述DFA之間的內在鏈式結構特征，識別出所述DFA中的鏈式結構；

根據所述DFA中的鏈式結構對所述DFA的狀態進行重新編號和編碼，在TCAM中對所述DFA的狀態轉移邊進行重新編碼；

以具體的所述源狀態域和輸入字符域的拼接作為搜索關鍵詞，按照所述搜索關鍵字在所述DFA的所有TCAM條目中進行搜索，將搜索得到的目的狀態域作為輸出結果。

一種基于TCAM的確定性有窮狀態自動機DFA的匹配裝置，包括：

DFA鏈式結構識別模塊，用于將DFA的每個狀態用若干三態內容尋址存儲器TCAM條目表示，每個TCAM條目由源狀態域、輸入字符域和目的狀態域三個域組成，基于生成所述DFA的非確定性有窮狀態自動機NFA中的鏈式結構，以及所述NFA和所述DFA之間的內在鏈式結構特征，識別出所述DFA中的鏈式結構；

重編碼處理模塊，根據所述DFA中的鏈式結構對所述DFA的狀態進行重新編號和編碼，在TCAM中對所述DFA的狀態轉移邊進行重新編碼；

搜索匹配模塊，用于以具體的所述源狀態域和輸入字符域的拼接作為搜索關鍵詞，按照所述搜索關鍵字在所述DFA的所有TCAM條目中進行搜索，將搜索得到的目的狀態域作為輸出結果。

本發明實施例通過對DFA狀態ID重新編號以反映DFA中鏈式結構副本的特征；最終基于重新編號的狀態ID，在TCAM中通過對DFA的狀態轉移邊進行編碼和壓縮，使得DFA中的副本鏈式結構在TCAM中能夠被合并，以達到減少存儲空間的目。