[mightybyte]

I would argue that the title is misleading and overly alarmist here. This particular bug may have involved recursion and a stack overflow, but that's like saying "malloc kills" in the title of an article about a heap overflow bug. The existence of stack overflow bugs does not imply that recursion is bad any more than the existence of heap overflow bugs implies that malloc is bad. Recursion and malloc are tools that both have pretty well understood resource limitations, and one must take those limitations into account when employing those tools.

[spyc]

Did you see the article references [1][2] from 2006 and 2017 that already argue that recursion is a security problem? It's not new just not well-known.

[1] https://www.researchgate.net/publication/220477862_The_Power...

[2] https://www.qualys.com/2017/06/19/stack-clash/stack-clash.tx...

[mrkeen]

You might be agreeing without realising it.

>> I would argue that the title is misleading and overly alarmist here. This particular bug may have involved recursion and a stack overflow, but that's like saying "malloc kills" in the title of an article about a heap overflow bug.

Let's see what the article[1] you cited says:

  Rule 3: Do not use dynamic memory allocation after initialization.
  Rationale: This rule appears in most coding guidelines for safety-critical software. The reason is simple: Memory allocators, such as malloc, and garbage collectors often have unpredictable behavior that can significantly impact performance.

If you think recursion is a known security problem, do you also think using the heap is a known security problem?

[pcwalton]

Arguably, Stack Clash is just a compiler bug--recursive code shouldn't be able to jump the guard pages. This was fixed in Clang in 2021 [1], in GCC even earlier, and in MSVC earlier than that.

[1]: https://blog.llvm.org/posts/2021-01-05-stack-clash-protectio...

[ndriscoll]

Recursion per se isn't an issue; unbounded stack use is. If you either know your input size is bounded (e.g. it's not user-generated) or use tail-recursion (which should get compiled to a loop), it's fine.

If your algorithm does unbounded heap allocations instead, you're still going to get oomkilled. The actual vulnerability is not enforcing request resource limits. Things like xml bombs can then exacerbate this by expanding a highly compressed request (so a small amount of attacker work can generate a large amount of receiver work).

[fc417fc802]

Exactly. The article would have been much more informative if it had detailed why the usual approaches to limiting resource usage wouldn't work to prevent DoS here.

[CJefferson]

The problem, in practice, is the limit for malloc on most systems is a few GB, while the default stack size on windows is 1MB, a stupidly small size.

I love recursion, so I will spawn a thread to do it in with a decent sized stack, but it’s very easy to break if you use defaults, and the defaults are configured differently in every OS.

[timewizard]

Using recursive techniques to parse potentially hostile inputs kills.

[fc417fc802]

Parsing anything from a potential adversary needs to account for failure. Unbounded recursion is secure (ie fails safely) if the compiler is working properly.

As to DoS, without looking at the code I'm unclear why various approaches to bounding resource consumption wouldn't have worked. I assume something specific to this library and how it is used must have prevented the obvious approaches. Still, not an issue in the general case.

[shadowgovt]

Guarding against unbounded recursion requires both compiler support and runtime environment support: you have to use enough resources to handle legitimate queries, but small enough memory constraints that a "query of death" doesn't kill nodes that are expensive to reactivate. Even then, by their very nature queries-of-death are usually hard to detect and a much simpler solution is something you can do in the static space, such as put an arbitrary hard-bound on recursion depth far below your resource constraints so you can fail the query without losing the whole processing node.

Google protobuffers have buried deep within at least their C++ parser an arbitrary hard limit for nesting depth (I think it may be 32). It's annoying when you hit it, but it's there for a reason.

[fc417fc802]

> Guarding against unbounded recursion requires both compiler support and runtime environment support

I feel like this is similar in spirit to saying "guarding against infinite loops requires both ...".

Where resource consumption is concerned, as you pointed out you can track that manually. Presumably you have to do that anyway, since the iterative case will also need to give up and fail the task at some point.

I really don't see where recursion itself introduces an issue here. I guess if you expect to pass through a great many nodes that don't otherwise trigger resource allocation except for the stack frame, and the compiler can't optimize the activation records away, it could be problematic. That's pretty specific though. Is that really the case for a typical parser?

[timewizard]

> can't optimize the activation records away

The stack frame also holds local variables. It's not just a return address. If your function requires 3 local variables then each call requires 3 stack slots.

[shadowgovt]

It was for the proto buffer c++ parser; couldn't say for typical.

[mannyv]

Nobody should use recursion in production code, period.

And no, it's not like malloc. If you don't understand why then you definitely shouldn't be putting recursive calls in your codebase.