Jump into the instructions, is it a case `objdump` can't handle?

Question

So basically I am using objdump on 32 bit x86 Linux, disassembling some static linked binary compiled by gcc

In the disassembled asm code, I find this:

 80ade23:       74 01                   je     0x80ade26
 80ade25:       f0 0f c1 16             lock xadd %edx,(%esi) // lock
 80ade29:       89 54 24 14             mov    %edx,0x14(%esp)
 80ade2d:       8b 54 24 14             mov    0x14(%esp),%edx
 80ade31:       3b 15 f0 0e 0f 08       cmp    0x80f0ef0,%edx
 80ade37:       73 75                   jae    0x80adeae
 80ade39:       65 83 3d 0c 00 00 00    cmpl   $0x0,%gs:0xc
 80ade40:       00
 80ade41:       74 01                   je     0x80ade44
 80ade43:       f0 0f c1 0d dc 0e 0f    lock xadd %ecx,0x80f0edc // lock
 80ade4a:       08

So basically, in my understanding, lock is a prefix of x86 asm opcode, which is legal here.

and it seems that je jump into the position right after lock.

so here are my questions:

1. Is the disassemble results from objdump correct? It is rare to see objdump generate this kind of "jump into instructions" asm code..(anyway, I am new to reverse engineering, so... :) )

2. Then how to adjust it to make it re-assemblable?

I tried to change it in this way and re-assemble it using gcc, it can pass the assemble process, but basically I really don't know if it is a correct way or not.

 je     S_0x80ade26
 lock   
 S_0x80ade26: xadd %edx,(%esi) // lock

Answer 1

I wouldn't go that far and state that the output provided by objdump isn't correct. True, Linear Sweep doesn't handle data properly, and jump tables & shellcodes are usually a source of disassembly errors. But still, this isn't an error.

If you take a closer look at your code you'll notice you have je. Meaning, the jump is taken only if the previous instruction - which is certainly a cmp or a test - returns true. The x86 ISA (instruction set) allows to jump in the middle of instructions, or a byte stream if you like. And this is sometimes used to avoid certain prefixes like rep, ..., and in your case a lock.

I'm 100% sure the output provided is correct and that the programmer (or the compiler) used this trick to avoid unnecessary additional code.

Answer 2

In fact, objdump use the linear sweep algorithm to disassemble executable files. It means that it disassembles instructions one after one. Like this:

1. First it goes to the entry point and disassemble the first instruction (and get its size):

   4028c0:       41 57                   push   %r15
   

2. Then, knowing the size of the previous instruction, it updates the current address to the next instruction and disassemble it (and get its size again):

   4028c2:       41 56                   push   %r14
   

3. And, it iterates again and again (go back to 2) until it reaches the end of the current section:

   4028c4:       41 55                   push   %r13
   4028c6:       41 54                   push   %r12
   4028c8:       55                      push   %rbp
   4028c9:       48 89 f5                mov    %rsi,%rbp
   4028cc:       53                      push   %rbx
   ...
   

objdump implementation add only one small increment on this simple algorithm, it will start on every symbols even if it appear in the middle of the current disassembled instruction. Meaning that you may have the following case (I encountered it while studying an obfuscated software):

   4028c0:       41 57                   push   %r15
   4028c2:       41 56                   push   %r14
   4028c4:       41 55                   push   %r13
   4028c6:       41 54                   push   %r12
   4028c8:       55                      push   %rbp
   4028c9:       48 89 f5                mov    %rsi,%rbp
   4028cc:       48 85 c0                test   %rax,%rax

00000000004028cd <.f668>:
   4028cd:       85 c0                   test   %eax,%eax
   4028cf:       53                      push   %rbx
   ...

The disassembler first disassembled 4028cc as an amd64 instruction, but a symbol was at 4028cd. So, the algorithm reseted to this value and started over from there.

Finally, be aware that the linear sweep algorithm is widely known as being incorrect. It may be mislead very easily. Its main problem is that it does not take into account the semantics of all the instructions, so when reaching a dynamic jump (jmp %rax), the algorithm won't be able to follow the execution flow. Of course, there are many other ways to mislead this algorithm, I won't try to be exhaustive here on all these techniques (note that recursive traversal is not really better).

To get back to your original questions:

1. The linear sweep algorithm cannot track the execution flow of a program. And won't be able to jump over a data if it lays in the middle of instructions. Yet, objdump may incidentally be correct when a symbol point to the instruction where to jump in the middle of the previous instruction (see the case I described before).

2. To obtain a proper disassembly of this program, there is no hope with objdump. But, you can use gdb and collect an execution trace by instrumenting it though a Python script. Also, other disassembler won't be tricked by this simple layout. You may try radare or, as Benny suggested, IDAPro. I can also advertise a bit my own tool which is cfgrecovery from the Insight framework (but it's a bit overkilling for such a simple trick).

Answer 3

I think that what you call "jump into instructions" could be an anti-static analysis technique called disassembly desynchronization, which interleaves data bytes with code in order to confuse the disassembler. This technique and others are explained in chapter 21 (Obfuscated Code Analysis) of the IDA Pro book.

Using IDA Pro you can obtain the correct disassembly of your code if you:

1. Open the binary with IDA (Free or Pro)

2. Put your cursor on one problematic line of code, which in your case is at addresses: 80ade25 and 80ade43

   lock xadd %edx,(%esi) // lock
   ...    
   lock xadd %ecx,0x80f0edc // lock
   

3. Click the Edit menu of IDA and then select Undefine

4. Now put your cursor at address where the jump instruction points to, which in your case is 0x80ade26 and80ade44

5. Click the Edit menu of IDA again and select Code this time

Note that this anti-static analysis technique is applied twice in your code. So you need to apply steps 2-5 twice.

UPDATE: However, in your objdump output there is no disassembly desynchronization as Peter Ferrie pointed out in the comments below. The jump into instruction is a means of improving performance. However, I leave this answer as a hint for anyone who stumbles upon your question and whose disassembly is actually suffering from desynchronization.