請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/47772完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 顏嗣鈞 | |
| dc.contributor.author | Chia-Ming Chang | en |
| dc.contributor.author | 張家銘 | zh_TW |
| dc.date.accessioned | 2021-06-15T06:17:42Z | - |
| dc.date.available | 2015-08-18 | |
| dc.date.copyright | 2010-08-18 | |
| dc.date.issued | 2010 | |
| dc.date.submitted | 2010-08-10 | |
| dc.identifier.citation | [1] M. Roesch, “Snort – lightweight intrusion detection for networks,” Proceedings of the 13th Systems Administration Conference, USENIX, 1999.
[2] V. Paxson, “Bro: a system for detecting network intruders in real-time,” Computer Networks, volume 31, pp. 2435-3463, 1999. [3] A. Aho and M. Corasick, “Efficient string matching: An aid to bibliographic search,” Communications of the ACM, June 1975. [4] R. Boyer and J. Moore, “A fast string searching algorithm,” Communications of the ACM, volume 20, October 1977. [5] C. Coit, S. Staniford, and J. McAlerney, “Towards faster pattern matching for intrusion detection or exceeding the speed of Snort,” 2nd DARPA Information Survivability Conference and Exposition, June 2001. [6] M. Fisk and G. Varghese, “Fast content-based packet handling for intrusion detection,” TR CS2001-0670, UC San Diego, May 2001. [7] R Liu, N Huang, C Chen, and C Kao, “A fast string-matching algorithm for network processor-based intrusion detection system,” Transactions on Embedded Computing Sys., volume 3, pp. 614-633, August 2004. [8] I. Sourdis and D. Pnevmatikatos, “Fast, latge-scale string match for a 10gbps fpga-based network intrusion detection system,” International Conference on Field Programmable Logic and Applications, September 2003. [9] L. Tan and T. Sherwood, “A high throughput string matching architecture for intrusion detection and prevention,” International Symposium on Computer Architecture, June 2005. [10] T. Ptacek and T. Newsham, “Insertion, evasion and denial of service: Eluding network intrusion detection,” Secure Networks, Inc., January 1998. [11] D. Brumley, J. Newsome, D. Song, H. Wang, and S. Jha, “Towards automatic generation of vulnerability-based signatures,” IEEE Symposium on Security and Privacy, May 2006. [12] H. Wang, C. Guo, D. Simon, and A. Zugenmaier, “Shield: Vulnerability-driven network filters for preventing known vulnerability exploits,” Proceedings of the 2004 ACM SIGCOMM Conference, August 2004. [13] S. Rubin, S. Jha, and B. Miller, “Language-based generation and evaluation of NIDS signatures,” IEEE Symposium on Security and Privacy, May 2005. [14] R. Sommer and V. Paxson, “Enhancing byte-level network intrusion detection signatures with context,” ACM Conference on Computer and Communications Security, 2003. [15] S. Kumar, S. Dharmapurikar, F. Yu, P. Crowley, and J. Turner, “Algorithms to accelerate multiple regular expressions matching for deep packet inspection,” proceedings of ACM SIGCOMM, September 2006. [16] S. Crosby, “Denial of service through regular expressions,” Usenix Security work in progress report, August 2003. [17] R. Sidhu and V. Prasanna, “Fast regular expression matching using FPGAs,” Field-Programmable Custom Computing Machines, April 2001. [18] C. Clark and D. Schimmel, “Scalable pattern matching for high-speed networks,” IEEE Symposium on Field-Programmable Custom Computing Machines, pp. 249-257, April 2004. [19] I. Sourdis and D. Pnevmatikatos, “Pre-decoded CAMs for efficient and high-speed NIDS pattern matching,” IEEE Symposium on Field-Programmable Custom Computing Machines, April 2004. [20] R. Smith, C. Estan, and S. Jha, “XFA: Faster Signature Matching With Extended Automata,” IEEE Symposium on Security and Privacy, pp. 187-201, 2008. [21] F. Yu, Z. Chen, Y. Diao, T. Lakshman, and R. Katz, “Fast and memory-efficient regular expression matching for deep packet inspection,” Proceedings of Architectures for Networking and Communications Systems, pp. 93-102, 2006. [22] “Vaucanson,” http://www.lrde.epita.fr/cgi-bin/twiki/view/Projects/Vaucanson [23] K. Thompson, “Programming techniques: Regular expression search algorithm,” Communications of the ACM, Volume 11, pp. 419-422, June 1968. [24] “MIT DARPA Intrusion Detection Data Sets,” http://www.ll.mit.edu/mission/communications/ist/corpora/ideval/data/index.html | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/47772 | - |
| dc.description.abstract | 網際網路在世界上已經普及化且容易使用。為了保護來自網際網路的攻擊，我們需要網路入侵偵測系統。在網路入侵偵測系統的特徵碼比對中，使用自動狀態機為基礎的方法是一個有用的解決辦法。將網路入侵偵測系統的特徵碼表示成決定性的有限自動狀態機可達到非常快速的特徵碼比對，但其需要的記憶體空間卻非常巨大。另一方面，使用非決定性的有限自動狀態機將造成特徵碼比對的速度過慢，雖然它需要的記憶體空間非常小。
在某些論文中，使用變種的有限自動狀態機做網路入侵偵測系統的特徵碼比對已經被提出。舉例來說，使用延展的有限自動狀態機做特徵碼比對是快速的，且記憶體空間的需求也不高，但它需要一個人工設定的步驟且建構一個延展的有限自動狀態機需要花相當多的時間。另一個例子是複合決定性的有限自動狀態機，它提供了一個可以在使用的記憶體空間和特徵碼比對的時間上做調整的機制。在這篇論文中，我們提出了一個使用加權式自動狀態機做網路入侵偵測系統的特徵碼比對的方法，此方法快速且完全自動化。透過使用不同的半環來建構加權式自動狀態機，我們可以調校加權式自動狀態機的效率以及其記憶體使用空間。我們也提出了一些在建構加權式自動狀態機做特徵碼比對時需要用到的演算法。 | zh_TW |
| dc.description.abstract | The Internet has become popular and easy to use for everyone in the world. Network Intrusion Detection Systems (NIDS) are useful for preventing attacks from malicious users. The automata-based solutions are useful for signature matching in NIDS. Representing NIDS signatures as deterministic finite state automata results in very fast matching speed but the memory usage would blowup, on the other hand, using nondeterministic finite state automata to match signatures results in very small memory usage but slow signature matching.
Variant finite state automata have been introduced for signature matching in NIDS in several papers. For example, extended finite automata (XFA) is fast and small memory usage but it needs a manual configuration and large construction time. Another example is multiple-DFA, it provide a mechanism to trade memory usage for time by enforcing an upper bound on the available memory. In this thesis, we introduce another method to match signatures in NIDS by using weighted automata, which is fast and fully automatic. By controlling the semiring of weighted automata we could tune performance and memory usage of the weighted automata. We also provide several algorithms for constructing weighted automata to match signatures. | en |
| dc.description.provenance | Made available in DSpace on 2021-06-15T06:17:42Z (GMT). No. of bitstreams: 1 ntu-99-R97921058-1.pdf: 1222329 bytes, checksum: 3b7baa19e4aa002d9a41f408f9f12ab6 (MD5) Previous issue date: 2010 | en |
| dc.description.tableofcontents | 口試委員會審定書 #
誌謝 i 中文摘要 ii ABSTRACT iii CONTENTS iv LIST OF FIGURES vi LIST OF TABLES viii Chapter 1 Introduction 1 Chapter 2 Preliminaries 5 2.1 Regular Expression 5 2.2 Finite State Automata 9 2.2.1 Deterministic Finite State Automata 10 2.2.2 Nondeterministic Finite State Automata 11 2.3 Building a Deterministic Finite State Automaton from a Regular Expression 13 2.4 Weighted Automata 20 2.5 Vaucanson 25 Chapter 3 Using Weighted Automata for Signature Matching 26 3.1 Reducing State Number with Weighted Automata 27 3.2 Annotating Regular Expression 30 3.3 Modified Algorithms 31 3.4 Combining weighted automata 37 3.5 The Option of Semirings 39 Chapter 4 Feasibility Study 42 4.1 Experimental Methodology 42 4.2 Constructing Weighted Automata 43 4.3 Performance and Memory Usage 45 Chapter 5 Conclusion and Future Work 47 REFERENCES 49 | |
| dc.language.iso | en | |
| dc.subject | 網路安全 | zh_TW |
| dc.subject | 網路入侵偵測系統 | zh_TW |
| dc.subject | 加權式自動狀態機 | zh_TW |
| dc.subject | Network Intrusion Detection System | en |
| dc.subject | Weighted Automata | en |
| dc.subject | Network Security | en |
| dc.title | 用加權式自動狀態機做特徵碼比對 | zh_TW |
| dc.title | Signature Matching with Weighted Automata | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 98-2 | |
| dc.description.degree | 碩士 | |
| dc.contributor.oralexamcommittee | 雷欽隆,郭斯彥,莊仁輝 | |
| dc.subject.keyword | 網路安全,網路入侵偵測系統,加權式自動狀態機, | zh_TW |
| dc.subject.keyword | Network Security,Network Intrusion Detection System,Weighted Automata, | en |
| dc.relation.page | 51 | |
| dc.rights.note | 有償授權 | |
| dc.date.accepted | 2010-08-11 | |
| dc.contributor.author-college | 電機資訊學院 | zh_TW |
| dc.contributor.author-dept | 電機工程學研究所 | zh_TW |
| 顯示於系所單位： | 電機工程學系 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-99-1.pdf 未授權公開取用 | 1.19 MB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。