Memory efficient program pre-execution verifier and method

• US 7,120,572 B1
• Filed: 03/01/2000
• Issued: 10/10/2006
• Est. Priority Date: 01/06/2000
• Status: Expired due to Term

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Liang, Sheng
• Primary Examiner(s): Phan, Thai
• Assistant Examiner(s): Day, Herng-der
• Application Number:
  US09/516,406
• Time in Patent Office: 2,414 Days
• Field of Search: 703/13, 703/22, 703/23, 703/26, 717/126
• US Class Current: 703/26
• CPC Class Codes: G06F 9/44589 Program code verification, e.g. Java bytecode verification, proof-carrying code high-level semantic checks G06F8/43; testing and debugging software G06F11/36

Abstract

A program authoring system, prior to distributing a program, preprocesses the program to verify the integrity of the program. The program is written in a language that uses a restricted set of data type specific instructions. The program preprocessor, upon verification of the program'"'"'s integrity, generates a modified version of the program containing an array of supplemental information. The supplemental information consists of data type snapshots of the program stack and local variables immediately prior to execution of each of a set of identified target instructions, which are successors of conditional jump, unconditional jump, branch and flow control instructions, if any, in the program. In client devices that receive programs, a program verifier verifies the integrity of each received program. The instructions of the program are emulated to determine whether any instruction in the program would violate the data type restrictions for that instruction.

Claims

1. A method of operating a computer system, comprising:

(A) storing a program in a memory, the program including a sequence of instructions, where each of a multiplicity of the instructions represents an operation on data of a specific data type;

said each instruction having associated data type restrictions on the data type of data to be manipulated by said each instruction;

(B) processing the program to determine whether execution of any instruction in the program would violate the data type restrictions for that instruction and generating a first fault signal when execution of any instruction in the program would violate the data type restrictions for that instruction;

the program processing including;

(B1) determining a subset of the instructions, comprising target instructions, that are successor instructions of conditional jump, unconditional jump, branch and flow control instructions;

(B2) generating, for at least one target instruction in the program, a data type snapshot, the data type snapshot including data type information for at least one datum stored in an operand stack or a local variable prior to execution of the at least one target instruction;

(B3) determining for an identified target instruction whether a set of selection criteria are met, the set of selection criteria including whether the identified target instruction is a successor to at least two distinct predecessor instructions of the program and whether the data types associated with data stored in the operand stack and local variables by the program immediately after execution of all the predecessor instructions are identical; and

(B4) when the determination for the identified target instruction is negative, storing the snapshot for the identified target instruction in an array of supplemental information, and when the determination is positive, determining whether the identified target instruction is the target of any predecessor instruction positioned later in the program than the identified target instruction, and when this determination is positive, storing information identifying the identified target instruction in the array of supplemental information; and

(C) when the first fault signal is not generated, storing in the memory a modified version of the program having the array of supplemental information that includes the data type snapshot generated for at least one of the target instructions of the program;

wherein the supplemental information includes data type snapshots only for instructions determined to be target instructions.

2. The method of claim 1, further including:

identifying subroutines and subroutine calls, if any, in the program and converting the identified subroutines and subroutine calls into inline instructions, thereby generating a version of the program that includes no subroutines and subroutine calls, whereby the modified program includes no subroutines and subroutine calls.

3. The method of claim 1, further including:

distributing the modified program to a client device;

at the client device, prior to execution of the modified program, preprocessing the modified program to verify that execution of the program will not violate the data type restrictions and generating a second fault signal when execution of any instruction in the modified program would violate the data type restrictions for that instruction;

the pre-processing of the modified program including;

emulating the operation of the instructions in the modified program and determining whether each emulated instruction would violate the data type restrictions for that instruction, including, when the modified program includes a data type snapshot for the instruction being emulated, comparing a data type value generated by said emulating with a corresponding data type in the data type snapshot, and generating the second fault signal when the generated and corresponding data types are inconsistent with each other.

