Re: Making C compiler generate obfuscated code

On Mon, 20 Dec 2010 12:53:51 +0100, torbenm@diku.dk (Torben Fgidius
Mogensen) wrote:


>Equivalence of programs is undecidable, ...


I'm not sure that's true ... at least in theory. Turing equivalence
guarantees that any program can be expressed in the lambda calculus,
and the Church-Rosser theorem proves that two lambda expressions which
reduce to the same expression are equivalent.


In practice, though, I agree that deciding equivalence is intractable.


>... so it is in theory possible to make a program so
>obfuscated that no automatic process can recover the original.


Without meta information, such as exists in Java and .NET binaries, it
is already difficult to accurately reconstruct source for any but the
simplest of programs.


>But what if you know the obfuscation method? Assuming that the
>obfuscation method is polynomic, deobfuscation is at worst NP-hard, so
>it is decidable. But it can be so intractable that it doesn't matter.


I don't think knowing the method will help because any decent
implementation likely will have multiple ways to obfuscate any
particular construct and the selection will be psuedo-random.


George

Return to the comp.compilers page.
Search the comp.compilers archives again.