ECEB: Enhanced Constraint Repetition Block for Regular Expression Matching on FPGA

Le Hoang Long; Tran Trung Hieu; Vu Tan Tai; Nguyen Hoa Hung; Tran Ngoc Thinh; Dinh Duc Anh Vu

doi:10.37936/ecti-eec.201191.172272

Authors

Le Hoang Long Faculty of Computer Science and Engineering Hochiminh City University of Technology
Tran Trung Hieu Faculty of Computer Science and Engineering Hochiminh City University of Technology
Vu Tan Tai Faculty of Computer Science and Engineering Hochiminh City University of Technology
Nguyen Hoa Hung Faculty of Computer Science and Engineering Hochiminh City University of Technology
Tran Ngoc Thinh Faculty of Computer Science and Engineering Hochiminh City University of Technology
Dinh Duc Anh Vu Faculty of Computer Science and Engineering Hochiminh City University of Technology

DOI:

https://doi.org/10.37936/ecti-eec.201191.172272

Keywords:

Constraint Repetition, FPGA, NIDS, PCRE

Abstract

Recent Network Intrusion Detection Systems (NIDSs) utilize Perl Compatible Regular Expression to describe malicious patterns existing in the content payload of packets more and more e±ciently. Several techniques are introduced to optimize the performance or complete the system for full support all of PCRE features in hardware platform, but some issues have just been solved partially. Constraint Repetition is among important characteristics of PCRE but its e®ective hardware-based implementation solutions are still limited. This paper describes an Enhanced Constraint rEpetition Block (ECEB) for regular expression matching engine in FPGA. To support more PCRE features, we improve our implementation to handle flag 'm' modifier. We also implement the block memory (BRAM) based character matching which saves a lot of LUTs and effectively improves overall system's throughput compared to related techniques. A software tool-chain for auto-generating PCRE matching system is also introduced. We do experiments on low-cost XC2VP50 Xilinx Virtex II Pro chip with the rule set of SNORT, an open source NIDS, to evaluate our implementation. The results verify that our architecture can achieve throughput up to 1Gbps and save up to 90% hardware resources compared with the conventional architecture.

References

[1] SNORT Network Intrusion Detection System, www.snort.org

[2] M. Faezipour, and M. Nourani, "Constraint Repetition Inspection for Regular Expression on FPGA," 16th IEEE Symposium on High Performance Interconnects, pp. 111-118, 2008.

[3] I. Sourdis, S. Vassiliadis, J. Bispo, and J. M. P. Cardoso, "Regular Expression Matching in Recon?gurable Hardware," Journal of VLSI Signal Processing, pp. 1-23, 2007.

[4] R. Sidhu, and V. K. Prasanna, "Fast Regular Expression Matching Using FPGAs," Proceedings of the 9th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, pp. 227-238, 2001.

[5] C. R. Clark, and D. E. Schimmel, "Scalable Pattern Matching for High Speed Networks," Proceedings of the 12th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, pp. 249-257, 2004.

[6] A. Mitra, W. Najjar, and L. Bhuyan, "Compiling PCRE to FPGA for accelerating SNORT IDS," Proceedings of the 3rd ACM/IEEE Symposium on Architecture for networking and communications systems, pp. 127-136, 2007.

[7] Yi-Hua E. Yang, W. Jiang, and V. K. Prasanna, "Compact architecture for high-throughput regular expression matching on FPGA," Proceedings of the 4th ACM/IEEE Symposium on Architectures for Networking and Communications Systems, pp. 227-238, 2008.

[8] Le H. Long, Tran T. Hieu, Vu T. Tai, Nguyen H. Hung, Tran N. Thinh, and Dinh D. A. Vu, "Enhanced FPGA-based architecture for regular expression matching in NIDS," the 7th IEEE International Conference Electrical Engineering/Electronics, Computer, Telecommunications and Information Technology (ECTI-Con 2010), pp. 666 - 670, May 19-21, 2010.

[9] Robert W. Floyd and Je rey D. Ullman, "The Compilation of Regular Expressions into Integrated Circuits," J. ACM (New York, NY, USA), vol. 29, ACM, 1982, pp. 603-62.

[10] C.-H. Lin, C.-T. Huang, C.-P. Jiang and S.-C. Chang, "Optimization of Pattern Matching Circuits for Regular Expression on FPGA," in IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 15, no. 12, pp. 1303-1310, Dec. 2007.

[11] R.McNaughton, H. Yamada, "Regular Expressions and State Graphs for Automata," in IEEE Transactions on Electronic Computers, EC-9(1), pp. 39-47, 1960.