How Denial of Service via Exponential Complexity Happens in Node.js and How to Fix It

How Denial of Service via Exponential Complexity Happens in Node.js and How to Fix It

Vulnerability at a Glance

Introduction

The cdk-eregs/package-lock.json file locks the entire transitive dependency tree for an AWS CDK infrastructure project. Buried several layers deep in that tree was brace-expansion, a utility that turns shell-style brace patterns like file.{js,ts,css} into lists of strings. It is a foundational package—pulled in by glob, minimatch, and dozens of other widely used tools—which makes it both invisible to most developers and dangerous when it misbehaves.

Trivy's dependency scanner flagged brace-expansion in this repository because the version in use contained a flaw that allows exponential-time processing of crafted brace patterns. An attacker who can influence the strings passed to any code path that eventually calls brace-expansion—even indirectly through a glob or file-watcher—can cause the Node.js event loop to hang indefinitely, effectively taking down the process.

The Vulnerability Explained

What is brace expansion?

Brace expansion converts a compact pattern into a list of strings:

// Input
'{a,b,c}.{js,ts}'

// Output
['a.js', 'a.ts', 'b.js', 'b.ts', 'c.js', 'c.ts']

This is useful for glob matching, file discovery, and CLI tooling. The problem arises when the expansion algorithm is applied to nested or repeated brace groups.

The exponential growth problem

Consider what happens with repeated nested alternatives:

{a,b}{a,b}{a,b}  →  8 strings   (2³)
{a,b}{a,b}...×10 →  1,024 strings (2¹⁰)
{a,b}{a,b}...×30 →  1,073,741,824 strings (2³⁰)

A 60-character input string produces over one billion expansion results. The vulnerable versions of brace-expansion attempt to generate the full Cartesian product in memory before returning, meaning both CPU time and memory consumption grow exponentially with the number of brace groups.

The specific algorithmic pattern that causes this is a recursive Cartesian-product expansion without any bound on output size or recursion depth. Internally, the library builds the result by calling something equivalent to:

// Simplified pseudocode of the vulnerable pattern
function expand(pattern) {
  const parts = parse(pattern); // splits on commas and nested braces
  return cartesianProduct(parts.map(expand)); // unbounded recursion + product
}

Each level of nesting multiplies the output size by the number of alternatives at that level. There is no guard that says "stop if output exceeds N items."

What does the vulnerable code look like in context?

The cdk-eregs/package-lock.json (before the fix) contained entries like:

"brace-expansion": {
  "version": "1.1.11",
  ...
}

or

"brace-expansion": {
  "version": "2.0.1",
  ...
}

These transitive versions—pulled in by tools like glob and minimatch which are themselves dependencies of CDK tooling—were all below the patched thresholds.

Attack scenario for this repository

The cdk-eregs project is an AWS CDK application. CDK's build and synthesis pipeline uses glob patterns extensively to discover assets, Lambda function bundles, and configuration files. If any part of that pipeline accepts external input that feeds into a glob pattern—such as a CI/CD parameter, an environment variable, or a configuration file read from an S3 bucket—an attacker with write access to that input could inject a pattern like:

{a,b,c,d,e}{a,b,c,d,e}{a,b,c,d,e}{a,b,c,d,e}{a,b,c,d,e}{a,b,c,d,e}

This 42-character string would generate 15,625 expansions (5⁶). Extend it to ten groups and you reach nearly 10 million. The CDK synthesis process—or any Lambda that calls glob with this input—would hang, causing deployment pipelines to time out or Lambda invocations to exhaust their memory limit.

Even without a direct injection path, the vulnerability is still relevant: the scanner assessment notes it is "present in dependency tree, not confirmed reachable," but the attack surface of a CDK project spans build tools, test runners, and local developer environments—all of which run this code.

The Fix

What changed

The fix introduced an npm overrides block in cdk-eregs/package.json:

Before (package.json — no overrides):

{
  "name": "cdk-eregs",
  "dependencies": {
    "fs-extra": "11.3.1",
    "path": "0.12.7",
    "source-map-support": "0.5.21"
  }
}

After (package.json — with override):

{
  "name": "cdk-eregs",
  "dependencies": {
    "fs-extra": "11.3.1",
    "path": "0.12.7",
    "source-map-support": "0.5.21"
  },
  "overrides": {
    "brace-expansion": "5.0.9"
  }
}

The overrides field (introduced in npm v8.3) forces every package in the dependency tree—regardless of what version they declare as their own dependency—to use brace-expansion@5.0.9. This is the canonical way to patch a transitive dependency vulnerability without waiting for every intermediate package to release an update.

Why this specific version?

The patched versions are 1.1.16, 2.1.2, and 5.0.7+. The fix in each adds a guard against combinatorial explosion—either by capping the maximum number of expansions, by detecting pathological patterns early and returning them unexpanded, or by rewriting the expansion loop to avoid building the full product set in memory.

By pinning to 5.0.9, the override ensures the fix is applied even if a transitive dependency specifies ^1.x or ^2.x, since npm's override mechanism replaces the resolved version regardless of the semver range declared by the dependent package.

