Is it possible to decode x86-64 instructions in reverse?

Question

I was wondering if it is possible to decode x86-64 instructions in reverse?

I need this for a runtime dissembler. Users can point to a random location in memory and then should be able to scroll upwards and see what instructions came before the specified address.

I want to do this by reverse decoding.

Answer 1

The basic format of x86 instructions is like this

Modern CPUs can support VEX and EVEX prefixes. In x86-64 there might also be the REX prefix at the beginning

Looking at the format it can easily be seen that the instructions aren't palindromes and you can't read from the end.

---

Regarding determining which instruction an arbitrary address belongs to, unfortunately it can't be done either, because x86 instructions are not self-synchronizable, and (generally) not aligned. You have to know exactly the begin of an instruction, otherwise the instruction will be decoded differently.

You can even give addresses that actually contain data and the CPU/disassembler will just decode those as code, because no one knows what those bytes actually mean. Jumping into the middle of instructions is often used for code obfuscation. The technique has also been applied for code size saving in the past, because a byte can be reused and has different meanings depending on which instruction it belongs to

• Jump into the middle of instruction - in IA-32
• Why are disassembled data becoming instructions?
• Designing an instruction sequence so that it does something else if decoded with an offset
• What is "overlapping instructions" obfuscation?
• Jump into the instructions, is it a case objdump can't handle?
• What is the reason for this method to call itself?

That said, it might be possible to guess in many cases since functions and loops are often aligned to 16 or 32 bytes, with NOPs padding around

Answer 2

An x86 instruction stream is not self-synchronizing, and can only be unambiguously decoded forward. You need to know a valid start-point to decode. The last byte of an immediate can be a 0x90 which decodes as a nop, or in general a 4-byte immediate or displacement can have byte-sequences that are valid instructions, or whatever other overlap possibilities with ModRM/SIB bytes looking like opcodes.

If you decode forward in code that isn't intentionally obfuscated, you often get back into sync with the "correct" instruction boundaries, so you might try remembering the instruction boundaries as a known-good point, and check that a decoding from a backwards-step candidate start address has an instruction boundary at your known-good point.

IDK if you could get more clever about finding more known-good points going backwards which further candidates also have to agree with.

Be sure to highlight backwards-decoded instructions for the user in red or gray or something, so they know it's not guaranteed reliable.

---

Another alternative is to require function symbols (extern functions, or any function with debug info).

GDB doesn't allow you to scroll upward (in layout reg mode), unless you're inside a function that it knows the start address. Then I guess it decodes from the function start address so it knows instruction boundaries when it gets to the part that fits in the window.

If you want to go backwards, you have to disas 0x12345, +16 to start decoding from there. Then you can scroll down, but if you get the insn boundary wrong you get garbage.