一种无匹配时间损耗的DFA压缩算法的研究与实现

doi:10.3969/j.issn.0372-2112.2020.06.013

电子学报 ›› 2020, Vol. 48 ›› Issue (6): 1132-1139.DOI: 10.3969/j.issn.0372-2112.2020.06.013

一种无匹配时间损耗的DFA压缩算法的研究与实现

孙明乾, 乔庐峰, 陈庆华

陆军工程大学通信工程学院, 江苏南京 210000

收稿日期:2019-07-29 修回日期:2019-11-17 出版日期:2020-06-25
- 通讯作者:
- 乔庐峰
- 作者简介:
- 孙明乾 男,1995年出生于山东-城,现为陆军工程大学通信工程学院硕士研究生.主要研究方向为网络安全、高性能交换机和路由器相关技术. E-mail:sunmq1995@163.com
  陈庆华 男,1976年出生于湖北红安,现为陆军工程大学通信工程学院副教授.主要研究方向为交换技术和通信网络. E-mail:whitenny@126.com

Research and Implementation of a DFA Compression Algorithm with No Matching Time Loss

SUN Ming-qian, QIAO Lu-feng, CHEN Qing-hua

Institute of Communication Engineering, Army Engineering University of PLA, Nanjing, Jiangsu 210000, China

Received:2019-07-29 Revised:2019-11-17 Online:2020-06-25 Published:2020-06-25

摘要/Abstract

摘要： 高性能深度包检测系统使用确定型有穷自动机DFA（Deterministic Finite Automata）来执行数据包的检测过程.然而，DFA所带来的存储消耗问题使其难以适用于片内资源稀缺的FPGA.目前已存在多种算法着眼于解决DFA的空间爆炸问题，但是其在带来较好压缩率的同时，也在一定程度上影响到了系统的检测速度.本文提出了一种无匹配时间损耗的DFA压缩算法，并在此基础上，基于FPGA硬件平台，设计实现了单个DFA匹配引擎.实验测试结果表明，本文所设计的算法，在未影响整个系统匹配性能的前提下，可以实现10%~30%左右的压缩率.

关键词: 深度包检测, DFA, 存储压缩, FPGA

Abstract: Start-of-the-art deep packet inspection system uses deterministic finite automata (DFA) algorithms to perform regular expression matching.Nevertheless,the storage consumption problem caused by DFA make it difficult to apply to FPGA with scarce on-chip resources.At present,there are many algorithms aiming at solving the space explosion problem of DFA,but it affects the detection speed of the system to some extent while bringing better compression ratio.In this paper,a DFA compression algorithm without matching time loss is proposed.Based on the hardware platform of FPGA,a single DFA matching engine is designed and implemented.Experimental results show that the algorithm can achieve a compression rate of 10% to 30% without affecting the matching performance of the whole system.

Key words: deep packet inspection, DFA, storage compression, FPGA

中图分类号:

TP393.0

孙明乾, 乔庐峰, 陈庆华. 一种无匹配时间损耗的DFA压缩算法的研究与实现[J]. 电子学报, 2020, 48(6): 1132-1139.

SUN Ming-qian, QIAO Lu-feng, CHEN Qing-hua. Research and Implementation of a DFA Compression Algorithm with No Matching Time Loss[J]. Acta Electronica Sinica, 2020, 48(6): 1132-1139.

参考文献

