Skip to content

tag-echo filter: space-separated long reference strings trigger catastrophic regex backtracking; 30 references block the | tag-echo 过滤器:空格分隔的长引用串触发正则灾难性回溯,30 个引用阻塞流式管线约分钟级(DoS) #4178

Closed

Description

@ranxianglei

这是啥问题?(现象+触发条件,一句话)

模型输出里出现空格分隔的 22+ 个引用串(如 m1111 m1111 …,模型回声/对抗提示都可能触发),流式过滤器的 push() 因 REFS_RUN 的灾难性回溯卡住——每多 2 个引用耗时 ×4,30 个引用 ≈ 5 分钟,34 个 ≈ 1 小时以上,SSE 处理管线整段停摆。

实测(真实 createTagEchoFilter,单次 push)

引用数(空格分隔) push() 耗时
16 3.5ms
18 14.5ms
20 57ms
22 227ms / 1103ms(带/不带尾随空格)
24+ ~4× 递增(外推:30 ≈ 5min,34 ≈ 1.2h)

对照:

  • 逗号分隔同样 30 个引用:2ms(无回溯)
  • 整文本模式 stripAcpTags 同输入:0ms(无回溯)
  • 空格+逗号混合(\" m1111 , \" 风格):0ms

即:只有空格分隔且走流式 push 才炸。

根本原因(代码级)

src/loop/tag-echo-filter.ts 的引用串模式:

```js
const REF_TOKEN = "m\\d{4,}";
const REFS_RUN = REF_TOKEN + "(?:\\s*[–—,-]?\\s*" + REF_TOKEN + ")*";
```

分隔符 \\\\s*[–—,-]?\\\\s* 里两个 \\\\s* 与外层 * 构成嵌套量词歧义——同一段空格可以分给内层左 \\\\s*、可选字符、右 \\\\s* 或外层迭代,失败时回溯组合爆炸(2^n)。

在 process() 里,对每个缓冲区执行的:

  • ORPHAN_REF_CLOSE(:135)= REFS_RUN + \\\\s*</NAME(?=[\\\\s>])… — 引用串后没有闭合标签 → 匹配失败 → 对 22 个引用的全部切分方式回溯;
  • PARTIAL_TAIL(:188)第 5 臂 REFS_RUN\\\\s*<[^<>]* 同样先于会成功的裸引用臂执行,失败时同样回溯。

逗号分隔不炸:, 无歧义地命中可选字符类,切分方式唯一。整文本 stripAcpTags 不炸:它的各 pass 要么快速成功要么不含该歧义分隔符。

后果

修复方向(供 owner 定夺)

  • 经典解法:消除分隔符歧义,如把 (?:\\\\s*[–—,-]?\\\\s*m\\\\d{4,})* 改写成首字符不相交的分支 (?:\\\\s+[–—,-]\\\\s*m\\\\d{4,}|\\\\s+m\\\\d{4,}|[–—,-]\\\\s*m\\\\d{4,})*,或用前瞻模拟占有量词 (?=(\\\\s*[–—,-]?\\\\s*m\\\\d{4,}))\\\\1;
  • 或匹配前把 \\\\s{2,} 归一成单空格(注意 \\\\s 含换行,归一化别改变语义);
  • REFS_RUN 被多条正则引用(ORPHAN_REF_CLOSE/PARTIAL_TAIL/ORPHAN_RUN_BEFORE/REFS_ONLY/PAIRED/PENDING_REF_SPAN),一处修全部受益;
  • 修完后建议给 tests/tag-echo-chunking-determinism.test.ts 补一个 40 引用空格列表的限时用例(当前语料没这么长的列表)。

关联

Activity

  1. changed the title [-]tag-echo 过滤器:空格分隔的长引用串触发正则灾难性回溯,30 个引用阻塞流式管线约分钟级(DoS)[/-] [+]tag-echo filter: space-separated long reference strings trigger catastrophic regex backtracking; 30 references block the | tag-echo 过滤器:空格分隔的长引用串触发正则灾难性回溯,30 个引用阻塞流式管线约分钟级(DoS)[/+] on Oct 21, 2026
  2. added
    verif工具发现由 verif 符号执行/判官或 BEX 穷举工具自动发现(工具链:verif/ 模块,PR #3853/#4071/#4103/#4108/#4112/#4151)
    on Oct 21, 2026
  3. ranxianglei commented on Oct 21, 2026

    @ranxianglei
    OwnerAuthor

    修复已提交:PR #4180(分隔符改成首字符互斥的等价写法,语言等价 4352 形状 0 差异,200 空格引用 0ms,含计时回归钉)。等人工合并。

  4. added 6 commits that reference this issue on Oct 21, 2026
  5. ranxianglei commented on Oct 23, 2026

    @ranxianglei
    OwnerAuthor

    🤖 Powered by ework · qwen3.8-27b

    (ai: vllm-qwen/qwen3.8-27b)

    查重:无重复立项;本 issue 已有在途修复 PR #4180。 按失败签名(REFS_RUN / 灾难性回溯 / tag-echo 流式卡死)检索 open+closed issue/PR,没有其他并行修复或立项。PR #4180(10-21 由前一个 agent 会话开出,Closes #4178)是本 issue 的唯一修复——按「一个 issue 最多一个 PR」的 loop guard,不另开第二个 PR;本次唤醒我做的是独立复核,不是重做。

    标签:bug / scope/wiring / p1(理由:流式管线可用性缺陷——模型回声 ≥22 个空格分隔引用即触发,命中一次该会话 SSE 处理停摆分钟级至小时级;条件触发但后果管线级,按缓存/可用性口径定 p1)。

    当前状态:PR #4180 已 rebase 到绿 master(v0.1.204 之上),head 2e0fd7c71 全量 CI 通过,等人工合并。我正在本地独立验证(不复读前会话结论):①旧正则指数爆炸复现;②新旧正则语言等价差分 fuzz;③计时回归钉 + tag-echo 相关定向套件。完成后按结构化八问给最终结论。

  6. ranxianglei commented on Oct 23, 2026

    @ranxianglei
    OwnerAuthor

    🤖 Powered by ework · qwen3.8-27b

    (ai: vllm-qwen/qwen3.8-27b)

    独立复核完成。本会话未复用任何前会话结论——以下全部是我在 PR head 2e0fd7c71 + 当前 master 970bd4d40 上本地重测的结果。结论:建议合并 #4180(合并动作按规则由人工执行)。

    八问:

    1. 是什么问题:模型输出里出现 ≥22 个空格分隔的 kernel 引用(m1111 m1111 …)时,流式 tag-echo 过滤器的 push() 陷入正则灾难性回溯,该会话 SSE 处理停摆分钟级至小时级——可用性/DoS 级缺陷。最炸的形状恰好是该过滤器专门防御的仿引用回声,攻击面即防御面。
    2. 什么原因导致的:REFS_RUN 的分隔符 \s*[–—,-]?\s* 里两个 \s* 夹一个可选分隔字符,构成嵌套量词歧义——同一段空格在内层左 \s*、可选字符、内层右 \s*、外层迭代之间有 2^(n−1) 种分法;尾随上下文(闭合标签/行尾)匹配失败时回溯穷举全部分法。逗号分隔不炸,因为 , 唯一命中可选字符类,分法只剩一种。
    3. 影响范围与严重程度:任何会话中模型回声长引用列表(复述历史引文、对抗提示)即触发;单次命中冻结该会话流式管线分钟级以上(issue 实测外推:30 引用 ≈5min、34 ≈1.2h);其他会话不受影响。p1(可用性级)。
    4. 怎么修复的:消除分隔歧义而非压慢正则——改写为 \s*(?:[–—,-]\s*)?:每个 gap「下一字符是不是分隔符」唯一决定解析方式,语言与旧正则完全等价(匹配同样的串、同样的 span),但回溯路径从 2^(n−1) 降到 1。共享常量 REFS_RUN 一处修复,六条引用它的正则(ORPHAN_REF_CLOSE/PARTIAL_TAIL/ORPHAN_RUN_BEFORE/REFS_ONLY/PAIRED/PENDING_REF_SPAN)全部受益;另对齐两处内联尾部同款分隔符(PENDING_REF_SPAN :127、PARTIAL_TAIL arm6,线性无 DoS 但同族歧义一并消除)。新增限时回归钉:40/200 引用空格列表 + 失败尾形状,断言 <1s。
    5. 是否有回归问题:无。逐项审过的既有行为:引用串匹配语义(六条正则的匹配 span)——差分 fuzz 对 24,800 个字符串(随机+结构化)做 732,154 次 span 级比较,新旧 0 diff;定向套件 112/112 绿(含 tag-echo filter occasionally lets m01233</acp> remnant through to the client reasoning stream (model echoes refs from compress confirmation markers) #2023 残留钉、Streaming tag filter output depends on chunk position: when the same text arrives in two chunks, internal residual m1255 | 流式标签过滤器输出依赖分块位置:同一文本分两块到达时内部残留 m1255</acPA 泄漏给客户端 #4107 chunk-split 钉、chunking-determinism、e2e-tag-echo、verif-tag-echo-filter);typecheck 干净;PR head CI 我直接查 API 确认:21 success / 9 skipped / 0 fail。高危模式逐项过:无语义漂移(fuzz 实证等价)、无 fail-fast 变吞错、无阈值/时序/输出格式漂移、缓存/重试策略未触碰。
    6. 是否破坏缓存:不涉及——过滤器作用于出站 prose 字节流,不碰前缀缓存键、重试、增量游标。
    7. 是否改了设计方向:不涉及——纯性能缺陷修复,架构/数据流无转向。
    8. 是否引入新配置:不涉及——无新 env/config/默认值。

    行为变更披露:无语义行为变更(新旧正则语言等价,fuzz 实证);唯一可观测差异是退化输入上的 push() 延迟从分钟/小时级降到亚毫秒(本地实测:200 空格引用+失败尾 = 0.4ms;40 引用各形状 ≤2.4ms),此即修复本身。纯引用列表经分块 push 后逐字往返,无数据损坏。

    旧代码爆炸复现(本地重测,ORPHAN_REF_CLOSE 形状整体失配):n=16 → 9.4ms,n=20 → 24.3ms,n=22 → 96.8ms,n=24 → 386.1ms,每 +2 引用 ×4~16,指数签名与 issue 实测一致(绝对值因机器而异)。

    顺带核查(发现一处代表一类):全仓扫了同类 dash 分隔正则——kernel/src/parse-compress-input.ts:459/:537 的范围模式结构安全(分隔符为必填非空白备选,解析方式唯一,无歧义量词对);其余命中是提示模板文本非正则。未发现同类缺陷,不立项。

    判定:可合。PR 基于绿 master(v0.1.204 之上)、与当前 master 无冲突(master 自 base 起未触碰该文件)、mergeable=True、CI 全绿,等人工合并 #4180

  7. ranxianglei commented on Oct 23, 2026

    @ranxianglei
    OwnerAuthor

    🤖 Powered by ework · qwen3.8-27b

    (ai: vllm-qwen/qwen3.8-27b)

    这条是 10-21 提交通知的镜像重同步,无新信息。复核结论见上一条八问回复(独立复现+73 万次 span 级差分 fuzz 0 diff+定向套件 112/112 绿,建议合并)。当前状态刚查过:PR #4180 仍 open、head 2e0fd7c71 CI 全绿、与 master 无冲突——等人工合并:#4180

  8. added 2 commits that reference this issue on Oct 24, 2026
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    bugSomething isn't workingp1scope/wiringverif工具发现由 verif 符号执行/判官或 BEX 穷举工具自动发现(工具链:verif/ 模块,PR #3853/#4071/#4103/#4108/#4112/#4151)

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions