Two quadratic scanners in python-markdown let one 30 KB document cost two minutes of CPU, and all the work is discarded #1654

Hi,

There are two quadratic scan functions in inlinepatterns.py, reachable by six different
payload shapes. On most of them the work is discarded, so it is pure waste. One line of
input is enough.

Scanner one: LinkInlineProcessor.getText, inlinepatterns.py:884

def getText(self, data: str, index: int) -> tuple[str, int, bool]:
    """Parse the content between `[]` of the start of an image or link
    resolving nested square brackets.
    """
    bracket_count = 1
    text = []
    for pos in range(index, len(data)):
        c = data[pos]
        if c == ']':
            bracket_count -= 1
        elif c == '[':
            bracket_count += 1
        index += 1
        if bracket_count == 0:
            break
        text.append(c)
    return ''.join(text), index, bracket_count == 0

Two things combine.

When the brackets never balance the loop runs all the way to len(data), one Python level
text.append(c) per character. There is no early exit for the case where there is no "]"
left in the input at all, so an unmatched "[" always costs a full scan of everything after
it.

And the result is then thrown away. handleMatch at :934 does:

text, index, handled = self.getText(data, m.end(0))
if not handled:
    return None, None, None

So the multi thousand character list that was just built and joined is discarded, and the
pattern is retried at the next "[". N unmatched brackets cost N full scans.

getText is inherited by six processors: Link, Reference, ShortReference, Image,
ImageReference and ShortImageReference. Each one calls it on the same data.

Scanner two: BacktickInlineProcessor.find_code_spans, inlinepatterns.py:445

This one makes no getText calls at all, so it is independent.

def find_code_spans(self, start: int, text: str) -> tuple[int, int] | None:
    last = len(text)
    ...
    i = start
    while i < last:
        span_length = 0
        while i < last and text[i] == '`':
            span_length += 1
            i += 1
        ...
        if max_ticks == span_length:
            return start, i - span_length
        if span_length > longest_span:
            longest_span = span_length
            end = i

Same shape. When no span of matching length exists, "while i < last" runs to the end of the
text, and it is re-entered once per backtick position.

Repro

python3 -c "import markdown,time; p='['*30000; t=time.perf_counter(); markdown.Markdown().convert(p); print(time.perf_counter()-t)"

127 seconds here on 3.11. For a quicker check, '['*10000 is about 13 seconds.

The curve, measured

"[" * n, one line, nothing else. Fresh subprocess per row.

 input B       sec   us per B   output B
   2,501      0.77        307      2,508
   5,001      3.02        603      5,008
  10,001     13.02      1,302     10,008
  15,001     30.37      2,024     15,008
  20,001     52.39      2,619     20,008
  30,001    126.99      4,233     30,008

Fitted exponent 2.06, per byte cost growth 13.8x. Output matches input on every row.

I stopped at 30 KB because that is already two minutes. Projecting from the last measured
point gives roughly 25 minutes at 100 KB and roughly 48 hours at 1 MB, but those are
projections and the 127 seconds is the measurement.

Six shapes, and the scan constant is the processor count

Sweeping every inline construct that has an opener needing a closer, sizes 250 to 4,000,
bare and with extra/admonition/sane_lists/toc loaded:

shape              payload            exponent   sec at n=4000   input B
image_mixed        "![[" * n              1.89           11.82    12,001
ref_open           "[a][" * n             1.99            6.46    16,001
image_open         "![" * n               1.99            5.16     8,001
footnote_open      "[^" * n               1.97            3.86     8,001
bracket_balanced   "["*n + x + "]"*n      2.06            3.55     8,001
bracket_open       "[" * n                2.07            2.18     4,001
backtick_open      "`" * n                2.06            0.37     4,001

Then I instrumented the scanners and counted characters, at n=1,000:

shape            getText calls   chars scanned   scan/n^2   resolved   processors
bracket_open             3,000       1,501,500       1.50          0   Link, Reference, ShortReference
image_open               3,000       3,000,000       3.00          0   Image, ImageReference, ShortImageReference
footnote_open            3,000       3,003,000       3.00          0   Link, Reference, ShortReference
ref_open                 5,000       5,001,500       5.00      2,500   Link, Reference, ShortReference
image_mixed              6,000       9,000,000       9.00          0   all six
backtick_open                0               0          0          0   none, separate path

scan/n^2 is an exact constant at every size, so this is precisely quadratic rather than
something that merely looks steep on a chart. And the constant is just how many processors
the payload gets to call getText: "![[" triggers all six, which is why it is the worst per
byte.

The resolved column is 0 everywhere except ref_open. So on five of the six shapes not one
call resolves, and every byte scanned and every character appended is discarded.

cProfile agrees. "[" * 4000, sorted by tottime:

  ncalls   tottime   cumtime   function
   12000     3.579     5.395   inlinepatterns.py:884(getText)
24006041     1.737     1.737   {method 'append' of 'list' objects}
    8000     0.012     3.580   inlinepatterns.py:934(handleMatch)

