Vulnerability-Lookup

GHSA-GG6H-894W-4M9C

Vulnerability from github – Published: 2026-10-28 21:10 – Updated: 2026-10-28 21:10

Summary

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

Details

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

'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

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.

Severity

7.5 (High)


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

Show details on source website

JSON

To clipboard

{
  "affected": [
    {
      "package": {
        "ecosystem": "npm",
        "name": "re2js"
      },
      "ranges": [
        {
          "events": [
            {
              "introduced": "2.2.0"
            },
            {
              "fixed": "2.8.7"
            }
          ],
          "type": "ECOSYSTEM"
        }
      ]
    }
  ],
  "aliases": [
    "CVE-2026-116795"
  ],
  "database_specific": {
    "cwe_ids": [
      "CWE-1333",
      "CWE-407"
    ],
    "github_reviewed": true,
    "github_reviewed_at": "2026-10-28T21:10:01Z",
    "nvd_published_at": "2026-10-28T18:17:14Z",
    "severity": "HIGH"
  },
  "details": "### Summary\n\nUsing the opt-in `LOOKBEHINDS` flag together with any repeated-matching API\n(`matcher().find()` in a loop, `matchAll()`, `split()`, `matcher().replaceAll()`)\ncauses quadratic-time (\u0398(n\u00b2)) matching, contradicting the library\u0027s own\n\"linear time matching\" guarantee. A single call with a 16,000-character input\ntakes **36.7\u201338.7 seconds of CPU**.\n\n### Description\n\n#### Root cause\n\nIn `build/index.cjs`, `Machine.match`:\n\n```js\nlet currentPos = this.prog.numLb \u003e 0 ? 0 : pos;   // ~line 1907\n...\nif (this.ncap === 0 \u0026\u0026 this.matched) break;        // ~line 1953\n```\n\nAny pattern containing a lookbehind sets `prog.numLb \u003e 0`, which forces the\nscan to **always restart at offset 0**, regardless of the requested start\nposition \u2014 the lookbehind automaton is re-seeded and the whole input is\nre-walked on every single `find()` call. The early-exit optimization that\nwould otherwise stop at the first match only fires when `ncap === 0`, but\nevery `Matcher`-based API (`find`/`matchAll`/`split`/`replaceAll`) always\nrequests `ncap = 2` (one capture group slot) **even for a captureless\nlookbehind pattern** \u2014 so the early exit never triggers through those APIs,\nand the scan continues to the end of the input on every find.\n\nA find-loop over *k* matches in an *n*-character string therefore costs\n*k* \u00d7 \u0398(*n*); for dense matches *k* \u221d *n*, giving **\u0398(n\u00b2)** total.\n\n#### Isolating control\n\nIdentical find-loop, identical input sizes, same 2-character literal pattern\n*shape* \u2014 but **without** the `LOOKBEHINDS` flag:\n\n| n | with `LOOKBEHINDS` (lookbehind pattern) | without (plain literal) | native JS `RegExp` lookbehind |\n|---|---|---|---|\n| 2,000 | 204\u2013228 ms | 3 ms | 0 ms |\n| 4,000 | 877\u2013899 ms | 4 ms | 0 ms |\n| 8,000 | 5,746\u20136,599 ms | 7 ms | 1 ms |\n| 16,000 | 36,667\u201338,732 ms | 6 ms | 1 ms |\n\nThis isolates the lookbehind machinery itself \u2014 not pattern length, not\nmatch density in the abstract \u2014 as the exact and sole cause.\n\n#### Impact\n\n- `re2js`\u0027s entire value proposition is being an RE2-style engine with\n  **linear-time, no-backtracking** matching, specifically to resist\n  algorithmic-complexity attacks that plague backtracking regex engines.\n  This finding defeats that guarantee for any consumer using the advertised\n  `LOOKBEHINDS` feature.\n- Realistic affected code paths: log/text processing that tokenizes or\n  redacts using a lookbehind-based pattern (`matchAll`, `split`,\n  `replaceAll` are the natural APIs for exactly this), applied to\n  attacker-influenced text (user input, uploaded logs, scraped content).\n- A single ~16\u201332 KB request pins a CPU core for tens of seconds to minutes;\n  Node.js being single-threaded, this freezes the whole worker process for\n  the duration. No authentication or special pattern knowledge is required\n  from the attacker \u2014 ordinary alternating text (`\"abababab...\"`) triggers it.\n\n#### Reproduction (copy-paste runnable)\n\ncreate file poc.js\n\n```js\n\u0027use strict\u0027;\n// PoC: quadratic-time DoS in re2js\u0027s lookbehind matching (opt-in LOOKBEHINDS flag).\n// Usage:\n//   npm pack re2js@2.8.6 --ignore-scripts \u0026\u0026 tar -xzf re2js-2.8.6.tgz\n//   node poc.js ./package\nconst path = require(\u0027path\u0027);\nconst pkgDir = process.argv[2] || \u0027./package\u0027;\nconst { RE2JS } = require(path.resolve(pkgDir, \u0027build/index.cjs\u0027));\n\nconst re = RE2JS.compile(\u0027(?\u003c=a)b\u0027, RE2JS.LOOKBEHINDS);\n\nfunction timeFindLoop(n) {\n  const s = \u0027ab\u0027.repeat(n / 2);\n  const t0 = Date.now();\n  const m = re.matcher(s);\n  let count = 0;\n  while (m.find()) count++;\n  return { ms: Date.now() - t0, count };\n}\n\nconsole.log(\u0027n, matches, ms\u0027);\nconst sizes = [2000, 4000, 8000, 16000];\nconst results = [];\nfor (const n of sizes) {\n  const r = timeFindLoop(n);\n  results.push(r.ms);\n  console.log(`${n}, ${r.count}, ${r.ms}`);\n}\n\nconst ratio = results[results.length - 1] / results[results.length - 2];\nconsole.log(\u0027\u0027);\nconsole.log(\u0027time ratio for the last doubling of n:\u0027, ratio.toFixed(2), \u0027(~2 =\u003e linear, ~4 =\u003e quadratic)\u0027);\nconsole.log(ratio \u003e 3 ? \u0027PASS  quadratic scaling confirmed on the REAL published package\u0027 : \u0027FAIL  scaling looks linear\u0027);\nprocess.exit(ratio \u003e 3 ? 0 : 1);\n```\n\nand run in terminal\n\n```sh\nnpm pack re2js@2.8.6 --ignore-scripts\ntar -xzf re2js-2.8.6.tgz\nnode poc.js ./package\n```\n\n`poc.js` times a `matcher(s).find()` loop over `(?\u003c=a)b` +\n`RE2JS.LOOKBEHINDS` on inputs of 2,000/4,000/8,000/16,000 chars and reports\nthe doubling ratio. Expected: clearly superlinear (ratio \u226b 2, approaching or\nexceeding the 4\u00d7 quadratic signature), reaching tens of seconds at 16,000\nchars. Run twice; results are deterministic.",
  "id": "GHSA-gg6h-894w-4m9c",
  "modified": "2026-10-28T21:10:01Z",
  "published": "2026-10-28T21:10:01Z",
  "references": [
    {
      "type": "WEB",
      "url": "https://github.com/le0pard/re2js/security/advisories/GHSA-gg6h-894w-4m9c"
    },
    {
      "type": "ADVISORY",
      "url": "https://nvd.nist.gov/vuln/detail/CVE-2026-116795"
    },
    {
      "type": "WEB",
      "url": "https://github.com/le0pard/re2js/pull/59"
    },
    {
      "type": "WEB",
      "url": "https://github.com/le0pard/re2js/commit/dfdd947785dfa113bdc97416375c246a39458395"
    },
    {
      "type": "PACKAGE",
      "url": "https://github.com/le0pard/re2js"
    },
    {
      "type": "WEB",
      "url": "https://github.com/le0pard/re2js/releases/tag/2.8.7"
    }
  ],
  "schema_version": "1.4.0",
  "severity": [
    {
      "score": "CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:H",
      "type": "CVSS_V3"
    }
  ],
  "summary": "RE2JS: Quadratic-time denial of service in re2js lookbehind matching"
}

