> OK, but how is the 32-bit header itself embedded?
The header is embedded according to the same rules as the rest of the message: it's treated as a bitstring, and flippable instructions are flipped appropriately to encode it.
> the possibility of a "collision" or of a false positive seems relatively high to me.
As others have pointed out, compilers (and assemblers) tend to stick to a single selection choice for register-to-register ops. Even in the case where a compiler writer flips between them randomly, their 32 random choices would have to align precisely with the expected header. It's certainly not impossible, but pretty unlikely. It's also completely remediable with a CRC32 or similar field tacked onto the header; I just didn't think the likelihood warranted that for the initial design.