Quadratic-time inline-link parsing: many unclosed [...]( cause a CPU DoS

Ouverte
  • Quelque chose ne va pas ?
#750 0 commentaires 0 réactions 0 personnes assignées Voir sur GitHub

Les mainteneurs répondent en général sous 3 jours

@ParamTanna y travaille déjà.

Depuis le 28/10/2026.

  • #751 par @ParamTanna — ouverte

Évaluation

Difficulté
4/5
Temps estimé
3-5 jours
Accessibilité débutants
30/100
Type d'issue
Bug
Clarté
Plutôt claire
Activité
À l'abandon
Stack technique
python
Domaine
performance

Piste de recherche

Reproduce first with the timing snippet in the report, then profile "[a](" * 4000 to confirm the cost sits in _find_balanced and the self._inline_link_title.search call inside parse_inline_anchor_or_image in markdown2.py. Read how the inline-link loop rebuilds text per resolved link, since the issue warns a per-text paren cache regresses "[a](b) " * 4000 badly; check PR #751 before duplicating work. Done means the unclosed-( benchmark scales roughly linearly while the existing test suite (including the link/image cases) still passes and no link-heavy slowdown appears.

Rédigé par le modèle d'indexation à partir du texte de l'issue.

Description

Summary

markdown2.markdown() is quadratic in the number of unclosed ( inline-link destinations. A small input of repeated [a]( (or ![a]( for images) grows with the square of its length and pins a CPU. This is the same denial-of-service class as #741 / #707 / #633, with a different trigger (the inline-link destination scan).

Reproduce

import time, markdown2
for n in (1000, 2000, 4000):
    doc = "[a](" * n
    t0 = time.perf_counter()
    markdown2.markdown(doc)
    print(f"{n:5d} links  {len(doc):6d} bytes  {time.perf_counter()-t0:6.2f}s")

 1000 links    4000 bytes    0.19s
 2000 links    8000 bytes    0.82s
 4000 links   16000 bytes    3.16s

Doubling the input roughly quadruples the time. "![a](" * n (images) behaves the same, slightly slower.

Where the time goes

cProfile on "[a](" * 4000 (3.39s total):

ncalls  tottime  function
  3999    2.363   markdown2.py:_find_balanced
  4001    0.988   {method 'search' of re.Pattern}   # self._inline_link_title.search

parse_inline_anchor_or_image calls _find_balanced(text, end_idx, "(", ")") for every [...](. When the ( never closes, _find_balanced scans to the end of the text, and the link loop runs it once per [...](, so the total work is O(n²). The following self._inline_link_title.search(text, idx, end_idx) with end_idx == len(text) is the other O(n) per call.

A note for whoever fixes it

This is more subtle than it looks. The obvious fix (precompute the balanced-paren positions once per text and reuse them, like a cache) is correct but regresses link-heavy documents badly, because the link loop rebuilds text every time a link resolves, so a per-text cache is invalidated on every resolved link. I measured "[a](b) " * 4000 going from 0.20s to ~87s with that approach. A good fix needs to avoid the full rescan without relying on a per-text cache, e.g. bailing out of both the _find_balanced scan and the title search as soon as the destination has no closing ). I am happy to help test a patch.

Environment

markdown2 2.5.x (PyPI) and master; CPython 3.12, Linux.

Langage dominant
Python
Étoiles
2.8k
Forks
477
Merge moyen
4 j 6 h
PR mergées (30 j)
12

Préparer son environnement

Ce projet ne fournit ni conteneur de développement, ni Dockerfile, ni guide de contribution : l'installation est à votre charge. Commencez par son README, et consultez notre guide de la première contribution pour les étapes générales.

Par où commencer

  1. Lisez l'issue en entier, puis le guide de contribution du projet.
  2. Signalez en commentaire que vous la prenez — cela évite que deux personnes fassent le même travail.
  3. Forkez le dépôt et travaillez sur une branche.
  4. Ouvrez une pull request qui référence le numéro de l'issue.

Autres issues de trentm/python-markdown2

Toutes les issues de trentm/python-markdown2

Issues similaires

Plus d'issues Python

Recevez les nouvelles issues par e-mail

Un résumé court des issues GitHub adaptées aux débutants.