{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,17]],"date-time":"2026-08-17T23:17:37Z","timestamp":1787008657191,"version":"build-2736575974"},"reference-count":60,"publisher":"Oxford University Press (OUP)","issue":"12","license":[{"start":{"date-parts":[[2022,10,23]],"date-time":"2022-10-23T00:00:00Z","timestamp":1666483200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"funder":[{"DOI":"10.13039\/501100012166","name":"National Key Research and Development Program of China","doi-asserted-by":"publisher","award":["2018YFB0204301"],"award-info":[{"award-number":["2018YFB0204301"]}],"id":[{"id":"10.13039\/501100012166","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023,12,14]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>Regular Expression Matching (REM) is the core of Deep Packet Inspection (DPI), which is important for various network security applications. The burgeoning Software Defined Network and Network Function Virtualization technologies make the network evolve more dynamic, which brings serious challenges for DPI engines to achieve high matching performance with fast rule-set update capability. To meet these challenges, this paper proposes a heterogeneous Field Programmable Gate Array (FPGA)-Central Processing Unit (CPU) architecture to accelerate Deterministic Finite Automaton (DFA)-based REM with high preprocessing performance. Firstly, a novel regex decomposition technique is proposed to solve the DFA state explosion problem, which splits each regex into one prefix and several postfixes. Secondly, heterogeneous architecture is presented to collaboratively handle regex matching, in which prefixes are matched in parallel in an FPGA and postfixes are matched in a CPU. To further improve the matching performance, several well-designed DFA compression techniques and regex decomposition optimizations are proposed. Our design has been implemented in a DPI prototype employing a medium-end FPGA. Extensive experiments are conducted to evaluate the performance. Results reveal that our proposed architecture achieves 6.33 Gbps matching throughput on the Snort rule-set (v3.0), which is close to state-of-the-art FPGA NFA-based schemes. However, the rule-set preprocessing time is significantly reduced to &amp;lt;7 minutes, compared with up to several hours of FPGA NFA-based countermeasures.<\/jats:p>","DOI":"10.1093\/comjnl\/bxac138","type":"journal-article","created":{"date-parts":[[2022,9,15]],"date-time":"2022-09-15T17:31:17Z","timestamp":1663263077000},"page":"2928-2947","source":"Crossref","is-referenced-by-count":6,"title":["FPGA-CPU Architecture Accelerated Regular Expression Matching With Fast Preprocessing"],"prefix":"10.1093","volume":"66","author":[{"given":"Jincheng","family":"Zhong","sequence":"first","affiliation":[{"name":"School of Computer, National University of Defense Technology , Changsha Deya Road 109, Hunan 410073, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shuhui","family":"Chen","sequence":"additional","affiliation":[{"name":"School of Computer, National University of Defense Technology , Changsha Deya Road 109, Hunan 410073, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Biao","family":"Han","sequence":"additional","affiliation":[{"name":"School of Computer, National University of Defense Technology , Changsha Deya Road 109, Hunan 410073, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2022,10,23]]},"reference":[{"key":"2023121811453270400_ref1","author":"Marty Roesch."},{"key":"2023121811453270400_ref2","author":"Zeek community."},{"key":"2023121811453270400_ref3","doi-asserted-by":"crossref","first-page":"2991","DOI":"10.1109\/COMST.2016.2566669","article-title":"A survey on regular expression matching for deep packet inspection: Applications, algorithms, and hardware platforms","volume":"18","author":"Xu","year":"2016","journal-title":"IEEE Comm. Surv. Tutorials"},{"key":"2023121811453270400_ref4","first-page":"631","volume-title":"16th USENIX Symposium on Networked Systems Design and Implementation (NSDI 19)","author":"Wang","year":"2019"},{"key":"2023121811453270400_ref5","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3314576","article-title":"Automata processing in reconfigurable architectures: In-the-cloud deployment, cross-platform evaluation, and fast symbol-only reconfiguration","volume":"12","author":"Bo","year":"2019","journal-title":"ACM Trans. Reconfig. Technol. Syst. (TRETS)"},{"key":"2023121811453270400_ref6","first-page":"1","volume-title":"2017 27th International Conference on Field Programmable Logic and Applications (FPL)","author":"Xie","year":"2017"},{"key":"2023121811453270400_ref7","doi-asserted-by":"crossref","first-page":"1013","DOI":"10.1109\/TC.2011.129","article-title":"High-performance and compact architecture for regular expression matching on fpga","volume":"61","author":"Yang","year":"2011","journal-title":"IEEE Trans. Comput."},{"key":"2023121811453270400_ref8","first-page":"177","article-title":"High speed regular expression matching engine with fast pre-processing","volume":"16","author":"Zhe","year":"2019","journal-title":"China Commun."},{"key":"2023121811453270400_ref9","author":"cisco"},{"key":"2023121811453270400_ref10","volume-title":"Society of Photo-Optical Instrumentation Engineers (SPIE) Conference Series","author":"Bace","year":"2001"},{"key":"2023121811453270400_ref11","doi-asserted-by":"crossref","first-page":"880","DOI":"10.1016\/j.csi.2013.12.001","article-title":"A regular expression matching engine with hybrid memories","volume":"36","author":"Chen","year":"2014","journal-title":"Comput. Standards Interfaces"},{"key":"2023121811453270400_ref12","volume-title":"2018 IEEE Symposium on Computers and Communications (ISCC)","author":"Yang","year":"2018"},{"key":"2023121811453270400_ref13","doi-asserted-by":"crossref","first-page":"1360","DOI":"10.1109\/ICCC47050.2019.9064254","volume-title":"2019 IEEE 5th International Conference on Computer and Communications (ICCC)","author":"Zhong","year":"2019"},{"key":"2023121811453270400_ref14","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1145\/3234664.3234669","volume-title":"Proceedings of the 2018 2nd High Performance Computing and Cluster Technologies Conference","author":"Haghighat","year":"2018"},{"key":"2023121811453270400_ref15","doi-asserted-by":"crossref","first-page":"2179","DOI":"10.1109\/TNET.2019.2941920","article-title":"A de-compositional approach to regular expression matching for network security","volume":"27","author":"Liu","year":"2019","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"2023121811453270400_ref16","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1145\/360825.360855","article-title":"Efficient string matching: an aid to bibliographic search","volume":"18","author":"Aho","year":"1975","journal-title":"Commun. ACM"},{"key":"2023121811453270400_ref17","first-page":"551","volume-title":"13th USENIX Symposium on Networked Systems Design and Implementation (NSDI 16)","author":"Choi","year":"2016"},{"key":"2023121811453270400_ref18","doi-asserted-by":"crossref","first-page":"1303","DOI":"10.1109\/TVLSI.2007.909801","article-title":"Optimization of pattern matching circuits for regular expression on fpga","volume":"15","author":"Lin","year":"2007","journal-title":"IEEE Trans. VLSI Syst."},{"key":"2023121811453270400_ref19","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1145\/1477942.1477948","volume-title":"Proceedings of the 4th ACM\/IEEE Symposium on Architectures for Networking and Communications Systems","author":"Yang","year":"2008"},{"key":"2023121811453270400_ref20","first-page":"227","volume-title":"The 9th Annual IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM\u201901)","author":"Sidhu","year":"2001"},{"key":"2023121811453270400_ref21","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1109\/FPL.2008.4629920","volume-title":"2008 International Conference on Field Programmable Logic and Applications","author":"Yamagaki","year":"2008"},{"key":"2023121811453270400_ref22","first-page":"359","volume-title":"Proc. 16th Workshop on Synthesis and System Integration of Mixed Information technologies","author":"Nakahara","year":"2010"},{"key":"2023121811453270400_ref23","doi-asserted-by":"crossref","first-page":"252","DOI":"10.1109\/ICUFN.2013.6614821","volume-title":"2013 Fifth International Conference on Ubiquitous and Future Networks (ICUFN)","author":"Hieu","year":"2013"},{"key":"2023121811453270400_ref24","first-page":"1","article-title":"Accelerating dfa construction by hierarchical merging","author":"Liu","year":"2011","journal-title":"IEEE Int. Symp. Parallel Distrib. Process. Appl."},{"key":"2023121811453270400_ref25","author":"Levandoski, J., Sommer, E. and Strait, M."},{"key":"2023121811453270400_ref26","volume-title":"2017 ACM International Conference","author":"Sidler","year":"2017"},{"key":"2023121811453270400_ref27","first-page":"1083","volume-title":"14th {USENIX} Symposium on Operating Systems Design and Implementation ({OSDI} 20)","author":"Zhao","year":"2020"},{"key":"2023121811453270400_ref28","doi-asserted-by":"crossref","first-page":"95","DOI":"10.12785\/amis\/080111","article-title":"A novel algorithm for the conversion of parallel regular expressions to non-deterministic finite automata","volume":"8","author":"Kumar","year":"2014","journal-title":"Appl. Math. Inform. Sci."},{"key":"2023121811453270400_ref29","doi-asserted-by":"crossref","first-page":"448","DOI":"10.1093\/comjnl\/bxu049","article-title":"An improved algorithm for the metamorphosis of semi-extended regular expressions to deterministic finite automata","volume":"58","author":"Kumar","year":"2015","journal-title":"Comput. J."},{"key":"2023121811453270400_ref30","first-page":"11960","article-title":"New heuristics for obtaining smaller regular expressions from deterministic finite automata","volume":"12","author":"Singh","year":"2017","journal-title":"Int. J. Appl. Eng. Res."},{"key":"2023121811453270400_ref31","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1145\/1185347.1185360","volume-title":"Proceedings of the 2006 ACM\/IEEE Symposium on Architecture for Networking and Communications Systems","author":"Yu","year":"2006"},{"key":"2023121811453270400_ref32","first-page":"1","volume-title":"Proceedings of the 2007 ACM CoNEXT Conference","author":"Becchi","year":"2007"},{"key":"2023121811453270400_ref33","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1016\/j.comcom.2014.08.005","article-title":"Practical regular expression matching free of scalability and performance barriers","volume":"54","author":"Wang","year":"2014","journal-title":"Comput. Commun."},{"key":"2023121811453270400_ref34","author":"The Snort Team."},{"key":"2023121811453270400_ref35","doi-asserted-by":"crossref","first-page":"154","DOI":"10.1016\/j.jnca.2015.05.012","article-title":"Freme: a pattern partition based engine for fast and scalable regular expression matching in practice - sciencedirect","volume":"55","author":"Wang, K. and Li, J.","year":"2015","journal-title":"J. Netw. Comput. Appl."},{"key":"2023121811453270400_ref36","first-page":"1","volume-title":"Proceedings IEEE Infocom 2006, 25th IEEE International Conference on Computer Communications","author":"Lunteren","year":"2006"},{"key":"2023121811453270400_ref37","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1145\/1629435.1629456","volume-title":"Proceedings of the 7th IEEE\/ACM International Conference on Hardware\/Software Codesign and System Synthesis","author":"Rohrer","year":"2009"},{"key":"2023121811453270400_ref38","doi-asserted-by":"crossref","first-page":"1797","DOI":"10.1109\/JSAC.2014.2358839","article-title":"Towards fast and optimal grouping of regular expressions via dfa size estimation","volume":"32","author":"Liu","year":"2014","journal-title":"IEEE J. Selected Areas Commun."},{"key":"2023121811453270400_ref39","doi-asserted-by":"crossref","DOI":"10.1371\/journal.pone.0206068","article-title":"Exploring efficient grouping algorithms in regular expression matching","volume":"13","author":"Xu","year":"2018","journal-title":"PLoS One"},{"key":"2023121811453270400_ref40","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1145\/1151659.1159952","article-title":"Algorithms to accelerate multiple regular expressions matching for deep packet inspection","volume":"36","author":"Kumar","year":"2006","journal-title":"ACM SIGCOMM Comput. Commun. Rev."},{"key":"2023121811453270400_ref41","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1145\/1323548.1323573","volume-title":"Proceedings of the 3rd ACM\/IEEE Symposium on Architecture for Networking and Communications Systems","author":"Becchi","year":"2007"},{"key":"2023121811453270400_ref42","doi-asserted-by":"crossref","first-page":"683","DOI":"10.1109\/TNET.2010.2089639","article-title":"Differential encoding of dfas for fast regular expression matching","volume":"19","author":"Ficara","year":"2010","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"2023121811453270400_ref43","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1109\/HPCA47549.2020.00017","volume-title":"2020 IEEE International Symposium on High Performance Computer Architecture (HPCA)","author":"Sadredini","year":"2020"},{"key":"2023121811453270400_ref44","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1145\/3373376.3378459","volume-title":"Proceedings of the Twenty-Fifth International Conference on Architectural Support for Programming Languages and Operating Systems","author":"Sadredini","year":"2020"},{"key":"2023121811453270400_ref45","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1017\/S1351324903003127","article-title":"An efficient incremental dfa minimization algorithm","volume":"9","author":"Watson","year":"2003","journal-title":"Natural Lang. Eng."},{"key":"2023121811453270400_ref46","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1109\/NOMS.2012.6211894","volume-title":"2012 IEEE Network Operations and Management Symposium","author":"Antonello","year":"2012"},{"key":"2023121811453270400_ref47","doi-asserted-by":"crossref","first-page":"2628","DOI":"10.1109\/INFCOM.2004.1354682","volume-title":"IEEE INFOCOM 2004","author":"Tuck","year":"2004"},{"key":"2023121811453270400_ref48","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1109\/IISWC.2008.4636093","volume-title":"2008 IEEE International Symposium on Workload Characterization","author":"Becchi","year":"2008"},{"key":"2023121811453270400_ref49","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1016\/j.comcom.2014.12.011","article-title":"Design and optimizations for efficient regular expression matching in dpi systems","volume":"61","author":"Antonello","year":"2015","journal-title":"Comput. Comm."},{"key":"2023121811453270400_ref50","author":"Intel"},{"key":"2023121811453270400_ref51","author":"Xilinx"},{"key":"2023121811453270400_ref52","author":"Jincheng Zhong"},{"key":"2023121811453270400_ref53","author":"Jincheng Zhong. davemmd\/rem-fpga-cpu: An rem engine in a heterogeneous fpga-cpu architecture"},{"key":"2023121811453270400_ref54","author":"Amazon"},{"key":"2023121811453270400_ref55","author":"Dell"},{"key":"2023121811453270400_ref56","author":"Kleene","year":"1951"},{"key":"2023121811453270400_ref57","doi-asserted-by":"crossref","first-page":"419","DOI":"10.1145\/363347.363387","article-title":"Programming techniques: regular expression search algorithm","volume":"11","author":"Thompson","year":"1968","journal-title":"Commun ACM"},{"key":"2023121811453270400_ref58","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"Hopcroft","year":"1979","edition":"3rd"},{"key":"2023121811453270400_ref59","doi-asserted-by":"crossref","DOI":"10.1016\/B978-0-12-417750-5.50022-1","article-title":"An n log n algorithm for minimizing states in a finite automaton","author":"Hopcroft","year":"1971","journal-title":"Theory of machines and computations"},{"key":"2023121811453270400_ref60","doi-asserted-by":"crossref","first-page":"1360","DOI":"10.1109\/ICCC47050.2019.9064254","article-title":"Accelerating dfa construction based on hierarchical merging","volume-title":"2019 IEEE 5th International Conference on Computer and Communications (ICCC)","author":"Zhong","year":"2019"}],"container-title":["The Computer Journal"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/comjnl\/article-pdf\/66\/12\/2928\/54446641\/bxac138.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/comjnl\/article-pdf\/66\/12\/2928\/54446641\/bxac138.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,12,18]],"date-time":"2023-12-18T06:46:14Z","timestamp":1702881974000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/comjnl\/article\/66\/12\/2928\/6770084"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,10,23]]},"references-count":60,"journal-issue":{"issue":"12","published-online":{"date-parts":[[2022,10,23]]},"published-print":{"date-parts":[[2023,12,14]]}},"URL":"https:\/\/doi.org\/10.1093\/comjnl\/bxac138","relation":{},"ISSN":["0010-4620","1460-2067"],"issn-type":[{"value":"0010-4620","type":"print"},{"value":"1460-2067","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2023,12]]},"published":{"date-parts":[[2022,10,23]]}}}