## Skipping Over a Function Call

Here is a C puzzle that involves some analysis of the machine code generated from it followed by manipulation of the runtime stack. The solution to this puzzle is implementation-dependent. Here is the puzzle:

Consider this C code:

    #include <stdio.h>

    void f()
    {
    }

    int main()
    {
        printf("1\n");
        f();
        printf("2\n");
        printf("3\n");
        return 0;
    }

Define the function `f()` such that the output of the above code is:

    1
    3

Printing `3` in `f()` and exiting is not allowed as a solution.

If you want to think about this problem, this is a good time to pause and think about it. There are spoilers ahead.

The solution essentially involves figuring out what code we can place in the body of `f()` such that it causes the program to skip over the machine code generated for the `printf("2\n")` operation. I'll share two solutions for two different implementations:

1. gcc 4.3.2 on 64-bit Debian 5.0.3 running on 64-bit Intel Core 2 Duo.
2. Microsoft Visual Studio 2005 on 32-bit Windows XP running on 64-bit Intel Core 2 Duo.

## Solution for GCC

Let us first see step by step how I approached this problem for GCC. We add a statement `char a = 7;` to the function `f()`. The code looks like this:

    #include <stdio.h>

    void f()
    {
        char a = 7;
    }

    int main()
    {
        printf("1\n");
        f();
        printf("2\n");
        printf("3\n");
        return 0;
    }

There is nothing special about the number `7` here. We just want to define a variable in `f()` and assign some value to it.

Then we compile the code and analyse the machine code generated for `f()` and `main()` functions.

    $ gcc -c overwrite.c && objdump -d overwrite.o

    overwrite.o:     file format elf64-x86-64

    Disassembly of section .text:

    0000000000000000 <f>:
       0:   55                      push   %rbp
       1:   48 89 e5                mov    %rsp,%rbp
       4:   c6 45 ff 07             movb   $0x7,-0x1(%rbp)
       8:   c9                      leaveq
       9:   c3                      retq

    000000000000000a <main>:
       a:   55                      push   %rbp
       b:   48 89 e5                mov    %rsp,%rbp
       e:   bf 00 00 00 00          mov    $0x0,%edi
      13:   e8 00 00 00 00          callq  18 <main+0xe>
      18:   b8 00 00 00 00          mov    $0x0,%eax
      1d:   e8 00 00 00 00          callq  22 <main+0x18>
      22:   bf 00 00 00 00          mov    $0x0,%edi
      27:   e8 00 00 00 00          callq  2c <main+0x22>
      2c:   bf 00 00 00 00          mov    $0x0,%edi
      31:   e8 00 00 00 00          callq  36 <main+0x2c>
      36:   b8 00 00 00 00          mov    $0x0,%eax
      3b:   c9                      leaveq
      3c:   c3                      retq

When `main()` calls `f()`, the microprocessor saves the return address (where the control must return to after `f()` is executed) in stack. The line at offset `1d` in the listing above for `main()` is the call to `f()`. After `f()` is executed, the instruction at offset `22` is executed. Therefore the return address that is saved on stack is the address at which the instruction at offset `22` would be present at runtime.

The instructions at offsets `22` and `27` are the instructions for the `printf("2\n")` call. These are the instructions we want to skip over. In other words, we want to modify the return address in the stack from the address of the instruction at offset `22` to that of the instruction at offset `2c`. This is equivalent to skipping 10 bytes (0x2c - 0x22 = 10) of machine code or adding 10 to the return address saved in the stack.

Now how do we get hold of the return address saved in the stack when `f()` is being executed? This is where the variable `a` we defined in `f()` helps. The instruction at offset `4` is the instruction generated for assigning `7` to the variable `a`.

From the knowledge of how microprocessor works and from the machine code generated for `f()`, we find that the following sequence of steps are performed during the call to `f()`:

1. The microprocessor saves the return address by pushing the content of RIP (instruction pointer) register into the stack.
2. The function `f()` pushes the content of the RBP (base pointer) register into the stack.
3. The function `f()` copies the content of the RSP (stack pointer) register to the RBP register.
4. The function `f()` stores the byte value `7` at the memory address specified by the content of RBP minus 1. This achieves the assignment of the value `7` to the variable `a`.

After `7` is assigned to the variable `a`, the stack is in the following state:

Address | Content | Size (in bytes)
--- | --- | ---
`&a + 5` | Return address (old RIP) | 8
`&a + 1` | Old base pointer (old RBP) | 8
`&a` | Variable `a` | 1

If we add 9 to the address of the variable `a`, i.e. `&a`, we get the address where the return address is stored. We saw earlier that if we increment this return address by 10 bytes, it solves the problem. Therefore here is the solution code:

    #include <stdio.h>

    void f()
    {
        char a;
        (&a)[9] += 10;
    }

    int main()
    {
        printf("1\n");
        f();
        printf("2\n");
        printf("3\n");
        return 0;
    }

