Memory efficient program pre-execution verifier and method

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.

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.

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.

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.