- 學位論文
用於入侵偵測系統的兩階段正規表示式比對方法
Two-Phase Pattern Matching for Regular Expressions in Intrusion Detection Systems
摘要
網路安全近年來已經被當成一項重要的議題，同時也發展了相當多種類的網路入侵偵測系統，這些偵測系統為了描述一些有可能造成安全威脅的特徵樣式，大部分都開始使用正規表示式。傳統上我們可以使用能力等同於這些正規表示式的有限自動機來辨識網路封包的資訊，而在多種有限狀態機的實現方法中，由於系統需要較快的處理速度以及隨時線上更新的能力，我們通常會選擇一種只需要執行單次掃描並以記憶體查表結果來決定下次狀態轉移的確定性有限狀態機來實現，但是此種實現方法在碰到“.*A. {N}B”類型的樣式時，會遭遇比對時需要的狀態數目太過巨大的問題。 本論文將探討現今網路的入侵偵測系統，討論範圍包括此種類型樣式的存在，以及造成狀態數劇烈增加的原因；並且進一步提出兩階段的正規表示式比對方法，預期解決這種樣式所引發的問題。兩階段的正規表示式比對方法可以將比對所需要的狀態數，從正比於重複限制數N的指數複雜度化約成線性複雜度，因此，使用我們的方法做為傳統確定性有限狀態機的輔助辨識器，能使上述的有限狀態機實現方法可以實作於現有的記憶體空間。另外，我們使用可現場規劃的邏輯陣列來實作這個輔助辨識器，可達每秒鐘處理超過十億位元的比對速度。
並列摘要
Recently, network security has become an important issue. Agood number of network intrusion detection (NID) systems are employed to detect potential attacks. Some NID systems may use regular expressions to describe the signatures of security threats. Traditionally, we can build finite-state automata corresponding to these regular expressions to identify the suspicious packets. Because of the high speed and update ability, the memory-based deterministic finite-state automata(DFA) with one-pass-scanning model are desirable for NID systems. However in practical implementations, there are some signature patterns that can cause the state explosion problem when applying this model. A prototype of these signature patterns is “.*A.{N}B”. In this thesis, we first argue that the state explosion problem does exist in the common signature patterns of an NID system. Then we propose a two-phase matching approach for regular expressions to solve the state explosion problem. It reduces the state storage cost from the exponential complexity to linear complexity with respect to N. By applying this approach as a co-processing unit with the traditional DFA, the memory-based DFA approaches can be achieved in practice. We also implement the two-phase matching engine, which is called TPME unit, in a field programmable gate array(FPGA) and the throughput of the pattern matching process can achieve over 1.86 gigabits per second.
參考文獻
延伸閱讀
- Hung, C. Y. (2009). 對於網路入侵偵測系統之功能平行化樣本比對演算法 [master's thesis, National Chiao Tung University]. Airiti Library. https://doi.org/10.6842/NCTU.2009.00653
- 王智弘、宋孝謙、邱業宸、楊吉閔、陳彥學（2014）。兩類型入侵偵測攻擊圖與警報關連配對之研究。資訊安全通訊，20(4)，41-53。https://www.airitilibrary.com/Article/Detail?DocID=a0000270-201410-201410300016-201410300016-41-53
- 邱奕湶（2012）。比較PCRE與RE2正規表達式函式庫在Snort入侵偵測系統中之效能〔碩士論文，淡江大學〕。華藝線上圖書館。https://doi.org/10.6846/TKU.2012.00486
- 任祥蓉（2008）。利用兩個非常態分配之樣本資料對製程能力指標的估計與比較分析〔碩士論文，淡江大學〕。華藝線上圖書館。https://doi.org/10.6846/TKU.2008.00593
- Tsai, W. Y. (2006). A Novel Multi-pattern Matching Algorithm and Implementation in SoC System [master's thesis, National Tsing Hua University]. Airiti Library. https://www.airitilibrary.com/Article/Detail?DocID=U0016-1303200709331594