具計數器共用之PERL相容正規表示法樣式比對架構

Abstract

目前正規表示法(Regular expression)以及PERL相容正規表示法(PERL compatible regular expression)在網路入侵偵測系統中，已經被廣泛地用來表示攻擊樣式。為了能夠匹配現代的高速網路，在近幾年的一些相關文獻中，已經有各種硬體架構被提出來，以達到快速的正規表示法比對。然而，由於網路的攻擊樣式數量正在持續成長當中，樣式比對電路所佔用的面積也將隨之增加。這對於樣式比對的硬體設計而言，將成為一大挑戰。因此，為了解決上述之問題，本論文提出一種共用計數器的硬體架構，透過共用樣式比對電路中的計數器，來縮小電路的面積及降低邏輯閘個數。為了達到正確的計數器共用，我們設計了一個演算法來判斷兩兩計數器之間是否可以彼此共用，並利用圖論中的著色演算法來決定哪些計數器將要在電路中共用，使得最佳化後的計數器個數能夠趨近於最少。此外，我們所提出的架構並不會與其他同樣以縮小電路面積為目標的架構互斥；相反地，我們的架構可以與其他架構結合，以達到更好的改善效果。實驗結果顯示，我們提出的演算法確實能夠減少電路中所使用的計數器個數，因此減小了比對電路的面積。另外，在與其他面積最佳化的架構整合之後，可達到更佳的改善效果。

Regular expressions and PCREs are widely used as a description language in many Network Intrusion Detection Systems (NIDS). To keep up with the high speed of modern networks, several NFA-based hardware architectures for performing regular expression matching were proposed previously. However, due to the rapid increase in the amount of signature patterns, the minimizing of the area of the circuit to accommodate all patterns has become a challenge. This thesis proposes a novel counter sharing architecture to reduce the number of counters used in NFA circuits and thus reduce the gate count of the regular expression matching circuit. We design an algorithm to determine if a counter can be shared with others. Also, a graph coloring algorithm is implemented to decide a group of counters that can share a common counter, making the total number of counters as small as possible. In addition, rather than competing with other area-optimized techniques, our approach can be integrated with them, hence achieving a higher reduction rate. Experimental results show that our approach can indeed reduce the area of the matching circuit, and a much higher reduction is achieved through integrating with other area-optimized approach.