ㄧ個新穎的多樣式匹配演算法及其在SoC系統的實現

A Novel Multi-pattern Matching Algorithm and Implementation in SoC System

蔡文嚴(Wen-Yen Tsai)

指導教授 ： 黃能富

國立清華大學/電機資訊學院/資訊工程學系/碩士(2006年)

摘要

隨著網路技術的進步，現今的網路設備除了具備依據封包標頭欄位作為選徑及封包分類的技術之外，尚需可以檢測封包內容的能力，以提供更進ㄧ步的應用及加值服務。檢測封包內容的關鍵技術在於ㄧ個多樣式字串匹配演算法，其根據事先定義的樣式資料庫搜尋封包內容找出所有吻合的樣式值及其出現位置。在以 Gpbs 為吞吐量的網路環境之下，此演算法如何滴水不漏檢測每秒通過動輒幾百萬的封包數量將是ㄧ大挑戰。本論文提出一個多樣式字串匹配演算法並衡量其純軟體實作及整合到 SoC 系統的可行性與效能。此一演算法結合了用以縮小搜尋範圍的濾除技術並利用樣式字串間字首、字尾可能交互重疊的關係以加速整體匹配速度。在ㄧ般的網路資料流情況下，前端的濾除技術可以大幅過濾不需要匹配的封包因而提高系統的吞吐量；然而在封包中ㄧ但發現了任何匹配的樣式之後，預先分析的樣式字串字首、字尾重疊關係將可派上用場，其效率可分兩方面來討論：若目前匹配的樣式字串其字尾與其他樣式字串有重疊關係時，這些與目前匹配樣式有重疊關係的其他樣式將有可能是下一個可能匹配的候選者，此時則逐一檢視這些樣式；另ㄧ方面，若在檢視所有可能匹配樣式之後仍沒有找到任何配，則搜尋引擎可以停在目前正在掃描的封包內容位置，而不像其他演算法需要向後倒退(bask shift)以重新開始下ㄧ輪的搜尋動作。此演算法在記憶體使用量及匹配速度均有不錯的表現，當使用最新的 Snort 版本作為樣式資料庫時，此演算法的記憶體消耗量只有 500 KB；另ㄧ方面，其效能與在平均狀況(average-case)下公認最好的Wu-Manber 演算法相接近，並在最糟狀況下(worst-case)擁有更佳的效能。因此，以實作的觀點而言，整個演算法的資料結構可以放到高速的 cache 或是 on-chip memory 以達到單一的記憶體存取而提升匹配速度，而在最糟狀況下效能的改善則可使系統避免針對演算法弱點的攻擊(algorithmic attack)。

關鍵字

網路安全 ； 深層封包檢測 ； 入侵偵測系統 ； 多樣式字串比對

並列摘要

無資料

並列關鍵字

Network Security ； Deep Packet Inspection ； Intursion Detection System ； Multi-pattern string matching ； Bloom filter

參考文獻

[1] Burton H. Bloom, “Space time tradeoffs in hash coding with allowable errors,” Communications of the ACM, 13(7):422-426, 1970

[2] Chang, F.; Wu-chang Feng; Kang Li, “Approximate caches for packet classification.” INFOCOM2004, Volume 4, Page(s):2196 - 2207 vol.4, 2004

[3] S. Dharmapurikar, P. Krishnamurthy, TS Sproull, and JW Lockwood. “Deep Packet Inspection using. Parallel Bloom Filters.” IEEE Micro, 24(1):52–61, 2004

[4] L. Fan, P. Cao, J. Almeida, and A. Z. Broder. ”Summary cache: A scalable wide-area web cache sharing protocol.” IEEE/ACM Transactions on Networking, 8(3):281-293, June 2000.

[7] J. C. R. Tseng and W. P. Yang, “New Search Filter and Analysis,” Proc. of National Computer Symposium, Taiwan, R.O.C., Dec. 1991.