Ken Thompson's Reflections on Trusting Trust

Posted Feb 27, 2009 23:41 UTC (Fri) by JoeBuck (subscriber, #2330)
In reply to: Ken Thompson's Reflections on Trusting Trust by pr1268
Parent article: LinuxDNA Supercharges Linux with the Intel C/C++ Compiler (Linux Journal)

Sigh. Not again.

GCC is built with a three-stage bootstrap procedure. First the compiler is built with some C compiler, that might be an older GCC, or might be a different compiler entirely. The result is "stage 1". Next, GCC is built again, by the "stage 1" compiler, to produce "stage 2". Finally, GCC is built with "stage 2" and the result is "stage 3". We then check to see whether "stage 2" is bit-for-bit identical (other than date stamps in object files) with "stage 3". If it isn't, we report a failure. The key is that this process is designed to remove any dependence in the final compiler from the initial compiler. This check is run every time gcc is built from source, and every developer must run this check before any patch is acceptable (plus all the other regressions, of course).

Now, suppose that you suspect that your GCC has a version of the Thompson hack installed. The check is simple: just do the three-stage bootstrap starting with a different compiler, and verify that you get an identical result. You've either proven that there's no hack, or that the other compiler has the hack too. You can repeat the process using cross-compilation. If you carry this out, you'll be forced to conclude that either there is no Thompson hack, or else that every C compiler you tried has the identical hack. Since I've used both Sun's proprietary compiler and GCC to build GCC on Solaris, I can confidently state that I proved that either GCC is clean or Sun's proprietary compiler is contaminated.

Ken Thompson's Reflections on Trusting Trust

Posted Feb 28, 2009 0:18 UTC (Sat) by nix (subscriber, #2304) [Link] (1 responses)

All this proves is that the GCC Cabal has sneaked appropriate patches into
every compiler capable of building GCC, even the proprietary ones.

(This is quite practical, using some of the money left over from the
construction of the secret Antarctic base. Rumours that the SC has orbital
compiler-control lasers are entirely without foundation.)

Ken Thompson's Reflections on Trusting Trust

Posted Feb 28, 2009 22:46 UTC (Sat) by JoeBuck (subscriber, #2330) [Link]

Shhh.

Ken Thompson's Reflections on Trusting Trust

Posted Feb 28, 2009 1:21 UTC (Sat) by pr1268 (guest, #24648) [Link]

Thank you, sir, for the description of how GCC is built. And my apologies for making you sigh. :)

Again, my question bordered somewhere between silly and rhetorical, but I was (and still am) fairly certain that the GCC devs considered the possibility of Thompson's hack when designing and implementing the compiler.

Ken Thompson's Reflections on Trusting Trust

Posted Mar 2, 2009 14:11 UTC (Mon) by forthy (guest, #1525) [Link]

This doesn't proof anything. If the compiler checks for duplicates (hack already there → don't install it again), then your stage 2 equals stage 3. Of course the hack in GCC would be in the source of GCC, sufficiently obfuscated ;-), so stage 1, 2, and 3 are functionally equivalent. The only suspicion could arise if you removed the hack from GCC's source (by wondering what said weird code does and commenting it out to try), and it would not disappear when recompiling. Doing such a check is obviously the first thing to do to avoid being discovered.