(19)中华人民共和国国家知识产权局
(12)发明专利说明书
(10)申请公布号 CN 110324204 A
(43)申请公布日 2019.10.11
(21)申请号 CN201910583091.9
(22)申请日 2019.07.01
(71)申请人 中国人民解放军陆军工程大学
    地址 210007 江苏省南京市秦淮区后标营路88号
(72)发明人 孙明乾 乔庐峰 陈庆华 陆雅丽 李礼思洋 赵彤
(74)专利代理机构 南京理工大学专利中心
正则匹配时间    代理人 薛云燕
(51)Int.CI
     
                                                                  权利要求说明书 说明书 幅图
(54)发明名称
      一种在FPGA中实现的高速正则表达式匹配引擎及方法
(57)摘要
      本发明公开了一种在FPGA中实现的高速正则表达式匹配引擎及方法。该匹配引擎包括DFA表项分发模块、数据包预处理模块、FIFO模块、并行匹配模块、存储器模块及控制器，其中DFA表项分发模块位于软件层，数据包预处理模块、FIFO模块、并行匹配模块、存储器模块及控制器位于硬件层。方法为：将整个数据包的匹配过程划分为并行匹配部分和串行匹配部分，由此形成一种串‑并结合的匹配方式：对于数据包中的大部分字段位置采用并行匹配，对于小部分字段位置采用串行匹配。同时，对于DFA表项的存储，采用寄存器+片内RAM+片外DDR3的三级存储结构。本发明提升了数据包的匹配速度，降低了FPGA片内的资源消耗。
法律状态
法律状态公告日
法律状态信息
法律状态
权 利 要 求 说 明 书
1.一种在FPGA中实现的高速正则表达式匹配引擎,其特征在于,包括DFA表项分发模块、数据包预处理模块、FIFO模块、并行匹配模块、存储器模块及控制器,其中DFA表项分发模块位于软件层,数据包预处理模块、FIFO模块、并行匹配模块、存储器模块及控制器位于硬件层;
所述DFA表项分发模块,依据每一表项的访问频率,将不同的表项存储至不同的存储器中,包括片内寄存器、片内RAM和片外DDR3;
所述数据包预处理模块,对输入至系统的数据包进行分割,划分为N*8bits一组,其中N为后续可同时并行匹配的字符数量,存入至FIFO模块中;
所述FIFO模块,用于缓存已分割完毕的数据包,供控制器读取;
所述并行匹配模块,接收来自控制器的并行匹配请求,依据寄存器文件中存储的状态表项信息同时对N个字符进行并行匹配,此部分电路基于组合逻辑实现,产生的并行匹配结果送至控制器做进一步分析;
所述存储器模块,用于存储DFA表项;
所述控制器,用于控制整个匹配引擎的运转。
2.根据权利要求1所述的在FPGA中实现的高速正则表达式匹配引擎,其特征在于,所述DFA表项分发模块位于软件层,DFA状态表项在CPU的控制下,依次被写入存储器内。
3.根据权利要求1所述的在FPGA中实现的高速正则表达式匹配引擎,其特征在于,所述FIFO模块及存储器模块中所包含的片内RAM,使用FPGA内部自带的IP核进行设计与实现。
4.一种在FPGA中实现的高速正则表达式匹配方法,其特征在于,包括以下步骤:
步骤1、从FIFO中读出待检测数据,依据内部寄存器记录的当前状态,来决定将要对这些数据采取的操作;
步骤2、若当前状态满足并行匹配的要求,则将此N*8bits数据送至并行匹配模块所对应的组合逻辑电路中,针对匹配失败的部分字符进行串行匹配,最后更新内部寄存器,读取下一组数据;
步骤3、若当前状态不满足并行匹配要求,则从数据最低字节所对应的第一个字符开始,依次进行串行匹配,每次串行匹配之后判断是否满足并行匹配要求,若满足,则将剩下的数据送至并行匹配模块进行并行匹配;否则继续进行串行匹配。
5.根据权利要求4所述的在FPGA中实现的高速正则表达式匹配方法,其特征在于,步骤3中所述的将剩下的数据送至并行匹配模块进行并行匹配,具体如下:
步骤3.1、从寄存器文件中提取出关键状态KS的信息,关键状态具有两个特点:一个是KS的默认转移,即占比最高的转移是自身;另一个是KS附近大量状态的默认转移也是KS;
步骤3.2、将n个并行输入字符分别送至n个并行执行的解码器进行字符解析,依据字符解析结果查询KS寄存器文件,即储存有KS的所有转移的相应地址,从而得到n个数据查询结果,分别与待匹配的n个字符对应,表示当系统处于关键状态时,输入此特定字符得到的下一跳状态;
步骤3.3、将步骤3.2产生的n个结果送至比较器,与KS的状态号进行相等比较,然后将n个比较结果拼成一个n位数据;
步骤3.4、对步骤3.3中的n位匹配结果进行二次匹配,生成了一个64位的并行匹配结果,送至控制器做进一步分
析。
说  明  书
<p>技术领域
本发明涉及电子电路技术领域,特别是一种在FPGA中实现的高速正则表达式匹配引擎及方法。
背景技术
高性能深度包检测(DPI)系统需要使用正则表达式匹配引擎来执行数据包的检测操作。在利用正则表达式进行深度包检测之前,需要先将其转换为确定型有穷自动机(DFA),生成DFA状态转移表,进而写入至匹配引擎内部的存储空间,正则表达式匹配引擎利用其内部存储的DFA状态信息完成整个数据包的检测过程。
传统的基于正则表达式的数据包检测是一个串行迭代的匹配过程,在这个过程中,只有在当前状态及当前字符都确定的情况下,才能计算出下一跳状态进而完成一次跳转。这种方法的优点是整个匹配引擎的设计具有一定的简洁性,只需简单地控制DFA表项的读取操作即可完成整个数据包的匹配过程,但同时该方法在一个时间单位内只能处理一个字符,这在一定程度上限制了其匹配速度的提升。目前,已有学者提出了多步DFA,其具体
实现思路是将数据包的串行匹配过程转换为并行匹配过程,通过将原始DFA迭代n次,产生N步DFA,在一个时间单位内可并行处理n个字符。N步DFA的存储消耗为原始DFA的n次方,利用FPGA等硬件平台实现该算法时,其所带来的存储资源消耗会瞬间耗尽FPGA的片内资源,倘若使用片外大容量存储器如DDR对N步DFA的表项进行存储的话,片外存储器较长的访问延迟又在一定程度上限制了整个系统的吞吐量。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。