{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T01:19:31Z","timestamp":1760231971480,"version":"build-2065373602"},"reference-count":48,"publisher":"MDPI AG","issue":"20","license":[{"start":{"date-parts":[[2022,10,13]],"date-time":"2022-10-13T00:00:00Z","timestamp":1665619200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Nature Science Foundation of China","doi-asserted-by":"publisher","award":["62102436","202250E060","614221722050603","2021CFB279","2020CFB339"],"award-info":[{"award-number":["62102436","202250E060","614221722050603","2021CFB279","2020CFB339"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Projects Foundation of University","award":["62102436","202250E060","614221722050603","2021CFB279","2020CFB339"],"award-info":[{"award-number":["62102436","202250E060","614221722050603","2021CFB279","2020CFB339"]}]},{"name":"National Defence Science and Technology Key Laboratory Foundation Project","award":["62102436","202250E060","614221722050603","2021CFB279","2020CFB339"],"award-info":[{"award-number":["62102436","202250E060","614221722050603","2021CFB279","2020CFB339"]}]},{"name":"Hubei Province Natural Science Foundation","award":["62102436","202250E060","614221722050603","2021CFB279","2020CFB339"],"award-info":[{"award-number":["62102436","202250E060","614221722050603","2021CFB279","2020CFB339"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Sensors"],"abstract":"<jats:p>With the exponential growth of cyber\u2013physical systems (CPSs), security challenges have emerged; attacks on critical infrastructure could result in catastrophic consequences. Intrusion detection is the foundation for CPS security protection, and deep-packet inspection is the primary method for signature-matched mechanisms. This method usually employs regular expression matching (REM) to detect possible threats in the packet payload. State explosion is the critical challenge for REM applications, which originates primarily from features of large character sets with unbounded (closures) or bounded (counting) repetitions. In this work, we propose Offset-FA to handle these repetitions in a uniform mechanism. Offset-FA eliminates state explosion by extracting the repetitions from the nonexplosive string fragments. Then, these fragments are compiled into a fragment-DFA, while a fragment relation table and a reset table are constructed to preserve their connection and offset relationship. To our knowledge, Offset-FA is the first automaton to handle these two kinds of repetitions together with a uniform mechanism. Experiments demonstrate that Offset-FA outperforms state-of-the-art solutions in both space cost and matching speed on the premise of matching correctness, and achieves a comparable matching speed with that of DFA on practical rule sets.<\/jats:p>","DOI":"10.3390\/s22207781","type":"journal-article","created":{"date-parts":[[2022,10,14]],"date-time":"2022-10-14T01:44:13Z","timestamp":1665711853000},"page":"7781","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Offset-FA: A Uniform Method to Handle Both Unbounded and Bounded Repetitions in Regular Expression Matching"],"prefix":"10.3390","volume":"22","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2417-434X","authenticated-orcid":false,"given":"Chengcheng","family":"Xu","sequence":"first","affiliation":[{"name":"National Key Laboratory of Science and Technology on Vessel Integrated Power System, Naval University of Engineering, Wuhan 430033, China"}]},{"given":"Kun","family":"Yu","sequence":"additional","affiliation":[{"name":"National Key Laboratory of Science and Technology on Vessel Integrated Power System, Naval University of Engineering, Wuhan 430033, China"}]},{"given":"Xinghua","family":"Xu","sequence":"additional","affiliation":[{"name":"National Key Laboratory of Science and Technology on Vessel Integrated Power System, Naval University of Engineering, Wuhan 430033, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3546-0253","authenticated-orcid":false,"given":"Xianqiang","family":"Bao","sequence":"additional","affiliation":[{"name":"National Key Laboratory of Science and Technology on Vessel Integrated Power System, Naval University of Engineering, Wuhan 430033, China"}]},{"given":"Songbing","family":"Wu","sequence":"additional","affiliation":[{"name":"National Key Laboratory of Science and Technology on Vessel Integrated Power System, Naval University of Engineering, Wuhan 430033, China"}]},{"given":"Baokang","family":"Zhao","sequence":"additional","affiliation":[{"name":"College of Computer, National University of Defense Technology, Changsha 410073, China"}]}],"member":"1968","published-online":{"date-parts":[[2022,10,13]]},"reference":[{"key":"ref_1","unstructured":"Lee, E.A. (2007). Computing Foundations and Practice for Cyber-Physical Systems: A Preliminary Report, University of California. Tech. Rep. UCB\/EECS-2007-72."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"1802","DOI":"10.1109\/JIOT.2017.2703172","article-title":"Cyber-physical systems security:A survey","volume":"4","author":"Humayed","year":"2017","journal-title":"IEEE Internet Things J."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Biron, K., Bazzaza, W., Yaqoob, K., Gawanmeh, A., and Fachkha, C. (September, January 31). A big data fusion to profile CPS security threats against operational technology. Proceedings of the 2020 IEEE 21st International Symposium on \u201cA World of Wireless, Mobile and Multimedia Networks\u201d (WoWMoM), Cork, Ireland.","DOI":"10.1109\/WoWMoM49955.2020.00073"},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Kwon, H.Y., Kim, T., and Lee, M.K. (2022). Advanced Intrusion Detection Combining Signature-Based and Behavior-Based Detection Methods. Electronics, 11.","DOI":"10.3390\/electronics11060867"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Nyasore, O.N., Zavarsky, P., Swar, B., Naiyeju, R., and Dabra, S. (2020, January 25\u201327). Deep packet inspection in industrial automation control system to mitigate attacks exploiting modbus\/TCP vulnerabilities. Proceedings of the 2020 IEEE 6th Intl Conference on Big Data Security on Cloud (BigDataSecurity), IEEE Intl Conference on High Performance and Smart Computing,(HPSC) and IEEE Intl Conference on Intelligent Data and Security (IDS), Baltimore, MD, USA.","DOI":"10.1109\/BigDataSecurity-HPSC-IDS49724.2020.00051"},{"key":"ref_6","unstructured":"(2022, June 01). Snort v2.9. Available online: http:\/\/www.snort.org\/."},{"key":"ref_7","unstructured":"(2022, June 01). Bro Intrusion Detection System. Available online: http:\/\/www.bro.org\/."},{"key":"ref_8","unstructured":"(2022, June 01). Application Layer Packet Classifier for Linux. Available online: http:\/\/l7-filter.sourceforge.net\/."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Kosar, V., Zadnik, M., and Korenek, J. (2013, January 9\u201311). NFA reduction for regular expressions matching using FPGA. Proceedings of the 2013 International Conference on Field-Programmable Technology (FPT), Kyoto, Japan.","DOI":"10.1109\/FPT.2013.6718381"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Callanan, D., Kljucaric, L., and George, A. (2021, January 27\u201329). Accelerating regular-expression matching on fpgas with high-level synthesis. Proceedings of the International Workshop on OpenCL, Munich Germany.","DOI":"10.1145\/3456669.3456716"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3476982","article-title":"Cicero: A domain-specific architecture for efficient regular expression matching","volume":"20","author":"Parravicini","year":"2021","journal-title":"ACM Trans. Embed. Comput. Syst. (TECS)"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Jiang, N., Lin, P., He, Y., Tan, Z., and Hu, J. (2021, January 29\u201331). Design of A New Type of Regular Expression Matching Engine Based on FPGA. Proceedings of the 2021 IEEE 15th International Conference on Anti-Counterfeiting, Security, and Identification (ASID), Xiamen, China.","DOI":"10.1109\/ASID52932.2021.9651676"},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Comodi, A., Conficconi, D., Scolari, A., and Santambrogio, M.D. (2008, January 21\u201325). TiReX: Tiled regular expression matching architecture. Proceedings of the 2018 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW), Vancouver, BC, Canada.","DOI":"10.1109\/IPDPSW.2018.00028"},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Wang, S., Zhang, M., Li, G., Liu, C., Liu, Y., Jia, X., and Xu, M. (2021, January 10). Making Multi-String Pattern Matching Scalable and Cost-Efficient with Programmable Switching ASICs. Proceedings of the IEEE INFOCOM 2021-IEEE Conference on Computer Communications, Vancouver, BC, Canada.","DOI":"10.1109\/INFOCOM42981.2021.9488796"},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Jiang, P., and Agrawal, G. (2017, January 4\u20138). Combining SIMD and Many\/Multi-core parallelism for finite state machines with enumerative speculation. Proceedings of the 22nd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, Austin, TX, USA.","DOI":"10.1145\/3018743.3018760"},{"key":"ref_16","first-page":"177","article-title":"High speed regular expression matching engine with fast pre-processing","volume":"16","author":"Fu","year":"2019","journal-title":"China Commun."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"1137","DOI":"10.1109\/TPDS.2019.2953646","article-title":"REACT: Scalable and high-performance regular expression pattern matching accelerator for in-storage processing","volume":"31","author":"Jeong","year":"2019","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"ref_18","unstructured":"Vasiliadis, G., Antonatos, S., Polychronakis, M., Markatos, E.P., and Ioannidis, S. (2008, January 15\u201317). Gnort: High performance network intrusion detection using graphics processors. Proceedings of the Recent Advances in Intrusion Detection, Cambridge, MA, USA."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Yu, X., and Becchi, M. (2013, January 14\u201316). GPU acceleration of regular expression matching for large datasets: Exploring the implementation space. Proceedings of the ACM International Conference on Computing Frontiers, Ischia, Italy.","DOI":"10.1145\/2482767.2482791"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1007\/s11265-016-1139-0","article-title":"An efficient GPU-based multiple pattern matching algorithm for packet filtering","volume":"86","author":"Hung","year":"2017","journal-title":"J. Signal Process. Syst."},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Gong, Q., Wu, W., and Fermi, P.D. (2018, January 1\u20134). GoldenEye: Stream-based network packet inspection using GPUs. Proceedings of the 2018 IEEE 43rd Conference on Local Computer Networks (LCN), Chicago, IL, USA.","DOI":"10.1109\/LCN.2018.8638115"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"94","DOI":"10.1109\/TNET.2013.2256466","article-title":"Fast Regular Expression Matching Using Small TCAM","volume":"22","author":"Meiners","year":"2014","journal-title":"IEEE\/ACM Trans. Netw. (TON)"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"963","DOI":"10.1109\/TNANO.2019.2936239","article-title":"Memristor TCAMs accelerate regular expression matching for network intrusion detection","volume":"18","author":"Graves","year":"2019","journal-title":"IEEE Trans. Nanotechnol."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"2003437","DOI":"10.1002\/adma.202003437","article-title":"In-Memory Computing with Memristor Content Addressable Memories for Pattern Matching","volume":"32","author":"Graves","year":"2020","journal-title":"Adv. Mater."},{"key":"ref_25","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":"ref_26","first-page":"4","article-title":"A-DFA: A time-and space-efficient DFA compression algorithm for fast regular expression evaluation","volume":"10","author":"Becchi","year":"2013","journal-title":"ACM Trans. Archit. Code Optim. (TACO)"},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Kumar, S., Turner, J., and Williams, J. (2006, January 3\u20135). Advanced algorithms for fast and scalable deep packet inspection. Proceedings of the 2006 ACM\/IEEE Symposium on Architecture for Networking and Communications Systems, San Jose, CA, USA.","DOI":"10.1145\/1185347.1185359"},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"1701","DOI":"10.1109\/TNET.2014.2309014","article-title":"Bypassing space explosion in high-speed regular expression matching","volume":"22","author":"Patel","year":"2014","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"2400","DOI":"10.1109\/TNET.2016.2533605","article-title":"Overlay Automata and Algorithms for Fast and Scalable Regular Expression Matching","volume":"24","author":"Liu","year":"2016","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Fu, Z., Zhou, S., and Li, J.Y. (2017, January 21\u201325). bitFA: A Novel Data Structure for Fast and Update-friendly Regular Expression Matching. Proceedings of the SIGCOMM Posters and Demos, Los Angeles, CA, USA.","DOI":"10.1145\/3123878.3132011"},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"e3940.1","DOI":"10.1002\/cpe.3940","article-title":"RICS-DFA: A space and time-efficient signature matching algorithm with Reduced Input Character Set","volume":"29","author":"Tang","year":"2017","journal-title":"Concurr. Comput."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"3317","DOI":"10.1007\/s11227-018-2517-0","article-title":"An improved method in deep packet inspection based on regular expression","volume":"75","author":"Sun","year":"2019","journal-title":"J. Supercomput."},{"key":"ref_33","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 Commun. Surv. Tutor."},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"Yu, F., Chen, Z., Diao, Y., Lakshman, T., and Katz, R.H. (2006, January 3\u20135). Fast and memory-efficient regular expression matching for deep packet inspection. Proceedings of the 2006 ACM\/IEEE Symposium on Architecture for Networking and Communications Systems, San Jose, CA, USA.","DOI":"10.1145\/1185347.1185360"},{"key":"ref_35","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. Sel. Areas Commun."},{"key":"ref_36","doi-asserted-by":"crossref","unstructured":"Xu, C., Su, J., and Chen, S. (2018). Exploring efficient grouping algorithms in regular expression matching. PLoS ONE, 13.","DOI":"10.1371\/journal.pone.0206068"},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"Becchi, M., and Crowley, P. (2007, January 10\u201313). A hybrid finite automaton for practical deep packet inspection. Proceedings of the 2007 ACM CoNEXT Conference, New York, NY, USA.","DOI":"10.1145\/1364654.1364656"},{"key":"ref_38","doi-asserted-by":"crossref","unstructured":"Kumar, S., Chandrasekaran, B., Turner, J., and Varghese, G. (2007, January 3\u20134). Curing regular expressions matching algorithms from insomnia, amnesia, and acalculia. Proceedings of the 3rd ACM\/IEEE Symposium on Architecture for Networking and Communications Systems, Orlando, FL, USA.","DOI":"10.1145\/1323548.1323574"},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"1810","DOI":"10.1109\/JSAC.2014.2358856","article-title":"TFA: A tunable finite automaton for pattern matching in network intrusion detection systems","volume":"32","author":"Xu","year":"2014","journal-title":"IEEE J. Sel. Areas Commun."},{"key":"ref_40","unstructured":"(2021, July 10). Cavium, OCTEON5860. Available online: http:\/\/www.cavium.com\/OCTEON_MIPS64.html\/."},{"key":"ref_41","unstructured":"(2022, March 04). Broadcom, XLP700 Series. Available online: https:\/\/jp.broadcom.com\/products\/embedded-and-networking-processors\/communications\/xlp700."},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1145\/1402946.1402983","article-title":"Deflating the big bang: Fast and scalable deep packet inspection with extended finite automata","volume":"38","author":"Smith","year":"2008","journal-title":"ACM SIGCOMM Comput. Commun. Rev."},{"key":"ref_43","doi-asserted-by":"crossref","unstructured":"Smith, R., Estan, C., and Jha, S. (2008, January 18\u201322). XFA: Faster signature matching with extended automata. Proceedings of the 2008 IEEE Symposium on Security and Privacy SP 2008, Oakland, CA, USA.","DOI":"10.1109\/SP.2008.14"},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"1822","DOI":"10.1109\/JSAC.2014.2358840","article-title":"Revisiting state blow-up: Automatically building augmented-fa while preserving functional equivalence","volume":"32","author":"Yu","year":"2014","journal-title":"IEEE J. Sel. Areas Commun."},{"key":"ref_45","doi-asserted-by":"crossref","unstructured":"Norige, E., and Liu, A. (2016, January 27\u201330). A De-compositional Approach to Regular Expression Matching for Network Security Applications. Proceedings of the 2016 IEEE 36th International Conference on Distributed Computing Systems (ICDCS), Nara, Japan.","DOI":"10.1109\/ICDCS.2016.63"},{"key":"ref_46","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":"ref_47","doi-asserted-by":"crossref","unstructured":"Xu, C., Su, J., Chen, S., and Han, B. (2017, January 22\u201325). Offset-FA: Detach the closures and countings for efficient regular expression matching. Proceedings of the 2017 IEEE 7th International Symposium on Cloud and Service Computing (SC2), Kanazawa, Japan.","DOI":"10.1109\/SC2.2017.50"},{"key":"ref_48","unstructured":"(2021, August 10). Mit Darpa Intrusion Detection Data Sets. Available online: https:\/\/ll.mit.edu\/ideval\/data\/index.html."}],"container-title":["Sensors"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1424-8220\/22\/20\/7781\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T00:53:35Z","timestamp":1760144015000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1424-8220\/22\/20\/7781"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,10,13]]},"references-count":48,"journal-issue":{"issue":"20","published-online":{"date-parts":[[2022,10]]}},"alternative-id":["s22207781"],"URL":"https:\/\/doi.org\/10.3390\/s22207781","relation":{},"ISSN":["1424-8220"],"issn-type":[{"type":"electronic","value":"1424-8220"}],"subject":[],"published":{"date-parts":[[2022,10,13]]}}}