And "`" * 6000:

  ncalls   tottime   cumtime   function
    6000     0.763     0.764   inlinepatterns.py:445(find_code_spans)
    6000     0.002     0.767   inlinepatterns.py:491(handleMatch)

What is NOT affected

Worth saying, because it narrows the fix. These were all linear in the same sweep:
star_open, star_balanced, under_open, strong_star, strong_under, tilde, tilde_pairs, caret,
equals, amp, amp_entityish, backslash, attr_open, pipes, ref_pairs, angle_open, and a plain
text control.

So emphasis is fine here, which is notable because emphasis is one of the axes Mistune was
hit on. The only mildly super-linear thing I found outside the six was "<a" * n at exponent
1.56, and I do not think that is worth your time.

While I was there: block level quadratics, and one uncaught exception

The sweep above was inline patterns only, so I ran the same method over block constructs and
the extensions. Sizes 4k to 64k, five points each, each extension loaded individually so the
attribution is unambiguous, and every shape re-run bare so "extension X is quadratic" is
only claimed where bare is linear.

shape            config    exponent   worst
atx headers      toc           2.01   64.21s at 63,999 B
setext headers   toc           1.96   35.65s at 63,995 B
ref definitions  BARE          1.94    3.79s at 71,379 B
setext headers   BARE          1.90    7.83s at 63,995 B
abbr definitions abbr          1.84    8.02s at 68,705 B
atx headers      tables        1.80    5.74s at 63,999 B
atx headers      smarty        1.50    3.15s at 63,999 B

Two things to pull out of that.

toc is the worst single thing I found anywhere in this work. 8,000 ATX headers, 64 KB,
64.2 seconds, exponent 2.01. Bare markdown does the same document in 0.239 seconds, so the
extension is adding a clean quadratic. I did not dig into which part, but the usual cause
for a headers-versus-headers quadratic is slug uniquification comparing each new slug
against every previous one.

Reference definitions and setext headers are quadratic in CORE, with no extension
loaded, which means every consumer is exposed to those two. They are milder than the bracket
scanners per byte, but they need no opt-in.

I left one shape out on purpose. A run of "- - -" looked quadratic bare, but "- - -" can
parse as nested list items as well as a thematic break, so I could not attribute it cleanly
and I am not claiming it.

The uncaught exception, which is a different defect class

Before the measurement, your own documented goal. docs/index.md lists this FIRST under
Goals, and the parenthetical is the relevant part:

Maintain a Python library (with an optional CLI wrapper) suited to use in web
server environments (never raise an exception, never write to stdout, etc.) as
an implementation of the markdown parser that follows the syntax rules and the
behavior of the original (markdown.pl) implementation as reasonably as possible

"Never raise an exception", for "web server environments". That is the property the next
measurement refutes, and it is also the reason this belongs in a security report rather
than an issue: you have told people they can point this library at a web request, and the
goal that makes that safe is the one that does not hold.

With def_list loaded, or with extra, which bundles it:

496 definition entries, 5,345 B -> renders fine
497 definition entries, 5,356 B -> RecursionError

python3 -c "import markdown; print(markdown.Markdown(extensions=['extra']).convert(chr(10).join(f't{j}{chr(10)}:   d' for j in range(497))))"

The RecursionError propagates straight out of md.convert(). I checked: it is not caught and
converted into anything, it escapes. Default recursion limit here is 1000, and the threshold
is sharp at 497, which is consistent with about two frames per entry.

So 5.4 KB of entirely ordinary looking markdown, a definition list with 497 terms, crashes
the renderer. For anything rendering user supplied markdown in a request that is a 500
rather than a slow response.

I am including it here because you already treat this class as a security issue in this
library: CVE-2025-69534 is "Python-Markdown has an Uncaught Exception", where malformed HTML
like sequences raised an unhandled AssertionError, fixed in 3.8.1. This is the same shape
with a different trigger.

Suggested fix

The cheap guard handles the worst case in getText. Before the loop, if there is no "]"
anywhere after index then the brackets cannot balance:

if data.find(']', index) == -1:
    return '', index, False

That turns "[" * n from quadratic into linear.

It does not fix every shape, because bracket_balanced and ref_open do contain closing
brackets and are still quadratic. The complete fix is to stop rescanning from scratch at
every candidate, for instance by hopping with str.find instead of a per character Python
loop, and by not building text until the match is known to resolve. Building a string that
gets discarded on the failure path is waste regardless of the complexity question.

find_code_spans needs the same treatment: it can precompute the backtick run positions once
per text rather than rescanning from each opener.

Because five of the six shapes funnel through one function, a fix in getText covers most of
this at once.

I tested the same payloads against cmark-gfm, and they are linear there

This is not theoretical, and it is the reason I think the fix is worth doing rather than
documenting as a known limit.

