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

• US 7,080,363 B2
• Filed: 11/05/2002
• Issued: 07/18/2006
• 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): CHAVIS, JOHN Q
• Application Number:
  US10/288,323
• Publication Number:
  US 20030135844A1
• Time in Patent Office: 1,351 Days
• Field of Search: 717/138, 717/139
• US Class Current: 717/139
• 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 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 mechanism comprising:

a program verifier 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;

said data type testing instructions including;

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

instructions for emulating operation of each of said instructions, including instructions for emulating operation of a selected instruction in the program by;

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

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

2. A method, comprising:

receiving from a source computer a program formed of low-level program code;

verifying prior to execution that when an instruction of the program is executed that can be executed along more than one execution path, a data type requirement of that instruction is satisfied and a number of operands on a stack is identical, regardless of the execution path taken to arrive at the instruction; and

executing the verified program.

3. The method of claim 2, wherein the receiving includes selectively connecting a computer system via a network to the source computer to receive from the source computer the program formed of low-level program code.

4. The method of claim 2, wherein the verifying includes confirming prior to execution of the program that the number of operands on the stack when arriving at the instruction that can be executed along more than one execution path is identical for all execution paths that include the instruction, even when the stack is not empty prior to execution of the instruction.

5. The method of claim 2, wherein the verifying includes confirming prior to execution of the program that execution of any loop in the program will not result in a net addition or deletion of operands on the stack.

6. The method of claim 3, wherein when the program is executed no check is made for overflow and underflow of the stack.

7. The method of claim 2, wherein the verifying includes verifying prior to execution that when a loop of the program is executed, immediately before and after each iteration of the loop, a number of operands on the stack is identical, even when the stack is not empty, and a set of types associated with the operands, if any, on the stack remains compatible with an initial set of types associated with the operands on the stack regardless of how many times the loop is executed.

8. The method of claim 2, wherein the executing includes executing the program without performing a check during execution of the program that corresponds to a check performed by the verifying.

9. The method of claim 2, wherein each instruction of the program comprises one or more bytecodes, and wherein the verifying includes determining whether execution of any bytecoded instruction in the program would violate predetermined data type restrictions for that instruction.

10. The method of claim 2, wherein at least one instruction of the program comprises one or more bytecodes that represent an operation on a specific data type and is selected from the group consisting of:

aaload, aastore, aconst_null, aload, aretum, arraylength, astore, astore_<

n>

, athrow, bipush, breakpoint, catchsetup, catchteardown, checkcast, df2, d2i, d2l, dadd, daload, dastore, dcmpg, dcnipl dconst_<

d>

, ddiv, dload, dload_<

ci>

, dmod, dmul, dneg, dretum, dstore, dstore_<

n>

, dsub, dup, dup2, dup2_—

×

1, dup2_—

×

2, dup_—

×

1, dup_—

×

2, f2d, f2i, f2l, fadd, faload, fastore, fempg, femp1, fconst_<

f>

, fdiv, fload, fload_<

n>

, fmod, fmul, fneg, freturn, fstore, fstore_<

n>

, fsub, gatfield, getstatic, goto, i2d, i2f, i2l, iadd, iaload, iand, iastore, iconst_<

n>

, iconst_m1, idiv, if_acmpeq, if_acmpne, if_icmpeq, if_icmpge, if_icmpgt, if_icmple, if_icmplt, if_icmpne, ifeq, ifge, ifgt, ifle, iflt, ifne, iinc, iload, iload_<

n>

, imod, imul, meg, instanceof, int2byte, int2char, invokeinterface, invokemethod, invokesuper, ior, ireturn, isbi, Ishr, istore, istore_<

n>

, isub, iushr, ixor, jsr, l2d, l2f, l2i, lacid, laload, land, lastore, lcmp, lconst_<

l>

, Icic1, ldc2, ldc2w, ldiv, lload, load_<

n>

, Imod, lmul, lneg, lookupswitch, lor, lreturn, lsbi, lshr, Istore, lstore_<

n>

, lsub, lusbr, lxor, monitorenter, monitorexit, new, newarray, newfronmame, nop, pop, pop2, putfield, putstatic, ret, return, saboad, sastore, siaboad, siastore, sipush, tableswitch, and verifystack.

11. The method of claim 2, wherein the verifying includes certifying that the program complies with a stack non-overflow constraint and a stack non-underflow constraint.

12. The method of claim 2, wherein the verifying includes using a virtual stack to track a set of types associated with operands, if any, on the stack.

13. The method of claim 2, wherein the verifying includes using an array of virtual local variables to track a set of types associated with local variables used by the program.

14. A computer system, comprising:

memory for storing a program formed of low-level program code;

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

a program verifier, stored in the memory and executed by the data processing unit, the program verifier including instructions for verifying prior to execution that when an instruction of the program is executed that can be executed along more than one execution path, a data type requirement of that instruction is satisfied and a number of operands on a stack is identical, regardless of the execution path taken to arrive at the instruction; and

