System and method for validating program execution at run-time using control flow signatures

• US 9,762,399 B2
• Filed: 12/30/2015
• Issued: 09/12/2017
• Est. Priority Date: 07/15/2010
• Status: Active Grant

• Current Assignee: The Research Foundation for The State University of New York (State University of New York)
• Original Assignee: The Research Foundation for The State University of New York (State University of New York)
• Inventors: Ghose, Kanad
• Primary Examiner(s): Zoubair, Noura
• Application Number:
  US14/984,800
• Publication Number:
  US 20160119148A1
• Time in Patent Office: 622 Days
• CPC Class Codes: G06F 11/1407 Checkpointing the instruction stream
• CPC Class Codes: G06F 11/3612 by runtime analysis performance monitoring G06F11/3466
• CPC Class Codes: G06F 12/0855 Overlapped cache accessing, e.g. pipeline G06F12/0846 takes precedence
• CPC Class Codes: G06F 12/0862 with prefetch
• CPC Class Codes: G06F 21/52 during program execution, e.g. stack integrity ; Preventing unwanted data erasure; Buffer overflow
• CPC Class Codes: G06F 21/602 Providing cryptographic facilities or services
• CPC Class Codes: G06F 21/74 operating in dual or compartmented mode, i.e. at least one secure mode
• CPC Class Codes: G06F 21/79 in semiconductor storage media, e.g. directly-addressable memories
• CPC Class Codes: G06F 2212/6026 Prefetching based on access pattern detection, e.g. stride based prefetch
• CPC Class Codes: G06F 9/3834 Maintaining memory consistency
• CPC Class Codes: G06F 9/3851 from multiple instruction streams, e.g. multistreaming
• CPC Class Codes: H04L 9/3247 involving digital signatures

Abstract

A processor comprising: an instruction processing pipeline, configured to receive a sequence of instructions for execution, said sequence comprising at least one instruction including a flow control instruction which terminates the sequence; a hash generator, configured to generate a hash associated with execution of the sequence of instructions; a memory configured to securely receive a reference signature corresponding to a hash of a verified corresponding sequence of instructions; verification logic configured to determine a correspondence between the hash and the reference signature; and authorization logic configured to selectively produce a signal, in dependence on a degree of correspondence of the hash with the reference signature.

Claims

1. A secure computing method, comprising:

storing a set of precomputed, encrypted reference signatures for a plurality of basic blocks of an executable program terminating in a control flow instruction in a first memory;

during execution of the executable program, retrieving a respective basic block of the executable program from a second memory;

partially processing instructions of the respective basic block of the executable program in a multistage instruction processing pipeline, and concurrently computing a signature of the instructions of the respective basic block with a signature generator, to generate a signature for the respective basic block along an execution path of the instructions to the terminating control flow instruction;

predictively fetching, based on a previously determined pattern of instruction fetching, at least one encrypted reference signature from the first memory;

securely decrypting the at least one encrypted reference signature from the first memory;

storing the securely decrypted at least one encrypted reference signature in a signature cache;

if;

(a) the control flow instruction terminating an execution path of the instructions of the respective basic block of the executable program is pending completion, and

(b) the decrypted reference signature of the respective basic block is available in the signature cache,

then;

verifying the signature for the respective basic block against the decrypted reference signature;

else;

stalling commitment of the control flow instruction terminating the execution path of the instructions of the respective basic block of the executable program, the multistage instruction processing pipeline comprising at least one stage provided as a buffer for a delay incurred by said stalling, until the decrypted reference signature of the respective basic block is available in the signature cache; and

verifying the signature for the respective basic block against the decrypted reference signature; and

if the signature for the respective basic block matches the decrypted reference signature, committing execution of the control flow instruction terminating the execution path of the instructions of the respective basic block of the executable program, else preventing commitment of the control flow instruction terminating the execution path of the instructions of the respective basic block of the executable program and flushing uncommitted instructions from the multistage instruction processing pipeline.

2. The method according to claim 1, further comprising computing a memory location of the respective encrypted reference signature for the respective basic block of the executable program in the first memory, based on an address of a first instruction of the respective basic block of the executable program from the second memory.

3. The method according to claim 1, further comprising computing a memory location of the respective encrypted reference signature for the respective basic block of the executable program in the first memory, based on an address of a last instruction of the respective basic block of the executable program from the second memory.

4. The method according to claim 1, wherein said securely decrypting the encrypted reference signature is performed by hardware decryption logic located on a same integrated circuit substrate as the multistage instruction processing pipeline, in dependence on a securely delivered decryption key.

5. The method according to claim 1, wherein said verifying the signature for the respective basic block against the decrypted reference signature comprises retrieving the decrypted reference signature from the signature cache.

6. The method according to claim 1, wherein the decrypted reference signature is retrieved from the signature cache prior to verifying.

7. The method according to claim 1, further comprising communicating the signature for the respective basic block to the signature cache, and generating a first signal from the signature cache dependent on whether the decrypted reference signature is stored in the signature cache.

8. The method according to claim 7, wherein the first signal is employed by pipeline control logic of the multistage instruction processing pipeline.

