On guarding against stack overflows while using recursion

1

I wrote this in response to @newpavlov's comment in the thread on Modern C++ memory safe, but realized it got a bit more sprawling than I intended and figured it might make as a nice topic for a new thread.

The main context here was discussion about, I think, improving the reliability of programs through voluntary restrictions on how the code for those programs is written. This particular restriction is about recursion. The main pain point of recursion is that if the call depth is somehow connected to the size of untrusted or user input, then it's likely possible to craft inputs that result in a stack overflow and thus possibly provoke a denial of service vulnerability.

Since the regex crate tries to make itself suitable for untrusted haystacks and untrusted regexes, its parser goes out of its way to avoid the aforementioned recursion pitfall. It does this via two methods:

  • When parsing the concrete syntax of a regex into an Ast, it never uses recursion and instead pushes what would be on the call stack to an explicit stack on the heap.
  • During parsing, it checks the "nesting depth" of the resulting Ast. If it's too big, then an error is returned. An important invariant of this check is that the size of the Ast is proportional to the size of the concrete syntax. (For example, you can't write \pL{100000} and get a monstrous Ast. The Ast doesn't expand repetitions and doesn't even try to resolve \pL (which is huge on its own) into a sequence of non-overlapping codepoint ranges.)

The regex-syntax crate also tries to avoid recursion in other places too, but is pretty hit or miss. For example, Ast->Hir translation doesn't use recursion, but Hir->NFA does. The Hir printer doesn't use recursion, but literal extraction does. The Display impl for Hir doesn't use recursion, but its Debug, Clone and PartialEq impls do. So now I'm considering removing the recursion mitigations on Hir at least, and just leaving them in place for the Ast. The idea here is that since we avoid recursion and check a nesting depth, maybe that's good enough.

Anyway, what follows is my original reply.

Since I was pinged with respect to restrictions in regex-syntax regarding recursion, I'll add a few quick notes.

I have personally found that avoiding recursion to be quite annoying. The most natural representation for things like an AST is via a recursive data type. And many of the algorithms on those types are most naturally conceived via structural induction on the type. The difference in code complexity between structural recursion and using something like a visitor is enormous. The AST->HIR translator in particular is pretty gruesome.

Avoiding recursion is annoying enough that once the AST is parsed and translated into the HIR, I've generally tended to just use recursion. In particular, for literal extraction and for converting the HIR into an NFA. (There is a heap based visitor for the HIR which I've used in some places, e.g., for a printer, but it has largely been a failure because I hate using it.) The reason why this works is because a nest limit is imposed. Namely, since recursion is not used in the initial parsing of the AST and because parsing will fail if the AST is too deeply nested, then using recursion downstream from that tends to be okay. There's certainly no guarantee of course, because who's to say that my arbitrarily chosen nest depth has anything to do with the stack size configured by the caller? Nada! But... the heuristic seems to work in practice, and my evidence of that is "people haven't complained." (Which is maybe not great evidence.) It really only gets tested if people are compiling untrusted regexes, and that is quite a precarious thing to do, even if the parser guards against overflow.

On top of all of that, despite ensuring that the Drop and Display impls of Hir are implemented without recursion, its Clone and Debug and PartialEq impls are not. Seems kind of like a bad situation if you ask me. :-/

So what's my point? I don't know. I don't know if I have a strong point to make here other than that mitigating against recursion is supremely annoying, difficult to get right and I'm not totally clear on how much it helps when compared against simpler heuristics such as a nest depth.

(There are also different patterns to recursion other than a Visitor-like trait, and maybe investigating some of those approaches would help make things easier. And yes, I've read this post on recursion schemes in Rust, but it has its own downsides and appears to be strongly motivated by perf, which isn't as much of a concern in regex-syntax.)

12 Likes
2

I think it could be worth to expand the scope a bit. The end goal of forbidding recursion is to make maximum stack usage of a function bounded, which is a subset of bounding total memory usage (stack + heap + statics + etc), which in turn can be viewed as a subset of limiting other resource used by a function (e.g. execution time), which finally can be viewed as inferring some properties of a program (could this function panic, could it potentially do IO, etc.).