a program execution module for executing the verified program.

15. A computer system, comprising:

means for selectively connecting the computer system via a network to a sending computer to receive from the sending computer a program formed of low-level program code;

memory for storing the program;

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

a program verifier, stored in the memory and executed by the data processing unit, the program verifier including instructions for verifying prior to execution that when an instruction of the program is executed that can be executed along more than one execution path, a data type requirement of that instruction is satisfied and a number of operands on a stack is identical, regardless of the execution path taken to arrive at the instruction; and

a program execution module for executing the verified program.

16. The computer system of claim 15, wherein the verifying instructions include instructions for confirming prior to execution of the program that the number of operands on the stack when arriving at the instruction that can be executed along more than one execution path is identical for all execution paths that include the instruction, even when the stack is not empty prior to execution of the instruction.

17. The computer system of claim 15, wherein the verifying instructions include instructions for confirming prior to execution of the program that execution of any loop in the program will not result in a net addition or deletion of operands on the stack.

18. The computer system of claim 17, wherein the program execution module does not check for overflow and underflow of the stack when executing the verified program.

19. The computer system of claim 15, wherein the verifying instructions include instructions for verifying prior to execution that when a loop of the program is executed, immediately before and after each iteration of the loop, a number of operands on the stack is identical, even when the stack is not empty, and a set of types associated with the operands, if any, on the stack remains compatible with an initial set of types associated with the operands on the stack regardless of how many times the loop is executed.

20. The computer system of claim 15, wherein the program execution module includes instructions for executing the program without performing a check during execution of the program that corresponds to a check performed by the program verifier.

21. The computer system of claim 15, wherein each instruction of the program comprises one or more bytecodes, and wherein the program verifier includes instructions for determining whether execution of any bytecoded instruction in the program would violate predetermined data type restrictions for that instruction.

22. The computer system of claim 15, wherein at least one instruction of the program comprises one or more bytecodes that represent an operation on a specific data type and is selected from the group consisting of:

aaload, aastore, aconst_null, aload, areturn, arraylength, astore, astore_<

n>

, athrow, bipush, breakpoint, catchsetup, catchteardown, checkcast, df2, d2i, d2l, dadd, daload, dastore, dcmpg, dcmpl, dconst_<

ci>

, ddiv, dload, dload_<

d>

, dmod, dmul, dneg, dreturn, dstore, dstore_<

n>

, dsub, chip, dup2, dup2_—

×

1, dup2_—

×

2, dup_—

×

1, dup_—

×

2, f2d, f2i, f2l, facid, faload, fastore, feznpg, fempl, fconst_<

f>

, fdiv, fload, fload_<

n>

, fmod, fmul, fneg, freturn, fstore, fstore_<

n>

, fsub, gatfield, getstatic, goto, i2d, i2f, i2l, iadd, iaload, iand, iastore iconst_<

n>

, iconst_m1, idiv, if_acmpeq, if_acmpne, if_icmpeq, if_icmpge, if_icmpgt, if_icmple, if_icmplt, if_icmpne, ifeq, ifge, ifgt, ifle, ifit, ifne, iinc, iload, iload_<

n>

, imod, imul, ineg, instanceof, int2byte, int2cbar, invokeinterface, invokemethod, invokesuper, ior, ireturn, ishl, Ishr, istore, istore_<

n>

, isub, iushr, ixor, jsr, l2d, l2f, l2i, ladd, laload, land, lastore, Icrup, lconst_<

l>

, ldc1, ldc2, ldc2w, ldiv, lload, lload_<

n>

, lmod, lmul, lneg, lookupswitch, lor, lreturn, lshl, lshr, lstore, lstore_<

n>

, lsub, lusbr, lxor, monitorenter, monitorexit, new, newarray, newfromname, flop, pop, pop2, putfield, putstatic, ret, return, saload, sastore, siaboad, siastore, sipush, tableswitch, and verifystack.

23. The computer system of claim 15, wherein the program verifier includes instructions for certifying that the program complies with a stack non-overflow constraint and a stack non-underflow constraint.

24. The computer system of claim 15, wherein the program verifier includes instructions using a virtual stack to track a set of types associated with operands, if any, on the stack.

25. The computer system of claim 15, wherein the program verifier includes instructions using an array of virtual local variables to track a set of types associated with local variables used by the program.

26. 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, for analyzing a program formed of low-level, program code;

the program verifier including instructions for verifying prior to execution of the program that when an instruction of the program is executed that can be executed along more than one execution path, a data type requirement of that instruction is satisfied and a number of operands on a stack is identical, regardless of the execution path taken to arrive at the instruction; and

a program execution module for executing the verified program.

