Skip to content
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

Parsing [\\\\\\… takes exponential time #157

Closed
andersk opened this issue Mar 9, 2019 · 4 comments
Closed

Parsing [\\\\\\… takes exponential time #157

andersk opened this issue Mar 9, 2019 · 4 comments

Comments

@andersk
Copy link
Contributor

andersk commented Mar 9, 2019

new commonmark.Parser().parse("[" + "\\".repeat(n)) runs in exponential time:

[\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\ → 1.2 seconds
[\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\ → 1.8 seconds
[\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\ → 2.9 seconds
[\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\ → 4.7 seconds
[\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\ → 7.5 seconds
[\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\ → 12.5 seconds
[\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\ → 20.2 seconds
[\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\ → 32.8 seconds
[\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\ → 52.7 seconds
[\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\ → 83.9 seconds
[\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\ → 137.8 seconds

This could be a denial of service vulnerability in an application that parses user input.

andersk added a commit to andersk/commonmark.js that referenced this issue Mar 10, 2019
ESCAPED_CHAR already matches `\\`, so matching it again in another
alternative was just causing an exponential complexity explosion.

Fixes commonmark#157.

Signed-off-by: Anders Kaseorg <andersk@mit.edu>
@andersk
Copy link
Contributor Author

andersk commented Mar 10, 2019

There are also quadratic time cases, like new commonmark.Parser().parse("[](".repeat(30000)). (Would you like separate bug reports for these?) Edit: This quadratic one was reported in #129.

@jgm
Copy link
Member

jgm commented Mar 10, 2019 via email

@jgm
Copy link
Member

jgm commented Mar 10, 2019 via email

jgm added a commit to jgm/commonmark-hs that referenced this issue Mar 10, 2019
commonmark currently exhibits quadratic behavior for this case.
See commonmark/commonmark.js#157.
@jgm
Copy link
Member

jgm commented Mar 10, 2019

The second case probably has to do with parseLinkDestination (though I don't see anything there that would explain quadratic behavior).

andersk added a commit to andersk/commonmark.js that referenced this issue Mar 10, 2019
ESCAPED_CHAR already matches `\\`, so matching it again in another
alternative was just causing exponential complexity explosion.

Fixes commonmark#157.

Signed-off-by: Anders Kaseorg <andersk@mit.edu>
andersk added a commit to andersk/commonmark.js that referenced this issue Mar 10, 2019
ESCAPED_CHAR already matches `\\`, so matching it again in another
alternative was just causing exponential complexity explosion.

Fixes commonmark#157.

Signed-off-by: Anders Kaseorg <andersk@mit.edu>
andersk added a commit to andersk/commonmark.js that referenced this issue Mar 10, 2019
ESCAPED_CHAR already matches `\\`, so matching it again in another
alternative was just causing exponential complexity explosion.

Fixes commonmark#157.

Signed-off-by: Anders Kaseorg <andersk@mit.edu>
andersk added a commit to andersk/commonmark.js that referenced this issue Mar 10, 2019
ESCAPED_CHAR already matches `\\`, so matching it again in another
alternative was causing exponential complexity explosion.

This makes the following behavior changes:

* `[foo\\\]` is no longer incorrectly accepted as a link reference.
* `<foo\>` is no longer incorrectly accepted as an angle-bracketed
  link destination.

Fixes commonmark#157.

Signed-off-by: Anders Kaseorg <andersk@mit.edu>
@jgm jgm closed this as completed in #158 Mar 11, 2019
jgm pushed a commit that referenced this issue Mar 11, 2019
ESCAPED_CHAR already matches `\\`, so matching it again in another
alternative was causing exponential complexity explosion.

This makes the following behavior changes:

* `[foo\\\]` is no longer incorrectly accepted as a link reference.
* `<foo\>` is no longer incorrectly accepted as an angle-bracketed
  link destination.

Fixes #157.

Signed-off-by: Anders Kaseorg <andersk@mit.edu>
jgm added a commit that referenced this issue Mar 11, 2019
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants