Bytecode program interpreter apparatus and method with pre-verification of data type restrictions and object initialization

• US 5,999,731 A
• Filed: 03/24/1998
• Issued: 12/07/1999
• Est. Priority Date: 12/20/1994
• Status: Expired due to Fees

• Current Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Gosling, James A., Yellin, Frank
• Primary Examiner(s): Hafiz, Tariq R.
• Assistant Examiner(s): Chavis, John Q.
• Application Number:
  US09/046,719
• Time in Patent Office: 623 Days
• Field of Search: 395/704, 395/705, 395/707
• US Class Current: 717/126
• CPC Class Codes: G06F 11/3612 by runtime analysis performance monitoring G06F11/3466
• CPC Class Codes: G06F 21/51 at application loading time, e.g. accepting, rejecting, starting or inhibiting executable software based on integrity or source reliability
• CPC Class Codes: G06F 21/52 during program execution, e.g. stack integrity ; Preventing unwanted data erasure; Buffer overflow
• CPC Class Codes: G06F 21/566 Dynamic detection, i.e. detection performed at run-time, e.g. emulation, suspicious activities
• 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
• CPC Class Codes: G06F 9/45508 Runtime interpretation or emulation, e g. emulator loops, bytecode interpretation

Abstract

A program interpreter for computer programs written in a bytecode language, which uses a restricted set of data type specific bytecodes. The interpreter, prior to executing any bytecode program, executes a bytecode program verifier procedure that verifies the integrity of a specified program by identifying any bytecode instruction that would process data of the wrong type for such a bytecode and any bytecode instruction sequences in the specified program that would cause underflow or overflow of the operand stack. If the program verifier finds any instructions that violate predefined stack usage and data type usage restrictions, execution of the program by the interpreter is prevented. After pre-processing of the program by the verifier, if no program faults were found, the interpreter executes the program without performing operand stack overflow and underflow checks and without performing data type checks on operands stored in operand stack. As a result, program execution speed is greatly improved.

Claims

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

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

each instruction in the subset having associated data type restrictions on the data type of data to be manipulated by that instruction;

(B) storing, for each instruction in the program, a data type snapshot, the data type snapshot including data type information concerning data types associated with data stored in an operand stack and registers by the program immediately prior to execution of the corresponding instruction;

(C) emulating operation of a selected instruction in the program by;

(C1) analyzing stack and register usage by the selected instruction so as to generate a current data type usage map for the operand stack and registers, (C2) determining all successor instructions to the selected instruction, (C3) merging the current data type usage map with the data type snapshot of the determined successor instructions, and (C4) marking for further analysis each of the determined successor instructions whose data type snapshot is modified by said merging;

(D) emulating operation of each of the instructions marked for further analysis by performing step C on each of those marked instructions and unmarking each emulated instruction; and

(E) repeating step D until there are no marked instructions;

said step C1 including determining when the stack and register usage by the instruction would violate the data type restrictions, if any, for that instruction and generating a fault signal when execution of the instruction would violate the data type restrictions.

2. The method of claim 1, said step C including:

determining whether execution of any loop in the program would result in a net addition or deletion of operands to the operand stack, and generating a program fault signal when execution of any loop in the program would produce a net addition or deletion of operands to the operand stack.

3. The method of claim 1, including

(F) when no program fault signals are generated, enabling execution of said program;

(G) when a program fault is generated, preventing execution of said program; and

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

4. The method of claim 1,

the program including at least one object creation instruction and at least one object initialization instruction;

said step C including storing in the current usage data map, for each object that would be stored in the operand stack and registers after execution of the selected instruction, a data type value for each uninitialized object that is distinct from a corresponding data type value for the same object after initialization thereof;

said step C further including, when the selected instruction is not the at least one object initialization instruction, generating a program fault signal when execution of the selected instruction would access a stack operand or register whose data type corresponds to an uninitialized object.

5. The method of claim 4,

said step 2B further including, when the selected instruction is the at least one object initialization instruction, generating a program fault signal when execution of the selected instruction would access a stack operand or register whose data type corresponds to an initialized object.

6. The method of claim 1,

