A For Loop Without a For Loop

Let’s build on the infinite loop we created in the post A Simple Infinite Loop, and turn it into a for loop. We will use it to loop over the digits 0 through 9. The program looks like this:

#include <stdlib.h>
#include <stdio.h>
 
void for_loop();
 
int main ()
{
    int min = 0;
    int max = 10;
 
    for_loop();
}
 
void for_loop ()
{
    int foo[1];
 
    printf("%d\n", foo[8]);
 
    (++foo[8] < foo[7]) ? (foo[3] -= 5) : ((void) 0);
}

Believe it or not, it does actually work:

The fact that it works may be upsetting. It may evoke feelings of confusion, anger, or even disgust. This is normal. Let’s try to process these feelings together.

Again, the GCC version and OS so you can replicate this at home:

Return Address Review

In the post A Simple Infinite Loop, we looked at how to manipulate the return address of a function so that it returns to its own function call, producing an infinite loop. Here, we are using the same mechanic, but we’re extending it by a conditional. Let’s take a closer look at our for_loop() function:

void for_loop ()
{
    int foo[1];
 
    printf("%d\n", foo[8]);
 
    (++foo[8] < foo[7]) ? (foo[3] -= 5) : ((void) 0);
}

The highlighted line contains our familiar construct for overwriting (part of) the return address: foo[3] -= 5. That line is written using the ternary operator. It can also be written as an if/else statement:

if (++foo[8] < foo[7]) {
    foo[3] -= 5;
}
else {
    (void)0;
}

We can simplify it further. The else clause is not actually necessary, since (void)0 evaluates to a no-op and gets optimized out by the compiler. We can also make the condition inside the if clause a bit clearer. Let’s rewrite that bit of code to look like this:

++foo[8];
if (foo[8] < foo[7]) {
    foo[3] -= 5;
}

What we’re doing then, is incrementing foo[8] by 1, checking whether foo[8] is smaller than foo[7], and, if so, we decrement the return address.

By decrementing the return address, we cause the function for_loop() to be called again, hence creating a loop.

Now what about foo[8] and foo[7]? What are they?

Let’s review our program:

int main ()
{
    int min = 0;
    int max = 10;
 
    for_loop();
}
 
void for_loop ()
{
    int foo[1];
    // ...
}

Since the variables min and max are local to the function main(), their values are stored on the stack. When for_loop() is called, a stack frame simply gets tacked onto the end of the stack, with some room for foo. Similarly to how we can access the return address by using the right index for foo, we can also access the values for min and max using the same technique.

The way I did it for this program is by first selecting some arbitrary indexes for foo and then loading the compiled program into GDB. Here, we are going to use the finished program but it doesn’t really matter. First, let’s open our program in GDB, set up a breakpoint, and run the program:

thebel:/home/thebel/programming/chack/loop$ gdb
GNU gdb (Debian 8.3.1-1) 8.3.1
Copyright (C) 2019 Free Software Foundation, Inc.                                                                                                                     
License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.
Type "show copying" and "show warranty" for details.
This GDB was configured as "x86_64-linux-gnu".
Type "show configuration" for configuration details.
For bug reporting instructions, please see:
<http://www.gnu.org/software/gdb/bugs/>.
Find the GDB manual and other documentation resources online at:
    <http://www.gnu.org/software/gdb/documentation/>.

For help, type "help".
Type "apropos word" to search for commands related to "word".
(gdb) file for01
Reading symbols from for01...
(gdb) break for01.c:1
Breakpoint 1 at 0x113d: file for01.c, line 8.
(gdb) run
Starting program: /home/thebel/programming/chack/loop/for01 

Breakpoint 1, main () at for01.c:8
8           int min = 0;
(gdb) 

Next, we need to find out the addresses at which variables min and max are located:

(gdb) run
Starting program: /home/thebel/programming/chack/loop/for01 

Breakpoint 1, main () at for01.c:8
8           int min = 0;
(gdb) p/x &min
$1 = 0x7fffffffe13c
(gdb) step
9           int max = 10;
(gdb) p/x &max
$2 = 0x7fffffffe138
(gdb) 

Now, we need to step into the function for_loop() so we can find out the address at which foo[0] is located:

(gdb) step
11          for_loop();
(gdb) step
for_loop () at for01.c:18
18          printf("%d\n", foo[8]);
(gdb) p/x &foo[0]
$3 = 0x7fffffffe11c
(gdb) 

And finally, we’re going to calculate the number of array elements between foo[0], and max and min, respectively:

gdb) p/d (0x7fffffffe138 - (long)&foo[0]) / sizeof(int)
$4 = 7
(gdb) p/d (0x7fffffffe13c - (long)&foo[0]) / sizeof(int)
$5 = 8

Ergo, foo[8] == 0 and foo[7] == 10, correct? Yes, indeed:

(gdb) p/d foo[8]
$6 = 0
(gdb) p/d foo[7]
$7 = 10
(gdb) 

So, we can rewrite for_loop() as:

void for_loop ()
{
    int foo[1];
 
    printf("%d\n", foo[8]);
 
    ++foo[8];
    if (foo[8] < foo[7]) {
        foo[3] -= 5;
    }
}

Every time you see foo[8], think min, and every time you see foo[7], think max. Essentially, we are accessing data from main()‘s stack frame inside for_loop(). Neat, huh?

We can finally turn the last bit of for_loop() into a ternary expression for extra elegance/obfuscation.

And there you have it: a for loop without a for loop. I hope we’ve been able to turn any feelings of confusion or disgust into curiosity about how the call stack works.