Dreamscape Jan 3, 2023

Out of bounds

Take a look at the code below. It’s pretty basic, so even if you don’t know C, you should be able to understand it.

int main()
{
    int i;
    int array[4];
    for(i = 0; i <= 4; i++)
    {
        array[i] = 0;
        printf("LOL ");
    }
    return 0;
}

Did you spot the bug? How many times do you think it will print “LOL”? 4? 5? Could be. It also could be infinite number of times like it happened on my system:

So how the hell did that happen? Enter the workings of the stack.

The Stack segment

Typically, programs have 4 different memory segments: text, data, stack and heap. Text segment is read only and contains the code, data segment contains global and static local variables, heap contains dynamically allocated variables (for example the ones allocated with malloc). The stack segment is the one we’re interested in here. The stack in and of itself is a data structure where data is added and removed in last in first out (LIFO) manner. But what we are referring to here is the so called “execution stack” which is basically a stack data structure for storing information about the active functions of a program. Each time a function is called, the return address is being pushed to the stack, and when the function finishes execution, the control is being transferred to the return address (which is now being popped off the stack). The actual details of the stack vary upon the compilers, operating systems and instruction set architectures, but what is important here is that typically memory for local variables of the function are also allocated on the stack as this is a convenient way to provide storage space for data local to the function.

So what happened?

So as main is a function and ‘array’ and ‘i’ are its local variables they are allocated on the stack. So we need space for 5 integers on the stack, 4 for array and 1 for i. The ‘array’ has 4 integers, but in the for loop we iterate 5 times because of <=. In the 4th iteration of the loop we are accessing array out of bounds. As per C standard, this is undefined behavior. It just so happened that on my system, this resulted in accessing the memory segment that resides just beyond the last element of the array (not uncommon behavior for out of bounds access). And it just so happened that in that memory location, the variable ‘i’ was stored. So in the final iteration I inadvertently set i to 0 which of course resulted in an infinite loop. It’s worth mentioning that since this is the result of undefined behavior, it’s not guaranteed to be reproducible on every system/compiler. This happened to me on Debian I think, a few years ago, I tried to reproduce it on Windows 10 just now, and the program just printed LOL 5 times and exited properly. Nevertheless, this show what kinds of weird behavior is possible when accessing array out of bounds.