第8卷第6期 信息技术快报 Vol.8 No.6
Information Technology Letter Nov. 2010
1 深度数据包检测技术研究进展
黄昆，谢高岗
摘要 深度数据包检测是数据包处理关键技术之一，即采用特征匹配算法，将每个数据包内容与一组预定义
的特征进行匹配。随着网络带宽的迅猛增长以及特征规则日益增多，研究者提出了基于硬件的特征匹配算
法，即采用FPGA、ASIC和NP等专用嵌入式硬件来设计与实现特征匹配算法，提高DPI的匹配吞吐量。
但是，这些基于硬件的特征匹配算法面临高性能挑战，即如何满足线速数据包内容过滤的时间和空间需求。
本文从时间和空间等方面综述了基于硬件的字符串匹配算法和正则表达式匹配算法的研究进展，并展望了
未来DPI技术研究。
关键词 网络安全 深度数据包检测 特征匹配 字符串匹配 正则表达式
1 引言
随着网络技术的迅猛发展和广泛应用，互联网承载着越来越多的应用业务，人们对互联
网的依赖性日益增强。近年来，网络蠕虫、僵尸网络和计算机病毒等新型攻击层出不穷，入
侵和劫持大量的计算机系统，滥用计算机网络资源，并威胁和破坏互联网基础设施，已经造
成重大的经济损失和恶劣的社会影响[1-2]。因此，如何快速检测和阻止这些攻击成为当前网
络安全研究的热点问题。
网络入侵检测与防御系统(Network Intrusion Detection/Prevention System, NIDS/NIPS)是
网络安全防御的主要手段，即通过实时监测网络流量来检查和阻断网络攻击[1]。NIDS/NIPS
已广泛部署于从终端计算机、边缘路由器到核心路由器等网络构件。随着网络攻击日益复杂
化和安全漏洞不断发现，在未来五年内，全球NIDS/NIPS市场将从2007年的9.32亿美元增
长到21亿美元[3]。深度数据包检测(Deep Packet Inspection, DPI)是NIDS/NIPS的核心，不仅
检查数据包头部信息，而且检查数据包有效载荷(即数据包内容)。深度数据包检测（以下简
称DPI）主要采用特征匹配算法，即将每个数据包内容与一组预定义的特征规则进行匹配[4-5]。
DPI采用一组规则描述攻击特征，即每条规则至少包括数据包类型、特征字符串、搜索起始
位置、以及匹配后的响应操作等。例如，在Snort特征规则集中[6]，规则{alert icmp (msg:
“DDOS TFN Probe”; content: “1234”;)}是描述分布式拒绝服务TFN1探测攻击，即当互联网控
制报文协议（Internet Control Message Protocol, ICMP）数据包内容包含特征字符串“1234”
时，产生告警消息为“DDOS TFN Probe”。DPI是一种数据包内容过滤技术，不仅应用于
NIDS/NIPS，而且还应用于应用层数据包分类、对等传输（P2P）流量识别、基于上下文的
流量计费等[7-8]。
特征匹配是计算机科学中经典问题之一，广泛应用于信息检索、模式识别和网络安全等
领域。特征匹配算法可分为字符串匹配算法和正则表达式匹配算法。字符串匹配算法采用字
符串语言来描述简单的特征规则；而正则表达式匹配算法采用正则表达式语言来描述复杂的
特征规则。根据匹配方式，特征匹配算法又分为单模式和多模式匹配算法。单模式匹配算法
是指一次内容扫描仅匹配一个特征串，例如克努斯-莫里斯-普拉特（Knuth-Morris-Pratt）算
法[9]和博耶-摩尔（Boyer-Moore）算法[10]等。当规则集包含s个特征串时，单模式匹配算法
1 Tribe Flood Network 深度数据包检测技术研究进展
2 需要重复匹配s次，存在匹配效率低等问题。多模式匹配算法是采用确定型有限自动机
(Deterministic Finite Automaton，DFA)来表示一组特征串，一次内容扫描可匹配多个特征串，
例如阿霍-克拉斯科（Aho-Corasick）算法[11]、科曼兹-沃尔特（Commentz-Walter）算法[12]
以及阿霍-克拉斯科和博耶-摩尔（Aho-Corasick Boyer-Moore）联合算法[13]等。
从1975年开始，过去近30多年的DPI技术研究主要关注基于软件的特征匹配算法，
即在单核CPU的软件平台上设计与实现特征匹配的算法，从而提高DPI的匹配速率。但是，
随着网络带宽和业务流量的迅猛增长以及特征规则日益增多，基于软件的特征匹配算法存在
匹配吞吐量低等问题，难以满足10-40Gbps线速数据包处理的高性能需求。近年来，研究者
提出了多种基于硬件的特征匹配算法[14-18]，即采用专用嵌入式硬件，例如现场可编程门阵列
（简称门阵列）、专用集成电路等，设计与实现特征匹配算法，从而提高DPI的匹配吞吐量。
例如，基于门阵列的特征匹配算法吞吐量可达10Gbps，支持特征规则集的动态更新，但是
存在重编译和重构时间长等缺点；基于专用集成电路的特征匹配算法吞吐量可达20Gbps，
不支持特征规则集的动态更新。这些基于硬件的特征匹配算法面临嵌入式存储器空间受限等
挑战，即确定型有限自动机（以下简称确定自动机）存储空间需求大，难以在片上高速存储
器中存储和查找整个确定自动机，而需要频繁访问片外低速存储器，导致DPI的匹配性能
降低。例如，Xilinx Vertex-5 门阵列[19]仅提供约10Mb的片上SRAM2，而当前Snort特征规
则集对应的确定自动机存储空间开销约为100MB，无法存储在片上SRAM中，难以实现线
速数据包处理。TCAM3和多核处理器(Multi-Core Processor)等硬件技术的不断发展，为DPI
的性能提升提供了新的机遇与挑战。TCAM可以在一个时钟周期内查找出与内容匹配的存
储索引，提供高速且确定的内容查找，用于加速DPI的匹配性能；多核处理器是在一块芯
片上集成多个CPU核，具有高速灵活的并行计算能力，用于提升DPI的匹配性能。因此，
如何设计与实现基于硬件的高性能特征匹配算法成为线速DPI技术研究的热点问题，已吸
引越来越多研究者的关注。
本文综述了DPI技术研究进展，特别是基于硬件的特征匹配算法设计与实现。第2节
介绍了DPI的高性能挑战，并指出了DPI技术的可伸缩性需求；第3节和第4节分别详细
讨论了几种基于硬件的字符串匹配算法和正则表达式匹配算法。最后，第5节总结全文，并
展望了未来DPI技术研究的关键问题。
2 DPI技术的高性能挑战
DPI是计算密集型操作，主要应用于高速路由器的关键数据路径上，需要检查高速海量
数据包，并与成千上万条规则进行特征匹配。近年来，互联网骨干链路带宽从2.5Gbps增至
10-40Gbps，以太网接口从10GbE增至100GbE；新型高质量网络应用，例如流媒体应用
PPLive、YouTube，内容发布应用Facebook、Twitter等，产生海量的业务内容和网络流量。
为了适应高速海量数据包处理，满足线速数据包处理的时间和空间需求，并提升可伸缩性，
DPI技术面临高性能挑战[20]：
1. 随着网络攻击、业务行为等日益复杂化，特征规则条数不断增多且特征描述越来越
复杂，导致DPI的存储空间开销日益增大。例如，Snort特征规则条数从2003年的
3166增至2009年的15047。Snort特征规则集的确定自动机存储空间需求超过75MB，
而门阵列和专用集成电路等嵌入式硬件的片上高速存储器仅约为10Mb，因而特征匹
配的整个确定自动机难以存储在片上高速存储器中，需要存储在片外低速存储器，
2 Static Random Access Memory，静态随机存储器
3 Ternary Content Addressable Memory, 三态内容可寻址存储器 第8卷第6期 信息技术快报 Vol.8 No.6
Information Technology Letter Nov. 2010
3 从而限制了DPI的匹配吞吐量。因此，基于硬件的DPI技术迫切要求存储高效特征
匹配算法，在片上高速存储器中存储和查找确定自动机，不仅满足特征规则集的可
伸缩性需求，而且提高DPI的匹配性能。
2. 为了实现未来100Gbps线速数据包处理，基于硬件的DPI技术要求利用片上高速存
储器、硬件并行计算能力等来提高特征匹配的吞吐量。门阵列和专用集成电路等嵌
入式硬件通常采用层次化存储器体系结构，即由片上高速存储器和片外低速存储器
构成。片上存储器支持快速查找，例如片上SRAM的访问时间为1-2ns，但是其存储
空间小；片外存储器的存储空间大，但是其查找速度慢，例如片外DRAM4的访问时
间为60ns。面向硬件实现的DPI技术面临如何利用片上高速存储器来尽量减少片外
低速存储器访问次数，从而实现线速DPI。专用嵌入式硬件虽然支持并行处理，但是
存在编程设计复杂、灵活性差和升级成本高等缺点。Intel Xeon CPU、Cavium OCTEON
和Nivida GPGPU等多核处理器具有强大并行计算能力和灵活可编程等优点，为线速
DPI实现带来新的机遇与挑战。线速DPI技术面临如何利用多核处理器平台的并行处
理能力，设计与实现时空高效特征匹配算法，从而加速DPI的匹配性能的挑战。
总之，DPI的可伸缩性需求主要体现在存储空间开销和匹配吞吐量等两方面[21]，即减少
特征匹配算法的存储空间开销，并提高其匹配速率，从而实现高性能DPI。因此，当前的
DPI技术研究主要是从时间和空间等方面来设计与实现基于硬件的特征匹配算法，从而满足
DPI的高性能需求。本文是以时空开销为视角，探讨基于硬件的字符串匹配算法和正则表达
式算法等研究进展，并展望未来DPI技术研究的关键问题。
3 基于硬件的字符串匹配算法
基于硬件的字符串匹配算法可分为：存储高效字符串匹配算法、多字符字符串匹配算法
和并行字符串匹配算法。如表1所示，存储高效算法是研究如何通过减少冗余迁移边来压缩
确定自动机存储空间开销，例如基于B-FSM5[22]和基于CDFA6[23]的阿霍-克拉斯科算法；多
表1 基于硬件的字符串匹配算法分类
存储高效算法多字符算法 并行算法 B-FSM √
CDFA √
JACK-NFA √
TDP-DFA √ 压缩DFA √
变步长DFA √
比特拆分DFA √
首尾分割DFA √
并行布隆过滤器 √
字符算法是研究如何通过构建一次处理多个字符的确定自动机来提高其匹配吞吐量，例如基
于JACK-NFA7[24]、基于TDP-DFA8[25]、基于压缩的确定型有限自动机[26]和基于变步长的确
定型有限自动机[27]的阿霍-克拉斯科算法；并行算法是研究如何通过并行化字符串匹配操作
4 Dynamic Random Access Memory，动态随机存储器
5 BART-based Finite State Machine, BART：Balanced Routing Table, 一种可编程状态机技术
6 Cached Deterministic Finite Automaton, 具有缓存的确定型有限自动机
7 Jump-ahead Aho-CorasicK NFA，NFA：Non-deterministic Finite Automaton，非确定型有限自动机
