x86 Disassembly/Branches
From Wikibooks, the open-content textbooks collection
Contents |
[edit] Branching
Computer science professors tell their students to avoid jumps and goto instructions, to avoid the proverbial "spaghetti code." Unfortunately, assembly only has jump instructions to control program flow. This chapter will explore the subject that many people avoid like the plague, and will attempt to show how the spaghetti of assembly can be translated into the more familiar control structures of high-level language. Specifically, this chapter will focus on If-Then-Else and Switch branching instructions.
[edit] If-Then
Let's take a look at a generic if statement:
if(condition) { action; } |
 |
What does this code do? In English, the code checks x, and doesn't jump if x is true. Conversely, the if statement does jump if x is false. In pseudo-code then, the previous if statement does the following:
if not condition goto end action end:
Now with that format in mind, let's take a look at some actual C code:
if(x == 0) { x = 1; } x++;
When we translate that to assembly, we need to reverse the conditional jump from a je to a jne because--like we said above--we only jump if the condition is false.
mov eax, $x cmp eax, 0x00000000 jne end mov eax, 1 end: inc eax mov $x, eax
When you see a comparison, followed by a je or a jne, reverse the condition of the jump to recreate the high-level code. For jump-if-greater (jg), jump-if-greater-or-equal (jge), jump-if-less-than (jl), or similar instructions, it is a bit different than simply reversing the condition of the jump. For example, this assembler code:
mov eax, $x //move x into eax cmp eax, $y //compare eax with y jg end //jump if greater than inc eax move $x, eax //increment x end: ...
Is produced by these c statements:
if(x <= y) { x++; }
As you can see, x is incremented only if it is less than or equal to y. Thus, if it is greater than y, it will not be incremented as in the assembler code. Similarly, the c code
if(x < y) { x++; }
Produces this assembler code:
mov eax, $x //move x into eax cmp eax, $y //compare eax with y jge end //jump if greater than or equal to inc eax move $x, eax //increment x end: ...
X is incremented in the c code only if it is less than y, so the assembler code now jumps if it's greater than or equal to y. This kind of thing takes practice, so we will try to include lots of examples in this section.
[edit] If-Then-Else
Let us now look at a more complicated case: the If-Then-Else instruction. Here is a generic example:
if(condition) { action; } else { alternative_action; } |
 |
