Is it possible for a programming language to confidently prevent undefined behavior on stack overflow?

Question

Given the following assumptions:

• We cannot check the stack pointer (%rsp) before every single push or sub operation
• We cannot calculate the maximum stack size at compile-time (e.g. our programming language supports recursion)

Is it possible to have a programming language that prevents undefined behavior in 100% of cases of stack overflow?

For example, many languages use MMU to catch stack overflow. But in my mind, if the language uses a dynamic heap, MMU cannot protect all memory, so theoretically, if the program enters an extremely large function which increases the stack size beyond the MMU-protected region, it could subsequently write into unprotected memory and cause undefined behavior without triggering the MMU.

Is my reasoning flawed? Is there a fool-proof way for programming languages to prevent undefined behavior upon stack overflow?

Answer 1

If you have an MMU, you can get well-defined safe behaviour: stack overflow causes an invalid page fault (Segmentation Fault on POSIX). This takes some help from the OS, or manually mapping a read-only page below the stack growth limit. Just make sure you touch each page of stack space as you grow the stack. (Or one probe per 64kiB if you reserve more guard space). You can catch SIGSEGV if you want in a POSIX OS. Other OSes may have different mechanisms.

---

GCC -fstack-check does this fairly cheaply, in combination with the OS having a "guard region" of unmapped pages below the stack mapping. (Or more specifically, below the max growth limit for the stack, so the stack can still grow, but not past that guard region.)

A 1MiB guard region (current Linux default) is normally enough that you don't even need stack probes to prevent stack clash bugs where the stack overlaps with a dynamic allocation below the stack. But a buggy / vulnerable program that uses an unchecked user-input as a size for an alloca or C99 VLA could skip all the way over the guard region.

And Windows always requires "stack probes" (touching memory in every 4kiB page for large or variable-size stack growth, just like gcc -fstack-protector does). Windows requires this to even trigger stack growth at all; it won't grow your stack if you touch multiple pages below the last used stack page.

Linux process stack overrun by local variables (stack guarding) has more details.

Stack probes are an essentially foolproof way to make sure your program segfaults by touching an unmapped page (which won't trigger stack growth) before it does anything dangerous. This can work on any OS and any ISA with an MMU.

The total runtime cost is just a loop on function entry (and on every alloca or scope that includes VLAs) that touches memory with a 4kiB stride until it covers the distance of stack growth. If that size is known at compile time, it can be fully unrolled / peeled to just one or a couple instructions.

Or in most functions that only have a few locals not including any huge or variable size array, no overhead at all. Making another function call involves writing to stack memory to save a return address, either as part of x86 call, or on function entry for RISC ISAs that pass a return address in a link register. So even a whole chain of functions that allocate small to medium arrays and don't touch them can't sneak the stack pointer past the guard page. Saving/restoring the return address to/from the stack is effectively a probe.

Answer 2

A programming language could fairly easily be made to support recursion while providing static guarantees about stack overflow, provided that any cycle on the call graph was guarded by an "if (__STACK_SAFE)" check, and would only make recursive function calls on the "true" branch. Except when invoking external functions outside the implementation's control, there would be no need for the programmer to specify stack usage.

A C implementation could accomplish this with relatively minimal modifications:

1. For any function that contains a __STACK_SAFE check, build two versions--one where that check returns true, one where it returns false (perhaps use a modified name for the version where the check returns true). For both versions, produce a list of all function calls and the difference between the stack pointer when the call is made, versus the value on function entry. Additionally for both versions report the stack usage of the function itself.

2. At the start of the "normally-named" version, compare the stack pointer to a symbol formed form the function name, and branch to the alternative version if the available stack space exceeds the value of that symbol. This branch should not be included on the list of function calls and stack requirements.

3. Include in the list of function calls, for any function whose address is taken, a pseudo-call from a pseudo-function with a name based on the function pointer type and the function whose address was taken. Any call to a function pointer should be listed as a call to that pseudo-function. Any type conversion between involving function pointers should be listed as a call from the original type to the new type.

4. Feed the reports from the compilation of all functions into a program that would build a call graph and determine the maximum stack requirement for each function, and generate a file that would define a symbol for each function giving its stack requirements.

5. Build that output file and link it in with the main program.

Code which uses recursion would need to include a stack safety check on every recursive cycle, but would be able to fully specify the behavior that should occur when a stack overflow occurs.

For example, a recursive-descent parser could have each function start with a stack safety check and, in case of stack insufficiency, set and error flag and return. Some other forms of recursive algorithm may be able to set an "action incomplete" flag and switch to a fallback strategy which would be slower than a recursive one, but would nonetheless work. For example, a QuickSort implementation that recursively Quicksort the halves of partition [yes I know Quicksort is generally best implemented non-recursively] could simply use insertion sort to process each half.

There are various ways by which a more sophisticated implementation could minimize the number of __STACK_SAFE checks, but even in many programs that make heavy use of recursion, the majority of functions wouldn't need such checks to ensure that there was at least one check on every call graph cycle.