For an old CPU, finding all the valid instructions wasn’t very hard. You simply tried them all. Sure, really old CPUs might make it hard to tell what the instruction did, but once CPUs got illegal instruction traps, you could quickly just scan possible op codes and see what didn’t throw an exception. Modern processors, though, are quite another thing. For example, you might run a random instruction that locks up the machine or miss an instruction that would have been valid but the CPU is in the wrong mode. [Can Bölük] has a novel solution: By speculatively executing the target instruction and then monitoring the microcode sequencer, he can determine if the CPU is decoding an instruction even if it refuses to execute it.
Some unknown instructions may have power for good or evil, such as the recently announced undocumented instructions that can apparently rewrite the microcode. We expect to see a post soon on how to reprogram your Intel processor to run as a 6502 natively.
The speculative execution exploit is quite clever. Modern processors execute code out of order and run different parts of instructions at the same time. In other words, it might be fetching instruction C while storing the result of instruction A and decoding instruction B. The problem is when the code can conditionally branch it causes a problem. If instruction A is a conditional jump, do you take B and C as the next instructions or the instructions at the branch address? Either way, if you are wrong you’ll need to discard any work you’ve already done and restart.
One answer is to simply stall the pipeline until the decision is final. That’s bad for performance, though. Another common technique is to try to guess what direction a branch in your code will take and use that. That might be a simple heuristic such as mode jumps go backward or it could keep a history of where the jump has gone in the past.
The key is that the code is partially executed, but can’t do whatever it is supposed to do until the branch resolves. Normally, that wouldn’t be helpful, but watching the performance counters of the microcode translators tells you if the instruction generated actual low-level microcode instructions or was simply pruned out immediately as a bad instruction. The assumption is that if the CPU designer sent an instruction to microcode it must do something. [Can] provides a list of instructions found on his i7 6850K CPU.