What is "overlapping instructions" obfuscation?

Question

I analyzed some binaries in x86/x86-64 using some obfuscation tricks. One was called overlapping instructions. Can someone explain how does this obfuscation work and how to work around?

Answer 1

The paper Static Analysis of x86 Executables explains overlapping instructions quite well. The following example is taken from it (page 28):

0000: B8 00 03 C1 BB  mov eax, 0xBBC10300
0005: B9 00 00 00 05  mov ecx, 0x05000000
000A: 03 C1           add eax, ecx
000C: EB F4           jmp $-10
000E: 03 C3           add eax, ebx
0010: C3              ret

By looking at the code, it is not apparent what the value of eax will be at the return instruction (or that the return instruction is ever reached, for that matter). This is due to the jump from 000C to 0002, an address which is not explicitly present in the listing (jmp $-10 denotes a relative jump from the current program counter value, which is 0xC, and 0xC10 = 2). This jump transfers control to the third byte of the five byte long move instruction at address 0000. Executing the byte sequence starting at address 0002 unfolds a completely new instruction stream:

0000: B8 00 03 C1 BB  mov eax, 0xBBC10300
0005: B9 00 00 00 05  mov ecx, 0x05000000
000A: 03 C1           add eax, ecx
000C: EB F4           jmp $-10
0002: 03 C1           add eax, ecx
0004: BB B9 00 00 00  mov ebx, 0xB9
0009: 05 03 C1 EB F4  add eax, 0xF4EBC103
000E: 03 C3           add eax, ebx
0010: C3              ret

It would be interesting to know if/how Ida Pro and especially the Hex Rays plugin handle this. Perhaps @IgorSkochinsky can comment on this...

Answer 2

It's also known as the 'jump in the middle' trick.

explanation

execution rules

• most instructions take more than one byte to be encoded
  • they can take up to 15 bytes on modern CPUs
• execution can start at any position as long as permissions are valid

so any byte following the first one of an instruction can be re-used to start another instruction.

abusing disassemblers

• straighforward disassemblers start the next instruction right after the end of the last one.

