💻 computer science

PUFFERDOS: Efficient and Effective Attack String Generation for Regular Expression Denial of Service Vulnerabilities

本文介绍了 PUFFERDOS，一种通过基于三种经形式化验证的漏洞模式合成输入，并利用组合式符号执行进行优化，以确保在现实长度预算内实现真实世界可利用性的新颖工具，从而生成实用且有效的 ReDoS 攻击字符串。

原作者： Shangzhi Xu, Ziqi Ding, Xiao Cheng, Yuekang Li, Nan Sun, Benjamin Turnbull, Shuangxiang Kan, Siqi Ma

发布于 2026-06-19

📖 1 分钟阅读☕ 轻松阅读

原作者： Shangzhi Xu, Ziqi Ding, Xiao Cheng, Yuekang Li, Nan Sun, Benjamin Turnbull, Shuangxiang Kan, Siqi Ma

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

想象一下，你面前有一名非常聪明但有点强迫症的保安，守在建筑物的门口。他的工作是检查你的身份证（输入内容）是否符合特定的模式（正则表达式，或称“regex”）。通常情况下，这很快且很容易。

但这里有一个陷阱。如果你给出一个非常特定、令人困惑的身份证，保安的大脑就会陷入循环。他会开始反复检查你的身份证可能匹配该模式的所有方式，直到耗尽体力并昏厥过去。这被称为 ReDoS 攻击（正则表达式拒绝服务攻击）。这就像是诱导计算器进行无限循环的数学运算，从而导致其死机。

长期以来，安全研究人员一直试图寻找这些陷阱，并创建“测试 ID”来证明这个保安是存在缺陷的。然而，旧的方法有两个大问题：

ID 太长了： 它们需要极其庞大的输入（比如一本书长度的文本），以至于任何真实的网站都不会接受这样的输入。
它们不符合实际场景： 它们是在孤立地测试保安，忽略了在现实建筑中，会有其他保安（过滤器）在你的 ID 到达主门之前就将其拦截。

于是有了 PUFFERDOS。你可以把 PUFFERSDOS 想象成一位大师级的锁匠，他不只是在开锁，而是弄清楚了如何通过整个建筑到达那把锁，并使用最简短、最高效的钥匙。

以下是 PUFFERDOS 的工作原理，分为几个简单的步骤：

1. “停顿点”策略（让保安更辛苦地工作）

研究人员意识到，要让保安陷入瘫痪，你不仅需要一个令人困惑的模式，还需要一个让保安必须采取微小、低效步骤的模式。

类比： 想象保安正在走廊里行走。如果你让他每走一英寸就停下来检查地面，他很快就会累；如果他每 10 英尺才停一次，他累得慢一些。
解决方法： PUFFERDOS 创建了“钥匙”（攻击字符串），强制保安在每一个微小的英寸处停下。它通过精心选择特定的字符并进行排列，使得保安必须尽可能多次地进行回溯（返回并重新检查）。这使得攻击比之前的方法快了数千倍，因为它能用更短的钥匙实现同样的“冻结”效果。

2. 三种“陷阱”模式

团队发现大多数损坏的锁都属于三种特定的形状。PUFFERDOS 为每种形状都有特殊的配方：

单循环陷阱（The One-Loop Trap）： 一个可以有多种混淆解读方式的单一模式。PUFFERDOS 选择最短且最令人困惑的重复字符。
双循环陷阱（The Two-Loop Trap）： 两个相邻的模式都可以读取同一个字符。PUFFERDOS 使用一个两种模式都能读取的字符，迫使它们为了谁来处理该字符而发生争执。
多循环陷阱（The Multi-Loop Trap）： 一个长链模式。PUFFERDOS 构建一把钥匙，迫使保安逐一检查链条中的每一个环节。

3. “现实世界”的演练（符号执行/Concolic Execution）

这是最重要的部分。旧的工具只是在真空中测试锁。PUFFERDOS 则模拟了整个建筑。

