Method of protecting a computer stack

• US 7,581,089 B1
• Filed: 04/18/2007
• Issued: 08/25/2009
• Est. Priority Date: 04/20/2006
• Status: Active Grant

• Current Assignee: National Security Agency
• Original Assignee: The United States of America As Represented By The Director National Security Agency
• Inventors: White, Andrew H.
• Primary Examiner(s): Coleman; Eric
• Application Number:
  US11/787,832
• Time in Patent Office: 860 Days
• Field of Search: 712/242
• US Class Current: 712/242
• CPC Class Codes: G06F 12/1416 by checking the object accessibility, e.g. type of access defined by the memory independently of subject rights G06F12/1458 takes precedence
• CPC Class Codes: G06F 21/54 by adding security routines or objects to programs
• CPC Class Codes: G06F 9/30054 Unconditional branch instructions
• CPC Class Codes: G06F 9/30134 Register stacks; shift registers
• CPC Class Codes: G06F 9/323 for indirect branch instructions
• CPC Class Codes: G06F 9/3806 using address prediction, e.g. return stack, branch history buffer
• CPC Class Codes: G06F 9/4486 Formation of subprogram jump address

Abstract

A method of protecting a return address on a computer stack is disclosed. Two stacks are created, the first a normal stack, and the second, or shadow, having shadow frames containing the return address upon a subroutine call, the address on the first stack where the return address is stored, and a user-definable state variable which is used to identify a shadow frame as a return address. Before returning from a subroutine, the two return addresses are compared, and if they do not match, the second stack is searched down, and then up, for a matching return address. If there is a match, the shadow is re-synchronized with the first stack by comparing the stored values of the first stack pointer with the first stack pointer and adjusting appropriately the shadow stack pointer. The matching shadow frame must also be a return address datatype of return address.

Claims

1. A method of protecting a value on a computer stack, comprising the steps of:

a) creating a first computer stack on a computer, the first computer stack having a first stack pointer;

b) creating a second computer stack on a computer, the second computer stack having a second stack pointer which points to shadow frames, wherein the second stack stores a return address located on the first stack upon a call to a subroutine in a first shadow element, the address of the return address stored on the first stack upon a call to a subroutine in a second shadow element, and a user-definable variable defining the status of the return address stored on the second computer stack in a third shadow element;

c) storing a return address upon a call to a subroutine on the first computer stack;

d) storing on the second stack the return address from step (c), the address of the return address stored in step (c), and the user-definable status variable to indicate the current shadow frame contains a return address;

e) advancing the first stack pointer to the next available frame on the first computer stack and advancing the second stack pointer to the next available shadow frame on the second computer stack;

f) jumping to the subroutine;

g) executing the subroutine;

h) fetching the return address from the second computer stack and the return address from the first computer stack, wherein the return address from the second computer stack is the first return address stored on the second computer stack below the current position of the second stack pointer;

i) comparing the return address from the second computer stack to the return address from the first computer stack;

j) if the return address from the second computer stack is the same as the return address from the first computer stack, proceed to step (c), otherwise proceeding to step (o);

k) decrementing the stack pointer on the first computer stack;

l) synchronizing the second computer stack'"'"'s stack pointer with the first computer stack'"'"'s stack pointer by decrementing the second stack pointer on the second computer stack to at least one previous shadow frame;

m) loading the instruction pointer with the return address;

n) if additional subroutines exist on the first computer stack, returning to step (c), otherwise stopping;

o) searching the second computer stack, below the position of the current second stack pointer and above the position of the current stack pointer, for a return address that matches the return address fetched from the first computer stack;

p) if a matching return address is found in step (o), and if user-definable status variable indicates the shadow frame containing the return address was stored on the second computer stack as a return address;

q) if the result of step (p) indicates a matching return address, proceeding to step (k), otherwise stopping; and

r) write-disabling the second computer stack by application software, the second computer stack write-enabled by hardware code when storing on the second stack the return address from step (c).

