18

Possible Duplicate:
What is a stack overflow error?

Can any one tell me how and why stack overflow and heap overflow actually occur in programs, and how to overcome stack overflow in programming - how to avoid it?

Community
  • 1
  • 1
Vishwanath Dalvi
  • 35,388
  • 41
  • 123
  • 155

3 Answers3

40

Stack Overflow

void stack_overflow(const char *x)
{
    char y[3];
    strcpy(y, x);
}

Heap Overflow

void heap_overflow(const char *x)
{
    char *y = malloc(strlen(x));
    strcpy(y, x);
}

Analysis

Both functions trample beyond the allocated space.

If you call stack_overflow("abc"), it copies 4 characters (including the null) into space allocated for 3 characters. What happens after that depends on where the damage was done. The variable y is on the stack, so it is stack overflow.

Regardless of how you call heap_overflow(), it asks for one too few bytes from the heap and then writes beyond the end. What's insidious about that is that some of the time - even most of the time - it will seem to work because the heap system allocates more space than you request. However, you might trample on control data, and then all bets are off.

The heap overflow is very small, and hard to detect. The stack overflow can be small (non-existent if the passed string is short enough) or dramatic. You normally get more dramatic effects when you write further beyond the allocated space, but any writing beyond the allocated space leads to undefined behaviour - anything could happen.

You ensure there are no problems by knowing how big the object you are copying is and how much space there is to receive it, and by making sure that you do not copy more material than there is space. Always, every time.

Jonathan Leffler
  • 730,956
  • 141
  • 904
  • 1,278
  • 3
    There are two views on what 'stack overflow' and 'heap overflow' mean. One variant, the one illustrated in this answer, is a buffer overflow, where you write (or read) outside the bounds of a buffer (chunk of memory). Another variant is resource exhaustion, where you try to use more space than is available to you. The stack, in particular, is a finite resource (often just 8 MiB, or even less on some systems), so creating large stack-based variables (e.g. arrays) on the stack can lead into trouble. With virtual memory, it is harder to run out of heap, but leaking memory can do that too. – Jonathan Leffler Jan 25 '15 at 15:09
  • you say that "the heap system allocates more space than you request". Can you give some good reference/article, which explains me more about this ? – Mangu Singh Rajpurohit May 09 '16 at 05:34
  • @user2393267: If you find any example implementation of `malloc()`, you will probably find that it rounds up a request for N bytes to `((N + BLOCK_SIZE - 1) / BLOCK_SIZE) * BLOCK_SIZE` bytes, so that the request is a multiple of an internal block size (often 8 or 16 bytes on 32-bit or 64-bit systems respectively). It is also common to store information about the size of the allocation immediately prior to the requested memory, so that when it is freed, `free()` can tell how big a chunk was originally allocated. So the calculation may well be an extra BLOCK_SIZE bigger than the number above. – Jonathan Leffler May 09 '16 at 05:39
  • @user2393267: An example implementation of `malloc()` is found in K&R 2nd Edition (or 1st Edition, but you shouldn't be using that — though it has an honoured place in my personal library because it was current when I bought it). You can undoubtedly find many others online (Linux GLIBC, BSD, dlmalloc, and many others). – Jonathan Leffler May 09 '16 at 05:41
  • How would the heap overflow happen if we do `malloc(strlen(x))`. shouldn't that allocate space exactly equal the user input? I don't get it – dlock Oct 14 '16 at 14:48
  • @deadlock: `strlen(x)` doesn't include the null byte at the end of the string. If you use `strcpy()` to copy `x` into the allocated memory, you will copy one byte too many with potentially devastating consequences. – Jonathan Leffler Oct 14 '16 at 14:52
  • @JonathanLeffler So we can call it an Off-By-One vulnerability – dlock Oct 14 '16 at 16:09
  • @deadlock: yes, it is also an off-by-one vulnerability. – Jonathan Leffler Oct 14 '16 at 16:39
  • @JonathanLeffler the stack_overflow you mentioned is actually buffer overflow on stack allocated buffer or stack smashing, not stack overflow – e.jahandar Dec 29 '16 at 06:35
  • The line "it will seem to work because the heap system allocates more space than you request" is perfect. That happened to me. – rustyMagnet Aug 31 '17 at 09:44
5

"stack overflow" is different from "stack-based buffer overflow". The former is due to too deep activation records, for example an unstopping recursive call. The latter is a software bug due to insufficient boundary check, which is the most frequently exploited vulnerability.

Infinite
  • 3,198
  • 4
  • 27
  • 36
-5

Stack overflow:

 static void f(void) { f() ; }
 int main() { f() ; }

Heap overflow:

 #include <stdlib.h>
 int main() { while (1) malloc (1000) ; }

Edit Apparently this is not what heap overflow means. See comments below.

TonyK
  • 16,761
  • 4
  • 37
  • 72
  • 4
    Those show stack exhaustion and heap exhaustion, but not stack overflow or heap overflow. – Jonathan Leffler Jan 15 '11 at 17:32
  • 2
    -1 for wrong answer and `memory.h`. The header for `malloc` is `stdlib.h`. – R.. GitHub STOP HELPING ICE Jan 15 '11 at 17:44
  • @Jonathan Leffler: I think I'm right about stack overflow. For what it's worth, Wikipedia (http://en.wikipedia.org/wiki/Stack_overflow) backs me up (and the article describes your notion as 'stack buffer overflow'). But you're right about heap overflow. – TonyK Jan 15 '11 at 20:16
  • If you distinguish between 'stack overflow' and 'stack buffer overflow', then your stack overflow code eventually runs out of stack (which is also 'exhaustion'), but that could be regarded as overflow too. Very often, stack overflow is used as a shorthand for stack buffer overflow, and your example does not illustrate that. So, I'm OK to call your stack overflow an example of one variant of stack overflow. – Jonathan Leffler Oct 14 '16 at 15:26