加速深層封包檢查的字串比對演算法

Abstract

為數增多的網路設備會檢視封包的內容來找尋違背安全的特徵字串。加速這個稱為深層封包檢查(Deep Packet Inspection; DPI)的程序，可從兩個方面進行：演算法及封包流程。這個研究著眼在前者。我們首先檢閱了現有用來做 DPI 的字串比對演算法，來看哪些已經做了以及哪些應該要解決的。在這個檢閱當中，我們指出每種演算法的優缺點，以及一個適合各種應用之不同的樣式集合的高延展性、有效率的設計仍是一種挑戰。我們也剖析了字串比對在各種不同樣式個數、長度及字元分佈的應用下的效能，以了解影響有效率的字串比對的重要因素。剖析的結果顯示出了哪種 DPI的應用適合哪種演算法。在考慮了前述的議題後，我們設計了一個可以利用演算法啟示法則的硬體字串比對引擎，以及給擁有龐大樣式集合的應用，如掃毒應用的一種混合的軟體方法。然而，單是字串比對不足以加速某些DPI 的應用，例如網頁過濾器。所以我們提出了一個機率方法，稱為早期決定演算法，來加速網頁過濾的分類。

這個研究有幾點重要的觀察與貢獻。首先，所做的檢閱和剖析研究了數個主要的 DPI應用，包含入侵偵測、掃毒和網頁過濾，而不像大部分現有的方法集中在入侵偵測上。這個研究也顯示了字串比對在入侵偵測上並非那麼嚴重，因此字串比對的發展在其他的應用也應受到關注。所做的剖析指出記憶體的存取(因此含快取的區域性)、驗證的頻率、和搜尋視窗的移動距離是影響效能的主要因素。

其次，所呈現的字串比對硬體架構，稱之為 Bloom Filter Accelerated Sub-linear Time (BFAST)，能從 Bloom filter中獲得演算法的啟示法則，在次線性的時間內掃描內容。BFAST 當中的 bad-block啟示法則能比過去使用查表的方式保留精確的資訊在 Bloom filter 當中，以得到較好的效能。我們也提出了處理最壞情況的一些務實的技巧，以及一個在理論上可以達到線性時間的方法。模擬顯示出使用8 個字元的區塊，可以讓單一字串比對引擎的效能在 16,384 個樣式下達到 9.34 Gbps。此外我們也提出了一個混合的掃描病毒方法，用於無法使用硬體方法時。我們把 ClamAV中的樣式依他們的長短做區隔，並使用衍生自 Wu-Manber (WM) 演算法的Backward-Hashing (BH)演算法來負責長樣式，以加長平均的移動距離，並讓 Aho-Corasick 演算法只處理短樣式以縮小自動機的大小。前者使用了bad-block 啟示法則以獲取更長的移動距離並減少驗證的頻率，所以比 ClamAV原先用的 WM 演算法更快。後者則因較好的快取區域性而提高了 AC 演算法約50%的效能。

除了加速字串比對外，我們也提出了一個簡單但有效的早期決定演算法，透過只檢查一部分的網頁內容來加速過濾流程。這個演算法能儘快做出要阻擋或是通過網頁內容的決定，只要有夠高的機率來判定該內容是屬於該阻擋或是該通過的種類。實驗結果顯示這個演算法平均能只看1/4 的網頁內容就已足夠做決定，而仍能保持相當好的準確度。這個演算法可與其他網頁過濾的方法互補來高效率地過濾網頁內容。

關鍵字：字串比對、演算法、深層封包檢查

An increasing number of network devices inspect the packet content for various signatures of security violation. Accelerating the process, namely deep packet inspection (DPI), can be in two aspects: algorithm and packet flow. This work focuses on the former. We first review existing string matching algorithms for DPI to see what work has been done and what should be addressed. In the review, we indicate the pros and cons of each algorithm, and a scalable, efficient design to meet the different characteristics of the pattern set in various applications is still a challenge. We also profile the performance of string matching in practical applications for various numbers, lengths and character distributions of the patterns to realize the key factors in efficient string matching. The results shed light on which approach is appropriate for each DPI application. Considering the above study, we design a hardware-based string-matching engine that can exploit algorithmic heuristics for acceleration, and a hybrid software method for applications with a large pattern set, say anti-virus applications. However, it is insufficient to accelerate some DPI applications, such as Web filter, with string matching alone. We thus present a probabilistic approach, namely the early decision algorithm to accelerate the classification in Web filtering.

This work features a number of observations and contributions. First, the review and profiling study several major DPI applications, including intrusion detection, anti-virus and Web filtering, unlike most existing work that focuses on intrusion detection. The study shows string matching is not so critical in intrusion detection, and its development for DPI should also cover other applications more. The profiling indicates memory access (thus also cache locality), verification frequency and shift distance of the search window are major factors that affect the performance.

Second, the presented hardware architecture of string matching, namely Bloom Filter Accelerated Sub-linear Time (BFAST), can exploit algorithmic heuristics with Bloom filters to scan the content in sub-linear time. The bad-block heuristic in the BFAST has better performance than that from the conventional table due to the precise information kept in the Bloom filters. We also propose practical techniques to handle the worst case, and the theoretical method to achieve linear worst-case time. The simulation shows that the peak throughput of a single match engine can achieve up to 9.34 Gbps for 16,384 patterns with an eight-character block in the heuristics. A hybrid method for virus scanning is also presented since the hardware approach may be not applicable. We partition the patterns in ClamAV into long and short ones. An algorithm enhanced from the Wu-Manber (WM) algorithm, namely the Backward-Hashing algorithm (BH), is responsible for only long patterns to lengthen the average skip distance, while the Aho-Corasick algorithm scans for only short patterns to reduce the automaton sizes. The former utilizes the bad-block heuristic to exploit long shift distance and reduce the verification frequency, so it is much faster than the original WM implementation in ClamAV. The latter increases the AC performance by around 50% due to better cache locality.

Besides speeding up string matching, we present a simple, but effective early decision algorithm to accelerate the filtering process by examining only part of the Web content. The algorithm can make the filtering decision, either to block or to pass the Web content, as soon as it is confident with a high probability that the content should belong to a banned or an allowed category. The experiments show the algorithm can examine only around one-fourth of Web content on average, while the accuracy remains fairly good. This algorithm can complement other Web filtering approaches to filter the Web content with high efficiency.

Keywords: string matching, algorithm, deep packet inspection