High, CVSS 7.5npmAmendedPublished
RE2JS: Quadratic-time denial of service in re2js lookbehind matching
CVE-2026-116795 · GHSA-gg6h-894w-4m9c
- Affected
- npm re2js >= 2.2.0, < 2.8.7
- Fixed in
- 2.8.7· Vendor fix available
- Issue
- 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`)…
Recommended action: Upgrade to 2.8.7 or later, then redeploy and verify.A vendor fix does not resolve your finding until you verify it in your own systems.