💻 computer science

Towards Efficient Matching of Regexes with Backreferences using Register Set Automata (Technical Report)

该论文提出了一种名为寄存器集自动机（RSA）的新模型，通过将带反向引用的正则表达式转换为确定性 RSA，实现了线性或二次时间复杂度的高效匹配，显著提升了现有匹配器的鲁棒性，并证明了该模型的空性问题可判定且其表达能力与其他数据词自动机模型不可比。

原作者： Vojtěch Havlena, Lukáš Holík, Ondřej Lengál, Jan Vašák, Sabína Gulčíková

发布于 2026-04-16

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Vojtěch Havlena, Lukáš Holík, Ondřej Lengál, Jan Vašák, Sabína Gulčíková

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

这篇论文主要解决了一个计算机领域的“老难题”：如何快速、安全地匹配带有“回溯引用”的正则表达式。

为了让你轻松理解，我们可以把整个过程想象成**“在图书馆找书”和“防止图书馆被捣乱”**的故事。

1. 背景：什么是正则表达式和“回溯引用”？

想象你是一位图书管理员（计算机程序），手里有一本**“找书规则手册”（这就是正则表达式**）。

普通规则：比如“找所有红色的书”。这很简单，你扫一眼书架，看到红色的就拿走。
带“回溯引用”的规则：这就像规则里写着：“先找一本红色的书，记住它的名字；然后找一本蓝色的书；最后，必须再找一本名字和第一本完全一样的书。”

这种“记住之前的内容，后面再对照”的功能，就是回溯引用（Backreferences）。它在处理复杂数据（比如检查 XML 文件、验证用户输入）时非常有用。

2. 问题：为什么现在的系统会“崩溃”？

目前，大多数图书管理员（现有的正则匹配器，如 PCRE2、Python 的 re 等）在处理这种“先记后对”的规则时，使用的是**“笨办法”，也就是回溯算法（Backtracking）**。

比喻：迷宫探险
想象你要在一个巨大的迷宫里找出口。

笨办法（回溯）：你走到一个岔路口，随便选一条路走。如果走不通，你就退回到岔路口，换另一条路再试。如果还是不行，再退回去……
灾难现场（ReDoS 攻击）：如果迷宫设计得很狡猾（比如有很多看似能走其实走不通的死胡同），或者有人故意给你一张画满死胡同的地图（恶意输入），管理员就会陷入**“无限循环”。他会在岔路口进进出出几百万次，最后累死在原地，导致整个图书馆（服务器）瘫痪，谁也进不来了。这就是“正则表达式拒绝服务攻击”（ReDoS）**。

现状：为了追求速度，很多现代系统（如 Google 的 RE2）直接禁止使用这种“回溯引用”功能，因为没人能写出一个既快又不会卡死的算法来处理它。

3. 解决方案： register set automata (RSA) —— “超级记忆库”

这篇论文的作者提出了一种新的“找书策略”，叫做寄存器集自动机（Register Set Automata, RSA）。

比喻：从“单本笔记”升级为“智能清单”

旧方法（普通寄存器自动机）：
以前的管理员手里只有一个小记事本。他只能记下一个名字。
- 规则：“记住第一个名字，后面再找一样的。”
- 如果规则是：“记住第一个名字，再记住第二个名字，最后找跟第一个一样的……"
- 小记事本不够用了！他必须擦掉第一个记第二个，或者疯狂地在脑子里模拟“如果当时记的是 A 会怎样，如果是 B 会怎样”。这就是导致卡死的原因。
新方法（寄存器集自动机 RSA）：
作者给管理员换了一个**“超级智能清单”**（Set Register）。
- 这个清单不是记“一个名字”，而是可以同时记下“所有见过的名字”。
- 操作：
  1. 添加：每看到一个新名字，直接扔进清单里（清单自动去重）。
  2. 合并：如果两个清单要合并，直接倒在一起。
  3. 检查：要检查“这个名字在不在清单里？”，只要看一眼清单就行，不用回头重走。

核心突破：
作者设计了一种算法，能把那些复杂的、带有“回溯引用”的规则，自动翻译成这种“超级智能清单”的指令。

确定性：这个新系统不需要“猜”或者“退回去重走”。它像一条笔直的高速公路，每读一个字符，只做一次检查。
速度：无论输入多长，它都能在线性时间内搞定（比如 100 个字符，就花 100 步；100 万个字符，就花 100 万步，绝不会变成 100 万步的平方）。

