HTML-to-Markdown quadratic parsing: small documents, expensive conversions

GHSA-h3wg-gqjr-jjmw · CWE-407 · league/html-to-markdown 2.0.0–5.1.3 · published October 10, 2026

An 80 KB HTML document should not occupy a PHP worker for tens of seconds. In affected versions of league/html-to-markdown, however, documents containing many sibling elements could make conversion time grow with the square of the element count.

The result was an algorithmic-complexity denial of service. Applications that passed attacker-controlled HTML into HtmlConverter could have their worker capacity consumed by small, valid inputs—without malformed markup, deep nesting, or a large request body.

The issue was published as GHSA-h3wg-gqjr-jjmw. It affects league/html-to-markdown from version 2.0.0 through 5.1.3 and is fixed in 5.1.4. GitHub rates it Moderate with CVSS 3.1 score 5.3 and classifies it as CWE-407: Inefficient Algorithmic Complexity.

Finding at a glance

Why the runtime became quadratic

If a converter performs a constant amount of work for each element, doubling the input should roughly double the conversion time. The vulnerable paths repeatedly revisited siblings or the full document while processing each element. With n siblings, the total work approached:

1 + 2 + 3 + ... + n = n(n + 1) / 2 = O(n²)

The advisory identified three independent causes, all centered in src/Element.php.

1. Repeated sibling scans for list items

ListItemConverter::convert() requested each item's sibling position. Element::getSiblingPosition() rebuilt the parent's complete child list and scanned forward to the current node every time. Processing item one was cheap; processing later items repeatedly traversed everything before them.

This affected:

• every item in an ordered list;
• unordered lists nested inside another list; and
• unordered lists using the list_item_style_alternate option.

A flat, top-level unordered list with the default options did not use this particular vulnerable path.

2. Document-wide canonicalization for each serialized element

Element::getChildrenAsString() used DOMNode::C14N() on a node that remained attached to the document. Canonicalization performed work proportional to the document size for every call, so repeating it across many elements again produced quadratic growth.

Affected shapes included:

• <pre> and <code> elements;
• table rows and cells handled by TableConverter; and
• tags preserved as HTML, including repeated <span> elements.

3. Replacement cost on older PHP releases

Element::setFinalMarkdown() called DOMNode::replaceChild(). On PHP 8.0 and earlier, that operation scanned siblings preceding the node being replaced. Its per-element cost was smaller than the first two cases, but it applied broadly to every element.

No HTML-size, element-count, or work limit inside the converter bounded these paths.

Reproducing the growth safely

A local benchmark can demonstrate the complexity without network traffic or persistent side effects. It generates ordered lists at increasing sizes and measures only conversion time:

<?php
require __DIR__ . '/vendor/autoload.php';

use League\HTMLToMarkdown\HtmlConverter;

foreach ([1000, 2000, 4000, 8000] as $count) {
    $html = '<ol>'
        . str_repeat('<li>x</li>', $count)
        . '</ol>';

    $started = hrtime(true);
    (new HtmlConverter())->convert($html);

    printf(
        "items=%d input_bytes=%d seconds=%.3f\n",
        $count,
        strlen($html),
        (hrtime(true) - $started) / 1e9
    );
}

On version 5.1.3 with PHP 8.4 and one CPU, the reported measurements were:

Doubling the element count produced approximately four times the work—the signature expected from quadratic behavior. Equivalent tests with repeated <pre><code> blocks or preserved <span> elements exposed the canonicalization path.

Patched behavior

Version 5.1.4 reduces conversion to approximately linear growth without changing the generated Markdown. In the advisory's comparison, the 8,000-item ordered list completed in roughly 0.2 seconds, and doubling the input approximately doubled the runtime rather than quadrupling it.

That distinction is the useful security invariant:

Vulnerable: T(2n) ≈ 4 × T(n)
Patched:    T(2n) ≈ 2 × T(n)

Impact and reachability

The vulnerable library is not automatically remotely exploitable everywhere it is installed. The application must expose a path that converts attacker-controlled HTML—for example, an import, preview, email-processing, migration, or rich-text conversion feature.

When that path is reachable, no authentication or user interaction is inherently required by the library flaw. One request is still bounded by PHP's max_execution_time and any upstream request-size limit, and the CPU cost ends when conversion terminates. Repeated or concurrent requests can nevertheless occupy a PHP-FPM or worker pool and delay legitimate traffic.

The demonstrated effect is availability loss. The advisory does not claim confidentiality or integrity impact.

Remediation

1. Upgrade league/html-to-markdown to 5.1.4 or later.
2. Until upgrading, cap the byte size and element count of HTML submitted for conversion.
3. Configure a finite PHP max_execution_time and enforce request timeouts at the worker and reverse-proxy layers.
4. Apply concurrency and rate limits to conversion endpoints so one tenant cannot consume the full worker pool.
5. Benchmark adversarial structures—not only large files—when evaluating parsers and document converters.
6. Monitor conversion duration, timeouts, queue depth, and worker saturation for early evidence of abuse.

Security lessons

• Input bytes are a weak proxy for cost. An 80 KB structured document can be more expensive than a much larger ordinary one.
• Valid input can still be adversarial. The proof uses ordinary HTML elements and does not depend on parser errors.
• Nested loops can hide across call boundaries. A linear-looking element loop becomes quadratic when its helper repeatedly scans siblings or the document.
• Measure the scaling curve. Timings at several powers of two reveal complexity problems more clearly than a single slow sample.
• Resource limits are defense in depth. Timeouts and size caps reduce exposure but do not replace the algorithmic fix.

References

• GitHub Security Advisory GHSA-h3wg-gqjr-jjmw
• league/html-to-markdown 5.1.4 release
• CWE-407: Inefficient Algorithmic Complexity