動態過濾器應用在偵測病毒特徵碼防毒軟體

Dynamic Pre-filter Designs for Signature Based Anti-Virus/Worm Applications

10.6842/NCTU.2013.00459

王廣煜

Aho-Corasick演算法 ； 字串比對 ； 正規表示式 ； 動態過濾器 ； Aho-Corasick algorithm ； pattern matching ； Regular expression ； Dynamic pre-filter

交通大學電信工程系所學位論文

2013年

碩士

李程輝

英文

字串比對在病毒偵測的應用上是一門很重要的技術，因為字串比對的精確度比異常行為偵測來的高。目前有許多有名的字串比對演算法已經被提出，其中Aho-Corasick (AC) 是一種可以同時比對多隻病毒的演算法。然而，AC演算法偵測的對象是以普通字串表示的病毒，無法偵測以正規表示式表示的病毒。 在我們提出的字串比對系統中，主要是偵測正規表示式的病毒特徵碼，包含動態過濾器與驗證模組兩部分。動態過濾器的主要目的是快速移動到檔案可疑的病毒位置，它透過將相對應的字串資訊逐步加入系統中，可以避免不必要的字串資訊加入，增強效能。驗證模組是驗證動態過濾器找出來的可疑位置是否真的是病毒特徵碼的某一段，我們事先將病毒特偵碼分段建造狀態機，驗證模組只需要針對可能的狀態機進行追蹤，減少時間上的浪費。

Pattern matching is an important technology in anti-virus/worm applications and is more accuracy than behavior anomaly. Many famous pattern matching algorithms have been presented in the past, and Aho-Corasick (AC) is one of the famous algorithms that can match multiple patterns simultaneously. However, the AC algorithm was developed for plain strings while virus/worm signatures could be specified by simple regular expressions. Our proposed signature matching system which consists of a dynamic pre-filter and a verification module is designed for simple regular expressions detection. The main purpose of dynamic pre-filter is to quickly find the starting position of suspicious substrings which may result in match of some signatures. It can avoid unnecessary information by adding a few fragments of signature to enhance the performance. The verification module is used to verify whether there is any virus at suspicious position found by dynamic pre-filter. We built the state machine in advanced according to the fragments of signatures. The verification module only traces the possible state machine to save the time.

1. [3] R. S. Boyer and J. S. Moore, “A fast string searching algorithm,” Communications of the ACM, Vol. 20, October 1977, pp. 762-772.
   連結：
2. [4] 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.
   連結：
3. [6] B Bloom, “Space/time trade-offs in hash coding with allowable errors,” ACM, 13(7): 422–426, May 1970.
   連結：
4. [7] A. Broder and M. Mitzenmacher, “Network applications of Bloom filters:a survey,” Internet Mathematics, vol. 1, no. 4, pp. 485–509.
   連結：
5. [8] S. Dharmapurikar, P. Krishnamurthy, T. Sproull, and J. Lockwood,“Deep packet inspection using parallel Bloom filters,” IEEE Micro, vol. 24, no. 1, pp. 52–61, Jan./Feb. 2004.
   連結：
6. [11] N. S. Artan and H. J. Chao, “Multi-packet signature detection using prefix Bloom filters,” IEEE GLOBECOM, vol. 3, pp. 1811–1816, 2005.
   連結：
7. [12] N. S. Artan, K. Sinkar, J. Patel, and H. J. Chao, “Aggregated Bloom filters for intrusion detection and prevention hardware,” IEEE GLOBECOM, pp. 349–354, Nov. 2007.
   連結：
8. [13] T. H. Lee and N. L. Huang, “A Pattern Matching Scheme with High Throughput Performance and Low Memory Requirement,” IEEE/ACM Transactions on Networking.
   連結：
9. [14] Clam anti virus signature database, www.clamav.net.
   連結：
10. [15] T. H. Lee, “Generalized Aho-Corasick algorithm for signature based anti-virus applications,” IEEE ICCCN 2007.
    連結：
11. [16] R. Smith, C. Estan, and S. Jha, “XFA: Fast signature matching with extended automata,” In IEEE Symposium on Security and Privacy, May 2008.
    連結：
12. [1] 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.
13. [2] D. E. Knuth, J. H. Morris, and V. R. Pratt, “Fast pattern matching in strings,” TR CS-74-440, Stanford University, Stanford, California, 1974.
14. [5] S. Wu and U. Manber, “A fast algorithm for multi-pattern searching,” TR-94-17, 1994.
15. [9] M. Attig, S. Dharmapurikar, and J. Lockwood, “Implementation results of Bloom filters for string matching,” Field-Programmable Custom Computing Machines, pp. 322–323, Apr. 2004.
16. [10] S. Dharmapurikar, P. Krishnamurthy, and D. E. Taylor, “Longest prefix matching using Bloom filters,” IEEE/ACM Transactions on Networking, vol. 14, pp. 397–409, Apr. 2006.
17. [17] Snort website http://www.snort.org/.
18. [18] M. Roesch, “Snort – lightweight intrusion detection for networks,” Proceedings of LISA’99: 13th Systems Administration Conference, pp.s229–238, Nov. 1999.