由於網際網路應用蓬勃發展，網路安全問題也日益重要。其中如何偵測非法之網路入侵事件，便是一項很重要的工作。我們知道在入侵偵測系統中，樣式比對扮演著相當重要的腳色，被廣泛的使用到網路安全來偵測攻擊或是病毒。但是樣式比對的行程也是網路入侵偵測最耗時之部分，以SNORT 來說，樣式比對是整個軟體執行的33%。除此之外，也使用掉相當的CPU運算量。
在論文中，我們提出以軟硬體協同設計的方法來實現著名的SNORT 開放性原始碼網路入侵偵測系統。我們將SNORT 系統移植到以ARM9為核心的嵌入式系統，嵌入式系統內之作業環境為Linux作業系統，並且將SNORT 內部最耗時的樣式比對工作以FPGA硬體實現之，我們採用SNORT 內部Aho-Corasick演算法，因為AC演算法可以同時比對多個字串，且保證最壞的情況下之效能。且實驗證明了本系統可以增加SNORT 在分析異常資料封包之速度。

Due to the rapid advance of internet, the security issue becomes more and more serious. Network Intrusion Detection (IDS) is now one of the most important security issues. It is known that pattern matching is the essential way for an IDS software to identify illegal behaviors, warms, and viruses from the outside world. This has been an effect approach, however, very time consuming. Take the famous IDS software SNORT for example, it has been reported that nearly 1/3 computation time is spent on pattern matching. Now, the challenge of IDS comes from how to maintain real time inspection, while the speed of data transmission on the internet and the patterns to be matched keep growing. Purely software solution may not meet the ever increasing demand of performance.
Therefore, some solutions based on hardware/software co-design strategies are developed. In this paper, we propose an embedded IDS system. The embedded O.S. adopts Linux kernel[2.4.18]. We have ported the SNORT software to the system. The hardware system contains an ARM9 32-bits micro-processor. The most time consuming part, the pattern matching, is done by a specific hardware circuit realized in an FPGA chip.
We used Aho-Corasick algorithm for pattern matching. It can do multi-pattern matching at a comparable lower time complexity. We also give some experimental result to demonstrate the effectiveness and efficiency of our design.

摘要 ii
英文摘要 iii
致謝 iv
目次 v
表目錄 vii
圖目錄 viii
第一章 緒論 1
1.1 背景 1
1.2 分析架構 7
1.3 研究動機 8
1.4 國內外相關研究 9
1.5 論文架構 10
第二章 SNORT 網路入侵偵測系統 12
2.1 SNORT 簡介 12
2.2 SNORT 原理 13
第三章 樣式比對 17
3.1 樣式比對定義 17
3.2 Aho-Corasick 樣式比對演算法 17
3.3 SFK-search 樣式比對演算法 19
3.4 Modified Wu-Manber 樣式比對演算法 20
第四章 嵌入式系統 21
4.1 ARM9 介紹 21
4.2 ARM9 架構 22
4.3 ARM9 周邊架構 24
第五章 軟硬體協同實現 26
5.1 嵌入式入侵偵測系統架構 26
5.2 SDRAM的配置 28
5.3 ARM9與FPGA溝通架構 31
5.4 Linux kernel與FPGA溝通 32
5.5 平台測試 34
5.6 樣式比對硬體實現 39
5.6.1 位址解碼單元 40
5.6.2 樣式比對單元 42
第六章 實驗結果 46
6.1 測試環境架構介紹 46
6.2 測試結果 47
6.2.1 測試條件一 48
6.2.2 測試條件二 51
第七章 結論 53
附錄A 54
附錄B 57
附錄C 59
參考文獻 62

