Call stack memory architecture

Question

Following my question yesterday, I tried to learn a bit more about the architecture of call stacks. Online and SO searches have not yielded the answer I'm looking for, which could be because I don't know precisely which keywords to use. Anyway, I'm sure someone here can help me...

First, lets start with an excerpt from Wikipedia's entry for stack buffer overflow:

In software, a stack buffer overflow occurs when a program writes to a memory address on the program's call stack outside of the intended data structure; usually a fixed length buffer.

A colleague told me he remembered learning that, on Linux, the stack is at the very end of a process' virtual memory and grows backwards as needed -- hence it would not be a 'fixed length buffer'. However I have not been able to confirm that. So my questions are:

1. On Windows and Linux is the call stack always a fixed size buffer? If not, how does it grow? How does it manage sharing the virtual memory with the heap?
2. Does the architecture of the stack depends on the compiled language used? On the OS? On the hardware?
3. Is the size of the stack determined at compile-time or can it be changed a posteriori?
4. How and where are individual thread's call stacks allocated?

Answer 1

Stack Buffer Overflow

A stack buffer overflow is when a program accidentally or maliciously writes outside the extents of a particular data item on the stack, such as a c-string. This has the effect of modifying the values of nearby control or data structures on the stack (not the heap), which can cause undesireable program behaviour such as crashes, bugs or changing control flow.

This does not generally refer to writing outside the extent of the stack itself, which is often protected by guard pages to prevent accidental over- or under-run.

| start of stack |
| data           |
| parameters     |
| return address |
| data           |
| parameters     |
| return address |
| parameters     |
| return address | <- might overflow into this region or above
| string data    | <- writes to this region ... (look up)
 stack head
  |
  V direction of growth for pushes
 ...
| end of stack   |
| guard page     | <- writes to this region cause a segfault
 ...
| heap           |

The Call Stack on Linux

The call stack is fixed size, the actual stack itself grows and shrinks as requires within this limit.

The heap and the stack do not overlap or share memory - they are typically managed in different areas of the virtual address space.

The size of the process's main stack is determined by the environment that exists at the point the program is run. For c functions to set this, see man 3 ulimit and to view/set it from bash, see, ulimit -s for details.

> ulimit -s
8192

If you create your own threads you can assume responsibility for creating their stacks (see man pthread_attr), you can either use the system recommended size or set your own.

Answer 2

For Windows:

1. For a user mode app, by default, the memory for the stack is initially reserved at 1 MB. Reserved means that the address range cannot be used for any other purpose, but the memory isn't actually allocated. This allows the stack to be contiguous in memory, but not require all of it (even if most will be unused) to be allocated by default. At the end of actual committed stack there is a guard page - whenever this is accessed Windows will allocate more memory to the stack. If you attempt to use space beyond what was reserved for the stack, you get a stack overflow exception. The MSDN page for VirtualAlloc goes into a bit more detail on reserve versus commit.

2. x86 puts some strong requirements on the stack (must grow downward for example). Other architectures are more flexible. Nearly all x86-based OS's use the stack similarly. It is possible to go with a different stack architecture. You couldn't use any of the x86's stack support, you'd have to manually do it yourself, but you'd have to convert to a traditional stack when you call into any OS API.

3. The information is stored in the .exe. You can adjust it with a linker flag. Alternatively, the CreateThread API allows you to change the stack size.

4. Thread's stacks are created at thread creation time, either using the defaults in the .exe or from what is specified in the call to CreateThread.

A stack buffer overflow happens when you overrun a fixed length buffer stored on the stack and overwrite other control data that is on the stack, like the return address.

For instance, let's suppose you call function, and it has a local buffer of size 16 bytes. The call stack may look like this (other details left out for clarity:

0x1000 - Return address
0x990 - Buffer

If your code has a bug and overruns the buffer at 0x990, you will overwrite the return address. If an attacker can cause the buffer overflow, they could put some code into the buffer, and overwrite the return address to point back to the injected code. When your function returns, it jumps to the attacker's code.