In general terms, how could the Thompson Hack be implemented in Microcode?

Question

In his lecture Reflections on Trusting Trust, Ken Thompson describes a virus that infects a compiler; the infected compiler installs backdoors into programs, but the key part is that the infected compiler also infects all compilers it compiles.

K. Thompson notes that if this was implemented at the Microcode level, it would be almost impossible to stop.

My question is this; in general terms (i.e. I'm not going to ask for details on how to create the most insidious trojan that has ever existed) how can you write microcode that would inject Thompson's trojan into every program compiled on a computer with that microcode.

As far as I can tell, the core of this question (i.e. the most important part, theoretically speaking) is:

Can the code implementing machine code (such as microcode) detect when the machine code it is implementing is a compiler that is compiling (in order to inject trojans into the compiled program), and if so, how?

Answer 1

In general, it certainly can not; this follows from Rice's theorem. That is, if you want to restrict the set of functions that are compilers in a meaningful way (one might also say that every function is a compiler).

In practice, you can of course inspect the sources of popular compilers and include heuristics in your malicious code that detect gcc, javac or any other known compiler.

Answer 2

how can you write microcode that would inject Thompson's trojan into every program compiled on a computer with that microcode

A way to look at it is that the microcode is an interpreter for the public machine code. It is in fact the true machine code (well some machine have a two level microcode ;-) and in theory it can do whatever it want, included inspecting the executed code and replacing it with hacked up version. In practice, there are severe limitation to what you can do in microcode. Three aspects:

• space for the microcode program is usually very limited; I'm not sure there would be enough place there to put the trojan in place (especially that the trojan would have to do more things than in Thompson's case -- you don't know the name of the function you are executing --, especially if you want to avoid the next point)
• performance would probably be impacted and make the insertion of the trojan visible, people making benchmark will ask questions
• in current processors most instructions are executed directly by the hardware without going to the microcode; I'm not sure there is enough hooks to implement such trojan.

(For the conspiracy minded, obviously if the processor is designed to make such trojan possible, all those points are solvable).