Should we be able to scan binaries for these instructions? I guess an exploit should be able to call these instructions.

Keep in mind: in a variable length instruction set like x86, you can jump into the middle of an instruction, and have it interpreted as another instruction. If you have

    mov $0x123, %r16

you can think of it as a sequence of bytes, which (oversimplified) encodes to something like:

    0: $0xb8 # opcode for mov
    1: $0x10 # destination register
    2: $0x23 0x01 0x00 0x00 # constant

if you jump to address 2, you're in the middle of your constant. If that constant happens to be a malicious opcode, you're screwed.

So you can't just decode instructions starting from the program entry to find out if an opcode is trying to execute malicious code. You need to find all possible paths, including all computed jumps, to make that decision.

retrac

It's particularly bad with x86 due to the enormous variety of encodings and prefixes accumulated over the last half-century in the architecture. For example, the two instructions:

  mov rax, [table + rax*8] 
  mov [table + rax*8], rax

plus some lookup tables make a Turing-complete subset: https://drwho.virtadpt.net/files/mov.pdf (With jumping via conditional faulting done with an invalid MOV, of course.) There are many other subsets. And even C compilers targeting them: https://github.com/xoreaxeaxeax/movfuscator

Even better, there are multiple encodings of those instructions. And even better than that, there are Turing-complete subsets comprised only of printable ASCII characters. And even better than that, there are subsets of x86 the instruction set that can masquerade as readable English text: https://news.ycombinator.com/item?id=16312317

If your program counter ever diverges off to start executing unsanitized user data on x86, you are potentially pwn'd.