[發明專利]一種基于正則表達式的匹配方法及裝置

有效

• 申請號: 202010042993.4
• 申請日: 2020-01-15
• 公開（公告）號: CN111222022B
• 公開（公告）日: 2023-05-12
• 發明（設計）人: 王彬;覃永靖;程詩堯;馬江波
• 申請（專利權）人: 奇安信科技集團股份有限公司;奇安信網神信息技術（北京）股份有限公司
• 主分類號: G06F16/903
• 分類號: G06F16/903;G06F9/448
• 代理公司: 北京路浩知識產權代理有限公司 11002
• 代理人: 苗曉靜

本發明實施例提供了一種基于正則表達式的匹配方法及裝置，包括將每個預設正則表達式轉化為對應的非確定有窮自動機NFA狀態，基于部分NFA狀態生成目標確定有窮自動機DFA狀態；創建目標DFA狀態對應的所有子DFA狀態，判斷每個子DFA狀態是否對應有次級子DFA狀態；若是，創建每個子DFA狀態對應的所有次級子DFA狀態，并判斷每個次級子DFA狀態是否對應有下一層級的次級子DFA狀態；若否，基于目標DFA狀態、每個子DFA狀態、每個次級子DFA狀態，及除部分NFA狀態之外的所有NFA狀態，生成目標混合有限自動機，以基于目標混合有限自動機執行匹配任務。本發明可以提高正則表達式的匹配性能，提高網絡安全性能。

技術領域

本發明涉及計算機技術領域，尤其涉及一種基于正則表達式的匹配方法及裝置。

背景技術

隨著計算機技術的不斷發展，為防止出現網絡安全事件，進行網絡安全檢測也顯得尤為重要。正則表達式作為一種匹配算法，由于其較強的靈活性、邏輯性和功能性，已逐漸成為網絡安全檢測中的關鍵技術。

目前，正則表示式通常編譯為有限自動機來執行匹配任務，有限自動機分為確定有窮自動機(Deterministic?finite?automaton，DFA)和非確定有窮自動機(Non-deterministic?finite?automaton，NFA)。由于DFA的匹配性能更好。所以，目前正則表達式匹配引擎通常會將NFA轉換為DFA，由DFA對網絡數據包(即待匹配數據)進行匹配，以實現網絡安全檢測。

NFA轉換為DFA的過程會占用較多的內存空間及CPU資源，從而會影響到正則表達式的匹配性能，導致對待匹配數據的匹配結果的準確性較低，進而會使得網絡安全檢測結果的準確性較低，網絡安全性能較差。故而，目前亟需一種高匹配性能的基于正則表達式的匹配方法。

發明內容

由于現有方法存在上述問題，本發明實施例提出一種基于正則表達式的匹配方法及裝置。

第一方面，本發明實施例提供了一種基于正則表達式的匹配方法，包括：

將每個預設正則表達式轉化為對應的非確定有窮自動機NFA狀態，基于部分NFA狀態生成目標確定有窮自動機DFA狀態；

當所述目標DFA狀態對應有子DFA狀態時，創建所述目標DFA狀態對應的所有子DFA狀態，并判斷每個子DFA狀態是否對應有次級子DFA狀態；

如果是，則創建每個子DFA狀態對應的所有次級子DFA狀態，并判斷每個次級子DFA狀態是否對應有下一層級的次級子DFA狀態；

如果否，則基于所述目標DFA狀態、每個子DFA狀態、每個次級子DFA狀態，及除所述部分NFA狀態之外的所有NFA狀態，生成目標混合有限自動機，以基于所述目標混合有限自動機對待匹配數據進行匹配。

第二方面，本發明實施例提供了一種正則表達式的匹配裝置，包括轉化模塊、創建模塊、判斷模塊及生成模塊，其中：

所述轉化模塊，用于將每個預設正則表達式轉化為對應的非確定有窮自動機NFA狀態，基于部分NFA狀態生成目標確定有窮自動機DFA狀態；

所述創建模塊，用于當所述目標DFA狀態對應有子DFA狀態時，創建所述目標DFA狀態對應的所有子DFA狀態，并判斷每個子DFA狀態是否對應有次級子DFA狀態；

所述判斷模塊，用于如果是，則創建每個子DFA狀態對應的所有次級子DFA狀態，并判斷每個次級子DFA狀態是否對應有下一層級的次級子DFA狀態；

所述生成模塊，用于如果否，則基于所述目標DFA狀態、每個子DFA狀態、每個次級子DFA狀態，及除所述部分NFA狀態之外的所有NFA狀態，生成目標混合有限自動機，以基于所述目標混合有限自動機對待匹配數據進行匹配。