Why is disassembly not an exact science?

Question

Newbie here.

From Wikipedia

Disassembly is not an exact science: on CISC platforms with variable-width instructions, or in the presence of self-modifying code, it is possible for a single program to have two or more reasonable disassemblies. Determining which instructions would actually be encountered during a run of the program reduces to the proven-unsolvable halting problem.

1. Why is disassembly on CISC it not an exact science? I understand that reassembling disassembled code may produce different, but similar opcodes for the same instruction, but as they are similar, it should not affect the resulting program. And also, if it is not an exact science, i.e. assemble(disassemble(opcode)) != opcode, how can the CPU determine which way to interpret the stream of opcodes?

2. On a side note, does this imply that disassembly on a RISC platform an exact science?

Answer 1

To answer the first question. The biggest problem is that you can't really separate data from code. There are basically two approaches to dissasembly:

1. Linear sweep
2. Recursive traversal

Dissasemblers using linear sweep start at some address and dissasemble instructions one by one until the end, without following jumps or reasoning about the dissasembled code in any way. For example SoftICE and Windbg use linear sweep. This can be a problem, because you don't know when to stop. You don't know where instructions end and where data starts. You have to rely on executable format metadata, like sections sizes, for that. That's what makes it problematic.

On the other hand, recursive traversal algorithms take jumps and calls into consideration, and the dissasembler follows jumps, only dissasembling the code that will actually get executed. For example IDA and OllyDBG use this approach. It has the benefit that it essentially knows what's code and what's data. But it has it's drawbacks, obviously. First, by pure recursive traversal, not all code will be dissasembled. For example, functions that aren't directly referenced, called in runtime by calculating their address will not be spotted. Again, engines have some heuristics to bypass this problem.

Take, for example, a program that jumps back a few instructions, but instead of landing on the beginning of a previously dissasembled and executed instruction, it jumps in the middle of it. How should the dissasembler decide which one to show? Both might be valid, if that was the intention of the coder. The recursive traversal dissasembler will probably show the first dissasembled version, and just mark a jump to the middle of a function. But without you inspecting the bytes in details, it's hard to tell what will actually get executed after the jump.

There are many other examples.

Another big problem with both of these approaches is self modifying code. It just can't be done statically.

The CPU its self doesn't have any of these problem as it's executing code, in other words, it's dynamic.

To answer the second question I don't think this is a problem with CISC architectures only, some of these can be applied to RISCs too.

Answer 2

In addition to the issues described in the previous answers, here's another way in which a program can have more than one disassembly. Consider code that has the following logic (my apologies for the syntax-butchery):

buf = ...some string...
val = read()
if (val == 7) {
  mprotect(buf, ..., PROT_EXEC);    /* make buf executable */
  goto buf;     /* execute buf */
}
else {
  print(buf);
}

In this case, whether buf is code (and therefore should be disassembled) or data (and therefore should not be disassembled) depends on the input. Thus, the program has multiple possible disassemblies. Note that this is because code is fundamentally indistinguishable from data and has nothing to do with RISC vs. CISC.

There's a delightful discussion of how code can be disguised as plausible-looking data in this paper:

J. Mason, S. Small, F. Monrose, G. MacManus. English Shellcode. Proceedings of the 16th ACM Conference on Computer and Communications Security (CCS), Chicago, IL. November 2009. [PDF]

Answer 3

I think what the comment is meant to describe is the fact that on CISC, taking the x86 as an example here, there are several possible reasonable representations of the disassembly. But I'd think this can also in part be said of typical RISC implementations, where - however - the assembler can offer something like a CISC-like mnemonic represented by a different combination of basic (RISC) opcodes.

For example the rep prefix is meaningless on many opcodes and yet has been employed in the past to make it harder for reverse engineers. However, which is the better representation for a human who is ultimately looking at the disassembly? The one with the rep prefix or the one without (which reflects more what the CPU does).

If the disassembler stays true to what it finds, it should include the rep prefix. On the other hand it's the job of the disassembler to make machine code readable for a human. So it makes perfect sense to go that extra mile and make sure that redundant prefixes are removed for brevity. Similarly multi-byte opcodes representing a nop (no operation) could be stripped completely or represented in a way to stand out from the rest (e.g. as IDA does with alignment bytes) or each as nop respectively (for the 1 and the 5 byte version alike).