so such disassemblers (that don't follow the flow) will hide the instruction that is in the middle of a visible one.

examples

trivial

00: EB 01           jmp  3
02: 68 c3 90 90 90  push 0x909090c3

will effectively execute as

00: EB 01           jmp  3
03: C3              retn
...

as the first jmp skips the first byte 68 (which encodes an immediate push) of the following instruction.

multiple overlaps

from this example, 69 84 defines an imul instruction that can take up to 11 bytes. Thus you can fit several lines of instruction in its 'fake' operands.

00: EB02                    jmp  4
02: 69846A40682C104000EB02  imul eax, [edx + ebp*2 + 0102C6840], 0x002EB0040
0D: ....

will actually be executed as

00: EB02       jmp  4
04: 6A40       push 040
06: 682C104000 push 0x40102C
0B: EB02       jmp  0xF
0F: ...

instruction overlapping itself

The instruction is jumping in the 2nd byte of itself:

00: EBFF    jmp 1
02: C0C300  rol bl, 0

will actually be executed as

00: EBFF    jmp 1
01: FFC0    inc eax
03: C3      retn

different CPU modes

this obfuscation can be extended to jumping to the same EIP but in different CPU mode:

• 64b CPUs still supports 32b instruction
• 64b mode is using 0x33 for cs
• some instructions are available only in a particular mode:
  • arpl in 32b mode
  • movsxd in 64b mode

so you can jump to the same EIP but with a different CS, and get different instructions.

In this example, this code is first executed in 32b mode:

00: 63D8   arpl   ax,bx
02: 48     dec    eax
03: 01C0   add    eax,eax
05: CB     retf

and then re-executed in 64 bit mode as:

00: 63D8   movsxd rbx,eax
02: 4801C0 add    rax,rax
05: CB     retf

In this case, the instructions are overlapping, not because of a different EIP, but because the CPU temporarily changed from 32b to 64b mode.

Answer 3

Almost any multi-byte instruction can be used as an overlapping instruction in x86/x86_64. The reason is very easy: x86 and x86_64 instruction sets are CISC. Which means, among other things, that the instructions doesn't have a fixed length. So, as the instruction are variable length, carefully writing that machine code, every instruction is susceptible of hiding overlapping instructions.

For example, given the following code:

[0x00408210:0x00a31e10]> b
0x000050f5 (01) 56                     PUSH ESI 
0x000050f6 (04) 8b742408               MOV ESI, [ESP+0x8] 
0x000050fa (01) 57                     PUSH EDI 
0x000050fb (03) c1e603                 SHL ESI, 0x3 
0x000050fe (06) 8bbe58a04000           MOV EDI, [ESI+0x40a058] 
0x00005104 (01) 57                     PUSH EDI 
0x00005105 (06) ff15f4804000           CALL 0x004080f4  ; 1 KERNEL32.dll!GetModuleHandleA
0x0000510b (02) 85c0                   TEST EAX, EAX 
0x0000510d (02) 750b                   JNZ 0x0000511a   ; 2 

Let's suppose that somewhere after the last instruction there is a jump in the middle of some instruction in the displayed code as, for example, to the 2nd byte in the MOV ESI... instruction:

[0x000050f7:0x00405cf7]> c
0x000050f7 (02) 7424                   JZ 0x0000511d    ; 1 
0x000050f7 ----------------------------------------------------------------------
0x000050f9 (03) 0857c1                 OR [EDI-0x3f], DL 
0x000050fc (02) e603                   OUT 0x3, AL 

It turns out that this instruction changes to a JZ. Which is valid. Jumping to the 3rd byte...

[0x000050f7:0x00405cf7]> s +1
[0x000050f8:0x00405cf8]> c
0x000050f8 (02) 2408                   AND AL, 0x8 
0x000050fa (01) 57                     PUSH EDI 
0x000050fb (03) c1e603                 SHL ESI, 0x3 
0x000050fe (06) 8bbe58a04000           MOV EDI, [ESI+0x40a058] 

Jumping to the 2nd byte of the CALL instruction:

[0x000050f5:0x00405cf5]> s 0x5106
[0x00005106:0x00405d06]> c
0x00005106 (05) 15f4804000             ADC EAX, 0x4080f4    ; '\x8e\x91'
0x0000510b (02) 85c0                   TEST EAX, EAX 
0x0000510d (02) 750b                   JNZ 0x0000511a   ; 1 

As you can see, virtually any multi-byte instruction is susceptible of being used as an overlapping instruction.

This anti-reversing trick is quite often used with opaque predicates in order to f**k the flow graph.

Answer 4

Because x86 instructions can be any length and don't need to be aligned, one instruction's immediate value can be another instruction altogether. For example:

00000000  0531C0EB01        add eax,0x1ebc031
00000005  055090EB01        add eax,0x1eb9050
0000000A  05B010EB01        add eax,0x1eb10b0
0000000F  EBF0              jmp short 0x1

This does exactly what it says, until the jump. When it jumps, the immediate value being added to eax become an instruction, so the code looks like:

00000000  05                db 5
00000001  31C0              xor ax,ax           xor ax, ax
00000003  EB01              jmp short 0x6
00000005  05                db 5
00000006  50                push ax             push ax
00000007  90                nop
00000008  EB01              jmp short 0xb
0000000A  05                db 5
0000000B  B010              mov al,0x10         mov al,0x10
....

The instructions which are actually significant are shown in the right-hand column. In this example, short jump instructions are used to skip the add eax part of the instruction (05). It should be noted that this could be done more effectively by using an single-byte to eat the 05s, like 3C05 which is cmp al, 0x5, and would be harmless in code that doesn't care about the flags.

In the pattern above, you easily replace all the 05s with 90 (nop) to view the correct disassembly. This can be made trickier by using the 05s as immediate values to hidden code (that the execution depends on). In reality, the person obfuscating the code would probably not use add eax over and over again, and might change the execution order to make it messier to trace.

I prepared a sample using the pattern above. This is a 32-bit Linux ELF file in base64. The effect of the hidden code is running execve("//usr/bin/python", 0, 0). I suggest you don't run random binaries from SE answers. You can, however, use it to test your disassemblers. IDA, Hopper and objdump all fail miserably at first glance, although I imagine you can get IDA to do it correctly somehow.

f0VMRgEBAQAAAAAAAAAAAAIAAwABAAAAYIAECDQAAAAoAQAAAAAAADQAIAABACgAAwACAAEAAAAA
AAAAAIAECACABAgUAQAAFAEAAAUAAAAAEAAAAAAAAAAAAAAAAAAABTHA6wEFUJDrAQWwEOsBBffg
6wEF9+DrAQWJw+sBBbRu6wEFsG/rAQX34+sBBbRo6wEFsHTrAQVQkOsBBbR56wEFsHDrAQX34+sB
BbQv6wEFsG7rAQVQkOsBBbRp6wEFsGLrAQX34+sBBbQv6wEFsHLrAQVQkOsBBbRz6wEFsHXrAQX3
4+sBBbQv6wEFsC/rAQVQkOsBBTHJ6wEF9+HrAQWJ4+sBBbAL6wEFzYDrAelN////AC5zaHN0cnRh
YgAudGV4dAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAACwAAAAEA
AAAGAAAAYIAECGAAAAC0AAAAAAAAAAAAAAAQAAAAAAAAAAEAAAADAAAAAAAAAAAAAAAUAQAAEQAA
AAAAAAAAAAAAAQAAAAAAAAA=