4. The method of claim 3, wherein the emulating, performed at the client device, includes,

when emulating an instruction of the modified program that has a successor instruction for which the modified program includes a data type snapshot, generating a current data type snapshot, comparing the current data type snapshot with the data type snapshot in the modified program and generating the second fault signal when the current data type snapshot and the data type snapshot in the modified program are inconsistent with each other.

5. The method of claim 4, wherein the emulating, performed at the client device, includes determining whether executing of any instruction in the modified program would result in an operand stack underflow or overflow, and whether execution of any loop in the modified program would result in a net addition or deletion of operands to the operand stack, and generating the second fault signal when the execution of the modified program would result in an operand stack underflow or overflow and when execution of any loop in the modified program would produce a net addition or deletion of operands to the operand stack.

6. The method of claim 5, including emulating, at the client device, each instruction in the modified program exactly once, in a predefined linear order starting at the beginning of the program and continuing in the predefined linear order without regard to actual order in which the instructions of the modified program would be executed during execution thereof.

7. The method of claim 5, including

when the preprocessing of the modified program results in the generation of no second fault signals, enabling execution of the modified program;

when the preprocessing of the program results in the generation of the second fault signal, preventing execution of the modified program; and

when execution of the modified program has been enabled, executing the modified program without performing data type checks on operands stored in the operand stack during execution of the modified program.

8. The method of claim 4, wherein the emulating of the modified program includes:

when the modified program includes information identifying the instruction being emulated but does not include a data type snapshot for the instruction being emulated, (A) generating and storing in a memory array a data type snapshot for the instruction being emulated, unless a data type snapshot for the instruction has already been stored in the memory array by the emulating step, and (B) when a data type snapshot for the instruction has already been stored in the memory array by the emulating step, comparing a data type value generated by said emulating with a corresponding data type in the data type snapshot in the memory array, and generating the second fault signal when the generated and corresponding data types are inconsistent with each other.

9. The method of claim 8, wherein the emulating of the modified program further includes:

when the instruction being emulated is a conditional jump, unconditional jump, branch instruction or flow control instructions and any successor instruction of the instruction being emulated is at a position later in the program than the instruction immediately following the instruction being emulated, (A) generating and storing a data type snapshot in the memory array for each successor instruction of the instruction being emulated that is at a position later in the program than the instruction immediately following the instruction being emulated and for which there is not already a data type snapshot stored in the memory array, and (B) otherwise, for each successor instruction of the instruction being emulated that is at a position later in the program than the instruction immediately following the instruction being emulated and for which there is already a data type snapshot stored in the memory array, generating a current data type snapshot, comparing the current data type snapshot with the data type snapshot stored in the memory array for the successor instruction, and generating the second fault signal when the current data type snapshot and the data type snapshot stored in the memory array for the successor instruction are inconsistent.

10. A computer program product for use in conjunction with a computer system, the computer program product comprising a computer readable storage medium and a computer program mechanism embedded therein, the computer program mechanism comprising:

an authoring module for storing a program in a memory in the computer system, the program including a sequence of instructions, where each of a multiplicity of the instructions represents an operation on data of a specific data type;

said each instruction having associated data type restrictions on the data type of data to be manipulated by said each instruction;

a program pre-processing module, including;

program emulation instructions that generate a first fault signal when execution of any instruction in the program would violate the data type restrictions for that instruction;

target instruction identification instructions for determining a subset of the instructions, comprising target instructions, that are successor instructions of conditional jump, unconditional jump, branch and flow control instructions; and

snapshot instructions for generating, for at least one target instruction in the program, a data type snapshot, the data type snapshot including data type information for at least one datum stored in an operand stack or a local variable prior to execution of the at least one target instruction; and

