請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/42165
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 王勝德 | |
dc.contributor.author | Chang-Ching Yang | en |
dc.contributor.author | 楊長青 | zh_TW |
dc.date.accessioned | 2021-06-15T00:50:20Z | - |
dc.date.available | 2010-09-02 | |
dc.date.copyright | 2008-09-02 | |
dc.date.issued | 2008 | |
dc.date.submitted | 2008-08-14 | |
dc.identifier.citation | [1] Bro intrusion detection system. http://www.bro-ids.org/.
[2] flex: The fast lexical analyzer. http://flex.sourceforge.net/. [3] Pcre - perl compatible regular expressions. http://www.pcre.org/. [4] Snort - the de facto standard for intrusion detection/prevention. http://www.snort.org/. [5] A. V. Aho and M. J. Corasick. Efficient string matching: An aid to bibliographic search. Communications of the ACM, 1975. [6] M. Aldwairi, T. Conte, and P. Franzon. Configurable string matching hardware for speeding up intrusion detection. SIGARCH Comput. Archit. News, 33(1):99-107, 2005. [7] S. Antonatos, K. G. Anagnostakis, and E. P. Markatos. Generating realistic workloads for network intrusion detection systems. SIGSOFT Softw. Eng. Notes, 29(1):207-215, 2004. [8] Z. K. Baker and V. K. Prasanna. A methodology for synthesis of efficient intrusion detection systems on fpgas. In FCCM ’04: Proceedings of the 12th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, pages 135-144, Washington, DC, USA, 2004. IEEE Computer Society. [9] M. Becchi and P. Crowley. A hybrid finite automaton for practical deep packet inspection. In CoNEXT ’07: Proceedings of the 2007 ACM CoNEXT conference, pages 1-12, New York, NY, USA, 2007. ACM. [10] B. C. Brodie, D. E. Taylor, and R. K. Cytron. A scalable architecture for high-throughput regular-expression pattern matching. SIGARCH Comput. Archit. News, 34(2):191-202, 2006. [11] C. R. Clark and D. E. Schimmel. Efficient reconfigurable logic circuits for matching complex network intrusion detection patterns. In FPL ’03: 13th International Conference on Field-Programmable Logic and Applications, pages 956-959, 2003. [12] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms. The MIT Press, 2nd edition, 2001. [13] S. Dharmapurikar and J. W. Lockwood. Fast and scalable pattern matching for network intrusion detection systems. Selected Areas in Communications, IEEE Journal on, 24(10):1781-1792, Oct. 2006. [14] R. W. Floyd and J. D. Ullman. The compilation of regular expressions into integrated circuits. J. ACM, 29(3):603-622, 1982. [15] J. E. Hopcroft, R. Motwani, and J. D. Ullman. Introduction to Automata Theory, Languages and Computation. Addison-Wesley, 2nd edition, 2001. [16] S. Kumar, S. Dharmapurikar, F. Yu, P. Crowley, and J. Turner. Algorithms to accelerate multiple regular expressions matching for deep packet inspection. In SIGCOMM’06: Proceedings of the 2006 conference on Applications, technologies, architectures, and protocols for computer communications, pages 339-350, New York, NY, USA, 2006. ACM. [17] S. Kumar, J. Turner, and J. Williams. Advanced algorithms for fast and scalable deep packet inspection. In ANCS ’06: Proceedings of the 2006 ACM/IEEE symposium on Architecture for networking and communications systems, pages 81-92, New York, NY, USA, 2006. ACM. [18] J. Moscola, J. Lockwood, R. P. Loui, and M. Pachos. Implementation of a contentscanning module for an internet firewall. In FCCM ’03: Proceedings of the 11th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, page 31,Washington, DC, USA, 2003. IEEE Computer Society. [19] V. Paxson. Bro: a system for detecting network intruders in real-time. Comput. Netw., 31(23-24):2435-2463, 1999. [20] T. Ramabadran and S. Gaitonde. A tutorial on crc computations. Micro, IEEE, 8(4):62-75, Aug 1988. [21] M. Roesch. Snort - lightweight intrusion detection for networks. In LISA ’99: Proceedings of the 13th USENIX conference on System administration, pages 229-238, Berkeley, CA, USA, 1999. USENIX Association. [22] R. Sidhu and V. K. Prasanna. Fast regular expression matching using fpgas. In FCCM’01: Proceedings of the the 9th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, pages 227-238, Washington, DC, USA, 2001. IEEE Computer Society. [23] L. Tan and T. Sherwood. A high throughput string matching architecture for intrusion detection and prevention. In ISCA ’05: Proceedings of the 32nd annual international symposium on Computer Architecture, pages 112-122, Washington, DC, USA, 2005. IEEE Computer Society. [24] N. Tuck, T. Sherwood, B. Calder, and G. Varghese. Deterministic memory-efficient string matching algorithms for intrusion detection. INFOCOM 2004. Twenty-third Annual Joint Conference of the IEEE Computer and Communications Societies, 4:2628-2639 vol. 4, March 2004. [25] S. Wu and U. Manber. A fast algorithm for multi-pattern searching. Technical Report TR-94-17, Dept. of Comp. Science, Univ of Arizona, 1994. [26] Xilinx. Ml405 evaluation platform user guide. UG210 (v1.5.1). [27] F. Yu, Z. Chen, Y. Diao, T. V. Lakshman, and R. H. Katz. Fast and memory-efficient regular expression matching for deep packet inspection. In ANCS ’06: Proceedings of the 2006 ACM/IEEE symposium on Architecture for networking and communications systems, pages 93-102, New York, NY, USA, 2006. ACM. | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/42165 | - |
dc.description.abstract | 網路安全近年來已經被當成一項重要的議題,同時也發展了相當多種類的網路入侵偵測系統,這些偵測系統為了描述一些有可能造成安全威脅的特徵樣式,大部分都開始使用正規表示式。傳統上我們可以使用能力等同於這些正規表示式的有限自動機來辨識網路封包的資訊,而在多種有限狀態機的實現方法中,由於系統需要較快的處理速度以及隨時線上更新的能力,我們通常會選擇一種只需要執行單次掃描並以記憶體查表結果來決定下次狀態轉移的確定性有限狀態機來實現,但是此種實現方法在碰到“.*A. {N}B”類型的樣式時,會遭遇比對時需要的狀態數目太過巨大的問題。
本論文將探討現今網路的入侵偵測系統,討論範圍包括此種類型樣式的存在,以及造成狀態數劇烈增加的原因;並且進一步提出兩階段的正規表示式比對方法,預期解決這種樣式所引發的問題。兩階段的正規表示式比對方法可以將比對所需要的狀態數,從正比於重複限制數N的指數複雜度化約成線性複雜度,因此,使用我們的方法做為傳統確定性有限狀態機的輔助辨識器,能使上述的有限狀態機實現方法可以實作於現有的記憶體空間。另外,我們使用可現場規劃的邏輯陣列來實作這個輔助辨識器,可達每秒鐘處理超過十億位元的比對速度。 | zh_TW |
dc.description.abstract | 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. | en |
dc.description.provenance | Made available in DSpace on 2021-06-15T00:50:20Z (GMT). No. of bitstreams: 1 ntu-97-R95921079-1.pdf: 3334789 bytes, checksum: 0ae939826bd07d8882cb2aa8c1f8fe6e (MD5) Previous issue date: 2008 | en |
dc.description.tableofcontents | 誌謝 i
摘要 iii Abstract v List of Figures x List of Tables xii List of Algorithms xiii Chapter 1 Introduction 1 1.1 Motivation 2 1.2 Thesis Organization 3 Chapter 2 Background and Problem Analysis 5 2.1 Preliminary 5 2.1.1 Regular Expression in Computation theory 5 2.1.2 Syntax of Regular Expressions 8 2.1.3 Recognizer Design Consideration 9 2.2 In the Real World 11 2.2.1 An Example of Network Applications 11 2.2.2 Analysis of the Recognizer 12 2.2.3 The Prototype of Regular Expressions with State Problems 13 2.3 Summary 16 Chapter 3 Related Work 19 3.1 String Pattern Matching 19 3.2 Patterns using Regular Expression 20 3.3 Summary 22 Chapter 4 Proposed Matching Approaches 25 4.1 Motivation of Hybrid Matching 25 4.2 Multi-Staged Partition 26 4.3 Grouping 29 4.4 Summary 30 Chapter 5 Implementations 33 5.1 Hash Function 33 5.2 Pre-processing 36 5.2.1 The Format of Memory Contents 36 5.2.2 Translator 37 5.3 Run-time Matcher 41 5.3.1 Evaluation Board 41 5.3.2 Architecture 42 5.4 Summary 47 Chapter 6 Experiment Results 49 6.1 Comparison 49 6.2 Throughput 52 6.3 Summary 53 Chapter 7 Conclusions 55 7.1 Future Work 56 Bibliography 57 Appendix A Hash Functions 61 | |
dc.language.iso | en | |
dc.title | 用於入侵偵測系統的兩階段正規表示式比對方法 | zh_TW |
dc.title | Two-Phase Pattern Matching for Regular Expressions in Intrusion Detection Systems | en |
dc.type | Thesis | |
dc.date.schoolyear | 96-2 | |
dc.description.degree | 碩士 | |
dc.contributor.oralexamcommittee | 鄭振牟,雷欽隆,洪士灝,李漢銘 | |
dc.subject.keyword | 入侵偵測,樣式比對,正規表示式,確定性有限自動機,兩階段比對引擎, | zh_TW |
dc.subject.keyword | Network Intrusion Detection,Pattern Matching,Regular Expressions, | en |
dc.relation.page | 60 | |
dc.rights.note | 有償授權 | |
dc.date.accepted | 2008-08-15 | |
dc.contributor.author-college | 電機資訊學院 | zh_TW |
dc.contributor.author-dept | 電機工程學研究所 | zh_TW |
顯示於系所單位: | 電機工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-97-1.pdf 目前未授權公開取用 | 3.26 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。