深度封包檢測使用進階Aho-Corasick演算法

Abstract

因為字串比對的準確性，使其技術近年來被廣泛運用到網際網路應用上，其中，Snort為最具彈性與精確性的偵測軟體之一。Snort是一套開放原始碼的網路入侵預防與入侵檢測軟體，使用以特徵值(signature-based)和通訊協定的偵測方式，加上Snort規則語言(rules language)，搭配正規表示式(Perl compatible regular expression-PCRE)資料庫透過正規表示式字串比對，來達到流量封包辨識目的。其不僅單純檢測網路封包的表頭(header)，更依據封包內容(payload)做比對，檢查其是否與所設定的網路安全規範一致，這過程稱深度封包檢測(deep packet inspection)，效果會比傳統偵測方式僅檢測封包表頭更具安全性。有一著名正規表示式比對的演算法稱Aho-Corasick演算法，不僅可以同時比對多字串並保證在各情形下有合理的效能。我們提出一個方法延伸Aho-Corasick演算法，可以將Snort PCRE部分，依其特徵規則式有系統地建造特徵正規表示式比對圖，實驗數據顯示可得到合理的效能及較少的記憶體需求量。

Snort is an open source and free network intrusion prevention system (NIPS) and network intrusion detection system (NIDS) clever of performing packet logging and real-time traffic analysis on IP networks. Snort can also deal with deep packet inspection (DPI) which is an effective security measure that checks not only the packet headers but also the packet content. It uses Perl Compatible Regular Expression (PCRE) library for checking regular expressions which is replacing explicit string patterns as the pattern matching language of choice in many deep packet scanning applications. For regular expression, there is a famous pattern matching algorithm named Aho-Corasick (AC) which can match multiple patterns simultaneously and guarantee deterministic performance under all circumstances. We provide a method to extend the AC algorithm, and use this scheme to systematically construct a signature matching system which can indicate the ending position in a finite input string for the occurrence of Snort rules signatures that are specified by regular expressions. Use extended AC algorithm on Snort PCRE yields acceptable throughput performance and memory requirement.