6 ms·

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 m

by shasta 16y 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.

drx 16y 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.
- shasta 16y 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.
- demallien 16y 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?
  - peti 16y ago
    In that case, the GCC extension is part of the input language (in a broader sense). Still, your example clearly shows the difficulties involved in practice.
- nandemo 16y 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.
  - shasta 16y ago
    I think he had in mind that the language is fixed, but not the compiler.
    - nandemo 16y ago
      In this context, "programming language" and compiler are really the same thing: a mapping from source code to object code. 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.
peti 16y ago
The set of all possible inputs is infinite: Halting Problem.
- grav1tas 16y 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.
  - burgerbrain 16y 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? " 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)
    - grav1tas 16y ago
      The point about the macros being Turing Complete is trivial in this instance because if you wrote a macro that never terminated, you'd never compile anything do decompile ;-).
      - burgerbrain 16y ago
        No, you are incorrect about the point being trivial. First off, the macros used in the original program will of course terminate, but if you simply "try every input to the compiler" like is being suggested, you will be attempting to compile any number of non-terminating macros (and you will of course not know which terminate and which do not (Halting Problem)). The point is that "compilers terminate for every input" is trivially false.
grav1tas 16y 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.
- shasta 16y 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.
Alistra 16y ago
Of course it's undecidable, even with a compiler on the input, you can write a series of programs like: main() { return 1; } and main() { return 1+1-1; } and main() { return 1+2-2; } and so on. So there is an infinite sequence of programs, that compile into the same binary, and only one is the right source code.
barrkel 16y 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.
- shasta 16y 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.
  - barrkel 16y ago
    Well, you have no guarantee that a sane compiler was used, obfuscation and encryption may also play a part. Things worth reverse engineering are often convoluted in such ways.
kenjackson 16y ago
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. 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!"...?
- shasta 16y 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.
  - Someone 16y ago
    Obviously? 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)
    - shasta 16y ago
      Well, I think "obviously" was right, since my algorithm would never terminate if no source is ever found that matches the generated binary (there are infinitely many possible programs for most idealized languages). 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.

by shasta 16y ago

drx 16y 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.

shasta 16y 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.
demallien 16y 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?
- peti 16y ago
  In that case, the GCC extension is part of the input language (in a broader sense). Still, your example clearly shows the difficulties involved in practice.
nandemo 16y 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.
- shasta 16y ago
  I think he had in mind that the language is fixed, but not the compiler.
  - nandemo 16y ago
    In this context, "programming language" and compiler are really the same thing: a mapping from source code to object code. 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.

peti 16y ago

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

grav1tas 16y 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.
- burgerbrain 16y 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? " 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)
  - grav1tas 16y ago
    The point about the macros being Turing Complete is trivial in this instance because if you wrote a macro that never terminated, you'd never compile anything do decompile ;-).
    - burgerbrain 16y ago
      No, you are incorrect about the point being trivial. First off, the macros used in the original program will of course terminate, but if you simply "try every input to the compiler" like is being suggested, you will be attempting to compile any number of non-terminating macros (and you will of course not know which terminate and which do not (Halting Problem)). The point is that "compilers terminate for every input" is trivially false.

grav1tas 16y 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.

shasta 16y 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.

Alistra 16y ago

Of course it's undecidable, even with a compiler on the input, you can write a series of programs like: main() { return 1; } and main() { return 1+1-1; } and main() { return 1+2-2; } and so on. So there is an infinite sequence of programs, that compile into the same binary, and only one is the right source code.

barrkel 16y 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.

shasta 16y 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.
- barrkel 16y ago
  Well, you have no guarantee that a sane compiler was used, obfuscation and encryption may also play a part. Things worth reverse engineering are often convoluted in such ways.

kenjackson 16y ago

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

shasta 16y 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.
- Someone 16y ago
  Obviously? 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)
  - shasta 16y ago
    Well, I think "obviously" was right, since my algorithm would never terminate if no source is ever found that matches the generated binary (there are infinitely many possible programs for most idealized languages). 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.