Auto discover function locations in a target executable known from a source executable

[xezon]

We need a way to discover all function symbols in a target executable from a source executable.

Possible directions are:

Mach-O to x86 Release.
x86 Release to x86 Debug.

Step 1

Discover addresses to functions in the target executable(s). This simply gives a long list of function addresses without knowing what these functions are.

Potential approach 1

Crawl over assembly instructions beginning from the entry point and enter all calls and jumps once to try discover all function addresses.

Potential approach 2

Crawl over all assembly instructions from top to bottom and detect function headers and footers of functions that have them.

Potential approach 3

Export a list of function addresses from a disassembler tool if it can generate it already.

Check quality

To verify the quality of the address list, compare it with the addresses known from the disassembler tool.

Step 2

Discover names and properties to function addresses in the target executable(s). This gives a long list of function properties for the known function addresses.

Possible approach 1

Process the assembler instructions of the source and target executables and break them down into simplified instructions that can be matched across the executables. Pick a function of the source executable and try to match it with all functions of the target executable. Give scores for the match quality and let the best score win. Search locality and score optimizations can apply if nearby function addresses are already known.

Simplified instructions can contain, among others:

• reading a global X or offset N
• jumping short
• calling a global X or offset N
• returning a value of size N

Ordered combinations of simplified universal instructions should give a function a somewhat unique print. The more complexity the function has, the better the match quality can be. Simplified instructions may not compare optimal in case compilers use different strategies to generate code, such as unrolling loops or wild jumps. In this case the matching strategy needs to be smart and lenient. In theory, even a bad matching score could still present the right winner.

Possible approach 2

Train an Ai to understand how a function body from a source executable matches to a target executable. To do this, we would need to compile programs with relevant compilers, crawl through their symbols, and train the AI to recognize how the function instructions of the source executable translate to the target executable. After the training is complete, the Ai Model can be used to match all functions from the target executable.

Check quality

To verify the quality of the matching, check for collisions. If too many matches are colliding, then it is not right.

Also, compare it with the addresses and symbols from the disassembler that have been mapped by hand already.

[xezon]

Instruction markers with GCC vs MSVC x86

Theory: Function match quality can be estimated by finding instruction "markers", save their relative location (in %) and compare it with the other side. The more markers are similarly placed on both sides, the better the match quality.

function length

The function length can be a matching quality factor.

function proximity

The function proximity to other functions can be a matching quality factor.

mov or push global string offsets

Static strings are typically identical.

gcc:  mov     dword ptr [esp+4], offset asc_64E8CC ; "\n LOD %d, time %.2fms\n"
msvc: push    offset asc_A0E04C ; "\n LOD %d, time %.2fms\n"

mov or push constant value(the closer the better)

The closer the value, the better the match!

gcc: __textcoal_nt:006E423E  C7 04 24 D0 00 00 00    mov     dword ptr [esp], 0D0h
msvc:        .text:007421C6  68 CC 00 00 00          push    0CCh

gcc:  __text:0042D5E4  C7 44 24 08 21 00 00 00    mov     dword ptr [esp+8], 21h
msvc:  .text:007413C7  6A 21                      push    21h

Perhaps need to ignore small number < 8 or so. Compilers generate noise with small numbers.

mov global data offsets into registers

gcc:  mov     ecx, ds:_TheWritableGlobalData_ptr
msvc: mov     ecx, _TheWritableGlobalData

gcc:  A1 F0 0A 7F 00       mov     eax, ds:W3DDisplay::m_3DScene
msvc: 8B 0D 0C 25 A3 00    mov     ecx, W3DDisplay::m_3DScene

gcc:  __text:0042D596  A1 E4 0A 7F 00    mov     eax, ds:W3DDisplay::m_assetManager
msvc:  .text:0074136E  A1 18 25 A3 00    mov     eax, W3DDisplay::m_assetManager

It would help massively to know the symbol of the data, but can we know it?

mov, cvtsi2ss, fild dword ptr [register + offset(the closer the better)]

The closer the offset value, the better the match!

gcc:  cvtsi2ss xmm0, dword ptr [eax+48h]
msvc: fild    dword ptr [ecx+48h]

call C functions

Calling a C function which we may know the symbol for:

gcc:  call    _QueryPerformanceFrequency
msvc: call    ds:QueryPerformanceFrequency

gcc:  __textcoal_nt:006E4245  E8 A0 FF F1 FF    call    operator new(ulong)
msvc:         .text:007421CB  E8 80 22 CD FF    call    void * operator new(uint)

call 4 byte address

Calling a 4 byte address to somewhere:

gcc:  E8 65 8B 1A 00    call    WW3D::Begin_Render(bool,bool,Vector3 const&,float,void (*)(void))
msvc: E8 1F 97 0C 00    call    WW3D::Begin_Render(bool,bool,Vector3 const&,float,void (*)(void))

It would help massively to know the function symbol name, but that is chicken egg problem...

call dword ptr [register + offset(the closer the better)]

The closer the value, the better the match!

Offsets are very close:

gcc:  call    dword ptr [edx+1FCh]
msvc: call    dword ptr [edx+1E4h]

Call operands can be optimized differently: Not straight forward to compare.

gcc:  __text:0042AEDE  8B 70 54    mov     esi, [eax+54h]
      ...
      __text:0042AEFF  FF D6       call    esi
msvc:  .text:0073ED1D  FF 52 50    call    dword ptr [edx+50h]

jumps

Number of jump instructions (any kind) in locations can be a matching quality factor.

gcc:  __text:0042AE64  7A 0A                jp      short loc_42AE70
      __text:0042AE66  73 08                jnb     short loc_42AE70
msvc:  .text:0073EC6A  0F 85 F1 00 00 00    jnz           loc_73ED61

gcc:  __text:0042D5A6  75 08                jnz     short loc_42D5B0
msvc:  .text:00741397  0F 84 17 02 00 00    jz            loc_7415B4