The stack is frequently used for convenient temporary storage, because allocated memory is automatically freed when the function returns. Also, the kernel automatically grows the stack if the process accesses memory beyond the current allocation. This can fail due to lack of memory or collision with other allocated areas of the address space. However, most methods of stack allocation have no way to report failure. Instead of returning an error code, a failure to grow the stack results in the process being killed. If user input is able to influence the amount of stack memory allocated then an attacker could use this in a denial-of-service attack.

Dynamic Arrays

C99 includes support for variable length arrays. If the value used for the length of the array is influenced by user input, an attacker could cause the program to use a large number of stack pages, possibly resulting in the process being killed due to lack of memory, or simply cause the stack pointer to point to a different region of memory. The latter could result in a page fault and the process being killed or a write to an arbitrary memory location. An easy solution is to use the malloc family of functions to allocate and free memory, and handle any errors that malloc returns.

Non-Compliant Code Example

Compliant Solution

Recursion

Excessive recursion also requires the kernel to grow the stack, and can thus lead to the process being killed due to lack of memory. Depending on the algorithm, this can be much more difficult to fix than the use of dynamic arrays. However, the use of recursion in most C programs is limited in part because non-recursive solutions are often faster.

Non-Compliant Code Example

This is a naive implementation of the Fibonacci function using exponential recursion (as well as exponential time). When tested on a Linux system, fib1(100) crashes with a segmentation fault.

int fib1(unsigned int n)
{
  if (n == 0)
    return 0;
  else if (n == 1 || n == 2)
    return 1;
  else
    return fib1(n-1) + fib1(n-2);
}

Compliant Solution

This is a much more efficient solution, using constant space and linear time. Tested on a Linux system, fib2(100) is calculated almost instantly and with almost no chance of crashing due to a failed stack allocation.

int fib2(unsigned int n)
{
  if (n == 0)
    return 0;
  else if (n == 1 || n == 2)
    return 1;

  unsigned int prev = 1;
  unsigned int cur = 1;

  int i;
  for (i = 3; i <= n; i++)
  {
    int tmp = cur;
    cur = cur + prev;
    prev = tmp;
  }

  return cur;
}

Risk Assessment

Stack overflow caused by excessive stack allocations or recursion could lead to abnormal termination and denial-of-service attacks.

References

[Sprundel 06] "Stack Overflow"