Re:How decompilers work
by barrkel on Thursday May 05, 2011 @12:01PM
(#2517839)
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.
Re:How decompilers work
by shasta on Thursday May 05, 2011 @12:17PM
(#2517901)
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.
Re:How decompilers work
by barrkel on Friday May 06, 2011 @03:00AM
(#2520226)
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.
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.