基于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]. 计算机应用, 2021, 41(9): 2602-2608.
[2]	王月, 江逸茗, 兰巨龙. 基于改进三元组网络和K近邻算法的入侵检测[J]. 计算机应用, 2021, 41(7): 1996-2002.
[3]	王垚, 孙国梓. 基于聚类和实例硬度的入侵检测过采样方法[J]. 计算机应用, 2021, 41(6): 1709-1714.
[4]	张全龙, 王怀彬. 基于膨胀卷积和门控循环单元组合的入侵检测模型[J]. 计算机应用, 2021, 41(5): 1372-1377.
[5]	任晓奎, 刘鹏飞, 陶志勇, 刘影, 白立春. 基于单快拍信号到达角估计算法的室内入侵检测[J]. 计算机应用, 2021, 41(4): 1153-1159.
[6]	程小辉, 牛童, 汪彦君. 基于序列模型的无线传感网入侵检测系统[J]. 计算机应用, 2020, 40(6): 1680-1684.
[7]	许英鑫, 孙磊, 赵建成, 郭松辉. 基于蚁群优化算法的虚拟现场可编程门阵列部署策略[J]. 计算机应用, 2020, 40(3): 747-752.
[8]	欧彬利, 钟夏汝, 代建华, 杨田. 基于变精度覆盖粗糙集的入侵检测方法[J]. 计算机应用, 2020, 40(12): 3465-3470.
[9]	李中伟, 谭凯, 关亚东, 姜文淇, 叶麟. 车载CAN总线脱离攻击及其入侵检测算法[J]. 计算机应用, 2020, 40(11): 3224-3228.
[10]	雷小康, 尹志刚, 赵瑞莲. 基于FPGA的卷积神经网络定点加速[J]. 计算机应用, 2020, 40(10): 2811-2816.
[11]	池亚平, 莫崇维, 杨垠坦, 陈纯霞. 面向软件定义网络架构的入侵检测模型设计与实现[J]. 计算机应用, 2020, 40(1): 116-122.
[12]	杨宏宇, 王峰岩. 基于改进卷积神经网络的网络入侵检测模型[J]. 计算机应用, 2019, 39(9): 2604-2610.
[13]	曹卫东, 许志香. 高效的半监督多层次入侵检测算法[J]. 计算机应用, 2019, 39(7): 1979-1984.
[14]	潘建国, 李豪. 基于实用拜占庭容错的物联网入侵检测方法[J]. 计算机应用, 2019, 39(6): 1742-1746.
[15]	郭旭东, 李小敏, 敬如雪, 高玉琢. 基于改进的稀疏去噪自编码器的入侵检测[J]. 计算机应用, 2019, 39(3): 769-773.

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

Survey on FPGA-based regular expressions matching algorithms

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics