US6151618A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Safe general purpose virtual machine computing system
Assignee: Microsoft Technology Licensing LLC
•
Filing: 1997-06-18
•
Granted: 2000-11-21
•
Expires: 2017-06-18
Abstract
Abstract A safe general purpose virtual machine computing system having a general purpose memory protection model that is hardware architecture and programming language independent. The safe general purpose virtual machine computing system is software based to facilitate operation on hardware architectures that otherwise would prevent the exchange and successful execution of mobile code programs from one computer system to another. The safe general purpose virtual machine computing system also facilitates generating Bytecode Reduced Instruction Set Computer (BRISC) compressed mobile code that can be compiled or translated into executable code very quickly in addition to being compact for transmission purposes, and that is prevented from accessing unauthorized memory locations due to Software Fault Isolation techniques implemented in the code.
Inventors
- 👤 Robert S. Wahbe
- 👤 Steven E. Lucco
- 👤 Christopher W. Fraser
- 👤 Vance Palmer Morrison
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-02 01:44
CPC Classifications
G; G06; G06F; G06F11/00; G06F11/36; G06F11/362; G06F11/3624
Claims Analysis
Total Claims: 44
Claim 1
Independent Claim
203 words
A computer readable medium containing computer executable instructions to perform a method for implementing a safe general purpose virtual machine, said method comprising: defining said safe general purpose virtual machine having a general purpose memory protection model that does not rely or depend upon a specific hardware architecture or programming language feature for memory protection, at least one memory access permission based on said memory protection model, a bytecode reduced instruction set computer compiler wherein said bytecode reduced instructions occur only on byte boundaries, and a plurality of reduced instruction set computer virtual machine instructions selected from at least one of a group of types comprised of: control transfer instructions, arithmetic instructions, bitwise manipulation instructions, register/memory instructions, and miscellaneous instructions; generating a safe virtual machine program from a source program that contains at least one unsafe instruction, wherein said safe virtual machine program is hardware architecture independent and programming language independent; optionally compressing said safe virtual machine program pursuant to a bytecode reduced instruction set computer compression system, wherein said bytecode reduced instructions occur only on byte boundaries; and executing said safe virtual machine program within a memory space defined by said memory protection model and said at least one memory access permission.
Claim 2
Dependent Claim
203 words
A computer readable medium containing computer executable instructions to perform a method for implementing a safe general purpose virtual machine, said method comprising: defining said safe general purpose virtual machine having a general purpose memory protection model that does not rely or depend upon a specific hardware architecture or programming language feature for memory protection, at least one memory access permission based on said memory protection model, a bytecode reduced instruction set computer compiler wherein said bytecode reduced instructions occur only on byte boundaries, and a plurality of reduced instruction set computer virtual machine instructions selected from at least one of a group of types comprised of: control transfer instructions, arithmetic instructions, bitwise manipulation instructions, register/memory instructions, and miscellaneous instructions; generating a safe virtual machine program from a source program that contains at least one unsafe instruction, wherein said safe virtual machine program is hardware architecture independent and programming language independent; optionally compressing said safe virtual machine program pursuant to a bytecode reduced instruction set computer compression system, wherein said bytecode reduced instructions occur only on byte boundaries; and executing said safe virtual machine program within a memory space defined by said memory protection model and said at least one memory access permission.
Claim 3
Dependent Claim
103 words
A method according to claim 1 wherein said step of generating includes: identifying a first set of program instructions within said source program capable of converting a legal memory address into a memory address prohibited by said memory access permissions; identifying a second set of program instructions within said source program that are capable of jumping to a memory address prohibited by said memory access permissions; preassigning explicit register allocations for each symbolic reference in said source program; and altering said first set of program instructions and said second set of program instructions to cause a trap catchable by a trusted program host.
Claim 4
Dependent Claim
54 words
A method according to claim 1 wherein said step of optionally compressing includes: determining a compression benefit for said safe virtual machine program; and implementing a dense randomly accessible stream of bytecodes using a bytecode reduced instruction set computer compression on said safe virtual machine program in positive response to said step of determining.
Claim 5
Dependent Claim
92 words
A method according to claim 3 wherein said step of determining includes: generating a list of repeated instruction patterns in said safe virtual machine program to add to an instruction dictionary; estimating a program size reduction P to said safe virtual machine program based on a record of said list of repeated instruction patterns in said instruction dictionary; identifying a number of bytes W required to represent said list of repeated instruction patterns in said instruction dictionary; and determining a compression benefit B based on a weighted evaluation of P and W.
Claim 6
Dependent Claim
36 words
A method according to claim 4 including: determining said compression benefit B based on an arithmetic difference of P and W; and compressing said safe virtual machine program in response to a positive value of B.
Claim 7
Dependent Claim
21 words
A method according to claim 4 including: compressing said safe virtual machine program in response to a positive value of P.
Claim 8
Dependent Claim
77 words
A method according to claim 4 wherein said step of implementing includes: maintaining a heap of candidate compression instructions from said list of repeated instruction patterns; adding distinct instruction combinations of said list of repeated instruction patterns in said heap to said instruction dictionary; associating a unique opcode-combined instruction with each of said distinct instruction combinations; and substituting said unique opcode-combined instruction with a corresponding one of said distinct instruction combinations in said safe virtual machine program.
Claim 9
Dependent Claim
42 words
A method according to claim 7 wherein said step of maintaining includes: hashing said heap to identify repeated ones of said list of repeated instruction patterns; and updating said instruction dictionary with only one copy of each of said distinct instruction combinations.
Claim 10
Dependent Claim
42 words
A method according to claim 1 wherein said step of optionally compressing includes: generating operand specialization compression on repeated instruction operands within said safe virtual machine program; and generating opcode combination compression on repeated instruction patterns within said safe virtual machine program.
Claim 11
Dependent Claim
40 words
A method according to claim 9 wherein said step of generating operand specialization compression includes: adding commonly repeated instructions to a repeated instruction dictionary; and implicitly representing repeated operands from among said commonly repeated instructions in said repeated instruction dictionary.
Claim 12
Dependent Claim
59 words
A method according to claim 9 wherein said step of generating opcode combination compression includes: adding repeated pairs of adjacent instruction combinations to a repeated instruction dictionary; generating a single meta-instruction for each unique one of repeated pairs of adjacent instruction combinations; and combining pairs of zero-field and one-field instructions to maximize optimal byte boundaries of densely packed instructions.
Claim 13
Dependent Claim
39 words
A method according to claim 11 wherein said step of combining pairs includes: delaying said step of combining until a maximum number of instruction pairs are available to maximize a selection of optimal byte boundaries of densely packed instructions.
Claim 14
Dependent Claim
107 words
A method according to claim 1 wherein said step of executing includes: verifying that said safe virtual machine program is free of unsafe instructions, hardware architecture dependencies, and programming language dependencies; assigning a memory access permission to said safe virtual machine program; generating a program execution interrupt to trap said safe virtual machine program at a time a memory address is accessed other than a memory address allowed by said assigned memory access permission; generating a native machine executable program from said safe virtual machine program just-in-time to execute said native machine executable program; and executing said native machine executable program on a native machine hardware host.
Claim 15
Dependent Claim
50 words
A method according to claim 13 wherein said step of verifying includes: identifying a safe program instruction from and unsafe program instruction within said safe virtual machine program; and generating a new safe virtual machine program in negative response to an unsafe program instruction within said safe virtual machine program.
Claim 16
Dependent Claim
96 words
A method according to claim 1 wherein said step of generating includes: converting said source program into a sequence of virtual machine program instructions; identifying ones of said sequence of virtual machine program instructions capable of accessing memory addresses other than said memory addresses defined by said at least one memory access permission; and modifying said virtual machine program with safety check instructions to prevent access to memory addresses other than said memory addresses defined by said at least one memory access permission, wherein said virtual machine program with modifications is said safe virtual machine program.
Claim 17
Dependent Claim
49 words
A method according to claim 15 wherein said step of modifying includes: inserting dedicated register segment matching instructions for at least one of said sequence of virtual machine program instructions capable of accessing memory addresses other than said memory addresses defined by said at least one memory access permission.
Claim 18
Dependent Claim
49 words
A method according to claim 15 wherein said step of modifying includes: inserting dedicated register address sandboxing instructions for at least one of said sequence of virtual machine program instructions capable of accessing memory addresses other than said memory addresses defined by said at least one memory access permission.
Claim 19
Dependent Claim
19 words
A method according to claim 1 including: implementing run time performance enhancing optimizations on said safe virtual machine program.
Claim 20
Dependent Claim
63 words
A method according to claim 18 wherein said implementing includes: removing related non-essential safety check instructions from said safe virtual machine program, wherein said related safety check instructions are both positioned in response to the setting or using of a common register and prevent unauthorized access to memory addresses other than said memory addresses defined by said at least one memory access permission.
Claim 21
Dependent Claim
18 words
A method according to claim 18 wherein said implementing includes: improving said safe virtual machine program logic flow.
Claim 22
Independent Claim
218 words
A method comprising: defining a safe general purpose virtual machine having a general purpose memory protection model that does not rely or depend upon a specific hardware architecture or programming language feature for memory protection, at least one memory access permission based on said memory protection model, a bytecode reduced instruction set computer compiler wherein said bytecode reduced instructions occur only on byte boundaries, and a plurality of reduced instruction set computer virtual machine instructions selected from at least one of a group of types comprised of: control transfer instructions, arithmetic instructions, bitwise manipulation instructions, register/memory instructions, and miscellaneous instructions; generating, on a first computer, a safe virtual machine program from a source program that contains at least one unsafe instruction, wherein said safe virtual machine program is hardware architecture independent and programming language independent; optionally compressing said safe virtual machine program pursuant to a bytecode reduced instruction set computer compression system; transferring said safe virtual machine program from said first computer to said second computer; and executing said safe virtual machine program within a memory space defined by said memory protection model and said at least one memory access permission on a second computer that is independent from and network accessible to said first computer, and said first computer is hardware architecturally distinguishable from said second computer.
Claim 23
Independent Claim
218 words
A method comprising: defining a safe general purpose virtual machine having a general purpose memory protection model that does not rely or depend upon a specific hardware architecture or programming language feature for memory protection, at least one memory access permission based on said memory protection model, a bytecode reduced instruction set computer compiler wherein said bytecode reduced instructions occur only on byte boundaries, and a plurality of reduced instruction set computer virtual machine instructions selected from at least one of a group of types comprised of: control transfer instructions, arithmetic instructions, bitwise manipulation instructions, register/memory instructions, and miscellaneous instructions; generating, on a first computer, a safe virtual machine program from a source program that contains at least one unsafe instruction, wherein said safe virtual machine program is hardware architecture independent and programming language independent; optionally compressing said safe virtual machine program pursuant to a bytecode reduced instruction set computer compression system; transferring said safe virtual machine program from said first computer to said second computer; and executing said safe virtual machine program within a memory space defined by said memory protection model and said at least one memory access permission on a second computer that is independent from and network accessible to said first computer, and said first computer is hardware architecturally distinguishable from said second computer.
Claim 24
Dependent Claim
105 words
A method according to claim 21 wherein said step of generating includes: identifying a first set of program instructions within said source program capable of converting a legal memory address into a memory address prohibited by said memory access permissions; identifying a second set of program instructions within said source program capable of jumping to a memory address prohibited by said memory access permissions; preassigning explicit register allocations for each symbolic reference in said source program; and altering said first set of program instructions and said second set of program instructions to cause a trap catchable by a trusted program host on said second computer.
Claim 25
Dependent Claim
109 words
A method according to claim 21 wherein said step of executing includes: verifying that said safe virtual machine program is free of unsafe instructions, hardware architecture dependencies, and programming language dependencies; assigning a memory access permission to said safe virtual machine program; generating a program execution interrupt to trap said safe virtual machine program at a time a memory address is accessed other than a memory address allowed by said assigned memory access permission; generating a native machine executable program from said safe virtual machine program just-in-time to execute said native machine executable program; and executing said native machine executable program on native machine hardware of said second computer.
Claim 26
Dependent Claim
13 words
A method according to claim 23 including: decompressing said safe virtual machine program.
Claim 27
Dependent Claim
49 words
A method according to claim 23 wherein said step of verifying includes: distinguishing a safe program instruction from and unsafe program instruction within said safe virtual machine program; generating a new safe virtual machine program in negative response to an unsafe program instruction within said safe virtual machine program.
Claim 28
Independent Claim
240 words
A system for executing a safe virtual machine program in a safe general purpose virtual machine, said system comprising: a first computer communicatively connected to a second computer, said first computer being operationally independent from said second computer; means for defining a safe general purpose virtual machine having a general purpose memory protection model that does not rely or depend upon a specific hardware architecture or programming language feature for memory protection, at least one memory access permission based on said memory protection model, a bytecode reduced instruction set computer compiler wherein said bytecode reduced instructions occur only on byte boundaries, and a plurality of reduced instruction set computer virtual machine instructions selected from at least one of a group of types comprised of: control transfer instructions, arithmetic instructions, bitwise manipulation instructions, register/memory instructions, and miscellaneous instructions; means for generating, on said first computer, a safe virtual machine program from a source program that contains at least one unsafe instruction, wherein said safe virtual machine program is hardware architecture independent and programming language independent; means for optionally compressing said safe virtual machine program pursuant to a bytecode reduced instruction set computer compression system; means for transferring said safe virtual machine program from said first computer to said second computer; and means for executing said safe virtual machine program within a memory space defined by said memory protection model and said at least one memory access permission on said second computer.
Claim 29
Independent Claim
240 words
A system for executing a safe virtual machine program in a safe general purpose virtual machine, said system comprising: a first computer communicatively connected to a second computer, said first computer being operationally independent from said second computer; means for defining a safe general purpose virtual machine having a general purpose memory protection model that does not rely or depend upon a specific hardware architecture or programming language feature for memory protection, at least one memory access permission based on said memory protection model, a bytecode reduced instruction set computer compiler wherein said bytecode reduced instructions occur only on byte boundaries, and a plurality of reduced instruction set computer virtual machine instructions selected from at least one of a group of types comprised of: control transfer instructions, arithmetic instructions, bitwise manipulation instructions, register/memory instructions, and miscellaneous instructions; means for generating, on said first computer, a safe virtual machine program from a source program that contains at least one unsafe instruction, wherein said safe virtual machine program is hardware architecture independent and programming language independent; means for optionally compressing said safe virtual machine program pursuant to a bytecode reduced instruction set computer compression system; means for transferring said safe virtual machine program from said first computer to said second computer; and means for executing said safe virtual machine program within a memory space defined by said memory protection model and said at least one memory access permission on said second computer.
Claim 30
Dependent Claim
113 words
A system according to claim 26 wherein said means for generating includes: means for identifying a first set of program instructions within said source program capable of converting a legal memory address into a memory address prohibited by said memory access permissions; means for identifying a second set of program instructions within said source program capable of jumping to a memory address prohibited by said memory access permissions; means for preassigning explicit register allocations for each symbolic reference in said source program; and means for altering said first set of program instructions and said second set of program instructions to cause a trap catchable by a trusted program host on said second computer.
Claim 31
Dependent Claim
119 words
A system according to claim 26 wherein said means for executing includes: means for verifying that said safe virtual machine program is free of unsafe instructions, hardware architecture dependencies, and programming language dependencies; means for assigning a memory access permission to said safe virtual machine program; means for generating a program execution interrupt to trap said safe virtual machine program at a time a memory address is accessed other than a memory address allowed by said assigned memory access permission; means for generating a native machine executable program from said safe virtual machine program just-in-time to execute said native machine executable program; and means for executing said native machine executable program on native machine hardware of said second computer.
Claim 32
Dependent Claim
15 words
A system according to claim 28 including: means for decompressing said safe virtual machine program.
Claim 33
Dependent Claim
54 words
A system according to claim 28 wherein said means for verifying includes: means for distinguishing a safe program instruction from and unsafe program instruction within said safe virtual machine program; and means for generating a new safe virtual machine program in negative response to an unsafe program instruction within said safe virtual machine program.
Claim 34
Dependent Claim
228 words
A computer readable medium containing computer executable instructions to perform a method for implementing a safe general purpose virtual machine, said method comprising: defining said safe general purpose virtual machine having a general purpose memory protection model, at least one memory access permission based on said memory protection model, a bytecode reduced instruction set computer compiler, and a plurality of reduced instruction set computer virtual machine instructions comprising: non-trap type control instructions that operate only in user mode and do not invoke a privileged or supervisory mode, arithmetic instructions, bitwise manipulation instructions, register/memory instructions that include one or more load and store instructions that are enhanced to allow a variety of higher level addressing modes to facilitate generating efficient code of a variety of hardware target platforms, and miscellaneous instructions that include a no-operation instruction, one or more instructions that return specific hardware environment information, and one or more register-to-memory location link and release instructions; generating a safe virtual machine program from a source program that contains at least one unsafe instruction, wherein said safe virtual machine program is hardware architecture independent and programming language independent; optionally compressing said safe virtual machine program pursuant to a bytecode reduced instruction set computer compression system; and executing said safe virtual machine program within a memory space defined by said memory protection model and said at least one memory access permission.
Claim 35
Dependent Claim
228 words
A computer readable medium containing computer executable instructions to perform a method for implementing a safe general purpose virtual machine, said method comprising: defining said safe general purpose virtual machine having a general purpose memory protection model, at least one memory access permission based on said memory protection model, a bytecode reduced instruction set computer compiler, and a plurality of reduced instruction set computer virtual machine instructions comprising: non-trap type control instructions that operate only in user mode and do not invoke a privileged or supervisory mode, arithmetic instructions, bitwise manipulation instructions, register/memory instructions that include one or more load and store instructions that are enhanced to allow a variety of higher level addressing modes to facilitate generating efficient code of a variety of hardware target platforms, and miscellaneous instructions that include a no-operation instruction, one or more instructions that return specific hardware environment information, and one or more register-to-memory location link and release instructions; generating a safe virtual machine program from a source program that contains at least one unsafe instruction, wherein said safe virtual machine program is hardware architecture independent and programming language independent; optionally compressing said safe virtual machine program pursuant to a bytecode reduced instruction set computer compression system; and executing said safe virtual machine program within a memory space defined by said memory protection model and said at least one memory access permission.
Claim 36
Independent Claim
141 words
A method for compressing a safe virtual machine program, which is hardware architecture independent and programming language independent, said method comprising: generating a list of repeated instruction patterns in said safe virtual machine program to add to an instruction dictionary; estimating a program size reduction P to said safe virtual machine program based on a record of said list of repeated instruction patterns in said instruction dictionary; identifying a number of bytes W required to represent said list of repeated instruction patterns in said instruction dictionary; determining a compression benefit B based on a weighted evaluation of P and W; and implementing a dense randomly accessible stream of bytecodes using a bytecode reduced instruction set computer compression on said safe virtual machine program in positive response to said step of determining, wherein said bytecode reduced instructions occur only on byte boundaries.
Claim 37
Independent Claim
141 words
A method for compressing a safe virtual machine program, which is hardware architecture independent and programming language independent, said method comprising: generating a list of repeated instruction patterns in said safe virtual machine program to add to an instruction dictionary; estimating a program size reduction P to said safe virtual machine program based on a record of said list of repeated instruction patterns in said instruction dictionary; identifying a number of bytes W required to represent said list of repeated instruction patterns in said instruction dictionary; determining a compression benefit B based on a weighted evaluation of P and W; and implementing a dense randomly accessible stream of bytecodes using a bytecode reduced instruction set computer compression on said safe virtual machine program in positive response to said step of determining, wherein said bytecode reduced instructions occur only on byte boundaries.
Claim 38
Dependent Claim
36 words
A method according to claim 32 including: determining said compression benefit B based on an arithmetic difference of P and W; and compressing said safe virtual machine program in response to a positive value of B.
Claim 39
Dependent Claim
21 words
A method according to claim 32 including: compressing said safe virtual machine program in response to a positive value of P.
Claim 40
Dependent Claim
77 words
A method according to claim 32 wherein said step of implementing includes: maintaining a heap of candidate compression instructions from said list of repeated instruction patterns; adding distinct instruction combinations of said list of repeated instruction patterns in said heap to said instruction dictionary; associating a unique opcode-combined instruction with each of said distinct instruction combinations; and substituting said unique opcode-combined instruction with a corresponding one of said distinct instruction combinations in said safe virtual machine program.
Claim 41
Dependent Claim
42 words
A method according to claim 35 wherein said step of maintaining includes: hashing said heap to identify repeated ones of said list of repeated instruction patterns; and updating said instruction dictionary with only one copy of each of said distinct instruction combinations.
Claim 42
Independent Claim
120 words
A method for compressing a safe virtual machine program, which is hardware architecture independent and programming language independent, said method comprising: generating operand specialization compression on repeated instruction operands within said safe virtual machine program including: adding commonly repeated instructions to a repeated instruction dictionary; and implicitly representing repeated operands from among said commonly repeated instructions in said repeated instruction dictionary; generating opcode combination compression on repeated instruction patterns within said safe virtual machine program, including: adding repeated pairs of adjacent instruction combinations to a repeated instruction dictionary; generating a single meta-instruction for each unique one of repeated pairs of adjacent instruction combinations; and combining pairs of zero-field and one-field instructions to maximize optimal byte boundaries of densely packed instructions.
Claim 43
Independent Claim
120 words
A method for compressing a safe virtual machine program, which is hardware architecture independent and programming language independent, said method comprising: generating operand specialization compression on repeated instruction operands within said safe virtual machine program including: adding commonly repeated instructions to a repeated instruction dictionary; and implicitly representing repeated operands from among said commonly repeated instructions in said repeated instruction dictionary; generating opcode combination compression on repeated instruction patterns within said safe virtual machine program, including: adding repeated pairs of adjacent instruction combinations to a repeated instruction dictionary; generating a single meta-instruction for each unique one of repeated pairs of adjacent instruction combinations; and combining pairs of zero-field and one-field instructions to maximize optimal byte boundaries of densely packed instructions.
Claim 44
Dependent Claim
39 words
A method according to claim 37 wherein said step of combining pairs includes: delaying said step of combining until a maximum number of instruction pairs are available to maximize a selection of optimal byte boundaries of densely packed instructions.
References Cited (Backward Citations)
US4667290A
Cited
US5386557A
Cited
US5586323A
Cited
US5537551A
Cited
US5590329A
Cited
US5644709A
Cited
US5551051A
Cited
US5590331A
Cited
US5761477A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-11-21 | 2004-05-22 | 2004-11-21 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-11-21 | 2008-05-22 | 2008-11-21 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-11-21 | 2012-05-22 | 2012-11-21 | $7700.00 | Window Closed / Lapsed |