-
-
Notifications
You must be signed in to change notification settings - Fork 353
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Quadratic complexity on highly nested lists #1010
Comments
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. 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. |
Initial checklist
Affected packages and versions
remark 14.0.2
Link to runnable example
No response
Steps to reproduce
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
The text was updated successfully, but these errors were encountered: