BradSwain

> while stack clashing was considered and is a theoretical possibility — denial of service was considered to be the realistic impact.

In many contexts, regular process failure is still a vulnerability.

And the stack is (usually) tiny compared to other resources. It doesn't take that many nested calls to get to the bottom of the stack. At least compared to trying to exhaust the heap or keep the CPU busy long enough to cause DoS.

> Unixes give us that. You have to fork the computation to have it contained in its own process

Is forking a new process on each call to a recursive function practical?

> Outdated programming practices are.

What is the outdated programming practice at fault here?

I agree. I use the word dangerous to mean there are risks that need to be considered, not that recursion should never be used under any circumstances.

In the general case though, recursion can be tricky to think through, the stack is small, and malicious inputs can be very creative.

> Any recursive function can be transformed into a tail recursive form, exchanging stack allocation for heap allocation. And any tail recursive program can be transformed into a loop (a trampoline)

A computer can chug through millions of loop iterations. I don't think tail recursion will ever result in heap exhaustion. But a stack overflow can be caused with tens of thousands of nested calls, which is tiny in comparison.

Recursion based stack overflow issues are easier to exploit because modern computer's stack space is much smaller relative to other resources.

> On modern "hosted" OSes, there are safeguards about stack overflows, which will quickly kill your process.

There are lots of contexts where a processing being killed is bad.

Sending a deeply nested JSON object as part of a request to some API should not crash the server that handles the request.

In contexts where availability matters, recursing on user supplied input is dangerous.

This is a neat bug!

A colleague and I spent some time last year looking for DoS vulnerabilities caused by recursing on user input [1].

TL;DR: With CodeQL and some manual review, we found several issues resulting in two assigned CVEs, a rustsec advisory, and a handful of fixes implemented in various projects.

We mostly looked at Java projects. It is interesting to see a C vulnerability from around the same time.

It would be cool to see a larger study on how common this issue is across different programming languages.

[1]: https://resources.trailofbits.com/input-driven-recursion-whi...

This is a good point, but recursion and iteration have very different security implications in practice. Iterative functions are much harder to exploit.

It doesn't take many stack frames to overflow the stack. Java only handles ~10k frames by default. Most applications will have no problem with 10k loop iterations, and it might take millions to cause a notable slowdown. It is usually trivial to craft an input causing ~10k recursive calls, but an input causing millions of iterations is likely much harder. One example from the whitepaper that crashed a real application is a string repeated 20k times taking up ~200KB. To get to one million iterations the request would be ~20MB.

The failure modes also differ significantly. Recursion crashes the application with a stack overflow. Iteration just ties up a thread. Web frameworks often auto kill busy threads after timeout anyway.

You could argue that catching StackOverflow exceptions is a built in defense as well, but that only works for langauges that support catching such exceptions. Even among those languages, there are many DoS CVEs for crashes caused by stack overflows.