[發明專利]一種多字符串匹配方法和芯片

無效

• 申請號: 200710099389.X
• 申請日: 2007-05-18
• 公開（公告）號: CN101051321A
• 公開（公告）日: 2007-10-10
• 發明（設計）人: 嵩天
• 申請（專利權）人: 北京哲安科技有限公司;嵩天
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京三高永信知識產權代理有限責任公司
• 代理人: 何文彬

技術領域

本發明涉及信息處理領域，特別涉及一種多字符串匹配方法和芯片。

背景技術

多字符串匹配技術，也叫多關鍵詞匹配技術，已經比較成熟，并且廣泛的應用于文本處理、內容過濾等很多領域。該技術能夠在一維的待匹配內容中發現預先定義的一組字符串中的一個或多個，在匹配文本的過程中，充分利用一組字符串中的特點，進行預處理，并且根據預處理后的中間數據結構進行內容匹配，從而實現對一組預定義字符串的匹配。

多字符串匹配算法的性能主要受以下幾方面影響：字符串集合(也叫規則集、特征集、關鍵詞集)的數量、字符串集合的最小長度、待匹配文本中出現匹配的可能性等。根據多字符串匹配技術對字符串集合預處理方法的不同，相關匹配算法可以分為以下三類：

前綴算法，包括：KMP、AC、Shift-AND、Shift-OR等；

后綴算法，包括：Boyer-Moore、Wu-Manber等；

子串模式算法，包括：BDM、BOM、SBDM、SBOM等。

在網絡安全領域中，有一類基于內容的安全應用需要利用多字符串匹配技術，典型應用如入侵檢測和防御系統、垃圾郵件過濾、病毒掃描和過濾、惡意代碼掃描和過濾、內容過濾等。這類應用對多字符串匹配技術的典型使用方式是通過程序抓取網絡中的數據包，并將其還原成特定網絡層的數據，根據預先定義的規則集(如入侵規則、病毒規則、垃圾郵件規則等)在數據中進行匹配。

由于網絡帶寬的發展十分迅速，為了能夠滿足千兆甚至更高網絡帶寬下內容的安全應用需求，對高性能的多字符串匹配技術的需求十分迫切。為了不斷提高多字符串匹配技術的匹配性能，出現了一些改進的軟件算法，盡管改進的算法匹配性能有一定的提高，但提高幅度仍然十分有限，通常能夠較傳統算法提高性能20％-40％。僅通過軟件實現上述已有算法已經無法滿足實際系統對該技術的性能需求。

在實際的多字符串匹配技術應用中，有一個算法因為具有如下一些特點而倍受青睞：匹配的性能與規則庫的大小無關、匹配的性能與規則庫的最小長度無關、匹配的性能與規則庫和待匹配文本之間的關系無關。這個軟件算法叫做AC(Aho-Corasick)算法。

如圖1所示，其中，圓圈表示狀態，線條表示轉換規則，有6個狀態和16個轉換規則，以字符串集合P＝{SIG，SSH}進行匹配為例，AC算法將P進行預處理，對其構造一個有限狀態自動機(DFA，Deterministic?Finite?Automata)，通過該有限狀態自動機，對待匹配的一維文本(比如SSSIG)，可以每次讀入一個字符，并且在上述結構中根據轉換關系，每次向前前進一個位置，當到達S3或者S5位置時，算法報告出一個有效匹配。

盡管AC算法具有上述優點，但也有比較明顯的缺陷。對于P＝{SIG，SSH}這樣簡單的規則集，該算法的中間結構(即DFA)一共需要6個狀態和16個轉換規則。隨著規則集中規則數量的增加，AC算法中間結構的規模將成指數形式遞增，造成存儲空間爆炸，應用領域十分有限。

現有技術中還有提出了一種帶優先級的轉換規則存儲方法，可以將AC算法中將狀態帶回初始狀態和初始狀態的下狀態的轉換規則合并成最多256條規則。在實際應用中，可以在一定程度上減少轉換規則的數量。該技術將狀態帶回初始狀態的轉換規則定為高優先級，將狀態帶回初始狀態的下狀態的轉換規則定為次優先級。參見圖2，其中，圓圈表示狀態，線條表示轉換規則，有6個狀態14條規則，通過優先級描述，實際存在的規則為6條，如表1所示：

表1