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

有效

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

技術領域

本發明涉及計算機應用技術領域，尤其涉及一種基于TCAM(ternary?content?addressable?memory，三態內容尋址存儲器)的NFA(non-deterministic?finite?automaton，非確定性有限自動機)的匹配方法和裝置。

背景技術

從最早的grep(global?search?regular?expression?and?print?out?the?line，全面搜索正則表達式并把行打印出來)，到現在非常流行的PCRE(Perl?Compatible?Regular?Expressions，perl語言兼容正則表達式)，正則表達式因其強大、便捷、高效的文本處理能力，得到了廣泛的使用。目前，幾乎所有主編程流語言都支持正則表達式；在軟件開發和日常數據處理工作中，正則表達式更是人們不可或缺的得力助手。

正則表達式是一種“通用的模式語言”，它由兩種字符構成：特殊字符和普通字符。特殊字符稱為“元字符”，普通字符稱為“文字”。“文字”就像語言中的單詞，“元字符”則像文法；把單詞按文法組織起來，就有了語義。正如文章由句子段落構成一樣，一個完整的正則表達式也是由小的模塊單元組成的。雖然模塊單元各自都很簡單，但它們的組合卻千變萬化。正是這種簡單模塊的復雜組合，使得正則表達式具有了強大的表達能力。

例如，正則表達式a+b可以用來描述ab，aab，aaab，......等一系列特征的

字符串。正則表達式匹配技術是一項用于檢測給定的輸入字符流中是否包含特定的正則表達式所描述的模式的技術，它計算機網絡系統的一項核心基礎技術，被廣泛應用于如入侵檢測和防護、簽名匹配、蠕蟲檢測、深度包檢測、流量分析、協議識別等等。正則表達式的匹配通過有限自動機實現，即將正則表達式的規則編譯成一個等價的有限自動機，包括NFA(non-deterministic?finite?automaton，非確定性有限自動機)和DFA(deterministic?finite?automaton，確定性有限自動機)。

基于自動機的正則表達式匹配技術急需解決的兩大難題是自動機的存儲體積和匹配速度。在這兩個關鍵性能指標上，DFA和NFA各自具有不同的優點和缺點。

DFA的每個狀態對于每個輸入字符都只轉移到一個唯一的目的狀態，使得在DFA運行的時刻，都只有一個狀態是活躍的，因此DFA實現正則表達式匹配的過程非常簡單：一次DFA狀態轉換即可處理一個輸入字符。DFA因此具有確定的匹配速度，但是DFA所需的狀態空間可能呈現指數膨脹，在最壞情況下，具有n個狀態的DFA，其等價的DFA可能多達2n個狀態，在實際的網絡應用中，幾十個具有“.*”結構(表示匹配任意多數量的任意字符)的正則表達式組合在一起，就會使得編譯得到的DFA因為狀態空間發生指數膨脹而無法存儲。而隨著網絡應用和流量的快速發展，需要同時檢測的正則表達式規則往往成千上萬，基于DFA的正則表達式技術往往變得不可行。

NFA的優點在于它的存儲體積小，其體積與正則表達式規則集大小(即規則集中字符數)成線性增長關系，即使成千上萬條規則，所生成的NFA占用的體積也很小。但NFA的狀態轉移具有不確定性，對于NFA的每一個狀態和每一個字符，它所到達的目的狀態的數目是不唯一的，也就是說一個NFA狀態可以經過一個字符激活多個NFA狀態，而這多個NFA狀態被同時激活以后，在處理下一個輸入字符時，又可能進一步激活更多的狀態。因此在NFA運行的過程中，總是會有一組數目不確定的狀態同時活躍。由于同時活躍的狀態所組成的集合始終是NFA全體狀態集合的一個子集，我們把NFA運行時可能出現的活躍狀態組成的集合稱之為活躍狀態子集，NFA的一次狀態轉換的過程也就是一個源活躍狀態子集經過一個輸入字符激活一個目的活躍狀態子集的過程。

目前，NFA的上述特征導致其匹配速度變得緩慢和不可預測。實際應用中，通常需要幾十次內存訪問甚至更多才能完成一次NFA狀態轉換，遠不能滿足網絡線速。

發明內容

本發明的實施例提供了一種基于三態內容尋址存儲器的正則表達式的匹配方法和裝置，以提高基于NFA的正則表達式匹配的速度。

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

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