27. The computer program product of claim 26, wherein the verifying instructions include instructions for confirming prior to execution of the program that the number of operands on the stack when arriving at the instruction that can be executed along more than one execution path is identical for all execution paths that include the instruction, even when the stack is not empty prior to execution of the instruction.

28. The computer program product of claim 26, wherein the verifying instructions include instructions for confirming prior to execution of the program that execution of any loop in the program will not result in a net addition or deletion of operands on the stack.

29. The computer program product of claim 26, wherein the program execution module does not check for overflow and underflow of the stack when executing the verified program.

30. The computer program product of claim 26, wherein the verifying instructions include instructions for verifying prior to execution that when a loop of the program is executed, immediately before and after each iteration of the loop, a number of operands on the stack is identical, even when the stack is not empty, and a type associated with each of the operands on the stack is compatible regardless of how many times the loop is executed.

31. The computer program product of claim 30, wherein the program execution module includes instructions for executing the program without performing a check during execution of the program that compounds to a check performed by the program verifier.

32. The computer program product of claim 26, wherein each instruction of the program comprises one or more bytecodes, and wherein the program verifier includes instructions for determining whether execution of any bytecoded instruction in the program would violate predetermined data type restrictions for that instruction.

33. The computer program product of claim 26, wherein at least one instruction of the program comprises one or more bytecodes that represent an operation on a specific data type and is selected from the group consisting of:

aaload, aastore, aconst_null, aload, areturn, arraylength, astore, astore_<

n<

, athrow, bipush, breakpoint, catchsetup, catchteardown, checkcast, df2, d2i, d2l, dadd, daload, dastore, dcinpg, dcmpl, dconst_<

d>

, ddiv, dload, dload_<

d>

, dmod, dmul, dneg, dreturn, dstore, dstore_<

n>

, dsub, dup, dup2, dup2_—

×

1, dup2_—

×

2, dup_—

×

1, dup_—

×

2, f2d, f2i, f2l, fadd, faload, fastore, fempg, fempl, fconst_<

f>

, fdiv, fload, fload_<

n>

, fmod, fmul, flieg, freturn, fstore, fstore_<

n>

, fsub, gatfield, getstatic, goto, i2d, i2f, i2l, iadd, iaload, iand, iastore, iconst_<

n>

, iconst_m1, idiv, if_acmpeq, if_acmpne, if_icmpeq, if_icmpge, if_icmpgt, if_icmple, if_icmplt, if_icmpne, ifeq, ifge, ifgt, ifie, ifit, iflie, iinc, iload, iload_<

n>

, imod, imul, ineg, instanceof, int2byte, int2char, invokeinterface, invokemethod, invokesuper, ior, ireturn, ishl, Ishr, istore, istore_<

n>

, isub, iushr, ixor, jsr, l2d, l2f, l2i, ladd, laload, land, lastore, lcmp, lconst_—

<

1>

, ldc1, ldc2, ldc2w, ldiv, lload, lload_<

n>

, lmod, lmul, lneg, lookupswitch, lor, lreturn, lshl, lshr, lstore, lstore_<

n>

, lsub, lushr, lxor, monitorenter, monitorexit, new, newarray, newfromname, flop, pop, pop2, putfield, putstatic, ret, return, saload, sastore, siaload, siastore, sipush, tableswitch, and verifystack.

34. The computer program product of claim 26, wherein the program verifier includes instructions for certifying that the program complies with a stack non-overflow constraint and a stack non-underflow constraint.

35. The computer program product of claim 26, wherein the program verifier includes instructions using a virtual stack to track a set of types associated with operands, if any, on the stack.

36. The computer program product of claim 26, wherein the program verifier includes instructions using an array of virtual local variables to track set of types associated with local variables used by the program.

37. A method, comprising:

receiving from a source computer a program formed of low-level program code;

verifying prior to execution that when an instruction of the program is executed that can be executed along more than one execution path, a number of operands on a stack is identical and a data type state associated with the stack is compatible with the instruction, regardless of the execution path taken to arrive at the instruction; and

executing the verified program.

38. The method of claim 37, wherein the receiving includes selectively connecting a computer system via a network to the source computer to receive from the source computer a program formed of low-level program code.

39. The method of claim 37, the verifying including confirming prior to execution of the program that the number of operands on the stack when arriving at the instruction that can be executed along more than one execution path is identical for all execution paths that include the instruction, even when the stack is not empty prior to execution of the instruction.

40. The method of claim 37, the verifying including confirming prior to execution of the program that execution of any loop in the program will not result in a net addition or deletion of operands on the stack.

41. The method of claim 37, the verifying including confirming prior to execution of the program that when a loop of the program is executed, immediately before and after each iteration of the loop, a number of operands on the stack is identical, even when the stack is not empty, and a type associated with each of the operands on the stack is compatible regardless of how many times the loop is executed.

42. The method of claim 41, including executing the program without performing a check during execution of the program that corresponds to a check performed by the verifying prior to execution of the program.

