Data processing: software development – installation – and managem – Software program development tool – Testing or debugging
Reexamination Certificate
2000-11-09
2002-11-05
Morse, Gregory (Department: 2124)
Data processing: software development, installation, and managem
Software program development tool
Testing or debugging
Reexamination Certificate
active
06477702
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 downloaded 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: 3878513 (1975-04-01), Werner
patent: 4521851 (1985-06-01), Trubisky et al.
patent: 4524416 (1985-06-01), Stanley et al.
patent: 4622013 (1986-11-01), Cerchio
patent: 4742215 (1988-05-01), Daughters et al.
patent: 5165465 (1992-11-01), Kenet
patent: 5179734 (1993-01-01), Candy et al.
patent: 5187799 (1993-02-01), McAuley et al.
patent: 5220522 (1993-06-01), Wilson et al.
patent: 5283864 (1994-02-01), Knowlton
patent: 5307499 (1994-04-01), Yin
patent: 5347632 (1994-09-01), Filepp et al.
patent: 5422992 (1995-06-01), Motoyama et al.
patent: 5446875 (1995-08-01), Ogisu et al.
patent: 5450575 (1995-09-01), Sites
patent: 5590329 (1996-12-01), Goodnow, II et al.
patent: 5640503 (1997-06-01), Alpert et al.
patent: 5668999 (1997-09-01), Gosling
patent: 5740441 (1998-04-01), Yellin et al.
patent: 5748964 (1998-05-01), Gosling
patent: 5925125 (1999-07-01), Alpert et al.
patent: 5978574 (1999-11-01), Sharma
patent: 5999731 (1999-12-01), Yellin et al.
patent: 6075940 (2000-06-01), Gosling
patent: 6247171 (2001-06-01), Yellin et al.
patent: 0 424 056 (1990-10-01), None
patent: 0 718 764 (1995-12-01), None
Mili et al., A system for Classifying Program Verification . . . , 1984, IEEE, p. 499-509.*
Gumb, R., A First Course in Program Verification . . . 1989, ACM, p. 146-150.*
Kamikawai et al., A Critical Path System, 1981, IEEE, p. 118-123.*
Adobe Systems Inc., “PostScript Language Reference Manual Second Edition,” 1990, pp. 23-143.
Ahamed et al., “An Application of Name Based Addressing to Low Level Distributed Algorithms,” Jan. 1985, IEEE Transactions On Software Engineering, vol. SE-11, No. 1, p59.
Almes et al., “The Eden System: A Technical Review,” Jan. 1985, IEEE Transactions On Software Engineering, vol SE-11, No. 1, pp. 43-58.
Almes, Guy. T, “Integration and Distribution in the Eden System,” Department of Computer Science, University of Washington Seattle, Technical Report 83-01-02, Jan. 19, 1983, pp. 1-18.
Almes, Guy. T, “The Evolution of the Eden Invocation Mechanism,” Department of Computer Science, University of Washington Seattle, Technical Report 83-01-03, Jan. 19, 1983, pp. 1-14.
Almes, Guy. T, “Eden Project Proposal,” Department of Computer Science, University of Washington Seattle, Technical Report 80-10-01, Oct. 1980, pp. i-ii.
Almes et al., “Research in Integrated Distributed Computing,” Department of Computer Science, University of Washington Seattle, Oct. 1979 pp. 1-42.
Almes et al., “The Eden System: A Technical Review,” Department of Computer Science, University of Washington Seattle, Technical Report 83-10-05, Oct. 1983, pp. 1-25.
Almes et al., “Edmas: An Object-Oriented Locally Distributed Mail System,” Department of Computer Science, FR-35 University of Washington Seattle, Te
Gosling James A.
Yellin Frank
Chavis John Q.
Morse Gregory
Pennie & Edmonds LLP
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-2978840