modified program generation instructions that, when the first fault signal is not generated, store in the memory a modified version of the program having an array of supplemental information that includes the data type snapshot generated for at least one of the target instructions of the program, wherein the supplemental information includes data type snapshots only for instructions determined to be target instructions;

wherein the snapshot instructions include

instructions for determining for an identified target instruction whether a set of selection criteria are met, the set of selection criteria including whether the identified target instruction is a successor to at least two distinct predecessor instructions of the program and whether the data types associated with data stored in the operand stack and local variables by the program immediately after execution of all the predecessor instructions are identical; and

instructions for storing the snapshot for the identified target instruction in the array of supplemental information when the determination for the identified target instruction is negative, and when the determination is positive, for determining whether the identified target instruction is the target of any predecessor instruction positioned later in the program than the identified target instruction, and when this determination is positive, for storing information identifying the identified target instruction in the array of supplemental information.

11. The computer program product of claim 10, wherein the program pre-processing module includes subroutine miming instructions that identify subroutines and subroutine calls, if any, in the program and convert the identified subroutines and subroutine calls into inline instructions, thereby generating a version of the program that includes no subroutines and subroutine calls, whereby the modified program includes no subroutines and subroutine calls.

12. A computer program product for use in conjunction with a computer controlled apparatus, the computer program product comprising a computer readable storage medium and a computer program mechanism embedded therein, the computer program mechanism comprising:

a communications module for receiving a program and storing it in a memory in the computer controlled apparatus, the program including a sequence of instructions, where each of a multiplicity of the instructions represents an operation on data of a specific data type;

said each instruction having associated data type restrictions on the data type of data to be manipulated by said each instruction;

the received program including an array of supplemental information that includes a data type snapshot for at least one of the instructions of the program, the data type snapshot including data type information for at least one datum stored in an operand stack or a local variable prior to execution of the at least one of the instructions;

wherein the supplemental information in the received program includes data type snapshots only for instructions determined to be target instructions, the target instructions comprising successor instructions of conditional jump, unconditional jump, branch and flow control instructions, if any, in the program; and

a program pre-processing module, including;

program emulation instructions that generate a fault signal when execution of any instruction in the program would violate the data type restrictions for that instruction, including;

instructions for determining whether the program includes a data type snapshot for the instruction being emulated, comparing a data type value generated by the program emulation instructions with a corresponding data type in the data type snapshot, and generating the fault signal when the generated and corresponding data types are inconsistent with each other; and

instructions, activated when the instruction being emulated is a last instruction of a method, for generating the fault signal when the instruction being emulated is not one of an unconditional jump, a switch instruction, and a flow control instruction.

13. The computer program product of claim 12, wherein the program emulation instructions include instructions, activated when emulating an instruction of the program that has a successor instruction for which the modified program includes a data type snapshot, for generating a current data type snapshot, comparing the current data type snapshot with the data type snapshot in the program and generating the fault signal when the current data type snapshot and the data type snapshot in the modified program are inconsistent with each other.

14. The computer program product of claim 13, wherein the program emulation instructions include instructions for determining whether executing of any instruction in the program would result in an operand stack underflow or overflow, and whether execution of any loop in the program would result in a net addition or deletion of operands to the operand stack, and generating the fault signal when the execution of the program would result in an operand stack underflow or overflow and when execution of any loop in the program would produce a net addition or deletion of operands to the operand stack.

15. The computer program product of claim 14, wherein the program emulation instructions include instructions for emulating each instruction in the program exactly once, in a predefined linear order starting at the beginning of the program and continuing in the predefined linear order without regard to actual order in which the instructions of the program would be executed during execution thereof.

16. The computer program product of claim 14, including

instructions for preventing execution of the program when the preprocessing module generates the fault signal, and for enabling execution of the program when the preprocessing module does not generate the fault signal;

and

a program execution module for executing the program without performing data type checks on operands stored in the operand stack and in local variables during execution of the modified program.

17. The computer program product of claim 14, wherein the program emulation instructions include instructions, activated when the array of supplemental information for the program includes information identifying the instruction being emulated but does not include a data type snapshot for the instruction being emulated, for (A) generating and storing in a memory array a data type snapshot for the instruction being emulated, unless a data type snapshot for the instruction has already been stored in the memory array, and (B) when a data type snapshot for the instruction has already been stored in the memory array by the emulation instructions, comparing a data type value generated by said emulation instructions with a corresponding data type in the data type snapshot in the memory array, and generating the fault signal when the generated and corresponding data types are inconsistent with each other.

18. The computer program product of claim 14, wherein the program emulation instructions further include instructions, activated when the instruction being emulated is a conditional jump, unconditional jump, branch instruction or flow control instruction and any successor instruction of the instruction being emulated is at a position later in the program than the instruction immediately following the instruction being emulated, for (A) generating and storing a data type snapshot in the memory array for each successor instruction of the instruction being emulated that is at a position later in the program than the instruction immediately following the instruction being emulated and for which there is not already a data type snapshot stored in the memory array, and (B) otherwise, for each successor instruction of the instruction being emulated that is at a position later in the program than the instruction immediately following the instruction being emulated and for which there is already a data type snapshot stored in the memory array, generating a current data type snapshot, comparing the current data type snapshot with the data type snapshot stored in the memory array for the successor instruction, and generating the fault signal when the current data type snapshot and the data type snapshot stored in the memory array for the successor instruction are inconsistent.

19. A computer system, comprising:

memory for storing a program, the program including a sequence of instructions, where each of a multiplicity of said instructions each represents an operation on data of a specific data type;

said each instruction having associated data type restrictions on the data type of data to be manipulated by said each instruction;

a data processing unit for executing programs stored in the memory;

a program pre-processing module, executable by the data processing unit, including;

program emulation instructions that generate a first fault signal when execution of any instruction in the program would violate the data type restrictions for that instruction;

target instruction identification instructions for determining a subset of the instructions, comprising target instructions, that are successor instructions of conditional jump, unconditional jump, branch and flow control instructions; and

snapshot instructions for generating, for at least one target instruction in the program, a data type snapshot, the data type snapshot including data type information for at least one datum stored in an operand stack or a local variable prior to execution of the at least one target instruction; and

modified program generation instructions that, when the first fault signal is not generated, store in the memory a modified version of the program having an array of supplemental information that includes the data type snapshot generated for at least one of the target instructions of the program, wherein the supplemental information includes data type snapshots only for instructions determined to be target instructions;

wherein the snapshot instructions include

instructions for determining for an identified target instruction whether a set of selection criteria are met, the set of selection criteria including whether the identified target instruction is a successor to at least two distinct predecessor instructions of the program and whether the data types associated with data stored in the operand stack and local variables by the program immediately after execution of all the predecessor instructions are identical; and

instructions for storing the snapshot for the identified target instruction in the array of supplemental information when the determination for the identified target instruction is negative, and when the determination is positive, for determining whether the identified target instruction is the target of any predecessor instruction positioned later in the program than the identified target instruction, and when this determination is positive, for storing information identifying the identified target instruction in the array of supplemental information.

20. The computer system of claim 19, wherein the program pre-processing module includes subroutine inlining instructions that identify subroutines and subroutine calls, if any, in the program and convert the identified subroutines and subroutine calls into inline instructions, thereby generating a version of the program that includes no subroutines and subroutine calls, whereby the modified program includes no subroutines and subroutine calls.

21. A computer controlled apparatus, comprising:

memory;

a data processing unit for executing programs stored in the memory;

a communications module, executable by the data processing unit, for receiving a program and storing it in a memory in the computer controlled apparatus, the program including a sequence of instructions, where each of a multiplicity of the instructions represents an operation on data of a specific data type;

said each instruction having associated data type restrictions on the data type of data to be manipulated by said each instruction;