43. The method of claim 41, wherein each instruction of the program comprises one or more bytecodes, and wherein the computer system determines prior to execution of the program whether execution of any bytecoded instruction in the program would violate predetermined data type restrictions for that instruction.

44. The method of claim 41, wherein at least one instruction of the program comprises one or more bytecodes that represent an operation on a specific data type and is selected from the group consisting of:

aaload, aastore, aconst_null, aload, areturn, arraylength, astore, astore_<

n>

, athrow, bipush, breakpoint, catchsetup, catchteardown, checkcast, df2, d2i, d2l, dadd, daload, dastore, dcmpg, dcmpl dconst_<

d>

, ddiv, dload, dload_<

d>

, dmod, dmul, dneg, dreturn, dstore, dstore_<

n>

, dsub, dup, dup2, dup2_—

×

1, dup2_—

×

2, dup_—

×

1, dup_—

×

2, f2d, f2i, f2l, fadd, faload, fastore, fempg, fempl, fconst_<

f>

, fdiv, fload, fload_<

n>

, fmod, fmul, fneg, freturn, fstore, fstore_<

n>

, fsub, gatfield, getstatic, goto, i2d, i2f, i2l, iadd, iaload, iand, iastore, iconst_<

n>

, iconst_m1, idiv, if_acmpeq, if_acmpne, if_icmpeq, if_icmpge, if_icmpgt, if_icmple, if_icmplt, if_icmpne, ifeq, ifge, ifgt, ifle, iflt, ifne, iinc, iload, iload_<

n>

, imod, imul, ineg, instanceof, int2byte, int2char, invokeinterface, invokemethod, invokesuper, ior, ireturn, ishl, Ishr, istore, istore_<

n>

, isub, iushr, ixor, jsr, l2d, l2f, l2i, ladd, laload, land, lastore, lcmp, lconst_<

l>

, ldc1, ldc2, ldc2w, ldiv, lload, lload_<

n>

, lmod, lmul, lneg, lookupswitch, lor, lreturn, lshl, lshr, lstore, lstore_<

n>

, lsub, lushr, lxor, monitorenter, monitorexit, new, newarray, new fromname, nop, pop, pop2, putfield, putstatic, ret, return, saload, sastore, siaload, siastore, sipush, tableswitch, and verifystack.

45. The method of claim 37, the verifying including, prior to execution of the program, verifying that the program complies with a stack non-overflow constraint and a stack non-underflow constraint.

46. The method of claim 37, the verifying including, prior to execution of the program, using a virtual stack to track a set of types associated with operands, if any, on the stack during execution of the program.

47. The method of claim 37, the verifying including, prior to execution of the program, using an array of virtual local variables to track a set of types associated with local variables used during execution of the program.

48. A computer system, comprising:

memory for storing a program formed of low-level program code;

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

a program verifier, stored in the memory and executed by the data processing unit, the program verifier including instructions for verifying, prior to execution, that when an instruction of the program is executed that can be executed along more than one execution path, a number of operands on a stack is identical and a data type state associated with the stack is compatible with the instruction, regardless of the execution path taken to arrive at the instruction; and

a program execution module for executing the verified program.

49. A computer system, comprising:

means for selectively connecting the computer system via a network to a sending computer to receive from the sending computer a program formed of low-level program code;

memory for storing the program;

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

a program verifier, stored in the memory and executed by the data processing unit, the program verifier including instructions for verifying, prior to execution, that when an instruction of the program is executed that can be executed along more than one execution path, a number of operands on a stack is identical and a data type state associated with the stack is compatible with the instruction, regardless of the execution path taken to arrive at the instruction; and

a program execution module for executing the verified program.

50. The computer system of claim 49, wherein the verifying instructions include instructions for confirming prior to execution of the program that the number of operands on the stack when arriving at the instruction that can be executed along more than one execution path is identical for all execution paths that include the instruction, even when the stack is not empty prior to execution of the instruction.

51. The computer system of claim 49, wherein the verifying instructions include instructions for confirming prior to execution of the program that execution of any loop in the program will not result in a net addition or deletion of operands on the stack.

52. The computer system of claim 49, wherein the verifying instructions include instructions for verifying prior to execution that when a loop of the program is executed, immediately before and after each iteration of the loop, a number of operands on the stack is identical, even when the stack is not empty, and a type associated with each of the operands on the stack is compatible regardless of how many times the loop is executed.

53. The computer system of claim 52, including a program execution module having instructions for executing the program without performing a check during execution of the program that corresponds to a check performed by the program verifier.

54. The computer system of claim 49, wherein each instruction of the program comprises one or more bytecodes, and wherein the program verifier includes instructions for determining whether execution of any bytecoded instruction in the program would violate predetermined data type restrictions for that instruction.

55. The computer system of claim 49, wherein at least one instruction of the program comprises one or more bytecodes that represent an operation on a specific data type and is selected from the group consisting of:

aaload, aastore, aconst_null, aload, areturn, arraylength, astore, astore_<

n>

, athrow, bipush, breakpoint, catchsetup, catchteardown, checkcast, df2, d2i, d2l, dadd, daload, dastore, dcmpg, dcmpl, dconst_<

d>

, ddiv, dload, dload_<

d>

, dmod, dmul, dneg, dreturn, dstore, dstore_<

n>

, dsub, dup, dup2, dup2_—

×

1, dup2_—

×

2, dup_—

×

1, dup_—

×

2, f2d, f2i, f2l, fadd, faload, fastore, fempg, fempl, fconst_<

f>

, fdiv, fload, fload_<

n>

, fmod, fmul, fneg, freturn, fstore, fstore_<

n>

,fsub, gatfield, getstatic, goto, i2d, i2f, i2l, iadd, iaload, iand, iastore iconst_<

n>

, iconst_m1, idiv, if_acmpeq, if_acmpne, if_icmpeq, if_icmpge, if_icmpgt, if_icmple, if_icmplt, if_icmpne, ifeq, ifge, ifgt, ifle, ifit, ifne, iinc, iload, iload_<

n>

, imod, imul, ineg, instanceof, int2byte, int2char, invokeinterface, invokemethod, invokesuper, ior, ireturn, ishi, Ishr, istore, istore_<

n>

, isub, iushr, ixor,jsr, l2d, l2f, l2i, ladd, laload, land, lastore, lcmp, lconst_—

<

1>

, ldc1, ldc2, ldc2w, ldiv, lload, lload_<

n>

, lmod, lmul, lneg, lookupswitch, lor, lreturn, lshl, lshr, lstore, lstore_<

n>

, lsub, lusbr, lxor, monitorenter, monitorexit, new, newarray, newfromname, nop, pop, pop2, putfield, putstatic, ret, return, saload, sastore, siaload, siastore, sipush, tableswitch, and verifystack.

56. The computer system of claim 49, wherein the program verifier includes instructions for certifying that the program complies with a stack non-overflow constraint and a stack non-underflow constraint.

57. The computer system of claim 49, wherein the program verifier includes instructions using a virtual stack to track the type state of the stack.

58. The computer system of claim 49, wherein the program verifier includes instructions using an array of virtual local variables to track a type state of local variables used by the program.

59. 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 for analyzing a program formed of low-level program code, the program verifier including instructions for verifying, prior to execution, that when an instruction of the program is executed that can be executed along more than one execution path, a number of operands on a stack is identical and a data type state associated with the stack is compatible with the instruction, regardless of the execution path taken to arrive at the instruction; and

a program execution module for executing the verified program.

60. The computer program product of claim 59, wherein the verifying instructions include instructions for confirming prior to execution of the program that a number of operands on the stack when arriving at the instruction that can be executed along more than one execution path is identical for all execution paths that include the instruction, even when the stack is not empty prior to execution of the instruction.

61. The computer program product of claim 59, wherein the verifying instructions include instructions for confirming prior to execution of the program that execution of any loop in the program will not result in a net addition or deletion of operands on the stack.

62. The computer program product of claim 59, wherein the verifying instructions include instructions for verifying prior to execution that when a loop of the program is executed, immediately before and after each iteration of the loop, a number of operands on the stack is identical, even when the stack is not empty, and a type associated with each of the operands on the stack is compatible regardless of how many times the loop is executed.

63. The computer program product of claim 62, further including a program execution module having instructions for executing the program without performing a check during execution of the program that corresponds to a check performed by the program verifier.

64. The computer program product of claim 59, wherein each instruction of the program comprises one or more bytecodes, and wherein the program verifier includes instructions for determining whether execution of any bytecoded instruction in the program would violate predetermined data type restrictions for that instruction.

65. The computer program product of claim 59, wherein at least one instruction of the program comprises one or more bytecodes that represent an operation on a specific data type and is selected from the group consisting of:

aaload, aastore, aconst_null, aload, areturn, arraylength, astore, astore_<

n>

, athrow, bipush, breakpoint, catchsetup, catchteardown, checkcast, df2, d2i, d2l, dadd, daload, dastore, dcmpg, dcmpl, dconst_<

d>

, ddiv, dload_<

d>

, dmod, dmul, dneg, dreturn, dstore, dstore_<

n>

, dsub, dup, dup2, dup2_—

×

1, dup2_—

×

2, dup_—

×

1, dup_—

×

2, f2d, f2i, f2l, fadd, faload, fastore, fempg, fempl, fconst_<

f>

, fdiv, fload, fload_<

n>

, fmod, fmul, fneg, freturn, fstore, fstore_<

n>

, fsub, gatfield, getstatic, goto, i2d, i2f, i2l, iadd, iaload, iand, iastore, iconst_<

n>

