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

模式字符串匹配实现过程

在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以后也能正常工作。