Skip to content

Quadratic regexp validation for ES2025 duplicate named capture groups #1445

Closed

Description

@Str1ckl4nd

Summary

acorn.parse appears to spend quadratic time in regexp validation for ES2025 duplicate named capture groups when the same group name appears across many disjoint regexp alternatives.

The input is accepted by the ES2025 duplicate-name semantics, but validation compares each later same-name group against all previous same-name groups.
With a compact regexp literal, the duplicate-name case becomes much slower than a same-size control that uses unique names.

Affected path

  • Observed on acorn 8.17.0.
  • Also observed on current master at 5b9d16c256b81682d2b26246d86387f1d78633e9.
  • Entry point: acorn.parse(source, { ecmaVersion: "latest" }).
  • Relevant path: regexp tokenization and pattern validation, especially acorn/src/regexp.js.

Reproduction

From the source checkout repository root, save this as verify-duplicate-names.mjs and run it with Node.
The script imports ./acorn/src/index.js, so it is meant for a repository checkout rather than an installed package:

import {performance} from "node:perf_hooks"
import {parse, version} from "./acorn/src/index.js"

function term(depth, name) {
  return "(?:".repeat(depth) + `(?<${name}>a)` + ")".repeat(depth)
}

function payload(count, depth, duplicateName) {
  const body = Array.from({length: count}, (_, i) => {
    return term(depth, duplicateName ? "x" : `x${i}`)
  }).join("|")

  return `/${body}/v`
}

function measure(label, source) {
  const started = performance.now()
  parse(source, {ecmaVersion: "latest"})
  const elapsedMs = performance.now() - started
  return {label, bytes: source.length, elapsedMs}
}

parse("/a/", {ecmaVersion: "latest"})

const count = Number(process.env.COUNT || 240)
const depth = Number(process.env.DEPTH || 240)

const control = payload(count, depth, false)
const duplicateCase = payload(count, depth, true)

const controlResult = measure("unique capture names control", control)
const duplicateResult = measure("duplicate capture names", duplicateCase)
const ratio = duplicateResult.elapsedMs / Math.max(controlResult.elapsedMs, 1)

const result = {
  acornVersion: version,
  count,
  depth,
  control: {
    bytes: controlResult.bytes,
    elapsedMs: Number(controlResult.elapsedMs.toFixed(3))
  },
  duplicateCase: {
    bytes: duplicateResult.bytes,
    elapsedMs: Number(duplicateResult.elapsedMs.toFixed(3))
  },
  ratio: Number(ratio.toFixed(2))
}

console.log(JSON.stringify(result, null, 2))

if (duplicateResult.elapsedMs < 500) {
  throw new Error(`Expected duplicate-name parsing to take at least 500 ms, got ${duplicateResult.elapsedMs.toFixed(3)} ms`)
}

if (ratio < 20) {
  throw new Error(`Expected duplicate-name parsing to be at least 20x slower than the control, got ${ratio.toFixed(2)}x`)
}

Command:

node verify-duplicate-names.mjs

The example uses the /v flag to exercise the ES2025 path. In local checks, /u showed the same pattern, while omitting a Unicode-style flag made parsing slower because the regexp was validated more than once.
The 500 ms and 20x checks are only a coarse oracle for the reproduction script; the printed ratio is the main value to compare across machines.

Observed result

In a Docker-based check using node:22-bookworm-slim against acorn 8.17.0 / 5b9d16c256b81682d2b26246d86387f1d78633e9, the same generation and parse logic produced:

{
  "acornVersion": "8.17.0",
  "count": 240,
  "depth": 240,
  "control": {
    "bytes": 232932,
    "elapsedMs": 36.952
  },
  "duplicateCase": {
    "bytes": 232322,
    "elapsedMs": 3014.735
  },
  "ratio": 81.59
}

The exact numbers vary by machine, but the duplicate-name case consistently takes much longer than the same-size unique-name control.

Expected result

Duplicate named capture groups across disjoint alternatives are valid ES2025 syntax, but validating them should scale much closer to the same-size unique-name control.

Implementation note

The expensive behavior seems to come from the duplicate-name validation path.
For each same-name group, regexp_groupSpecifier checks every previous branch id stored for that name.
Each separatedFrom check then walks the two branch ancestry chains.
With many same-name alternatives, this makes the total validation work grow much faster than input size.

Relevant areas:

  • acorn/src/tokenize.js: regexp literals are validated before the token is returned.
  • acorn/src/regexp.js: ES2025 branch tracking is enabled for duplicate named capture groups.
  • acorn/src/regexp.js: duplicate names call altID.separatedFrom(state.branchID) for prior same-name branch ids.
  • acorn/src/regexp.js: separatedFrom walks both branch ancestry chains.

Reporters:

Activity

  1. marijnh commented on Jul 2, 2026

    @marijnh
    Member

    What prompted this issue? Did you run into a real program where this is a problem? Or are you worried about it being used as a denial-of-service vector? Or did you just let loose an agent on the code looking for random quadratic behavior?

  2. Str1ckl4nd commented on Jul 2, 2026

    @Str1ckl4nd
    Author

    Thanks for the question.

    Yes, this was found through automated exploration, but it was not a scan specifically aimed at denial-of-service reports or at filing arbitrary quadratic behaviors. The issue was manually reviewed before filing, and the reproduction was reduced into a concrete PoC with observed results.

    We chose to file this as a public performance/resource-usage bug, not as a security advisory, because the impact depends on downstream usage: it matters mainly when Acorn is used to parse untrusted JavaScript with ecmaVersion: 2025 or latest. Similar algorithmic-complexity and parser resource-exhaustion issues have been accepted and fixed in other codebases, so we considered it reasonable to report this and let the maintainers decide how it should be classified.

    That said, we understand that whether this behavior is an expected tradeoff, a normal bug, or a vulnerability is ultimately a maintainer decision. If you consider this within the expected behavior or outside Acorn’s scope to optimize, we will accept that. We will also use your feedback to improve our internal triage process so that we avoid sending reports that are not useful to maintainers.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions