實現於圖形處理器上的雙字元平行字串比對演算法

Abstract

Aho-Corasick 演算法已經被廣泛使用於網路入侵檢測系統（Network Intrusion Detection System，簡稱 NIDS），用來檢查網路封包裡數以千計數的惡意代碼片段。為了提高網路入侵檢測系統的性能，許多基於 Aho-Corasick 衍生出來的演算法使用圖形處理器（GPU）或特殊硬體來加速多字串比對，其中一種方法便是增加每週期處理的字元數來提升多字串比對的速度。然而，增加每週期處理的字元數將會遇到兩個主要問題，第一個問題是輸入對齊問題，第二個問題則是儲存狀態轉換表所需的記憶體空間大幅增加。這兩個問題導致多字元比對的方法變得不太可行。在本文中，我們提出了一種適合在圖形處理器上執行的雙字元平行字串比對演算法。而前述的兩個主要問題，本文提出了一個新形態的狀態機來解決輸入對齊問題，並用完美雜湊壓縮狀態轉換表以解決記憶體空間爆炸問題。實驗結果證明所提出的演算法無論在性能或記憶體空間需求方面均優於目前最先進的方法。Aho-Corasick algorithm has been widely used in network intrusion detection system to inspect network packets against thousands of attack patterns. To improve the performance of network intrusion detection systems, many variations of Aho-Corasick algorithm are proposed to accelerate multiple string matching on GPUs or dedicated hardware. One of the proposed variations is to increase the number of characters that are processed per cycle. However, increasing the number of characters processed per cycle will encounter two major problems. The first problem is the input alignment problem while the second problem is the large increase of memory required for storing the state transition table. The two problems cause the multi-character approach become less feasible. In this thesis, we propose a novel parallel dual-character string matching algorithm on graphical processing units. In order to solve the two major problems, the proposed algorithm presents a new state machine to solve the input alignment problem, and compresses the state transition table using perfect hashing to solve the memory explosion problem. The experimental results show that the proposed algorithm is superior to the state-of-the-art approaches in terms of performance and memory requirements.