Lecture
A stack frame (or frame) is a mechanism for passing arguments and allocating temporary memory (in procedures of high-level programming languages) using the system stack; it is also a visual representation of a subroutine's data on the call stack.
A typical case of a high-level language using the stack, shown for a procedure call with arguments "A, B, C" (using the cdecl calling convention), compared with assembly language
The system stack is usually used to save return addresses when calling subroutines, as well as to save and restore processor register values.
When a procedure is called, the arguments are pushed onto the stack, and only then is the subroutine called. As a result, the procedure receives a stack with the return address on top and, beneath it, the arguments with which it was called.
When returning from the procedure (or after the return, see below), the arguments must be removed from the stack.
If the stack pointer is moved "higher" (toward lower addresses), part of the memory on the stack becomes unused (including during a call to a third procedure) and can be used by the procedure as it sees fit until it returns to the procedure that called it. This is how high-level languages implement variables that exist only inside a procedure (the C language calls them "automatic").
Before returning, the procedure must restore the stack pointer to its original position (that is, to the return address).
Different compilers of high-level languages approach the organization of the stack frame differently, depending on the features of the hardware platform and the standards of the particular language. The main differences concern the order in which arguments are pushed onto the stack and how they are removed from it on return.
The stack frame is a convenient technique for allocating temporary memory to pass an arbitrary number of arguments or for internal use. However, it has a number of drawbacks.
Passing data through memory unnecessarily slows down program execution (compared with assembly programs, in which most arguments and temporary data are placed in processor registers).
To reduce accesses to local variables, the program is optimized at compile time to use registers instead of variables in memory, or to hold their intermediate values.
Some languages use calling conventions that support passing integer arguments through registers.
The stack frame interleaves application data with critical data: pointers, register values, and return addresses. This, combined with the architectural features of some processors (namely, the direction in which the stack grows), makes malicious overwriting of critical data through a buffer overflow very easy to achieve (of course, the program must first contain a bug that permits the overflow).
Hardware platforms whose machine stack grows in this "unfortunate" direction, from the buffer overflow point of view, include x86.
A stack buffer overflow attack is usually carried out as follows:
In software, a stack overflow occurs when more information is stored on the call stack than it can hold. The stack capacity is usually set when the program or thread starts. When the stack pointer goes out of bounds, the program terminates abnormally.
This error occurs for three reasons.
The simplest example of infinite recursion in C:
int foo() { return foo(); }
The function will call itself, consuming stack space until the stack overflows and a segmentation fault occurs.
This is a distilled example, and in real code infinite recursion can arise for two reasons:
A common cause of infinite recursion is that, under some extreme, untested circumstances, the termination condition of the recursion never triggers at all.
int factorial (int n) { if (n == 0) return 1; return n * factorial(n - 1); }
The program will go into deep recursion (4 billion calls) for a negative n.
Many languages perform an optimization called "tail recursion". Recursion at the end of a function is turned into a loop and does not consume stack. If such an optimization kicks in, an endless loop occurs instead of a stack overflow.
A programmer can write recursion unintentionally, for example when several overloaded functions perform the same functionality and one calls another.
int Obj::getData(int index, bool& isChangeable) { isChangeable = true; return getData(index); } int Obj::getData(int index) { bool noMatter; return getData(index, noMatter); }
In GUI frameworks such as Qt and VCL, recursion can occur if, for example, in a field-change handler the programmer modifies that very same field.
A singly linked list can be destroyed with the following code:
void destroyList(struct Item* it) { if (it == NULL) return; destroyList(it->next); free(it); }
If the list is not corrupted, this algorithm will theoretically finish in finite time, but it will require O(n) stack. Of course, with a long list the program will fail. Possible solutions:
The third major cause of stack overflow is allocating a huge amount of memory at once through large local variables. Many authors recommend allocating memory larger than a few kilobytes on the heap rather than on the stack.
Example in C:
int foo() { double x[1000000]; }
The array occupies 8 megabytes of memory; if the stack does not have that much memory, an overflow will occur.
Anything that reduces the effective size of the stack increases the risk of overflow. Threads usually get less stack than the main program, so a program may work in single-threaded mode and fail in multithreaded mode. Subroutines running in kernel mode often use someone else's stack, so when programming in kernel mode people try to avoid recursion and large local variables.
Comments