How decompilers work
archfinch.com
archfinch.com
But I've spent enough time hand-reversing code to know that that doesn't do justice to the work done by decompiler writers, it's just that it's a problem that requires strong AI to do it properly.
To give you an idea of how easy it is, if you want the decompiler to drop the ball on a for-loop, all you need to do is something simple like increment by two and then decrement by one at the start of the loop body... The tool might be looking for the use of an INC instruction, but because you increment by two, the compiler generates an ADD... and now your tool doesn't know how to recognise the loop.
Just because they exist doesn't mean what they provide is of any practical value, as you said it yourself they decompile badly.
From the Wikipedia article: "As of 30 June 2009, the mandatory pre-installation of the Green Dam software on new computers has been delayed to an undetermined date."
This missing information includes, but is not limited to, the extra information that the programmer put in deliberately: class names, variable names, comments, etc. They also encoded a large number of assumptions about typical program inputs, the execution environment, expected and unexpected branches, chunks of logic (classes, functions, etc) into the code. With all this lost, even a strong AI would not be able to piece together the original program.
Instead, I think, the best that could be hoped for is a sort of uncanny-valley zombie of the original code. Certainly better than nothing, but totally not a replacement for your dead wife.
(1) is not easy, but is becoming easier. (2) is still a long way off, and isn't solvable without a good understanding of the domain the original code was written for.
Both AIs and Humans both attempt to ape some fundamental truism or formalism about logic to compile and decompile programs. To me, it's better off knowing what those formalisms are than aping them with intelligent behavior, though finding formalisms is hard so sometimes we make do.
I've worked on many projects where that's lost when the code is written.
You are right.
Decompiling seems hopeless when you look at the problem. Which is one of the reasons why I wrote my decompiler -- to see what can be done.
That also depends on what problem you think decompilers are to solve. Decompilers are somewhat good at telling you additional information about the original structure of the program. They suck at recovering the original source code (which, with enough optimization and mangling, is impossible).
You have to call decompiling a success if the result executes the same algorithm. Much more than that is very hard.
I wrote a similar conversion tool - PL/M to C - years ago. It did quite a good job, because it had semantic clues (not to mention the original variable names). And even that can be done badly - the 1st pass result folks called "CL/M" because it was obviously not written by a C programmer.
I think they're very different. Compilation strips semantic information from code. Decompilation attempts to recover semantic information from program structure and, in the AI case, domain knowledge. They are fundamentally different processes.
Intent is gone from compiled code. You can not formally reconstruct it. All you could formally get are reasonable guesses, and actually that's what the decompiler is giving you; it is not hard to interpret its output as very precisely vague on exactly the points it does not know about.
You mentioned that a decompiler would have been only slightly useful for older games written in C/C++; is flow analysis not helpful in practice for simplifying code that was originally hand-coded in assembly?
Edit1: Thanks for the link to the paper[1], by the way. Do you know of any other good resources?
Edit2: Nevermind, I see you have them in github[2]. Thanks again.
[1] http://www.ci.tuwien.ac.at/~grill/decompilation_thesis.pdf [2] https://github.com/drx/ocd
Hand-coded assembly code is better in that it's less optimized and mangled. But worse in that it has much less structure -- I can't convert ASM code into C. Each programmer has its own way of implementing certain programming patterns, etc.
IDA Pro is actually quite good at flow analysis of ASM code.
> Do you know of any other good resources?
The thesis has many references, I would start with that.
"you cannot write an algorithm that would decompile every possible piece of code"
When the compiler is part of the input, then yes, the problem is decidable.
In any case, the problem with your original argument is not the choice of compiler, it's that your algorithm migh not halt, as explained by kenjackson.
The Halting Problem does apply in the general case, but if you carve up your programs and reason about them, you can still show that you can have a halter. The Halting Problem just states that there does not exist a method that will take an arbitrary program and show it to be a halter.
No, because unlike this "try all possible inputs" plan for decompilers, compilers only operate on any particular single input.
"I think most compilers are written in a way that can be shown to halt, as well."
Not C++ compilers (Turing Complete macros) or Lisp dialects (same issue, but even moreso)
The point is that "compilers terminate for every input" is trivially false.
I agree with your point in a sister thread that decidable doesn't imply practical, but the claim of the original article was undecidable, which has a technical meaning.
I think you may be right about the point your trying to make, but the point I'm making is that your point covers a negligible section of programs that the author would hope to analyze, so it doesn't matter.
The parent comment's suggestion was: (1) for each possible input program, (1.a) compile it, and (1.b) check if the result equals the given compiled code.
Agreed, steps (1.a) and (1.b) terminate deterministically (for a given compiler).
However, the search space for this search procedure is infinite.
Similarly, it would be impossible, in general, to exhaustively test every possible input of a compiler.
And while not strictly related to "is it decidable", in the real world we have to keep in mind the complexity of the solution. The presence of the naive solution for a particular language doesn't say much about how well we can* actually do it. Is the problem actually decidable within the confines of the physical observable universe for real world inputs?
If the compiler did not halt, then we don't have anything to disassemble in the first place.
Formally, it is obvious that a diagonalization-based search will eventually find a correct input, regardless of the halting status of any given input. In practice, none of this matters very much.
You are however correct that this can be circumvented with diagonalization.
Program1 -> Compiler -> BinProg1 (compilation)
BinProg1 -> Decompiler -> Program2 (decompilation)
Even if the source language of the Compiler and the target language of the decompiler are the same, you're usually still screwed because the compiler is going to manipulate your program to optimize it or fit it onto your target architecture. The result is going to be a program that looks way more general case than your original program.
Is this undecideable? No way.
The code could be self-modifying. Figuring out what the code turns into, to generate a meaningful translation of it, turns into the Halting problem pretty quickly. At the limit, the best you can do is produce assembly output, and even that may be problematic if there are ambiguities in the encoding but the program uses code as data or vice versa.
How do you know that you'll find a program that works? What if the program wasn't generated by the compiler and that compiler can't generate that particular sequence of instructions? At what point do you know, in general, "this instruction sequence isn't derivable from this compiler!"...?
Iterating over all possible input 'programs' (including buggy ones) is easy, even if the language allows for multiple input files of different types.
=> if you can give an upper bound for the length of the source code of a binary of size N, you are all set. I do not see how to proof that such an upper bound exists, but it seems fairly reasonable that one must exist. I cannot really think of any real-world compiler that would need, say, more than a GB of source code for every bit of output (it is easy to design such a language, but it would be quite esoteric)
For your idea of modifying my algorithm to bail after some number of inputs have been checked, clearly there does exist a bound on the source length necessary to generate all possible binaries of size N, since there are only finitely many such binaries (and thus they can be produced by finitely many sources). But to turn this into an algorithm, you'd need a computable bound. For a language like C, I think such a bound probably exists and is a reasonable function of the input size. For a language like Coq, though, I doubt the bound would be computable. Basically, I think that there are programs that work for reasons that are very difficult to prove.
Also, I think we're far enough from practical that appeals to the real world are somewhat silly. Either we're interested in understanding the theoretical situation, in which case lack of real world examples doesn't help, or we're interested in practical decompilation, in which case this whole conversation is stupid.