Follow us on Twitter!
It is the path of least resistance that makes rivers and men crooked. - Bj Palmer
Wednesday, April 23, 2014
Navigation
Home
HellBoundHackers Main:
HellBoundHackers Find:
HellBoundHackers Information:
Learn
Communicate
Submit
Shop
Challenges
HellBoundHackers Exploit:
HellBoundHackers Programming:
HellBoundHackers Think:
HellBoundHackers Track:
HellBoundHackers Patch:
HellBoundHackers Other:
HellBoundHackers Need Help?
Other
Members Online
Total Online: 19
Guests Online: 16
Members Online: 3

Registered Members: 82877
Newest Member: MWiki
Latest Articles

Reverse Engineering Terminology and Logic

Arrow Image Terminology and Logic behind Assembly language and an introduction to Optimization



--------------------------------------------------------------------------------------------------------------------
****************Reverse Engineering Terminology and Logic -- by Frost_T*******************
--------------------------------------------------------------------------------------------------------------------


--------
-Intro:
--------

Welcome to Reversing Terminology and Logic. The goal of this article isn\'t to help you through any of the application challenges on here, probably lost 50% of you by now ;), but to enlighten you as to how assembly language logic works, how its efficiency is maximized, and how assembly language translates to the high-level counterparts.

------------
-Terminology
------------

Before we can just jump into the logic behind high-level to low-level conversions, we must first be familiarized with the instructions used in assembly language. Other articles cover certain ones, yet I felt the more important ones were over-looked; therefore here is a simplified list:

Conditional codes:

cmp --- Compare, simple enough, compares two values, whether they be variables, or constants.
je --- Jump if equal, will perform the jump if the preceding values are equal
jne --- Jump if not equal, performs the jump if values are not equal
jmp --- Unconditional jump, will jump regardless

Mathematical:

add, sub, mult, div --- Common sense, don\'t need an explanation
shl --- Shift to the left, performs a \'binary shift\' to the left, which is equivalent to multiplying by 2
shr --- Shift to the right, performs another \'binary shift\', which is dividing by 2

Calls:

calls require a bit of a note before I can introduce the actual instructions. Firstly, there are two types of commands, imported, and internal. Secondly, CALL instructions include prologues(the \'call\' itself) and epilogues(a \'ret\' instruction), which are what make them easily recognizable from a reversing point of view.

call codeaddress --- Sample of an internal function, where it will jump to the written address

call DWORD PTR [pointer] --- Sample of an external function, pointers are above the scope of this article, however it enough to understand that it will jump to the code that the pointer points to, not the address of the pointer itself.

Registers:

If assembly language code were to access RAM every time it needed to store a variable or a value, then programs would run horrendously slow. To counter this, CPUs have their own internal memory, called registers. Typical IA-32 processors have 8 registers, all of which are generic. The functions of ESI, EDI, EBP, and ESP are unfortunately outside the scope of this article, however here is a list of those 8, and a list of their general use:

EAX, EBX, EDX --- Used for any integer/boolean/logical/memory operations
ECX --- Sometimes used as a counter, as those used in loops
ESI/EDI --- Used as source/destination pointers
EBP --- Used as a stack base counter
ESP --- Used as the CPU stack pointer

----------------
Logic: Branching
----------------

Ok, now that we\'ve gotten the basics out of the way, let\'s move on to the actual logic. Ever wonder how high-level language statements are represented in assembly language? no? Well what are you doing reading this article! Suffice to say, assembly language is represented much more abstractly, and sometimes it may not be easy to recognize the similarities. However, I will attempt clarify the ambiguity, allowing you to recognize patterns, and then reconstruct the high-level code from the assembly language code.

** Single Branching **

Single branching refers to a fork, where when code reaches a point, it will either go in one direction, or the other. This is represented in high-level programming with an \'if\' statement.

-- The high level representation --

if (variable == 10)
CallFunction();

-- Assembly language representation --

mov eax, [variable] ---> moves variable into eax
cmp eax, 10 ---> compares value with 10
jne Afterfunction ---> jumps to Afterfunction if not equal
call Function
Afterfunction ---> section it jumps to if not equal

As you can see, the code moves our inputted variable into eax, then will cmp eax with 10. Now if they are equal it will skip over the jne, and move to \'call Function\', which will call up our function. If they are NOT equal however, once the code reaches \'jne Afterfunction\', it will see that they are not equal, and jump to \'Afterfunction\'.

** Two Way Conditional Branching **

Two way conditionals are similar to single branching. They are represented by an if-else statement in high-level coding.

-- The high level representation --

if (variable == 10)
Function();
else
OtherFunction();

-- Assembly language representation --

mov eax, [variable]
cmp eax, 10
jne OtherFunction
call Function
jmp AfterIfElse
call OtherFunction
AfterIfElse...

A quick summary about the assembly code: Moves our variable into eax, then compares it to 10. If it is not equal to 10, it will jump to \'call OtherFunction\', which calls the respected function and then exits the conditional section. If it is equal to 10, it does not jump, moves on to \'call Function\', which again calls the respected Function, then after the function is complete, returns, and unconditionally jumps out of the conditional section.

** Multiple-Alternative Branching **

This is essentially the same as two way, just instead of an else, it would be an else-if. I will therefore quickly go over this one and skip the summary.

-- The high level representation --

if (variable == 10)
Function();
else if (variable == 365)
OtherFunction();

-- Assembly language representation --

mov eax, [variable]
cmp eax, 10
jne OtherFunction
call Function
jmp Afterfunction
cmp eax, 365 ---> Where \'jne Otherfunction\' jumps to
jne Afterfunction
call OtherFunction
Afterfunction...

** Compound Conditional Branching **

Compound Conditionals refer to when more than one condition must be satisfied before the condition is s

-- The high level representation --

if (variable == 10 &&
variable2 == 50)
Function();

-- Assembly language representation --

cmp [variable], 100
jne Afterfunction
cmp [variable2], 50
jne Afterfunction
call Function
Afterfunction...

The same kind of conditional can be built using OR\'s instead of AND\'s.

-- The high level representation --

if (variable == 10 ||
variable2 == 50)
Function();

-- Assembly language representation --

cmp [variable], 10
je Function
cmp [variable2], 50
je Function
jump Afterfunction
call Function
Afterfunction...

As you can see, the code checks if the first variable equals 10, and if it does, jumps to the \'call Function\', disregarding the second variable. If, however, the first variable does not equal 10, then the code immediately check the second variable to see if it equals 50. If it is, it then jumps to the \'call Function\'. Otherwise it then unconditionally jumps to after the function at Afterfunction.

-----------
Logic:Loops
-----------

Loops are an essential part of programming. Loops are essentially the same as the code we have been watching except that the code gets repeated. There are essentially two types of loops, Pre-tested loops, and Post-tested loops. As their names indicate, pre-tested check the conditions before the code is executed, and post-tested execute the code first, then check the conditions.

** Pre-Tested Loop **

Pre-tested loops are slightly less efficient then post-tested loops in the fact that they need two jumps: a conditional branch in the beginning, and an unconditional jump at the end that jumps back to the beginning.

-- The high level representation --

a = 0
while (a < 100)
{
array[a] = a;
c++;
}

-- Assembly language representation --

mov ecx, DWORD PTR [array]
xor eax,eax ---> xor\'s eax to zero
mov DWORD PTR [ecx+eax*4], eax ----> beginning of loop
add eax, 1
cmp eax, 100
jl ------------------> Jumps to beginning of loop if lower then 100

Ok, this code needs a bit of explaining. Firstly, you might be wondering why the conditional is at the beginning in the high-level code, yet at the end of the assembly language code? That is actually due to the compiler. It is slightly more efficient to put the test at the end of the code, since it will not require an unconditional JMP, so the compiler moved it there. I will go more in-depth later in the article. What the code is doing is firstly XORing eax, which is setting it to zero. Then the code will execute the loop, ADD 1 to eax, which is our counter. It will then CMP our counter to 100, and if it is less it will jump back to the beginning of the loop, essentially continuing until it reaches 100, where it will then exit the loop.

** Post-Tested Loop **

If a compiler already produces a post-tested loop from a pre-tested loop, you may be asking yourself what the compiler will do with a post-tested loop. If you answered \"They would essentially be the same\" you are right! The compiler basically re-arranges the code to make it the most efficient. So a sample would look like:

-- The high level representation --

a = 0
do
{
array[a] = a;
c++;
} while (c < 100);


-- Assembly language representation --

mov ecx, DWORD PTR [array]
mov DWORD PTR [ecx+eax*4], eax ----> beginning of loop
add eax, 1
cmp eax, 100
jl ------------------> Jumps if lower then 100

As you can see the only difference is that there is no XORing involved in the post-tested. Since the Pre-tested loop\'s conditional statement was moved to the end, the compiler added the XOR function to make sure \'a\' was within the boundaries of the conditional. The only difference with the post-tested is that in the post-tested the code will run at least once, no matter what a is set as, therefore there is no need to modify a.

----------
Efficiency
----------

The code you have seen so far in this article is only one of many ways of interpreting a high-level language. The style is mostly dependent on the compiler you use, however most compilers will strive to achieve the highest efficiency. Efficiency can be accomplished by either generating the smallest possible program binaries, or the most high high-performance code possible. In this section I\'ll give examples of such Optimization.

Mathematically:

Multiplication and Division are considered \'Complex\' operations by the CPU. To compensate for that, the CPU will perform a series of \'Simpler\' operations. Although there may be many more operations to get the equivalent result, the net result will still be faster than the slower multiplication and division.

** Multiplication **

A sample of multiplying a variable by 32 in an efficient way:

lea eax, DWORD PTR [edx+edx] ----> lea is what the processor uses to make quick additions and shifts
add eax, eax
add eax, eax
add eax, eax
add eax, eax

As you can see, the first line will add your variable which is stored in edx with itself, then store the result in eax. Then the code will add eax with itself 4 times, resulting in 32 times the original edx value.

** Division **

Division is by far the slowest of the arithmical operations of a processor. Division is upwards 50 cycles slower then Addition and Subtraction, each of which is less than 1 cycle. As a result, the CPU treats divisions differently and attempts to streamline this operation using \'Reciprocal Division\'. This is not ALWAYS possible, as is the case with unknown divisors, however whenever possible, reciprocal division is sought after. An example of a typical reciprocal-division that is dividing our value by 3 is:

mov ecx, eax ---> moves our number into ecx
mov eax ,0xaaaaaaab ---> moves 2/3 into eax
mul ecx ---> multiplies ecx by eax, so our value * (2/3)
shr edx, 2 ---> then divides our value by 2, so value * (2/3) / 2 = value * (1/3)
mov eax, edx ---> then moves our divided value back into eax

What is that 0xaaaaaab you might be asking? Well that is how Reciprocal-Division is used. In the above code, the function is dividing the value by 3. It is combining a reciprocal 0xaaaaaab, whose value in fractional is 2/3, with another divisor of 2, which comes out to being divided by 3. (2/3) / 2 = (1/3). Combining a fraction with a simple divisor, such as a binary shift, the CPU can create a division as efficiently as possible.

Branching Optimization:

** Branching **

Optimization and efficiency aren\'t only restricted to mathematical operations. Code segments such as branching can also be modified to operate more efficiently. The following is an example of more efficient/less efficient using a simple IF-OR statement like the one shown earlier in the article.

--- less efficient ---

cmp [variable], 10
je Function
cmp [variable2], 365
je Function
jmp Afterfunction
Call Function
Afterfunction...

--- more efficient ---

cmp [variable], 100
je Function
cmp [variable2], 365
jne Afterfunction
call Function
Afterfunction...

As you can see both codes execute the same branching conditional, however the section on the right has less instructions, and is therefore more efficient. The same can be said for pretty much all sections of code, there is almost always a way to make the code more efficient.

----------
Conclusion
----------

Well here comes to end my first of hopefully several articles related to Reverse Engineering / Low level logic. Hopefully this article has enlightened you in some way, and has peaked your interest in low-level logic and the transition from high-level to low-level. Thank you again for reading this, and if you have any comments/critique, please feel free to leave them.

Frost_T

Comments

Apollo_15on January 13 2008 - 23:30:30
wow. nice article. it helped me. tnx
Futilityon January 13 2008 - 23:33:08
Jeez- how long did it take to write that? Very in-depth and helpful. Thanks a lot.
Frost_Ton January 14 2008 - 00:12:49
hehe, Futility, you'd be surprised, I started last night, wrote for about 2 hours, then another hour this morning and the spend the rest of the day proofing/editing it. Pfft...btw thanks guys for the comments/ratings!
Zephyr_Pureon January 14 2008 - 03:10:37
Very nice article. Even though I don't dabble in Assembly, this article makes me want to now! Oh, and before anyone else criticizes the author for it... yes, his while loop writes 0 to the first spot in the array 100 times. Such mistakes are forgivable, especially when the rest of the content is of such a pleasing quality. I look forward to your later articles!
Zephyr_Pureon January 14 2008 - 03:11:31
Oh, and that was the second while loop... the first one is an infinite loop. Pfft
Frost_Ton January 14 2008 - 03:14:58
sorry about that zephyr Pfft but thanks for the kind criticism!:happy:
spywareon January 14 2008 - 11:31:43
Grand, you are true. Stick with it <3
Uber0non January 14 2008 - 16:05:02
I'm surprised to see such good explanations of ASM code Smile very well done!
hellboundhackersokon January 15 2008 - 02:21:22
Thats a great article! Thanks for posting it Grin
korgon January 15 2008 - 09:53:47
Sweet article, Good content, If you guy's want more info look for the SnD teams cracking tuts. Great job here, Thanks awesome read. forums.techarena.in/images/smilies/thumbsupsmiley.gif
goofyon January 21 2008 - 17:03:25
Great article, Good explanation. It helped me a lot.
DigitalFireon February 01 2008 - 02:25:04
well written. i enjoyed Grin
sam207on October 14 2008 - 01:59:04
well written, awesome..
NigNigon November 06 2008 - 18:09:52
Looks good, especially the high level/low level comparison parts but you missed out flags and more importantly what instructions set the flags, but I suppose these can be covered in later articles with the rest, more in depth
Frvmannon November 08 2012 - 14:31:30
I like it man, it's good. Thanks for the help!!!:ninja:
Post Comment

Sorry.

You must have completed the challenge Basic 1 and have 100 points or more, to be able to post.