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

Abierto
  • ¿Algo no está bien?
#750 0 comentarios 0 reacciones 0 asignados Ver en GitHub

Los mantenedores suelen responder en 3 días

@ParamTanna ya está trabajando en esto.

Desde el 28/10/2026.

  • #751 de @ParamTanna — abierto

Evaluación

Dificultad
4/5
Tiempo estimado
3-5 días
Aptitud para principiantes
30/100
Tipo de issue
Error
Claridad
Bastante claro
Estado de actividad
Estancado
Stack tecnológico
python
Área
performance

Línea de trabajo

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.

Escrito por el modelo de indexación a partir del texto del issue.

Descripción

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.

Lenguaje dominante
Python
Estrellas
2.8k
Forks
477
Merge medio
4 d 6 h
PR fusionados (30 d)
12

Preparar el entorno

Este proyecto no incluye contenedor de desarrollo, Dockerfile ni guía de contribución, así que la configuración corre por tu cuenta: empieza por su README y consulta nuestra guía para la primera contribución para los pasos generales.

Primeros pasos

  1. Lee el issue completo y luego la guía de contribución del proyecto.
  2. Comenta en el issue que vas a ocuparte — evita que dos personas hagan lo mismo.
  3. Haz un fork del repositorio y trabaja en una rama.
  4. Abre un pull request que haga referencia al número del issue.

Más de trentm/python-markdown2

Todos los issues de trentm/python-markdown2

Issues similares

Más issues de Python

Recibe los nuevos issues en tu correo

Un resumen breve de issues de GitHub para principiantes.