4. 实验结果：真的有用吗？

作者写了一个原型工具（叫 rsamatch），并拿它和现有的顶级工具（如 PCRE2, grep, Python re 等）做比赛。

场景：给它们一些精心设计的“恶意地图”（ReDoS 攻击向量），这些地图会让旧工具卡死几秒甚至几分钟。
结果：
- 旧工具：大部分直接超时（超过 100 秒），或者跑了几万步还没找到答案。
- 新工具（rsamatch）：几乎全部在1 秒以内搞定，而且非常稳定。
- 结论：新方法不仅快，而且极其稳健，彻底消除了被恶意输入卡死的风险。

5. 理论上的“副作用”

虽然新方法很快，但作者也诚实地指出，这种“超级清单”在数学上变得更复杂了。

代价：如果要证明这个清单里“有没有书”（空集问题），计算难度比以前的方法高了很多（从“中等难度”变成了“超级难度”，虽然理论上还是可解的，但计算量很大）。
权衡：但在实际应用中，我们更关心“匹配速度快不快”和“会不会被卡死”，而不是“证明它有没有书”。所以，这个代价是值得的。

总结

这篇论文就像给图书馆管理员发了一套**“防暴盾牌”和“超级清单”**：

以前：遇到复杂规则就靠“猜”，容易被坏人（恶意输入）绕晕，导致服务器崩溃。
现在：用“超级清单”把所有可能性一次性记下来，只走一遍就能完成匹配。
效果：速度快如闪电，且绝对安全，不再怕“拒绝服务攻击”。

这对于保护互联网安全（防止网站被正则表达式攻击搞挂）有着非常重要的意义。

这是一份关于论文《Towards Efficient Matching of Regexes with Backreferences using Register Set Automata》（利用寄存器集自动机高效匹配带反向引用的正则表达式）的详细技术总结。

1. 研究背景与问题 (Problem)

核心问题：正则表达式（Regex）匹配是计算机科学中的常见任务，广泛应用于搜索、数据验证、入侵检测等领域。然而，包含**反向引用（Backreferences）**的扩展正则表达式（例如 (.).*\1，匹配重复的子串）会导致匹配性能急剧下降。
现有挑战：
- 性能瓶颈：大多数支持反向引用的匹配器（如 PCRE2, Python re）基于回溯（Backtracking）算法。对于某些输入，回溯会导致指数级的时间复杂度，引发正则表达式拒绝服务攻击（ReDoS）。
- 自动机局限：传统的基于自动机的快速匹配算法（如 Thompson 算法、DFA 确定化）无法直接处理反向引用，因为带反向引用的语言通常不是正则语言，且难以构建确定性的有限自动机。
- 安全威胁：由于缺乏高效且确定的算法，工业界最先进的匹配器（如 RE2, HyperScan）通常完全不支持反向引用，或者在支持时性能极差。
目标：开发一种新的形式化模型和算法，能够在保证线性或二次时间复杂度的前提下，高效、鲁棒地匹配包含反向引用的正则表达式，从而消除 ReDoS 风险。

2. 方法论 (Methodology)

论文提出了一种名为**寄存器集自动机（Register Set Automata, RSA）**的新模型，并设计了一套完整的转换与匹配流程。

2.1 核心模型：寄存器集自动机 (RSAs)

定义：RSA 是寄存器自动机（Register Automata, RAs）的扩展。
- 传统 RA：寄存器中存储单个数据值（Data Value）。
- RSA：寄存器中存储数据值的集合（Sets of Symbols）。
操作能力：
- 支持将输入值添加到寄存器集合中。
- 支持寄存器的合并（Union）、**清空（Clear）**操作。
- 支持测试输入值是否属于某个寄存器集合（ $in \in r$ ）或不属于（ $in \notin r$ ）。
确定性 (DRSA)：论文证明了可以将一大类非确定性 RA 转换为确定性寄存器集自动机（DRSA）。DRSA 的匹配过程是确定性的，因此具有可预测的时间复杂度。

2.2 技术流程

