Skip to content

Parsing *_*_*_… takes quadratic time #583

@andersk

Description

@andersk
$ time node -e 'new require("markdown-it")("commonmark").parse("*_".repeat(10000))'
0.65user 0.01system 0:00.65elapsed 103%CPU (0avgtext+0avgdata 43360maxresident)k
0inputs+0outputs (0major+5493minor)pagefaults 0swaps
$ time node -e 'new require("markdown-it")("commonmark").parse("*_".repeat(20000))'
3.05user 0.01system 0:03.06elapsed 100%CPU (0avgtext+0avgdata 49972maxresident)k
0inputs+0outputs (0major+7101minor)pagefaults 0swaps
$ time node -e 'new require("markdown-it")("commonmark").parse("*_".repeat(40000))'
19.67user 0.05system 0:20.29elapsed 97%CPU (0avgtext+0avgdata 65260maxresident)k
0inputs+0outputs (0major+10989minor)pagefaults 0swaps
$ time node -e 'new require("markdown-it")("commonmark").parse("*_".repeat(80000))'
88.29user 0.17system 1:30.10elapsed 98%CPU (0avgtext+0avgdata 102900maxresident)k
0inputs+0outputs (0major+20453minor)pagefaults 0swaps

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

Metadata

Metadata

Assignees

No one assigned

    Labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions