Function Signatures

Copy-paster's note: this article is here because it supplements the articles on the Orpheu module.

Contents:
I. Basics
II. Creating a function signature pattern
Appendix A. Finding the function you need

I. Basics
Do you know what the code of a C++ or assembly program turns into after compilation? Anyone who has ever opened executable files in a text editor saw only a pile of incomprehensible characters there. In fact, it is the sequence of bytes your program was turned into. The thing is that the processor knows nothing about C++, classes or objects; it doesn't even see the difference between positive and negative numbers. The processor can only execute micro-instructions, such as addition or division. These micro-instructions are small sequences of bytes, and the program consists of them. By reading the bytes, the processor recognizes the micro-instructions and executes them.

However, executable files consist of more than just micro-instructions. In both Windows and GNU\Linux, the program and the data it works with are held in a special wrapper that defines the file format. On Windows it is the PE format, and on GNU\Linux it is the ELF format. Each file contains a header that tells which format the file has.

In the case of executable files, the program is divided into a header and sections. The header contains information about the file itself and its sections. Sections can contain various kinds of data, including micro-instructions. The OS reads the header to know how to work with the file correctly.

The processor doesn't know where a function ends, where the text data is and where the micro-instructions are. The processor's work is controlled by the micro-instructions themselves. For example, you can place the text "Hello, brah" right in the middle of the code, but add micro-instructions telling the processor not to read that sequence of bytes. This means that functions regulate by themselves where they end, and there are no separators between them. The micro-instructions of functions simply follow one another.

So what are micro-instructions? Let's loosely divide the byte sequence of a micro-instruction into the following parts: opcode and operands. In reality the structure of micro-instructions is more complex, but this picture is enough for understanding. A micro-instruction's opcode is its unique name, and most often a single assembly command can correspond to several machine ones, which is done for convenience. Operands can be immediate values, addresses or registers. Sometimes an operand in the form of a register can produce a micro-instruction with a different opcode. An address is an offset from the start of the file that contains the function.

And now we have come to the topic of our article. What is a function signature? A function signature is generally considered to be the unique name of a function, which allows the translator to recognize it among other functions. In GNU\Linux these names are called symbols. And everything seems fine, but sometimes these names are stripped from the program and it is impossible to find the function by its name.
Therefore, in the context of our articles, a function signature is any unique sequence of bytes (which make up a set of the function's micro-instructions) that exists only within this function. Moreover, the whole sequence of the function's micro-instructions is also its signature. The question arises: why not simply search for the whole sequence of the function's micro-instructions? First, the function can be very large. Second, as discussed earlier, addresses can be used as operands of micro-instructions. And these addresses can be changed by a multitude of different reasons. That is why it is necessary to create a function signature pattern that can be used to find the function in a "changing environment".

The next article will cover using the obtained signatures to find functions in an executable file. After that, the function can be intercepted (splicing) by modifying its body, for example by inserting a trampoline to your own handler function.

II. Creating a function signature pattern
A pattern consists of two parts: a signature and a mask. The signature is that very unique sequence of bytes. The mask indicates which parts of the signature may change, so they are ignored during the search.

To get the information we need, we will use Interactive Disassembler (IDA). After opening the library under study, you need to turn on the display of micro-instruction codes. In the menu Options->General..., on the Disassembly tab, set the Number of opcode bytes field to 10. After that, their machine representation will appear to the left of the assembly micro-instructions.

Once you have found the function you need, you can start creating the pattern.

The function signature is that very unique sequence of bytes. Just copy them from the disassembler. The main condition is that this sequence must be unique within the program. I use 32 bytes as the signature, but the size is not limited in any way. It should be noted right away that these must be exactly the FIRST n bytes, since the address is the function's entry point, which is its beginning. This makes the search easier.

Next you need to build the signature mask, thereby excluding the dynamic parts. Addresses, as operands of micro-instructions, always change. In fact, only they are worth excluding from the search. These are usually the following micro-instructions:

jmp
call
conditional jumps jXX (jc, jnz, jbne etc.)
lea
mov

It is easy to tell that an address is used: the micro-instruction is 5 bytes or more in size (on 32-bit systems an address is 4 bytes, which is where the 4 GiB RAM limit comes from). Micro-instructions that work with immediate values and/or registers may be larger than 5 bytes, but they don't need to be excluded. The mask is a string in which the bytes containing dynamic values are marked with question marks ('?'), and all the others with 'x' or anything else.

Let's look at a small example. After the code come the mask characters that correspond to the micro-instruction codes.

Assembly

; пролог функции не нуждающийся в исключении
.text:01D6C2F0 55                      push    ebp
.text:01D6C2F1 8B EC                   mov     ebp, esp
.text:01D6C2F3 56                      push    esi
x
xx
x

;обычные операции с регистрами
.text:01D6C2F4 8B 75 08                mov     esi, [ebp+arg_0]
.text:01D6C2F7 56                      push    esi
xxx
x

;вызов функции, первый байт - опкод, остальные 4 - адрес, его мы помечаем знаками вопроса
.text:01D6C2F8 E8 B3 08 00 00          call    sub_1D6CBB0
x????

;обычные операции с регистрами
.text:01D6C2FD 83 C4 04                add     esp, 4
.text:01D6C300 83 F8 01                cmp     eax, 1
xxx
xxx

;короткий переход не использует адрес, лишь смещение относительно текущего адреса
.text:01D6C303 7C 38                   jl      short loc_1D6C33D
xx

;сравнение регистра eax с адресом
;первый байт - опкод, второй - регистр eax, остальные - адрес
.text:01D6C305 3B 05 28 6F 13 02       cmp     eax, dword_2136F28
xx????

;опять короткий переход
.text:01D6C30B 7F 30                   jg      short loc_1D6C33D
xx

;перемещение в регистр адреса
;первый байт - опкод, второй - регистр edx, остальные - адрес
.text:01D6C30D 8B 15 24 6F 13 02       mov     edx, dword_2136F24
xx????

;обычные операции с регистрами и непосредственными значениями
.text:01D6C313 8D 0C 80                lea     ecx, [eax+eax*4]
.text:01D6C316 C1 E1 09                shl     ecx, 9
.text:01D6C319 03 C8                   add     ecx, eax
.text:01D6C31B 6A 39                   push    39h
xxx
xxx
xx
xx

;обратите внимание, код микрокоманды занимает 7 байт, но не использует адреса
;это значит что исключать из поиска ничего не нужно
.text:01D6C31D 8D 84 CA F8 AF FF FF    lea     eax, [edx+ecx*8-5008h]
xxxxxxx

;опять опычные операции
.text:01D6C324 8D 70 7C                lea     esi, [eax+7Ch]
.text:01D6C327 56                      push    esi
xxx
x

;вызов функции, первый байт - опкод, остальные - адрес
.text:01D6C328 E8 F3 9E FC FF          call    sub_1D36220
x????

As a result we get:
signature: "55 8B EC 56 8B 75 08 56 E8 B3 08 00 00 83 C4 04 83 F8 01 7C 38 3B 05 28 6F 13 02 7F 30 8B 15 24 6F 13 02 8D 0C 80 C1 E1 09 03 C8 6A 39 8D 84 CA F8 AF FF FF 8D 70 7C 56 E8 F3 9E FC FF"
mask: "xxxxxxxxx????xxxxxxxxxx????xxxx????xxxxxxxxxxxxxxxxxxxxxx????"

The more you practice, the easier it gets. For me, finding the function and creating the pattern takes no more than 3 minutes.

A note on symbols. The GNU\Linux hlds libraries contain function symbols, which can be used to find functions. It is recommended to do it this way, since changing a function does not change its symbol (except when the arguments change - symbols usually include the function name and its arguments). Windows libraries have no symbols.

Appendix A. Finding the function you need
Another bottleneck is finding the function's disassembled code in IDA. Here are a few tips:

Look in the GNU\Linux libraries first. Most functions can be found by name, since the libraries contain symbol names.
If you don't know the function's name, look for the nearest names related to this function, strings, cvar names, variables. The function name you find is a symbol that can be used for searching in the GNU\Linux libraries.
Finding the equivalent function in the Windows library takes some effort. Windows libraries have no symbols, so you have to look for workarounds. Here too you can find the function by the string constant it uses, or by cvars.
There is an interesting method: if the function uses an unusual size of local variables, you can find all occurrences of the opcode that allocates stack space for local variables - sub esp, xx. Then look for the most plausible allocated size and check whether it is the function you need.
There are cases when a function in the GNU\Linux library is a regular one, but in Windows it is inlined. This means the function's code is substituted at the call site and no separate function exists.
If you are converting disassembled code into C, you should rely on the Windows libraries. I don't know the exact reason, maybe gcc optimizes so well, or maybe HEX-Rays decompiles it poorly, but Windows functions decompile better, and the resulting code is more structured. Decompile both versions of the function: the Windows version will show the structure, and the GNU\Linux one will show the names of the functions used.

Image: http://i.creativecommons.org/l/by-sa/3.0/88x31.png

This work is licensed under a Creative Commons Attribution-ShareAlike 3.0 Unported License.

Source: http://www.amx-x.ru/viewtopic.php?f=28&t=8004