3

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?

Peter Cordes
  • 328,167
  • 45
  • 605
  • 847
Joshua Wise
  • 613
  • 4
  • 15
  • 3
    It suffices to check stack usage at the beginning of each function for the maximal amount of stack the function is going to use. – fuz Mar 30 '20 at 16:37
  • 1
    Fairly recently, stack/heap collision returned to the (computer) news after having been mitigated against with guard pages for a long time, because funtions that allocate large stack buffers could sometimes cause the problem you hint at: https://blog.qualys.com/securitylabs/2017/06/19/the-stack-clash. The current fix is to ensure the function touches every page on the stack at least once when indexing into a stack buffer, which ensures that the MMU will catch a guard page access. – EOF Mar 30 '20 at 18:13
  • no, there is no fool proof way – old_timer Mar 30 '20 at 19:42
  • @fuz: Actually, languages could statically verify stack usage for an entire program if all recursive functions were marked with the maximum number of nested invocations, or if all recursive calls were within `if(__STACK_SAFE)` blocks; the implementation could statically determine how much space would be required for each such "if" to return true. – supercat Mar 30 '20 at 20:31
  • @supercat Sure. It's usually not a good idea to make this check that coarse as you might be able to get away with less stack space in 99% of the possible code paths and can thus lazily allocate more stack than needed. Go does it this way for example. – fuz Mar 30 '20 at 23:04
  • @fuz: It's not necessary that every call to a recursive function be guarded by such a check, but merely that every cycle within the call graph contain such a check. Note that using this style of check makes it possible for code to cleanly handle a lack of stack space, since the check will return false *before* a stack overflow occurs. – supercat Mar 30 '20 at 23:09
  • @fuz: Ever since recursion was invented, however, it seems most programming languages have opted for "hope for the best" semantics rather than offering substantive guarantees. – supercat Mar 30 '20 at 23:10
  • @supercat It really depends on what you want to achieve. If you want a static limit on stack size, do what you say. If you want to have small stacks that can be resized on the fly, do what I say. Both have useful applications. – fuz Mar 30 '20 at 23:21
  • @fuz: No need for a static limit if code uses a `__STACK_SAFE` check as I described. Indeed, things like recursive-descent parsers could safely use whatever amount of stack exists, and report an inability to parse things that would exceed stack space, without having to use a hard-coded limit to nesting depth. – supercat Mar 30 '20 at 23:42
  • @supercat Imagine your program is an embedded application that must not fail. That's generally the kind of application where you want to compute all stack usage statically. – fuz Mar 30 '20 at 23:43
  • @fuz: If such applications have more critical and less critical aspects, something like `__STACK_STAFE` would be able to ensure that the less critical aspects "fall back" nicely by deciding not to do things that would endanger system stability, rather than trying to recover after the fact. – supercat Mar 31 '20 at 04:32

2 Answers2

3

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.

Peter Cordes
  • 328,167
  • 45
  • 605
  • 847
1

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.

supercat
  • 77,689
  • 9
  • 166
  • 211