类比： 想象你有一把能打开门的钥匙，但这扇门位于一个安全检查站、一个接待处和一个迷宫之后。旧工具只展示了你的钥匙能开锁。而 PUFFERDOS 会带你走过整个迷宫，检查接待处是否让你通过，并确保你确实到达了那扇门。
方法： 它使用了一种叫做“组合式符号执行（compositional concolic execution）”的技术。你可以把它理解为地图摘要。它不会每次都重新走完建筑里的每一步，而是为每个房间（函数）创建一个“小抄”。它会问：“如果我给这个房间一把令人困惑的钥匙，它是会将钥匙传递给下一个房间，还是会将其丢弃？”
通过使用这些小抄，PUFFERDOS 可以快速判断一个短小、高效的钥匙是否真的能到达真实程序中的脆弱锁具，或者是否会在过程中的早期阶段就被过滤器拦截。

结果

团队在数千个真实程序和已知的安全漏洞（CVE）上测试了 PUFFERDOS。

速度： 它生成的攻击字符串比之前的最佳工具效率高出 97 到 3,800 倍。它可以用极短的字符串让系统死机，而不是需要巨大的字符串。
成功率： 它成功重现了 96.8% 的已知安全漏洞（相比之下，旧工具为 77.4%）。
新发现： 当他们在 12 个流行的真实软件项目上进行测试时，发现了 59 个此前未知的安全漏洞。这些漏洞之所以被旧工具漏掉，是因为旧工具无法生成足够真实且足够短的攻击来证明漏洞的存在。

简而言之： PUFFERDOS 是一种更聪明、更实用的寻找并证明计算机系统会被混乱模式冻结的方法。它不仅找到了锁，还找到了最简短、最真实的钥匙来卡住它，从而证明了这种危险是真实存在的，并且需要被修复。

技术摘要：PUFFERDOS

问题陈述

正则表达式拒绝服务（ReDoS）攻击利用回溯型正则表达式引擎在最坏情况下的病态执行行为，迫使引擎探索超线性或指数级的匹配路径。这会消耗过多的 CPU 资源，导致服务性能下降或不可用。虽然目前已有许多检测工具可以识别易受攻击的正则表达式并生成概念验证（PoC）攻击字符串，但现有方法在实际利用方面存在两个关键局限性，阻碍了其应用：

输入长度不切实际： 现有工具生成的攻击字符串往往过长（例如，需要数十万个字符）才能触发显著的延迟。在现实世界的部署中，输入约束（如 HTTP 请求头限制）往往会在这些字符串到达易受攻击的正则表达式之前将其截断，从而使攻击失效。
缺乏程序级验证： 许多生成的字符串仅针对孤立的正则表达式进行验证。它们未能考虑到宿主程序中的数据流约束、过滤逻辑或输入截断。因此，这些字符串在真实的程序执行上下文中往往无法到达目标正则表达式，导致开发者将报告的漏洞视为低严重性或不可利用。

方法论

作者提出了 PUFFERDOS，这是一个混合框架，旨在合成既高效（在现实长度预算内最大化匹配成本）又有效（经过验证能到达程序中目标正则表达式）的攻击字符串。该方法由三个核心组件组成：

1. 形式化分析与模式分类

作者首先形式化了攻击字符串结构与匹配成本之间的关系。通过形式化证明（引理 3.2–3.4 和定理 3.5），他们确立了当满足以下条件时，匹配成本会增加：

重复单元尽可能短。
重复单元选自相邻循环表达式（Loop Expressions, LEs）字母表的交集，允许多个 LE 消耗相同的子串。
停止点（LE 终止的索引）是分离而非交错的，这迫使引擎在回溯期间重新处理更长的输入段。

基于此，他们定义了三种易受攻击的模式来指导字符串生成：

指数级单循环 (Exponential One-Loop, EOL)： 单个 LE 具有字母表重叠的展开子正则表达式。
循环-交集-循环 (Loop-Intersect-Loop, LIL)： 两个相邻的 LE 被一个可被两者匹配的非循环段分隔。
多项式多循环 (Polynomial Multi-Loop, PML)： 相邻的 LE 具有不相交的字母表或无法被两者共同消耗的分隔符。