The package-lock.json impact

After adding the override and running npm install, the package-lock.json is regenerated so that all entries for brace-expansion—regardless of which package required them—resolve to 5.0.9. The lock file is the authoritative record that the scanner (Trivy) reads, so this change directly eliminates the CVE finding.

Prevention & Best Practices

1. Audit transitive dependencies regularly

brace-expansion is a zero-direct-dependency package that almost no project lists explicitly, yet it appears in hundreds of node_modules trees. Run:

npm audit
# or
npx trivy fs . --scanners vuln

in CI on every pull request to catch newly disclosed CVEs before they reach production.

2. Use overrides (npm) or resolutions (Yarn) for transitive fixes

When a vulnerability lives in a transitive dependency you don't control directly, the overrides field is the right tool:

"overrides": {
  "vulnerable-package": ">=patched-version"
}

For Yarn Berry:

"resolutions": {
  "vulnerable-package": "patched-version"
}

3. Validate and sanitize brace patterns from external sources

If your application accepts glob patterns from users or external configuration, apply a length cap and a nesting-depth check before passing them to any expansion library:

const MAX_PATTERN_LENGTH = 256;
const MAX_BRACE_DEPTH = 3;

function safeBraceExpand(pattern) {
  if (pattern.length > MAX_PATTERN_LENGTH) {
    throw new Error('Pattern too long');
  }
  const depth = (pattern.match(/\{/g) || []).length;
  if (depth > MAX_BRACE_DEPTH) {
    throw new Error('Pattern nesting too deep');
  }
  return braceExpansion(pattern);
}

This is a defense-in-depth measure; upgrading the library is still the primary fix.

4. Pin dependency versions in lock files and commit them

Always commit package-lock.json to version control. This ensures that npm ci in CI/CD uses exactly the versions you tested, and that security scanners like Trivy can read the resolved tree accurately.

5. Reference standards

• CWE-1333: Inefficient Regular Expression Complexity — the authoritative classification for this class of algorithmic DoS
• OWASP: Denial of Service Cheat Sheet
• Node.js Security Best Practices: validate all inputs that flow into pattern-matching or file-system APIs

Key Takeaways

• brace-expansion is a hidden risk in virtually every Node.js project that uses glob or minimatch—check your lock file, not just your direct dependencies.
• A 60-character crafted string can generate billions of expansions; the attack payload is trivially small, making it easy to embed in configuration files or CI parameters.
• The overrides field in package.json is the correct surgical fix for transitive dependency CVEs—it forces the patched version across the entire dependency tree without touching unrelated packages.
• Trivy correctly identified this in cdk-eregs/package-lock.json even though brace-expansion is not a direct dependency, demonstrating why scanning the full resolved lock file matters more than scanning package.json alone.
• Patched versions (1.1.16, 2.1.2, 5.0.7+) add complexity bounds to the expansion algorithm; upgrading is preferable to application-level workarounds because the fix is in the right place.

How Orbis AppSec Detected This

• Source: The cdk-eregs/package-lock.json file, which resolves transitive dependency versions including brace-expansion at a vulnerable version, is read during CDK build and synthesis operations that process file-system glob patterns.
• Sink: Any call to braceExpansion(pattern) within the resolved brace-expansion module—invoked transitively through glob → minimatch → brace-expansion—where pattern contains repeated or deeply nested brace groups.
• Missing control: No upper bound on the number of expansions or recursion depth in the brace-expansion expansion algorithm prior to versions 1.1.16 / 2.1.2 / 5.0.7.
• CWE: CWE-1333 – Inefficient Regular Expression Complexity (applies broadly to algorithms with super-linear time growth on adversarial inputs).
• Fix: An npm overrides directive was added to cdk-eregs/package.json pinning brace-expansion to 5.0.9 across the entire dependency tree, and package-lock.json was regenerated to reflect the patched resolution.

Orbis AppSec automatically detected this vulnerability and opened a pull request with the fix. Try Orbis AppSec on your repositories to find and fix issues like this automatically.

Conclusion

CVE-2026-13149 is a sharp reminder that the most dangerous vulnerabilities are often the quietest ones. brace-expansion is a tiny utility with no dependencies of its own, yet its presence in nearly every Node.js project's transitive tree makes a flaw in its core algorithm a systemic risk. Exponential-complexity attacks are particularly insidious because the payload is small, the impact is immediate, and the vulnerable code path is rarely something developers think to audit.

The fix here—a single overrides block in package.json—is minimal, surgical, and does not affect any valid input. It is also a template for how to handle transitive dependency CVEs in npm projects generally. Pair it with automated scanning in CI, commit your lock files, and validate pattern inputs at application boundaries, and you have a robust defense against this class of vulnerability.

References

• CWE-1333: Inefficient Regular Expression Complexity
• OWASP Denial of Service Cheat Sheet
• npm Overrides Documentation
• brace-expansion on npm
• Semgrep rules for ReDoS / algorithmic complexity
• fix: upgrade brace-expansion to 5.0.7, 1.1.16, 2.1.2 (CVE-2026-13149)