正则表达式转 RA：利用**Antimirov 偏导数（Partial Derivatives）**技术，将带有反向引用的正则表达式（特别是单字符捕获组）转换为非确定性寄存器自动机（NRA）。
NRA 转 DRSA（确定化）：提出了一种半算法（Semi-algorithm），将 NRA 转换为 DRSA。
- 状态构造：使用子集构造法（Subset Construction），但状态不仅包含原自动机的状态集合，还包含寄存器中数据集合大小的分类（0, 1, 或 $\omega$ ）。
- 处理不精确性：通过跟踪寄存器大小类（Size Classes）和检查笛卡尔积过近似（Cartesian Overapproximation），确保转换的精确性。如果无法确定化，算法会返回失败（ $\bot$ ），但在实践中对大多数实际用例是成功的。
匹配执行：在转换得到的 DRSA 上运行匹配算法。由于 DRSA 是确定性的，匹配过程只需遍历输入一次。

3. 主要贡献 (Key Contributions)

引入 RSA 模型：提出了寄存器集自动机，扩展了寄存器自动机的能力，使其能够存储值集合，从而支持更复杂的模式匹配。
理论性质分析：
- 证明了 RSA 的空性问题（Emptiness Problem）是可判定的，且复杂度为 $F_\omega$ -完全（阿克曼级，Ackermannian），这比传统 RA 的 PSPACE-完全要高，但仍是可判定的。
- 证明了 DRSA 在并、交、补运算下的封闭性，而 NRA 在补运算下不可判定。
- 建立了 RSA 与其他自动机模型（如交替寄存器自动机 ARA、Pebble 自动机）在表达能力上的关系。
确定化算法：设计了一个将 NRA 转换为 DRSA 的（半）算法。该算法对于由单寄存器且无不等式测试的 NRA 通过布尔运算生成的语言类是完备的。
复杂度分析：
- 对于有限字母表，DRSA 匹配的时间复杂度为输入长度的线性 $O(|w|)$ 。
- 对于无限字母表，复杂度为二次 $O(|w|^2)$ 。
- 如果自动机是“无复制”（Copy-free）的，复杂度可进一步优化为线性。
实验验证：实现了原型匹配器 rsamatch，并在真实世界的 ReDoS 攻击向量上进行了测试。

4. 实验结果 (Results)

数据集：使用了来自 Lingua Franca 和 Rengar 的 12,046 个真实世界正则表达式，其中 1,335 个被识别为易受 ReDoS 攻击。
确定化成功率：
- 对于单字符反向引用的正则表达式，算法成功转换为 DRSA 的比例高达 91%。
- 对于所有输入正则表达式，成功率约为 34.5%（受限于语法复杂度和多字符捕获组）。
性能对比：
- 鲁棒性：在 1,246 个支持的正则表达式测试中，rsamatch 在 99.8% 的测试用例中运行时间低于 1 秒（绝大多数在毫秒级）。
- 对比竞品：现有的主流匹配器（如 PCRE2, grep, Python re, Java, .NET）在面对相同的 ReDoS 攻击向量时，经常发生超时（>100 秒）或极慢运行。
- ReDoS 防御：rsamatch 成功消除了所有测试用例中的 ReDoS 风险，而竞品匹配器中有大量案例表现出灾难性回溯。
- 稳定性：rsamatch 的运行时间标准差极低，表现出极高的可预测性。

5. 意义与影响 (Significance)

解决 ReDoS 痛点：该研究提供了一种理论可行且实践有效的方案，能够高效匹配带反向引用的正则表达式，从根本上解决了由回溯引起的拒绝服务攻击问题。
填补技术空白：目前工业界最强大的匹配器（RE2, HyperScan）因缺乏高效算法而放弃支持反向引用。本论文提出的 DRSA 模型填补了这一空白，使得构建支持反向引用且具备高性能、高安全性的匹配器成为可能。
理论突破：将自动机理论扩展到数据字（Data Words）领域，证明了在引入集合操作后，虽然空性问题复杂度上升，但仍可判定，且能实现确定性匹配。
实际应用价值：对于网络入侵检测系统（NIDS）、Web 应用防火墙（WAF）以及任何需要处理用户输入验证的系统，该方法提供了构建更健壮、更安全的正则匹配引擎的基础。

总结：这篇论文通过引入“寄存器集自动机”这一新模型，成功地将带反向引用的正则表达式匹配从“指数级回溯”转变为“确定性线性/二次匹配”，在理论和实践上显著提升了正则匹配的安全性和效率，是解决 ReDoS 攻击的重要进展。