计算机应用 ›› 2016, Vol. 36 ›› Issue (4): 927-930.DOI: 10.11772/j.issn.1001-9081.2016.04.0927

• 先进计算 • 上一篇    下一篇

基于FPGA改进电路的高性能正则表达式匹配算法

卓艳男1,2, 刘强1, 姜磊2, 戴琼2   

  1. 1. 东北石油大学 电子科学学院, 黑龙江 大庆 163318;
    2. 中国科学院 信息工程研究所, 北京 100093
  • 收稿日期:2015-09-11 修回日期:2015-10-27 出版日期:2016-04-10 发布日期:2016-04-08
  • 通讯作者: 姜磊
  • 作者简介:卓艳男(1991-),女,黑龙江大庆人,硕士研究生,主要研究方向:字符串处理、信息安全; 刘强(1980-),男,黑龙江大庆人,副教授,博士,主要研究方向:网络与信息安全、原子磁力仪; 姜磊(1984-),男,山东烟台人,助理研究员,博士,主要研究方向:网络与信息安全;戴琼(1975-),女,湖南张家界人,工程师,硕士,主要研究方向:网络与信息安全。
  • 基金资助:
    国家自然科学基金资助项目(51574087)。

High-performance regular expressions matching algorithm based on improved FPGA circuit

ZHUO Yannan1,2, LIU Qiang1, JIANG Lei2, DAI Qiong2   

  1. 1. College of Electronic Science, Northeast Petroleum University, Daqing Heilongjiang 163318, China;
    2. Institute of Computing Engineering, Chinese Academy of Sciences, Beijing 100093, China
  • Received:2015-09-11 Revised:2015-10-27 Online:2016-04-10 Published:2016-04-08
  • Supported by:
    This work is partially supported by the National Natural Science Foundation of China (51574087).

摘要: 针对正则表达式匹配过程中吞吐率低及逻辑资源占用数多的问题,提出一种完全基于现场可编程门阵列(FPGA)逻辑电路的改进确定有限自动机(DFA)匹配算法。首先,该算法统计了DFA中每个状态的大多数转移边都会集中指向相同状态特征的结果,随后根据正则表达式的转移矩阵为DFA的每个状态设置一条默认的转移边,最后进行逻辑电路简化处理,并采用L7-filter规则集进行实测。实验结果表明,改进后的DFA方案与非确定有限自动机(NFA)方案相比,有10%~60%的规则获得了更高的吞吐率,62%~87%的规则占用了更少的逻辑资源。

关键词: 正则表达式, 现场可编程门阵列, 模式匹配, 确定性有穷状态自动机

Abstract: Concerning the low throughput and too much logic resource usage in the process of regular expressions matching, an improved Deterministic Finite Automaton (DFA) regular expression matching algorithm fully based on Field-Programmable Gate Array (FPGA) logic circuit was designed. Firstly, the result that most transfer edges of each state in DFA would point intensively to the same state characteristics was counted; then an acquiescent transfer edge for each state setting in DFA was provided according to the transfer matrix of regular expressions; finally, simplified logical circuit was given, and measurement was conducted on the L7-filter rule set. The experimental result shows that, compared with the former Nondeterministic Finite Automaton (NFA) algorithm, 10%-60% rules get a higher throughput, and 62%-87% rules cost less logic resources.

Key words: regular expression, Field-Programmable Gate Array (FPGA), pattern matching, Deterministic Finite Automaton (DFA)

中图分类号: