Data processing: software development – installation – and managem – Software program development tool – Translation of code
Reexamination Certificate
1999-12-06
2001-06-12
Powell, Mark R. (Department: 2122)
Data processing: software development, installation, and managem
Software program development tool
Translation of code
Reexamination Certificate
active
06247171
ABSTRACT:
The present invention relates generally to the use of computer software on multiple computer platforms which use distinct underlying machine instruction sets, and more specifically to an program verifier and method that verify the integrity of computer software obtained from a network server or other source.
BACKGROUND OF THE INVENTION
Referring to
FIG. 1
, in a networked computer system
100
, a first computer
102
may download a computer program
103
residing on a second computer
104
. In this example, the first user node
102
will typically be a user workstation (often called a client) having a central processing unit
106
, a user interface
108
, memory
110
(e.g., random access memory and disk memory) for storing an operating system
112
, programs, documents and other data, and a communications interface
114
for connecting to a computer network
120
such as the Internet, a local area network or a wide area network. The computers
102
and
104
are often called “nodes on the network” or “network nodes.”
The second computer
104
will often be a network server, but may be a second user workstation, and typically would contain the same basic array of computer components as the first computer.
In the prior art (unlike the system shown in FIG.
1
), after the first computer
102
downloads a copy of a computer program
103
from the second computer
104
, there are essentially no standardized tools available to help the user of the first computer
102
to verify the integrity of the download program
103
. In particular, unless the first computer user studies the source code of the downloaded program, it is virtually impossible using prior art tools to determine whether the downloaded program
103
will underflow or overflow its stack, or whether the downloaded program
103
will violate files and other resources on the user's computer.
A second issue with regard to downloading computer software from one computer to another concerns transferring computer software between computer platforms which use distinct underlying machine instruction sets. There are some prior art examples of platform independent computer programs and platform independent computer programming languages. What the prior art lacks are reliable and automated software verification tools for enabling recipients of such software to verify the integrity of transferred platform independent computer software obtained from a network server or other source.
SUMMARY OF THE INVENTION
The present invention verifies the integrity of computer programs written in a bytecode language, commercialized as the JAVA bytecode language, which uses a restricted set of data type specific bytecodes. All the available source code bytecodes in the language either (A) are stack data consuming bytecodes that have associated data type restrictions as to the types of data that can be processed by each such bytecode, (B) do not utilize stack data but affect the stack by either adding data of known data type to the stack or by removing data from the stack without regard to data type, or (C) neither use stack data nor add data to the stack.
The present invention provides a verifier tool and method for identifying, prior to execution of a bytecode program, any instruction sequence that attempts to process data of the wrong type for such a bytecode or if the execution of any bytecode instructions in the specified program would cause underflow or overflow of the operand stack, and to prevent the use of such a program.
The bytecode program verifier of the present invention includes a virtual operand stack for temporarily storing stack information indicative of data stored in a program operand stack during the actual execution a specified bytecode program. The verifier processes the specified program using data flow analysis, processing each bytecode instruction of the program whose stack and register input status map is affected by another instruction processed by the verifier. A stack and register input status map is generated for every analyzed bytecode instruction, and when an instruction is a successor to multiple other instructions, its status map is generated by merging the status maps created during the processing of each of the predecessor instructions. The verifier also compares the stack and register status map information with data type restrictions associated with each bytecode instruction so as to determine if the operand stack or registers during program execution would contain data inconsistent with the data type restrictions of the bytecode instruction, and also determines if any bytecode instructions in the specified program would cause underflow or overflow of the operand stack.
The merger of stack and register status maps requires special handling for the instructions associated with exception handlers and the instructions associated with subroutine calls (including “finally” instruction blocks that are executed via a subroutine call whenever a protected code block is exited).
After pre-processing of the program by the verifier, if no program faults were found, a bytecode program 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.
REFERENCES:
patent: 5179734 (1993-01-01), Candy et al.
patent: 5450575 (1995-09-01), Sites
patent: 5590329 (1996-12-01), Goodnow, II et al.
patent: 5812436 (1998-09-01), Degrousilliers et al.
Kin-Man Chung et al., A 'Tiny Pascal Compiler; Part 1-Part 2 . . . , BYTE Pub., Inc. 1978.*
Takahashi et al., Validating Network Protocols Using a Flexible Verifier, IEEE, 1994, p. 811-817.*
Shih, An Automated Design Specification and Verification Tool . . . , IEEE, 1992, p. 6-17.*
Stuart, Implementing a Verifier for Real-Time Systems, IEEE, 1990, p. 62-71.*
Wang et al., A Verifier for Distributed Real-Time Systems . . . , IEEE, 1993, p. 135-151.*
Ken Thompson, “Regluar Expression Search Algorithm,”Communications of the ACM,Jun., 1968, vol. 11, No. 6, pp. 419-422.
Kin-Man Chung and Herbert Yuen, “A ‘Tiny’ Pascal Compiler; Part 1: The P-Code Interpreter,” BYTE Publications, Inc., Sep. 1978.
Kin-Man Chung and Herbert Yuen, “A ‘Tiny’ Pascal Compiler; Part 2: The P-Compiler,” BYTE Publications, Inc., Oct. 1978.
Gene McDaniel, “An Analysis of a Mesa Instruction Set,” Association for Computing Machinery, May 1982.
Kenneth A. Pier, “A Retrospective on the Dorado, a High-Performance Personal Computer,” IEEE Computer Society, 10thAnnual Intl. Symposium on Computer Architecture, 1983, pp. 252-269.
James G. Mitchell, et al., “Mesa Language Manual,” Xerox Corporation, Palo Alto Research Center.
Gosling James A.
Yellin Frank
Chavis John Q.
Pennie & Edmonds LLP
Powell Mark R.
Sun Microsystems Inc.
LandOfFree
Bytecode program interpreter apparatus and method with... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Bytecode program interpreter apparatus and method with..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Bytecode program interpreter apparatus and method with... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2443391