PFA在FPGA正则引擎上的设计和仿真

doi:10.13190/j.jbupt.2015.06.015

北京邮电大学学报 ›› 2015, Vol. 38 ›› Issue (6): 69-73.doi: 10.13190/j.jbupt.2015.06.015

PFA在FPGA正则引擎上的设计和仿真

敬茂华^1,2,3, 江彬², 辛阳^3,4, 杨义先^2,4

1. 东北大学秦皇岛分校计算机与通信工程学院, 河北秦皇岛 066004;
2. 东北大学信息科学与工程学院, 沈阳 110819;
3. 云安全技术北京市工程实验室, 北京 100082;
4. 北京邮电大学信息安全中心, 北京 100876

收稿日期:2015-01-22 出版日期:2015-12-28 发布日期:2015-12-01
作者简介:敬茂华(1977—),女,讲师,E-mail:jing_jmh@163.com;杨义先(1961—),男,教授,博士生导师.
基金资助:
国家自然科学基金项目(61100021,61121061,61202447);河北省自然科学基金项目(F2012501014);河北省教育厅自然科学指导项目(Z2010215)

Design and Simulation of FPGA Engine for Regular Expressions Matching Based on PFA

JING Mao-hua^1,2,3, JIANG Bin², XIN Yang^3,4, YANG Yi-xian^2,4

1. School of Computer and Communication Engineering and Northeastern University at Qinhuangdao, Hebei Qinhuangdao 066004, China;
2. College of Information Science and Engineering and Northeastern University, Shenyang 110819, China;
3. Beijing Engineering Laboratory for Cloud Security, Beijing 100082, China;
4. Information Security Center, Beijing University of Posts and Telecommunications, Beijing 100876, China

Received:2015-01-22 Online:2015-12-28 Published:2015-12-01

摘要/Abstract

摘要：

将后缀自动机构造方法应用到现场可编程门阵列的正则引擎设计上,能够有效地压缩状态空间,提高"速度"和"面积"这2个最主要的现场可编程门阵列的引擎性能指标,并能利用有限的现场可编程门阵列资源来实现更多正则表达式的匹配处理. Testbench模拟仿真结果表明,所设计的正则引擎完全实现了预期匹配要求,而其支持的正则表达式的数量和匹配速度都因有效的规模压缩而得到了很大的提升,对比传统的基于Thompson不确定的有限自动机实现的硬件引擎,其所需要的硬件逻辑资源更少,能够并行执行的正则表达式数量也就越多,有效地提高了匹配效率.

关键词: 正则表达式, 模式匹配, 现场可编程门阵列, 后缀自动机, Thompson不确定的有限自动机

Abstract:

A field programmable gate array(FPGA) engine for regular expressions matching based on postfix automata(PFA) was designed. PFA can obtain smaller size and then reduce the space effectively. The limited FPGA resources can be used to implement more regular expressions simultaneously. Simulation by Testbench implies that the number and speed of the supported regular expressions is deeply improved. Compared with Thompson non-deterministic finite automata (NFA) method, it needs less hardware resources and the number of regular expressions that can be implemented concurrently becomes more, so the efficiency of implement has been increased.

Key words: regular expression, pattern matching, field programmable, postfix automata, Thompson non-deterministic

中图分类号:

TN393

敬茂华, 江彬, 辛阳, 杨义先. PFA在FPGA正则引擎上的设计和仿真[J]. 北京邮电大学学报, 2015, 38(6): 69-73.

JING Mao-hua, JIANG Bin, XIN Yang, YANG Yi-xian. Design and Simulation of FPGA Engine for Regular Expressions Matching Based on PFA[J]. JOURNAL OF BEIJING UNIVERSITY OF POSTS AND TELECOM, 2015, 38(6): 69-73.

[1]	石子成, 李新, 唐颖, 黄善国. 基于全光模式匹配的光包过滤系统[J]. 北京邮电大学学报, 2022, 45(3): 96-101.
[2]	吴江, 许克锋, 李允博. Open ROADM标准OFEC码在300 Gbit/s FPGA系统中的验证[J]. 北京邮电大学学报, 2021, 44(4): 135-140.
[3]	戴庆达, 叶茂. 基于FPGA的高精度时间数字转换电路设计[J]. 北京邮电大学学报, 2020, 43(4): 88-94.
[4]	黎阳, 武昊, 刘斌. 自适应非线性流采样算法的硬件实现[J]. 北京邮电大学学报, 2016, 39(3): 85-90.
[5]	陈璐, 王建立, 贾建禄, 马鑫雪. 地基大型望远镜数字通信系统软件设计[J]. 北京邮电大学学报, 2015, 38(6): 74-80.
[6]	吴高进邹永忠谭敏强. 时频二维搜索捕获算法及其FPGA实现[J]. 北京邮电大学学报, 2009, 32(3): 91-95.
[7]	郑强罗守山辛阳. 无条件安全的隐私保护的集合模式匹配协议[J]. 北京邮电大学学报, 2009, 32(1): 99-102.
[8]	魏景芝，辛阳，杨义先，钮心忻. 用于检测过滤的多模式匹配[J]. 北京邮电大学学报, 2007, 30(6): 69-72.
[9]	谭茂金1，张庚骥2，赵文杰1. 用新型模式匹配法计算地球物理中的电磁场[J]. 北京邮电大学学报, 2006, 29(5): 6-10.
[10]	杨冰，王勇，袁哲明，白洁，张平. MIMO-OFDM系统定时同步算法的FPGA设计[J]. 北京邮电大学学报, 2006, 29(4): 99-102.
[11]	杨震, 崔丙锋, 王亚丹, 丁炜. 一种改进的CCK调制解调方案与FPGA实现[J]. 北京邮电大学学报, 2004, 27(3): 33-37.
[12]	姜军,白春龙,张平,胡健栋. WCDMA系统中Turbo码译码器的FPGA实现——高效实现Log-MAP算法的硬件结构[J]. 北京邮电大学学报, 2002, 25(1): 22-26.

PFA在FPGA正则引擎上的设计和仿真

Design and Simulation of FPGA Engine for Regular Expressions Matching Based on PFA

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 12

编辑推荐

Metrics

本文评价