怎么提高大規模正則匹配的效能

這篇文章主要講解了“怎么提高大規模正則匹配的效能”，文中的講解內容簡單清晰，易于學習與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學習“怎么提高大規模正則匹配的效能”吧！

背景

日常工作中會大量應用正則表達式，用正則表達式去定義規則，然后去匹配數據。這里先看兩個安全場景下的正則應用需求

場景1，FTP賬號被成功暴力破解后數據遭竊取

? 數據源：FTP服務器日志

? 關聯邏輯：針對特定賬號暴力破解，然后利用該特定賬號登錄成功，之后利用該特定賬號下載大量文件

? 告警內容：FTP賬號${user_name}被成功暴力破解后竊取數據

? 告警級別：高危

場景1中，正則表達式用于在日志中匹配多次賬戶登錄的行為上。

場景2，Deep packet inspection (DPI) ，例如過濾網絡威脅和違反安全策略的流量等

? 數據源：網絡數據包

? 檢測規則條件：數據命中規則集

場景2中，正則表達式用于時間序列上的多個數據包之間的安全檢測。

其實，場景1中只列舉了FTP被攻擊的一種方式，FTP攻擊還有很多其他手段，所以檢測FTP被攻擊的正則匹配場景的另一個特征就是整個規則集可能很大；場景2中，利用已知的入侵行為構建模式集合，通過檢測網絡數據包，發現是否存在不符合安全策略的行為或被攻擊的跡象，這需要對數據包的載荷部分進行檢測，要求匹配的速度非常快，否則將會影響用戶體驗。

另一方面，這里用到的正則與傳統用法又不太一樣，對正則的傳統用法是，給定一個文本，用一個或少數幾個正則規則，去匹配文本，找出文本中匹配的數據。而現在面對的問題，首先是規則的數量大，上千上萬或者超過十萬的規則集，如果仍然采用之前的做法，用|分割，或者外層用循環去匹配，那么處理的時間將很長，對資源的消耗也很大，基本不可接受；其次在匹配的時候，待匹配的數據不是一個完整的整體，比如說網絡數據包，是一個一個接收的，這是一個流式的形式，傳統的正則處理引擎不能很好的處理流式數據，需要緩存一批數據去匹配，這樣匹配就不夠及時，而且目前正則處理有個很大的問題，如果正則表達式寫的不好，那么匹配會很慢。所以，需要一個解決方案來應對以下這些挑戰：

? 規則數量多

? 匹配速度要快

? 支持流式數據

? 資源消耗不能太大

Hyperscan算子介紹

針對上述正則匹配中遇到的挑戰，經過調研和對比測試市面上的主流正則匹配引擎，我們最終選擇了Hyperscan。

Hyperscan是Intel開源的高性能正則表達式匹配庫，提供了C語言API，目前已經在很多商業項目和開源項目中得到應用。

Hyperscan具備這些特性：

? 支持大部分PCRE正則語法（如果使用Chimera庫，那將支持所有語法）

? 支持流式匹配

? 支持多模匹配

? 采用特定指令集加速匹配

? 易于擴展

? 內部多種引擎結合

Hyperscan在設計之初就是為了更好的處理流式匹配和多模匹配，對流模式的支持極大的方便了正則用戶，不再需要用戶去維護接收到的數據，無需緩存數據；多模匹配允許把多個正則表達式傳入并在同一時間進行匹配。

因為需要特定的指令集，所以Hyperscan對CPU有要求，如下圖：

CPU最低要支持SSSE3指令集，最下面一行的指令集能加速匹配

和大多數正則引擎類似，Hyperscan也包括編譯和匹配階段，編譯是把正則表達式解析然后構建成內部需要的database，后續可以多次使用這個database去匹配；如果是多模匹配，編譯時每個正則表達式需要有一個唯一的標識id，id在匹配的時候會用到。編譯過程如下圖所示：

匹配的時候Hyperscan默認會返回所有命中的結果，這點不像有些正則引擎，指定貪婪的時候返回貪婪的匹配結果，指定懶惰的時候返回懶惰的結果。匹配時如果有命中，那么會以回調函數的形式通知用戶在哪個位置命中了哪個正則表達式id。匹配過程如下圖所示：

Hyperscan的缺點是只能是單機執行，沒有分布式能力，其可以解決延遲的問題，但無法解決吞吐的問題，解決吞吐問題，可以依靠主流實時計算框架Flink。Flink 是一個在無界和有界數據流上進行狀態計算的框架和分布式處理引擎。無界就是有開始但沒有結束的數據，無界的數據流計算即流式計算，有界就是有開始有結束的數據，有界的數據流計算即批處理。

Flink可以用于很多的計算場景中，這里列舉了3個，Flink可以處理事件驅動的程序，除了簡單事件，Flink還提供了CEP庫可以處理復雜事件；Flink還可以作為數據管道，做一些數據清洗篩選、轉換等操作，把數據從一個存儲系統轉移到另一個系統；Flink可以做流或批式數據的分析、指標計算，用于大屏展示等。Flink已經成為業界公認的流式處理的第一選擇。

把正則匹配引擎整合到Flink中，借助Flink強大的分布式能力，強強聯合，那么將會發揮更大威力。所以提供了這樣的解決方案，如下圖所示：

該解決方案實現了一個自定義的UDF算子，算子支持指定只匹配輸入數據中的某幾個字段，算子的輸出是待匹配的字段文本，匹配最終狀態，包括命中，不命中，錯誤，超時四種狀態，如果是命中的狀態，那么還會返回匹配中的正則表達式的id，輸出還包括輸入原始數據，如果有后續處理，這樣不受影響；為了進一步方便用戶使用，擴展了一個新的datastream，稱之為Hyperscanstream，它把算子封裝進了進去，用戶在使用時只需要把datastream轉換為Hyperscanstream，然后通過調用一個方法就可以使用正則的算子了。整個解決方案以一個獨立的jar包提供給用戶，這樣可以保持原來編寫Flink作業的習慣，并且與Flink的核心框架解耦。

數據流轉的過程是這樣，數據源讀取到一條記錄后交給下游的Hyperscan算子，Hyperscan算子把數據交給Hyperscan子進程，子進程匹配完成后把結果返回給Hyperscan算子，然后Hyperscan算子把原始記錄和匹配的結果傳遞給后續算子。

算子使用說明

私有化部署

針對私有化部署場景，用法如下，用戶首先需要去編輯正則表達式文件，然后用工具把正則表達式編譯為database并且序列化為本地文件，如果部署的環境中有HDFS，那么可以把序列化后的文件上傳至HDFS，如果沒有那就不用上傳，然后開發Flink作業，引用序列化的文件去匹配數據。

為什么要有工具編譯并序列化這一步呢，編輯完正則表達式，直接在Flink作業中使用不行嗎？前面說了，Hyperscan執行包括編譯和匹配階段，如果作業中只引用正則表達式，假設作業設置了并行度為5，那么每個task都需要編譯一次，一共需要編譯5次，浪費資源；而且編譯在hyperscan中是個相對緩慢的動作，所以把編譯過程單獨出來也為了加速flink作業在盡快執行。編譯提前進行也有利于提前知道正則表達式是否有語法錯誤，或者不支持的情況，而不是作業啟動后才知道。

私有化部署時，hyperscan相關依賴程序會提供給用戶，依賴程序通過全靜態編譯而來所以無需再添加依賴，只需機器支持需要的指令集即可。

公司內部使用

使用示例

假設現在要匹配的是HTTP報文中的Host字段和Referer字段，如下圖所示:

代碼示例如下圖：

整個邏輯分為四步，第一步要從數據源構建輸入流，第二步把輸入流轉換為Hyperscanstream，第三步調用hyperscan方法進而使用Hyperscan算子，在第一個參數HyperscanFunction中指定要匹配的是Host和Referer字段，第四步使用匹配返回的結果，返回的結果是Tuple2對象，其中第一個字段Event是原始記錄，在本例中就是整個HTTP報文，第二個字段是HyperScanRecord組成的List，HyperScanRecord類中包括匹配的字段，例如本例中Host或Referer，匹配命中的正則表達式id（如果匹配命中的話）和匹配的最終狀態。

使用1萬條規則集以及不同大小的待匹配樣本經過測試，方案達到了期望的性能，測試結果如下圖，

使用Hyperscan算子的一些建議，如下圖：

前面提到，在不使用himera庫時，Hyperscan有部分PCRE語法不支持的情況，在使用時要注意，下圖列舉了不支持的語法（使用Chimera庫將會影響匹配性能）

感謝各位的閱讀，以上就是“怎么提高大規模正則匹配的效能”的內容了，經過本文的學習后，相信大家對怎么提高大規模正則匹配的效能這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是億速云，小編將為大家推送更多相關知識點的文章，歡迎關注！