如何提高大规模正则匹配的效能

背景

日常工作中会大量应用正则表达式，用正则表达式去定义规则，然后去匹配数据。这里先看两个安全场景下的正则应用需求：

场景 1，FTP 账号被成功暴力破解后数据遭窃取

•  数据源：FTP 服务器日志

•  关联逻辑：针对特定账号暴力破解，然后利用该特定账号登录成功，之后利用该特定账号下载大量文件

•  告警内容：FTP 账号 ${user_name}被成功暴力破解后窃取数据

•  告警级别：高危

场景 1 中，正则表达式用于在日志中匹配多次账户登录的行为上。

场景 2，Deep packet inspection (DPI) ，例如过滤网络威胁和违反安全策略的流量等

•         数据源：网络数据包

•         检测规则条件：数据命中规则集

场景 2 中，正则表达式用于时间序列上的多个数据包之间的安全检测。

其实，场景 1 中只列举了 FTP 被攻击的一种方式，FTP 攻击还有很多其他手段，所以检测 FTP 被攻击的正则匹配场景的另一个特征就是整个规则集可能很大；场景 2 中，利用已知的入侵行为构建模式集合，通过检测网络数据包，发现是否存在不符合安全策略的行为或被攻击的迹象，这需要对数据包的载荷部分进行检测，要求匹配的速度非常快，否则将会影响用户体验。

另一方面，这里用到的正则与传统用法又不太一样，对正则的传统用法是，给定一个文本，用一个或少数几个正则规则，去匹配文本，找出文本中匹配的数据。而现在面对的问题，首先是规则的数量大，上千上万或者超过十万的规则集，如果仍然采用之前的做法，用|分割，或者外层用循环去匹配，那么处理的时间将很长，对资源的消耗也很大，基本不可接受；其次在匹配的时候，待匹配的数据不是一个完整的整体，比如说网络数据包，是一个一个接收的，这是一个流式的形式，传统的正则处理引擎不能很好的处理流式数据，需要缓存一批数据去匹配，这样匹配就不够及时，而且目前正则处理有个很大的问题，如果正则表达式写的不好，那么匹配会很慢。所以，需要一个解决方案来应对以下这些挑战：

•  规则数量多

•  匹配速度要快

•  支持流式数据

•  资源消耗不能太大

Hyperscan 算子介绍

针对上述正则匹配中遇到的挑战，经过调研和对比测试市面上的主流正则匹配引擎，我们最终选择了 Hyperscan。

Hyperscan 是 Intel 开源的高性能正则表达式匹配库，提供了 C 语言 API，目前已经在很多商业项目和开源项目中得到应用。

Hyperscan 具备这些特性：

•  支持大部分 PCRE 正则语法（如果使用 Chimera 库，那将支持所有语法）

•  支持流式匹配

•  支持多模匹配

•  采用特定指令集加速匹配

•  易于扩展

•  内部多种引擎结合

Hyperscan 在设计之初就是为了更好的处理流式匹配和多模匹配，对流模式的支持极大的方便了正则用户，不再需要用户去维护接收到的数据，无需缓存数据；多模匹配允许把多个正则表达式传入并在同一时间进行匹配。

因为需要特定的指令集，所以 Hyperscan 对 CPU 有要求，如下图：

CPU 最低要支持 SSSE3 指令集，最下面一行的指令集能加速匹配

和大多数正则引擎类似，Hyperscan 也包括编译和匹配阶段，编译是把正则表达式解析然后构建成内部需要的 database，后续可以多次使用这个 database 去匹配；如果是多模匹配，编译时每个正则表达式需要有一个唯一的标识 id，id 在匹配的时候会用到。编译过程如下图所示：

匹配的时候 Hyperscan 默认会返回所有命中的结果，这点不像有些正则引擎，指定贪婪的时候返回贪婪的匹配结果，指定懒惰的时候返回懒惰的结果。匹配时如果有命中，那么会以回调函数的形式通知用户在哪个位置命中了哪个正则表达式 id。匹配过程如下图所示：

Hyperscan 的缺点是只能是单机执行，没有分布式能力，其可以解决延迟的问题，但无法解决吞吐的问题，解决吞吐问题，可以依靠主流实时计算框架 Flink。Flink 是一个在无界和有界数据流上进行状态计算的框架和分布式处理引擎。无界就是有开始但没有结束的数据，无界的数据流计算即流式计算，有界就是有开始有结束的数据，有界的数据流计算即批处理。

