GHSA-c8j7-8cv4-2xmq

Summary

Type: Algorithmic-complexity denial of service. A run of N closed pairs ~~x~~~~x~~... (or the analogous ==x== for mark, ^^x^^ for insert) causes O(N²) work in the formatting parser. With the strikethrough, mark, or insert plugin enabled, an 8 KB input pegs the CPU for ~4 seconds; 16 KB → ~17 seconds. File: src/mistune/plugins/formatting.py, lines 13-15 (the _STRIKE_END / _MARK_END / _INSERT_END patterns and their per-position scan). Root cause: for each opening ~~/==/^^ the parser scans forward for the matching close pattern. The scan itself uses a bounded regex, but the parser tries the close-scan at every potential start position. For input shaped like ~~x~~ repeated N times, every ~~ is examined as a possible start, each scan covers up to the end of input. Total work is O(N²). Default config without these plugins handles the same input in linear time (4 ms for 4000 reps), confirming the cost is in the formatting plugin's per-marker scan, not in core parsing.

Affected Code

File: src/mistune/plugins/formatting.py, lines 12-16.

_STRIKE_END = re.compile(r"(?:" + PREVENT_BACKSLASH + r"\\~|[^\s~])~~(?!~)")
_MARK_END = re.compile(r"(?:" + PREVENT_BACKSLASH + r"\\=|[^\s=])==(?!=)")
_INSERT_END = re.compile(r"(?:" + PREVENT_BACKSLASH + r"\\\^|[^\s^])\^\^(?!\^)")
# Each pattern is scanned forward from every start position fired by the
# corresponding inline rule. The end-pattern itself is bounded; the cost
# comes from the surrounding parser invoking the scan at every '~~' / '==' / '^^'
# token in the input, giving N starts × O(N) per scan = O(N^2) total.

Why it's wrong: the same algorithmic-complexity flaw class as [ / [a parsing in core: a per-token retry loop without memoisation of failed positions. Each formatting marker is tried as both a potential start and as a continuation. A linear-pass delimiter-stack algorithm (matching how commonmark-py and markdown-it-py handle...