How do interpreters avoid stack buffer overflow-related undefined behavior and exploits?

Question

Most interpreters (including those for bytecode-based languages like Java) are assumed to be exempt of UB at the low-level. For instance, I would never expect NodeJS or the Hotspot JVM to allow blowing the stack in a way that the runtime doesn't handle early, e.g. by throwing an interpreted language-level exception. For this purpose, Java has StackOverflowExceptions, while JS engines may throw InternalError or RangeError (resp. SpiderMonkey and V8/Node), and maybe others.

As far as I know, there is no perfect way to handle stack overflows at lower level (C, C++, Rust [actually not Rust]) and they are considered UB. If we're lucky enough, we get a segfault, or memory is silently corrupted in the worst case.

I'm wondering how interpreters tend to deal with these issues. There's probably not a single answer to this question, and it may also depend a lot on hardware capabilities (mostly MMU) and OS features. Here are a few ideas I had:

Using a "virtual" stack (reified stack)

That's probably the simplest and obvious solution. Instead of using the host language's native call stack, allocate stack frames manually on a heap-allocated stack structure. Then your overflows turn into out-of-memory/overcomitting (none of which should be exploitable), and it's also easy to add an upper size limit.

However, this is supposedly slow and may start to be tricky to implement when native calls (built-ins or JIT-compiled) are involved. I'm sure that it's possible to play with assembly code and make your stack/frame pointers point to heap memory temporarily, but that would be nontrivial.

OS segfault handler

Similarly to how the Hotspot JVM implements implicit null checks by registering a segfault handler at the OS-level, it might be possible to receive a signal when the stack overflows. However, I'm not sure that this is super reliable nor that all OSes/hardware support it. It can be a nice way to do things when it's available, but would require a fallback.

Guess the stack limit and check

Some OSes may allow dynamically checking the maximum call stack size. You can also expect it to always be larger than a constant value. In these cases, you can implement guards in recursive functions that throw an exception when the limit is reached, with overly conservative slack just to be sure. That is, IIRC, how GNU R checks for stack overflows.

---

The Wikipedia page on Stack buffer overflows mentions protection schemes, but they seem to be unreliable and more useful as general safety measures in a program that isn't malicious and doesn't evaluate arbitrary code.

Answer 1

It’s not difficult at all for an interpreter to set a hard cap on stack size that is well within what the system can support, and they do. Platform stack size limits are no longer at a level where anything but runaway recursion will hit them, so these limits have no effect on almost all programs, and they’re often configurable for the situations where the user knows they will need more.

We can see examples of different variations of that in existing systems:

• The JVM enforces a software stack memory limit that is configurable at run time (or with -Xss on the command line). The default is platform-specific but well within acceptable limits.

  • Linux/x64 (64-bit): 1024 KB
  • macOS (64-bit): 1024 KB
  • Oracle Solaris/x64 (64-bit): 1024 KB
  • Windows: The default value depends on virtual memory

  It knows the stack effects of every method precisely from bytecode verification and is able to detect when that limit is reached. If you set a value that is too high for your system, you can blow the system stack with all of the effects that go with that.

• Python has a maximum recursion depth — this is a limit of recursive calls, not a stack memory consumption limit. It is also configurable with a platform-specific default, and you can also create problems by making it too large. Each function invocation increments and checks the level as part of its bookkeeping.

• Many interpreters do reify stack frames on the heap anyway, for language semantic reasons or ease of debugging. There can be performance implications of this, but for most cases these don’t really matter to the extent of being worth doing anything about.

  These won’t hit stack limits from the in-language data allocations, but can still from their own recursion. They will likely still have a recursion cap in the manner of Python in order to report useful errors — but if they don’t, and they have naive recursion, they could blow the stack too; this is an implementation quality issue.

There is nothing that makes interpreters inherently safe from exceeding system stack limits, but it is nearly trivial to implement them to avoid it and so production ones do. There’s not really anything special about them here as contrasted with other software, other than having a few obvious points to insert the bookkeeping.

Answer 2

If you're interested in how these sorts of things were done in ancient times, I wrote the stack probing code for VBScript and JScript back when it was the 1990s. Which was complicated by the fact that it had to work on Windows 3.1, Windows 95 and Windows NT, all of which have different approaches to stack management. VBScript and JScript were written in C++.

• For executing code in the scripts themselves, it was clearly necessary to allocate our own stack management objects. Particularly for JScript, which had the ability for user code to inspect some aspects of the call stack.

• However, we made the somewhat dubious choice of calling a method in the interpreter every time a function was called in the script, which meant that "real" call stack was consumed by every call to a script function, and that's a scarce resource. Threads only get 1MB of stack by default.

