應用於網路安全之正規表示式字樣比對

Abstract

特徵(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.