How Exponential-Time Complexity Causes Denial of Service in brace-expansion and How to Fix It

Introduction

In a production web application handling user-influenced file patterns, we discovered a HIGH severity denial of service vulnerability lurking in package-lock.json. The brace-expansion package at version 1.1.13—a dependency likely pulled in through glob-matching utilities—contained an algorithmic flaw that could freeze your entire Node.js process with a single malicious input.

The vulnerable code in node_modules/brace-expansion at line 9603 of package-lock.json showed:

"node_modules/brace-expansion": {
  "version": "1.1.13",
  "resolved": "https://registry.npmjs.org/brace-expansion/-/brace-expansion-1.1.13.tgz",
  "integrity": "sha512-9ZLprWS6EENmhEOpjCYW2c8VkmOvckIJZfkr7rBW6dObmfgJ/L1GpSYW5Hpo9lDz4D1+n0Ckz8rU7FwHDQiG/w==",

This version string—1.1.13—is the smoking gun. When brace-expansion processes nested brace patterns, the algorithm's time complexity grows exponentially with input depth. For a web application accepting user-provided glob patterns, this creates a trivial denial of service vector.

The Vulnerability Explained

What brace-expansion Does

Brace-expansion is a core JavaScript library that expands brace patterns like file-{1,2,3}.txt into file-1.txt, file-2.txt, file-3.txt. It's a dependency of glob, minimatch, and countless other packages—making this vulnerability extremely widespread.

The Algorithmic Flaw

The vulnerability in version 1.1.13 stems from exponential-time complexity in the brace expansion algorithm. Consider this pattern:

{a,b}{a,b}{a,b}{a,b}{a,b}{a,b}{a,b}{a,b}{a,b}{a,b}

Each nested brace doubles the computation. With 10 levels, this generates 2^10 = 1,024 combinations. With 25 levels, you get 33,554,432 combinations. The algorithm doesn't implement:

• Depth limiting
• Memoization to avoid redundant computations
• Early termination on excessive expansion

Real-World Attack Scenario

In our web application context, imagine an endpoint accepting a pattern parameter for file search:

// Hypothetical vulnerable endpoint
app.get('/search', (req, res) => {
  const pattern = req.query.pattern;  // User-controlled!
  const files = glob.sync(pattern);   // Uses brace-expansion internally
  res.json(files);
});

An attacker sends:

GET /search?pattern={a,b}{a,b}{a,b}{a,b}{a,b}{a,b}{a,b}{a,b}{a,b}{a,b}{a,b}{a,b}{a,b}{a,b}{a,b}{a,b}{a,b}{a,b}{a,b}{a,b}

The server hangs. CPU spikes to 100%. Other requests timeout. Depending on the Node.js configuration, this could crash the process or exhaust resources until manual intervention.

The package-lock.json entry at line 9603 confirmed this vulnerable version was in the production dependency tree—not devDependencies, meaning it reached actual users.

The Fix

The remediation involved two coordinated changes to enforce patched versions across the dependency tree.

Change 1: Direct Dependency Update in package-lock.json

Before (vulnerable):

"node_modules/brace-expansion": {
  "version": "1.1.13",
  "resolved": "https://registry.npmjs.org/brace-expansion/-/brace-expansion-1.1.13.tgz",
  "integrity": "sha512-9ZLprWS6EENmhEOpjCYW2c8VkmOvckIJZfkr7rBW6dObmfgJ/L1GpSYW5Hpo9lDz4D1+n0Ckz8rU7FwHDQiG/w==",

After (patched):

"node_modules/brace-expansion": {
  "version": "1.1.16",
  "resolved": "https://registry.npmjs.org/brace-expansion/-/brace-expansion-1.1.16.tgz",
  "integrity": "sha512-IDw48K2/2kRkg9LdJxurvq3lV3aBgq0REY89duEqFRthjlPdXHKMj7EnQOXVckxzgisinf3nHfrcE2FufFLXMw==",

Version 1.1.16 (and the parallel releases 2.1.2 and 5.0.7) implement algorithmic fixes:

• Linear-time expansion: Restructured recursion to avoid exponential blowup
• Depth limiting: Maximum brace nesting prevents abuse
• Early termination: Stops expansion when output would exceed reasonable bounds

Change 2: npm Overrides in package.json

The package.json received a critical addition at line 93:

,
  "overrides": {
    "brace-expansion": "1.1.16"
  }
}

This overrides field (npm 8.3+) forces all transitive dependencies to use the specified version, regardless of what their own package.json requests. This is essential because:

• glob might require brace-expansion ^1.1.0
• minimatch might require brace-expansion ^2.0.0
• Other packages might pull in vulnerable versions

Without overrides, you'd need to wait for every upstream maintainer to update. The override cuts through the dependency tree immediately.

Why Three Versions?

The PR mentions 5.0.7, 1.1.16, and 2.1.2 because brace-expansion has multiple major version lines in active use:

The overrides in this project targets 1.1.16 specifically for the 1.x line used by its direct dependencies.

Prevention & Best Practices

Dependency Management

1. Audit regularly: Run npm audit and tools like Trivy in CI/CD
2. Pin with purpose: Use exact versions for security-critical packages
3. Override aggressively: Don't wait for upstream—use overrides or resolutions (Yarn) to force security patches

Input Handling

// Defensive pattern for user-provided globs
const MAX_PATTERN_LENGTH = 500;
const MAX_BRACE_DEPTH = 5;

function sanitizeGlobPattern(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('Excessive brace nesting');
  }

  return pattern;
}

Detection Tools

Standards & References

• CWE-400: Uncontrolled Resource Consumption
• CWE-1333: Inefficient Regular Expression Complexity (related)
• OWASP: ReDoS Cheat Sheet

Key Takeaways

• The package-lock.json at line 9603 contained brace-expansion@1.1.13, which has exponential-time complexity on nested brace patterns—always audit your lockfile, not just package.json
• Use npm overrides (or Yarn resolutions) to force security patches when upstream dependencies lag, rather than waiting for transitive updates
• Algorithmic complexity attacks bypass traditional input validation—the input looks valid but consumes excessive resources; depth limits and timeouts are essential
• Multiple major version lines require parallel fixes—brace-expansion 1.x, 2.x, and 5.x all needed separate patches, so verify which line your project uses
• Production code assessment matters—Trivy correctly flagged this as "likely exploitable" because the dependency was in the production dependency tree, not dev-only

How Orbis AppSec Detected This

Source: User-influenced input entering through HTTP request parameters (e.g., pattern query parameter) that flow into glob-matching operations

Sink: The brace-expansion package's pattern expansion algorithm in node_modules/brace-expansion/index.js, invoked through transitive dependencies like glob or minimatch

Missing control: No input length limits, no brace nesting depth validation, and no execution timeouts on pattern expansion operations; the package-lock.json contained the vulnerable version 1.1.13 without overrides

CWE: CWE-400: Uncontrolled Resource Consumption (Algorithmic Complexity)

Fix: Upgraded brace-expansion to patched versions 1.1.16, 2.1.2, and 5.0.7 and added an overrides entry in package.json to force all transitive dependencies onto secure versions

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 exemplifies how a seemingly simple utility library can become a critical attack vector. The brace-expansion vulnerability didn't require exotic exploits—just a basic understanding of algorithmic complexity and a crafted HTTP request. The fix demonstrates modern dependency management best practices: don't just upgrade direct dependencies, use overrides to secure your entire dependency tree immediately.

For Node.js developers, this is a reminder that package-lock.json is a security surface. Tools like Trivy caught this vulnerability in CI, and automated fixes like Orbis AppSec can apply the patches before attackers exploit them. Keep your dependencies updated, implement defense-in-depth with input limits, and never underestimate the damage from exponential complexity.

References

• CWE-400: Uncontrolled Resource Consumption
• OWASP ReDoS Cheat Sheet
• npm overrides documentation
• brace-expansion GitHub repository
• Semgrep ReDoS rules
• fix: upgrade brace-expansion to 5.0.7, 1.1.16, 2.1.2 (CVE-2026-13149)