用CAM实现OC-48线速字符串匹配的FPGA设计

互联网络蓬勃发展的今天，在网络入侵检测系统(NIDS)中，大部分的网络入侵检测设备几乎都依赖于一些基于特征码检测的字符串匹配算法，而字符串匹配算法的实现几乎都是由软件来实现的。目前应用比较成功的实例有，Snort软件使用字符串匹配算法对包含特征码的数据包进行检测。但是软件在内容字节流中进行搜索匹配时，需要在不同的处理单元中/内搬移或读取数据，这对于高速实现线速(OC-48)的检测系统来说，带来了很大的处理负荷。因此，如果采用硬件在数据包进入内存之前实现字符串匹配这一功能，将大大减少后端软件操作的处理负载。

基于IXP2400和FPGA的系统结构

IXP2400是英特尔公司推出的第二代网络处理器芯片，大量应用于宽带接入、防火墙、NIDS和负载均衡等系统中，它能满足OC-48网络线速的处理要求。玉衡铱达公司设计开发的骨干网络监控系统采用了IXP2400作为数据包主处理器，FPGA作为协处理器的硬件架构来实现，系统结构框图如图1所示。

如图1所示，系统外接了4个千兆光口，用以接收和发送数据包，它是整个监控系统和骨干网络的交际通道。光口数据包通过光模块进入PMC-Sierra公司的MAC3386芯片。接收数据包时，以太网帧数据包从千兆光口进入MAC3386，MAC3386对数据包进行解码后通过POS PHY3接口进入FPGA的FIFO单元，同时对进入FPGA的数据包进行模式字符串(Pattern-String)的匹配操作，处理后的数据包通过POS PHY3接口传输到IXP2400的MSF单元进行下一步的处理。发送时，FPGA只需要将IXP2400发送来的数据包通过POS PHY3接口传输给MAC3386，MAC3386对数据包进行编码后发送给光模块，光模块通过光口将数据包发送出去。IXP2400提供了一组数据总线来访问外部设备寄存器，IXP2400中称之为慢端口(Slow Port)。在这里，和FPGA相连的慢端口总线的一部分功能是作为写入FPGA的模式字符串通道。



图1：基于IXP2400和FPGA的系统结构示意图。   

POS PHY3是一种标准化的网络传输接口，接口数据传输速率为2.5Gbps，最大支持OC-48的传输速率接口。POS PHY3包括接收和发送两组32位总线，工作频率为104MHz，峰值吞吐率为3.2Gbps。支持2.5Gbps数据包的全双工操作。POS PHY3接口接收时序图如图2所示。


图2：POS PHY3接口接收逻辑时序图。   

该时序图描述了POS PHY3接口接收数据包时，数据流在POS PHY3总线上的传输方式和相关的控制信号关系。关于更进一步的详细描述可以参考POS PHY3接口标准文档。

系统采用时钟同步设计，在时钟上升沿进行数据采样，与FPGA相连的MAC3386、IXP2400的工作时钟由FPGA的DCM单元提供，可以保证数据采集的同步和稳定性。

CAM的设计

本设计中，由于要实现几路32B的模式字符串匹配，需要占用大量的RAM存储单元，同时还得为数据包缓存FIFO保留一定的存储单元，综合几家FPGA芯片厂商RAM的存储容量，决定选用赛灵思的Virtex2或Virtex Pro系列的FPGA芯片，因为对于相同规模的逻辑资源和寄存器资源来说， Virtex2或Virtex Pro系列的FPGA芯片的RAM容量比其他厂商都要多几倍。

FPGA中，与RAM存储单元相关的资源有三类：Block RAM、LUT、寄存器。这三类资源可以通过配置和粘合逻辑(Glue Logic)实现为不同类型和位宽大小的单端口/双端口RAM、ROM、CAM、FIFO等。FPGA中CAM的实现和配置非常灵活，CAM是实现模式字符串模式匹配的核心资源。

