以Bloom filters硬體實作加速傳統次線性時間字串比對演算法: 設計、實作與評估

Abstract

目前針對封包內容作檢查的網路應用程式主要是用字串比對的方式來偵測封包中是否有入侵行為、病毒、廣告等惡意的傳輸資料。雖然目前針對字串比對演算法的研究已多不勝數，但用一般處理器跑軟體的運作方式上，由於其大計算量和頻繁的記憶體存取使得字串比對的處理速度存在一定的上限。所以在高速應用中已經走向使用硬體加速器來加速字串比對的運算。 本研究提出了一個應用Bloom filter的特性實作表格的查詢來達到次線性比對時間的硬體架構。此架構中利用二個機制來克服原本次線性時間演算法不適於硬體實作的因素，分別是：一、以平行詢問(parallel query)多個Bloom filter來取代原本演算法中需要存取在於外部記憶體的表格查詢動作。在次線性時間演算法中，普遍存在一個置於外部記憶體的大表格用以查詢判斷下一步掃描的動作；用Bloom filter的方式，不但可以模擬取代查詢表格的動作，更提供了比原本表格查詢更精確的資訊。二、設計一個非阻斷式(non-blocking) 的驗證介面，使得最差情況下的處理速度仍達到線性時間。次線性時間演算法在一般情形下的處理速度雖然是次線性時間，但是基於演算法原理，最糟情形下處理時間會比線性時間演算法長數倍。經由非阻斷式介面實作使得掃描與驗證的工作得以同時進行來達到最慢的處理速度會是線性時間演算法的處理速度。 本實作經過軟體模擬和Xilinx FPGA 合成模擬後驗證無誤，最高速度可達將近9.2Gbps；完全是病毒碼的驗證速度是600Mbps。

Many network security applications heavily rely on string matching to detect malicious intrusions, viruses, spam, and so on. A software-based implementation may not meet the performance requirement of high-speed applications due to intensive computation and frequent memory accesses. A hardware solution to take advantage of hardware parallelism is a promising trend to inspect the packet payload at line rate. In this work, we propose an innovative memory-based architecture using Bloom filters to realize a sub-linear time algorithm that can effectively process multiple characters simultaneously. The two key ideas to realize the sub-linear time algorithm in this architecture are (1) replacing the slow table lookup in the external memory with simultaneous queries to several Bloom filters and (2) designing a non-blocking verification interface to keep the worst-case performance in linear time. The proposed architecture is verified in both behavior simulation in C and timing simulation in HDL. The simulation result shows that the throughput is nearly 10 Gbps for Windows executable files and 600 Mbps in the worst case.