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

オープン
  • 何か問題がありますか？
#750 コメント 0 件 リアクション 0 件 担当者 0 名 GitHub で見る

メンテナーはふだん 3 日以内に返信

@ParamTanna がすでに取り組んでいます。

2026年10月28日 から。

  • #751 @ParamTanna による — オープン

評価

難易度
4/5
見積もり時間
3〜5日
初心者へのやさしさ
30/100
issue の種類
バグ
明瞭さ
おおむね明確
活発さ
停滞
技術スタック
python
領域
performance

調査の方向性

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.

索引モデルが issue の本文から書いたものです。

説明

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.

主要言語
Python
スター
2.8k
フォーク
477
平均マージ
4日 6時間
マージ済み PR（30日）
12

環境構築

このプロジェクトには開発コンテナ、Dockerfile、コントリビューションガイドがありません。まず README を読み、一般的な手順ははじめてのコントリビューションガイドを参照してください。

はじめの一歩

  1. issue を最後まで読み、次にプロジェクトのコントリビューションガイドを読みます。
  2. 着手することを issue にコメントします — 二人が同じ作業をするのを防げます。
  3. リポジトリをフォークし、ブランチを切って変更します。
  4. issue 番号を参照したプルリクエストを送ります。

trentm/python-markdown2 のほかの issue

trentm/python-markdown2 の issue をすべて見る

似ている issue

Python の issue をもっと見る

新しい issue をメールで受け取る

初心者向けの GitHub issue を短くまとめたダイジェスト。