Next, someone will look at timing and notice something strange. So, add stuff that tweaks the real-time clock to correct for this when your binary runs, when the OS gets built with your compiler. That way, running 'time' on your binary will not show anything suspicious.
Next, someone may notice a discrepancy between real-time clocks and their OS. Solution? Make sure analog clocks aren't that precise, hook all digital clocks up to a time signal, and tweak that signal if you hit slower code paths that the user shouldn't see. Also, make sure that all other computers in the world slow down whenever one of them hits one of these paths.
Next, someone will notice a discrepancy between clock time and solar time.
For that, the NSA made up the leap second.
[2] https://en.wikipedia.org/wiki/Portable_C_Compiler
EDIT: in case you don't follow the links and realize the implications yourself, from wikipedia:
"It was very influential in its day, so much so that at the beginning of the 1980s, the majority of C compilers were based on it."
Not sure if that's a case for or against tinfoil hats.
And would be at least powerful enough to solve the halting problem.
There's nothing to doubt. A 'perfect' KTH virus is impossible.
I wonder if you couldn't reduce this to the halting problem to prove that this is actually impossible.
edit: Ah, never mind. It's already been mentioned in the OP that this has to be the case.
Though yes, to accomplish this the original infection would have to basically #include a godlike AI that would be able to intelligently infect all future debugging tools.
Sure, in theory, a perfect KTH scheme would be undetectable, since it suborns every means of detection. But in practice it often wouldn't. A KTH virus would have to anticipate all tools which may be written to detect it, and given the modern open and closed source software world the complexity would explode.