以多核心圖形處理器為基礎之並行化正規表示樣式比對演算法與架構設計(II)
No Thumbnail Available
Date
2011-07-31
Authors
林政宏
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
網路入侵偵測系統（Network Intrusion Detection System, NIDS）已經被廣泛運用於 保護電腦系統免於網路攻擊。正規表示(Regular Expression)已經被廣泛應用於網路入侵 偵測系統中，例如Snort [1], Bro [2], and Linux L7-filter [3] 以用來描述網路上惡意攻擊的 特徵。為了辨識網路攻擊的特徵，近來有多個研究採用多核心圖形處理器（Graphic Processor Units, GPU）來加速特徵比對的程序。然而，這些研究並未處理複雜的正規表 示法樣式。而這些複雜的正規表示法已經在目前網路入侵偵測系統之中佔有極重要的角 色。 在這個計畫中，我們將深入研究正規表示法樣式比對平行化的問題並企圖善用GPU 加速正規表示法樣式比對的速率。我們將說明利用GPU加速正規表示法樣式比對，包含 了傳統邏輯架構與記憶體架構的優點。首先，GPU的方法如同記憶體架構一樣可以輕易 的更新病毒攻擊樣式，而GPU的方法也類似邏輯架構，具有多重並行的硬體，可以平行 比對病毒特徵。然而，利用GPU加速正規表示法樣式比對，仍存在三個主要的挑戰。首 先，我們需要一個高效率的平行演算法來處理大量的簡單正規表示法樣式。第二，我們 需要解決特定型態的複雜正規表示法樣式轉換為DFA時，會導致記憶體爆量的問題。第 三、我們需要一個架構可以整合簡單與複雜正規表示樣式比對於一個單一平台。 因此，在這個計畫中，我們將企圖發展一個新穎的平行演算法於GPU上，來加速正 規表示樣式比對程序。同時，我們也要針對複雜的正規表示樣式，發展一個創新的狀態 機架構，以解決記憶體爆量問題並可以實行於GPU的平行化架構。此外並以Snort與Bro 等系統之特徵樣式作為測試向量。
Network Intrusion Detection System (NIDS) has been widely used to protect computer systems from network attacks. In terms of expressive power and flexibility, regular expression has been adopted in many NIDS systems, such as Snort [1], Bro [2], and Linux L7-filter [3], to represent certain attack patterns instead of string expressions. To recognize network attack patterns, several recent researches adopt Graphic Processor Units (GPUs) to speed up the matching process. However, all of them cannot deal with complex regular expressions which have become an important representation in virus database. In this proposal, we will study in detail the parallelism of regular expression pattern matching and attempt to utilize the GPU hardware to speed up regular expression pattern matching. We will show that the GPU approach combines the advantages of both logic-based and memory-based hardware approaches. First, the GPU approach can easily update the new attack patterns. But the GPU approach is also similar to the logic-based approach, inasmuch as multiple hardware units can simultaneously process data. Still, there are three major challenges in accelerating regular expression matching by GPUs. First, we need an efficient parallel algorithm to process massive attack patterns, which mainly consist of simple regular expressions. In addition, we need to resolve certain types of complex regular expressions which incur the memory explosion problem when being translated into DFA. Third, we need a smooth way to integrate the simple and the complicated regular expressions in the same platform. Therefore, in this proposal, we intend to develop a novel parallel algorithm to accelerate regular expression matching performed on GPUs. We also intend to develop an innovative state machine for complex regular expression patterns, the state machine of which is more suitable for performing in the parallel algorithm. Additionally, we intend to use Snort and Bro as benchmarks to verify our results.
Network Intrusion Detection System (NIDS) has been widely used to protect computer systems from network attacks. In terms of expressive power and flexibility, regular expression has been adopted in many NIDS systems, such as Snort [1], Bro [2], and Linux L7-filter [3], to represent certain attack patterns instead of string expressions. To recognize network attack patterns, several recent researches adopt Graphic Processor Units (GPUs) to speed up the matching process. However, all of them cannot deal with complex regular expressions which have become an important representation in virus database. In this proposal, we will study in detail the parallelism of regular expression pattern matching and attempt to utilize the GPU hardware to speed up regular expression pattern matching. We will show that the GPU approach combines the advantages of both logic-based and memory-based hardware approaches. First, the GPU approach can easily update the new attack patterns. But the GPU approach is also similar to the logic-based approach, inasmuch as multiple hardware units can simultaneously process data. Still, there are three major challenges in accelerating regular expression matching by GPUs. First, we need an efficient parallel algorithm to process massive attack patterns, which mainly consist of simple regular expressions. In addition, we need to resolve certain types of complex regular expressions which incur the memory explosion problem when being translated into DFA. Third, we need a smooth way to integrate the simple and the complicated regular expressions in the same platform. Therefore, in this proposal, we intend to develop a novel parallel algorithm to accelerate regular expression matching performed on GPUs. We also intend to develop an innovative state machine for complex regular expression patterns, the state machine of which is more suitable for performing in the parallel algorithm. Additionally, we intend to use Snort and Bro as benchmarks to verify our results.