[發明專利]一種基于特征值生成與檢索的防火墻規則匹配方法

有效

• 申請號: 201811590986.7
• 申請日: 2018-12-25
• 公開（公告）號: CN109729082B
• 公開（公告）日: 2021-11-19
• 發明（設計）人: 韓飛;季統凱
• 申請（專利權）人: 國云科技股份有限公司
• 主分類號: H04L29/06
• 分類號: H04L29/06
• 代理公司: 廈門市新華專利商標代理有限公司 35203
• 代理人: 徐勛夫

本發明涉及一種基于特征值生成與檢索的防火墻規則匹配算法。本發明的方法包括規則集處理和對數據包匹配；規則集處理包括輸入并初始化規則集、對每條規則生產特征值，以及，基于規則特征值的數字大小，對特征值進行排序；對數據包匹配包括：對待匹配的數據包生成特征值；在規則特征值集里二分查找生成的特征值；如果查找得到一致的特征值，執行對應規則的策略；如果查找不到，則向上去匹配比數據包特征值更大的規則特征值；查找和數據包特征值匹配的規則；匹配則執行規則設定的策略，不匹配則執行默認策略。本發明提供了一種性能出色，空間復雜度可控，對增減規則支持友好的防火墻規則匹配算法。

技術領域

本發明涉及信息安全技術領域，尤其是一種基于特征值生成與檢索的防火墻規則匹配算法。

背景技術

在互聯網與信息化時代，組織與個人時刻都在產生及請求大量數據。數據通過網絡交互傳輸，這其中又隱藏了大量的惡意信息。防火墻作為保障網絡安全的重要手段和設施，起著不可或缺的作用。防火墻設備的核心工作原理之一，就是根據預設或習得的規則，對過往數據包進行檢查匹配并處理。這其中，通信數據匹配性能成為影響防火墻網絡吞吐能力與響應速度的關鍵。高性能的數據包匹配策略與算法對優化防火墻設備網絡性能具有重大意義。

傳統的防火墻規則匹配算法具有各種不完善的地方。

比如linux的netfilter防火墻框架，對規則的匹配是簡單的順序匹配，具有線性時間復雜度，在大規模規則情景下效率低下。

Ternary CAM算法、Bitmap Intersection算法等是基于專用芯片與設備的算法，適用范圍狹窄。

Hierachical Tries是一種基于Trie樹的最長前綴匹配算法，該算法對規則維數的可擴展性支持比較差，規則動態更新困難，不支持業務邏輯層面的靈活高效匹配，比如地址范圍、端口范圍的比對；Set-Pruning Tries算法通過復制規則來改進了HierachicalTries算法的回溯問題，但是又帶來了空間復雜度上升以及對動態更新規則的困難；

RFC算法是另一類典型的包分類和規則匹配算法，其核心思想是構建規則的交叉乘積表來實現高效匹配。該算法實現比較復雜，在大規模規則集、多維的場景下，規則預處理和生成交叉乘積表的空間復雜度不可控。

還有另外一大類算法，核心思想是基于對規則的歷史匹配數統計(統計數據可以來自防火墻引擎或防火墻日志統計)，來調整規則的匹配順序和優先級，從而達到降低規則的平均匹配數量，改善性能的效果。這類算法的缺點在于它是依賴歷史匹配數統計，依賴待處理數據的特征以及匹配統計情況；因此性能不穩定；優點是實現很簡單。

發明內容

本發明解決的技術問題在于提供一種基于特征值生成與檢索的防火墻規則匹配算法；提供一種性能出色，空間復雜度可控，對增減規則支持友好的算法。

本發明解決上述技術問題的技術方案是：

所述的方法包括規則集處理和對數據包匹配；

所述的規則集處理包括輸入并初始化規則集、對每條規則生產特征值，以及，基于規則特征值的數字大小，對特征值進行排序；

所述的對數據包匹配包括：

對待匹配的數據包生成特征值；

在規則特征值集里二分查找生成的特征值；

如果查找得到一致的特征值，執行對應規則的策略；如果查找不到，則向上去匹配比數據包特征值更大的規則特征值；

查找和數據包特征值匹配的規則；匹配則執行規則設定的策略，不匹配則執行默認策略。

所述的輸入并初始化規則集包括對語義邏輯重復的規則進行清除，對具有復雜邏輯的規則進行分解，對規則進行邏輯上、格式上的完整補充。