[1] 付哲,李军.高性能正则表达式匹配算法综述[J].计算机工程与应用,2018,54(20):1-13. Fu Zhe,Li Jun.Survey on high performance regular expression matching algorithms[J].Computer Engineering and Applications,2018,54(20):1-13.(in Chinese)
[2] Xu C,Chen S,Su J,et al.A survey on regular expression matching for deep packet inspection:Applications,algorithms,and hardware platforms[J].IEEE Communications Surveys & Tutorials,2016,18(4):2991-3029.
[3] Kumar S,Dharmapurikar S,Yu F,et al.Algorithms to accelerate multiple regular expressions matching for deep packet inspection[A].ACM SIGCOMM 2006[C].Pisa,Italy:ACM,2006.339-350.
[4] Ficara D,Giordano S,Procissi G,et al.An improved DFA for fast regular expression matching[J].ACM SIGCOMM Computer Communication Review,2008,38(5):29-40.
[5] 邵翔宇,刘勤让,谭力波.基于规则模板的正则表达式分组算法[J].电子学报,2016,44(01):236-240. Shao Xiangyu,Liu Qinrang,Tan Libo. A regular expression grouping algorithm based on signature templates[J].Acta electronica Sinica,2016,44(01):236-240.(in Chinese)
[6] Orosz P,Tóthfalusi T,Varga P.FPGA-assisted DPI systems:100 Gbit/s and beyond[J].IEEE Communications Surveys & Tutorials,2018,21(2):2015-2040.
[7] Matousek D,Matousek J,Korenek J.High-speed regular expression matching with pipelined memory-based automata[A].FCCM 2018[C].Boulder,CO,USA:IEEE,2018.214-214.
[8] Su J,Chen S,Han B,et al.A 60GBps DPI prototype based on memory-centric FPGA[A].ACM SIGCOMM 2016[C].New York,NY,USA:ACM,2016.627-628.
[9] Liu A X,Torng E,Liu A X,et al.Overlay automata and algorithms for fast and scalable regular expression matching[J].IEEE/ACM Transactions on Networking (TON),2016,24(4):2400-2415.
[10] Zilberman N,Audzevich Y,Covington G A,et al.NetFPGA SUME:Toward 100 Gbps as research commodity[J].IEEE micro,2014,34(5):32-41.
[11] Marty Roesch,Joel Esler,Christine Council,et al.Snort[EB/OL].https://www.snort.org,2019.
[12] Vern Paxson.The bro network security monitor[EB/OL].https://www.bro.org,2019.
[13] Becchi M,Crowley P.A-dfa:A time-and space-efficient dfa compression algorithm for fast regular expression evaluation[J].ACM Transactions on Architecture and Code Optimization (TACO),2013,10(1):4.
[14] Becchi M,Cadambi S.Memory-efficient regular expression search using state merging[A].INFOCOM 2007[C].Barcelona,Spain:IEEE,2007.1064-1072.

[1]	袁海英, 曾智勇, 成君鹏. 面向灵活并行度的稀疏卷积神经网络加速器[J]. 电子学报, 2022, 50(8): 1811-1818.
[2]	陈晓杰, 李斌, 周清雷. RTL级可扩展高性能数据压缩方法实现[J]. 电子学报, 2022, 50(7): 1548-1557.
[3]	许皓文, 陆浩, 王振占. 高光谱微波辐射计系统中2GHz带宽数字谱仪设计[J]. 电子学报, 2022, 50(6): 1472-1479.
[4]	曲立国, 陈国豪, 胡俊, 陈鹏. 单次扫描连通域分析算法研究综述[J]. 电子学报, 2022, 50(6): 1521-1536.
[5]	王鹏, 邹彬, 刘金枝, 周丹阳. 基于Xilinx型FPGA系统单粒子效应评估方法研究[J]. 电子学报, 2022, 50(11): 2716-2721.
[6]	李斌, 齐延荣, 周清雷. 基于Winograd算法的目标检测加速器设计与优化[J]. 电子学报, 2022, 50(10): 2387-2397.
[7]	蔡莹, 朱翔, 王舰, 李昊远, 韩建伟. 基于激光注入的FPGA加密防护设计验证研究[J]. 电子学报, 2022, 50(10): 2381-2386.
[8]	张建民, 黎铁军, 马柯帆, 肖立权. 一种加速FPGA布线的不可满足子式求解算法[J]. 电子学报, 2021, 49(6): 1210-1216.
[9]	刘杰, 葛一凡, 田明, 马力强. 基于ZYNQ的可重构卷积神经网络加速器[J]. 电子学报, 2021, 49(4): 729-735.
[10]	蹇强, 张培勇, 王雪洁. 一种可配置的CNN协加速器的FPGA实现方法[J]. 电子学报, 2019, 47(7): 1525-1531.
[11]	刘公绪, 史凌峰, 辛东金. 基于FPGA的零误差大数阶乘算法的设计与实现[J]. 电子学报, 2019, 47(5): 1180-1184.
[12]	余乐, 李任伟, 王瑶, 李洋洋, 吴超, 贾瑞. 综述:面向SoC-FPGA的开源处理器[J]. 电子学报, 2018, 46(4): 992-1004.
[13]	薛一鸣, 陈鹞, 何宁宁, 胡彩娥, 王建平. 基于DFT滤波器组的低时延FPGA语音处理实现研究[J]. 电子学报, 2018, 46(3): 695-701.
[14]	孙悦, 王传伟, 康龙飞, 叶超, 张信. 基于CORDIC的精确快速幅相解算方法[J]. 电子学报, 2018, 46(12): 2978-2984.
[15]	唐然, 吴虹, 赵迎新, 穆巍炜, 徐锡燕, 马肖旭, 刘兵, 刘之洋. AIS多小区同频信号实时盲分离的FPGA设计[J]. 电子学报, 2017, 45(9): 2121-2126.

一种无匹配时间损耗的DFA压缩算法的研究与实现

Research and Implementation of a DFA Compression Algorithm with No Matching Time Loss

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics