Memory-efficient distribution of regular expressions for fast deep packet inspection

ABSTRACT

Current trends in network security force network intrusion detection systems (NIDS) to scan network traffic at wirespeed beyond 10 Gbps against increasingly complex patterns, often specified using regular expressions. As a result, dedicated regular-expression accelerators have recently received considerable attention. The storage efficiency of the compiled patterns is a key factor in the overall performance and critically depends on the distribution of the patterns to a limited number of parallel pattern-matching engines. In this work, we first present a formal definition and complexity analysis of the pattern distribution problem and then introduce optimal and heuristic methods to solve it. Our experiments with five sets of regular expressions from both public and proprietary NIDS result in an up to 8.8x better storage efficiency than the state of the art. The average improvement is 2.3x.

REFERENCES

• 1: SNORT network intrusion detection system." http://www.snort.org/.
• 2: A. Aho and M. Corasick, "Efficient string matching: An aid to bibliographic search," Communications of the ACM, vol. 18, no. 6, pp. 333--340, 1975.
• 3: R. Sidhu and V. K. Prasanna, "Fast regular expression matching using FPGAs," in Proc. FCCM '01, pp. 227--238, IEEE, 2001.
• 4: S. Kumar, B. Chandrasekaran, J. Turner, and G. Varghese, "Curing regular expressions matching algorithms from insomnia, amnesia, and acalculia," in ANCS '07, pp. 155--164, ACM, 2007.
• 5: Z. K. Baker and V. K. Prasanna, "A methodology for synthesis of efficient intrusion detection systems on FPGAs," in Proc. FCCM '04, pp. 135--144, 2004.
• 6: I. Sourdis and D. Pnevmatikatos, "Pre-decoded CAMs for efficient and high-speed NIDS pattern matching," in Proc. FCCM '04, pp. 258--267, IEEE, 2004.
• 7: F. Yu, Z. Chen, Y. Diao, T. V. Lakshman, and R. H. Katz, "Fast and memory-efficient regular expression matching for deep packet inspection," in Proc. ANCS '06, pp. 93--102, ACM, 2006.
• 8: J. van Lunteren, J. Rohrer, K. Atasu, and C. Hagleitner, "Regular expression acceleration at multiple tens of Gb/s," in 1st Workshop on Accelerators for High-performance Architectures in conjunction with ICS, 2009.
• 9: J. van Lunteren, "High-performance pattern-matching for intrusion detection," in Proc. INFOCOM 2006, pp. 1--13, 2006.
• 10: K. Thompson, "Programming techniques: Regular expression search algorithm," Commun. ACM, vol. 11, no. 6, pp. 419--422, 1968.
• 11: S. Dharmapurikar, P. Krishnamurthy, T. S. Sproull, and J. W. Lockwood, "Deep packet inspection using parallel bloom filters," IEEE Micro, vol. 24, no. 1, pp. 52--61, 2004.
• 12: Y. H. Cho and W. H. Mangione-Smith, "A pattern matching coprocessor for network security," in Proc. DAC '05, pp. 234--239, ACM, 2005.
• 13: J. Moscola, J. Lockwood, R. P. Loui, and M. Pachos, "Implementation of a content-scanning module for an internet firewall," in Proc. FCCM '03, pp. 31--38, 2003.
• 14: C.-H. Lin, C.-T. Huang, C.-P. Jiang, and S.-C. Chang, "Optimization of pattern matching circuits for regular expression on FPGA," IEEE Trans. Very Large Scale Integr. Syst., vol. 15, no. 12, pp. 1303--1310, 2007.
• 15: I. Sourdis, J. Bispo, J. M. Cardoso, and S. Vassiliadis, "Regular expression matching in reconfigurable hardware," J. Signal Process. Syst., vol. 51, no. 1, pp. 99--121, 2008.
• 16: S. Kumar, S. Dharmapurikar, F. Yu, P. Crowley, and J. Turner, "Algorithms to accelerate multiple regular expressions matching for deep packet inspection," in Proc. SIGCOMM '06, pp. 339--350, ACM, 2006.
• 17: R. Smith, C. Estan, S. Jha, and S. Kong, "Deflating the big bang: fast and scalable deep packet inspection with extended finite automata," in Proc. SIGCOMM '08, pp. 207--218, ACM, 2008.
• 18: L. Tan and T. Sherwood, "A high throughput string matching architecture for intrusion detection and prevention," in Proc. ISCA '05, pp. 112--122, 2005.
• 19: R. M. Garey and D. S. Johnson, Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman and Co., 1979.
• 20: R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, Network Flows: Theory, Algorithms, and Applications. Prentice Hall, Englewood Cliffs, N.J., 1993.
• 21: S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, "Optimization by simulated annealing," Science, vol. 220, pp. 671--680, 1983.
• 22: Application layer packet classifier for Linux." http://l7-filter.sourceforge.net/.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Simulated annealing

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.3 Other Architecture Styles
          Subjects: Heterogeneous (hybrid) systems

General Terms:
Algorithms, Performance, Security

Keywords:
DFA, deep packet inspection, hardware acceleration, network intrusion detection, regular expression