通信学报 ›› 2014, Vol. 35 ›› Issue (6): 47-55.doi: 10.3969/j.issn.1000-436x.2014.06.007

• 学术论文 • 上一篇    下一篇

基于两级存储的正则表达式匹配技术

陈曙晖,徐成成   

  1. 国防科学技术大学 计算机学院,湖南 长沙 410073
  • 出版日期:2014-06-25 发布日期:2017-06-29

Regular expression matching technology with two-stage memory

Shu-hui CHEN,Cheng-cheng XU   

  1. College of Computer, National University of Defense Technology, Changsha 410073, China
  • Online:2014-06-25 Published:2017-06-29

摘要:

为解决正则表达式匹配中内存需求与检测性能的矛盾,首次提出两级存储的匹配方案。将马尔可夫链理论应用于自动机,通过求解稳态向量,得到各状态被随机访问的概率。将高概率的状态表项配置在FPGA嵌入存储器中,低概率的状态表项配置在SRAM中。使用L7-filter规则集进行实验,吞吐量达到33 Gbit/s,匹配性能比将状态表完全存储在SRAM中提高了50倍。

关键词: 正则表达式, 马尔可夫链, 两级存储, 混合自动机

Abstract:

To solve the contradiction between the memory requirement and the inspection performance, a matching en-gine with two-stage memory was proposed for the first time. To deploy the state table to two-stage memory, theories of Markov chain was applied to the FSA. By computing the steady vector, the random access probabilities of each state could be obtained. Further, the states with higher probabilities were deployed in the embedded memory of FPGA, and the states with lower probabilities were deployed in SRAM. Rules in L7-filter were tested in simulation experiments, and the results show that our method can reach a throughput of 33 Gbit/s in large scale FSA, which is 50 times than that of ar-ranging the whole state table in SRAM.

Key words: regular expression, Markov chain, two-stage memory, hybrid FA

No Suggested Reading articles found!