GHSA-c8j7-8cv4-2xmq: Mistune plugins/formatting: quadratic-time parsing on long runs of `~~x~~`, `==x==`, and `^^x^^` markers (strikethrough / mark / insert)

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 emphasis) would do this work in O(N) total. The bounded regex on each individual scan does not