2. 结构驱动的攻击字符串生成

PUFFERDOS 将易受攻击的正则表达式解析为抽象语法树（rAST），以识别特定的易受攻击模式（EOL、LIL 或 PML）。然后，它使用特定于模式的规则合成候选攻击字符串（ $s_a = x \cdot y^q \cdot z$ ）：

中间体生成 (Infix Generation)： 从相关 LE 字母表的交集中选择最短的重复单元（ $y$ ）。对于具有多个 LE 的模式，它通过拼接独立重复的单元来确保停止点是分离的，从而最大化回溯步骤。
前缀/后缀构建： 从正则表达式的非循环前缀导出前缀（ $x$ ），从非循环后缀导出后缀（ $z$ ），确保最终字符串被正则表达式拒绝，从而触发详尽的回溯。

3. ReDoS 特定的组合共路执行精炼

为了确保生成的字符串能在实际程序中到达易受攻击的正则表达式，PUFFERDOS 采用了组合共路执行（compositional concolic execution）策略：

路径提取： 构建调用图，识别从程序入口点到易受攻击正则表达式的可行路径。
函数摘要： 对路径上的函数进行共路单元测试，以生成 ReDoS 特定的函数摘要。与传统摘要不同，这些摘要经过剪枝，仅保留与攻击字符串传播相关的行为（例如，恒等变换或常量返回），丢弃会导致路径爆炸的无关正则表达式推理。
系统级精炼： 使用这些摘要来指导系统级共路执行，通过解决过程间约束来精炼攻击字符串，使其既能绕过过滤器到达目标正则表达式，又不超过现实的输入长度预算。

核心贡献

效率的形式化证明： 本文形式化证明了通过选择特定字符并按顺序排列以分离相邻 LE 中的停止点，可以显著放大正则表达式的匹配成本。这导出了三种正则表达式易受攻击模式以及可证明高效的生成规则。
PUFFERDOS 框架： 开发了一个结合了形式化生成规则与 ReDoS 特定组合共路精炼的混合生成器。这种方法通过确保生成的字符串足够短以符合现实世界约束，并且在程序数据流中有效，弥合了理论检测与实际利用之间的鸿沟。
全面评估： 该工具在包含 17,962 个易受攻击正则表达式、31 个已知 CVE 和 12 个流行开源项目的规模化语料库上进行了评估。

结果

评估表明 PUFFERDOS 相比于最先进的工具 RENGAR 有显著改进：

效率： 在达到相同的匹配时间阈值（0.1s, 1s, 和 10s）时，PUFFERDOS 生成的攻击字符串比 RENGAR 生成的字符串短 97.2 倍至 3,872.4 倍。
CVE 复现： PUFFERDOS 成功复现了 96.8% 的被利用的 ReDoS CVE，而 RENGAR 为 77.4%。
新漏洞发现： 应用于 12 个流行的开源项目，PUFFERDOS 发现了 59 个可利用的 ReDoS 实例（比 RENGAR 多出 25 个）。其中六个项目的开发者验证了其中的 21 个发现。
现实影响： 在一个涉及语法高亮库的启发式案例中，PUFFERDOS 生成了一个 1,000 字符的字符串，导致系统挂起超过 4,000 秒；而传统方法需要 500,000 个字符，且由于实际程序中的输入截断，无法触发挂起。

重要性

本文认为，ReDoS 检测的实用性目前受到限制，因为生成的攻击字符串往往过长，或者无法在程序逻辑中传播。通过解决这些特定缺陷，PUFFERDOS 提供了一种生成实际可利用的漏洞证据的机制。这具有重要意义，因为它直接解决了开发者经常忽略 ReDoS 报告的原因（即认为其为低严重性或不可利用）。通过提供简短且有效的攻击字符串，PUFFERDOS 能够实现更准确的风险评估，并促进现实软件系统中 ReDoS 漏洞的修复。