正規表示法樣式比對之演算法與硬體架構設計
No Thumbnail Available
Date
2009-07-31
Authors
林政宏
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
網路入侵偵測系統(network intrusion detection system, NIDS)的主要功能為檢查網路 封包的內容是否包含有害或可疑的攻擊樣式特徵。這些特徵描述包括服務阻斷攻擊 (denial of service attacks)、端口掃描(port scans)與惡意軟體(malware)的行為。為了有效描 述攻擊特徵，正規表示法(regular expressions)被廣泛運用在包括Snort、Bro 與ClamAV 等 入侵偵測系統上。 為了加速正規表示法比對，記憶體架構的硬體設計被廣泛使用於入侵偵測系統上， 因為記憶體架構具有重複組態(re-configurability) 與規模擴充(scalability) 的優點 [5][6][7][8][9]。記憶體架構的設計中，其中一個重要的議題在於降低記憶體的大小。主 要原因是記憶體架構的效能、價格與耗能直接與記憶體大小相關，因此降低記憶體使用 量對於記憶體架構而言非常重要。 然而，記憶體架構對於特定複雜的正規表示法樣式（regular expression pattern）面 臨記憶體爆量的問題，例如含有wildcard 與constraint repetitions的正規表示法樣式。實 現這類複雜的正規表示法樣式，會造成非常大的記憶體需求。因此，解決這類正規表示 法樣式所造成的記憶體爆量變成非常迫切。本研究將深入研究哪些正規表示法樣式會造 成記憶體爆量，並提出一個新的記憶體架構與演算法來處理這類正規表示法樣式。我們 將以Snort當作我們的testbench，以驗證我們的結果。
The main purpose of a network intrusion detection system (NIDS) is to inspect the packet header and payload against thousands of predefined malicious or suspicious patterns. These patterns which describe behaviors such as denial of service attacks, port scans, or malware are commonly represented as regular expressions such as Snort[22], Bro[24], and ClamAV[25]. To speed up regular expression matching, the memory architecture based hardware design is widely adopted by NIDS because of the advantages of easy re-configurability and scalability of the memory architecture[5][6][7][8][9]. One of the key design issues in the memory architecture is to reduce the memory size because the performance, cost, and power consumption of the memory architecture are directly related to the memory size. However, it is well known that the memory architecture suffers from the problem of memory explosion caused by certain types of complex regular expressions such as wildcards and constraint repetitions. Implementing those types of regular expression pattern leads to extremely large memory requirements. As a result, it is imperative to handle those regular expressions causing memory explosion. In this proposal, we intend to study in detail which regular expressions can cause memory problem and propose new memory architecture accompanied with new algorithm to deal with those regular expressions. We intend to use SNORT as test benches to verify our results.
The main purpose of a network intrusion detection system (NIDS) is to inspect the packet header and payload against thousands of predefined malicious or suspicious patterns. These patterns which describe behaviors such as denial of service attacks, port scans, or malware are commonly represented as regular expressions such as Snort[22], Bro[24], and ClamAV[25]. To speed up regular expression matching, the memory architecture based hardware design is widely adopted by NIDS because of the advantages of easy re-configurability and scalability of the memory architecture[5][6][7][8][9]. One of the key design issues in the memory architecture is to reduce the memory size because the performance, cost, and power consumption of the memory architecture are directly related to the memory size. However, it is well known that the memory architecture suffers from the problem of memory explosion caused by certain types of complex regular expressions such as wildcards and constraint repetitions. Implementing those types of regular expression pattern leads to extremely large memory requirements. As a result, it is imperative to handle those regular expressions causing memory explosion. In this proposal, we intend to study in detail which regular expressions can cause memory problem and propose new memory architecture accompanied with new algorithm to deal with those regular expressions. We intend to use SNORT as test benches to verify our results.