the program including at least one jump to subroutine (jsr) instruction and at least one subroutine return (ret) instruction located within a subroutine included in the program;

said step C2 including, when the selected instruction is the subroutine return instruction, determining each of the successor instructions to be an instruction immediately following a jsr instruction for jumping to the subroutine;

said step C2 including, when the selected instruction is the subroutine return instruction, merging the current data type usage map with the data type snapshot of each of the determined successor instructions by storing in the data type snapshot for each of the successor instructions data type information from the current data type usage map for each register accessed and each register modified by the subroutine and data type information for each other register from the data type snapshot for the jsr instruction immediately preceding each of the successor instructions.

7. 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:

a program verifier, stored in the memory, for verifying that any specified program meets predefined data type and program stack usage restrictions, the specified program including a sequence of instructions, where each of a subset of the instructions each represents an operation on data of a specific data type;

each instruction in the subset having associated data type restrictions on the data type of data to be manipulated by that instruction;

the program verifier including data type testing instructions for determining whether execution of any instruction in a specified program would violate data type restrictions, if any, for that instruction and generating a program fault signal when execution of any instruction in the specified program would violate the data type restrictions for that instruction;

the data type testing instructions including;

instructions for storing, for each instruction in the specified program, a data type snapshot, the data type snapshot including data type information concerning data types associated with data stored in an operand stack and registers by the specified program immediately prior to execution of the corresponding instruction;

instructions for emulating operation of a selected instruction in the specified program by;

analyzing stack and register usage by the selected instruction so as to generate a current data type usage map for the operand stack and registers, determining all successor instructions to the selected instruction, merging the current data type usage map with the data type snapshot of the determined successor instructions, and marking for further analysis each of the determined successor instructions whose data type snapshot is modified by said merging;

instructions for emulating operation of each of the instructions marked for further analysis and unmarking each emulated instruction; and

instructions for continuing to emulate operation of any instructions marked for further analysis until there are no marked instructions;

the data type testing instructions including instructions for determining when the stack and register usage by the instruction would violate the data type restrictions for that instruction and generating a program fault signal when execution of the instruction would violate the data type restrictions.

8. The computer program product of claim 7, including:

program execution enabling instructions that enable execution of the specified program only after processing the specified program by the program verifier generates no program fault signals; and

a program interpreter, coupled to the specified program enabling instructions, for executing the specified program after processing of the specified program by the program verifier and after the specified program enabling instructions enable execution of the specified program by the program interpreter;

the program interpreter including instructions for executing the specified program without performing data type checks on operands stored in the operand stack.

9. The computer program product of claim 8,

the data type testing instructions including stack overflow/underflow testing instructions for determining whether execution of any loop in the specified program would result in a net addition or deletion of operands to the operand stack, and for generating a program fault signal when execution of any loop in the specified program would produce a net addition or deletion of operands to the operand stack;

and

the executing instructions of the program interpreter including instructions for executing the specified program without performing operand stack underflow and overflow checks during execution of the specified program.

10. The computer program product of claim 7,

the specified program including at least one object creation instruction and at least one object initialization instruction;

the data type testing instructions including instructions for storing in the current usage data map, for each object that would be stored in the operand stack and registers after execution of the selected instruction, a data type value for each uninitialized object that is distinct from a corresponding data type value for the same object after initialization thereof;

the data type testing instructions further including instructions for generating, when the selected instruction is not the at least one object initialization instruction, a program fault signal when execution of the selected instruction would access a stack operand or register whose data type corresponds to an uninitialized object.

11. The computer program product of claim 10,

the data type testing instructions further including instructions for generating, when the selected instruction is the at least one object initialization instruction, a program fault signal when execution of the selected instruction would access a stack operand or register whose data type corresponds to an initialized object.

12. The computer program product of claim 7,

the specified program including at least one jump to subroutine (jsr) instruction and at least one subroutine return (ret) instruction located within a subroutine included in the specified program;

the data type testing instructions including instructions for determining, when the selected instruction is the subroutine return instruction, each of the successor instructions to be an instruction immediately following a jsr instruction for jumping to the subroutine;

