how can the processor instruction set be identified solely by examining a binary image? [duplicate]

Question

Constraints:

I am doing reverse engineering of a binary firmware image of unknown provenance, which operates on a device that is not physically accessible to me. That is, I can't take apart the device, don't have even block diagrams for its function, and have no ability to identify the microprocessor by visual inspection or by asking the creator of the object. Literally the only thing available is the binary image.

The Question:

My question is: given those constraints what tools or theoretical approaches could be employed to identify the processor's instruction set by examining the binary?

Research so far:

I have, of course, attempted to use disassemblers for various popular ISAs such as ARM, x86 and MIPS. I have also done a literature search for research papers but haven't turned up anything at all.

Ideally, what I'd like is a tool that would examine the binary and then report something like "75% probability that this is code for a Renesas M16C."

Answer 1

This is extremely hard to perform. Given no initial information, you'll have to go through it heuristically using pattern matching & probabilistic approximations.

I've been working for two years on such a tool (I have written tons of helpful tools destined to be used by myself for work & which I plan to share someday, not soon though). It works, but it's not mature enough to be thrown in the jungle. My approach is as follows : detect binary format data structures if possible, disassemble a chunk of binary code by using multiple instruction set encoding (ARM, x86, MIPS, ...) and then heuristically assess (using bads & some other stuff :]) which is closer ...

But interestingly, your question has been asked here before and an interesting approach was given and considered an answer. It uses a similar approach as in biology to identify the phylogenetic distance.

Answer 2

This presentation offers one approach.

Title: Reverse engineering of binary programs for custom virtual machines

Authors: Alexander Chernov and Katerina Troshina

• Initial markup of the binary program. Identification of data sections and code sections. Prior information about the purpose of the program or even some documentation hints may be used. At this step the entry point to the code (or several entry points) are identified.
• Reconstruction of subroutine structure by identification of the subroutine borders. The subroutine return (RET) instruction is identified. It is naturally to expect that the last instruction in the code segment would be the return instruction. RET instruction normally separates subroutines, so we may expect, that CALL instruction should pass the control right after RET instruction in many (or even most) cases.
• Identification of the unconditional jump (JMP) instruction using the assumption, that code execution starts at some fixed address.
• Identification of call instruction. Call instructions are similar to unconditional jumps. By investigation of initialization code several candidates for the CALL instruction can be identified, and the one candidate remained after validation on the whole code.
• Recovering of absolute and relative jumps and call by looking at the bit encoding of instruction and checking whether it could be an offset relative to the next instruction word. This way relative jumps, calls and candidates for conditional jumps were identified.
• Identification of memory load and store instruction by observing load-store patterns for memory-memory copy operations.
• Observations on the virtual machine register structure and register width. How many registers this VM probably has and how wide are they.
• Observations on the arithmetics and logics operation by pairing with the identified conditional jumps.