Re: getting around Ken Thompson's compiler Trojan

From: Barry Margolin (barmar@genuity.net)
Date: 01/22/03 

From: Barry Margolin <barmar@genuity.net>
Date: Wed, 22 Jan 2003 22:34:06 GMT

In article <3e2f18f8$0$49105$e4fe514c@news.xs4all.nl>,
Casper H.S. *** <Casper.***@Sun.COM> wrote:
>christopherlmarshall@yahoo.com (Chris Marshall) writes:
>
>>First, write a program to obfuscate the source code of any other program
>>by randomizing the variable and function names, as well as the names
>>of the source code files.
>
>The compiler could recognize itself from the resulting parse
>trees which are abstracted from the names of variables.
>(And the trojaned compiler would need to accept a certain "fuzz"
>or the compiler could never evolve)
>
>No amount of obfuscation based on names of functions/variables
>would work. You would need to restructure the code and don't
>forget to rename that source file too :-)

I'll bet some of the regular winners of the IOCCC could design an
obfuscation algorithm that does more than just cosmetic changes. As a very
simple example, something like

  if (<expr>)

could be transformed to

  int temp1 = 1;
  int temp2;
  if (<expr> + 0 != var1 - (var2 = var1))

The compiler *might* be able to recognize the similarity if it has a good
enough optimizer and does the comparison after this optimization. But I
expect that a determined obfuscator could come up with ways that would
confound any compiler without very good AI. 

-- 
Barry Margolin, barmar@genuity.net
Genuity, Woburn, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.
Quantcast