具前置共用和字串共用PERL相容正規表示比對架構

Abstract

資訊安全對於系統管理者與使用者而言相當重要。許多網路入侵偵測系統使用正規表示式或PERL相容正規表示式法來表示它們的樣式。為了跟上網路流量，學者提出建立於確定有限狀態自動機和非確定有限狀態自動機基礎上之硬體化PERL相容正規表示式樣式比對架構。由於比對樣式的增加，樣式比對架構的電路面積會變大，電路面積減少成為一個議題。在這篇論文，我們使用前置共用、字串共用、預先解碼和字符類塊的方式來減少非確定有限狀態自動機型態的硬體架構。我們設計一個極盡所能地擷取前置共用的演算法，並在不增加電路複雜度下，加上字串共用來更進一步減少電路面積。此外，我們在實驗中測試大量的SNORT比對條例，高達2281條。實驗結果顯示，我們的方法可以產生2281筆條例的比對引擎，在virtex-6的器材上減少約35%的邏輯單元。此方法有效於減少電路面積。

Network security is important for both system managers and end users. Lots of network intrusion detection systems (NIDS) use regular expressions or PCREs as a description language to represent their signature patterns. To keep up the network flow rate, hardware PCRE pattern matching architectures based on NFA or DFA are proposed. Owing to the ever signature patterns, the circuit area required to implement the pattern matching architecture for regular expression is becoming large. Thus, the reduction of the area of the circuit becomes an important issue. In this thesis, we reduce the circuits required to realize an NFA-based hardware architecture with common prefix sharing, common string sharing, pre-decode and character-class blocks. We design an algorithm to fetch as more common prefix as possible. The common string sharing can further reduce the circuit area without increasing the complexity. In addition, we test as many as 2281 snort rules, quiet many rules, in the experiment. The experiment results show that our approach is able to generate a regular pattern engine to match 2281 rules and is able to reduce 35.5% logic cells on a virtex-6 device. It is effective to reduce the area of circuit.