Finally, we compile and run this code and confirm that the solution works fine:

    $ gcc overwrite.c && ./a.out
    1
    3

## Solution for Visual Studio

Now we will see another example solution, this time for Visual Studio 2005.

Like before we define a variable `a` in `f()`. The code now looks like this:

    #include <stdio.h>

    void f()
    {
        char a = 7;
    }

    int main()
    {
        printf("1\n");
        f();
        printf("2\n");
        printf("3\n");
        return 0;
    }

Then we compile the code and analyse the machine code generated from it.

    C:\>cl overwrite.c
    Microsoft (R) 32-bit C/C++ Optimizing Compiler Version 14.00.50727.42
    for 80x86
    Copyright (C) Microsoft Corporation.  All rights reserved.

    overwrite.c
    Microsoft (R) Incremental Linker Version 8.00.50727.42
    Copyright (C) Microsoft Corporation.  All rights reserved.

    /out:overwrite.exe
    overwrite.obj

    C:\>dumpbin /disasm overwrite.obj
    Microsoft (R) COFF/PE Dumper Version 8.00.50727.42
    Copyright (C) Microsoft Corporation.  All rights reserved.

    Dump of file overwrite.obj

    File Type: COFF OBJECT

    _f:
      00000000: 55                 push        ebp
      00000001: 8B EC              mov         ebp,esp
      00000003: 51                 push        ecx
      00000004: C6 45 FF 07        mov         byte ptr [ebp-1],7
      00000008: 8B E5              mov         esp,ebp
      0000000A: 5D                 pop         ebp
      0000000B: C3                 ret
      0000000C: CC                 int         3
      0000000D: CC                 int         3
      0000000E: CC                 int         3
      0000000F: CC                 int         3
    _main:
      00000010: 55                 push        ebp
      00000011: 8B EC              mov         ebp,esp
      00000013: 68 00 00 00 00     push        offset $SG2224
      00000018: E8 00 00 00 00     call        _printf
      0000001D: 83 C4 04           add         esp,4
      00000020: E8 00 00 00 00     call        _f
      00000025: 68 00 00 00 00     push        offset $SG2225
      0000002A: E8 00 00 00 00     call        _printf
      0000002F: 83 C4 04           add         esp,4
      00000032: 68 00 00 00 00     push        offset $SG2226
      00000037: E8 00 00 00 00     call        _printf
      0000003C: 83 C4 04           add         esp,4
      0000003F: 33 C0              xor         eax,eax
      00000041: 5D                 pop         ebp
      00000042: C3                 ret

      Summary

               B .data
              57 .debug$S
              2F .drectve
              43 .text

Just like in the previous `objdump` listing, in this listing too, the instruction at offset `4` shows where the variable `a` is allocated and the instructions at offsets `25`, `2A` and `2F` show the instructions we want to skip, i.e. instead of returning to the instruction at offset `25`, we want the microprocessor to return to the instruction at offset `32`. This involves skipping 13 bytes (0x32 - 0x25 = 13) of machine code.

Unlike the previous `objdump` listing, in this listing we see that the Visual Studio I am using is a 32-bit on, so it generates machine code to use 32-bit registers like EBP, ESP, etc. Thus the stack looks like this after `7` is assigned to the variable `a`:

Address | Content | Size (in bytes)
--- | --- | ---
`&a + 5` | Return address (old EIP) | 4
`&a + 1` | Old base pointer (old EBP) | 4
`&a` | Variable `a` | 1

If we add 5 to the address of the variable `a`, i.e. `&a`, we get the address where the return address is stored. Here is the solution code:

    #include <stdio.h>

    void f()
    {
        char a;
        (&a)[5] += 13;
    }

    int main()
    {
        printf("1\n");
        f();
        printf("2\n");
        printf("3\n");
        return 0;
    }

Finally, we compile and run this code and confirm that the solution works fine:

    C:\>cl /w overwrite.c
    Microsoft (R) 32-bit C/C++ Optimizing Compiler Version 14.00.50727.42
    for 80x86
    Copyright (C) Microsoft Corporation.  All rights reserved.

    overwrite.c
    Microsoft (R) Incremental Linker Version 8.00.50727.42
    Copyright (C) Microsoft Corporation.  All rights reserved.

    /out:overwrite.exe
    overwrite.obj

    C:\>overwrite.exe
    1
    3

## Conclusion

The machine code that the compiler generates for a given C code is highly dependent on the implementation of the compiler. In the two examples above, we have two different solutions for two different compilers.

Even with the same brand of compiler, the way it generates machine code for a given code may change from one version of the compiler to another. Therefore, it is very likely that the above solution would not work on another system (such as your system) even if you use the same compiler that I am using in the examples above.

However, we can arrive at the solution for an implementation of the compiler by determining what number to add to `&a` to get the address where the return address is saved on stack and what number to add to this return address to make it point to the instruction we want to skip to after `f()` returns.