GHSA-MJ63-M3RC-8PPR: Quadratic-Time Complexity in league/commonmark XML Pretty-Printing

The PHP package league/commonmark provides a highly extensible Markdown parser and renderer. Starting in version 2.0.0, the package introduced the XmlRenderer component, which is responsible for converting the abstract syntax tree (AST) generated from a Markdown document into a structured XML representation. This module is typically accessed programmatically through the MarkdownToXmlConverter class or by invoking XmlRenderer::renderDocument directly.

The vulnerability resides within the pretty-printing mechanism of the XML rendering logic. When generating XML output, the renderer formats elements by indenting them proportionally to their nesting level within the document tree. However, prior to version 2.9.0, the rendering engine did not place any upper limit on the maximum indentation depth.

An attacker can exploit this structural behavior by crafting a Markdown payload that contains extreme levels of nesting. When parsed and passed to the XML renderer, the lack of constraints on indentation depth results in asymmetric resource consumption. This issue is tracked under the identifier GHSA-mj63-m3rc-8ppr.

The root cause of GHSA-mj63-m3rc-8ppr is an algorithmic complexity vulnerability classed under CWE-405: Asymmetric Resource Consumption (Amplification). The XmlRenderer class traverses the node tree using an event-driven loop that tracks whether the engine is entering or exiting a node. For each entering event of a non-self-closing tag, the renderer calculates the current nesting depth and emits a matching sequence of space characters for indentation formatting.

The vulnerability manifests in how the indentation string is constructed. The system calculates the number of spaces by repeating a predefined indentation constant a number of times equal to the current depth. As the depth $n$ increases, the number of space characters emitted for a single node is proportional to $n$. Across a tree of depth $n$, the total space characters generated across all nodes grows quadratically, specifically $O(n^2)$.

While the library features a max_nesting_level parser constraint, this configuration is insufficient to prevent the flaw. First, the default value is high enough to allow significant resource exhaustion before being triggered. Second, it can be customized or disabled by developers. Third, the parser constraint only limits block-level structures and does not restrict nested inline sequences or abstract syntax trees constructed programmatically by downstream applications before being serialized to XML.

The vulnerable version of XmlRenderer.php processed node formatting without any boundary verification. The code relied entirely on the tracker variable $indent to determine string expansion size:

// Vulnerable implementation in XmlRenderer.php
if ($event->isEntering()) {
    $attrs = $renderer->getXmlAttributes($node);
    // Indentation expands indefinitely based on current depth
    $xml .= "\n" . \str_repeat(self::INDENTATION, $indent);
    $xml .= self::tag($tagName, $attrs, $selfClosing);
    ...
} elseif (! $closeImmediately) {
    $indent--;
    // Indentation scales quadratically as depth increases
    $xml .= "\n" . \str_repeat(self::INDENTATION, $indent);
    $xml .= self::tag('/' . $tagName);
}

The patch committed in version 2.9.0 addresses the vulnerability by decoupling the cosmetic visual indentation from the actual syntactic nesting level. The developer introduced a configuration option xml/max_indentation_level, which is initialized with a safe default value of 16.

// Patched implementation in XmlRenderer.php
$maxIndent = $this->getMaxIndentationLevel();
...
if ($event->isEntering()) {
    $attrs = $renderer->getXmlAttributes($node);
    // Indentation multiplier is bounded by maxIndent
    $xml .= "\n" . \str_repeat(self::INDENTATION, \min($indent, $maxIndent));
    $xml .= self::tag($tagName, $attrs, $selfClosing);
    ...
} elseif (! $closeImmediately) {
    $indent--;
    // Multiplier is safely capped, restoring linear complexity
    $xml .= "\n" . \str_repeat(self::INDENTATION, \min($indent, $maxIndent));
    $xml .= self::tag('/' . $tagName);
}

By wrapping the $indent multiplier within a \min() constraint, the maximum memory allocated per line for structural whitespace is strictly bounded. The overall complexity of the output payload is reduced from quadratic $O(n^2)$ back to linear $O(n)$ relative to the input depth, completely neutralizing the amplification vector while keeping the generated XML structurally valid.

An attack targeting this vulnerability is executed through the network vector by transmitting a specially crafted input to an application endpoint that converts user-supplied Markdown into XML format. The primary prerequisite is that the target application must instantiate the XML rendering module and expose it to unauthenticated user input.

To trigger the amplification, the attacker generates a payload consisting of deep recursive blockquotes or inline nesting sequences. A payload with a nesting depth of 1,000 blocks can be constructed using repeating blockquote characters:

> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > >

When the PHP runtime processes this input, the parser creates an AST with 1,000 nested levels. During serialization, XmlRenderer repeats the standard 4-character indentation string up to 1,000 times for each nested element. This results in the generation of several megabytes of pure whitespace characters within the PHP memory space.

The consequence is a rapid exhaustion of available memory allocated to the PHP worker process, triggering an Out-of-Memory (OOM) error. Alternatively, the CPU becomes saturated performing repetitive string allocation and copying routines, stalling the application container and preventing it from handling legitimate web requests.

The security impact of GHSA-mj63-m3rc-8ppr is limited to service availability, with a calculated CVSS v3.1 base score of 5.3 (Medium). The vector string is CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:L.

Because the vulnerability occurs within the boundaries of the PHP runtime environment, it does not lead to remote code execution, privilege escalation, or unauthorized access to sensitive application data. The scope remains unchanged because the impact is restricted to the resources allocated to the executing PHP application process.

However, on high-traffic systems, exploiting this vulnerability can cause a complete Denial of Service (DoS) of the web application. A single malicious request can block a PHP-FPM worker thread indefinitely or trigger process termination. Under continuous submission of the payload, an attacker can exhaust the pool of available workers, rendering the entire web service unresponsive.

The recommended remediation for this vulnerability is to upgrade the league/commonmark dependency to version 2.9.0 or higher. This release implements the xml/max_indentation_level restriction by default, bounding the maximum pretty-printing space duplication to a safe value of 16.

For environments where immediate package upgrades are not possible, several temporary workarounds can be applied. Developers should limit the global parsing depth of block structures by lowering the max_nesting_level configuration setting to a value of 50 or less.

// Custom environment configuration workaround
use League\CommonMark\Environment\Environment;
 
$config = [
    'max_nesting_level' => 50,
];
$environment = new Environment($config);

In addition, implementing strict length validation on incoming Markdown payloads before they are passed to the parser represents an effective mitigation. Restricting the input payload size to 10 kilobytes or less ensures that the maximum potential AST depth is bounded, thereby eliminating the possibility of high-ratio resource amplification.