CAM即内容可寻址存储器。CAM这种存储器在其每个存储单元都包含了一个内嵌的比较逻辑，CAM基于内容寻址，通过硬件电路并行查找，实现快速匹配。一般来说在一个时钟周期内，写入CAM的待比较数据和其内部存储的每一个数据进行比较，并返回与端口数据相同的内部数据存储的地址和是否匹配的标识符。CAM的这种并行处理特性使得它在数据分选领域倍受青睐，被广泛应用在以太网网址搜寻、路由器中的地址交换表、高速数据处理等方面。

CAM对于高速的数据包模式字符串匹配查找操作来说，我们需要足够快的时间来完成，如果按照POS PHY3接口标准来说，必须保证寄存器建立(Setup)时间和CAM一次查找匹配时间之和小于1个周期10ns(一般情况下，FPGA设计中的保持(Hold Up)时间都可以满足，可以不予考虑)。根据FPGA芯片厂商数据手册提供的性能基准数据，我们配置CAM存储器选用的资源是Block RAM，配置的地址匹配类型选择的是非编码地址的多匹配方式(Multi Match Unencoded)，选用该项配置的CAM32_32完成一次匹配查找的操作时间为7ns左右，CAM32_32的配置大小是32位位宽，32个存储单元的地址深度。

对于POS PHY3的接口标准来说，数据传输操作周期为10ns，根据性能基准数据，我们因此除去寄存器的建立时间(＜2ns)，完成一次CAM匹配操作是完全可以和POS PHY3的接口标准相匹配的。根据数据包在POS PHY3接口的传输字节情况和实际设计需要，我们设计了一个CAM-heap来完成数据包的一路32B模式字符串的匹配操作。一个CAM-heap是由4个相同结构和配置的CAM32_32组成。CAM32_32是根据设计需要由自己配置定义的，其配置端口示意图如图3所示。


图3：CAM32_32端口示意图。   

模式字符串匹配实现过程

在NIDS检测系统中，先将协议解码后的域值与事先精心提取的攻击特征(规则)提取相应的字段，即模式字符串，然后从数据包包头和净载荷中进行查找匹配模式字符串，从中发现潜在的攻击行为。基于模式字符串的模式匹配是一项传统而成熟的入侵检测技术，提供了很高的准确性与广泛性。例如：目前网络应用中大部分使用了一种被称为智能隧道(Smart Tunnel)的技术，其特点是：服务端(或接收端)没有绑定任何固定的端口，客户端(或发起端)可以自行使用任意随机端口连接服务器，如P2P(点到点)应用(如各种P2P 下载工具、IP电话等)、IMS(实时消息系统 如MSN、Yahoo Pager)、网络在线游戏等。他们避开了防火墙、NIDS 产品。但是我们可以通过上层的协议识别和动态分析网络报文中包含的协议特征，发现其所在协议，提取相关的几段模式字符串，然后递交给模式字符串模式匹配引擎(FPGA)进行处理。

模式字符串匹配过程可以用纸带传输的过程来进行描述。假设一条纸带上附有数据包的全部内容(abcd..xyz0123456789...)，从包头sop字段ABCD开始一直到包结束eop字段，依次单个字符的向前流动，有一个匹配字符串xyz0123456789模板和该数据包进行匹配。当字符串的流入模板长度等于模式匹配字符串长度后就进行比较，数据包字符串每向前流进一个字符，模式匹配字符串就和数据包流入的字符串匹配一次，直到数据包最后的字符串流入模板，查找结束。如果字符串流入直至流出过程中，数据包中存在与模板字符串相同的序列，则说明匹配成功，否则没有模板匹配字符串。上例中，当流入模板的数据包字符串为xyz0123456789时，则指示该匹配成功。

MAC3386传输数据包给FPGA与纸带传输数据包类似，只不过在POS PHY3接口传输数据包时是每周期4字符/字节。FPGA进行模式字符串匹配时，在CAM-heap中每周期进行一次4个输入字符串的匹配操作。采用并行操作的原理，使用4个CAM模块一个周期进行4个字符/字节的匹配操作。

举例说明4个CAM单元的操作关系：假设输入数据包的某段内容是ABCD EFGH IJKL，要匹配的模式字符串是CD EFGH IJ，先将要匹配的模式字符串按照一定规则写入4个CAM单元中。数据包传输FPGA时第一个周期传入的是ABCD，第二个周期传入的是EFGH，第三个周期传入的是IJKL，在第二个周期到来后，开始进行字符串的匹配操作。

