Methods for enforcing control flow of a computer program

1. A computer-implemented method of controlling execution of a computer program by a Just-In-Time (JIT) compiler, the method comprising the following steps:

maintaining a shadow code heap in memory outside the JIT compiler's sandbox;

as a code region is loaded into the JIT compiler's code heap:

parsing the code region to identify one or more pseudo-instruction start addresses, indirect branch target addresses, and direct branch target addresses;

adding those addresses to a pseudo-instruction start addresses (PSA′) set, an indirect branch target addresses (IBT′) set, and a direct branch target (DBT′) addresses set;

verifying that:

all members of the IBT′ set and the DBT′ set are also members of the PSA′ set;

all indirect branches and memory-write instructions in the new code region are appropriately instrumented;

all direct branches in the new code region jump to addresses in the DBT′ set; and

the new code region contains only instructions corresponding to the JIT compiler;

upon successful completion of the verifying step, copying the new code region into the shadow code heap;

updating a branch ID data structure in memory that maps an indirect branch location to a branch ID and a target ID data structure that maps an address to a target ID with the addresses from the IBT′ set; and

prior to execution of an indirect branch including a return instruction located at an address:

obtaining the branch ID associated with the return address from the branch ID data structure;

obtaining the target ID associated with an actual return address for the indirect branch from the target ID data structure;

comparing the branch ID and the target ID; and

if the branch ID and the target ID differ, preventing execution of the indirect branch.

2. The computer-implemented method of claim 1 , wherein the shadow code heap is readable and writable, but not executable.

3. The computer-implemented method of claim 1 , wherein the pseudo-instruction start addresses, the indirect branch target addresses, and the direct branch target addresses are stored as bitmaps.

4. The computer-implemented method of claim 1 , wherein the verifying step further comprises iterating through a Deterministic Finite Automata (DFA) of all possible allowed instruction encoding.

5. The computer-implemented method of claim 4 , wherein the DFA is generated from a trie structure of all possible allowed instruction encoding.

6. The computer-implemented method of claim 1 , further comprising:

upon receiving a request to delete the code region from the shadow code heap and the JIT compiler's code heap:

determining whether direct branches outside of the code region target any instructions within the code region;

removing code-region-related entries from the branch ID data structure and the target ID data structure; and

determining whether any threads are running or sleeping in the code region.

7. The computer-implemented method of claim 6 , wherein the determining whether any threads are running or sleeping in the code region step further comprises waiting until each thread enters runtime code after execution of the removing step.

8. The computer-implemented method of claim 6 , wherein the determining whether any threads are running or sleeping in the code region step further comprises:

checking each one of a plurality of counters, each counter associated with one of the threads after execution of the removing step;

incrementing the associated counter each time the associated thread enters the runtime code; and

checking whether each one of a plurality of counters has changed.

9. The computer-implemented method of claim 1 , further comprising:

generating a fine-grained control flow graph (CFG) for the JIT compiler prior to runtime.

10. A computer-implemented method of controlling execution of a computer program, the method comprising the following runtime steps:

parsing code to identify one or more indirect branches;

creating a branch ID data structure in memory that maps an indirect branch location to a branch ID, which is the indirect branch's equivalence class ID;

creating a target ID data structure in memory that maps an address to a target ID, which is an equivalence class ID to which the address belongs; and

prior to execution of an indirect branch including a return instruction located at an address:

obtaining the branch ID associated with the return address from the branch ID data structure;

obtaining the target ID associated with an actual return address for the indirect branch from the target ID data structure;

marking a link between the branch ID and the return address as active in the branch ID data structure and the target ID data structure;

comparing the branch ID and the target ID; and

if the branch ID and the target ID differ, preventing execution of the indirect branch.

11. The computer-implemented method of claim 10 , further comprising:

if the branch ID and the target ID match, permitting execution of the indirect branch.

12. The computer-implemented method of claim 10 , wherein the marking step comprises invoking an idempotent operation.

13. The computer-implemented method of claim 10 , wherein the branch ID data structure is an array.

14. The computer-implemented method of claim 10 , wherein the target ID data structure is an array.