10

A disassembler is supposed to produce a human readable representation of the binary program. But the most well known techniques: linear sweep and recursive traversal (see this comment for more) are known to be easily mislead by specific tricks. Once tricked, they will output code that will never be executed by the real program.

Thought there exists new techniques and new tools more concerned about correctness (eg Jakstab, McVeto, ...), the notion of correctness of the output has never been properly defined, up to my knowledge, for disassemblers.

What would be a good definition of a disassembler, what would be a proper definition of correctness for its output and how would you classify the existing disassemblers in regard of this definition of correction ?

Community
  • 1
perror
  • 19,083
  • 29
  • 87
  • 150
  • 4
    It seems to me you are practially answering yourself in the question. In addition to that your metric of correctness is probably entirely subjective. Since you can't do an exact decompilation what you do from there just depends. – cb88 Mar 25 '13 at 17:17
  • This appears more like a blog post than a question :) – asheeshr Mar 25 '13 at 17:31
  • 1
    Yes, please split it into a question and answer. You can answer your own questions, that's not a problem. Also, question at the end does not match the title. – Igor Skochinsky Mar 25 '13 at 18:07
  • @Emmanuel: please split the answer from the question, before it gets closed off. – 0xC0000022L Mar 25 '13 at 18:23
  • done (and sorry for the mess). Hopefully there will be a better answer... – perror Mar 25 '13 at 18:29
  • Still, this is not a good fit for Q&A. It's subjective. Voting to close. –  Mar 25 '13 at 18:43
  • I would say that the two questions you are asking ("What would be a good definition of a disassembler" and "what would be a proper definition of correctness for its output"), might fit better at cs.se? – Jesper.Reenberg Mar 26 '13 at 08:47
  • @Jesper: Yes, you summed up the two questions that I failed to ask. But, as a disassembler is really a corner stone in software reverse engineering, why shouldn't it be placed here ? – perror Mar 26 '13 at 09:28
  • @Emmanuel, My impression of most RE people (at least on the software side, beware of colored opinions) is that they are self thought and damn good at what they do. However, because of this they are not well founded in academics and would have trouble giving out a proper definition of correctness. Here I see more emphasis on the definition and correctness parts, and the disassembler part just being an example of what to define correctness of, etc. This should turn into a debate or be seen as an attempt at smearing any people. – Jesper.Reenberg Mar 26 '13 at 09:41
  • @Jesper, you are probably right (even it was not my prior intent at all). Lets keep this question closed, then. I agree with this decision. – perror Mar 26 '13 at 09:45
  • I forgot some negations. Obviously I intended to write something along the lines: "This is not intended to turn into a debate or should be seen as an attempt at smearing any people". – Jesper.Reenberg Mar 26 '13 at 09:49

2 Answers2

17

I'm the author of rdis and have put a bit of thought into this problem. I recommend taking a look at my blog if you have more questions after this.

I would also refer you to Andrew Ruef's blog post Binary Analysis Isn't. The key take away is we often attempt to understand our programs with the context of compilers, and not necessarily as just a continuum of instructions. He coins the term, "Compiler Output Analysis," which is more or less what we attempt to achieve in our disassemblers.

Terms and Definitions

