[發明專利]一種面向大規模ＵＲＬ過濾的多模式串匹配算法

在審

• 申請號: 201610813801.9
• 申請日: 2016-09-10
• 公開（公告）號: CN107818090A
• 公開（公告）日: 2018-03-20
• 發明（設計）人: 余漫游
• 申請（專利權）人: 長沙有干貨網絡技術有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術領域

本發明涉及一種多模式串匹配算法，尤其涉及一種面向大規模ＵＲＬ過濾的多模式串匹配算法。

背景技術

對大量有害的ＵＲＬ進行過濾，是目前網絡安全應用系統中所亟需的關鍵技術，目前有七類典型應用需要進行ＵＲＬ過濾，包括：色情內容、垃圾郵件、惡意軟件、漏洞利用、網絡釣魚、代理和可能不受歡迎的應用，對這些造成巨大危害的ＵＲＬ進行過濾，可以有效地對人們上網瀏覽非法、有害、不良信息內容進行控制與管理，創造綠色潔凈的網絡空間環境，在海量的網絡數據中檢測龐大的ＵＲＬ規則集，需要消耗大量的計算資源和存儲資源，如何保證串匹配算法仍然能夠高效實時地運行，是我們當前面臨的一個重大難題；

本文設計了一種適合于大規模ＵＲＬ過濾的多模式串匹配算法——ＳＯＧＯＰＴ，該算法在經典的ＳＯＧ算法基礎上，針對ＵＲＬ規則的特點，提出了最優窗口選擇、模式串分組規約這兩種優化技術，大幅度提高了算法的匹配速度，在大規模ＵＲＬ規則集上效果尤其顯著，實驗結果顯示：在１００萬ＵＲＬ規則上，ＳＯＧＯＰＴ算法的匹配速度是原始ＳＯＧ算法的４．３３倍，并且性能遠遠優于其它經典串匹配算法（ＡＣ、ＳＢＯＭ、ＫＲ、ＷＭ），本文設計的算法非常適合于大規模ＵＲＬ實時在線匹配的應用環境。

發明內容

一種面向大規模ＵＲＬ過濾的多模式串匹配算法，其特征在于，ＳＯＧ算法，ＳＯＧ算法是面向１０萬規模模式串的匹配方法。在隨機數據集上的測試表明，該算法優于眾多其它經典串匹配算法．該算法的基本思想是：首先，將模式串集合 Ｐ＝｛ｐ（１），ｐ（２），…，ｐ（ｒ）｝規約為一個通配形式的模式串ｐ；然后，使用位并行串匹配算法Ｓｈｉｆｔ－ＯＲ對ｐ進行搜索；最后，對于可能出現的匹配位置，使用二級哈希和二分搜索進行校驗，以報告所有真正匹配的結果，本質上，ＳＯＧ算法是一種過濾型串匹配算法，適合于模式串命中較少的應用場景。

一種面向大規模ＵＲＬ過濾的多模式串匹配算法，其特征在于，最優窗口選擇，當模式串長度不相等時，ＳＯＧ、ＷＭ、ＫＲ等算法需要從每個模式串中選取一個長度為ｍ的子串作為待查找的目標，這里 ｍ是最短模式串的長度，選取的長度為ｍ的子串稱之為窗口．對于模式串集合Ｐ＝ ｛ｐ（１），ｐ（２），…，ｐ（ｒ）｝，其中ｐ（ｉ）＝ｐ（ｉ）１ｐ（ｉ）２…ｐ（ｉ）ｍｉ有ｍｉ－ｍ＋１種可供選擇的窗口。

一種面向大規模ＵＲＬ過濾的多模式串匹配算法，其特征在于，模式串分組歸約，ＳＯＧ是一種過濾型匹配算法，它將模式串集合Ｐ＝｛ｐ（１），ｐ（２），…，ｐ（ｒ）｝規約為一個通配形式的模式串，然后利用該通配模式串進行粗過濾，排除掉不可能匹配的文本位置．對于剩下的可能出現匹配的文本位置，逐個進行校驗，以報告真正的匹配結果；隨著模式串集合規模的增大，ＳＯＧ 算法的過濾效果越來越差，需要進行校驗的次數越來越多，大幅度降低了算法的匹配速度，為了解決這個問題，本方法采用模式串分組歸約的方法來改進ＳＯＧ算法的過濾效果。

模式串分組歸約的基本思想是：將模式串集合Ｐ平均分為Ｇ組Ｐ＝Ｐ１∪Ｐ２∪…∪ＰＧ，每一組模式串Ｐｊ單獨規約為一個通配形式的模式串＾ｐｊ（１ｊＧ），然后將這Ｇ個通配模式＾ｐｊ拼接到一個機器字中，使用ＳＯＧ算法進行并行搜索．設機器字位寬為ｗ，因為每個通配模式＾ｐｊ需要ｍ－ｑ＋１比特位來表示，因此最多 可以將模式串集合劃分為 Ｇ＝ｗ/（ｍ－ｑ＋１）組。