以多核心圖形處理器為基礎之並行化正規表示樣式比對演算法與架構設計(I)

Abstract

正規表示(Regular Expression)已經被廣泛應用於網路入侵偵測系統中用來描述網路上惡意攻擊的特徵。由於正規表示樣式比對是系統中運算複雜度最高的程序，提升正規表示樣式比對程序的吞吐量(throughput)成為非常重要的課題。儘管有非常多的研究目標在改善速度，由於病毒大量的增加，系統仍然很難達到吞吐量的要求。在這個計畫中，我們企圖利用多核心圖形處理器(multicore Graphic Processing Unit, multicore-GPUs)來設計與實現高吞吐量的正規表示樣式比對程序。 我們都知道由於多核心圖形處理器在運算單元的數量、記憶體頻寬與記憶體時脈，都已超過目前高階的多核心電腦中央處理器(multicore Central Processing Unit, multicore-CPU)，在並行處理的程式下，使用多核心圖形處理器的運算效能會比多核心中央處理器快上數十倍甚至百倍，因此多核心圖形處理器除了用於影像處理的用途之外，也成功地被運用於科學計算，例如：運算型液體動力學、電子設計自動化、與數值運算等方面。然而，據我們所知到目前為止，尚未有研究利用多核心圖形處理器來處理網路入侵偵測系統上的問題。 然而，目前的編譯器無法有效地針對多核心圖形處理器進行優化，換言之，直接編譯正規表示比對的軟體至圖形處理器上執行，無法滿足高吞吐量的要求，仍必須仰賴設計者針對多核心圖形處理器硬體特性，設計並行化的演算法與程式技巧，以最佳化多核心圖形處理器的效能。因此，我們將分三年探討以多核心圖形處理器提升正規表示樣式比對並行度的相關議題： 1. 以多核心圖形處理器為基礎之並行化正規表示樣式比對架構：提高樣式比對頻寬，可以提高樣式比對並行度，進而提升系統的吞吐量與效能。然而增加頻寬，會遭遇邊界對齊(boundary alignment)與誤診(false positive)等問題，我們將提出改良的演算法以解決上述問題，並以多核心圖形處理器實現並評估改良演算法之效能與吞吐量。 2. 以多核心圖形處理器為基礎之階層式狀態機架構：合併正規演算法樣式可以有效提升樣式比對並行度。然而針對特定複雜的正規表示樣式，合併時會發生記憶體爆量的問題，我們將提出並行化之階層式狀態機架構以減輕這類正規表示樣式合併時之記憶體爆量問題，並以多核心圖形處理器實現並評估改良演算法之效能與吞吐量。 3. 以多核心圖形處理器效能導向之並行化正規表示樣式比對演算法與架構：以多核心圖形處理器並行處理正規表示樣式比對，其效能除了與演算法之並行化程度，有密切關係之外，更要瞭解多核心圖形處理器的硬體架構，以設計最佳化的計算方法和平行程式，我們將提出以多核心圖形處理器效能導向之並行化正規表示樣式比對架構的效能優化策略。 總結，我們將深入探討正規表示樣式比對演算法與架構並行化的議題並以NVIDIA之多核心圖形處理器實現與評估我們提出的演算法與架構。此外並以Snort、Bro、與L7-filter等系統之特徵樣式作為測試向量。我們期待我們提出的以多核心圖形處理器為基礎之並行化正規表示樣式比對演算法架構設計，可裨益於網路入侵偵測系統相關之發展。

Regular Expression has been widely used in Network Intrusion Detection Systems (NIDS) to represent network attack signatures. Because Regular Expression Pattern Matching is the most computation-intensive process in an NIDS, increasing the throughput of Regular Expression Pattern Matching has become a critical issue. Despite the tremendous amount of research seeking speed improvements, it is still very difficult for the system to meet the throughput requirement because of an ever increasing number of viruses. In this proposal, we intend to use multicore Graphic Processing Units (multicore-GPUs) to design and implement a very high-throughput Regular Expression Pattern Matching process. It is known that in areas such as the number of cores, memory bandwidth, and memory clock, the development of multicore-GPUs has progressed faster than that of multicore Central Processing Units (multicore-CPUs). Using parallel programming techniques, the performance of multicore-GPUs may be dozens of times, even hundreds of times faster than that of multicore-CPUs. Therefore, in addition to graphic processing, multicore-GPUs have been successfully applied to scientific computations, such as computational fluid dynamics, electronic design automation, numeric calculation, etc. However, as far as we know, there are no studies that focus on using the GPU to deal with the problem of network intrusion detection systems. Current compliers cannot effectively optimize programs for multicore-GPUs. In other words, directly compiling the regular expression matching software to multicore-GPUs will not achieve high throughput requirement. The optimization needs specific parallel algorithm and programming techniques based on the characteristics of multicore-GPU hardware architectures. Therefore, in this three year project, we intend to explore the parallelism techniques for Regular Expression Pattern Matching on multicore-GPUs. We will focus on the following three main issues. 1. Multicore-GPU based Architecture for Parallel Regular Expression Pattern Matching: Increasing bandwidth of pattern matching can increase parallelism and therefore improve throughput and performance, but suffers from the problems of boundary alignment and false positive. Therefore, we will propose a modified algorithm and implement on multicore-GPUs to evaluate the performance and throughput. 2. Multicore-GPU based Hierarchical State Machine Architecture: Compiling multiple regular expression patterns into a single composite Deterministic Finite Automaton (DFA) is an efficient way to increase the parallelism of Regular Expression Pattern Matching. However, there are specific Regular Expression patterns which cause the composite DFA to grow exponentially. Therefore, we will propose a Hierarchical State Machine Architecture to mitigate the memory explosion caused by such complex Regular Expression patterns, and then implement on multicore-GPUs to evaluate the performance and throughput. 3. Performance-Driven Multicore-GPU based Architecture for Parallel Regular Expression Pattern Matching: The performance of multicore-GPU based architecture for Parallel Regular Expression Pattern Matching is not only related to the parallelism of pattern matching algorithm, complexity of automaton, and memory requirements and allocation, but also closely linked to hardware architectures of GPUs, computation methodologies, and parallel programming. Therefore, we will propose optimization strategies for Parallel Regular Expression Pattern Matching on multicore-GPUs. In summary, we will study in detail the parallelism of Regular Expression Pattern Matching, and then implement and evaluate our Parallel Regular Expression Pattern Matching algorithm and architecture on the multicore-GPUs developed by the NVIDIA Corporation. Additionally, we intend to use Snort, Bro, and L7-filter as benchmarks to verify our results. We expect our proposed multicore-GPU based Architecture for Parallel Regular Expression Pattern Matching could be utilized for the development of NIDS.