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

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

王廣煜(Kuang-Yu Wang)

指導教授 ： 李程輝

國立交通大學/電機學院/電信工程系所/碩士(2013年)

https://doi.org/10.6842/NCTU.2013.00459

摘要

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

關鍵字

Aho-Corasick演算法 ； 字串比對 ； 正規表示式 ； 動態過濾器

並列摘要

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.

並列關鍵字

Aho-Corasick algorithm ； pattern matching ； Regular expression ； Dynamic pre-filter

參考文獻

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

[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.

[6] B Bloom, “Space/time trade-offs in hash coding with allowable errors,” ACM, 13(7): 422–426, May 1970.

[7] A. Broder and M. Mitzenmacher, “Network applications of Bloom filters:a survey,” Internet Mathematics, vol. 1, no. 4, pp. 485–509.

[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.