Data processing: software development – installation – and managem – Software program development tool – Translation of code
Reexamination Certificate
2000-02-28
2004-03-09
Chaki, Kakali (Department: 2122)
Data processing: software development, installation, and managem
Software program development tool
Translation of code
C717S152000, C717S152000
Reexamination Certificate
active
06704923
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
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 a method of verifying the integrity of computer software obtained from a network server or other source.
2. Prior Art
As represented generally in
FIG. 1
, in a typical prior art 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 having a central processing unit
106
, a user interface
108
, a primary memory
110
(e.g., random access memory) for program execution, a secondary memory
112
(e.g., a hard disc) for storage of an operating system
113
, programs, documents and other data, and a modem or other communication 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, 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, to be commercialized as the OAK 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 execution a specified bytecode program. The verifier processes the specified program by sequentially processing each bytecode instruction of the program, updating the virtual operand stack to indicate the number, sequence and data types of data that would be stored in the operand stack at each point in the program. The verifier also compares the virtual stack information with data type restrictions associated with each bytecode instruction so as to determine if the operand stack 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.
To avoid detailed analysis of the bytecode program's instruction sequence flow, and to avoid verifying bytecode instructions multiple times, all points (called multiple-entry points) in the specified program that can be can be immediately preceded in execution by two or more distinct bytecodes in the program are identified. In general, at least one of the two or more distinct bytecodes in the program will be a jump/branch bytecode. During processing of the specified program, the verifier takes a “snapshot” of the virtual operand stack immediately prior to each multiple-entry point (i.e., subsequent to any one of the preceding bytecode instructions), compares that snapshot with the virtual operand stack state after processing each of the other preceding bytecode instructions for the same multiple-entry point, and generates a program fault if the virtual stack states are not identical.
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: 5668999 (1997-09-01), Gosling
patent: 5740441 (1998-04-01), Yellin et al.
patent: 5748964 (1998-05-01), Gosling
patent: 5999731 (1999-12-01), Yellin et al.
patent: 6075940 (2000-06-01), Gosling
patent: 6247171 (2001-06-01), Yellin et al.
patent: 6477702 (2002-11-01), Yellin et al.
patent: 0 424 056 (1990-10-01), None
patent: 0424056 (1991-04-01), None
patent: 0 718 764 (1995-12-01), None
Ken Thompson, “Regular 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 Complier; Part 1: The P-Code Interpreter,”BYTE Publications, Inc., Sep. 1978.
Kin-Man Chung and Herbert Yuen, “A ‘Tiny’ Pascal Complier; 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, 10th Annual Intl. Symposium on Computer Architecture, 1983, pp. 252-269.
James G. Mitchell, et al., “Mesa Language Manual”,Xerox Corporation, Palo Alto Research Center.
Robert E. Strom, et al., “Extending Typestate Checking Using Conditional Liveness Analysis”, IEEE Transactions on Softare Engineering, vol. 19, No. 5, May 1993.
Schauer, H., “Architektur und Implementierung eines PASCAL-Systems für Mikrocomputer”, Elektronische Rechenanlagen, vol. 24, No. 3, Jun. 1982, pp. 108-117.
Perrott, R.H., et al., “A Supercomputer Program Development System”, Software Practice & Experience 17, No. 10, Oct. 1987, pp. 663-683.
Wright, Andrew K., et al., “A Practical Soft Type System for Scheme”, LISP 94—Jun. 1994 Orlando, Florida, pp. 250-262.
Gosling, James, “Java Intermediate Bytecodes”, ACM SIGPLAN Workshop on Intermediate Representations (IR '95), Jan. 1995, San Francisco, California, ACM SIGPLAN NOTICES, vol. 30, No. 3, Mar. 1995, pp. 111-118.
Chambers, Craig, et al., “An Efficient Implementation of SELF, a Dynamically-Typed Objec
Chaki Kakali
Pennie & Edmonds LLP
Sun Microsystems Inc.
Williams Gary S.
LandOfFree
System and method for pre-verification of stack usage in... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for pre-verification of stack usage in..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for pre-verification of stack usage in... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3210816