---
title: Ultrascan高性能正则表达式匹配库
description: "Ultrascan是开源的高性能正则表达式匹配库，鲲鹏BoostKit平台做了ARM指令集适配和优化，并针对实际数据分流业务规则集的弱点做了算法革新（例如短规则旁路混合模型）。"
url: https://www.hikunpeng.com/document/detail/zh/kunpengddk/twp/kunpeng_datadistribution_03_0007.html
sourcePath: /source/zh/kunpengddk/twp/kunpeng_datadistribution_03_0007.html
indexId: 2f86235cd3b13a666cb84273fefbc3cdf3a872217d33a35b5b530ce3f4179eb863
---
# Ultrascan高性能正则表达式匹配库

Ultrascan是开源的高性能正则表达式匹配库，鲲鹏BoostKit平台做了ARM指令集适配和优化，并针对实际数据分流业务规则集的弱点做了算法革新（例如短规则旁路混合模型）。


Ultrascan的工作流程有两个主要时期：编译期和运行期。编译期将一条或者一组规则编译成一个只读数据库；运行期不需要读入规则，而是借助编译好的数据库进行匹配。

Ultrascan在十万以下常规数量规则集匹配场景是世界最快，被广泛应用于应用分类、IDP、WAF（Web Application Firewall）等场景。在以Suricata为代表的典型开源方案中，其检测引擎为第一计算热点，集成和优化Ultrascan可有效提升数据分流业务端到端性能。

关键技术：

高速预过滤算法；多模式匹配算法；自动机算法。

适用场景：

信息安全数据分流，运营商数据精细分流，安平数据分流，IDPS，WAF，大模型应用防火墙等。

#### 短规则旁路技术

存在短规则的规则集会导致Ultrascan规则匹配陷入性能瓶颈。客户现网部署的规则集通常都存在短规则瓶颈，例如人为写入了短规则，又或是正则规则中包含了短字符串被图分割算法切割成短规则。在短规则进入多模匹配后，短规则匹配率高，频繁打断前端快速指令流水，触发相对较慢的后端精确校验；短规则与常规规则混杂处理时，大量冗余操作导致成为性能瓶颈。

华为Ultrascan提供了短规则旁路混合模型，对包含短规则的规则集合能大幅提高匹配性能。短规则旁路混合模型将导致性能瓶颈的短规则从常规规则中分离，用极少量向量指令实现快速旁路算法，消除冗余操作，保持主算法的指令流水并行效率，大幅提升整体匹配性能。

研究表明，Suricata开源规则集里表现最差的子集，去除八条单字节规则后，整体匹配性能上升50%，原因主要是短规则参与了太多不必要的向量计算和精确校验。最近版本交付的短规则旁路混合模型将规则集里的短规则用TBL查表指令优化的高速旁路算法绕过主算法流程，用20%的额外开销处理短规则，最终能够取得整体30%+的性能提升。


高速的短规则旁路shuf-and算法是混合模型高效处理规则集里短规则瓶颈的关键。

- 单字节短规则
  考虑一个含有8条1字节规则的集合的实例，用以描述短规则旁路shuf-and算法。假设8条短规则分别是{A, B, C, D, c, d, e, f}，先给每条规则分配一个组，分别用不同的位来表达，则规则的组ID分别为{0x1, 0x2, 0x4, 0x8, 0x10, 0x20, 0x40, 0x80}。将整个ASCII表表达为16x16的形式，高4位值相同的字符位于同一行，低4位值相同的字符位于同一列。再向每个规则对应的表项内填入其组ID，如下图所示。

  将表内每行的数值按位或，得到上图中第二列所示向量，记为maskHigh；将每列的数值按位或，得到上图中第二行所示向量，记为maskLow。则maskLow和maskHigh如下图所示。

  做好上述准备后，在后续匹配过程中，maskLow和maskHigh作为混洗操作的源向量参与运算，而待匹配数据作为控制向量参与运算。

  假设待匹配数据中一个16字节数据块为AgggDd3366666666，只需要5条指令，即可得到其中所有位置的匹配结果。首先将数据块中每字节的低4位和高4位分别表达为两个控制向量，这需要一个AND操作擦除每字节高4位内容，和一个SHIFT操作将每字节高4位内容移到低4位上。得到两个向量inputLow和inputHigh。

  然后做两次混洗操作，得到结果shufLow和shufHigh如下。

  将shufLow和shufHigh做AND，得到的就是每个位置的匹配结果。

  可以清晰地看出，在偏移量0、4、5分别匹配上了组0x01(A)、组0x08(D)、组0x20(d)。


