# Re: Making C compiler generate obfuscated code

## George Neuner <gneuner2@comcast.net>

Tue, 21 Dec 2010 12:25:16 -0500

*From comp.compilers*

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