第二个周期进行匹配时，CAM1输入待匹配的字符串是ABCD(匹配失败)；CAM2输入待匹配的字符串是BCDE (匹配失败)；CAM3输入待匹配的字符串是CDEF(匹配成功)；CAM4输入待匹配的字符串是DEFG(匹配成功)，所有的匹配地址都保存于寄存器中。

第三个周期进行匹配时，CAM1输入待匹配的字符串是EFGH(匹配成功)；CAM2输入待匹配的字符串是FGHI(匹配成功)；CAM3输入待匹配的字符串是GHIJ(匹配成功)；CAM4输入待匹配的字符串是HIJL(匹配失败)。所有的匹配地址都保存于寄存器中。

因为我们匹配是8个字符的字符串，因此在第二个周期CAM3匹配成功后，到第三个周期CAM3的匹配成功，根据一定的逻辑关系和算匹配地址中匹配情况，就可以知道该字符串是否匹配成功。

我们把完成一个标准模式字符串匹配的4个CAM称之为一个CAM-heap，一个CAM-heap完成一路字符串的匹配查找。如果一个完整的数据包都流经模式字符串模板后，综合每周期保存匹配地址的寄存器的结果，就可以知道流入的字符串是否和模式字符串匹配。在进行模式字符串的匹配之前，需要先将模式字符串进行4字节的分段，不同段的4个字节写入不同的CAM单元和不同CAM单元的不同地址中。因为一个CAM-heap可以完成一路字符串的匹配查找，因此我们可以设计几个CAM-heap并行操作来完成几路模式字符串的匹配。匹配的模式字符串路数需要根据所选FPGA芯片RAM资源大小来决定。

FPGA的设计实现

模式字符串的FPGA输入是通过IXP2400的慢端口来写入的。在接收数据包之前，FPGA译码慢端口控制信号，通过IXP2400的慢端口接收模式字符串并写入FPGA的ROM中。要匹配的模式字符串接收完毕后，设置CAM写使能信号WE，将几路模式字符串按照一定格式分别写入不同的CAM单元中，然后进行下一步的字符串匹配操作。

接收的数据包按照数据流的先后顺序写入FPGA的FIFO中，先入先出。模式字符串匹配完成后，在FIFO出口端添加一个模式字符串的匹配标识头，来描述该数据包与模式字符串的匹配情况(包括与哪一个数据包匹配还是几个同时匹配，还是没有匹配)，该匹配标识头添加在数据包头，作为数据包内容的一部分发送给IXP2400。IXP2400在接收数据包时，对接收的数据包头进行解码，便可知道该数据包的模式字符串模式的匹配情况，以便进行下一步的动作。

从模式字符串匹配实现过程来看，数据包的流入过程和匹配过程是同时进行的，也就是模式字符串匹配过程的时间开销隐藏在数据包的接收阶段，接收完毕，模式字符串匹配结束。数据包只有在接收完毕后，才能决定发送什么样的数据包字符串匹配标识头，因此数据包在FPGA芯片中的延时为数据包的输入延时，按照网络传输最大数据包为1,514B计算，则数据包的最大延时为1514/4=379个周期，按照10ns一个周期计算延时为3.79um。

FPGA芯片的配置模式灵活，包括主串模式、从串模式、并行的SelectMap模式和边界扫描JTAG模式。经过配置后的FPGA芯片就可以正常工作了。但是基于SRAM的FPGA芯片掉电后，配置文件会自动丢失，因此需要为FPGA芯片配置一块闪存PROM来保存FPGA的下载文件，这样掉电后的FPGA以后也能正常工作。

本文小结

本文讲述了一种使用FPGA的CAM资源快速实现模式字符串的匹配查找方法，使用在线速(OC-48)的网络监控系统中，大大减少了后端软件操作的处理负载。系统设计时，选用的FPGA型号为Virtex2的XC2V2000-5，使用了FPGA中大量的Block RAM存储单元来构造CAM，采用了并行的设计思想，OC-48处理了3路模式字符串的模式匹配。经过工程实际测试，FPGA模块很好地实现了3路模式字符串的模式匹配功能，达到了系统的设计要求。