Stack Overflow in memory

Stack Overflow in Computing Systems

1. What is Stack Overflow?

• Stack Overflow occurs when a program uses more stack memory than is allocated for it.
• The stack is a region of memory for storing local variables, function parameters, return addresses, and bookkeeping information.
• On most CPUs, the stack grows downward (toward lower memory addresses).

2. Why Does Stack Overflow Happen?

• Deep or infinite recursion.
• Large local variables.
• Excessively deep call chains.
• Buffer overflows: writing more data to a stack variable than its declared size.

3. Hardware and Software Perspectives

3.1 Hardware

• The stack pointer (SP) starts at a high address and is decremented (moves to lower addresses) as stack frames are added.
• Stack is bounded at the bottom by a guard page or limit; exceeding this triggers an exception or segfault.

3.2 Software

• Each process/thread has its own downward-growing stack.
• Stack overflows corrupt memory, causing a crash, undefined behavior, or vulnerabilities.

4. Stack Frame and Call Graph Example (Downward-Growing Stack)

4.1 Before and After Function Call

Before call (just main):
|--------------------| 0x7FFFFFFF  <-- Stack Start (high address)
|                    |
|  Free Stack        |
|                    |
|--------------------|
|   main() frame     | <-- SP (after main started)
|--------------------| 0x7FFFE000  <-- Stack Base (low address)

After calling foo() from main():

|--------------------| 0x7FFFFFFF
|                    |
|  Free Stack        |
|--------------------|
|   foo() frame      | <-- SP (top of stack now lower)
|--------------------|
|   main() frame     |
|--------------------| 0x7FFFE000

Each function call pushes a new frame below the previous frame, moving SP downward.

4.2 Deep Recursion Example

void recurse() {
    int dummy[1000]; // 4000 bytes
    recurse();       // Each call pushes more stack
}
int main() {
    recurse();
    return 0;
}

4.3 Stack Growth Table

When SP crosses the stack limit (e.g., 0x7FFFE000), overflow occurs.

4.4 ASCII Stack Diagram (Downward-Growing)

High Address (Stack Top)
|--------------------| 0x7FFFFFFF
|   Free/unused      |
|--------------------|
|   recurse (3rd)    |
|--------------------|
|   recurse (2nd)    |
|--------------------|
|   recurse (1st)    |
|--------------------|
|   main             |
|--------------------| 0x7FFFE000
Low Address (Stack Base/Limit)

5. Large Local Variable Stack Overflow

void foo() {
    char bigbuf[1000000]; // ~1MB on stack!
    bigbuf[0] = 'X';
}
int main() {
    foo();
}

• Here, the SP moves down by 1MB for `foo()`. On most systems, this will hit the guard page immediately—**instant overflow**.

6. Buffer Overflow (Security Risk)

void vuln() {
    char buf[16];
    gets(buf);  // Danger! Overwrites stack if >16 chars entered
}
int main() {
    vuln();
}

Downward-Growing Stack Layout

High Address
|--------------------|
|   Return Address   | <-- Overwritten by overflow!
|--------------------|
|   Saved FP         |
|--------------------|
|   buf[15]          |
|   ...              |
|   buf[0]           |
|--------------------|
Low Address

7. How Stack Overflow Is Detected

• Segmentation fault: SP moves below allowed region, guard page triggers fault.
• Canaries: compiler inserts guard values before return address.
• Static analysis: warns about recursion/large stack vars.

8. Preventing Stack Overflow

• Use heap (malloc) for large data, not stack.
• Avoid deep recursion.
• Set appropriate stack sizes, enable compiler/RTOS protections.

9. Example: Safe Recursion

void safe_recurse(int n) {
    if (n == 0) return;
    safe_recurse(n-1);
}
int main() {
    safe_recurse(10);
}

10. Debugging Stack Overflows

• Use gdb, Valgrind, or AddressSanitizer to trace.
• Monitor stack pointer in embedded via RTOS APIs.