針對記憶體受限裝置執行模式匹配的正規表達式分群演算法

Abstract

模式匹配是各種重要應用程序的關鍵，例如在封包檢測，它偵測惡意封包以保護網絡。為了使應用程序更強大，我們可能需要在資源受限的設備上執行模式匹配。例如，嘗試在智能網卡上應用DPI，以使我們的服務能夠在短時間內處理更多的封包。但是，DPI的內存需求可能比 NIC 所擁有的記憶體量大得多。因此，我們嘗試將正規表達式 分群，讓每個運算資源只需要構建較小的自動機。 為了實現這個想法，我們設計了一種通用的分群算法，稱為Evolutionary Rule Balancer。通過合適的估計和評估函數，該算法能夠適用於各種自動機模型。整個系統由FA Engine、Matched String Generator、FA Size Estimator和Intelligent Optimization Algorithm組成。該算法是有效率的，因為我們透過估計自動機大小避免構造過多的資動機。另一方面，利用 RegEx 的嵌入模型，我們的做法也支持動態更新。根據實驗結果，對於在多個 NFA 上執行的模式匹配，Rule Balancer 可以獲得更好的結果。

Pattern matching is the key component of various important applications such as deep packet inspection, which detects malicious packets to protect our network. To make the applications be more stronger, we may need to perform pattern matching on resource-constrained devices. For instance, we try apply DPI on smart network interface card to make our service be able to handle more packets in a short time. However, the memory space requirement can be much larger than NIC have. Therefore, we try to divide RegExes into several groups and build smaller FA for each core. To realize the idea, we design a general grouping algorithm, called Evolutionary Rule Balancer. With suitable estimation and evaluation functions, the algorithm should be able to work for various FA models. The entire system consists of FA Engine, Matched String Generator, FA Size Estimator and Intelligent Optimization Algorithm. This method is efficient as we estimate FA size to avoid too many FA constructions and the entire algorithm supports dynamic update by utilizing RegEx Embedding Model. Our experiments show that for pattern matching performed on multi-NFAs, Rule Balancer achieves better results.