Stack Overwriting Function

By Susam Pal on 28 Jul 2010

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 analyze 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 highlighted in orange 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 highlighted in olive 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 analyze 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 highlighted in olive shows where the variable a is allocated and the instructions at offsets 25, 2A, and 2F highlighted in orange 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 always arrive at the solution for any 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.