對於網路入侵偵測系統之功能平行化樣本比對演算法

Abstract

在網路入侵偵測系統(NIDS)中，處理封包速度過慢的NIDS對於所保護的系統會有安全性上的漏洞。其中，樣本比對演算法佔著影響系統效能的關鍵性角色。在本篇論文中，我們試著分析目前NIDS中常見的樣本比對演算法，並且針對不同的演算法探討影響其效能的因素。我們發現，樣本群中最短樣本的長度對於Wu-Manber演算法有決定性的影響，當最短樣本的長度太短，會使其演算法效能過慢，另外同字首的樣本數量過多也會拖累比對的速度，而使得攻擊者可經由設計封包內容大量使用此字首拖累比對的速度，此稱為演算法攻擊(Algorithmic Attackes)。而對於Aho-Corasick演算法，長度短的樣本或是相同字首的樣本群卻可使比對速度快過一般的情況。因此，我們提出結合此兩種演算法的資料結構，並且透過功能平行化的方式將演算法對應到多核心系統中，可加速樣本比對的速度，並使得儲存空間在可接受的範圍。透過比較各個演算法的實驗，我們可得到使用功能平行化的比對演算法在雙處理器系統上比起原先的演算法最快可達2.2倍的效。並且對於演算法攻擊有一定的防禦力。

Pattern-matching algorithms are the core of network intrusion detection systems (NIDS). The performance of a good pattern-matching algorithm hence dominates the processing time required for deep packet inspections. In this research, we discuss the factors that can affect the performance of a pattern-matching algorithm. Such factors include prefixes of rules and lengths of the longest rules in a ruleset. Previous work to improve the performance of matching patterns (Wu-Manber's and Aho-Corasick's algorithms) adopt either a hash table or finite automaton to store the rulesets. None of these algorithms considers the parallelization when running on multicore systems. Herein, we propose a new pattern-matching algorithm for NIDS that can be easily adapted to multi-core systems. Our algorithm is composed of a search mechanism based on the function-parallelism approach and a composite data structure, combining the hash table and finite state machines. We conduct a series of experiments to show that our algorithm is 2.2 times faster than the Aho-Corasick algorithm and 1.21 times than Wu-Manber's in a dual-processor system.