Flink 可以用于很多的计算场景中，这里列举了 3 个，Flink 可以处理事件驱动的程序，除了简单事件，Flink 还提供了 CEP 库可以处理复杂事件；Flink 还可以作为数据管道，做一些数据清洗筛选、转换等操作，把数据从一个存储系统转移到另一个系统；Flink 可以做流或批式数据的分析、指标计算，用于大屏展示等。Flink 已经成为业界公认的流式处理的第一选择。

把正则匹配引擎整合到 Flink 中，借助 Flink 强大的分布式能力，强强联合，那么将会发挥更大威力。所以提供了这样的解决方案，如下图所示：

该解决方案实现了一个自定义的 UDF 算子，算子支持指定只匹配输入数据中的某几个字段，算子的输出是待匹配的字段文本，匹配最终状态，包括命中，不命中，错误，超时四种状态，如果是命中的状态，那么还会返回匹配中的正则表达式的 id，输出还包括输入原始数据，如果有后续处理，这样不受影响；为了进一步方便用户使用，扩展了一个新的 datastream，称之为 Hyperscanstream，它把算子封装进了进去，用户在使用时只需要把 datastream 转换为 Hyperscanstream，然后通过调用一个方法就可以使用正则的算子了。整个解决方案以一个独立的 jar 包提供给用户，这样可以保持原来编写 Flink 作业的习惯，并且与 Flink 的核心框架解耦。

数据流转的过程是这样，数据源读取到一条记录后交给下游的 Hyperscan 算子，Hyperscan 算子把数据交给 Hyperscan 子进程，子进程匹配完成后把结果返回给 Hyperscan 算子，然后 Hyperscan 算子把原始记录和匹配的结果传递给后续算子。

算子使用说明

私有化部署

针对私有化部署场景，用法如下，用户首先需要去编辑正则表达式文件，然后用工具把正则表达式编译为 database 并且序列化为本地文件，如果部署的环境中有 HDFS，那么可以把序列化后的文件上传至 HDFS，如果没有那就不用上传，然后开发 Flink 作业，引用序列化的文件去匹配数据。

为什么要有工具编译并序列化这一步呢，编辑完正则表达式，直接在 Flink 作业中使用不行吗？前面说了，Hyperscan 执行包括编译和匹配阶段，如果作业中只引用正则表达式，假设作业设置了并行度为 5，那么每个 task 都需要编译一次，一共需要编译 5 次，浪费资源；而且编译在 hyperscan 中是个相对缓慢的动作，所以把编译过程单独出来也为了加速 flink 作业在尽快执行。编译提前进行也有利于提前知道正则表达式是否有语法错误，或者不支持的情况，而不是作业启动后才知道。

私有化部署时，hyperscan 相关依赖程序会提供给用户，依赖程序通过全静态编译而来所以无需再添加依赖，只需机器支持需要的指令集即可。

公司内部使用

公司内部使用相对简单，用户可以在奇麟平台编辑正则表达式，或者把编写好的正则表达式文件上传到奇麟平台，奇麟平台负责把正则表达式编译为 database 上传到 HDFS，然后开发作业进行匹配。

使用示例

假设现在要匹配的是 HTTP 报文中的 Host 字段和 Referer 字段，如下图所示：

代码示例如下图：

整个逻辑分为四步，第一步要从数据源构建输入流，第二步把输入流转换为 Hyperscanstream，第三步调用 hyperscan 方法进而使用 Hyperscan 算子，在第一个参数 HyperscanFunction 中指定要匹配的是 Host 和 Referer 字段，第四步使用匹配返回的结果，返回的结果是 Tuple2 对象，其中第一个字段 Event 是原始记录，在本例中就是整个 HTTP 报文，第二个字段是 HyperScanRecord 组成的 List，HyperScanRecord 类中包括匹配的字段，例如本例中 Host 或 Referer，匹配命中的正则表达式 id（如果匹配命中的话）和匹配的最终状态。

使用 1 万条规则集以及不同大小的待匹配样本经过测试，方案达到了期望的性能，测试结果如下图，

使用 Hyperscan 算子的一些建议，如下图：

前面提到，在不使用 Chimera 库时，Hyperscan 有部分 PCRE 语法不支持的情况，在使用时要注意，下图列举了不支持的语法（使用 Chimera 库将会影响匹配性能）

未来展望

一方面，目前 Hyperscan 算子在安全、威胁感知的场景中已经得到运用，但希望能在更多场景中进行检验，理论上在所有正则匹配的场景中都能使用，比方说文本审核、内容提取等。

另一方面，也在提升 Hyperscan 算子易用性，比方说现在的规则发生变化时，需要重启作业才能生效，后续希望能做到规则的动态热加载。

本文转载自：360 技术（ID：qihoo_tech）

原文链接：如何提高大规模正则匹配的效能