Earlier in the same work I swept cmark-gfm, compiled to WebAssembly, over 26 payload shapes
at sizes from 250 bytes to 256,000 bytes. The shapes included open bracket runs, bracket
pairs, unclosed links, backtick runs, nested blockquotes, nested lists and many reference
definitions, which is the same family I am reporting here.

Every one was linear. Per byte cost stayed flat across a 1,000x size range.

So a C markdown parser handles these exact inputs in linear time, after it was hit by
CVE-2023-22486 and added dedicated quadratic fuzzers in 2023. The inputs are not
pathological in some unavoidable way, they are pathological for this implementation.

Prior art

I checked before writing. The same mechanism has a CVE in two sibling projects:

Mistune, CVE-2026-49851, fixed in 3.3.0: "Under specific conditions involving dense,
unmatched nesting of opening square brackets, the parser fallback loops degrade from linear
execution time to a worst-case quadratic complexity."

cmark-gfm, CVE-2023-22486, fixed in 0.29.0.gfm.7: "Quadratic complexity bug in
handle_close_bracket may lead to a denial of service."

The python-markdown CVE I could find, CVE-2025-69534, is a different bug: malformed HTML
like sequences causing an unhandled AssertionError in html.parser, fixed in 3.8.1. I could
not find any python-markdown advisory for quadratic bracket or backtick parsing.

Honest limits

CPU only. Peak memory stays between 0.3 and 0.6 MB on every arm.

Severity depends on the consumer's input cap and the library has none of its own, so I
cannot give you a single number. I found this while measuring Zulip, where messages are
capped at 10,000 characters and rendering is wrapped in a 5 second timeout, so there it
burns the budget and gets killed. Applications without a cap or a timeout are worse off, and
30 KB is a perfectly ordinary document size.

The payloads are visually obvious, a line of "[" or backticks, so a content check could
block these exact shapes. That does not fix the complexity.

Measured on Python 3.13.14 on Windows with Markdown 3.11 from PyPI. Absolute times will
differ on other platforms. The scan/n^2 constants are character counts, so those do not
depend on the platform.

Thanks,
furkan

--

A 30,001 byte document consisting of "[" characters takes 126.99 seconds to render on
current 3.11. The output is the same size as the input, so the parser spends two minutes
and produces nothing. Fitted exponent across the range is 2.06, so it is quadratic, and I
measured that rather than projecting it.

There are two independent quadratic scanners behind this and six payload shapes that reach
them. The worst per byte is "![[" repeated, which persuades all six inline processors to
scan the remaining text, giving 9 times n squared characters scanned.

I instrumented the scanners and counted. The characters scanned come to exactly 1.50, 3.00,
5.00 or 9.00 times n squared depending on the shape, with the constant being simply how
many processors the payload triggers. On five of the six shapes every single call fails to
resolve, so 100% of the scanning and string building is thrown away. At n=4,000 that is
24,006,041 list appends.

How bad this is depends on the consumer, and I want to be straight about that, because the
library has no input size limit of its own. The ceiling is whatever the application
accepts. 30 KB is an ordinary README. A wiki page, a pull request description, a docs
build, or a comment field with no cap gets the full quadratic. Zulip, where I found this,
caps messages at 10,000 characters and wraps rendering in a 5 second timeout, so there an
attacker burns the whole budget and the request is killed, which is a much softer landing
than an uncapped consumer gets.

This is CPU only. Peak memory stays under 1 MB on every arm, so it is not memory
exhaustion.

Two more things from the same sweep.

The first one goes against your own stated goal, which is why I am leading with it. Your
docs/index.md lists this first under Goals:

"Maintain a Python library (with an optional CLI wrapper) suited to use in web server
environments (never raise an exception, never write to stdout, etc.)"

With def_list loaded, or with extra which bundles it, a definition list of 497 terms in
5,356 bytes makes md.convert() raise an uncaught RecursionError. 496 terms renders fine, so
the threshold is sharp. That is a crash rather than a slowdown, a 500 for anything rendering
user markdown in a request, and it is the same class as CVE-2025-69534 which you already
fixed as a security issue. I am not reading "never raise an exception" as a promise you broke
on purpose, I am pointing out that the goal and the deployment context it names are exactly
what makes this a security issue rather than a bug report.

Second, the toc extension has a quadratic worse in absolute terms than anything else here:
8,000 ATX headers in 64 KB takes 64.2 seconds, against 0.239 seconds for the same document
with no extensions loaded.

The bracket mechanism already has a CVE in two sibling projects. Mistune fixed it in 3.3.0 as
CVE-2026-49851, described as "dense, unmatched nesting of opening square brackets"
degrading "to a worst-case quadratic complexity". cmark-gfm fixed it in 0.29.0.gfm.7 as
CVE-2023-22486, "Quadratic complexity bug in handle_close_bracket". python-markdown looks
like the one that did not get the fix, and I checked that directly rather than inferring it:
I ran the same payloads through cmark-gfm from 250 bytes to 256,000 bytes and every one was
linear.