Skip to content
Heist/ feed
MediumFix available

brace-expansion: Quadratic-time expansion of the `{a},b}` rewrite causes CPU denial of service

Type: advisorySource: OSV1 source record

### Summary Expanding `{a},b}`-shaped input takes time quadratic in the number of literal `}` characters, blocking the event loop. Bash preserves a quirk where a brace group followed by a comma set still expands (`{a},b}`). The parser implements this by rewriting the string and restarting the scan. Each pass absorbs exactly one `}` and re-scans from the beginning, so `n` trailing braces cost `n` full passes. ### Reproduction ```js const build = n => '{a}' + '}'.repeat(n) + ',z}' for (const n of [8000, 16000, 32000, 64000, 128000]) { const t = Date.now() expand(build(n)) console.log(n, Date.now() - t + 'ms') } ``` | n | input | time | results | |---|---|---|---| | 8,000 | 8 KB | 110 ms | 2 | | 16,000 | 16 KB | 446 ms | 2 | | 32,000 | 32 KB | 1.7 s | 2 | | 64,000 | 64 KB | 6.9 s | 2 | | 128,000 | 128 KB | **27.7 s** | 2 | `ms/n^2` is flat at ~1.7 and each doubling of `n` costs exactly 4.0x - quadratic. 128 KB of input blocks the event loop for nearly half a minute to produce two results. ### Mechanism Instrumenting the rewrite branch confirms it runs exactly `n + 1` times, once per literal `}`, each re-scanning the whole string. There is a second multiplier. The rewrite replaces the group's closing `}` with the internal `escClose` sentinel, which is `'\0CLOSE' + Math.random() + '\0'` - about 25 characters. The working string therefore *grows* by ~25 characters on every pass: | n | input length | final string length | |---|---|---| | 1,000 | 1,006 | 26,006 | | 8,000 | 8,006 | 20

Announced Source revision 1
Original source ↗

GHSA-q2hr-2g5m-vwhr

Primary source · Revision 1

Imported from structured advisory data. Source references identify upstream records or fields; verify affected versions and your deployed configuration.

Security context

Source reference: osv:GHSA-q2hr-2g5m-vwhr

brace-expansion

Source reference: /affected/0/package/name

Affected versions
Not stated in this record
Fixed versions
5.0.12

Source reference: /affected/0/ranges

Prerequisites
Not stated in this record

brace-expansion

Source reference: /affected/1/package/name

Affected versions
Not stated in this record
Fixed versions
3.0.9

Source reference: /affected/1/ranges

Prerequisites
Not stated in this record

brace-expansion

Source reference: /affected/2/package/name

Affected versions
Not stated in this record
Fixed versions
2.1.7

Source reference: /affected/2/ranges

Prerequisites
Not stated in this record

brace-expansion

Source reference: /affected/3/package/name

Affected versions
Not stated in this record
Fixed versions
1.1.21

Source reference: /affected/3/ranges

Prerequisites
Not stated in this record

Structured affected-version data

Original package identities and version rules from this source.

[
  {
    "ranges": [
      {
        "type": "SEMVER",
        "events": [
          {
            "introduced": "4.0.0"
          },
          {
            "fixed": "5.0.12"
          }
        ]
      }
    ],
    "package": {
      "name": "brace-expansion",
      "purl": "pkg:npm/brace-expansion",
      "ecosystem": "npm"
    },
    "database_specific": {
      "source": "https://github.com/github/advisory-database/blob/main/advisories/github-reviewed/2026/09/GHSA-q2hr-2g5m-vwhr/GHSA-q2hr-2g5m-vwhr.json"
    }
  },
  {
    "ranges": [
      {
        "type": "SEMVER",
        "events": [
          {
            "introduced": "3.0.0"
          },
          {
            "fixed": "3.0.9"
          }
        ]
      }
    ],
    "package": {
      "name": "brace-expansion",
      "purl": "pkg:npm/brace-expansion",
      "ecosystem": "npm"
    },
    "database_specific": {
      "source": "https://github.com/github/advisory-database/blob/main/advisories/github-reviewed/2026/09/GHSA-q2hr-2g5m-vwhr/GHSA-q2hr-2g5m-vwhr.json"
    }
  },
  {
    "ranges": [
      {
        "type": "SEMVER",
        "events": [
          {
            "introduced": "2.0.0"
          },
          {
            "fixed": "2.1.7"
          }
        ]
      }
    ],
    "package": {
      "name": "brace-expansion",
      "purl": "pkg:npm/brace-expansion",
      "ecosystem": "npm"
    },
    "database_specific": {
      "source": "https://github.com/github/advisory-database/blob/main/advisories/github-reviewed/2026/09/GHSA-q2hr-2g5m-vwhr/GHSA-q2hr-2g5m-vwhr.json"
    }
  },
  {
    "ranges": [
      {
        "type": "SEMVER",
        "events": [
          {
            "introduced": "0"
          },
          {
            "fixed": "1.1.21"
          }
        ]
      }
    ],
    "package": {
      "name": "brace-expansion",
      "purl": "pkg:npm/brace-expansion",
      "ecosystem": "npm"
    },
    "database_specific": {
      "source": "https://github.com/github/advisory-database/blob/main/advisories/github-reviewed/2026/09/GHSA-q2hr-2g5m-vwhr/GHSA-q2hr-2g5m-vwhr.json"
    }
  }
]
Related CVEs
CVE-2026-102277

Source reference: /aliases

Publisher severity

No explicit severity was provided.

Linked CVE context

These ratings describe the referenced vulnerabilities and products. They are not a severity rating for every application using this dependency.

CVE-2026-102277 · Medium

brace-expansion

Event
#33267 · Revision 1
Added to Heist Feed
Publisher date
Read the original announcement