RE2JS: Quadratic-time denial of service in re2js lookbehind matching

### Summary Using the opt-in `LOOKBEHINDS` flag together with any repeated-matching API (`matcher().find()` in a loop, `matchAll()`, `split()`, `matcher().replaceAll()`) causes quadratic-time (Θ(n²)) matching, contradicting the library's own "linear time matching" guarantee. A single call with a 16,000-character input takes **36.7–38.7 seconds of CPU**. ### Description #### Root cause In `build/index.cjs`, `Machine.match`: ```js let currentPos = this.prog.numLb > 0 ? 0 : pos; // ~line 1907 ... if (this.ncap === 0 && this.matched) break; // ~line 1953 ``` Any pattern containing a lookbehind sets `prog.numLb > 0`, which forces the scan to **always restart at offset 0**, regardless of the requested start position — the lookbehind automaton is re-seeded and the whole input is re-walked on every single `find()` call. The early-exit optimization that would otherwise stop at the first match only fires when `ncap === 0`, but every `Matcher`-based API (`find`/`matchAll`/`split`/`replaceAll`) always requests `ncap = 2` (one capture group slot) **even for a captureless lookbehind pattern** — so the early exit never triggers through those APIs, and the scan continues to the end of the input on every find. A find-loop over *k* matches in an *n*-character string therefore costs *k* × Θ(*n*); for dense matches *k* ∝ *n*, giving **Θ(n²)** total. #### Isolating control Identical find-loop, identical input sizes, same 2-character literal pattern *shape* — but **without** the `LOOKBEHINDS` flag: | n | with `LOOKBEHINDS` (lookbehind pattern) | without (plain literal) | native JS `RegExp` lookbehind | |---|---|---|---| | 2,000 | 204–228 ms | 3 ms | 0 ms | | 4,000 | 877–899 ms | 4 ms | 0 ms | | 8,000 | 5,746–6,599 ms | 7 ms | 1 ms | | 16,000 | 36,667–38,732 ms | 6 ms | 1 ms | This isolates the lookbehind machinery itself — not pattern length, not match density in the abstract — as the exact and sole cause. #### Impact - `re2js`'s entire value proposition is being an RE2-style engine with **linear-time, no-backtracking** matching, specifically to resist algorithmic-complexity attacks that plague backtracking regex engines. This finding defeats that guarantee for any consumer using the advertised `LOOKBEHINDS` feature. - Realistic affected code paths: log/text processing that tokenizes or redacts using a lookbehind-based pattern (`matchAll`, `split`, `replaceAll` are the natural APIs for exactly this), applied to attacker-influenced text (user input, uploaded logs, scraped content). - A single ~16–32 KB request pins a CPU core for tens of seconds to minutes; Node.js being single-threaded, this freezes the whole worker process for the duration. No authentication or special pattern knowledge is required from the attacker — ordinary alternating text (`"abababab..."`) triggers it. #### Reproduction (copy-paste runnable) create file poc.js ```js 'use strict'; // PoC: quadratic-time DoS in re2js's lookbehind matching (opt-in LOOKBEHINDS flag). // Usage: // npm pack re2js@2.8.6 --ignore-scripts && tar -xzf re2js-2.8.6.tgz // node poc.js ./package const path = require('path'); const pkgDir = process.argv[2] || './package'; const { RE2JS } = require(path.resolve(pkgDir, 'build/index.cjs')); const re = RE2JS.compile('(?<=a)b', RE2JS.LOOKBEHINDS); function timeFindLoop(n) { const s = 'ab'.repeat(n / 2); const t0 = Date.now(); const m = re.matcher(s); let count = 0; while (m.find()) count++; return { ms: Date.now() - t0, count }; } console.log('n, matches, ms'); const sizes = [2000, 4000, 8000, 16000]; const results = []; for (const n of sizes) { const r = timeFindLoop(n); results.push(r.ms); console.log(`${n}, ${r.count}, ${r.ms}`); } const ratio = results[results.length - 1] / results[results.length - 2]; console.log(''); console.log('time ratio for the last doubling of n:', ratio.toFixed(2), '(~2 => linear, ~4 => quadratic)'); console.log(ratio > 3 ? 'PASS quadratic scaling confirmed on the REAL published package' : 'FAIL scaling looks linear'); process.exit(ratio > 3 ? 0 : 1); ``` and run in terminal ```sh npm pack re2js@2.8.6 --ignore-scripts tar -xzf re2js-2.8.6.tgz node poc.js ./package ``` `poc.js` times a `matcher(s).find()` loop over `(?<=a)b` + `RE2JS.LOOKBEHINDS` on inputs of 2,000/4,000/8,000/16,000 chars and reports the doubling ratio. Expected: clearly superlinear (ratio ≫ 2, approaching or exceeding the 4× quadratic signature), reaching tens of seconds at 16,000 chars. Run twice; results are deterministic.