Scalable code signature approach for control-flow integrity

1 . A method of detecting a corrupted instruction stream, comprising:

executing, by a processor, a program, the program including a plurality of basic blocks, wherein each basic block has one or more instructions to be executed by the processor without branching;

retrieving, by an instruction fetch unit of the processor, a first basic block of the program from a memory address associated with a memory device;

initializing a first cyclic-redundancy-check (CRC) generator within the processor based, at least in part, on a first portion of the memory address of a first instruction in the first basic block of the plurality of basic blocks;

initializing a second CRC generator within the processor based, at least in part, on a second portion of the memory address of the first instruction;

generating, by the first CRC generator, a first CRC output based on the first basic block according to a first polynomial;

generating, by the second CRC generator, a second CRC output based on the first basic block according to a second polynomial;

executing the first basic block; and

when an end of the first basic block is reached without encountering an instruction to transfer control from a first function of the first basic block to a second function, selectively deferring a CRC check operation; and

generating, by the first CRC generator, a third CRC output based on a next basic block of the program according to the first polynomial without reinitializing the first CRC generator; and

generating, by the second CRC generator, a fourth CRC output based on the next basic according to the second polynomial without reinitializing the second CRC generator; and

wherein a first order of the first polynomial and a first order of the second polynomial are selected to provide a selected security level.

2 . The method of claim 1 , wherein the first polynomial and the second polynomial are co-prime.

3 . The method of claim 1 , wherein:

the selected security level is sixteen bits;

the first order of the first polynomial is eleven; and

the second order of the second polynomial is five.

4 . The method of claim 3 , wherein:

the first CRC generator is a CRC-11 generator; and

the second CRC generator is a CRC-5 generator.

5 . The method of claim 1 , further comprising:

determining a second basic block includes a branch function to the next basic block;

performing the CRC check operation based on the second basic block; and

optionally performing a CRC correction operation when the CRC check operation determines a bit error.

6 . The method of claim 1 , wherein, when a number n of basic blocks branch to a common basic block, the method comprises:

performing the CRC check operation for one less than the number (n−1) of the basic blocks that branch to the common basic block; and

optionally performing a CRC correction operation for bits of one of the number n of the basic blocks when the CRC check operation for the one determines a bit error.

7 . The method of claim 1 , wherein selectively deferring the CRC check operation comprises:

concatenating reference bits from instructions of the first basic block to form a reference value;

determining a number of the reference bits; and

deferring the CRC check operation when the number of reference bits is less than a number of bits of either the first CRC generator or the second CRC generator.

8 . The method of claim 1 , further comprising:

concatenating reference bits from instructions of the first basic block to form a reference value;

determining a number of the reference bits; and

selectively performing a partial correction based on one of the first CRC value or the second CRC value to produce corrected bits when the number of reference bits is equal to or greater than a number of bits of the second CRC generator and less than a number of bits of the first CRC generator.

9 . The method of claim 8 , wherein, subsequently, when the CRC check operation is performed, the method further comprising:

performing the CRC check operation on the corrected bits; and

ignoring a state of the uncorrected bits.

10 . The method of claim 1 , further comprising:

concatenating reference bits from instructions of the first basic block to form a reference value;

determining a number of the reference bits;

performing the CRC check operation based on both the first CRC value and the second CRC value when the number of the reference bits is equal to a sum of a first number of bits of the first CRC generator and a second number of bits of the second CRC generator; and

reinitializing the first CRC generator and the second CRC generator using a first memory address of a first instruction of the next basic block.

11 . The method of claim 1 , wherein implicitly initializing the first CRC generator occurs at a beginning of execution of the first basic block.

12 . A method of using code signatures to verify flow control integrity, the method comprising:

executing, by a processor, a program, the program including a plurality of basic blocks, wherein each basic block has one or more instructions to be executed by the processor without branching;

retrieving, by an instruction fetch unit of the processor, a first basic block of the program from a memory address associated with a memory device;

implicitly initializing a first cyclic-redundancy-check (CRC) generator and a second CRC generator within the processor based on one or more portions of the memory address of a first instruction in the first basic block of the plurality of basic blocks;

generating, by the first CRC generator, a first CRC output according to a first polynomial and, by the second CRC generator, a second CRC output according to a second polynomial based on the first basic block;

executing the first basic block;

concatenating reference bits determined from instructions of the first basic block to determine reference bits; and

when an end of the first basic block is reached without encountering an instruction to transfer control from a first function of the first basic block to a second function, determining a number of reference bits; and

selectively deferring a CRC check operation based on the number of reference bits; and

wherein a first order of the first polynomial and a first order of the second polynomial are selected to provide a selected security level.

13 . The method of claim 12 , wherein selectively deferring the CRC check operation comprises deferring the CRC check operation when the number of reference bits is less than a number of bits of either the first CRC generator or the second CRC generator.

14 . The method of claim 12 , further comprising selectively performing a partial correction based on one of the first CRC value or the second CRC value to produce corrected bits when the number of reference bits is equal to or greater than a number of bits of the second CRC generator and less than a number of bits of the first CRC generator.

15 . The method of claim 14 , wherein, subsequently, when the CRC check operation is performed, the method further comprising:

performing the CRC check operation on the corrected bits; and

ignoring a state of the uncorrected bits.

16 . The method of claim 12 , further comprising:

performing the CRC check operation based on both the first CRC value and the second CRC value when the number of the reference bits is equal to a sum of a first number of bits of the first CRC generator and a second number of bits of the second CRC generator; and

reinitializing the first CRC generator and the second CRC generator using a memory address of a first instruction of the next basic block.

17 . The method of claim 12 , wherein:

a first order of the first polynomial and a second order of the second polynomial are selected to provide a selected security level;

the selected security level is sixteen bits;

the first CRC generator generates an eleven-bit checksum; and

the second CRC generator generates a five-bit checksum.

18 . A processor comprising:

a program counter;

an instruction fetch unit configured to provide instructions that comprise a program including a plurality of basic blocks, each basic block including a sequence of instructions to be executed without branching;

an instruction decode unit coupled to the instruction fetch unit, the instruction decode unit configured to receive a first basic block of the plurality of basic blocks, and to generate a plurality of control signals;

a first cyclic-redundancy-check (CRC) generator coupled to the program counter to receive an address, coupled to the instruction fetch unit to receive the bits of the instructions, and coupled to the instruction decode unit to receive at least a portion of the plurality of control signals, the first CRC generator configured to generate a first CRC output in accordance with a first polynomial based on the instructions of the first basic block;

a second CRC generator coupled to the program counter to receive the address, coupled to the instruction fetch unit to receive at least a second portion of the bits of the instructions, and coupled to the instruction decode unit to receive at least a portion of the plurality of control signals, the second CRC generator configured to generate a second CRC output in accordance with a second polynomial based on the instructions of first basic block;

a register to store the first CRC output and the second CRC output and to concatenate and store reference bits determined from each of the instructions to form a reference value; and

CRC control circuitry configured to determine a number of reference bits of and to selectively defer a CRC checking operation based, at least in part, on the number of reference bits;

wherein the instruction fetch unit and the instruction decode unit are implemented in circuitry; and

wherein a first order of the first polynomial and a first order of the second polynomial are selected to provide a selected security level.

19 . The processor of claim 18 , wherein the CRC control circuitry selectively defers the CRC check operation when, at the end of execution of the first basic block, the instructions do not branch to another function and when the number of reference bits is less than a number of bits of either the first CRC generator or the second CRC generator.