the received program including an array of supplemental information that includes a data type snapshot for at least one of the instructions of the program, the data type snapshot including data type information for at least one datum stored in an operand stack or a local variable prior to execution of the at least one of the instructions;

wherein the supplemental information in the received program includes data type snapshots only for instructions determined to be target instructions, the target instructions comprising successor instructions of conditional jump, unconditional jump, branch and flow control instructions, if any, in the program; and

a program pre-processing module, executable by the data processing unit, including;

program emulation instructions that generate a fault signal when execution of any instruction in the program would violate the data type restrictions for that instruction, including

instructions for determining whether the program includes a data type snapshot for the instruction being emulated, comparing a data type value generated by the program emulation instructions with a corresponding data type in the data type snapshot, and generating the fault signal when the generated and corresponding data types are inconsistent with each other; and

instructions, activated when the instruction being emulated is a last instruction of a method, for generating the fault signal when the instruction being emulated is not one of an unconditional jump, a switch instruction, and a flow control instruction.

22. The computer controlled apparatus of claim 21, wherein the program emulation instructions include instructions, activated when emulating an instruction of the program that has a successor instruction for which the modified program includes a data type snapshot, for generating a current data type snapshot, comparing the current data type snapshot with the data type snapshot in the program and generating the fault signal when the current data type snapshot and the data type snapshot in the modified program are inconsistent with each other.

23. The computer controlled apparatus of claim 22, wherein the program emulation instructions include instructions for determining whether executing of any instruction in the program would result in an operand stack underflow or overflow, and whether execution of any loop in the program would result in a net addition or deletion of operands to the operand stack, and generating the fault signal when the execution of the program would result in an operand stack underflow or overflow and when execution of any loop in the program would produce a net addition or deletion of operands to the operand stack.

24. The computer controlled apparatus of claim 23, wherein the program emulation instructions include instructions for emulating each instruction in the program exactly once, in a predefined linear order starting at the beginning of the program and continuing in the predefined linear order without regard to actual order in which the instructions of the program would be executed during execution thereof.

25. The computer controlled apparatus of claim 23, including

instructions for preventing execution of the program when the preprocessing module generates the fault signal, and for enabling execution of the program when the preprocessing module does not generate the fault signal;

and

a program execution module for executing the program without performing data type checks on operands stored in the operand stack and in local variables during execution of the modified program.

26. The computer controlled apparatus of claim 23, wherein the program emulation instructions include instructions, activated when the array of supplemental information for the program includes information identifying the instruction being emulated but does not include a data type snapshot for the instruction being emulated, for (A) generating and storing in a memory array a data type snapshot for the instruction being emulated, unless a data type snapshot for the instruction has already been stored in the memory array, and (B) when a data type snapshot for the instruction has already been stored in the memory array by the emulation instructions, comparing a data type value generated by said emulation instructions with a corresponding data type in the data type snapshot in the memory array, and generating the fault signal when the generated and corresponding data types are inconsistent with each other.

27. The computer controlled apparatus of claim 23, wherein the program emulation instructions further include instructions, activated when the instruction being emulated is a conditional jump, unconditional jump, branch instruction or flow control instruction and any successor instruction of the instruction being emulated is at a position later in the program than the instruction immediately following the instruction being emulated, for (A) generating and storing a data type snapshot in the memory array for each successor instruction of the instruction being emulated that is at a position later in the program than the instruction immediately following the instruction being emulated and for which there is not already a data type snapshot stored in the memory array, and (B) otherwise, for each successor instruction of the instruction being emulated that is at a position later in the program than the instruction immediately following the instruction being emulated and for which there is already a data type snapshot stored in the memory array, generating a current data type snapshot, comparing the current data type snapshot with the data type snapshot stored in the memory array for the successor instruction, and generating the fault signal when the current data type snapshot and the data type snapshot stored in the memory array for the successor instruction are inconsistent.