, iconst_m1, idiv, if_acmpeq, if_acmpne, if_icmpeq, if_icmpge, if_icmpgt, if_icmple, if_icmplt, if_icmpne, ifeq, ifge, ifgt, ifle, iflt, ifne, iinc, iload, iload_<

n>

, imod, imul, ineg, instanceof, int2byte, int2char, invokeinterface, invokemethod, invokesuper, ior, ireturn, ishl, Ishr, istore, istore_<

n>

, isub, iushr, ixor, jsr, l2d, l2f, l2i, ladd, laload, land, lastore, lcmp, lconst_—

<

1>

, ldc1, ldc2, ldc2w, ldiv, lload, lload_<

n>

, lmod, Imul, lneg, lookupswitch, lor, lreturn, lshl, lshr, lstore, lstore_<

n>

, lsub, lushr, lxor, monitorenter, monitorexit, new, newarray, newfromname, nop, pop, pop2, putfield, putstatic, ret, return, saload, sastore, siaload, siastore, sipush, tableswitch, and verifystack.

66. The computer program product of claim 59, wherein the program verifier includes instructions for certifying that the program complies with a stack non-overflow constraint and a stack non-underflow constraint.

67. The computer program product of claim 59, wherein the program verifier includes instructions using a virtual stack to track the type state of the stack.

68. The computer program product of claim 59, wherein the program verifier includes instructions using an array of virtual local variables to track a type state of local variables used by the program.

69. 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, for analyzing a program formed of low-level, program code;

the program verifier including instructions for verifying prior to execution of the program that when an instruction of the program that can be executed along more than one execution path is executed by the computer system, a number of operands on a stack associated with that instruction is identical regardless of the execution path taken to arrive at the instruction, and a type associated with each of the operands on the stack for a first execution path that includes the instruction is compatible with a respective type associated with each of the operands on the stack for all other execution paths that include the instruction;

a program execution module for executing the verified program.

70. The computer program product of claim 69, wherein the verifying instructions include instructions for confirming prior to execution of the program that a number of operands on the stack when arriving at the instruction that can be executed along more than one execution path is identical for all execution paths that include the instruction, even when the stack is not empty prior to execution of the instruction.

71. The computer program product of claim 69, wherein the verifying instructions include instructions for confirming prior to execution of the program that execution of any loop in the program will not result in a net addition or deletion of operands on the stack.

72. The computer program product of claim 69, wherein the verifying instructions include instructions for verifying prior to execution that when a loop of the program is executed, immediately before and after each iteration of the loop, a number of operands on the stack is identical, even when the stack is not empty, and a type associated with each of the operands on the stack is compatible regardless of how many times the loop is executed.

73. The computer program product of claim 72, further including a program execution module having instructions for executing the program without performing a check during execution of the program that corresponds to a check performed by the program verifier.

74. The computer program product of claim 69, wherein each instruction of the program comprises one or more bytecodes, and wherein the program verifier includes instructions for determining whether execution of any bytecoded instruction in the program would violate predetermined data type restrictions for that instruction.

75. The computer program product of claim 69, wherein at least one instruction of the program comprises one or more bytecodes that represent an operation on a specific data type and is selected from the group consisting of:

aaload, aastore, aconst_null, aload, areturn, arraylength, astore, astore_<

n>

, athrow, bipush, breakpoint, catchsetup, catchteardown, checkcast, df2, d2i, d2l, dadd, daload, dastore, dcmpg, dcmpl dconst_<

d>

, ddiv, dload, dload_<

d>

, dmod, dmul, dneg, dreturn, dstore, dstore_<

n>

, dsub, dup, dup2, dup2_—

×

1, dup2_—

×

2, dup_—

×

1, dup_—

×

2, f2d, f2i, f2l, fadd, faload, fastore, fempg, fempl, fconst_<

f>

, fdiv, fload, fload_<

n>

, fmod, fmul, fneg, freturn, fstore, fstore_<

n>

, fsub, gatfield, getstatic, goto, i2d, i2f, i2l, iadd, iaload, iand, iastore, iconst_<

n>

, iconst_m1, idiv, if_acmpeq, if_acmpne, if_icmpeq, if_icmpge, if_icmpgt, if_icmple, if_icmplt, if_icmpne, ifeq, ifge, ifgt, ifle, iflt, ifne, iinc, iload, iload_<

n>

, imod, imul, ineg, instanceof, int2byte, int2char, invokeinterface, invokemethod, invokesuper, ior, ireturn, ishl, Ishr, istore, istore_<

n>

, isub, iushr, ixor, jsr, l2d, l2f, l2i, ladd, laload, land, lastore, lcmp, lconst_<

l>

, ldc1, ldc2, ldc2w, ldiv, lload, lload_<

n>

, lmod, lmul, lneg, lookupswitch, lor, lreturn, lshl, lshr, lstore, lstore_<

n>

