Activation Records on the Stack

Part of 22C:169, Computer Security Notes
by Douglas W. Jones
THE UNIVERSITY OF IOWA Department of Computer Science

Storage Allocation in C/C++

Consider the following variant Hello World program in C:

#include <stdio.h>

char s[] = "Hello World!\n";

void output(char s[])
{
    int i;
    for (i = 0; s[i] != '\0'; i++) {
        putchar(s[i]);
    }
}

int main()
{
    output(s);
}

This program consists of a main program that calls a subroutine named output. The term subroutine says nothing about the nature of the routine. In this case, it is a parameterized procedure, which is to say, it is not a function in the mathematical sense, because it has no return value. C insists on considering such procedures to be functions returning an object of type void. We don't call it a method, because it is not associated with any objects or classes.

The program declares one global variable, s, a dimensionless array of characters initialized with a string constant. In C and C++, global variables are allocated statically, which is to say, each such variable is assigned a memory address that remains constant throughout the life of a program.

The program also contains, in the procedure output, a parameter named s. Global variables are accessible throughout the program, except where a local declaration reuses the same name. In this example, the parameter s prevents direct use of the global variable s from within the body of the output subroutine.

In C and C++, the local variables and parameters of a block of code (a term that includes subroutines) are allocated on entry to the block and deallocated on exit. Parameters are initialized by the caller, while local variables must be initialized within the block itself.

In this exxample, the parameter s is allocated as part of the call to the output subroutine, and it is deallocated when the subroutine returns. Each time the subroutine is called, the parameter s is allocated over again, not necessarily in the same location it was allocated on any former call.

In most programming languages, including C, C++ and Java, local variables are allocated on a push-down stack. For multithreaded languages, one such stack is commonly allocated to each thread.

The different local variables of a subroutine aren't pushed separately, they are gathered together as a single record. To use C and C++ terminology, this record might be called a structure. In C++ and Java terminology, it might be called a methodless object, or even an object where the only method was the block itself, serving as initializer and finalizer all at once.

This block is called an activation record or stack frame. Thee former term applies even if a stack is not used, while the latter term emphasizes the pushing and popping of these objects on the stack.

In addition to the parameters passed to a subroutine and its local variables, the activation record typicaly also contains at least one other field, the return address for the subroutine -- that is, the address to which the subroutine will transfer control when it returns.

Memory Addresses of Variables and Activation Records

C and C++ allow a program to examine the memory address of a variable directly. This is commonly used in parameter passing. Consider the following C/C++ declarations:

int i;
int * p = &i;
*p = 5;

In this little example, the variable p is a pointer to an integer, and it is initialized with the address of the variable i. Until the next assignment to p, the variable p is a pointer to the variable i. Therefore, the assignment *p=5 assigns the value 5 to the variable i. Note that it does nothing to the value of p. The expression *p refers to the thing p points to, which is quite distinct from p, the pointer variable or &p, the address of the pointer variable.

Introductory C programmers see pointers in only one context, parameter passing:

#include <stdio.h>

char hello[] = "Hello World!\n";

void output(char *s)
{
    for (; *s != '\0'; s++) {
        putchar(*s);
    }
}

int main()
{
    output(&(s[0]));
}

In this program, the main program passes the address of the first element of the array of characters s instead of passing the array itself, and the subroutine output takes a pointer to a character as a parameter instead of an array.

NOTICE OF FIB: One of the more interesting design errors in the C programming language is that the type constructors *s and s[] create identically the same type. As a result, passing an array in C is identically the same thing as passing a pointer to an array, and the expressions s and &s[0] mean exactly the same thing. Another consequence of this is that an array, in C and C++ is not, strictly speaking, an object in its own right. This makes arrays quite distinct from other entities that programmers can declare, and is itself the source of significant programming errors. Of course, advocates of C and C++ consider this a feature, not a fault.

We can easily write a procedure in C that prints out the address of its first local variable. Consider this function:

void print_address()
{
        void * p;
        p = (void *)&p;
        printf("%x;\n", (long int)p);
}

This routine prints the address of the local variable p as a long integer, in hexidecimal. In c, variables of type void* are naked pointers, in the sense that they are an address for which the compiler is being explicitly told to forget what it is that they are the address of. The type void indicates an object with zero bytes in its representation; it is illegal to try to instantiate such an object, for example, by declaring a variable of type void, but it is perfectly legal to use pointers to such objects. In this case, p is a void pointer that points to itself.

Modifying the Hello World program given above so that both the main and output routines call print_address is an interesting experiment because it shows which way the stack grows. Stack implementations in which pushing increments the stack pointer work just as well as stack implementations in which pushing decrements the stack pointer. In this case, running this routine on different computers can produce different results. Different CPUs, over the years, have had different natural directions of stack growth.

For what follows, it's more useful to get the address than to print it out, so we invent the following routine:

void * my_address()
{
        void * p;
        p = (void *)&p;
        return p;
}

This routine returns the address of the local variable p instead of printing it.

Which way does the stack grow?

If we want to find things in the activation record, it helps to know which way is up on the stack. That is, do activation records get pushed by incrementing the stack pointer, or do they get pushed by decrementing the stack pointer. We can explore this by sampling some return values from the my_address routine given above.

void * stack_padding()
{
        void * r;
        r = my_address();
        putchar('|');
        return r;
}

int push_direction()
{
        void * low;
        void * high;
        int up;
        low = my_address();
        high = stack_padding();
        if (((long int)high) > ((long int)low)) {
                up = 1;
        } else {
                up = -1;
        }
        return up;
}

Here, the void pointers high and low point to addresses in two different activation records of my_address. The first, low was called directly. The second, high was called through an intermediate routine called stack_padding that served only to push an extra activation record on the stack. Stack padding does some work in order to guarantee that an optimizing compiler will actually generate code for it -- a good compiler might otherwise notice that it does nothing and replace all calls to it with calls to the routine it calls.

Where is the Return Address in the Activation Record?

Now that we know which way the stack grows, we can start with the address of a local variable in the current activation record and march down the stack from that variable looking for the return address. The easiest way to find the return address is to try to destroy it, causing the program to cease behaving sensibly when the return address is finally damaged. Consider the following program:

/* abuse of a global variables as a parameters to clobber */
int limit;    /* the number of bytes to clobber */
int upward;   /* the direction that is up on the stack */
void clobber()
{
        void * pp;
        pp = (void *)(&pp); 
        {
                int i;
        	void * p = pp; 
                for (i = 1; i <= limit; i++) {
                        *(char *)p = '\xaa';
                        p = (void *)(((long int)p) - upward);
                }
        }
}

int main()
{
        limit = 0;
        upward = push_direction();
        for (;;) {
                printf("%d\n", limit);
                clobber();
                limit = limit + 1;
        }
}

The main program calls clobber repeatedly, each time requesting that clobber destroy more and more of the stack. It communicates with clobber through the global variable limit instead of using a parameter, since clobber is highly likely to damage its parameters in the process of clobbering the stack.

The clobber routine overwrites limit bytes of the stack with the character AA16. This value is half one bits and half zero bits, in order to defend against the extreme case that all ones or all zeros will do no real damage.

The local variables in clobber that are used to control the loop clobbering the stack are declared in local block, after the first local variable that marks the start of the stack region to be clobbered. Declaring them this way is an attempt to force the compiler to allocate them after the region that is to be clobbered.

Good References

Good documentation on activation records is found in

The Wikipedia entry for Call stack

The Wikipedia entry for Local variable