臺灣博碩士論文加值系統

網路入侵偵測系統(NIDS) 普遍地被使用來防護網路攻擊。NIDS 透過將封包內容與事先定義好的攻擊特徵進行比對，防止具有攻擊性的封包進入。由於NIDS 必須對每個封包進行比對，因此NIDS 的處理速度相當重要。文獻指出NIDS 的執行時間有31% 用在字串比對上，因此，如何提升字串比對的速度成為一個重要的議題。另一方面，由於軟體實作的NIDS 處理速度受到限制，考量到目前網路的成長速度，使用硬體實作的NIDS 是個較好的選擇。硬體方面，我們選擇在兼具彈性與速度的網路處理器上實作NIDS。然而，網路處理器因為快取記憶體較小，導致現有字串比對演算法所產生的資料結構無法完整儲存在快取記憶體中，造成比對時必須花費大量的時間在讀取外部記憶體。為了改善此問題，本論文提出利用具擴充性雙層查詢表的多字串比對演算法，透過建立足夠小的查詢表儲存在快取記憶體中進行初步的比對以減少存取外部記憶體的機率。因為讀取快取記憶體的延遲時間遠小於讀取外部記憶體的延遲時間，所以本論文所提出的演算法能降低NIDS 比對封包的時間。在效能評估部分，我們使用Snort 的規則進行模擬，並與設計應用在網路處理器的字串比對演算法HMA 進行比較，模擬結果顯示我們的演算法能減少19% 〜84% 的執行時間。

In order to protect networks from attacks, Network Intrusion Detection Systems (NIDS) have been widely deployed. These devices monitor packets in the network and scan packet payloads to detect malicious intrusions according to the predefined rules called patterns or signatures. It is time consuming for NIDS to check each packet to see if it contains any malicious patterns. Studies reveal that about 31% of the processing time in NIDS is spent on pattern matching. Since software-based NIDS suffer from speed limitation, hardware-based NIDS appear to a good choice for the future Internet. Network processors provide a scalable and flexible solution to implement NIDS. One distinct feature of network processors is that the size of on-chip memory is typical several 10 KB, which is too small to store the required data structures for the existing pattern matching algorithms. Thus, considerable amount of time has to be spent accessing external memory. In this thesis, we propose a pattern matching algorithm that uses scalable two-layer lookup tables to improve the performance in time. The key idea is to build a tiny and adjustable lookup table which can be fully stored in the on-chip memory of network processors, and reduce the probability of accessing the external memory. Since the latency of one on-chip memory access is far smaller than that of one external memory excess, the time required to process a packet payload can be greatly reduced. We use the well-known Snort rule sets to evaluate the proposed algorithm. Compared with the HMA, an efficient pattern matching algorithm designed for network processors, simulation results show that the proposed algorithm can reduce the processing time by 19% to 84%.

