Parsing [[[[[[… takes quadratic time

[andersk]

markdown.markdown('[' * 13000) takes about a minute (in 3.0.1 and master), with the time increasing by about a factor of four every time the length is doubled.

[waylan]

I expect this is because the link processor allows for nested brackets. On the bright side, it doesn't crash (many such things raised recursion errors back in version <2.0). The fact is, performance is not a high priority for us. If you are providing such a unrealistic input, then I don't really care that it is slow. Although, I'm curious how different this is for version 2.x as we changed the bracket parsing in 3.0.

[facelessuser]

Makes sense to me. I'm sure it's running through the entire algorithm for each [. And for each [, it runs to the end of the chain of [. So, if you double the size of the string, it goes through the entire string trying to resolve all the [. This allows you to nest [[]], which is a good thing.

Currently, I see no problem with this behavior as the current compliant is based on an unrealistic situation. A document consisting of a chain of 13,000 [ is not a good argument for changing anything. To me it seems like an academic exercise to show you can construct documents that take a long time to parse.

Before, we used regular expression which failed miserably when tasked with nested []. The new algorithm allows it to handle as much nesting as needed. As far as performance is concerned, I would say it behaves as one would expect.

If we are just concerned someone could create a document that freezes up the parser, we could add nested bracket limit just to prevent the parser from getting tied up in ridiculously large nested situations.

[andersk]

Thanks for the quick response.

My perspective is that I’m concerned about denial of service attacks on applications parsing user input as Markdown. This isn’t an academic exercise—this very comment is user input that GitHub is parsing as Markdown, and you can imagine that they’d be really sad if I could easily cause their parser to spin for minutes or hours, whether maliciously or by accident. In an even less hypothetical sense, I’m filing this issue in the aftermath of a real denial of service attack that actually took down a large application via a complexity attack on Python-Markdown.

Now, obviously, you’re under no obligation to support my use case. You are free to decide that Python-Markdown is not designed for use on untrusted input. Part of the reason I’m filing this is that I’d like to know how these kinds of issues will be handled. Should I file more of them, or should I work on finding a Markdown library that better suits my requirements?

[facelessuser]

I’m filing this issue in the aftermath of a real denial of service attack that actually took down a large application via a complexity attack on Python-Markdown.

Context is important, and I think pointing this out is important when filing such an issue.

I suspected near the end of my reply that the act of a hanging parser might have been the direction you were heading in, which is why I also suggested the possibility of limiting the recursion. In general, you aren't going to get a performance boost unless you cache the nested brackets that you've already evaluated to avoid reprocessing them again later as you move down the list of [ (not really practical in our current environment), or you simply limit the recursion depth.

By limiting the recursion depth, let's say by 10, instead of processing 13,000 nested [, then 12,999, etc., you only process 10 of them when testing each [.

[waylan]

This projects goals are documented as follows (emphasis added):

• Maintain a Python 2 and Python 3 library (with an optional CLI wrapper) suited to use in web server environments (never raise an exception, never write to stdout, etc.) as an implementation of the markdown parser that follows the syntax rules and the behavior of the original (markdown.pl) implementation as reasonably as possible (see differences for a few exceptions).

• Provide an Extension API which makes it possible to change and/or extend the behavior of the parser.

In general, the way that any Markdown parser informs the document author that they provided bad syntax is by outputting an illformed document. In other words, Markdown always returns output.

That said, we do no input sanitation. If input causes the parser to crash, we consider that a bug and will modify the parser to not crash. However, that is it. Performance is not a high priority (it is not even mentioned in the "goals"). If you are allowing your users to post large documents, then it is your responsibility to sanitize them properly (perhaps limit their size?).

By the way, for a good review of the issues involved in avoiding XSS attacks via Markdown I suggest reading Markdown and XSS by Michel Fortin (the developer of PHP Markdown). There is no Markdown parser which fully addresses that issue on its own. If you need to address this yourself, then I would think you should expect to address other attack vectors on your own as well.

In other words, as a security concern, this is out-of-scope for any Markdown parser to be concerned with. Regardless, there are some parsers out there which put a higher priority on performance. But they don't have the low barrier-to-entry for creating extensions. We simply have chosen a different set of compromises. Only you can decide which set of compromises meets your needs.

[waylan]

By limiting the recursion depth, let's say by 10

I suppose its noteworthy that in previous versions, we supported 6 levels of brackets. And that was because we used a regex which had six levels hardcoded into it. In over a decade, I don't recall ever getting a complaint about that limit. I suppose we could artificially limit the existing implementation to some arbitrary nesting level.

[facelessuser]

It's an idea at least. I think the current algorithm is more robust than the regex was, but while it is nice to be able to support any amount of nesting, maybe endless nesting is a bit unrealistic 🤷‍♂️ .

[andersk]

If you’re concerned about crashing with recursion errors, what are your thoughts on markdown.markdown('>' * 1000)?

(Personally I’m somewhat less concerned by that, since it’s much easier to detect and recover from an explicit crash.)

[facelessuser]

There are areas where there may still be recursion, and possibly some areas that are hard for us to eliminate currently. And yes with recursion, you can get crashes when the limit is exceeded. Generally, we try to avoid crashes were possible.

The point that was being made is that the new algorithm for handling [] wasn't introducing exceptions, something we try to avoid. It gave us the benefit of handling nested [] and () in links in a more sane and robust way without using recursion which can cause exceptions (which has been a problem in the past). But yes, if abused, it can cause cycles to get chewed up, something that limiting the nesting depth should solve.

It would still allow nesting horizontally [[] [] []] which should perform much better than the biggest issue of massively deep nesting. [[[[[[[[[[[[[[[[[[[[[[[[]]]]]]]]]]]]]]]]]]]]]]]].

[andersk]

There also seem to be problems in the horizontal direction: markdown.markdown('[]()' * 20000) takes quadratic time (and this case probably has a reasonably large performance impact on “real” documents, too).

[facelessuser]

There also seem to be problems in the horizontal direction

When I mentioned horizontal, I was referring to horizontal nesting, which does not perform as badly as it doesn't re-evaluate the same things as often.

markdown.markdown('[]()' * 20000)

Unfortunately, I don't agree that there is problems with this. This is simply evaluating 20,000 links. If you give the parser large enough data to parse, it's going to take a while. You can probably use almost any syntax with a big enough number to cause things to freeze up. At that point, maybe you should implement a time out on your server, or limit the size of your input coming in.

[andersk]

One would think that careful design would avoid needing 20,000 ⋅ 20,000 operations to parse 20,000 links; there’s no fundamental reason that each link needs to do something with each other link. I’ll grant that perhaps the current design of the parser makes this difficult to avoid, but I think it’s wrong to dismiss the problem as “simply too much data”. The question is whether there’s interest in trying to solve it.

[facelessuser]

If there's a legitimate problem then we'll of course fix it. We'll have to double check what the algorithm is doing. If parsing time exploding then it would most likely be because it is trying to parse the whole chain of links because the algorithm doesn't cut off the parsing after the first link, which might be possible. There might be a case that is causing that.

[mitya57]

If you’re concerned about crashing with recursion errors, what are your thoughts on markdown.markdown('>' * 1000)?

Can you please file a separate issue for this bug? (FWIW '>' * 331 is enough to reproduce it)

[andersk]

@mitya57 Sure, filed as #799.