正規表示法比對之演算法與硬體架構設計

Efficient Algorithm and Architecture Design for Regular Expression Matching

林政宏(Cheng-Hung Lin)

指導教授 ： 張世杰

國立清華大學/電機資訊學院/資訊工程學系/博士(2008年)

https://doi.org/10.6843/NTHU.2008.00008

摘要

網路入侵偵測系統(network intrusion detection system, NIDS)的主要功能為檢查網路封包的內容是否包含有害或可疑的攻擊特徵。這些特徵描述包括服務阻斷攻擊(denial of service attacks)、端口掃描(port scans)與惡意軟體(malware)的行為。為了有效描述攻擊特徵，正規表示法(regular expressions)被廣泛運用在包括Snort、Bro與ClamAV等入侵偵測系統上。由於網路複雜度與網路攻擊與日遽增，傳統以軟體為主的入侵偵測系統無法滿足網路效能的需求，因此有許多研究提出硬體架構以加速樣式比對(pattern matching)的效率，這些硬體架構可大致區分為邏輯架構(logic architecture)與記憶體架構(memory architecture)。
邏輯架構主要實現在Field-Programmable Gate Array (FPGA)上，因為FPGA允許不斷地更新病毒特徵，此外邏輯架構容易處理複雜的正規表示法特徵，例如：‘*’, ‘|’, 與‘+’等等。然而隨著病毒特徵的大量增加，如何降低邏輯架構的面積成為非常重要的課題，本論文第一部份提出一種新穎的硬體架構，可以抽出並分享共同的特徵，以降低邏輯架構的面積。
另一方面，記憶體架構亦被廣泛使用於入侵偵測系統上，因為記憶體架構具有重複規劃(re-configurability)與規模擴充(scalability)的優點。然而隨著病毒特徵的大量增加，記憶體架構一樣面臨記憶體爆量的問題。由於記憶體架構的效能、價格與耗能直接與記憶體大小相關，因此降低記憶體使用量對於記憶體架構而言非常重要。本論文第二部分提出一個新穎的樣式比對(pattern-matching)演算法可以有效降低記憶體架構的記憶體使用量。
然而，記憶體架構對於特定複雜的正規表示法特徵面臨記憶體爆量的問題。理論證明對於特定的正規表示法特徵，其對應的DFA會產生指數(exponential) 大小的狀態機(state machine)。本論文第三部份針對特定的複雜正規表示法特徵，提出一個新的記憶體架構，藉由加入有限的邏輯電路以改善傳統記憶體架構處理此類正規表示法特徵的能力。

關鍵字

網路入侵偵測系統 ； 正規表示法 ； 樣式比對

並列摘要

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 describe behaviors such as denial of service attacks, port scans, or malware. To efficiently represent suspicious patterns, regular expressions are commonly adopted such as Snort[22], Bro[24], and ClamAV[25] because they have better expressive power and flexibility than explicit string patterns. Due to the increasing complexity of network traffic and the growing number of attacks, traditional software-based NIDS will become inadequate for networking needs due to its slowness. To speed up pattern matching, many researchers have proposed hardware approaches which can be classified into two main categories, the logic and the memory architectures.
The logic architectures are mostly implemented on Field-Programmable Gate Array (FPGA) because FPGA allows for updating new attack patterns. In addition, the logic architecture is easy to handle certain types of regular expressions containing meta-characters, such as ‘*’, ‘|’, and ‘+’, etc. However, due to the increasing number of attacks, it is important to develop a new methodology to minimize the circuit area of the large number of regular expressions. Although the minimization of logic equations has been studied intensively in the area of computer-aided design (CAD), the minimization of multiple regular expressions has been largely neglected. In the first part of this dissertation, we present a novel sharing architecture allowing our algorithm to extract and share common sub-regular expressions.
On the other hand, the memory architecture is also widely adopted by NIDS because of the advantages of easy re-configurability and scalability. Due to the increasing number of attacks, the required memory increases tremendously. Because the performance, cost, and power consumption of the memory architecture are directly related to the memory size, reducing the memory size has become imperative. In the second part of this dissertation, we propose a memory-efficient pattern-matching algorithm which can significantly reduce the memory requirement for the memory architecture.
However, the memory architecture suffers the problem of memory explosion caused by certain types of regular expressions. It is well known that the number of states and transitions of a DFA can be exponential to the size of its corresponding regular expression. Implementing such regular expression pattern leads to extremely large memory requirements for storing the corresponding state transition table. In the third part of this dissertation, we propose a novel memory architecture which inserts marginal logic elements to improve the ability of traditional memory architecture to deal with complex regular expressions.

並列關鍵字

NIDS ； regular expression ； pattern matching

參考文獻

[2] B.L. Hutchings, R. Franklin, and D. Carver, “Assisting Network Intrusion Detection with Reconfigurable Hardware,” in Proc.10th Ann. IEEE Symp. Field-Program. Custom Comput. Mach. (FCCM), 2002, pp. 111-120.

[3] C. R. Clark and D. E. Schimmel, “Scalable Parallel Pattern Matching for High Speed Networks,” in Proc. 12th Ann. IEEE Symp. Field-Program. Custom Comput. Mach. (FCCM), 2004, pp. 249-257.

[5] Y. H. Cho and W. H. Mangione-Smith, “A Pattern Matching Co-processor for Network Security,” in Proc. 42nd Des. Autom. Conf. (DAC), 2005, pp. 234-239.

[6] M. Aldwairi*, T. Conte, and P. Franzon, “Configurable String Matching Hardware for Speeding up Intrusion Detection,” in ACM SIGARCH Computer Architecture News, 2005, pp. 99–107.

[7] S. Dharmapurikar and J. Lockwood, “Fast and Scalable Pattern Matching for Content Filtering,” in Proc. of Symp. Architectures Netw. Commun. Syst. (ANCS), 2005, pp. 183-192.