In his lecture Reflections on Trusting Trust, Ken Thompson describes a virus tha
ID: 650592 • Letter: I
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?
Explanation / Answer
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.