How decompilers work

http://archfinch.com/item/21ace/i-wonder-how-decompilers-work#topcomment

by drx • 15 years ago

82 59 15 years ago

demallien6• 15 years ago

The cynical part of me wants to respond with one word: badly!

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.

ma2rten2• 15 years ago

why do you think that ? I actually would think that just statistics would also work.

demallien6• 15 years ago

Because for two years it was my job to make sure that decompilers didn't work on code generated by my company... It's so easy to throw automatic analysis tools of the track. It's easy to throw humans, and we're way better at this game than automated tools, at least for the time being.

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.

mjb2• 15 years ago

I don't thing strong AI would solve the problem, because one crucial piece of data is lost when the code is compiled: the intention of the programmer. Good code clearly indicates its intended function through structure, most of which does not translate into assembly. When decompiled, this structure needs to be inferred from the assembly, which contains an incomplete view of the required information.

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.

demallien6• 15 years ago

No, strong AI will solve the problem - just ask geohots... The system that is uncrackable has not yet been invented, the best we've been able to do is to make the process slower.

mgkimsal• 15 years ago

"because one crucial piece of data is lost when the code is compiled: the intention of the programmer"

I've worked on many projects where that's lost when the code is written.

drx4• 15 years ago

> The cynical part of me wants to respond with one word: badly!

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).

JoeAltmaier• 15 years ago

Decompiled code can end up looking like high-level assembly code. Like a programmer just learning a new language, using all the habits of their old one.

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.

leon_• 15 years ago

After playing around with the Hexrays C decompiler we got I decided to stay with analyzing disassemblies.

grav1tas7• 15 years ago

Applying AI to a decompilation problem is just like applying AI to a compilation problem. You're taking a potentially nondeterministic approach to a problem that should be formalized and deterministic. I think AI applied to compilers is something to avoid, in general.

hackinthebochs• 15 years ago

>Applying AI to a decompilation problem is just like applying AI to a compilation problem

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.

xcallemjudasx• 15 years ago

As a college student I found this article very easy to read and understand. It gave a simple enough overview with enough detail to explain but not confuse.

shasta9• 15 years ago

Decompilation is undecidable?

   "you cannot write an algorithm that would decompile every possible piece of code"

I'm not sure what claim is actually being made here, but decompilation of any particular compiler is trivially decidable: try every input program until you find the one that produces the observed output.

drx4• 15 years ago

The compiler isn't part of the input. You could get code that was compiled by a compiler not available to you.

When the compiler is part of the input, then yes, the problem is decidable.

shasta9• 15 years ago

I'm still doubtful. I think you're trying to invoke Rice's theorem here, but I don't think it really applies. Compilers don't apply arbitrary transformations that preserve behavior - they only employ transformations that are understood to preserve behavior.

demallien6• 15 years ago

I don't think it is decidable even when you have the compiler available to you - what happens if I decide to insert a bunch of assembly code in my gcc-compiled program using the gcc embedded assembly extensions? How do I decide that a particular sequence of generated op-codes is actually impossible from pure C code, and hence must have been assembly in the original program?

nandemo2• 15 years ago

The problem only makes sense if the compiler is fixed. Otherwise, it's trivial: for any input x I can say the source code is x. It's source code written in a programming language called MachineLanguage. The compiler is called cat.

peti4• 15 years ago

The set of all possible inputs is infinite: Halting Problem.

grav1tas7• 15 years ago

The set of all possible inputs for a compiler is infinite, too. Does that mean that compilers are all harangued by the halting problem as well? Nope. Having an infinite number of possible inputs (infinite input set size) does not prevent you from showing that a program can actually halt. I think most compilers are written in a way that can be shown to halt, as well.

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.

grav1tas7• 15 years ago

It depends on what you want from decompilation. Decompilation by its basic nature is just as decideable as compilation is. It's a translation from one language to another in addition to semantics-preserving translations. Now what a lot of people seem to want from a decompiler that makes them intractable is a guarantee that the output source will look just like the source used to compile the source program for the decompiler.

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.

shasta9• 15 years ago

We typically reserve the term "undecidable" for the case where there is a mathematical function we are interested in, but it isn't computable by any algorithm. Inverting a many-to-one function is just impossible.

barrkel2• 15 years ago

That's not what decidable means.

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.

shasta9• 15 years ago

Self-modifying code doesn't change my argument (see my response to kenjackson for my understanding of the problem) so long as it was produced by the compiler.

kenjackson• 15 years ago

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!"...?

shasta9• 15 years ago

You're right. I initially took the problem to be "given this (specific) compiler output, determine the corresponding compiler input." That seems like a reasonable interpretation of "decompiling". If the problem is instead "determine whether this chunk of machine code could have come from this compiler", then my proposed algorithm obviously doesn't work.

T-R• 15 years ago

Have you tried applying any of this to (segments of) 68k binaries?

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

drx4• 15 years ago

I've started writing a 68k ASM module a while ago but I never finished.

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.

drx4• 15 years ago

As I can't edit my post any more, and you don't have an email address in your profile, I will double post.

> Do you know of any other good resources?

The thesis has many references, I would start with that.

How decompilers work

Related Stories