- 2～4字节短规则
  Ultrascan短规则旁路引擎的2-4字节短规则旁路算法最多能够处理8条2～4字节规则，用不同的位来表达每个规则，编码为1字节。下面用一条3字节规则来举例说明匹配算法的设计。

  假设有一条3字节规则ddy，将每字节拆成高四位和低四位，分别填表，一共6行16列，每个单元为一字节，如下图所示：

  每位可表达1个规则的信息，本例中只有1个规则，每单元只利用1位即可表达。表中每行对应规则中每个半字节，填0表示半字节命中，填1表示不命中。

  上图展示了一段16字节内容yourdaddyisbravo进行3字节规则旁路算法匹配的实例。将该内容通过LDR指令读入128位向量寄存器，将每字节拆成低4位和高4位，分别对表的0/2/4行和1/3/5行做TBL并行查表得到6行结果，然后分别对0/1行、2/3行和4/5行的结果做OR得到3行，表达各位置对规则中3个字节的匹配结果；再将字节1的结果左移2字节，字节2的结果左移1字节，与字节3的结果一起做OR，即可得到精确的序列匹配结果。本例中在位置8匹配到规则ddy。


#### 假阳性阻断技术

客户现网部署的规则集有时存在少量含特殊片段的规则，导致多模匹配算法报告的假阳性过多，触发大量的解释器调用和低效的长规则校验，而最终无一真实匹配。大量无谓的解释器调用成为热点，多模匹配失去了应有的预过滤能力。

某真实客户现网流量环境中，核心规则集的极少量规则包含坏字符串片段导致多模匹配产生五百万余命中，解释器调用和完整长规则校验成为计算特点，而最终没有真实匹配。分析表明，去除这几条规则后原计算热点消失，匹配性能提升20倍。

图1 假阳性阻断示意图

Ultrascan提供了假阳性阻断模型，对包含坏字符串片段的规则集合能大幅提高匹配性能。


假阳性阻断模型通过在编译期控制图分割算法的行为，对NFA图上的候选“割”进行坏片段检查，拦截使用坏片段的图分割，避免坏片段进入多模匹配，从而减少坏片段产生的假命中，有效过滤无意义的校验；同时，运行期用向量指令优化解释器内的低效长规则校验算法。双管齐下，大幅提升整体性能。


#### 通用字节码技术

在复杂的信息安全与 DPI（深度报文检测）应用中，设备异构化与分布式部署已成为常态。传统模式下，规则编译生成的字节码往往深度绑定特定的硬件微架构（如x86的指令集或ARM的架构特性），导致在混合架构网络中需要针对不同设备重复编译，极大地增加了规则分发的复杂度和运维成本。

Universal Database（通用数据库） 功能应运而生。它实现了编译产物与底层硬件架构的解耦，通过标准化的字节码封装与自适应加载技术，使得在x86或ARM平台上生成的编译数据库能够实现跨平台兼容运行。该功能的引入，主要解决了多代际、多架构设备共存场景下的部署难题：1. 用户仅需在中心控制端完成一次规则编译，即可将生成的通用字节码无缝下发至全网不同架构的边缘节点；2. 消除了为不同架构维护多套规则库的冗余工作，显著降低了存储与版本管理的成本；3. 缩短了规则从更新到生效的路径，确保了在异构分布式环境下 DPI 业务的一致性与高效性。

图2 通用字节码技术示意图

如上图所示，在编译期，为每个预设平台生成优化的字节码，并将这些字节码打包到同一个数据库文件中。在编译期通过在数据库文件内设置偏移量字段记录x86和arm平台的两份字节码在内存中的相对位置，在运行期通过首先检测当前平台的CPU特性，然后从数据库中选择平台支持字节码并加载执行。这种设计实现了“一次编译，多处运行”的跨平台部署能力，同时通过分层存储优化，提升方案设计通用性。