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.

Sign up for GitHub

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

Jump to bottom

pathologic input: O(n^2) with link ref. defs #238

Closed
mity opened this issue Feb 7, 2024 · 1 comment · Fixed by #239
Closed

pathologic input: O(n^2) with link ref. defs #238

mity opened this issue Feb 7, 2024 · 1 comment · Fixed by #239
Labels
bug

Comments

@mity
Copy link
Owner

mity commented Feb 7, 2024

Input generated with this leads to O(n^2) in time and space (output size):

$ python -c 'N=1000; print("[x]: " + "x" * N + "\n[x]" * N)'
@mity mity added the bug label Feb 7, 2024
@mity
Copy link
Owner Author

mity commented Feb 7, 2024

Seems cmark stops generating the links after reaching some threshold, pulldown-cmark is vulnerable too.

@mity mity mentioned this issue Feb 7, 2024
Closed
mity added a commit that referenced this issue Feb 7, 2024
@mity
Introduce an overall limit to link. ref. defs instantiations.
787d4b7 
This is to prevent time and output size explosion in case of input
pattern generated by this:

    $ python -c 'N=1000; print("[x]: " + "x" * N + "\n[x]" * N)'

We roughly allow to blowing up the input size of the document
16 times by link reference definitions or up to 1 MB, whatever is
smaller. When the threashold is reached, following reference definitions
are sent to output unresolved as a text.

Fixes #238.
@mity mity mentioned this issue Feb 7, 2024
Merged
mity added a commit that referenced this issue Feb 7, 2024
@mity
Introduce an overall limit to link. ref. defs instantiations.
a2c20ba 
This is to prevent time and output size explosion in case of input
pattern generated by this:

    $ python -c 'N=1000; print("[x]: " + "x" * N + "\n[x]" * N)'

We roughly allow to blowing up the input size of the document
16 times by link reference definitions or up to 1 MB, whatever is
smaller. When the threshold is reached, following reference definitions
are sent to output unresolved as a text.

Fixes #238.
@mity mity closed this as completed in #239 Feb 7, 2024
mity added a commit that referenced this issue Feb 7, 2024
@mity
Introduce an overall limit to link. ref. defs instantiations.
aa53f82 
This is to prevent time and output size explosion in case of input
pattern generated by this:

    $ python -c 'N=1000; print("[x]: " + "x" * N + "\n[x]" * N)'

We roughly allow to blowing up the input size of the document
16 times by link reference definitions or up to 1 MB, whatever is
smaller. When the threshold is reached, following reference definitions
are sent to output unresolved as a text.

Fixes #238.
mity added a commit that referenced this issue Feb 7, 2024
@mity
CHANGELOG.md: Fix link to an issue #238.
b85a599
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
bug
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

Introduce an overall limit to link. ref. defs instantiations. mity/md4c
1 participant
@mity