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 ?
What is a correct disassembler?
obfuscation;disassembly;static analysis
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 DefinitionsStart 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 RecoveryInstead, 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.