If you don't know how stacks work in Windows, let me briefly explain how it works in modern Windows. (Windows 3.1 was different in ways I no longer remember.) This will be a simplification for pedagogic purposes.

The stack is a 1MB chunk of virtual memory. The entire stack is reserved but not committed to page file/memory. The "bottom" page is then committed. When the bottom page is full, the next-to-bottom page gets a fault when accessed, and it becomes committed. The top page is special. The first time the top page is hit, it triggers a stack overflow exception. The second time it is hit, the process is ended immediately. You get only one chance to blow the stack in Windows!

This then leads to some nasty problems. We want to detect out-of-stack cleanly in scripting and report an error to the host -- the browser, typically. But we quickly got bug reports about unbounded recursion in a script causing the browser process to end.

What was happening was:

• Before we do a script function call in the interpreter, we know that we're going to be consuming real stack to recurse on the interpreter, so I implemented a probe that checks to see how many pages away we are from the deadly top-of-the-stack page. If we're too close, we don't make the call. We issue an out of stack script error and tell the browser.

• But... the browser then calls a whole bunch of its own functions, some of which may be recursive, as part of its error handling, and it touches the final stack page. The browser then catches the resulting stack overflow exception.

• And now we're in a state where the next time anything touches that final page, the process is destroyed.

What a pain. We ended up building a system where we probed the stack before script function calls AND before calling into the browser to report a scripting error; in the event that we believed there would not be enough stack for the browser to handle the error, we unwound the real stack back a few pages by deferring the call into the browser error service until later.

In short, it was a godawful mess. As IE got more complicated, it used more stack on any callback into the browser, so several times I had to tweak the minimum number of pages we'd keep reserved at the end of the stack to avoid this sort of bad user experience.

Answer 3

As far as I know, there is no perfect way to handle stack overflows at lower level (C, C++, Rust)

While there's no way at the language level (at least for C/C++, not sure about rust), you can go below the language level to the undelying hardware/OS level (which requires understanding how your language implementation interacts with that lower level).

For example, on POSIX systems, you can use guard pages in the stack that will cause a signal, and have a signal handler using a separate stack (sigaltstack) to handle stack overflows. As long as you can guarentee that overflows do not happen in aynsc-unsafe functions, you can use siglongjump to reset/unwind the stack (though that may not interact well with C++'s exceptions and stack unwinding -- you need to check your implementation to see if that can work). You can protect the async-unsafe functions by inserting stack probes before calling them (to trigger the stack overflow before the call rather than in the call), though that again requires some knowledge of the implementation you are using and what its stack requirements are.

Answer 4

As far as I know, there is no perfect way to handle stack overflows at lower level (C, C++, Rust)

There are ways, it's just a matter of cost -- code-size and run-time performance -- C and C++ compilers typically don't bother (though there are flags) and Rust compilers do, as doing otherwise would be unsafe.

Guard Page + Stack Probing

The most practical way when available is to setup a guard page. That is, after the N pages required for the stack itself, the run-time will reserve an N+1th page with no permission (no read, no write). Any attempt to access the memory of this page will then trigger a page-fault, for which a handler is installed that will check whether the page is a guard page and if it is signal, in some way, that a stack-overflow occurred.

For languages where large values can be put on the stack, stack-probing may be necessary to trigger the guard page. That is, if the guard page is 4 KB, and the function stack starts at -16 bytes before it, then accessing the last element of an 8KB array on the stack would jump past the guard page. The compiler, then, for any function with a stack size greater than the page size, will introduce a small prelude in the function which will probe every 4KB before the start of the actual user-code of the function, thereby triggering the page guard if the entire stack frame is not within the stack.

This solution (guard page + stack probing) is generally the best in terms of performance. The platform already checks page permission access when accessing a new page anyway, so the guard page itself has nigh zero-cost. The stack-probing has a small cost (code-size and run-time), but functions with a large stack-frame are rare, and the run-time cost is typically a tiny fraction of the function cost -- probing a few bytes here and there is a much smaller cost than writing the bytes of the entire stack frame.

Note: the above implementation is used by rustc on all major platforms.

Systemic Check

Another possibility is to simply know how much stack size is remaining, and to check in the prologue of everything function whether the current stack frame + some red zone (in case of non-leaf function) will fit... the red zone being reserved so that the next function being called has space to execute the probing, or that very small functions need not be instrumented.

This is more costly, requiring a small operation on each function entry, but may be used even in the absence of OS facilities, or even of MMU.