{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:32:09Z","timestamp":1750307529840,"version":"3.41.0"},"reference-count":26,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2009,9,1]],"date-time":"2009-09-01T00:00:00Z","timestamp":1251763200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100006831","name":"U.S. Air Force","doi-asserted-by":"publisher","award":["26-0202-10"],"award-info":[{"award-number":["26-0202-10"]}],"id":[{"id":"10.13039\/100006831","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Reconfigurable Technol. Syst."],"published-print":{"date-parts":[[2009,9]]},"abstract":"<jats:p>With their expressiveness and simplicity, Perl compatible regular expressions (PCREs) have been adopted in mainstream signature based network intrusion detection systems (NIDSs) to describe known attack signatures, especially for polymorphic worms. NIDSs rely on an underlying string matching engine that simulates PCREs to inspect each network packet. PCRE is a superset of traditional regular expressions, and provides advanced features. However, this pattern matching becomes a performance bottleneck of software-based NIDSs, causing a big portion of their execution time to be dedicated to payload inspection, which results in an unacceptable packet drop rate. The penetration of these unexamined packets creates a security hole in such systems. Over the past decade, hardware acceleration for the pattern matching has been studied extensively and a marginal performance has been achieved. Among hardware approaches, FPGA-based acceleration engines provide great flexibility because new signatures can be compiled and programmed into their reconfigurable architecture. As more and more malicious signatures are discovered, it becomes harder to map a complete set of malicious signatures specified in PCREs to an FPGA chip. One of the space consuming components is the counter used in the constrained repetitions for PCREs. Therefore, we propose a space efficient SelectRAM counter for PCREs that use counting. The design takes advantage of the basic components contained in a configurable logic block, and thus optimizes space usage. A set of basic PCRE blocks has been built in hardware to implement PCREs. Experimental results show that the proposed scheme outperforms existing designs by at least fivefold.<\/jats:p>","DOI":"10.1145\/1575779.1575783","type":"journal-article","created":{"date-parts":[[2009,10,6]],"date-time":"2009-10-06T18:18:59Z","timestamp":1254853139000},"page":"1-18","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Space Optimization on Counters for FPGA-Based Perl Compatible Regular Expressions"],"prefix":"10.1145","volume":"2","author":[{"given":"Chia-Tien Dan","family":"Lo","sequence":"first","affiliation":[{"name":"Southern Polytechnic State University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yi-Gang","family":"Tai","sequence":"additional","affiliation":[{"name":"University of Texas at San Antonio"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2009,9]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Aho A. Sethi R. and Ullman J. 1988. Compilers - Principles Techniques and Tools Addison-Wesley 117--123.   Aho A. Sethi R. and Ullman J. 1988. Compilers - Principles Techniques and Tools Addison-Wesley 117--123."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/360825.360855"},{"volume-title":"Proceedings of the 16th International Conference on Field Programmable Logic and Applications. 1--8.","author":"Baker Z.","key":"e_1_2_1_3_1","unstructured":"Baker , Z. , Prasanna , V. , and Jung , H . -J. 2006. Regular expression software deceleration for intrusion detection systems . In Proceedings of the 16th International Conference on Field Programmable Logic and Applications. 1--8. Baker, Z., Prasanna, V., and Jung, H.-J. 2006. Regular expression software deceleration for intrusion detection systems. In Proceedings of the 16th International Conference on Field Programmable Logic and Applications. 1--8."},{"volume-title":"Proceedings of the 16th International Conference on Field Programmable Logic and Applications (FPL\u201906)","author":"Bispo J.","key":"e_1_2_1_4_1","unstructured":"Bispo , J. , Sourdis , I. , Cardoso , J. , and Vassiliadis , S . 2006. Regular expression matching for reconfigurable packet inspection . In Proceedings of the 16th International Conference on Field Programmable Logic and Applications (FPL\u201906) . 119--126. Bispo, J., Sourdis, I., Cardoso, J., and Vassiliadis, S. 2006. Regular expression matching for reconfigurable packet inspection. In Proceedings of the 16th International Conference on Field Programmable Logic and Applications (FPL\u201906). 119--126."},{"key":"e_1_2_1_5_1","volume-title":"Reconfigurable Computing: Architectures, Tools, and Applicatins. 179--190.","author":"Bispo J.","year":"2007","unstructured":"Bispo , J. , Sourdis , I. , Cardoso , J. , and Vassiliadis , S . 2007 . Synthesis of regular expressions targeting FPGAs: current status and open issues. In Proceedings of the Reconfigurable Computing: Architectures, Tools, and Applicatins. 179--190. Bispo, J., Sourdis, I., Cardoso, J., and Vassiliadis, S. 2007. Synthesis of regular expressions targeting FPGAs: current status and open issues. In Proceedings of the Reconfigurable Computing: Architectures, Tools, and Applicatins. 179--190."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/359842.359859"},{"key":"e_1_2_1_7_1","unstructured":"Bro. 2008. Intrusion detection system. http:\/\/www.bro-ids.org.  Bro. 2008. Intrusion detection system. http:\/\/www.bro-ids.org."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISCA.2006.7"},{"volume-title":"Proceedings of the 12th International Conference on Field Programmable Logic and Applications (FPL\u201902)","author":"Cho Y. H.","key":"e_1_2_1_9_1","unstructured":"Cho , Y. H. , Navab , S. , and Mangione-Smith , W. H . 2002. Specialized hardware for deep network packet filtering . In Proceedings of the 12th International Conference on Field Programmable Logic and Applications (FPL\u201902) . Cho, Y. H., Navab, S., and Mangione-Smith, W. H. 2002. Specialized hardware for deep network packet filtering. In Proceedings of the 12th International Conference on Field Programmable Logic and Applications (FPL\u201902)."},{"volume-title":"Proceedings of the IEEE Symposium on Field-Programmable Custom Computing Machines.","author":"Clark C.","key":"e_1_2_1_10_1","unstructured":"Clark , C. and Schimmel , D . 2004. Scalable parallel pattern-matching on high-speed networks . In Proceedings of the IEEE Symposium on Field-Programmable Custom Computing Machines. Clark, C. and Schimmel, D. 2004. Scalable parallel pattern-matching on high-speed networks. In Proceedings of the IEEE Symposium on Field-Programmable Custom Computing Machines."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/322326.322327"},{"volume-title":"Proceedings of the 12th International Conference on Field Programmable Logic and Applications (FPL\u201902)","author":"Gokhale M.","key":"e_1_2_1_12_1","unstructured":"Gokhale , M. , Dubois , D. , Dubois , A. , Boorman , M. , Poole , S. , and Hogsett , V . 2002. Granidt: Towards gigabit rate network intrusion detection technology . In Proceedings of the 12th International Conference on Field Programmable Logic and Applications (FPL\u201902) . Gokhale, M., Dubois, D., Dubois, A., Boorman, M., Poole, S., and Hogsett, V. 2002. Granidt: Towards gigabit rate network intrusion detection technology. In Proceedings of the 12th International Conference on Field Programmable Logic and Applications (FPL\u201902)."},{"volume-title":"Proceedings of the 10th Annual IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM\u201902)","author":"Hutchings B. L.","key":"e_1_2_1_13_1","unstructured":"Hutchings , B. L. , Franklin , R. , and Carver , D . 2002. Assisting network intrusion detection with reconfigurable hardware . In Proceedings of the 10th Annual IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM\u201902) . 111--120. Hutchings, B. L., Franklin, R., and Carver, D. 2002. Assisting network intrusion detection with reconfigurable hardware. In Proceedings of the 10th Annual IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM\u201902). 111--120."},{"volume-title":"Proceedings of the Conference on Design, Automation, and Test in Europe (DATE\u201906)","author":"Lin C.-H.","key":"e_1_2_1_14_1","unstructured":"Lin , C.-H. , Huang , C.-T. , Jiang , C.-P. , and Chang , S . -C. 2006. Optimization of regular expression pattern matching circuits on FPGA . In Proceedings of the Conference on Design, Automation, and Test in Europe (DATE\u201906) . 12--17. Lin, C.-H., Huang, C.-T., Jiang, C.-P., and Chang, S.-C. 2006. Optimization of regular expression pattern matching circuits on FPGA. In Proceedings of the Conference on Design, Automation, and Test in Europe (DATE\u201906). 12--17."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1363686.1364044"},{"volume-title":"Proceedings of the IEEE International Conference on Field Programmable Technology.","author":"Lo C.-T. D.","key":"e_1_2_1_16_1","unstructured":"Lo , C.-T. D. , Tai , Y.-G. , Psarris , K. , and Hwang , W . -J. 2006. Super fast hardware string matching . In Proceedings of the IEEE International Conference on Field Programmable Technology. Lo, C.-T. D., Tai, Y.-G., Psarris, K., and Hwang, W.-J. 2006. Super fast hardware string matching. In Proceedings of the IEEE International Conference on Field Programmable Technology."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/TEC.1960.5221603"},{"volume-title":"Proceedings of the IEEE Workshop on FPGAs for Custom Computing Machines. 31--38","author":"Moscola J.","key":"e_1_2_1_18_1","unstructured":"Moscola , J. , Lockwood , J. , Loui , R. , and Pachos , M . 2003. Implementation of a content-scanning module for an internet firwall . In Proceedings of the IEEE Workshop on FPGAs for Custom Computing Machines. 31--38 . Moscola, J., Lockwood, J., Loui, R., and Pachos, M. 2003. Implementation of a content-scanning module for an internet firwall. In Proceedings of the IEEE Workshop on FPGAs for Custom Computing Machines. 31--38."},{"key":"e_1_2_1_19_1","unstructured":"PCRE. 2008. Perl compatible regular expressions. http:\/\/www.pcre.org.  PCRE. 2008. Perl compatible regular expressions. http:\/\/www.pcre.org."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/1058426.1058885"},{"key":"e_1_2_1_21_1","unstructured":"Snort. 2008. Snort intrusion detection system. http:\/\/snort.org.  Snort. 2008. Snort intrusion detection system. http:\/\/snort.org."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVLSI.2007.912036"},{"volume-title":"Proceedings of the IEEE Symposium on Field-Programmable Custom Computing Machines. 258--267","author":"Sourdis I.","key":"e_1_2_1_23_1","unstructured":"Sourdis , I. and Pnevmatikatos , D. N . 2004. Predecoded cams for efficient and high-speed NIDs pattern matching . In Proceedings of the IEEE Symposium on Field-Programmable Custom Computing Machines. 258--267 . Sourdis, I. and Pnevmatikatos, D. N. 2004. Predecoded cams for efficient and high-speed NIDs pattern matching. In Proceedings of the IEEE Symposium on Field-Programmable Custom Computing Machines. 258--267."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/FPT.2004.1393247"},{"key":"e_1_2_1_25_1","unstructured":"Xilinx I. 2008. Xilkernel documents. http:\/\/www.xilinx.com\/ise\/embedded\/edk91i_docs\/xilkernel_v3_00_a.pdf.  Xilinx I. 2008. Xilkernel documents. http:\/\/www.xilinx.com\/ise\/embedded\/edk91i_docs\/xilkernel_v3_00_a.pdf."},{"volume-title":"Proceedings of the Reconfigurable Computing: Architectures and Applications. 389--400","author":"Yusuf S.","key":"e_1_2_1_26_1","unstructured":"Yusuf , S. , Luk , W. , Szeto , M. K. N. , and Osborne , W . 2006. Unite: Uniform hardware-based network intrusion detection engine . In Proceedings of the Reconfigurable Computing: Architectures and Applications. 389--400 . Yusuf, S., Luk, W., Szeto, M. K. N., and Osborne, W. 2006. Unite: Uniform hardware-based network intrusion detection engine. In Proceedings of the Reconfigurable Computing: Architectures and Applications. 389--400."}],"container-title":["ACM Transactions on Reconfigurable Technology and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1575779.1575783","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1575779.1575783","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T12:23:08Z","timestamp":1750249388000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1575779.1575783"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,9]]},"references-count":26,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2009,9]]}},"alternative-id":["10.1145\/1575779.1575783"],"URL":"https:\/\/doi.org\/10.1145\/1575779.1575783","relation":{},"ISSN":["1936-7406","1936-7414"],"issn-type":[{"type":"print","value":"1936-7406"},{"type":"electronic","value":"1936-7414"}],"subject":[],"published":{"date-parts":[[2009,9]]},"assertion":[{"value":"2008-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-09-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}