2. The method of claim 1, wherein the step of searching the second computer stack, above the current stack pointer and below the current stack pointer, for a value that matches the value fetched from the first computer stack further comprises searching below the current stack pointer before searching above the current stack pointer.

3. The method of claim 1, further comprising encrypting the return address of a next instruction upon a call to a subroutine with an encryption key and decrypting the return address after fetching the return address, the encryption key selected from the group of encryption keys consisting of the address on the computer stack at which the return address is to be stored, a fixed encryption key, a fixed encryption key in a central processing unit, a changeable encryption key, a changeable encryption key in the central processing unit, an address of the subroutine, an encryption key stored at a fixed delta from the address at which the return address is to be stored, and the stack pointer of the computer stack.

4. The method of claim 1, wherein the second computer stack is randomly located in memory when created.

5. A method of protecting a value on a computer stack, comprising the steps of:

a) creating a first computer stack on a computer, the first computer stack having a first stack pointer;

b) creating a second computer stack on a computer, the second computer stack having a second stack pointer which points to shadow frames, where the second stack stores a return address located on the first stack upon a call to a subroutine in a first shadow element, the address of the return address stored on the first stack upon a call to a subroutine in a second Shadow element, and a user-definable variable defining the status of the return address stored on the second computer stack in a third shadow element;

c) storing a return address upon a call to a subroutine on the first computer stack;

d) storing on the second stack the ret address from step (c), the address of the return address stored in step (a), and the user-definable status variable to indicate the current shadow frame contains a return address;

e) advancing the first stack pointer to the next available frame on the first computer stack and advancing the second stack pointer to the next available shadow frame on the second computer stack;

f) jumping to the subroutine;

g) executing the subroutine;

h) fetching the return address from the second computer stack and the return address from the first computer stack, wherein the return address from the second computer stack is the first return address stored on the second computer stack below the current position of the second stack pointer;

i) comparing the return address from the second computer stack to the return address from the first computer stack;

j) if the return address from the second computer stack is the same as the return address from the first computer stack, proceed to step k), otherwise proceeding to step (o);

k) decrementing the stack pointer on the first computer stack;

l) synchronizing the second computer stack'"'"'s stack pointer with the first computer stack'"'"'s stack pointer by decrementing the second stack pointer on the second computer stack to at least one previous shadow frame;

m) loading the instruction pointer with the return address;

n) if additional subroutines exist on the first computer stack, returning to step (c), other stopping;

o) re-synchronizing the second computer stack'"'"'s stack pointer with the first computer stack'"'"'s stack pointer by decrementing the second stack pointer on the second computer stack to at least one pious shadow frame;

p) if the first computer stack pointer matches the stack pointer in the shadow frame found in step (o) proceed to step (q), otherwise proceed to step (s);

q) searching the second computer stack, below the position of the shadow stack pointer and above the position of the shadow stack pointer, for a return address that matches the return address fetched from the first computer stack;

r) if the result of step (q) indicate a match, proceed to step (s), otherwise stopping;

s) decrementing the stack pointer of the first computer stack to the previous frame, and proceed to step (m); and

t) write-disabling the second computer stack by application software, the second computer stack write-enabled hardware code when storing on the second stack the ret address from step (c).

6. The method of claim 5, wherein the step of searching the second computer stack, above the current stack pointer and below the current stack pointer, for a value that matches the value fetched from the first computer stack further comprises searching below the current stack pointer before searching above the current stack pointer.

7. The method of claim 5, further comprising encrypting the return address of a next instruction upon a call to a subroutine with an encryption key and decrypting the return address after fetching the return address, the encryption key selected from the group of encryption keys consisting of the address on the computer stack at which the return address is to be stored, a fixed encryption key, a fixed encryption key in a central processing unit, a changeable encryption key, a changeable encryption key in the central processing unit, an address of the subroutine, an encryption key stored at a fixed delta from the address at which the return address is to be stored, and the stack pointer of the computer stack.

8. The method of claim 5, wherein the second computer stack is randomly located in memory when created.