Re: Making C compiler generate obfuscated code

George Neuner <gneuner2@comcast.net>
Tue, 21 Dec 2010 12:25:16 -0500

          From comp.compilers

Related articles
[7 earlier articles]
Re: Making C compiler generate obfuscated code martin@gkc.org.uk (Martin Ward) (2010-12-17)
Re: Making C compiler generate obfuscated code gah@ugcs.caltech.edu (glen herrmannsfeldt) (2010-12-18)
Re: Making C compiler generate obfuscated code rpw3@rpw3.org (2010-12-18)
Re: Making C compiler generate obfuscated code DrDiettrich1@aol.com (Hans-Peter Diettrich) (2010-12-16)
Re: Making C compiler generate obfuscated code torbenm@diku.dk (2010-12-20)
Re: Making C compiler generate obfuscated code gneuner2@comcast.net (George Neuner) (2010-12-21)
Re: Making C compiler generate obfuscated code gneuner2@comcast.net (George Neuner) (2010-12-21)
Re: Making C compiler generate obfuscated code walter@bytecraft.com (Walter Banks) (2010-12-21)
Re: Making C compiler generate obfuscated code gah@ugcs.caltech.edu (glen herrmannsfeldt) (2010-12-21)
Re: Making C compiler generate obfuscated code martin@gkc.org.uk (Martin Ward) (2010-12-22)
Re: Making C compiler generate obfuscated code DrDiettrich1@aol.com (Hans-Peter Diettrich) (2010-12-22)
Re: Making C compiler generate obfuscated code gneuner2@comcast.net (George Neuner) (2010-12-23)
Re: Making C compiler generate obfuscated code torbenm@diku.dk (2011-01-04)
[1 later articles]
| List of all articles for this month |

From: George Neuner <gneuner2@comcast.net>
Newsgroups: comp.compilers
Date: Tue, 21 Dec 2010 12:25:16 -0500
Organization: A noiseless patient Spider
References: 10-12-017 10-12-019 10-12-023 10-12-030 10-12-033
Keywords: C, code
Posted-Date: 21 Dec 2010 22:32:14 EST

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


Post a followup to this message

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