How Denial of Service via Exponential Time Complexity happens in brace-expansion and how to fix it

Introduction

In this project's dependency tree, Trivy flagged a high-severity vulnerability lurking in yarn.lock: the brace-expansion package at versions 1.1.18, 2.1.1, and 5.0.6 contained CVE-2026-13149—a Denial of Service vulnerability caused by exponential time complexity in the brace expansion algorithm.

The brace-expansion package is a foundational dependency used by glob matching libraries like minimatch and micromatch, which in turn power countless build tools, file watchers, and CLI utilities. When an attacker can influence input that flows through brace expansion—such as file patterns in configuration or user-provided glob strings—they could craft patterns that cause the application to hang indefinitely.

Looking at the vulnerable dependency chain in yarn.lock:

"brace-expansion@npm:^1.1.7":
  version: 1.1.18

"brace-expansion@npm:^2.0.1, brace-expansion@npm:^2.0.2":
  version: 2.1.1

"brace-expansion@npm:^5.0.5":
  version: 5.0.6

Multiple semver ranges were resolving to vulnerable versions, creating several attack vectors throughout the dependency tree.

The Vulnerability Explained

Brace expansion is a shell-like feature that expands patterns like {a,b,c} into a b c or {1..5} into 1 2 3 4 5. The brace-expansion npm package implements this functionality for JavaScript applications.

How Exponential Complexity Attacks Work

The vulnerability occurs when the parsing algorithm processes deeply nested or specially crafted brace patterns. Consider a pattern like:

{a{b{c{d{e{f{g{h{i{j}}}}}}}}}

Each level of nesting can cause the algorithm to explore an exponentially growing number of combinations. In vulnerable versions, the algorithm lacks proper safeguards against this explosion, leading to:

1. CPU exhaustion: The event loop blocks while processing the malicious pattern
2. Memory pressure: Intermediate results accumulate exponentially
3. Application freeze: The Node.js process becomes unresponsive

Real-World Attack Scenario

Imagine this application uses a glob library (which depends on brace-expansion) to process user-provided file patterns—perhaps in a file upload feature, build configuration, or search functionality:

const minimatch = require('minimatch');

// User-provided pattern from API request
const userPattern = req.body.filePattern;

// This could hang if userPattern contains malicious braces
const matches = files.filter(f => minimatch(f, userPattern));

An attacker could submit a pattern like {,,,,,,,,,,,,,,,,,,,,,,,,,} or deeply nested braces, causing the server to freeze. Even a single malicious request could take down the entire Node.js process.

Why This Is High Severity

The vulnerability is rated HIGH because:
- Low attack complexity: Crafting malicious input is trivial
- No authentication required: Any input path that reaches brace expansion is vulnerable
- Full availability impact: The application becomes completely unresponsive
- Wide attack surface: brace-expansion is a transitive dependency of many popular packages

The Fix

The fix uses Yarn's resolution feature to force all semver ranges to resolve to patched versions. Here's the before and after:

Before (package.json)

"resolutions": {
  "uuid": "^14.0.0",
  "yargs": "^18.1.0"
}

After (package.json)

"resolutions": {
  "uuid": "^14.0.0",
  "yargs": "^18.1.0",
  "brace-expansion@npm:^1.1.7": "1.1.16",
  "brace-expansion@npm:^2.0.1": "2.1.2",
  "brace-expansion@npm:^2.0.2": "2.1.2",
  "brace-expansion@npm:^5.0.5": "5.0.7"
}

Why Multiple Resolution Entries?

The dependency tree contains multiple packages requesting different semver ranges of brace-expansion:
- Some packages request ^1.1.7 (1.x compatibility)
- Others request ^2.0.1 or ^2.0.2 (2.x compatibility)
- Newer packages request ^5.0.5 (5.x compatibility)

Each resolution entry ensures that regardless of which range a package requests, Yarn resolves it to a patched version:
- ^1.1.7 → 1.1.16 (was resolving to vulnerable 1.1.18)
- ^2.0.1 and ^2.0.2 → 2.1.2 (was resolving to vulnerable 2.1.1)
- ^5.0.5 → 5.0.7 (was resolving to vulnerable 5.0.6)

The yarn.lock Changes

The lockfile updates reflect the version pinning:

-"brace-expansion@npm:^1.1.7":
-  version: 1.1.18
+"brace-expansion@npm:1.1.16":
+  version: 1.1.16

-"brace-expansion@npm:^2.0.1, brace-expansion@npm:^2.0.2":
-  version: 2.1.1
+"brace-expansion@npm:2.1.2":
+  version: 2.1.2

-"brace-expansion@npm:^5.0.5":
-  version: 5.0.6
+"brace-expansion@npm:5.0.7":
+  version: 5.0.7

The patched versions (1.1.16, 2.1.2, 5.0.7) include algorithmic improvements that prevent the exponential blowup, likely through:
- Input length limits
- Recursion depth guards
- Optimized parsing that avoids exponential branching

Prevention & Best Practices

1. Use Dependency Scanning in CI/CD

Integrate tools like Trivy, Snyk, or npm audit into your pipeline:

# GitHub Actions example
- name: Run Trivy vulnerability scanner
  uses: aquasecurity/trivy-action@master
  with:
    scan-type: 'fs'
    scan-ref: '.'
    severity: 'HIGH,CRITICAL'

2. Leverage Package Manager Resolutions

Both Yarn and npm support overriding transitive dependency versions:

Yarn (package.json):

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

npm (package.json):

"overrides": {
  "vulnerable-package": "^patched.version"
}

3. Audit Dependencies Regularly

# npm
npm audit

# yarn
yarn audit

# With automatic fix attempts
npm audit fix

4. Implement Input Validation

When accepting user input that flows to glob/pattern matching:

const MAX_PATTERN_LENGTH = 100;
const MAX_BRACE_DEPTH = 3;

function validatePattern(pattern) {
  if (pattern.length > MAX_PATTERN_LENGTH) {
    throw new Error('Pattern too long');
  }

  const braceDepth = (pattern.match(/{/g) || []).length;
  if (braceDepth > MAX_BRACE_DEPTH) {
    throw new Error('Pattern too complex');
  }

  return pattern;
}

5. Consider Timeouts for Parsing Operations

const { setTimeout } = require('timers/promises');

async function safeGlobMatch(pattern, files, timeoutMs = 1000) {
  const controller = new AbortController();

  const result = await Promise.race([
    performMatch(pattern, files),
    setTimeout(timeoutMs, null, { signal: controller.signal })
  ]);

  if (result === null) {
    throw new Error('Pattern matching timed out');
  }

  return result;
}

Key Takeaways

• Transitive dependencies matter: The vulnerable brace-expansion wasn't a direct dependency but came through packages like minimatch—always scan the full dependency tree
• Multiple version ranges require multiple resolutions: This fix needed four separate resolution entries to cover all semver ranges (^1.1.7, ^2.0.1, ^2.0.2, ^5.0.5)
• Algorithmic complexity is a real attack vector: DoS vulnerabilities don't require memory corruption or code execution—exponential algorithms are exploitable
• Yarn resolutions provide surgical fixes: Rather than waiting for every intermediate package to update, resolutions let you patch vulnerabilities immediately
• The assessment noted "not confirmed reachable": Even without confirmed exploitation paths, upgrading is the right call—attack surface reduction is proactive security

How Orbis AppSec Detected This

• Source: Transitive dependency brace-expansion in yarn.lock resolved to vulnerable versions (1.1.18, 2.1.1, 5.0.6)
• Sink: Any code path using glob matching, file pattern expansion, or minimatch functionality that accepts external input
• Missing control: No version pinning or resolution overrides to enforce patched versions across the dependency tree
• CWE: CWE-1333 (Inefficient Regular Expression Complexity) / CWE-400 (Uncontrolled Resource Consumption)
• Fix: Added yarn resolutions in package.json to force all brace-expansion semver ranges to resolve to patched versions (1.1.16, 2.1.2, 5.0.7)

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 demonstrates how algorithmic complexity vulnerabilities in foundational packages can create widespread risk. The brace-expansion package, while small, sits at the base of the npm dependency pyramid—used by glob matching libraries that power build tools, test runners, and countless CLI utilities.

The fix was straightforward: yarn resolutions that pin all semver ranges to patched versions. This approach is immediately effective, doesn't require waiting for intermediate packages to update, and ensures the entire dependency tree is protected.

For developers: treat dependency updates as security hygiene. Automated scanning catches these issues early, and package manager resolutions give you the tools to fix them quickly—even in complex dependency trees.

References

• CWE-1333: Inefficient Regular Expression Complexity
• CWE-400: Uncontrolled Resource Consumption
• OWASP Denial of Service Cheat Sheet
• Yarn Selective Dependency Resolutions
• npm Overrides Documentation
• Semgrep Rules for DoS
• fix: upgrade brace-expansion to 5.0.7, 1.1.16, 2.1.2 (CVE-2026-13149)