9. The method according to claim 7, wherein said verifying is performed on the decrypted reference signature contained within the signature cache, and the signature cache generates a second signal if the verifying is successful.

10. The method according to claim 9, wherein the second signal is employed by pipeline control logic of the multistage instruction processing pipeline.

11. A microprocessor configured for secure computing execution, comprising:

a signature cache configured to store a plurality of respective reference signatures of respective basic blocks of at least one executable program each terminating in a control flow instruction;

a multistage instruction processing pipeline comprising at least one stage provided as a buffer for a delay incurred by a presence of a control signal to stall execution of at least one instruction of a basic block in the multistage instruction processing pipeline, responsive to;

at least a first control signal to stall execution of the at least one instruction,

at least a second control signal to flush uncommitted instructions from the multistage instruction processing pipeline, and

at least a third control signal to commit execution of the at least one instruction;

a signature generator configured to determine a signature of the basic block of instructions within the multistage instruction processing pipeline, in parallel with instruction execution within the multistage instruction processing pipeline;

predictive fetching logic, configured to;

fetch at least one encrypted reference signature, based on a previously determined pattern of instruction fetching,

securely decrypt the at least one encrypted reference signature with secure hardware decryption logic, and

store the securely decrypted at least one encrypted reference signature in the signature cache;

verification logic configured to;

determine a match of the determined signature of the basic block of instructions with the decrypted reference signature in the signature cache,

produce the at least the second control signal to flush uncommitted instructions from the multistage instruction processing pipeline in event of a failure to match, and

produce the at least the third control signal to commit the execution of the at least one instruction in event of success of the match; and

flow control logic configured to determine presence of the control flow instruction terminating the basic block in the multistage processing pipeline, and to produce the at least the first control signal to stall execution of the instruction if the control flow instruction terminating the basic block is pending execution and the decrypted reference signature corresponding to the basic block is not available to the verification logic, and to resume execution of the instruction after the decrypted reference signature corresponding to the basic block becomes available to the verification logic.

12. The microprocessor according to claim 11, wherein the predictive fetching logic is further configured to determine an address of the respective reference signature based on at least one of information identifying the control flow instruction terminating the basic block and information identifying an instruction initiating the basic block.

13. The microprocessor according to claim 11, wherein the signature cache is further configured to generate at least a fourth control signal dependent on whether the decrypted reference signature corresponding to the basic block is stored in the signature cache.

14. The microprocessor according to claim 13, wherein the fourth control signal is received by pipeline control logic of the multistage instruction processing pipeline.

15. The microprocessor according to claim 11, wherein the signature cache is provided on a common integrated circuit with the verification logic, and are together configured to verify the decrypted reference signature stored within the signature cache.

16. The microprocessor according to claim 11, wherein the multistage instruction processing pipeline is configured to partially process instructions of the basic block of the executable program, concurrently with a determination of the signature of the basic block of instructions in the multistage instruction processing pipeline by the signature generator.

17. The microprocessor according to claim 11, wherein the signature generator is provided on a common integrated circuit with the instruction processing pipeline.

18. The microprocessor according to claim 11, wherein the predictive fetching logic is further configured to determine an address of the respective reference signature based on at least one of the control flow instruction terminating the basic block and an instruction initiating the basic block.

19. The microprocessor according to claim 11, further comprising a secure memory location and secure hardware logic configured to securely receive a decryption key for the encrypted reference signature into the secure memory location.

20. A secure computing microprocessor, comprising:

a multistage instruction processing pipeline comprising a buffer stage configured to buffer a delay incurred by a stall in execution of an instruction of a basic block of an executable program, the basic block terminating in a control flow instruction, responsive to;

a first control signal, to stall the execution of the instruction,

a second control signal, to flush uncommitted instructions from the multistage instruction processing pipeline, and

a third control signal, to commit the execution of the instruction;

a signature generator configured to generate a signature of the basic block, in parallel with instruction execution within the multistage instruction processing pipeline;

a signature cache configured to store a plurality of reference signatures of respective basic blocks of the executable program;

predictive fetching logic, configured to;

fetch at least one encrypted reference signature, based on a previously determined pattern of instruction fetching;

securely decrypt the at least one encrypted reference signature with secure hardware decryption logic; and

securely store the decrypted at least one encrypted reference signature in the signature cache;

verification logic configured to;

compare the generated signature of the basic block, with a respective decrypted encrypted reference signature securely stored in the signature cache to determine a match;

produce the second control signal to flush uncommitted instructions from the multistage instruction processing pipeline in event of a failure to determine the match, and

produce the third control signal to commit the execution of the at least one instruction in event of a success to determine the match; and

flow control logic configured to determine presence of the control flow instruction terminating the basic block in the multistage processing pipeline, and to produce the first control signal to stall execution of the instruction if the control flow instruction terminating the basic block is pending execution and the decrypted reference signature corresponding to the basic block is not available to the verification logic, and to resume execution of the instruction by cessation of the first control signal after the decrypted reference signature corresponding to the basic block becomes available to the verification logic.