CVE-2026-116795 (GCVE-0-2026-116795)

Vulnerability from cvelistv5 – Published: 2026-10-28 17:14 – Updated: 2026-10-28 17:14

Title

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

Summary

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.

Severity

7.5 (High)


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

CWE

CWE-407 - Inefficient Algorithmic Complexity
CWE-1333 - Inefficient Regular Expression Complexity

Assigner

GitHub_M CNA under the mitre root

CNA scorecard C 72/100 over 7994 records in the last 180 days details

References

4 references

URL	Tags
https://github.com/le0pard/re2js/security/advisor…	x_refsource_CONFIRM
https://github.com/le0pard/re2js/pull/59	x_refsource_MISC
https://github.com/le0pard/re2js/commit/dfdd94778…	x_refsource_MISC
https://github.com/le0pard/re2js/releases/tag/2.8.7	x_refsource_MISC

Impacted products

1 product

Vendor	Product	Version
le0pard	re2js	Affected: >= 2.2.0, < 2.8.7

Show details on NVD website

JSON

To clipboard

{
  "containers": {
    "cna": {
      "affected": [
        {
          "product": "re2js",
          "vendor": "le0pard",
          "versions": [
            {
              "status": "affected",
              "version": "\u003e= 2.2.0, \u003c 2.8.7"
            }
          ]
        }
      ],
      "descriptions": [
        {
          "lang": "en",
          "value": "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."
        }
      ],
      "metrics": [
        {
          "cvssV3_1": {
            "attackComplexity": "LOW",
            "attackVector": "NETWORK",
            "availabilityImpact": "HIGH",
            "baseScore": 7.5,
            "baseSeverity": "HIGH",
            "confidentialityImpact": "NONE",
            "integrityImpact": "NONE",
            "privilegesRequired": "NONE",
            "scope": "UNCHANGED",
            "userInteraction": "NONE",
            "vectorString": "CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:H",
            "version": "3.1"
          }
        }
      ],
      "problemTypes": [
        {
          "descriptions": [
            {
              "cweId": "CWE-407",
              "description": "CWE-407: Inefficient Algorithmic Complexity",
              "lang": "en",
              "type": "CWE"
            }
          ]
        },
        {
          "descriptions": [
            {
              "cweId": "CWE-1333",
              "description": "CWE-1333: Inefficient Regular Expression Complexity",
              "lang": "en",
              "type": "CWE"
            }
          ]
        }
      ],
      "providerMetadata": {
        "dateUpdated": "2026-10-28T17:14:15.988Z",
        "orgId": "a0819718-46f1-4df5-94e2-005712e83aaa",
        "shortName": "GitHub_M"
      },
      "references": [
        {
          "name": "https://github.com/le0pard/re2js/security/advisories/GHSA-gg6h-894w-4m9c",
          "tags": [
            "x_refsource_CONFIRM"
          ],
          "url": "https://github.com/le0pard/re2js/security/advisories/GHSA-gg6h-894w-4m9c"
        },
        {
          "name": "https://github.com/le0pard/re2js/pull/59",
          "tags": [
            "x_refsource_MISC"
          ],
          "url": "https://github.com/le0pard/re2js/pull/59"
        },
        {
          "name": "https://github.com/le0pard/re2js/commit/dfdd947785dfa113bdc97416375c246a39458395",
          "tags": [
            "x_refsource_MISC"
          ],
          "url": "https://github.com/le0pard/re2js/commit/dfdd947785dfa113bdc97416375c246a39458395"
        },
        {
          "name": "https://github.com/le0pard/re2js/releases/tag/2.8.7",
          "tags": [
            "x_refsource_MISC"
          ],
          "url": "https://github.com/le0pard/re2js/releases/tag/2.8.7"
        }
      ],
      "source": {
        "advisory": "GHSA-gg6h-894w-4m9c",
        "discovery": "UNKNOWN"
      },
      "title": "RE2JS: Quadratic-time denial of service in re2js lookbehind matching"
    }
  },
  "cveMetadata": {
    "assignerOrgId": "a0819718-46f1-4df5-94e2-005712e83aaa",
    "assignerShortName": "GitHub_M",
    "cveId": "CVE-2026-116795",
    "datePublished": "2026-10-28T17:14:15.988Z",
    "dateReserved": "2026-10-26T21:53:35.168Z",
    "dateUpdated": "2026-10-28T17:14:15.988Z",
    "state": "PUBLISHED"
  },
  "dataType": "CVE_RECORD",
  "dataVersion": "5.2"
}

