Program Obfuscation

Program-Transformation.Org: The Program Transformation Wiki

Obfuscation is a ProgramTransformation that makes a program harder to understand by renaming variables, inserting dead code, etc. Obfuscation is done to hide the business rules embedded in software by making it harder to reverse engineer the program.

The main ideas seem to revolve around control-flow and data-flow "encoding". The real code is padded with "decoy" code, and simple operations (like adding and subtracting) are hidden behind "transformed variables". For example, by subtracting two polynomials, you can effectively perform an addition. It is claimed that this sort of thing becomes very difficult even for the original author to reverse engineer, or the writers of the encoding programs.

It could turn out that this technology will render decompilation ineffective. My opinion (and it's not very well informed, I admit) is that present obfuscation and tamper resistance is largely ineffective. My guess is that it will stay that way, but only time will tell. To get a flavour of what it's about, search for "tamper resistant software", or start with these sites:

Gregory Wroblewski's work seems to have a good summary of work on the obfuscation of binary programs. His web page is http://www.mysz.org/publications.html.
Christian Collberg is a pioneer in obfuscation. See his page titled Robust Obfuscation.
There are many obfuscators for Java. See for example DashO.
PreEmptive Solutions has a product called Dotfuscator for CLI/MSIL/.NET, a light version of which is distributed with Microsoft® Visual Studio® .NET.

I came across a paper recently that claims that general program obfuscation is impossible, as reported by this paper:

B. Barak, O. Goldreich, R. Impagliazzo, S. Rudich, A. Sahai, S. Vadhan, and K. Yang. On the (Im)possibility of Obfuscating Programs. In Advances in Cryptology (CRYPTO'01), volume 2139 of Lecture Notes in Computer Science, pp 1-18, August 2001.