Diversification of instruction set encodings to protect software

A system for diversifying instruction encodings in embedded devices that operate using a set of standard binary encodings of each instruction in an instruction set, the system comprising:

• first circuitry implementing a permutation encoding unit configured to:
• receive as input a binary executable encoded using the set of standard binary encodings for the instruction set, the binary executable representing a program;
• and
• recode the binary executable one or more times to produce, as output, corresponding one or more permuted executables representing the program, wherein to perform each recoding the first circuitry:
• obtains one of a plurality of keys each having a corresponding value that identifies one of a plurality of possible permutations of the standard binary encodings in the set;
• determines a set of permuted binary encodings that represents the identified permutation of the set of standard binary encodings;
• and
• procedurally replaces appearances in the binary executable of each of the standard binary encodings with the corresponding permuted binary encoding to produce a corresponding permuted executable associated with the key;
• transport circuitry configured to receive the output of the first circuitry and cause the output to be stored in memory of one or more of the embedded devices such that each embedded device having one of the plurality of keys receives the corresponding permuted executable associated with that key;
• and
• second circuitry in each of the embedded devices that implements a permutation decoding unit having access to the key and the memory of the corresponding embedded device and configured to:
• receive a control signal initiating execution of the program by a processor of the corresponding embedded device;
• and
• until a program counter has reached an end of the program, repeatedly:
• obtain, based on the program counter, a next value to be processed from the permuted executable stored in memory of the corresponding embedded device;
• use the key to identify the permuted binary encoding present in the next value and decode it into the corresponding standard binary encoding;
• replace the determined permuted binary encoding with the corresponding standard binary encoding within the next value to produce, as output, a standard encoded instruction;
• and
• transmit the standard encoded instruction to a decoder circuit of the corresponding embedded device, the decoder circuit responsively:
• using the set of standard binary encodings to decode the standard encoded instruction into a corresponding instruction;
• causing the corresponding instruction to be executed by the processor;
• and
• causing the program counter to be updated.

A method for protecting execution of a program on an embedded device that operates using a set of standard binary encodings of each instruction in an instruction set, the method comprising:

• accessing, by a permutation decoding unit of the embedded device, a permuted executable stored in memory of the embedded device, the permuted executable comprising a binary representation of the program encoded using a first permutation of the standard binary encodings, the first permutation based on a key associated with the embedded device;
• obtaining, by the permutation decoding unit, the key and a program counter associated with execution of the program;
• and
• until the program counter has reached an end of the program, repeatedly:
• obtaining, based on the program counter, a next value to be processed from the permuted executable;
• identifying in the next value one of a set of permuted binary encodings;
• using the key to decode the determined permuted binary encoding into a corresponding one of the set of standard binary encodings;
• replacing the determined permuted binary encoding with the corresponding standard binary encoding within the next value to produce a standard encoded instruction;
• and
• transmitting the standard encoded instruction to a decoder circuit of the embedded device, the decoder circuit responsively:
• using the set of standard binary encodings to decode the standard encoded instruction into a corresponding instruction;
• causing the corresponding instruction to be executed by the processor;
• and
• causing the program counter to be updated.