GHSA-j7hq-qg5v-47jq: 
Rust vulnerability analysis and mitigation

Summary

Rendering a GFM table to HTML takes time quadratic in the number of cells per row, while parsing stays linear. A table of about 130 KB takes about 3 s to render. Disclosure: an AI coding agent (Claude) found this while measuring renderer limits for a small Markdown pad we build on comrak. It made the measurements and wrote this report; I read it before sending. I'm sending it privately because your contributing guide allows LLM-written reports only for security issues, and you have treated quadratic cases as such.

Details

Cause: in render_table_cell (src/html.rs, the loop at lines 1187–1192 in 0.57.0 and 1197–1202 on main at 0f2c946), each cell finds its column by walking from the row's first child to itself. So a row of n cells costs about n²/2 sibling steps. The XML renderer does the same for header cells with node.preceding_siblings().count() (src/xml.rs, line 244 in 0.57.0 and 257 on main). CommonMark output is not affected. The pathological tests don't catch it: a row is limited to u16::MAX cells, and pathological_table_columns_1/2 use 100 000 columns, so their input is not a table. From reading the code (not measured): body rows are padded to the header width, so short body rows each add the cost of a full row, up to MAX_AUTOCOMPLETED_CELLS. A possible fix, in words: while rendering, remember the last cell rendered and its index. If the current cell's previous sibling is that cell, its index is one more; otherwise fall back to today's walk. The parser gives every row exactly as many cells as the header, so alignments stay as they are, including after AST edits and with create_formatter! overrides of rows or cells. Keeping a running counter that the row resets would break when a custom formatter overrides the row or a cell. Storing the column on the cell at parse time would go stale after AST edits; it might fit with the grid tables work in #820. The same approach would apply to the XML renderer.

Proof of concept

comrak 0.57.0, default-features = false, extension.table = true, release build, rustc 1.99.1, Apple M5 Max. The input is one header row of n cells and its delimiter row, nothing else:

let input = format!("{}|\n{}|\n", "|a".repeat(n), "|-".repeat(n));

Impact

Denial of service (CPU) for services that render untrusted Markdown with the table extension enabled: an input of about 130 KB costs about 3 s of CPU per render. CWE-407 (Inefficient Algorithmic Complexity). Severity is left to you. We work around it in our own cell renderer for now. Thank you for comrak.