, lsub, lushr, lxor, monitorenter, monitorexit, new, newarray, newfromname, nop, pop, pop2, putfield, putstatic, ret, return, saload, sastore, siaload, siastore, sipush, tableswitch, and verifystack.

76. The computer program product of claim 69, wherein the program verifier includes instructions for certifying that the program complies with a stack non-overflow constraint and a stack non-underflow constraint.

77. The computer program product of claim 69, wherein the program verifier includes instructions using a virtual stack to track a type associated with each of the operands on the stack.

78. The computer program product of claim 69, wherein the program verifier includes instructions using an array of virtual local variables to track a type associated with each of a plurality of local variables used by the program.

79. A method, comprising:

receiving from a source computer a program formed of low-level program code;

verifying prior to execution that when an instruction of the program is executed that can be executed along more than one execution path, a number of operands on a stack associated with that instruction is identical regardless of the execution path taken to arrive at the instruction, and a type associated with each of the operands on the stack for a first execution path that includes the instruction is compatible with a respective type associated with each of the operands on the stack for all other execution paths that include the instruction; and

executing the verified program.

80. The method of claim 79, wherein the receiving includes selectively connecting a computer system via a network to the source computer to receive from the source computer the program formed of low-level program code.

81. The method of claim 79, wherein the verifying includes confirming prior to execution of the program that the number of operands on the stack when arriving at the instruction that can be executed along more than one execution path is identical for all execution paths that include the instruction, even when the stack is not empty prior to execution of the instruction.

82. The method of claim 79, wherein the verifying includes confirming prior to execution of the program that execution of any loop in the program will not result in a net addition or deletion of operands on the stack.

83. The method of claim 79, wherein when the program is executed no check is made for overflow and underflow of the stack.

84. The method of claim 79, wherein the verifying includes verifying prior to execution that when a loop of the program is executed, immediately before and after each iteration of the loop, a number of operands on the stack is identical, even when the stack is not empty, and a type associated with each of the operands on the stack remains compatible with an initial type associated with each of the operands on stack regardless of how many times the loop is executed.

85. The method of claim 84, wherein the executing includes executing the program without performing a check during execution of the program that corresponds to a check performed by the verifying.

86. The method of claim 79, wherein each instruction of the program comprises one or more bytecodes, and wherein the verifying includes determining whether execution of any bytecoded instruction in the program would violate predetermined data type restrictions for that instruction.

87. The method of claim 79, wherein at least one instruction of the program comprises one or more bytecodes that represent an operation on a specific data type and is selected from the group consisting of:

aaload, aastore, aconst_null, aload, areturn, arraylength, astore, astore_<

n>

, athrow, bipush, breakpoint, catchsetup, catchteardown, checkcast, df2, d2i, d2l, dadd, daload, dastore, dcmpg, dcmpl dconst_<

d>

, ddiv, dload, dload_<

d>

, dmod, dmul, dneg, dreturn, dstore, dstore_<

n>

, dsub, dup, dup2, dup2_—

×

1, dup2_—

×

2, dup_—

×

1, dup_—

×

2, f2d, f2i, f2l, fadd, faload, fastore, fempg, fempi, fconst_<

f>

, fdiv, fload, fload_<

n>

, fmod, fmul, fneg, freturn, fstore, fstore_<

n>

, fsub, gatfield, getstatic, goto, i2d, i2f, i2l, iadd, iaload, iand, iastore, iconst_<

n>

, iconst_m1, idiv, if_acmpeq, if_acmpne, if_icmpeq, if_icmpge, if_icmpgt, if_icmple, if_icmplt, if_icmpne, ifeq, ifge, ifgt, ifle, iflt, ifne, iinc, iload, iload_<

n>

, imod, imul, ineg, instanceof, int2byte, int2char, invokeinterface, invokemethod, invokesuper, ior, ireturn, ishi, Ishr, istore, istore_<

n>

, isub, iushr, ixor, jsr, l2d, l2f, l2i, ladd, laload, land, lastore, lcmp, lconst_<

l>

, ldc1, ldc2, ldc2w, ldiv, lload, lload_<

n>

, lmod, lmul, lneg, lookupswitch, lor, lreturn, lshl, lshr, lstore, lstore_<

n>

, lsub, lushr, Ixor, monitorenter, monitorexit, new, newarray, newfromname, nop, pop, pop2, putfield, putstatic, ret, return, saload, sastore, siaload, siastore, sipush, tableswitch, and verifystack.

88. The method of claim 79, wherein the verifying includes certifying that the program complies with a stack non-overflow constraint and a stack non-underflow constraint.

89. The method of claim 79, wherein the verifying includes using a virtual stack to track a type associated with each of the operands on the stack.

90. The method of claim 79, wherein the verifying includes using an array of virtual local variables to track a set of types associated with local variables used by the program.

91. A computer system, comprising:

