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

有效

• 申請號: 201210071338.7
• 申請日: 2012-03-16
• 公開（公告）號: CN103294734B
• 公開（公告）日: 2016-11-16
• 發明（設計）人: 董群峰;彭坤楊
• 申請（專利權）人: 中國科學技術大學
• 主分類號: 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條目由源狀態域、輸入字符域和目的狀態域三個域組成，所述源狀態域由模板ID域和私有ID域兩個子域組成，分別用于存儲源狀態的模板ID編碼和私有ID編碼，所述目的狀態域由模板ID域和私有ID域兩個子域組成，所述模板ID域用于存儲目的狀態的模板ID編碼和源狀態的模板ID編碼的異或結果，所述私有ID域用于存儲目的狀態的私有ID編碼；

以具體的所述源狀態域和輸入字符域的拼接作為搜索關鍵詞，按照所述搜索關鍵字在所述DFA的所有TCAM條目中進行搜索，獲取搜索得到的目的狀態域，將所述目的狀態域中的模板ID域的值與所述搜索關鍵字搜索關鍵詞中的模板ID域的值進行異或，將所述異或結果作為所述目的狀態域中的最終的模板ID域的值。

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

TCAM條目構造模塊，用于將確定性有窮狀態自動機DFA的每個狀態用若干三態內容尋址存儲器TCAM條目表示，每個TCAM條目由源狀態域、輸入字符域和目的狀態域三個域組成，所述源狀態域由模板ID域和私有ID域兩個子域組成，分別用于存儲源狀態的模板ID編碼和私有ID編碼，所述目的狀態域由模板ID域和私有ID域兩個子域組成，所述模板ID域用于存儲目的狀態的模板ID編碼和源狀態的模板ID編碼的異或結果，所述私有ID域用于存儲目的狀態的私有ID編碼；