ETRI Journal

Electronics and Telecommunications Research Institute (한국전자통신연구원)
권호 표지
DOI QR코드

DOI QR Code

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

  • Peiravi, Ali (Department of Electrical Engineering, Faculty of Engineering, Ferdowsi University of Mashhad) ;
  • Rahimzadeh, Mohammad Javad (Department of Electrical Engineering, Faculty of Engineering, Ferdowsi University of Mashhad)
  • Received : 2008.06.20
  • Accepted : 2009.07.28
  • Published : 2009.10.31
Download PDF
⟨ Previous Next ⟩

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.

Keywords

References

  1. Snort-The Open Source Network Intrusion Detection System, http://www.snort.org
  2. Open Source Clam Antivirus. http://www.clamav.net
  3. B. Chazelle et al., “The Bloomier Filter: An Efficient Data Structure for Static Support Lookup Tables,” Proc. 15th Ann. ACM-SIAM Symp. Discrete Algorithms, 2004, pp. 30-39.
  4. B. Bloom, “Space/Time Trade-offs in Hash Coding with Allowable Errors,” Communications of the ACM, vol. 13, no. 7, 1970, pp. 422-426. https://doi.org/10.1145/362686.362692
  5. N. Tuck et al., “Deterministic Memory-Efficient String Matching Algorithms for Intrusion Detection,” IEEE INFOCOM, vol. 4, 2004, pp. 2628-2639.
  6. S. Dharmapurikar et al., “Deep Packet Inspection Using Parallel Bloom Filters,” IEEE Micro, vol. 24, no. 1, 2004, pp. 52-61. https://doi.org/10.1109/MM.2004.1268997
  7. S. Dharmapurikar and J. Lockwood, “Fast and Scalable Pattern Matching for Content Filtering,” Proc. Symp. Architecture for Networking and Communications Systems (ANCS), 2005, pp. 183-192.
  8. L. Tan and T. Sherwood, “Architectures for Bit-Split String Scanning in Intrusion Detection,” IEEE Micro, vol. 26, no. 1, 2006, pp. 110-117. https://doi.org/10.1109/MM.2006.5
  9. H. Jung, Z.K. Baker, and V.K. Prasanna, “Performance of FPGA Implementation of Bit-Split Architecture for Intrusion Detection Systems,” 20th Int. Parallel and Distributed Processing Symp. (IPDPS), 2006.
  10. I. Sourdis et al., “A Reconfigurable Perfect-Hashing Scheme for Packet Inspection,” Proc. 15th Int. Conf. Field Programmable Logic and Applications (FPL), 2005, pp. 644-647.
  11. G. Papadopoulos and D. Pnevmatikatos, “Hashing + Memory = Low Cost, Exact Pattern Matching,” Proc. 15th Int. Conf. Field Programmable Logic and Applications (FPL), 2005, pp. 39-44.
  12. J. Hasan et al., “Chisel: A Storage-Efficient, Collision-Free Hash-Based Network Processing Architecture,” Proc. 33rd Ann. Int. Symp. Computer Architecture (ISCA), IEEE CS Press, 2006, pp. 203-215.
  13. M. Ramakrishna and J. Zobel, “Performance in Practice of String Hashing Functions,” Proc. 5th Int. Conf. Database Systems for Advanced Applications, 1997, pp. 215-224.
  14. P.K. Pearson, “Fast Hashing of Variable-Length Text Strings,” Communications of the ACM, vol. 33, no. 6, 1990, pp. 677-680. https://doi.org/10.1145/78973.78978
  15. M. Attig, S. Dharmapurikar, and J. Lockwood, “Implementation Results of Bloom Filters for String Matching,” IEEE Symp. Field-Programmable Custom Computing Machines, 2004, pp. 322-323.
  16. Y.H. Cho and W.H. Mangione-Smith, “Programmable Hardware for Deep Packet Filtering on a Large Signature Set,” First Watson Conf. Interaction between Architecture, Circuits and Compilers, 2004.
  17. I. Sourdis and D. Pnevmatikatos, “Predecoded CAMs for Efficient and High-Speed NIDS Pattern Matching,” Proc. 12th Ann. IEEE Symp. Field-Programmable Custom Computing Machines (FCCM), IEEE CS Press, 2004, pp. 258-267.
  18. Z.K. Baker and V.K. Prasanna, “Automatic Synthesis of Efficient Intrusion Detection Systems on FPGAs,” IEEE Trans. Dependable and Secure Computing, vol. 3, no. 4, 2006, pp. 289-300. https://doi.org/10.1109/TDSC.2006.44
  19. J. Moscola, J.W. Lockwood, and Y.H. Cho, “Reconfigurable Content-Based Router Using Hardware-Accelerated Language Parser,” ACM Trans. Design Automation of Electronic Systems, vol. 13, no. 2, article 28, 2008, pp. 28:1-28:25.
  20. D. Charles and K. Chellapilla, “Bloomier Filters: A Second Look,” Lecture Notes in Computer Science, Proceedings 16th Annual European Symp. Algorithms, vol. 5193, 2008, pp. 259-270.

Cited by

  1. A Hardware-Based String Matching Using State Transition Compression for Deep Packet Inspection vol.35, pp.1, 2009, https://doi.org/10.4218/etrij.13.0212.0165