the data type testing instructions including instructions for merging, when the selected instruction is the subroutine return instruction, the current data type usage map with the data type snapshot of each of the determined successor instructions by storing in the data type snapshot for each successor instruction data type information from the current data type usage map for each register accessed and each register modified by the subroutine and data type information for each other register from the data type snapshot for the jsr instruction immediately preceding each successor instruction.

13. A computer data signal embodied in a carrier wave, comprising:

a program verifier, stored in the memory, for verifying that any specified program meets predefined data type and program stack usage restrictions, the specified program including a sequence of instructions, where each of a subset of the instructions each represents an operation on data of a specific data type;

each instruction in the subset having associated data type restrictions on the data type of data to be manipulated by that instruction;

the program verifier including data type testing instructions for determining whether execution of any instruction in a specified program would violate data type restrictions, if any, for that instruction and generating a program fault signal when execution of any instruction in the specified program would violate the data type restrictions for that instruction;

the data type testing instructions including;

instructions for storing, for each instruction in the specified program, a data type snapshot, the data type snapshot including data type information concerning data types associated with data stored in an operand stack and registers by the specified program immediately prior to execution of the corresponding instruction;

instructions for emulating operation of a selected instruction in the specified program by;

analyzing stack and register usage by the selected instruction so as to generate a current data type usage map for the operand stack and registers, determining all successor instructions to the selected instruction, merging the current data type usage map with the data type snapshot of the determined successor instructions, and marking for further analysis each of the determined successor instructions whose data type snapshot is modified by said merging;

instructions for emulating operation of each of the instructions marked for further analysis and unmarking each emulated instruction; and

instructions for continuing to emulate operation of any instructions marked for further analysis until there are no marked instructions;

the data type testing instructions including instructions for determining when the stack and register usage by the instruction would violate the data type restrictions for that instruction and generating a program fault signal when execution of the instruction would violate the data type restrictions.

14. The computer data signal of claim 13, including:

program execution enabling instructions that enable execution of the specified program only after processing the specified program by the program verifier generates no program fault signals; and

a program interpreter, coupled to the specified program enabling instructions, for executing the specified program after processing of the specified program by the program verifier and after the specified program enabling instructions enable execution of the specified program by the program interpreter;

the program interpreter including instructions for executing the specified program without performing data type checks on operands stored in the operand stack.

15. The computer data signal of claim 14,

the data type testing instructions including stack overflow/underflow testing instructions for determining whether execution of any loop in the specified program would result in a net addition or deletion of operands to the operand stack, and for generating a program fault signal when execution of any loop in the specified program would produce a net addition or deletion of operands to the operand stack;

and

the executing instructions of the program interpreter including instructions for executing the specified program without performing operand stack underflow and overflow checks during execution of the specified program.

16. The computer data signal of claim 13,

the specified program including at least one object creation instruction and at least one object initialization instruction;

the data type testing instructions including instructions for storing in the current usage data map, for each object that would be stored in the operand stack and registers after execution of the selected instruction, a data type value for each uninitialized object that is distinct from a corresponding data type value for the same object after initialization thereof;

the data type testing instructions further including instructions for generating, when the selected instruction is not the at least one object initialization instruction, a program fault signal when execution of the selected instruction would access a stack operand or register whose data type corresponds to an uninitialized object.

17. The computer data signal of claim 16,

the data type testing instructions further including instructions for generating, when the selected instruction is the at least one object initialization instruction, a program fault signal when execution of the selected instruction would access a stack operand or register whose data type corresponds to an initialized object.

18. The computer data signal of claim 13,

the specified program including at least one jump to subroutine (jsr) instruction and at least one subroutine return (ret) instruction located within a subroutine included in the specified program;

the data type testing instructions including instructions for determining, when the selected instruction is the subroutine return instruction, each of the successor instructions to be an instruction immediately following a jsr instruction for jumping to the subroutine;

the data type testing instructions including instructions for merging, when the selected instruction is the subroutine return instruction, the current data type usage map with the data type snapshot of each of the determined successor instructions by storing in the data type snapshot for each successor instruction data type information from the current data type usage map for each register accessed and each register modified by the subroutine and data type information for each other register from the data type snapshot for the jsr instruction immediately preceding each successor instruction.