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

doi:10.3724/SP.J.1087.2011.02943

计算机应用 ›› 2011, Vol. 31 ›› Issue (11): 2943-2946.DOI: 10.3724/SP.J.1087.2011.02943

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

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

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

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

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

摘要/Abstract

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

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

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

中图分类号:

TP393

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

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.

[1]	方介泼, 陶重犇. 应对零日攻击的混合车联网入侵检测系统[J]. 《计算机应用》唯一官方网站, 2024, 44(9): 2763-2769.
[2]	申云飞, 申飞, 李芳, 张俊. 基于张量虚拟机的深度神经网络模型加速方法[J]. 《计算机应用》唯一官方网站, 2023, 43(9): 2836-2844.
[3]	许睿, 梁爽, 万航, 文益民, 沈世铭, 李建. 基于烛台图模式匹配的PM_2.5扩散特征的提取[J]. 《计算机应用》唯一官方网站, 2023, 43(5): 1394-1400.
[4]	郝劭辰, 卫孜钻, 马垚, 于丹, 陈永乐. 基于高效联邦学习算法的网络入侵检测模型[J]. 《计算机应用》唯一官方网站, 2023, 43(4): 1169-1175.
[5]	马英杰, 肖靖, 赵耿, 曾萍, 杨亚涛. 可控网格多涡卷混沌系统族及其硬件电路实现[J]. 《计算机应用》唯一官方网站, 2023, 43(3): 956-961.
[6]	宋斌威, 王耀. 面向FPGA 知识产权保护的低开销按次付费授权方案[J]. 《计算机应用》唯一官方网站, 2023, 43(10): 3142-3148.
[7]	刘拥民, 杨钰津, 罗皓懿, 黄浩, 谢铁强. 基于双向循环生成对抗网络的无线传感网入侵检测方法[J]. 《计算机应用》唯一官方网站, 2023, 43(1): 160-168.
[8]	董宁, 程晓荣, 张铭泉. 基于物联网平台的动态权重损失函数入侵检测系统[J]. 《计算机应用》唯一官方网站, 2022, 42(7): 2118-2124.
[9]	高兵, 郑雅, 秦静, 邹启杰, 汪祖民. 基于麻雀搜索算法和改进粒子群优化算法的网络入侵检测算法[J]. 《计算机应用》唯一官方网站, 2022, 42(4): 1201-1206.
[10]	张师鹏, 李永忠, 杜祥通. 基于半监督学习和三支决策的入侵检测模型[J]. 计算机应用, 2021, 41(9): 2602-2608.
[11]	王月, 江逸茗, 兰巨龙. 基于改进三元组网络和K近邻算法的入侵检测[J]. 计算机应用, 2021, 41(7): 1996-2002.
[12]	王垚, 孙国梓. 基于聚类和实例硬度的入侵检测过采样方法[J]. 计算机应用, 2021, 41(6): 1709-1714.
[13]	张全龙, 王怀彬. 基于膨胀卷积和门控循环单元组合的入侵检测模型[J]. 计算机应用, 2021, 41(5): 1372-1377.
[14]	任晓奎, 刘鹏飞, 陶志勇, 刘影, 白立春. 基于单快拍信号到达角估计算法的室内入侵检测[J]. 计算机应用, 2021, 41(4): 1153-1159.
[15]	程小辉, 牛童, 汪彦君. 基于序列模型的无线传感网入侵检测系统[J]. 计算机应用, 2020, 40(6): 1680-1684.

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

Survey on FPGA-based regular expressions matching algorithms

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics