brace-expansion Denial of Service via Exponential Complexity

Impact Analysis

This vulnerability can lead to denial of service by causing significant CPU consumption and blocking the event loop.

If an attacker sends a specially crafted string to the expand() function, it can cause the application using the brace-expansion library to become unresponsive or slow down drastically.

This can affect the availability of services relying on this library, potentially leading to downtime or degraded performance.

Useful 0 Not Useful 0

Executive Summary

The vulnerability in brace-expansion through version 5.0.6 is a denial of service issue caused by the expand() function's exponential-time complexity when processing consecutive non-expanding '{}' brace groups.

An attacker can craft a string with many consecutive '{}' groups that do not expand, causing the function to consume excessive CPU resources and block the event loop for a significant time.

This happens because the expand_ function handles these non-expanding groups inefficiently, running in O(2^n) time complexity, which leads to severe performance degradation and potential service disruption.

The vulnerability was demonstrated with a test case of 30 consecutive '{}' groups, which caused the function to take an excessive amount of time to process.

Useful 0 Not Useful 0

Detection Guidance

This vulnerability can be detected by testing the brace-expansion library's expand() function with crafted input strings containing multiple consecutive non-expanding '{}' brace groups. Inputs with around 30 consecutive '{}' groups can cause significant CPU consumption and event-loop blocking, indicating the presence of the vulnerability.

To detect the vulnerability on your system, you can run a test script or command that calls the expand() function with such crafted input and observe if the process experiences severe performance degradation or blocking.

Example command (in a Node.js environment using the vulnerable brace-expansion library):

• Run a script that imports brace-expansion and calls expand() with a string like '{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}'.
• Observe CPU usage and responsiveness; excessive CPU consumption or blocking indicates the vulnerability.

Useful 0 Not Useful 0

Mitigation Strategies

Immediate mitigation involves updating the brace-expansion library to a version later than 5.0.6 where the vulnerability has been fixed.

The fix includes deferring expansion of the 'post' variable until it is confirmed that a brace set actually expands and converting the recursive restart mechanism into a loop to prevent call stack exhaustion.

If updating is not immediately possible, avoid processing untrusted input strings containing multiple consecutive '{}' brace groups with the expand() function to reduce risk.

Useful 0 Not Useful 0