Monday, January 11, 2010

Finding the number of parameters directly in the assembly

Recently, when working on my library tracer, I wanted to know the number of parameters a function uses. I did not have any access to source code or debug info, so I had to find another way to get this information. Programs like ltrace/strace have an extra file, usually located in /etc/ to define the prototype of certain functions. When ltrace does not know a specific function prototype, it simply sets the number of parameters to 5 by default. However, by doing a simple analysis of the assembly code we can infer the number of parameters with a pretty high success rate. In my study I assumed we are using a x86_64 Linux box that binaries have not been obfuscated.

We will focus on regular registers, but the theory applies for FPU registers too. By convention, on x86_64, GCC will use the registers to pass the arguments (before using the stack), in the following order: %di - %si - %dx - %cx - %r8 and %r9. Thus, without loss of generality, up to 6 parameters can be passed through registers (before using the stack), with some exceptions for bigger data structures.

We define a block as being the set of instructions between two instructions changing the control flow (e.g.: ret / call / j). First, we localize this instructions in the disassembled program. From there, we move backward to retrieve the different parameters.

Let's do it on a example. The following snippet of code defines 4 blocks:


402406: 84 c0 test %al,%al
402408: 0f 84 62 ff ff ff je 402370
----------------------------------------------------------
40240e: 40 84 ff test %dil,%dil
402411: 74 e0 je 4023f3
----------------------------------------------------------
402413: 83 3d e2 5e 21 00 03 cmpl $0x3,0x215ee2(%rip)
40241a: 75 d7 jne 4023f3
----------------------------------------------------------
40248c: 48 8b 2d 35 69 21 00 mov 0x216935(%rip),%rbp
402493: ba 05 00 00 00 mov $0x5,%edx
402498: be 88 0b 41 00 mov $0x410b88,%esi
40249d: 31 ff xor %edi,%edi
40249f: e8 24 fb ff ff callq 401fc8

If we take the last block, and we perform a backward analysis, we figure out that the registers %di, %si, %dx (and %bp) are modified. According to the _cdecl_ calling convention, it is likely that the function will take 3 arguments before jumping into the plt trampoline.

Sadly, this is not always as clear as in the previous example. For instance, we can see that the others block does not follow this nice rule, but can we deduce the function are not expecting any parameter ? As it was previously stated, it is very rare that a function in called only once. Although, the main purpose of a function is exactly the opposite, ie being called as often as possible from various parts of the program. Thus, by applying the previous criterion over all functions, we can deduce a heuristics that will retrieve the number of arguments with a good success rate.

Every time we encounter a function call, we save the set of registers of the block. A map looks like the following: (%di. %si. %dx. %cx, %r8, %r9). Every element is a boolean and says whether the register was used or not.

Let's take the same function as before, dcgettext(..) from /bin/ls. The function is called around 15 times in the overall program, but all the registers cannot be retrieved every time.

(0, 0, 1, 1, 0, 0)
(0, 0, 1, 0, 0, 0)
(0, 1, 1, 0, 0, 0)
(1, 0, 1, 0, 0, 0)
(1, 1, 1, 0, 0, 0)
[...]

Typically, (0, 0, 1, 1, 0, 0) means that only registers %dx and %cx were used. Thus, we take the set that has been used the most frequently. Let's assume the set appearing the most often is: (0, 0, 1, 0, 0, 0). This would mean that only register %dx is used. However, we do have a discrepancy compared to the official _cdecl_, because the first parameter must be sent through the %di register.

A good practice is to set to 1 all the registers that are on the left of the top-right register in the map. Thus, (0, 0, 1, 0, 0, 0) will become (1, 1, 1, 0, 0, 0). This means that register %di and %si are also used. To make sure our theory is correct, we can check in the man pages that the prototype is correct:

char * dcgettext (const char * domainname, const char * msgid, int category);

For the function having an associated man page, this technique has been shown to be very effective, by retrieving correctly the number of registers 90% of the time. When the mean gives us a guessable output, we will always choose the value that have more registers set, in order not to miss any of them. Note that this technique is very light, since it does not require to go into the called function to analyze the parameters in there.

To implement this, I chose Perl for a simple reason: I get the binary output from objdump and then I can parse into it pretty easily with simple regex. Using this kind of techniques we can also infer the type of the parameters, but this is another story 8).

No comments:

Post a Comment