勝德臺灣大學:電機工程學研究所張清諒Chang, Ching-LiangChing-LiangChang2010-07-012018-07-062010-07-012018-07-062008U0001-2807200819244400http://ntur.lib.ntu.edu.tw//handle/246246/187966在入侵偵測系統中，正規表示法用非常適合用來描述網路攻擊特徵。本篇論文著重於如何用運管線架構到非決定狀態機的硬體實作來達到增加系統的產能。我們提出一種分享比較運算元的比較器，分享比較器包含了美國信息互換標準代碼解碼器、靜態樣式比對以及字元類別，接著我們分割比較器成為兩階段的管線。進一步，我們運用一個三階段管線到我們的正規表示樣式比對器；它包含了一個兩階段的比較器和一個一階段的非決定狀態機辨識器。此外，當使用三階段管線架構，還可以容易實作出起始字元。最後，實驗結果顯示，原本的正規表示法樣式比對器產出可以到1.8 Gbps，使用三階段管線架構則是2.4 Gbps的產出在Altera DE2上。由此可知，三階段管線架構增加效能比原先的架構足足提升了三十百分比。A regular expression is powerful to describe signature patterns used in an Intrusion Detection System (IDS). This paper focuses on how to employ a pipeline architecture to NFA-based hardware implementations in order to increase the system performance. We propose a comparator that shares comparison operators including the ASCII decoder, the static pattern matching, and the char classes, and then we partition the comparator into two stages. As a result, we apply a three-stage pipeline to our Perl compatible regular expression pattern matching engine (PCRE engine) including a two-stage pipeline comparator and a one-stage NFA-based pattern recognizer. In addition, we can easily implement Caret meta-character (means the beginning of a string) when using the three-stage pipeline architecture. Finally, experimental results show that the proposed three-stage PCRE engine has a throughput of 2.4 Gbps as compared with the 1.8 Gpbs of the original PCRE engine in an Altera DE2 platform. This means that the proposed approach can have 30% performance increase in the current implementation with respect to the non-pipeline one.口試委員會審定書 i謝 iiHESIS ABSTRACT iv一章 介紹 1二章 相關研究 5三章 方法 11一節 狀態樣板 11二節 PCRE系統架構圖 12三節 比較器架構圖 14四節 變化字元樣板 17五節 量化樣板 20六節 開始與結尾樣板 24七節 替代變化字元轉換 26八節 使用管線技術來提升產能 27四章 實作過程 29一節 PCRE樣式轉Verilog之編譯器流程圖 29二節 PCRE之編譯器 30三節 FPGA實作 35五章 實驗結果 39一節 辨識器最長路徑分析 39二節 普通比較器與管線化比較器 41三節 為什麼不使用兩個行平比較器 42四節 整體效能 42六章 結論 45考文獻 461790293 bytesapplication/pdfen-US現場可程式化閘陣列Perl相容正規表示法Snort樣式正規表示法FPGAPerl Compatible Regular ExpressionPatternRegular Expressionthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/187966/1/ntu-97-R95921085-1.pdf