[01] Symantac corp. “Symantac Government Internet Security Threat Report,” Trends for January-June 07, vol XII, Published September 2007.
[02] C. Dowell and P. Ramstedt, “The COMPUTERWATCH data reduction tool” in Proc. 13th National Computer Security Conf., Washington, DC, Oct. 1990, pp. 99-108.
[03] W. T. Tener, “Discovery: an expert system in the commercial data security environment,” in Proc. Fourth IFIP TCII International Conf. on Computer Security, Noth-holland, Dec. 1986.
[04] S. E. Smaha, “Haystack: An intrusion detection system,” in proc. IEEE Fourth Aerospace Computer Security Applications, Orlando, FL, Dec. 1988.
[05] T. F. Lunt et al., “IDES: A progress report,” in Proc. Sixth Aunnal Computer Security Applications Conf., Tucson, AZ, Dec. 1990.
[06] H. S. Javitz and A. Valdez, “The SRI IDES statistical anomaly detection, ” in Proc. IEEE Symposium on Research in Security and Privacy, Oakland, CA, May 1991.
[07] M. M. Sebring et al., “Expert system in intrusion detection: A case study,” in Proc. 11th National Computer Security Conf., Baltimore, MD, Oct. 1988.
[08] D. E. Denning, “An intrusion detection model,” IEEE Trans. Software Engineer, vol. SE-13, no. 2, Feb 1987.
[09] http://www.SNORT .org
[10] H. S. Javitz and A. Valdes, “The NIDES statistical component: description and justification,” Technical Report, Computer Science Laboratory, SRI International, 1993.
[11] L. T. Heberlein et al., “A network security monitor,” in Proc. Symposium on Research in Security and Privacy, Oakland, CA, May 1990, pp. 296-304.
[12] S. R. Snapp et al., “DIDS(Distributed Intrusion Detection System) – motivation, architecture, and an early prototype,” in Proc. 14th national Computer Security Conf., Washington, D.C., Oct. 1991.
[13] J. Marcus, K. Landfield, M. Stolarchuk, M. Sienkiewicz, A. Lambeth, and E. Wall, “Implementing a generalized tool for network monitoring,” http://www.nfr.com/forum/publications/LISA-97.html, 1999.
[14] S. C. Lee and D. V. Heinbuch, “Training a neural-network based intrusion detector to recognized novel intrusions,” IEEE Trans. Systems, Man, and Cybernetics – Part A: Systems and Humand, vol. 31, no. 4, pp., July 2001.
[15] Lippmann, P. Richard, and “Using key-string selection and neural networks to reduce false alarms and detect new intrusions with Sniffer-based intrusion detection system,” in Proc. RAID Conf., Nov. 1999, pp. 429-433.
[16] W. Lee and S. J. Stolfo, “Data mining approached for intrusion detection,” inProc. 1998 USENIX Security Symposium, 1998.
[17] Y. T. Lin, S. S. Tseng, and S. C. Lin, “An Intrusion detection model based upon intrusion detection markup language(IDML),” Journal of Information Science and Engineering, vol. 17, no. 6, pp. 899-919, 2001.
[18] Y. T. Lin, S. S. Tseng, and S. J. Lin, “Intrusion detection markup language(IDML) and IDML based intrusion detection model,” in Proc. 5th World Multiconf. On Systemics, Cybernetics and Informatics, SCI 2001, Orlando, USA, 2001.
[19] R. S. Boyer and J. S. Moore, “A fast string searching algorithm,” Commun. Of ACM, vol. 20, no. 10, pp.762-772, Oct. 1977.
[20] D. E. Knuth, J. H. Morris, and V. R. Pratt, “Fast pattern matching in strings,” TR CS-74-440, Standford University, Stanford, California, 1974.
[21] V. Aho and M. J. Corasic, “Efficient string matching: an aid to bibliographic search,” Commun. Of ACM, vol. 18, no. 8, pp. 333-340, June 1975.
[22] E. P. Marktos, S. Antonatos, M. Polychronakis, and K. G. Anagnoatakis, “ExB: Exculsion-based signature matching for intrusion detection,” in Proc. International Conf. Commun. And Computer Network. IASTED, Combridge, USA, Nov. 2002, pp. 146-152.
[23] K. G. Anagnostakis, E. P. Markatos, S. Antonatos, and M. Polychronakis, “E2xB: A domainspecific string matching algorithm for intrusion detection,” in Proc. 18th IFIP International Information Security Conf. (SEC2003), May 2003.
[24] S. Wu and U. Manber, “A fast algorithm for multi-pattern searching,” Tech. Report TR94-17, Dept. of Computer Science, Univ. of Arizona, May 1994.
[25] M. Necker, D. Contis, and D. Schimmel, “TCP-Stream reassembly and state tracking in hardware,” in proc. IEEE Field-Programmable Custom Computing Machines Symposium, April 2002, pp. 22-24.