Now, what happens here? Like before, the if statement only jumps to the else clause when condition is false. However, we must also install an unconditional jump at the end of the "then" clause, so we don't perform the else clause directly afterwards.
Here is the above example in pseudocode:
if not condition goto else action goto end else: alternative_action end:
Now, here is an example of a real C If-Then-Else:
if(x == 10) { x = 0; } else { x++; }
Which gets translated into the following assembly code:
mov eax, $x cmp eax, 0x0A ;0x0A = 10 jne else mov eax, 0 jmp end else: inc eax end: mov $x, eax
As you can see, the addition of a single unconditional jump can add an entire extra option to our conditional.
[edit] Switch-Case
Switch-Case structures can be very complicated when viewed in assembly language, so we will examine a few examples. First, keep in mind that in C, there are several keywords that are commonly used in a switch statement. Here is a recap:
- Switch
- This keyword tests the argument, and starts the switch structure
- Case
- This creates a label that execution will switch to, depending on the value of the argument.
- Break
- This statement jumps to the end of the switch block
- Default
- This is the label that execution jumps to if and only if it doesn't match up to any other conditions
Lets say we have a general switch statement, but with an extra label at the end, as such:
switch (x) { //body of switch statement } end_of_switch:
Now, every break statement will be immediately replaced with the statement
jmp end_of_switch
But what do the rest of the statements get changed to? The case statements can each resolve to any number of arbitrary integer values. How do we test for that? The answer is that we use a "Switch Table". Here is a simple, C example:
int main(int argc, char **argv) { //line 10 switch(argc) { case 1: MyFunction(1); break; case 2: MyFunction(2); break; case 3: MyFunction(3); break; case 4: MyFunction(4); break; default: MyFunction(5); } return 0; }
And when we compile this with cl.exe, we can generate the following listing file:
tv64 = -4 ; size = 4 _argc$ = 8 ; size = 4 _argv$ = 12 ; size = 4 _main PROC NEAR ; Line 10 push ebp mov ebp, esp push ecx ; Line 11 mov eax, DWORD PTR _argc$[ebp] mov DWORD PTR tv64[ebp], eax mov ecx, DWORD PTR tv64[ebp] sub ecx, 1 mov DWORD PTR tv64[ebp], ecx cmp DWORD PTR tv64[ebp], 3 ja SHORT $L810 mov edx, DWORD PTR tv64[ebp] jmp DWORD PTR $L818[edx*4] $L806: ; Line 14 push 1 call _MyFunction add esp, 4 ; Line 15 jmp SHORT $L803 $L807: ; Line 17 push 2 call _MyFunction add esp, 4 ; Line 18 jmp SHORT $L803 $L808: ; Line 19 push 3 call _MyFunction add esp, 4 ; Line 20 jmp SHORT $L803 $L809: ; Line 22 push 4 call _MyFunction add esp, 4 ; Line 23 jmp SHORT $L803 $L810: ; Line 25 push 5 call _MyFunction add esp, 4 $L803: ; Line 27 xor eax, eax ; Line 28 mov esp, ebp pop ebp ret 0 $L818: DD $L806 DD $L807 DD $L808 DD $L809 _main ENDP
Lets work our way through this. First, we see that line 10 sets up our standard stack frame, and it also saves ecx. Why does it save ecx? Scanning through the function, we never see a corresponding "pop ecx" instruction, so it seems that the value is never restored at all. In fact, the compiler isn't saving ecx at all, but is instead simply reserving space on the stack: it's creating a local variable. The original C code didn't have any local variables, however, so perhaps the compiler just needed some extra scratch space to store intermediate values. Why doesn't the compiler execute the more familar "sub esp, 4" command to create the local variable? push ecx is just a faster instruction that does the same thing. This "scratch space" is being referenced by a negative offset from ebp. tv64 was defined in the beginning of the listing as having the value -4, so every call to "tv64[ebp]" is a call to this scratch space.
There are a few things that we need to notice about the function in general:
- Label $L803 is the end_of_switch label. Therefore, every "jmp SHORT $L803" statement is a break. This is verifiable by comparing with the C code line-by-line.
- Label $L818 contains a list of hard-coded memory addresses, which here are labels in the code section! Remember, labels resolve to the memory address of the instruction. This must be an important part of our puzzle.
To solve this puzzle, we will take an in-depth look at line 11:
mov eax, DWORD PTR _argc$[ebp] mov DWORD PTR tv64[ebp], eax mov ecx, DWORD PTR tv64[ebp] sub ecx, 1 mov DWORD PTR tv64[ebp], ecx cmp DWORD PTR tv64[ebp], 3 ja SHORT $L810 mov edx, DWORD PTR tv64[ebp] jmp DWORD PTR $L818[edx*4]
This sequence performs the following pseudo-C operation:
if( argc - 1 >= 4 )
{
goto $L810; /* the default */
}
label *L818[] = { $L806, $L807, $L808, $L809 }; /* define a table of jumps, one per each case */
//
goto L818[argc - 1]; /* use the address from the table to jump to the correct case */
Here's why...
[edit] The Setup
mov eax, DWORD PTR _argc$[ebp] mov DWORD PTR tv64[ebp], eax mov ecx, DWORD PTR tv64[ebp] sub ecx, 1 mov DWORD PTR tv64[ebp], ecx
The value of argc is moved into eax. The value of eax is then immediately moved to the scratch space. The value of the scratch space is then moved into ecx. Sounds like an awfully convoluted way to get the same value into so many different locations, but remember: I turned off the optimizations. The value of ecx is then decremented by 1. Why didn't the compiler use a dec instruction instead? Perhaps the statement is a general statement, that in this case just happens to have an argument of 1. We don't know why exactly, all we know is this:
- eax = "scratch pad"
- ecx = eax - 1
Finally, the last line moves the new, decremented value of ecx back into the scratch pad. Very inefficient.
[edit] The Compare and Jumps
cmp DWORD PTR tv64[ebp], 3 ja SHORT $L810
The value of the scratch pad is compared with the value 3, and if the unsigned value is above 3 (4 or more), execution jumps to label $L810. How do I know the value is unsigned? I know because ja is an unsigned conditional jump. Let's look back at the original C code switch:
switch(argc) { case 1: MyFunction(1); break; case 2: MyFunction(2); break; case 3: MyFunction(3); break; case 4: MyFunction(4); break; default: MyFunction(5); }
Remember, the scratch pad contains the value (argc - 1), which means that this condition is only triggered when argc > 4. What happens when argc is greater than 4? The function goes to the default condition. Now, let's look at the next two lines:
mov edx, DWORD PTR tv64[ebp] jmp DWORD PTR $L818[edx*4]
edx gets the value of the scratch pad (argc - 1), and then there is a very weird jump that takes place: execution jumps to a location pointed to by the value (edx * 4 + $L818). What is $L818? We will examine that right now.
[edit] The Switch Table
$L818:
DD $L806
DD $L807
DD $L808
DD $L809
$L818 is a pointer, in the code section, to a list of other code section pointers. These pointers are all 32bit values (DD is a DWORD). Let's look back at our jump statement:
jmp DWORD PTR $L818[edx*4]
In this jump, $L818 isn't the offset, it's the base, edx*4 is the offset. As we said earlier, edx contains the value of (argc - 1). If argc == 1, we jump to [$L818 + 0] which is $L806. If argc == 2, we jump to [$L818 + 4], which is $L807. Get the picture? A quick look at labels $L806, $L807, $L808, and $L809 shows us exactly what we expect to see: the bodies of the case statements from the original C code, above. Each one of the case statements calls the function "MyFunction", then breaks, and then jumps to the end of the switch block.
[edit] Ternary Operator ?:
Again, the best way to learn is by doing. Therefore we will go through a mini example to explain the ternary operator. Consider the following C code program:
int main(int argc, char **argv) { return (argc > 1)?(5):(0); }
cl.exe produces the following assembly listing file:
_argc$ = 8 ; size = 4 _argv$ = 12 ; size = 4 _main PROC NEAR ; File c:\documents and settings\andrew\desktop\test2.c ; Line 2 push ebp mov ebp, esp ; Line 3 xor eax, eax cmp DWORD PTR _argc$[ebp], 1 setle al dec eax and eax, 5 ; Line 4 pop ebp ret 0 _main ENDP
Line 2 sets up a stack frame, and line 4 is a standard exit sequence. There are no local variables. It is clear that Line 3 is where we want to look.
The instruction "xor eax, eax" simply sets eax to 0. For more information on that line, see the chapter on unintuitive instructions. The cmp instruction tests the condition of the ternary operator. The setle function is one of a set of x86 functions that works like a conditional move: al gets the value 1 if argc <= 1. Isn't that the exact opposite of what we wanted? In this case, it is. Let's look at what happens when argc = 0: al gets the value 1. al is decremented (al = 0), and then eax is logically anded with 5. 5 & 0 = 0. When argc == 2 (greater than 1), the setle instruction doesn't do anything, and eax still is zero. eax is then decremented, which means that eax == -1. What is -1?
In x86 processors, negative numbers are stored in two's-complement format. For instance, let's look at the following C code:
BYTE x;
x = -1;
At the end of this C code, x will have the value 11111111: all ones!
When argc is greater than 1, setle sets al to zero. Decrementing this value sets every bit in eax to a logical 1. Now, when we perform the logical and function we get:
...11111111 &...00000101 ;101 is 5 in binary ------------ ...00000101
eax gets the value 5. In this case, it's a roundabout method of doing it, but as a reverser, this is the stuff you need to worry about.
For reference, here is the GCC assembly output of the same ternary operator from above:
_main: pushl %ebp movl %esp, %ebp subl $8, %esp xorl %eax, %eax andl $-16, %esp call __alloca call ___main xorl %edx, %edx cmpl $2, 8(%ebp) setge %dl leal (%edx,%edx,4), %eax leave ret
Notice that GCC produces slightly different code than cl.exe produces. However, the stack frame is set up the same way. Notice also that GCC doesn't give us line numbers, or other hints in the code. The ternary operator line occurs after the instruction "call __main". Let's highlight that section here:
xorl %edx, %edx cmpl $2, 8(%ebp) setge %dl leal (%edx,%edx,4), %eax
Again, xor is used to set edx to 0 quickly. Argc is tested against 2 (instead of 1), and dl is set if argc is greater then or equal. If dl gets set to 1, the leal instruction directly thereafter will move the value of 5 into eax (because lea (edx,edx,4) means edx + edx * 4, i.e. edx * 5).
