A Novel Scalable and Storage-Efficient Architecture for High Speed Exact String Matching

다국어 초록 (Multilingual Abstract)

String matching is a fundamental element of an important category of modern packet processing applications which involve scanning the content flowing through a network for thousands of strings at the line rate. To keep pace with high network speeds, specialized hardware-based solutions are needed which should be efficient enough to maintain scalability in terms of speed and the number of strings. In this paper, a novel architecture based upon a recently proposed data structure called the Bloomier filter is proposed which can successfully support scalability. The Bloomier filter is a compact data structure for encoding arbitrary functions, and it supports approximate evaluation queries. By eliminating the Bloomier filter’s false positives in a space efficient way, a simple yet powerful exact string matching architecture is proposed that can handle several thousand strings at high rates and is amenable to on-chip realization. The proposed scheme is implemented in reconfigurable hardware and we compare it with existing solutions. The results show that the proposed approach achieves better performance compared to other existing architectures measured in terms of throughput per logic cells per character as a metric.

참고문헌 (Reference)

1 B. Chazelle, "The Bloomier Filter: An Efficient Data Structure for Static Support Lookup Tables" 30-39, 2004

2 B. Bloom, "Space/Time Trade-offs in Hash Coding with Allowable Errors" 13 (13): 422-426, 1970

3 "Snort-The Open Source Network Intrusion Detection System"

4 J. Moscola, "Reconfigurable Content-Based Router Using Hardware-Accelerated Language Parser" 13 (13): 28:1-28:25, 2008

5 Y.H. Cho, "Programmable Hardware for Deep Packet Filtering on a Large Signature Set" 2004

6 I. Sourdis, "Predecoded CAMs for Efficient and High-Speed NIDS Pattern Matching" 258-267, 2004

7 H. Jung, "Performance of FPGA Implementation of Bit-Split Architecture for Intrusion Detection Systems" 2006

8 M. Ramakrishna, "Performance in Practice of String Hashing Functions" 215-224, 1997

9 "Open Source Clam Antivirus"

10 M. Attig, "Implementation Results of Bloom Filters for String Matching" 322-323, 2004

11 G. Papadopoulos, "Hashing + Memory = Low Cost, Exact Pattern Matching" 39-44, 2005

12 S. Dharmapurikar, "Fast and Scalable Pattern Matching for Content Filtering" 183-192, 2005

13 P.K. Pearson, "Fast Hashing of Variable-Length Text Strings" 33 (33): 677-680, 1990

14 N. Tuck, "Deterministic Memory-Efficient String Matching Algorithms for Intrusion Detection" 2628-2639, 2004

15 S. Dharmapurikar, "Deep Packet Inspection Using Parallel Bloom Filters" 24 (24): 52-61, 2004

16 J. Hasan, "Chisel: A Storage-Efficient, Collision-Free Hash-Based Network Processing Architecture" 203-215, 2006

17 D. Charles, "Bloomier Filters: A Second Look" 259-270, 2008

18 Z.K. Baker, "Automatic Synthesis of Efficient Intrusion Detection Systems on FPGAs" 3 (3): 289-300, 2006

19 L. Tan, "Architectures for Bit-Split String Scanning in Intrusion Detection" 26 (26): 110-117, 2006

20 I. Sourdis, "A Reconfigurable Perfect-Hashing Scheme for Packet Inspection" 644-647, 2005