[發明專利]一種加速壓縮流量正則表達式匹配的Pairs方法

有效

• 申請號: 201810420111.6
• 申請日: 2018-05-04
• 公開（公告）號: CN108563795B
• 公開（公告）日: 2021-01-19
• 發明（設計）人: 胡成臣;孫秀文;李昊
• 申請（專利權）人: 西安交通大學
• 主分類號: G06F16/903
• 分類號: G06F16/903;H03M7/30
• 代理公司: 西安通大專利代理有限責任公司 61200
• 代理人: 徐文權

本發明一種加速壓縮流量正則表達式匹配的Pairs方法，核心部件是壓縮流量Pairs匹配引擎，其包括解碼模塊、Pairs匹配算法和有限狀態自動機三個處理模塊，以及處理過程所需的狀態記錄數據；壓縮流量Pairs匹配引擎使用待匹配正則表達式構建有限狀態自動機，之后對壓縮流量字節內容進行解碼，最后使用Pairs匹配算法進行匹配，輸出匹配結果；Pairs匹配算法使用有限狀態自動機掃描解碼后的文本字符串，使用Pairs算法對編碼字符串進行處理。該方法在保證得到與Naive方法相同的匹配結果的情況下，有效提升了對壓縮流量進行正則匹配的吞吐率，匹配速度快，實現簡便，擴展性強。

技術領域

本發明屬于壓縮流量的模式匹配方法，涉及針對使用gzip/DEFLATE壓縮編碼的HTTP等網絡流量進行正則表達式匹配的方法，具體為一種加速壓縮流量正則表達式匹配的Pairs方法。

背景技術

隨著壓縮技術在網絡流量中的廣泛應用，越來越多的Web服務器將HTTP頁面內容壓縮后發送給瀏覽器。2010年7月Alexa Top 1000的站點中有66％使用了HTTP壓縮，而2016年10月的Top 500站點中，該比例已超過90％。并且這些壓縮流量約為20％的壓縮比，嚴重影響了壓縮流量的匹配速度。

另外，為了全面多層次的匹配，越來越多的基于深度包檢測(Deep PacketInspection，DPI)的工具和應用采用正則表達式匹配引擎，識別流量中的特征。例如入侵檢測系統、流量計價和防火墻等。這些工具面對壓縮流量，通常采用以下兩種做法：

(1)樸素方法(Naive)：也就是先將壓縮流量進行完全解壓，之后再對解壓后的數據進行逐字節地模式匹配。該方法是最為樸素的方法，實現簡單，但由于壓縮的存在，使得處理吞吐率大大降低，成為系統整體過程中的性能瓶頸。

(2)補丁方法(Patch)：通過修改客戶端的請求，告知服務端自身不接收壓縮數據，從而強制服務端發送原始數據。這種方式相較于Naive來說，僅避免了流量解壓過程的開銷。但是破壞了客戶端與服務端之間通信數據的完整性；而且使用未壓縮的流量，也拋棄了HTTP設計壓縮流量的初衷，不能減少對網絡帶寬的使用。

目前，有許多關于多模式匹配的相關專利，如2010年12月01日公開的中國專利“一種多字符串匹配方法”、2007年10月10日公開的中國專利“一種多字符串匹配方法和芯片”、2013年08月21日公開的中國專利“基于后綴自動機正則引擎構造的深度包檢測方法”和2006年11月29日公開的中國專利“一種自適應多模式匹配方法及系統”，但它們均沒有涉及針對壓縮流量的多模式匹配。一些針對HTTP壓縮流量進行DPI的工作，其中，2012年發表在IEEE/ACM Transactions on Networking的文章中ACCH和2017年發表在IEEE/ACMInternational Symposium on Quality of Service的文章中COIN，均通過先解壓流量，之后利用解壓過程中所保存的信息，在匹配過程跳過對部分字符的掃描，以加速模式匹配的過程。然而他們只能對壓縮流量進行多字符串掃描，而不能應用于正則表達式的匹配中，進而也限制了應用場景。

2015年發表在IEEE Conference on Computer Communications的文章中ARCH是一種能夠對壓縮流量進行正則表達式匹配的方法，然而它的核心算法與ACCH相同，因此當編碼字符串中存在完整的模式之時，無可避免地對其重復掃描。另外，為適應ACCH算法而提出的計算depth參數的方法耗時較多，以至于相較于Naive的方法性能提升有限。

為進一步說明本發明的具體內容，我們首先對發明所涉及的技術和定義的名詞進行介紹：

A)gzip/DEFLATE；