[發明專利]一種基于字符串的快速匹配識別方法和裝置

有效

• 申請號: 201810362354.9
• 申請日: 2018-04-20
• 公開（公告）號: CN108628966B
• 公開（公告）日: 2019-06-14
• 發明（設計）人: 李小坤
• 申請（專利權）人: 武漢綠色網絡信息服務有限責任公司
• 主分類號: G06F16/903
• 分類號: G06F16/903
• 代理公司: 深圳市六加知識產權代理有限公司 44372
• 代理人: 向彬

本發明涉及計算機技術領域，提供了一種基于字符串的快速匹配識別方法和裝置。其中方法包括確定字符串中存在動態變化的一個或者多個字符位，以及相應字符串中的靜態字符位；根據所述字符串中的靜態字符位的內容信息和所述一個或者多個動態字符位，更新字符串映射庫。本發明將其中動態變化的字符位進行了標定，并可以通過在常規的字典樹的數組中增設例如第257位，用于存儲對應所述動態變化的字符位的下一級數組的鏈接信息，從而極大的簡化了字典樹的冗余程度。

【技術領域】

本發明涉及計算機技術領域，特別是涉及一種基于字符串的快速匹配識別方法和裝置。

【背景技術】

深度包檢測技術(Deep Packet Inspect，簡寫為：DPI)技術是一種基于應用層的流量檢測和控制技術，當IP數據包、TCP或UDP數據流通過基于DPI技術的帶寬管理系統時，該系統通過深入讀取IP包載荷的內容來對OSI七層協議中的應用層信息進行重組，從而得到整個應用程序的內容，然后按照系統定義的管理策略對流量進行整形操作。

在DPI技術中，對網絡數據報文做應用識別和惡意流量分析時，通常會搜集到報文負載前n個字節中某些字節的特征，例如：騰訊QQ的網絡數據報文中就會在報文指定位置出包含QQ兩個字節；然后生成特定的規則庫，最后通過一個匹配引擎來將規則和數據包做匹配。然而，在實際操作過程中卻會遇到，由于n個字節中存在某個字節不確定，無法通過自動機(Aho-Corasickautomation，簡寫為：AC)算法建立狀態機來做匹配，所以一般會一條一條規則去遍歷匹配是否命中。遍歷規則在規則數量少的情況下可行，但在規則數量級上去之后，匹配的性能就會非常的低，匹配速率會相當的慢。這樣會帶來計算資源極大程度上的浪費，而現有技術中卻沒有針對此種情況的簡潔、高效的解決手段。

專利權申請號為CN201210132834.9的專利文檔公開了一種多模式字符串匹配方法和裝置。該方法包括：將多個模式串，按其各自的字符組成順序，沿樹結構的根節點向下，將每個字符寫入一個節點中，生成一個決策樹結構；將待匹配的主串沿所述決策樹向下進行匹配。本發明的技術方案，能夠實現多模式字符串的精確匹配，同時根據子節點對應的哈希值查找該子節點，決策樹的寬度改變并不會影響字符串匹配的CPU時間開銷，該算法的時間開銷只取決于決策樹的平均深度，與模式串的數量無關。對于模式串較多的字符串匹配，該算法能大量降低CPU的時間開銷，提高應用的響應速度。但是，該專利中不支持字符串中包含的未確定字符的匹配的情況。

專利權申請號：CN201310744154.7的專利文檔公開了一種基于非確定有限自動機的字符串搜索方法，包括構造非確定有限自動機NFA并為非確定有限自動機設定狀態變量；在所述非確定有限自動機中載入匹配表達式，并按照有向圖運算符轉換規則，將所述非確定有限自動機中的匹配表達式轉換為有向圖；根據所述狀態變量中的狀態位置，對進入所述非確定有限自動機的字符串中的字符開始匹配；若所述字符匹配成功則根據所述有向圖中該位置所指向的最終位置更新所述狀態變量，從所述更新的狀態變量中的位置開始對下一字符進行匹配，直到獲得符合所述匹配表達式的字符串或有字符匹配失敗則匹配完成；當所述匹配完成時，并將所述狀態變量置為開始位置。該專利是通過類似“((A*B|AC)D)”的邏輯運算符進行字符串匹配，該專利中的NFA算法是支持abc*cd，并且abc和cd中間不確定的字符*個數不限的情況，因此，相比較本發明所提出的應用場景，采用NFA算法雖然和一般的AC算法一樣可以解決本發明所涉及的技術問題，但是，其各自因為AC算法自身實現過于固化和單板，以及NFA算法自身的適用靈活性過大，無法實現本發明所提出應用場合下的資源有效利用和計算性能的提高。

【發明內容】