Is a stack overflow detected by hardware or software?

Problem Detail: 

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?

Asked By : gilianzz

Answered By : Gilles

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.}

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/39677