字串比對在入侵偵測/防護系統上針對Aho-Corasick演算法的強化與實現

Abstract

因為現在網路的迅速成長，字串比對已經在防毒/防蟲當中被視為一種很重要的技術。目前相當有名的字串比對演算法：Aho-Corasick (AC)演算法，是一個能夠同時比對多重字串，並且在各種環境之下都能夠保證穩定的輸出表現的演算法。AC演算法的發展是依照字串比對的方式，然而病毒/蠕蟲本身是可以利用正規表示式來表示。這篇論文裡，我們會將AC演算法作強化，用一種系統化的方式來實現這套延伸強化應用的AC演算法，以達到可以針對一般字串以及正規表示式作為表示的字串比對，並且能準確指出字串的來源以及在文件中出現之後到結束的位置。

Because of its accuracy, pattern matching is considered an important technique in anti-virus/worm applications. Among some famous pattern matching algorithms, the Aho-Corasick (AC) can match multiple patterns simultaneously and guarantee deterministic performance under all circumstances. However, the AC algorithm was developed for strings while virus/worm signatures could be specified by simple regular expressions. In this paper, we enhance the AC algorithm to systematically construct a signature matching system which can indicate the ending position in a finite input string for the occurrence of virus/worm signatures that are specified by strings or simple regular expressions. The regular expressions studied are those adopted in ClamAV for signature specification.