Start over with your definitions of terms common to disassembly. We have data, or state, which can be composed of memory, registers, all the good stuff. We have code, which is a label we apply to data we expect the machine to execute (we'll come back to code). We have a program, which is an algorithm encoded in the data which, when interpreted by a machine, causes the data to be manipulated in a certain way. We have a machine which is a mapping of one state to another. We have instructions which, for our purposes, exist at a single point in time and are composed of specific pieces of data which control the way our machine manipulates data.

Often times we believe our goal is the transformation of code, the data we expect to be executed by the machine, into a readable disassembly. I believe we do this because of our division of program analysis between Control-Flow Analysis (Code) and Data-Flow Analysis (Data). In program analysis, our code is state-less, and our data has state. In reality, our code is just data, it all has state.

Program Recovery

Instead, our goal should be the recovery of the program by observation or prediction of the machine. In other words, we are not interested in transforming data into a readable disassembly, but in discovering the instructions which will be interpreted by our machine.

Additionally, our representation of the program should be stored separately from our stateless representation of data, which is usually the initial memory layout given to us by our executable file (ELF/PE/MACH-O/etc). Really, it should be stored in a directed graph. When I see a linear representation of memory with multiple locations labelled as instructions, I shutter. You don't know yet!

I believe the next step in disassembly involves processes which make better predictions about machines by allowing for changes in state during the disassembly process. I believe we will have both emulated disassembly and abstract disassembly. Some people are, more or less, doing this already, though I am unsure if anyone is doing it expressly for the purpose of creating usable and understandable "program recoveries".

You can see an example of the difference between a recursive disassembly of a program and an emulated disassembly of a program here.

What is a correct disassembler?

So, now to answer your question, "What is a correct disassembler?" I believe a correct disassembler is one which clearly defines the behavior of its program recovery process and adheres to this definition. Once we get disassemblers which do THAT, the better disassemblers will be the ones whose definitions best predict the behavior of the machines for which they recover programs.

endeavor
  • 366
  • 2
  • 5
2

What is a disassembler ?

I would decompose a disassembler into two parts, first a decoder that takes an hexadecimal code and output an assembly instruction (possibly with the length of the decoded instruction if the assembly language has variable length instructions). And, then a disassembly algorithm that will use the decoder to browse through the executable code.

The overall goal of a disassembler, in my humble opinion, would be to recover all the possible runs that can be built from a given executable and to present it in a concise and human readable format.

Problems in disassembly

There are many problems that a disassembler can encounter when disassembling a binary program. One of the most difficult would be to deal with self-modifying code. Indeed, til now there is no real good human readable representation for self-modifying program. So, all disassemblers when facing a self-modifying code fail miserably to output something clearly understandable.

The second problem that can stop a disassembler is that from time to time the binary program jump to another place to execute some code (function calls, if-then-else, switches, ...). And, if most of these jumps are static (the address where to jump is statically coded into the code), there are some jumps that depends on the context of the execution. We usually call these jumps dynamic jumps (opposed to static jumps). These dynamic jumps force the disassembler to track not only the syntax of the instructions but also their semantics in order to not be lost when encountering it.

Finally a last problem is that not all the binary programs can be assumed to follow a precise ABI (Application Binary Interface), defining a precise interface for function calls or a way to handle data-structures. Indeed, some binary programs are either crafted by hand or with a modified compiler that will try to mislead disassemblers. Therefore, the disassembler will have to recognize a function call by its semantics and not only by its syntax.

Correctness of a disassembler

As we stated previously, the ultimate goal of a disassembler is to rebuild all the possible traces of execution from a binary program. Of course, most of the time this is extremely difficult, so we can define three types of disassemblers:

  • Exact disassembler : Hypothetically, it should issue all the correct traces that can be run on the binary program, and only these traces.
  • Over-approximated disassembler : The output of this one should include all the possible traces, possibly with some extra ones.
  • Under-approximated disassembler : The output of this one should be included into the possible traces but not provide any infeasible ones.

Existing techniques and where to classify them

For now, the two most popular techniques are linear sweep and recursive traversal (see here for more details).

Both are quite widely used in the wild by numerous reverse-engineers. But, actually, none of these technique is neither exact, nor an over-approximation, nor an under-approximation. They both output something which is none of what we just seen before (sometime they will invent a path that will never be reached, and sometime they will forget about another one).

More advanced techniques with more concern about the correctness exists (eg Jakstab, McVeto, McVeto on self-modifying code, ...), but the quest for exact recovery is surely out of reach.

So, choosing between under and over-approximation depends of what will be the usage of the disassembler output.

Community
  • 1
perror
  • 19,083
  • 29
  • 87
  • 150