面向100G高速网络处理的正则表达式匹配关键技术研究

Regular expression matching is the key algorithm of network intrusion detection systems and deep packet inspection systems, and becomes research hotspot of network security in rencent years. With the development of 100Gbps networking, it is a urgent problem to provide the 100Gbps regular expression matching speed for network content security systems. This project plans to solve this problem from two aspects: regular expression algorithm optimization and hardware acceleration. In the aspect of algorithm optimization, we first research the space optimization technology of regular expression automata. We plan to design the automata split algorithm to solve the state-explosion problem of regular expression. We will design the DFA automata compression algorithm to solve the state information redundancy problem. Then, we plan to research the automata acceleration technoloty. By building state trasition tree dynamically, we plan to solve the exponential growth problem of multi-stride automata state trasitions, and increase the processing speed of regular expression matching engine. In the aspect of hardware acceleration, we first research the FPGA-based sparse matrix index algorithm to solve the storage problem of compressed aotumata on hardware. Then we plan to research state prediction algorithm to solve the quick matching problem of compressed automata. Our research is supposed to satisfy the 100Gbps performance requirement of regular expression matching system, and promote the development of networking content security technology.

正则表达式匹配是网络入侵检测技术和深度包检测技术的核心算法，是网络安全领域的研究热点。随着100G网络技术的日益实用化，如何满足100Gbps网络流量的线速匹配是正则表达式研究领域亟待解决的技术难点。本课题拟从算法优化和硬件加速两个方面进行研究。算法研究方面，首先研究自动机的空间优化算法，通过自动机分割和转移表压缩，解决自动机构造的状态爆炸问题和状态信息冗余问题，减少自动机的内存开销；然后研究自动机的速度优化算法，通过动态构造状态转移树，解决多步长自动机的转移边数量指数膨胀问题，提高正则表达式自动机处理输入字符的速度。硬件加速方面，首先研究稀疏矩阵在FPGA硬件上的快速索引技术，解决压缩自动机的高效存储问题；然后研究自动机的状态预测技术，解决压缩自动机在FPGA上的快速匹配问题。本课题的研究以期完成满足100Gbps性能需求的正则表达式匹配系统，促进网络内容安全技术的发展。

本课题研究100Gbps高速网络流量下的正则表达式匹配技术，从算法优化和硬件加速两个方面开展工作，取得成果如下。.设计了基于轮询调度策略的正则表达式匹配算法，思路是将串行匹配过程划分成两个可以并行的阶段来执行，即：1、匹配过程；2、确认过程。对于匹配过程，主要是采用预处理、数据轮询分发、多路径猜测方法来实现正则表达式匹配的并行化和流水化。对于确认过程，则按照轮询的串行方式逐一确认下一跳状态。实验结果表明，架构的吞吐率可达到140Gbps，是原始DFA的108倍，且内存消耗仅为原始DFA的1/10。.提出一种基于FPGA平台的域分割五元组匹配技术。在预处理阶段，通过将五元组规则分割成比特位级别的子域，并将子域转换成正则表达式DFA状态转移表。在查找阶段，将正则表达式匹配、五元组匹配以及硬件流水线技术相结合，完成五元组的高性能匹配要求。此外，针对空间开销大的问题，利用一种新的数据结构来表示规则-状态表，进一步减少空间资源的消耗。从实验结果来看，算法可以在最小数据包的情况下获得100G+的高性能吞吐率，而且平均每条规则仅仅消耗约10个字节，与经典的基于TCAM方法相比，获得6.79倍的功耗比。.在FPGA平台上，设计与实现100G高速网络数据包过滤专用卡的原型系统。基于所提出的关键成果，面向高速网络流量的安全过滤需求，在Virtex® UltraScale™ FPGA VCU108高性能板卡上设计与实现面向100G网络的数据包过滤专用卡原型系统。重点给出了数据包过滤专用卡原型系统的总体架构及各模块的功能描述。实验结果表明，过滤专用卡原型系统的吞吐率约为100Gbps，可实际满足于当前以太网100G链路上的内容安全扫描检测需求。