Quadratic complexity on highly nested lists

[andersk]

Initial checklist

• I read the support docs
• I read the contributing guide
• I agree to follow the code of conduct
• I searched issues and couldn’t find anything (or linked relevant results below)

Affected packages and versions

remark 14.0.2

Link to runnable example

No response

Steps to reproduce

$ 'time' node -e 'import("remark").then(({remark}) => remark().process("* ".repeat(8000) + "a"))'
…
RangeError: Maximum call stack size exceeded
…
35.51user 1.63system 0:27.79elapsed 133%CPU (0avgtext+0avgdata 182780maxresident)k
0inputs+0outputs (4major+870117minor)pagefaults 0swaps

Expected behavior

Ideally, remark should run in linear time (O(n) for input of length n). There are other Markdown parsers that achieve this.

When I reported this privately, the response indicated that security against computational complexity attacks is not considered to be goal of this project. If that’s the case, that should at least be noted in the Security section of the readme, similarly to the existing note about security against cross-site scripting attacks.

Actual behavior

remark runs in quadratic time (O(n²) for input of length n). It spends over 30 seconds of CPU time on this 16001 byte input before failing with RangeError: Maximum call stack size exceeded. The CPU time quadruples each time the input size is doubled. This means an application accepting Markdown input from the user can be tricked into spending enormous amounts of computation for relatively little input.

Runtime

Node v16

Package manager

npm 8

OS

Linux

Build and bundle tools

No response

[ChristianMurphy]

When a grammar is ambiguous, the time to build a parse tree will exceed linear time (or space) complexity, that is true of all parsers.
Polynomial time is unfortunate but at times necessary, hence why this does not meet the standard of "DDoS" or "a security vulnerability".

All that said, remark does strive to be fast, if a way to lower the complexity can be found, without breaking with the CommonMark standard, a pull request would be welcome.