目錄
誌謝. . . . . . . . . . . . . . . . . . . . . . . . . .iv
中文摘要. . . . . . . . . . . . . . . . . . . . . . . . . .v
英文摘要. . . . . . . . . . . . . . . . . . . . . . . . . .vi
目錄. . . . . . . . . . . . . . . . . . . . . . . . . .vii
表目錄. . . . . . . . . . . . . . . . . . . . . . . . . .ix
圖目錄. . . . . . . . . . . . . . . . . . . . . . . . . .x
1 序論 . . . . . . . . . . . . . . . . . . . . . . . . . .1
1.1 相關背景. . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 研究動機. . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 研究目的. . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.4 論文架構. . . . . . . . . . . . . . . . . . . . . . . . . . 5
2 相關研究. . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.1 符號與問題之定義. . . . . . . . . . . . . . . . . . . . . 6
2.2 單字串比對演算法. . . . . . . . . . . . . . . . . . . . . 6
2.3 多字串比對演算法. . . . . . . . . . . . . . . . . . . . . 9
2.3.1 Aho-Corasick 演算法. . . . . . . . . . . . . . . 9
2.3.2 Bitmap Compression and Path Compression . . . . 13
2.3.3 Wu-Manber 演算法. . . . . . . . . . . . . . . . 15
2.3.4 階層式多字串比對演算法. . . . . . . . . . . . 17
3 利用具擴充性雙層查詢表的多字串比對演算法 . . . .21
3.1 資料結構之建立. . . . . . . . . . . . . . . . . . . . . . 21
3.2 比對流程. . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.3 STL 實例. . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.4 壓縮位元的選擇. . . . . . . . . . . . . . . . . . . . . . 27
3.5 壓縮所需之計算時間. . . . . . . . . . . . . . . . . . . 29
4 模擬實驗與結果分析 . . . . . . . . . . . . . . . . . . . . . . . . . .32
4.1 模擬環境與參數設定. . . . . . . . . . . . . . . . . . . 32
4.2 模擬流程. . . . . . . . . . . . . . . . . . . . . . . . . . 34
4.3 額外使用的記憶體空間. . . . . . . . . . . . . . . . . . 35
4.4 實驗結果與分析. . . . . . . . . . . . . . . . . . . . . . 35
5 結論與未來研究 . . . . . . . . . . . . . . . . . . . . . . . . . .44
參考文獻 . . . . . . . . . . . . . . . . . . . . . . . . . .45
表目錄
1.1 防火牆過濾規則表. . . . . . . . . . . . . . . . . . . . . 1
1.2 三種實作IDS 方式比較. . . . . . . . . . . . . . . . . . 4
2.1 “bed” 位移表. . . . . . . . . . . . . . . . . . . . . . . . 9
2.2 字串集合{he, she, his, hers} 之失誤轉移函式. . . . . . 11
2.3 字串集合{he, she, his, hers} 的輸出函式. . . . . . . . . 12
2.4 位移表範例. . . . . . . . . . . . . . . . . . . . . . . . . 16
2.5 雜湊表範例. . . . . . . . . . . . . . . . . . . . . . . . . 16
4.1 字串長度分布. . . . . . . . . . . . . . . . . . . . . . . 32
4.2 各種動作與其cycle 數. . . . . . . . . . . . . . . . . . . 33
4.3 各壓縮位元所需之額外記憶體空間. . . . . . . . . . . 35
4.4 各壓縮位元在不同字串總數時，VBV的平均命中機
率(%) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
4.5 STL 與HMA 在Model 3 的效能(cycles)，存取L2 記
憶體需(100/250) 個cycle . . . . . . . . . . . . . . . . . 42
4.6 STL 與HMA 在Model 4 的效能，存取L2 記憶體需
(100/250) 個cycle . . . . . . . . . . . . . . . . . . . . . 43
圖目錄
1.1 IDS 比對流程與運作方式. . . . . . . . . . . . . . . . . 2
2.1 比對窗移動距離過大. . . . . . . . . . . . . . . . . . . 7
2.2 安全距離說明圖例. . . . . . . . . . . . . . . . . . . . . 8
2.3 字串集合{he, she, his, hers} 的有限狀態機建構轉移
函式. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.4 字串集合{he, she, his, hers} 加入失誤轉移函式的有
限狀態機. . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.5 bitmap 範例. . . . . . . . . . . . . . . . . . . . . . . . . 14
2.6 WM 演算法比對實例. . . . . . . . . . . . . . . . . . . 17
2.7 HMA 資料結構. . . . . . . . . . . . . . . . . . . . . . . 19
3.1 加入CBV與VBV之H1 表. . . . . . . . . . . . . . . . . 23
3.2 建立代表碼集合、延伸代表碼集合與設定VBV之虛
擬碼. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3.3 比對流程之虛擬碼. . . . . . . . . . . . . . . . . . . . . 25
3.4 STL 資料結構實例. . . . . . . . . . . . . . . . . . . . . 26
3.5 不同CBV對VBV的影響. . . . . . . . . . . . . . . . . . 28
3.6 壓縮位元為4 的情況. . . . . . . . . . . . . . . . . . . 29
3.7 pex 指令運作方式. . . . . . . . . . . . . . . . . . . . . 30
3.8 使用pex 壓縮延伸代表碼與比對VBV之程式碼. . . . . 30
4.1 字串數量與相對應之平均代表碼數量. . . . . . . . . . 33
4.2 STL3 與HMA 在Model 1 的平均cycle 數. . . . . . . . 38
4.3 STL3 至STL7 在Model 1 的平均cycle 數. . . . . . . . 39
4.4 Model1 誤判率. . . . . . . . . . . . . . . . . . . . . . . 40
4.5 STL3 與HMA 在Model 2 的平均cycle 數. . . . . . . . 41

[1] M. Fisk and G. Varghese, “Applying Fast String Matching to Intrusion
Detection,” Technical Report In Preparation, Successor to
UCSD TR CS2001-0670, University of California, San Diego, 2002.
[2] Intel® IXP4XX product line of network processors, http://
www.intel.com/p/en_US/embedded/hwsw/hardware/ixp-4xx.
[3] Snort, www.snort.org.
[4] R.S. Boyer and J.S. Moore, “A fast string searching algorithm,”
Communications of the ACM, 20(10), pp. 762 - 772, 1977.
[5] A.V. Aho and M.J. Corasick, “Efficient string matching: an aid to
bibliographic search,” Communications of the ACM, 18(6), pp. 333-
340, 1975.
[6] N. Tuck, T. Sherwood, B. Calder, and G. Varghese, “Deterministic
memory-efficient string matching algorithms for intrusion detection,”
IEEE INFOCOM, pp. 2628-2639, 2004.
[7] S. Wu and U. Manber, “A fast algorithm for multi-pattern searching,”
Technical Report TR-94-17, Department of Computer Science,
University of Arizona, 1994.
[8] T.F. Sheu, N.F. Huang and H.P. Lee, “Hierarchical multi-pattern
matching algorithm for network content inspection,” Information
Sciences, 178(14), pp. 2880-2898, 2008.
[9] Y. Hilewitz and R.B. Lee, “Fast bit gather, bit scatter and bit permutation
instructions for commodity microprocessors,” Journal of
Signal Processing Systems, 53(1-2), pp. 145-169, 2008.
[10] R.N. Horspool, “Practical fast searching in strings,” Software Practice
and Experience, 10(6), pp. 501-506, 1980.
[11] B. Xu, X. Zhou, J. Li, “Recursive shift indexing: A fast multi-pattern
string matching algorithm,” International Conference on Applied
Cryptography and Network Security, 2006.
[12] R.T. Liu, N.F. Huang, C.H. Chen and C.N. Kao, “A fast string matching
algorithm for network processor-based intrusion detection system,”
ACM Transactions in Embedded Computing Systems, 3(3), pp.
614-633, 2004.
[13] C.J. Coit, S. Staniford and J. McAlerney, “Towards faster string
matching for intrusion detection or exceeding the speed of snort,”
DARPA Information Survivability Conference and Exposition, pp.
367-371, 2001.