Journal of Computer Applications ›› 2011, Vol. 31 ›› Issue (11): 2943-2946.DOI: 10.3724/SP.J.1087.2011.02943

• Computer software technology • Previous Articles     Next Articles

Survey on FPGA-based regular expressions matching algorithms

TANG Qiu1,2,JIANG Lei1,TAN Jian-long1,LIU Jin-gang1,2   

  1. 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



  1. 1. 首都师范大学 计算机科学联合研究院,北京 100037
    2. 中国科学院 计算技术研究所,北京 100190
  • 通讯作者: 唐球
  • 作者简介:唐球(1985-),男,湖南怀化人,硕士研究生,主要研究方向:网络安全、模式匹配;姜磊(1984-),男,山东烟台人,博士研究生,主要研究方向:网络安全、模式匹配;谭建龙(1974-),男,湖南长沙人,副研究员,博士,主要研究方向:自然语言处理、网络安全、模式匹配;刘金刚(1963-),男,辽宁铁岭人,教授,博士,主要研究方向:操作系统、智能接口。
  • 基金资助:

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

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

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

CLC Number: