Survey on FPGA-based regular expressions matching algorithms

doi:10.3724/SP.J.1087.2011.02943

Journal of Computer Applications ›› 2011, Vol. 31 ›› Issue (11): 2943-2946.DOI: 10.3724/SP.J.1087.2011.02943

• Computer software technology • Previous Articles Next Articles

Survey on FPGA-based regular expressions matching algorithms

TANG Qiu¹,²,JIANG Lei¹,TAN Jian-long¹,LIU Jin-gang¹,²

1. Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190, China
2. Joint Faculty of Computer Scientific Research, Capital Normal University, Beijing 100037, China

Received:2011-04-15 Revised:2011-06-19 Online:2011-11-16 Published:2011-11-01
Contact: TANG Qiu

基于FPGA的正则表达式匹配算法综述

唐球¹,²,姜磊²,谭建龙²,刘金刚¹,²

1. 首都师范大学计算机科学联合研究院，北京 100037
2. 中国科学院计算技术研究所，北京 100190

通讯作者: 唐球
作者简介:唐球（1985-），男，湖南怀化人，硕士研究生，主要研究方向：网络安全、模式匹配；姜磊（1984-），男，山东烟台人，博士研究生，主要研究方向：网络安全、模式匹配；谭建龙（1974-），男，湖南长沙人，副研究员，博士，主要研究方向：自然语言处理、网络安全、模式匹配；刘金刚（1963-)，男，辽宁铁岭人，教授，博士，主要研究方向：操作系统、智能接口。
基金资助:
国家973计划项目;国家自然科学基金资助项目

Abstract

Abstract: The advantages of hardware-based regular expressions matching were analyzed. At the same time, the basic ideas and methodology for Field Programmable Gate Array (FPGA)-based regular expressions matching were introduced. Furthermore, an algorithm classification approach was proposed in terms of two technical indicators: matching speed and resource utilization. The advantages, disadvantages and the basic ideas of various algorithms were summarized. Finally, the key techniques, difficulties and the future direction in this field were discussed.

Key words: finite automata, Field Programmable Gate Array (FPGA), regular expression, intrusion detection, pattern matching

摘要： 分析了基于硬件正则表达式匹配的优势,介绍了基于现场可编程门阵列（FPGA）的正则表达式匹配算法的基本思想和设计方法，从匹配速度和资源利用率两个技术指标的角度对现有算法进行分类，综述了当前的主流算法并分析了其优缺点，最后论述了目前基于FPGA正则表达式匹配算法设计的难点并展望了未来研究的发展趋势。

关键词: 有穷自动机, 现场可编程门阵列, 正则表达式, 入侵检测, 模式匹配

CLC Number:

TP393

TANG Qiu JIANG Lei TAN Jian-long LIU Jin-gang. Survey on FPGA-based regular expressions matching algorithms[J]. Journal of Computer Applications, 2011, 31(11): 2943-2946.

唐球姜磊谭建龙刘金刚. 基于FPGA的正则表达式匹配算法综述[J]. 计算机应用, 2011, 31(11): 2943-2946.

[1]	Jiepo FANG, Chongben TAO. Hybrid internet of vehicles intrusion detection system for zero-day attacks [J]. Journal of Computer Applications, 2024, 44(9): 2763-2769.
[2]	Rui XU, Shuang LIANG, Hang WAN, Yimin WEN, Shiming SHEN, Jian LI. Extraction of PM_2.5 diffusion characteristics based on candlestick pattern matching [J]. Journal of Computer Applications, 2023, 43(5): 1394-1400.
[3]	Shaochen HAO, Zizuan WEI, Yao MA, Dan YU, Yongle CHEN. Network intrusion detection model based on efficient federated learning algorithm [J]. Journal of Computer Applications, 2023, 43(4): 1169-1175.
[4]	Yingjie MA, Jing XIAO, Geng ZHAO, Ping ZENG, Yatao YANG. Controllable grid multi-scroll chaotic system family and its hardware circuit implementation [J]. Journal of Computer Applications, 2023, 43(3): 956-961.
[5]	Binwei SONG, Yao WANG. Low-cost pay-per-use licensing scheme for FPGA intellectual property protection [J]. Journal of Computer Applications, 2023, 43(10): 3142-3148.
[6]	LIU Yongmin, YANG Yujin, LUO Haoyi, HUANG Hao, XIE Tieqiang. Intrusion detection method for wireless sensor network based on bidirectional circulation generative adversarial network [J]. Journal of Computer Applications, 2023, 43(1): 160-168.
[7]	Ning DONG, Xiaorong CHENG, Mingquan ZHANG. Intrusion detection system with dynamic weight loss function based on internet of things platform [J]. Journal of Computer Applications, 2022, 42(7): 2118-2124.
[8]	Bing GAO, Ya ZHENG, Jing QIN, Qijie ZOU, Zumin WANG. Network intrusion detection algorithm based on sparrow search algorithm and improved particle swarm optimization algorithm [J]. Journal of Computer Applications, 2022, 42(4): 1201-1206.
[9]	ZHANG Shipeng, LI Yongzhong, DU Xiangtong. Intrusion detection model based on semi-supervised learning and three-way decision [J]. Journal of Computer Applications, 2021, 41(9): 2602-2608.
[10]	HUANG Chengcheng, DONG Xiaoxiao, LI Zhao. Deep pipeline 5×5 convolution method based on two-dimensional Winograd algorithm [J]. Journal of Computer Applications, 2021, 41(8): 2258-2264.
[11]	WANG Yue, JIANG Yiming, LAN Julong. Intrusion detection based on improved triplet network and K-nearest neighbor algorithm [J]. Journal of Computer Applications, 2021, 41(7): 1996-2002.
[12]	WANG Yao, SUN Guozi. Oversampling method for intrusion detection based on clustering and instance hardness [J]. Journal of Computer Applications, 2021, 41(6): 1709-1714.
[13]	ZHANG Quanlong, WANG Huaibin. Intrusion detection model based on combination of dilated convolution and gated recurrent unit [J]. Journal of Computer Applications, 2021, 41(5): 1372-1377.
[14]	REN Xiaokui, LIU Pengfei, TAO Zhiyong, LIU Ying, BAI Lichun. Indoor intrusion detection based on direction-of-arrival estimation algorithm for single snapshot [J]. Journal of Computer Applications, 2021, 41(4): 1153-1159.
[15]	WANG Xiaofeng, JIANG Penglong, ZHOU Hui, ZHAO Xiongbo. Design of FPGA accelerator with high parallelism for convolution neural network [J]. Journal of Computer Applications, 2021, 41(3): 812-819.

Survey on FPGA-based regular expressions matching algorithms

基于FPGA的正则表达式匹配算法综述

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics