以根索引及預先雜湊加速自動機式字串比對硬體： 設計，實作，與評估

Abstract

字串比對在內容過濾應用程式中扮演相當重要的角色，例如入侵偵測、防毒、擋廣告信和網站過濾，這不僅相當耗時並且佔用大量記憶體，純軟體演算法的實作效能亦無法滿足這類應用程式的高速需求，因此將封包內容交給字串比對硬體去處理是個必然的趨勢。這篇論文主要著重於一個節省記憶體的AC變形演算法，即 位圖AC（bitmap AC），並且使用了兩個平行硬體加速的技巧，一個是跟索引，另一個是預先雜湊，進一步實作在 Xilinx ML310 FPGA平台上。根索引能夠一次比對多個字元，而預先雜湊能夠避免耗時的位圖AC 計算。此外，這篇論文所提的方法對於內部記憶體或是外部記憶體的架構都是相當適合的，採用內部記憶體的架構可以提供高效能，而外部記憶體的架構則提供更高的應用範疇，這兩種實作方式都具有優越的處理能力。

String matching plays a central role in content networking applications, such as intrusion detection, anti-virus, anti-spam and Web filtering. As it is computation and memory intensive, a software implementation of string matching algorithms is insufficient to meet the high-speed requirement of these applications. Thus, offloading the packet content to dedicated hardware seems inevitable. This thesis focuses on the memory efficient version of AC, namely bitmap AC, and employs two parallel hardware acceleration techniques, root-indexing and pre-hashing, onto the FPGA-based Xilinx ML310 platform. The root-indexing can match multiple bytes in one single matching, and the pre-hashing can be used to avoid bitmap AC matching which is a cycle-consuming operation. Furthermore, the proposed string matching hardware approach is feasible for either internal or external memory architecture. The internal memory architecture provides high performance, and the external memory architecture provides high scalability of patterns. These two implementations both have high throughput for matching.