Sightings

Author	Source	Type	Date	Other

Nomenclature

Seen: The vulnerability was mentioned, discussed, or observed by the user.
Confirmed: The vulnerability has been validated from an analyst's perspective.
Published Proof of Concept: A public proof of concept is available for this vulnerability.
Exploited: The vulnerability was observed as exploited by the user who reported the sighting.
Patched: The vulnerability was observed as successfully patched by the user who reported the sighting.
Not exploited: The vulnerability was not observed as exploited by the user who reported the sighting.
Not confirmed: The user expressed doubt about the validity of the vulnerability.
Not patched: The vulnerability was not observed as successfully patched by the user who reported the sighting.

Vulnerability timeline

Sightings and recorded dates, grouped by day · UTC

Order JSON

Publication & reservation Sightings KEV catalogs Other timestamps

Loading timeline…

The MITRE ATT&CK techniques below are AI-generated suggestions, inferred from the description of the vulnerability by the CIRCL/vulnerability-attack-technique-classification-roberta-base model, served locally by ML-Gateway. They have not been verified by an analyst and are provided for guidance only.
The approach is described in our paper Mapping CVEs to MITRE ATT&CK Techniques: A Curated Gold-Set Classifier and the Limits of LLM-Assisted Label Expansion.
Browse all ATT&CK techniques and the vulnerabilities related to each.

Related by attack behaviour

Vulnerabilities whose description is nearest to this one in the vector space of the CIRCL/vulnerability-attack-technique-biencoder model. This is a similarity search over the bi-encoder space (plain cosine), not a classification, and it has no measured accuracy.

Action not permitted

GHSA-GG6H-894W-4M9C

Summary

Description

Root cause

Isolating control

Impact

Reproduction (copy-paste runnable)

CVE-2026-116795 (GCVE-0-2026-116795)

Tags

Sightings

Nomenclature

Vulnerability timeline

Related by attack behaviour