{"id":"CVE-2026-116795","aliases":["GHSA-gg6h-894w-4m9c"],"title":"RE2JS: Quadratic-time denial of service in re2js lookbehind matching","titleSource":"GitHub_M","descriptionSource":"OSV","declaredSeverity":"HIGH","description":"### 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 > 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 > 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('(?<=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 => linear, ~4 => quadratic)');\nconsole.log(ratio > 3 ? 'PASS  quadratic scaling confirmed on the REAL published package' : 'FAIL  scaling looks linear');\nprocess.exit(ratio > 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 `(?<=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.","severity":"high","score":7.5,"published":"2026-10-28T17:14:15.988Z","modified":"2026-10-28T21:30:03.886Z","withdrawn":false,"knownExploited":false,"affected":[{"ecosystem":"npm","name":"re2js","sources":[{"name":"OSV · GHSA-gg6h-894w-4m9c","url":"https://osv.dev/vulnerability/GHSA-gg6h-894w-4m9c"}],"ranges":[{"events":[{"introduced":"2.2.0"},{"fixed":"2.8.7"}],"type":"SEMVER"}],"versions":[],"fixed":["2.8.7"]}],"sourceAffected":[],"references":["https://github.com/le0pard/re2js/security/advisories/GHSA-gg6h-894w-4m9c","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://nvd.nist.gov/vuln/detail/CVE-2026-116795","https://github.com/le0pard/re2js"],"sources":[{"name":"CVE","id":"CVE-2026-116795","modified":"2026-10-28T17:14:15.988Z","url":"https://www.cve.org/CVERecord?id=CVE-2026-116795"},{"name":"OSV","id":"GHSA-gg6h-894w-4m9c","modified":"2026-10-28T21:30:03.886208060Z","url":"https://osv.dev/vulnerability/GHSA-gg6h-894w-4m9c"}],"assessments":[{"source":"GitHub_M","vector":"CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:H","score":7.5},{"source":"OSV","vector":"CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:H","score":7.5}],"cve":{"records":[{"id":"CVE-2026-116795","source":"GitHub_M","state":"PUBLISHED","reasons":[],"replacements":[],"disputed":false,"unsupportedWhenAssigned":false,"reserved":"2026-10-26T21:53:35.168Z","published":"2026-10-28T17:14:15.988Z","modified":"2026-10-28T17:14:15.988Z"}],"publishers":[{"name":"GitHub_M","role":"CNA","organizationId":"a0819718-46f1-4df5-94e2-005712e83aaa","modified":"2026-10-28T17:14:15.988Z"}],"references":[{"url":"https://github.com/le0pard/re2js/security/advisories/GHSA-gg6h-894w-4m9c","tags":["x_refsource_CONFIRM"],"source":"GitHub_M"},{"url":"https://github.com/le0pard/re2js/pull/59","tags":["x_refsource_MISC"],"source":"GitHub_M"},{"url":"https://github.com/le0pard/re2js/commit/dfdd947785dfa113bdc97416375c246a39458395","tags":["x_refsource_MISC"],"source":"GitHub_M"},{"url":"https://github.com/le0pard/re2js/releases/tag/2.8.7","tags":["x_refsource_MISC"],"source":"GitHub_M"}],"weaknesses":[{"id":"CWE-407","description":"CWE-407: Inefficient Algorithmic Complexity","source":"GitHub_M"},{"id":"CWE-1333","description":"CWE-1333: Inefficient Regular Expression Complexity","source":"GitHub_M"}],"applicability":[],"prioritization":[]},"products":[{"vendor":"le0pard","name":"re2js","platforms":[],"versions":[{"version":">= 2.2.0, < 2.8.7","status":"affected"}],"cpes":[],"source":"GitHub_M","url":"https://www.cve.org/CVERecord?id=CVE-2026-116795"}],"remediation":[],"observedAt":"2026-10-29T15:05:42.873Z","kev":{"status":"not-listed","checkedAt":"2026-10-31T13:10:31.620Z"},"coverage":[{"source":"NVD","status":"no-result","checkedAt":"2026-10-28T17:45:35.610Z","attemptedAt":"2026-10-28T17:45:35.610Z"},{"source":"GHSA","status":"no-result","checkedAt":"2026-10-28T17:45:36.258Z","attemptedAt":"2026-10-28T17:45:36.258Z"},{"source":"EUVD","status":"refresh-failed","attemptedAt":"2026-10-28T17:45:34.314Z"},{"source":"EPSS","status":"no-result","checkedAt":"2026-10-28T17:45:35.600Z","attemptedAt":"2026-10-28T17:45:35.600Z"}],"evidence":[],"aiSummary":null}