Open Access Open Access  Restricted Access Subscription or Fee Access

Ultra High Tech Multi-Pipelining String Matching for Deep Packet Inspection

N. Kannaiya Raja, Dr.K. Arulanandam, R. Prabhu

Abstract


Multi-pattern string matching remains a major performance bottleneck in network intrusion detection and anti-virus systems for high-speed deep packet inspection (DPI). Although Aho-Corasick deterministic finite automaton (AC- DFA) based solutions produce deterministic throughput and are widely used in today's DPI systems such as Snort and ClamAV, the high memory requirement of AC-DFA (due to the large number of state transitions in AC-DFA) inhibits efficient hardware implementation to achieve high performance.. Novel and scalable pipeline architecture for memory- efficient multi-pattern string matching is then presented. The architecture can be easily extended to support multi-character input per clock cycle by mapping a compressed AC-DFA onto multiple pipelines. In this paper the architecture to support enhanced multi-character input per clock cycle to achieve multiplicative throughput improvement. By using multi pipelining Now we can use the efficient architecture also available to support much larger pattern sets by using a limited number of external memory and also work done integrating proposed string matching architecture with DPI processing engine such packet header and other flags with regular expressing. Very fast regular expression matching is currently used here for applications searching for large pattern sets with increasingly faster data streams and minimize the through put by pipelining process and comparing him high level to reduce the state and minimize the throughput.

Keywords


Deep Packet Inspection, DFA, FPGA, Pipeline, String Matching.

Full Text:

PDF

References


Snort: Open source network IDS/IPS, http://www.snort.org.

Clam AntiVirus, http://www.clamav.net.

D. Pao, W. Lin, and B. Liu, “Pipelined architecture for multistring matching,” Computer Architecture Letters, vol. 7, no. 2,pp. 33–36, Feb. 2008.

Y.-H. E. Yang and V. K. Prasanna, “Memory-efficient pipelined architecture for large-scale string matching,” in FCCM 2009. 17th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, April 2009.

M. Alicherry, M. Muthuprasanna, and V. Kumar, “High speed pattern matching for network IDS/IPS,” in ICNP ’06: Proceedings of the 2006 IEEE International Conference on Network Protocols. IEEE Computer Society, 2006, pp. 187–196.

P.-C. Lin, Y.-D. Lin, T.-H. Lee, and Y.-C. Lai, “Using string matching for deep packet inspection,” Computer, vol. 41, no. 4, pp. 23–28, April 2008.

M. Crochemore and T. Lecroq, “Sequential multiple string matching,” in Encyclopedia of Algorithms, M. Y. Kao, Ed.Berlin: Springer, 2008, pp. 826–829.

T. Song, W. Zhang, D. Wang, and Y. Xue, “A memory efficient multiple pattern matching architecture for network security,” in INFOCOM 2008. The 27th Conference on Computer Communications. IEEE, April 2008, pp. 166–170.

D. P. Scarpazza, O. Villa, and F. Petrini, “High-speed string searching against large dictionaries on the cell/b.e. processor,” in Parallel and Distributed Processing, 2008. IPDPS 2008.IEEE International Symposium on, April 2008, pp. 1–12.

S. Antonatos, K. G. Anagnostakis, and E. P. Markatos, “Generating realistic workloads for network intrusion detection systems,” SIGSOFT Softw. Eng. Notes, vol. 29, no. 1, pp. 207–215, 2004.

Xilinx Virtex-6 FPGA Family,www.xilinx.com/products/virtex6/.

A. V. Aho and M. J. Corasick, “Efficient string matching: an aid to bibliographic search,” Commun. ACM, vol. 18, no. 6, pp. 333–340, 1975.

A. M. Baskurt, H. Benoit-Cattin, and C. Odet, “3-D medical image coding method using a separable 3-D wavelet transform,” in Proc. SPIEMed. Imaging: Image Display, vol. 2431. Apr. 1995, pp. 173–183.

V. Sanchez, P. Nasiopoulos, and R.Abugharbieh, “Lossless compressionof 4D medical images using H.264/AVC,” in Proc. IEEE ICASSP, vol. II.May 2006, pp. 1116–1119.

J. Wei, P. Saipetch, R. K. Panwar, D. Chen, and B. K. Ho, “Volumetric image compression by 3-D DWT,” in Proc. SPIE Med. Imaging: Image Display, vol. 2431. Apr. 1995, pp. 184–194.

L. Anqiang and L. Jing, “A novel scheme for robust video watermark in the 3-D DWT domain,” in Proc. ISDPE, Nov. 2007, pp. 514–516.

D. Moore, V. Paxson, S. Savage, C. Shannon, S. Staniford, and N.Weaver. “Inside the slammer worm,” in IEEE Security and Privacy, vol.1, no. 4, Jul-Aug 2003, pp. 33-39.

D. Moore, C. Shannon, and J. Brown, “Code-Red: A Case Study on The Spread and Victims of an Internet Worm,” Proc. of the 2nd ACM Internet Measurement Workshop, ACM Press, 2002, pp. 273–284.

M. Roesch, “Snort - Lightweight Intrusion Detection for Networks,” Proc. of the 13th USENIX conference on System administration, Nov.07-12, 1999, Seattle, Washington.

S. Antonatos, K. G. Anagnostakis and E. P. Markatos. “Generating realistic workloads for network intrusion detection systems,” SIGSOFTSoftw. Eng. Notes 29, 1 (Jan. 2004), 207-215.

A. V. Aho and M. J. Corasick, “ Efficient string matching: an aid to bibliographic search,” Commun. ACM 18, 6 Jun. 1975, 333-340.

D.E. Knuth, J.H. Morris and V.R. Pratt, “Fast pattern matching in Strings,” SIAM Journal on Computing, vol. 6, no. 2, pp. 323-350, 1977.


Refbacks

  • There are currently no refbacks.


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.