If we are to talk about stack usage only, then there are other potential pitfalls such as dynamic dispatch. By default, we can not tell how much stack will be used by a trait object method, under the hood it may use recursion or, even worse, may call function from a dynamically linked library.

If we are to remember the end goal, then using recursion with statically enforced nesting limit is a perfectly fine solution, though it may be a bit harder for compiler to properly enforce it compared to a non-recursive code. I guess you could write something like this by abusing const generics (have N as a parameter, do recursion inside function body only with N - 1), but I think it would be quite inefficient compile-time wise.

Unfortunately, Rust currently severely lacks facilities to enforce restrictions like "this function uses bounded amount of stack for all possible inputs". I understand difficulties associated with such feature (e.g. if we want to compute the bound, we would need LLVM's support for that), but such feature could be immensely useful in several contexts, such as embedded programming (people currently have to use various hacks to protect against potential stack overflows), bleaching stack in cryptography code, and even asynchronous programming based on stackfull coroutines without most of the complexities which the current Rust async system brings to the language (I have an article in work which expands on the latter).

3 Likes
3

Isn't the same true for heap overflow? If you get a really large regex, your AST could run out of memory.

I think stack allocation should be treated in the same way as heap allocation, i.e. there shouldn't be a tiny 2MB limit on it. Enforcing such a limit incentivizes people to allocate memory on the heap when a stack allocation would do, which is less efficient.

Now it may be a bit tricky to implement unbounded stacks on some platforms, especially on platforms without virtual memory, but I think it's doable.

3 Likes
4

No. As I mentioned, the key bit is that the size of the Ast is proportional to the size of the concrete syntax. So an effective means of limiting heap usage of the parser and the Ast itself is to limit the size of the regex pattern you parse.

The size of the NFA that is ultimately built is not proportional to pattern.len() though, and there are separate limits for configuring that heap usage.

You could in theory say that the call depth is also proportional to the size of the pattern, just like heap usage is. For example, a++++++ is a valid regex and each occurrence of + is another nesting level in the Ast. But you might want to permit regexes longer than 100 bytes while simultaneously not permitting regexes of a nesting depth more than 50. So a simple check on the length of the regex isn't really enough.

Finally, there is the practical reality that heap memory tends to be a more bountiful resource than stack size, regardless of what is theoretically possible.

2 Likes
5

Sure, so verify the nesting depth as well as length.

That's my point. This is an artificial restriction on stack usage that Rust has (because operating systems tend to default to this). It doesn't have to be that way, I would prefer a world where the stack is cheaper than the heap.

1 Like
6

That's the status quo.............

I understand what you're saying, but I'm just not interested in it. I'd prefer a lot of things too (including a world where stack is cheaper than the heap), but I can either sit around thinking about what the ideal world would be or I can do the best with what I have. :slight_smile:

2 Likes
7

Another thing to remember for recursive data types is that the implicit Drop glue will be call-recursive too. I see that regex-syntax already goes through this pain of a manual Drop that uses heap memory instead.

8

Pain indeed. But Ast derives things like Clone and PartialEq and Debug though, and those are therefore all recursive sadly.

9

Another solution is something like stacker, which creates new segments for the stack on the heap whenever the current stack segment is running low on memory. The Rust compiler uses it in a few visitors so that it doesn't run out of stack when the recursion_limit is increased by the user. Of course, it comes with the caveat that not all platforms support it, and it may affect performance. (At least, GDB takes far longer to print a stack trace through the heap-allocated segments than the initial stack.)

3 Likes
10

It's worth noting that the stack size limit is both controllable and is effectively unbounded (in 64bit). The trouble is that the running code doesn't control the current stack size, (obviously), and can't reliably communicate the stack size it expects in the type system. Otherwise it's not clear to me that heap allocation is much better than stack if you don't need out of order deallocation.

(Btw, you can specify the main and default thread stack sizes in the Windows exe file header, using linker flags, does anyone know if there's any equivalent for Linux? I have never managed to figure out how process launches work there)

11

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.