GHSA-3JXR-9VMJ-R5CP
Vulnerability from github – Published: 2026-07-20 20:51 – Updated: 2026-07-20 20:51Summary
brace-expansion's expand() exhibits exponential-time - O(2ⁿ) - behavior in the number of consecutive non-expanding {} groups. A short, all-ASCII input (~90 bytes/30 groups) blocks the calling thread for minutes; a slightly longer input hangs it effectively indefinitely. Because the dominant consumers run on Node's single-threaded event loop, one small input can fully stall a worker/process.
In expand_, post is computed unconditionally at the top of the function, before the early-return branches that don't use it:
const post = m.post.length ? expand_(m.post, max, false) : ['']; // always recurses
...
if (!isSequence && !isOptions) {
if (m.post.match(/,(?!,).*\}/)) {
str = m.pre + '{' + m.body + escClose + m.post;
return expand_(str, max, true); // restart — `post` discarded
}
return [str];
}
For input like a{},{},…, the first {} is non-expanding, so control reaches the {a},b} rewrite branch - but expand_ has already recursed into post over the entire remaining tail, only to throw the result away.
Each level therefore spawns two recursive expansions over essentially the same remaining work: T(n) = 2·T(n−1) ⇒ O(2ⁿ).
The max option does not mitigate this: max only bounds the output-building loops; neither the post recursion nor the rewrite recursion consults it.
Measured on 5.0.6:
| groups (n) | input bytes | time |
|---|---|---|
| 20 | 60 | 130 ms |
| 24 | 72 | 1.9 s |
| 26 | 78 | 7.8 s |
| 30 (PoC) | 90 | ~2 min |
Proof of concept
const { expand } = require('brace-expansion');
// 30 non-expanding groups, ~90 bytes — blocks for minutes:
expand('a{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{}');
Impact
Any application that passes attacker-influenced strings to brace-expansion.expand() - directly or transitively via minimatch/glob brace patterns - can be driven into a multi-minute-to-indefinite CPU hang by a tiny request, denying service on that thread/process.
Remediation
Upgrade to a patched release. The fix: 1. Defers computing post until after the early-return branches (and computes it locally in the $-suffix branch), so post is only expanded when a brace set actually expands and the value is used. This alone removes the exponential. 1. Converts the {a},b} rewrite from recursion to an in-function loop, so a long run of rewrites cannot grow the call stack.
Verified: the PoC drops from ~2 min to 0.55 ms, 5,000 groups complete in ~344 ms, and output is identical to 5.0.6 across a behavioral-equivalence suite (sequences, padding, $-prefix, a{},b}c, {},a}b, x{{a,b}}y, etc.). Post-fix complexity is ~O(n²) on this input class - acceptable for the security fix; a linear rewrite can be a non-urgent follow-up.
If immediate upgrade isn't possible, avoid passing untrusted input to expand() / glob brace patterns, or run such expansion under a timeout/worker.
{
"affected": [
{
"package": {
"ecosystem": "npm",
"name": "brace-expansion"
},
"ranges": [
{
"events": [
{
"introduced": "3.0.0"
},
{
"fixed": "5.0.7"
}
],
"type": "ECOSYSTEM"
}
]
},
{
"package": {
"ecosystem": "npm",
"name": "brace-expansion"
},
"ranges": [
{
"events": [
{
"introduced": "0"
},
{
"fixed": "1.1.16"
}
],
"type": "ECOSYSTEM"
}
]
},
{
"package": {
"ecosystem": "npm",
"name": "brace-expansion"
},
"ranges": [
{
"events": [
{
"introduced": "2.0.0"
},
{
"fixed": "2.1.2"
}
],
"type": "ECOSYSTEM"
}
]
}
],
"aliases": [
"CVE-2026-13149"
],
"database_specific": {
"cwe_ids": [
"CWE-400",
"CWE-407"
],
"github_reviewed": true,
"github_reviewed_at": "2026-07-20T20:51:09Z",
"nvd_published_at": "2026-06-30T10:16:34Z",
"severity": "HIGH"
},
"details": "### Summary\nbrace-expansion\u0027s expand() exhibits exponential-time - O(2\u207f) - behavior in the number of consecutive non-expanding {} groups. A short, all-ASCII input (~90 bytes/30 groups) blocks the calling thread for minutes; a slightly longer input hangs it effectively indefinitely. Because the dominant consumers run on Node\u0027s single-threaded event loop, one small input can fully stall a worker/process.\n\nIn `expand_`, `post` is computed unconditionally at the top of the function, before the early-return branches that don\u0027t use it:\n```js\nconst post = m.post.length ? expand_(m.post, max, false) : [\u0027\u0027]; // always recurses\n ...\nif (!isSequence \u0026\u0026 !isOptions) {\n if (m.post.match(/,(?!,).*\\}/)) {\n str = m.pre + \u0027{\u0027 + m.body + escClose + m.post;\n return expand_(str, max, true); // restart \u2014 `post` discarded\n }\n return [str];\n}\n```\n\nFor input like a{},{},\u2026, the first {} is non-expanding, so control reaches the {a},b} rewrite branch - but `expand_` has already recursed into post over the entire remaining tail, only to throw the result away.\nEach level therefore spawns two recursive expansions over essentially the same remaining work: `T(n) = 2\u00b7T(n\u22121) \u21d2 O(2\u207f)`.\n\nThe max option does not mitigate this: max only bounds the output-building loops; neither the post recursion nor the rewrite recursion consults it.\n \nMeasured on 5.0.6:\n\n| groups (n) | input bytes | time |\n|---|---|---|\n| 20 | 60 | 130 ms |\n| 24 | 72 | 1.9 s |\n| 26 | 78 | 7.8 s |\n| 30 (PoC) | 90 | ~2 min |\n\n### Proof of concept\n```js\nconst { expand } = require(\u0027brace-expansion\u0027);\n// 30 non-expanding groups, ~90 bytes \u2014 blocks for minutes:\nexpand(\u0027a{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{}\u0027);\n```\n\n### Impact\n\nAny application that passes attacker-influenced strings to brace-expansion.expand() - directly or transitively via minimatch/glob brace patterns - can be driven into a multi-minute-to-indefinite CPU hang by a tiny request, denying service on that thread/process.\n\n### Remediation\n\nUpgrade to a patched release. The fix:\n1. Defers computing post until after the early-return branches (and computes it locally in the $-suffix branch), so post is only expanded when a brace set actually expands and the value is used. This alone removes the exponential.\n1. Converts the {a},b} rewrite from recursion to an in-function loop, so a long run of rewrites cannot grow the call stack.\n\nVerified: the PoC drops from ~2 min to 0.55 ms, 5,000 groups complete in ~344 ms, and output is identical to 5.0.6 across a behavioral-equivalence suite (sequences, padding, $-prefix, a{},b}c, {},a}b, x{{a,b}}y, etc.). Post-fix complexity is ~O(n\u00b2) on this input class - acceptable for the security fix; a linear rewrite can be a non-urgent follow-up.\n\nIf immediate upgrade isn\u0027t possible, avoid passing untrusted input to expand() / glob brace patterns, or run such expansion under a timeout/worker.",
"id": "GHSA-3jxr-9vmj-r5cp",
"modified": "2026-07-20T20:51:10Z",
"published": "2026-07-20T20:51:09Z",
"references": [
{
"type": "WEB",
"url": "https://github.com/juliangruber/brace-expansion/security/advisories/GHSA-3jxr-9vmj-r5cp"
},
{
"type": "ADVISORY",
"url": "https://nvd.nist.gov/vuln/detail/CVE-2026-13149"
},
{
"type": "WEB",
"url": "https://github.com/juliangruber/brace-expansion/pull/122"
},
{
"type": "WEB",
"url": "https://github.com/juliangruber/brace-expansion/pull/123"
},
{
"type": "WEB",
"url": "https://github.com/juliangruber/brace-expansion/commit/835d6be91201122d9adffb0c0c8c094189ace265"
},
{
"type": "WEB",
"url": "https://github.com/juliangruber/brace-expansion/commit/c7e33ec13ac1a684c116720843ce24e208611754"
},
{
"type": "WEB",
"url": "https://github.com/juliangruber/brace-expansion/commit/d74e63030c012e3b7ae81657b8d665619cd51b95"
},
{
"type": "PACKAGE",
"url": "https://github.com/juliangruber/brace-expansion"
},
{
"type": "WEB",
"url": "https://github.com/juliangruber/brace-expansion/releases/tag/v1.1.16"
},
{
"type": "WEB",
"url": "https://github.com/juliangruber/brace-expansion/releases/tag/v2.1.2"
},
{
"type": "WEB",
"url": "https://github.com/juliangruber/brace-expansion/releases/tag/v5.0.7"
},
{
"type": "WEB",
"url": "https://www.npmjs.com/package/brace-expansion"
}
],
"schema_version": "1.4.0",
"severity": [
{
"score": "CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:L",
"type": "CVSS_V3"
},
{
"score": "CVSS:4.0/AV:N/AC:L/AT:N/PR:N/UI:N/VC:N/VI:N/VA:H/SC:N/SI:N/SA:N/E:P/S:N/AU:Y/R:U/V:D/RE:M/U:Amber",
"type": "CVSS_V4"
}
],
"summary": "brace-expansion: DoS via exponential-time expansion of consecutive non-expanding {} groups"
}
Sightings
| Author | Source | Type | Date | Other |
|---|
Nomenclature
- Seen: The vulnerability was mentioned, discussed, or observed by the user.
- Confirmed: The vulnerability has been validated from an analyst's perspective.
- Published Proof of Concept: A public proof of concept is available for this vulnerability.
- Exploited: The vulnerability was observed as exploited by the user who reported the sighting.
- Patched: The vulnerability was observed as successfully patched by the user who reported the sighting.
- Not exploited: The vulnerability was not observed as exploited by the user who reported the sighting.
- Not confirmed: The user expressed doubt about the validity of the vulnerability.
- Not patched: The vulnerability was not observed as successfully patched by the user who reported the sighting.
The approach is described in our paper Mapping CVEs to MITRE ATT&CK Techniques: A Curated Gold-Set Classifier and the Limits of LLM-Assisted Label Expansion.
Browse all ATT&CK techniques and the vulnerabilities related to each.
Related by attack behaviour
Vulnerabilities whose description is nearest to this one in the vector space of the CIRCL/vulnerability-attack-technique-biencoder model. This is a similarity search over the bi-encoder space (plain cosine), not a classification, and it has no measured accuracy.