CVE-2026-13149: Algorithmic Complexity Denial of Service in brace-expansion

The NPM library brace-expansion is a foundational package responsible for resolving shell-like brace expansions such as file{1..3}.txt into discrete arrays of strings. Because it is transitively consumed by highly popular path-matching libraries like minimatch and glob, its attack surface extends to any downstream application that evaluates user-controlled input. Common exposure points include file upload endpoints, custom query engines, search criteria forms, and request router rules.

The core parsing engine within brace-expansion handles brackets and sequences recursively. However, when processing specific patterns of consecutive non-expanding brace groups, the library suffers from a classic Algorithmic Complexity flaw (CWE-407). This algorithmic inefficiency allows an attacker to manipulate the processing engine into performing exponential-time operations relative to the input length.

In Node.js, the execution of JavaScript code is bound to a single-threaded event loop. If a CPU-bound function blocks the event loop, all concurrent operations are starved, causing the service to become unresponsive. An unauthenticated attacker can exploit this behavior by submitting a payload of less than 100 bytes, which halts the application thread and causes an application-wide Denial of Service.

The root cause of CVE-2026-13149 lies in the main expansion routine expand_. When parsing a target string, the engine performs an unconditional, eager evaluation of the suffix or remaining part of the string (m.post) before validating whether the current brace group should actually expand.

When a non-expanding brace group like a{} is encountered, the parser reaches a rewrite rule that handles patterns matching {a},b}. The engine is designed to handle non-expanding groups by escaping the closing brace, rewriting the string, and starting the expansion process over again via a recursive call: return expand_(str, max, true).

This architecture creates a double-execution branch. The recursive evaluation of m.post is computed during the initialization of the current call frame, and then completely discarded when the rewrite logic is triggered and restarts the calculation on the rewritten string. As a result, each successive non-expanding group forces the engine to branch twice over the trailing substring.

This behavior yields an exponential execution recurrence relation:

$$T(n) = 2 \cdot T(n-1) + O(1)$$

Where $n$ represents the count of consecutive non-expanding brace groups. A string containing 30 non-expanding groups demands over one billion redundant calculations, completely exhausting the CPU resources allocated to the process thread.

To understand the mechanics of the flaw, compare the vulnerable execution path with the patched implementation in version 5.0.7. The vulnerable parser processed the suffix immediately upon parsing the balanced group:

function expand_(str, max, isTop) {
  var expansions = [];
  var m = balanced('{', '}', str);
  if (!m) return [str];
 
  // VULNERABLE: "post" is recursively evaluated unconditionally here
  var pre = m.pre;
  var post = m.post.length ? expand_(m.post, max, false) : [''];
 
  if (/\$$/.test(m.pre)) { 
    // dollar prefix logic
  } else {
    // ... sequence check ...
    if (!isSequence && !isOptions) {
      if (m.post.match(/,(?!,).*\}/)) {
        str = m.pre + '{' + m.body + escClose + m.post;
        // VULNERABLE: Recursion discards the already computed "post" variable
        return expand_(str, max, true); 
      }
      return [str];
    }
  }
}

The patch addresses this structural defect in two ways: it defers the suffix expansion until after validation, and it replaces recursion with an iterative loop. This eliminates both the exponential branching and the risk of call stack exhaustion:

function expand_(str, max, isTop) {
  const expansions = [];
 
  // FIX: Loop instead of recursively calling expand_ to avoid stack exhaustion
  for (;;) {
    const m = balanced('{', '}', str);
    if (!m) return [str];
    const pre = m.pre;
 
    if (/\$$/.test(m.pre)) {
      // Suffix is evaluated here only if required
      const post = m.post.length ? expand_(m.post, max, false) : [''];
      // ... execution continue ...
    }
 
    const isNumericSequence = /^-?\d+\.\.-?\d+(?:\.\.-?\d+)?$/.test(m.body);
    const isAlphaSequence = /^[a-zA-Z]\.\.[a-zA-Z](?:\.\.-?\d+)?$/.test(m.body);
    const isSequence = isNumericSequence || isAlphaSequence;
    const isOptions = m.body.indexOf(',') >= 0;
 
    if (!isSequence && !isOptions) {
      if (m.post.match(/,(?!,).*\}/)) {
        str = m.pre + '{' + m.body + escClose + m.post;
        isTop = true;
        // FIX: Utilize loop continuation rather than creating a new call frame
        continue;
      }
      return [str];
    }
 
    // FIX: Suffix computation is deferred until the group is confirmed as expanding
    const post = m.post.length ? expand_(m.post, max, false) : [''];
    // ... standard expansion paths ...
  }
}

Exploiting this vulnerability does not require complex payloads or network states. Because the execution complexity scales exponentially, an attacker can trigger the CPU exhaustion sequence using a short string containing consecutive empty or non-expanding braces.

An example of a functional payload is:

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

This payload consists of 30 non-expanding brace groups and is only 90 bytes long. A Python-based script or a raw HTTP request sending this payload to an exposed API parameter causes immediate thread block:

const { expand } = require('brace-expansion');
// A 90-byte input halts the main application thread for ~120 seconds
expand('a{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{},{}');

When a Node.js process receives this payload, the event loop stops processing incoming HTTP connections, database query callbacks, and network packets. Downstream clients experience timeouts, and routing proxies (e.g., Nginx or HAProxy) return HTTP 504 Gateway Timeout or HTTP 502 Bad Gateway responses.

The overall impact of CVE-2026-13149 is scored as High because it results in process-level Denial of Service. In environments where multi-threading or clustering is not configured, a single attack payload disables the entire application interface.

While CVSS v3.1 evaluated the availability impact as Low due to traditional scoping rules, the CVSS v4.0 framework assesses it with a base score of 7.7 and a High Availability rating (VA:H). This update reflects the real-world operational impact of event-loop blockages within Node.js microservices.

Because the payload size is so small, an attacker can sustain a total Denial of Service with minimal bandwidth. They only need to transmit one packet every few minutes per worker process, which bypasses traditional network-layer rate limiting systems.

The primary mitigation is updating the brace-expansion library to a patched release. Ensure that transitive dependencies are updated across all project lockfiles.

If you are using Node.js, you can identify vulnerable packages using the dependency analyzer:

npm ls brace-expansion

If the library is included as a transitive dependency of packages such as minimatch or glob, use the package overrides feature in your package.json to enforce the safe versions:

"resolutions": {
  "brace-expansion": "^5.0.7"
}

For systems where immediate updates cannot be deployed, you can use a validation filter to reject inputs containing sequential brace patterns before they reach the expansion engine:

const dangerousPattern = /(?:\{[^,.]*\}\s*,?\s*){4,}/;
function validateInput(input) {
  if (dangerousPattern.test(input)) {
    throw new Error('Invalid input payload detected');
  }
  return true;
}