臺灣博碩士論文加值系統

特徵(signature)比對在防止病毒/蠕蟲(virus/worm)應用中是個重要的技術。已經有許多大家所熟知的字樣比對(pattern matching)演算法，像是KMP、BM以及AC演算法。AC演算法將字樣事先處理並建造一個可以同時比對多個字樣的有限狀態機。AC演算法的另一個優點是它可以在所有環境底下保證其有一定的效能(performance)。因此，AC演算法在很多系統中被廣泛的使用，特別是當效能為主要訴求時。但是，AC演算法只能針對一般字樣(byte-string)比對，然而病毒/蠕蟲之特徵可以由簡單的正規表示式(regular expression)呈現。在本篇論文中，我們延展AC演算法，使其可以系統性的建構有限狀態字樣比對機，此字樣比對機可以在有限的輸入字串(string)中找出第一個字樣發生(first occurrence)的結束位置(ending position)且字樣可以是一般字樣或是正規表示式字樣。若我們事先使用可疑字樣過濾器(pre-filter)找出可疑字樣之起始位置，我們可以大幅度減低字樣比對機之複雜度。實驗結果顯示出我們所提出之字樣比對機之比對效能，比ClamAV的方法好很多。

Signature matching is considered an important technique in anti-virus/worm applications. There are some well-known pattern matching algorithms such as Knuth-Morris-Pratt (KMP), Boyer-Moore (BM), and Aho-Corasick (AC). The AC algorithm pre-processes the patterns and builds a finite automaton which can match multiple patterns simultaneously. Another advantage of the AC algorithm is that it guarantees deterministic performance under all circumstance. As a consequence, the AC algorithm is widely adopted in various systems, especially when worst-case performance is an important design factor. However, the AC algorithm was developed only for strings while virus/worm signatures could be specified by simple regular expressions. In this thesis, we generalize the AC algorithm to systematically construct a finite state pattern matching machine which can indicate the ending position in a finite input string for the first occurrence of virus/worm signatures that are specified by strings or simple regular expressions. We show that the complexity of the pattern matching machine cab be largely reduced if some pre-filter scheme is used to locate the starting positions of suspicious sub-string in the scanned text string. Experimental results show that our proposed pattern matching machine yield much better throughput performance than the ClamAV implementation.

中文摘要 i
English Abstract ii
誌謝 iii
第一章 簡介 1
1.1 研究背景 1
1.2 研究動機 2
第二章 相關工作 4
2.1 Aho-Cirasick演算法 4
2.2 可疑字樣過濾器 6
第三章 入侵偵測系統 9
3.1 入侵偵測系統簡介 9
3.2 ClamAV 10
第四章 應用於網路安全之正規表示式字樣之比對演算法 13
4.1 相關問題與定義 13
4.1.1 相關問題 13
4.1.2 相關定義 14
4.2 應用於網路安全之正規表示式字樣之比對演算法 16
4.2.1 僅有*運算子之正規表示式 16
4.2.2 僅有{min, max}運算子之正規表示式 24
4.2.3 {min, max}以及*運算子之正規表示式 26
4.2.4 程式流程圖及演算法 29
第五章 可疑字樣過濾器之使用 34
5.1 相關原理 34
5.2 使用pre-filter之範例 36
第六章 實驗模擬結果與比較 40
第七章 結論 44
參考文獻 45

[1] Clam Anti-Virus signature database, http://www.clamav.net.

[2] Clam Anti-Virus 0.90.3 user manual, http://www.clamav.net.

[3] Clam Anti-Virus, http://zh.wikipedia.org/wiki/ClamAV.

[4] D. E. Knuth, J. H. Morris, and V. R. Pratt, “Fast pattern matching in strings,” TR CS-74-440, Stanford University, Stanford, California, 1974.

[5] R. S. Boyer and J. S. Moore, “A fast string searching algorithm,” Communications of the ACM, Vol. 20, October 1977, pp. 762-772.

[6] A. V. Aho and M. J. Corasick, “Efficient String Matching: An Aid to Bibliographic Search,” Communications of the ACM, Vol. 18, June 1975, pp. 333-340.

[7] B. H. Bloom, “Space/time trade-offs in hash coding with allowable errors,” Communications of the ACM, Vol. 13, no. 7, pp. 422-426, July 1970.

[8] S. Wu and U. Manber, “A fast algorithm for multi-pattern searching,” Technical Report, May 1994.

[9] Y. Miretskiy, A. Das, C. P. Wright, and E. Zadok, “Avfs: An On-Access Anti-Virus File System,” proceedings of the 13th USENIX Security Symposium, 2004.

[10] T. H. Lee, ”Generalized Aho-Corasick Algorithm for Signatures Based Anti-Virus Applications,” ICCCN, August 2007.

[11] D. Moore, C. Shannon, and J. Brown, “Code-Red: a case study on the spread and victims of an Internet worm,”in Proc. ACM/USENIX Internet Measurement Workshop, France, Nov. 2002.

[12] CAIDA. Dynamic graphs of the Nimda worm, http://www.caida.org/dynamic/analysis/security/nimda.

[13] D. Moore, V. Paxson, S. Savage, C. Shannon, S. Staniford, and N. Weaver, “Inside the Slammer worm,” IEEE Security and Privacy, 1(4): 33-39, July 2003.

[14] S. E. Schechter, J. Jung, and A. W. Berger, “Fast Detection of scanning worm infections,” 7th International Symposium on Recent Advances in Intrusion Detection (RAID), French Riviera, September 2004.

[15] D. Seeley, “A tour of the worm,” in Proc. of the Winter Usenix Conference, San Diego, CA, 1989.


[16] S. Dharmapurikar, P. Krishnamurthy, T. Sproull, and J. Lockwood, “Deep packet inspection using parallel bloom filters,” Symposium on High-Performance Interconnect (HotI), Stanford, CA, pp. 44-51, August 2003.

[17] Creating signatures for ClamAV, http://www.clamav.net.