So from my point of view disassembling machine code is an exact science, since for every opcode there is an exact mnemonic (let's disregard the jne/jnz duality here). Otherwise, as you point out, how would the CPU go about and figure out what to do? However, in order to give a representation to the human reverse engineer, it is sometimes (dare I say often?) post-processed for readability and comprehension. That's where disassemblers and disassemblies vary.

---

Another problem is that in order to follow all possible code paths heuristics have to be used (and it's one of the distinguishing features of a good disassembler). Otherwise it's hard to distinguish data from code. But to my knowledge "CISC" cannot be singled out for that trait, so I'd hold that this isn't the main reason for the comment.

Answer 4

A critical issue in disassembly lies in precisely separating code from data in binary executables. To this end, you will need a static analysis that can precisely determine the targets of indirect jumps (jumps to addresses calculated at run-time). There are several examples of indirect jumps including switch target calculation and vtables in C++.

That type of static analysis, if existed, would be able of solving the Halting Problem which is known to be undecidable. Therefore such static analysis can't exist. Based on that, disassembly tools need to rely on heuristics and/or approximations for determining indirect jumps targets. More details on that can be found in answers to a similar question here Soundness of ARM disassembly. The task of code/data separation gets even harder if binaries where obfuscated and/or have self-modifying code.

Having extracted approximations of code and data from binaries. One needs then to deal with the problem of attaching semantics to them which is also difficult. For example a struct { int i; int j;} would look similar to an int arr [2] when accessed by instructions. Therefore, It's difficult to attach unique semantics to executed code without relying on external information such as debug symbols.

Answer 5

Preliminary Remarks

First of all, we need to agree on what does a correct disassembly of a binary program is. I would propose the following definition:

A correct disassembly of a binary program will give the set of all the possible instructions that can be executed by the program whatever input it takes.

Another way to state it would be to say that we expose the instructions of all the possible executions of the program on every input it can take.

Halting Problem

Here we already can make a parallel with the halting problem on a Turing machine which can be defined as follow (Wikipedia):

The halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running or continue to run forever.

This (apparently) very simple problem has been shown undecidable by Turing, meaning that, even if we can handle a certain amount of cases automatically with a program, some pathological cases will always escape from our program which will fail to tell if yes or no the machine/program will halt on the given input.

And, of course, such pathological cases are infinitely many (so, there is no hope to enumerate them one after one as special cases).

Back to our disassembly problem!

Exploring all the possible paths of a program is indeed undecidable because of the halting problem!

Indeed, a dual way to formulate the halting problem is the accessibility problem where you want to know if there is an input that allow you to reach a specific point of the program. And, knowing if a specific place in memory can be reached by the program and interpreted as an instruction (i.e. the instruction pointer takes the value of this address at some point) is an accessibility problem.

So, disassembly is undecidable.

But, In The Real World ?

I know, I know, this is only Math... Not reality... Most of the obfuscations (voluntary or not) can be worked out and automatically removed from binary code...

Well, this was essentially because people who did these obfuscations were not used to undecidable problems...

Imagine that you insert in your program the computation of an undecidable problem, or even, just something hard and complex enough that will break any automated reasoning applied to it.

To give an example, lets take the Collatz sequence (Wikipedia), this sequence is conjectured to always end at 1 after some time. But, the arithmetic problem behind it is so tremendously complex that this conjecture holds since about one century... This is a perfect opaque predicate to use! Of course, it might be that the proof of such conjecture exists, but this problem is complex enough to start building on it and confuse computer exploring the state space of a program.

In fact, this is the current direction of research in strong obfuscation nowadays... We are almost done with the small tricks that were used before and people start to build things on better grounded problem. Even if we still miss an equivalent of a Shannon (father of the information theory) in matter of software obfuscation to be compared with cryptology.

Final Words

So, we saw that the disassembly problem is strongly linked to the halting problem. And, also, that using highly complex problems might be the next step in modern software obfuscation.

I would just have a final word about the fact that current disassembly tools are probably way behind what we could do if we had to stick with the state of the Art in disassembly techniques. I am always crying in pain when I see how prehistoric are the current tools... but putting all the modern techniques into practice would require so much effort of development and maintenance that nobody seems to be ready to do it (but this is only my humble opinion).