memory for storing a program formed of low-level program code;

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

a program verifier, stored in the memory and executed by the data processing unit;

the program verifier including instructions for verifying prior to execution that when an instruction of the program is executed that can be executed along more than one execution path, a number of operands on a stack associated with that instruction is identical regardless of the execution path taken to arrive at the instruction, and a type associated with each of the operands on the stack for a first execution path that includes the instruction is compatible with a respective type associated with each of the operands for all other execution paths that include the instruction; and

a program execution module for executing the verified program.

92. A computer system, comprising:

means for selectively connecting the computer system via a network to a sending computer to receive from the sending computer a program formed of low-level program code;

memory for storing the program;

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

a program verifier, stored in the memory and executed by the data processing unit, the program verifier including instructions for verifying prior to execution that when an instruction of the program is executed that can be executed along more than one execution path, a number of operands on a stack associated with that instruction is identical regardless of the execution path taken to arrive at the instruction, and a type associated with each of the operands on the stack for a first execution path that includes the instruction is compatible with a respective type associated with each of the operands for all other execution paths that include the instruction; and

a program execution module for executing the verified program.

93. The computer system of claim 92, wherein the verifying instructions include instructions for confirming prior to execution of the program that the number of operands on the stack when arriving at the instruction that can be executed along more than one execution path is identical for all execution paths that include the instruction, even when the stack is not empty prior to execution of the instruction.

94. The computer system of claim 92, wherein the verifying instructions include instructions for confirming prior to execution of the program that execution of any loop in the program will not result in a net addition or deletion of operands on the stack.

95. The computer system of claim 92, wherein the program execution module does not check for overflow and underflow of the stack when executing the verified program.

96. The computer system of claim 92, wherein the verifying instructions include instructions for verifying prior to execution that when a loop of the program is executed, immediately before and after each iteration of the loop, a number of operands on the stack is identical, even when the stack is not empty, and a set of types associated with the operands, if any, on the stack remains compatible with an initial set of types associated with the operands on the stack regardless of how many times the loop is executed.

97. The computer system of claim 92, wherein the program execution module includes instructions for executing the program without performing a check during execution of the program that corresponds to a check performed by the program verifier.

98. The computer system of claim 92, wherein each instruction of the program comprises one or more bytecodes, and wherein the program verifier includes instructions for determining whether execution of any bytecoded instruction in the program would violate predetermined data type restrictions for that instruction.

99. The computer system of claim 92, wherein at least one instruction of the program comprises one or more bytecodes that represent an operation on a specific data type and is selected from the group consisting of:

aaload, aastore, aconst_null, aload, aretum, arraylength, astore, astore_<

n>

, athrow, bipush, breakpoint, catchsetup, catchteardown, checkcast, df2, d2i, d2l, dadd, daload, dastore, dcmpg, dcmpl, dconst_<

d>

, ddiv, dload, dload_<

d>

, dmod, dmul, dneg, dreturn, dstore, dstore_<

n>

, dsub, dup, dup2, dup2_—

×

1, dup2_—

×

2, dup_—

×

1, dup_—

×

2, f2d, f2i, f2l, fadd, faload, fastore, fempg, fempl, fconst_<

f>

, fdiv, fload, fload_<

n>

, fmod, fmul, fneg, freturn, fstore, fstore_<

n>

, fsub, gatfield, getstatic, goto, i2d, i2f, i2l, iadd, iaload, iand, iastore, iconst_<

n>

, iconst_m1, idiv, if_acmpeq, if_acmpne, if_icmpeq, if_icmpge, if_icmpgt, if_icmple, if_icmplt, if_icmpne, ifeq, ifge, ifgt, ifle, iflt, ifne, iine, iload, iload_<

n>

, imod, imul, ineg, instanceof, int2byte, int2char, invokeinterface, invokemethod, invokesuper, ior, ireturn, ishl, Ishr, istore, istore_<

n>

, isub, iushr, ixor, jsr, l2d, l2f, l2i, ladd, laload, land, lastore, lcmp, lconst_<

l>

, ldc1, ldc2, ldc2w, ldiv, lload, lload_<

n>

, lmod, lmul, lneg, lookupswitch, lor, lreturn, lshl, lshr, lstore, lstore_<

n>

, lsub, lushr, lxor, monitorenter, monitorexit, new, newarray, newfromname, nop, pop, pop2, putfield, putstatic, ret, return, saload, sastore, siaload, siastore, sipush, tableswitch, and verifystack.

100. The computer system of claim 92, wherein the program verifier includes instructions for certifying that the program complies with a stack non-overflow constraint and a stack non-underflow constraint.

101. The computer system of claim 92, wherein the program verifier includes instructions using a virtual stack to track a set of types associated with operands, if any, on the stack.

102. The computer system of claim 92, wherein the program verifier includes instructions using an array of virtual local variables to track a set of types associated with local variables used by the program.