25
$\begingroup$

Is it the task of the software (operating system) to detect stack overflows or is a stack overflow detected in hardware, causing an exception in the CPU?

$\endgroup$
  • $\begingroup$ I would say hardware, through MMU faults on most CPUs. x86 in 32bits mode had segmentation in addition to paging, and the "Stack Segment" is associated, like the Code, Data, Ext... segments with both a base address and a size. Any access outside that range would trigger a fault. $\endgroup$ – TEMLIB Feb 22 '15 at 19:47
25
$\begingroup$

It can be software, or hardware, or both, or none.

There are two kinds of overflows: overflow when growing the stack (when entering a function), and overflow when accessing an array on the stack. Overflows when growing the stack can be detected by making a bounds check on function entry, to verify that there is enough room (and either signal an error or grow the stack if there isn't). Overflows when accessing an array on the stack are only an issue in low-level languages that don't verify array bounds; the solution there is to verify array bounds.

These software approaches have the advantage that they work fully reliably: you can be sure that any stack overflow will be detected. Their downside is that they increase the code size and the execution time. Hardware can help by providing a method to detect most overflows at no cost as long as no overflow occurs. On an architecture with an MMU¹, the runtime environment can arrange to map the stack on a page boundary, with the next page remaining unmapped.

+---------------+---------------+---------------+---------------+
| stack                         | unmapped      | other stuff   |
|    ----> direction of growth  |               |               |
+---------------+---------------+---------------+---------------+
^               ^               ^               ^               ^  page boundaries

That way, if the software attempts to access data beyond the page boundary (whether because the stack pointer has moved beyond the boundary or because the array access is out of bounds and beyond the boundary), it will cause a fault by accessing an unmapped area. This only happens if the overflow is small enough: if the amount of overflow is too large, the program may end up accessing other stuff on the other side of the gap in the address space.

The downsides of the hardware approach are that it isn't fully reliable since an overflow by a large amount may not be detected, and that it doesn't detect array overflows that remain within the addressable space.

To detect array overflows, another software technique is a canary: put a special value at the top of the stack or between frames, and check that the canary value hasn't changed on function return. This is also an imperfect technique since the overflow might avoid the canary altogether or might not be detected because the canary value has been restored by the time it is checked. Nonetheless, it is useful to make it harder to exploit some security vulnerabilities.

The safest and cheapest way to avoid stack overflows is to calculate the amount of stack that the program will need before starting to execute it, by static analysis. However this is not always practical: the amount of stack needed by a program is undecidable in general and depends on the data that's manipulated by the program.

¹ The same principle can also be applied with just an MPU, or with no memory protection if there is a single thread whose stack is at the edge of the existing physical mappings.

$\endgroup$
  • 4
    $\begingroup$ I wouldn't call out-of-bounds array access a stack overflow, even if the array is on the stack. It's just a special case of a buffer overflow. $\endgroup$ – CodesInChaos Feb 22 '15 at 21:54
  • $\begingroup$ Not allocating to the primary stack items that are referenced relative to a non-stack/frame pointer or non-constant offset would avoid traditional stack overflows. Using a separate return address stack (or RA/register spill stack like Itanium) would at least greatly reduce return-oriented programming opportunities. $\endgroup$ – Paul A. Clayton Feb 22 '15 at 22:08
  • $\begingroup$ Out-of-bounds access is more properly called an overrun, not an overflow. $\endgroup$ – Ben Voigt Feb 22 '15 at 23:17
  • 3
    $\begingroup$ @awesomebing1 not every platform detects stack overflows. You might just end up overwriting whatever is after the stack (similar to any other buffer overflow). $\endgroup$ – immibis Feb 23 '15 at 3:33
  • 1
    $\begingroup$ @CodesInChaos, sometimes buffer overflows in stack-allocated buffers are called "stack overflows" (for short). Granted, that terminology can be a bit confusing without context. $\endgroup$ – D.W. Feb 23 '15 at 6:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.