使用FPGA 實現推測預先過濾器

Abstract

近年來網際網路在網路入侵偵測、防毒方面或是網路負載偵測對速度及準確 度上的需求越來越繁複，而在此方面經常使用的字串比對(pattern matching) 也同時在處理速度上要求越來越快。在此NTL 實驗室在字串比對理論中研發出一 種以預先過濾器的概念增加字串比對的速度。預先過濾器的方法是利用預先濾過 需求的關鍵字字串先去除不必要的資訊，讓後段硬體只需處理可能有用的資訊， 如此一來使處理器的負擔減輕，相形之下處理的資訊越少處理的速度相對性就會 變快。所以在此使用推測預先過濾器做為模型以硬體實現方式證明其實用上的可 行性及優越的處理速度。除此之外以此推測預先過濾器做為基礎，改良硬體處理 程序並且更進一步使用管線技術，利用同時處理多筆資訊的優點產生更快的資訊 處理速度。在文中並同時實現非推測的預先過濾器並以此做為速度的比較基礎點 來應證推測預先過濾器的實用性及硬體處理速度上的優越性。

Pattern matching, finding patterns to gain wealthy information, is one of the most applied techniques in information retrieval and malware detection. Based on the purpose of improving pattern matching outcome, we review several most popular theories of pattern matching process in current technology, including pre-filter, a quickly excluder to eliminate the nullity part of patterns, which is a common technique to lead to efficient pattern matching result . The Speculation pre-filter developed by NTL Lab is an efficient pre-filter that utilizes all previous query results by software programming. In the research, it is provided three different pre-filters implemented by Xilinx FPGA, containing Stateful pre-filter, Speculation pre-filter and Pipeline speculation pre-filter. Dual-port ram and pipeline are expected to accelerate pattern matching speed by multi-tasking function and enhance the performance of the hardware utility. Experimental result shows that the throughput in Speculation pre-filter is 1.5 times greater than Stateful pre-filter. Moreover, we discover that the throughput in pipe-line speculation pre-filter is 4 times faster than which in Speculation pre-filter, however, LUT in pipe-line speculation pre-filter only increases 2 times than which in Speculation pre-filter and no extra RAM spaces in pipe-line speculation pre-filter added. In the conclusion, pipe-line with pre-filters promises higher efficiency and performance in pattern matching.