Computer security system - Patent Review 4584639

Claims

What is claimed is:

1. In a capability based data processing system having at least one central processing unit, memory means and a multiplicity of keys, each key providing authority to its holder to use a specified portion of said system's resources, an arrangement comprising:

a plurality of domains for performing predefined processes, each including means for holding a plurality of keys; and

kernel means coupled to said domains for providing said domains with a predefined set of kernel functions, said kernel means having the exclusive means for creating keys and the exclusive means for resolving the authority conveyed by each said key;

wherein

a plurality of said domains comprise factories for creating factory products comprising new domains for performing specified tasks;

a multiplicity of said keys are non-sensory keys, which convey the authority to directly or indirectly cause data to be transmitted to, or changed within, a domain other than the domain invoking said key; and

predefined ones of said kernel functions allow a requestor domain with a key to a specified one of said factories to determine whether said specified factory has any non-sensory keys not included in a first predefined set of keys;

whereby a requestor domain can determine if use of a specified factory could compromise the confidentiality of data provided by said requestor domain to said factory.

2. An arrangement as set forth in claim 1, wherein said kernel functions include

a factory verification function for determining whether a specified factory has the ability to invoke, directly or indirectly, any non-sensory keys which are not included in a first predefined set, whereby a requestor domain can determine if a specified factory has access to any non-sensory keys whose nature and authority are not known to said requestor domain.

3. An arrangement as set forth in claim 2, wherein

said kernel functions include a set of predefined builder's functions;

each said factory includes means for responding to the invocation of a corresponding builder's key by a builder domain by performing a selected one from said set of predefined builder's functions in accordance with a parameter selected by said builder domain;

said set of builder's functions includes the functions of

installing components in said factory, including a program component defining a program to be performed by the factory products produced thereby, and key components for use by said program; and

sealing said factory, thereby preventing said builder domain from thereafter installing non-sensory components in said factory, and returning to said builder domain a corresponding requestor's key which the builder domain may distribute to other domains.

4. An arrangement as set forth in claim 3, wherein said kernel functions include

a factory verification function for determining whether a first specified factor has the ability to invoke, directly or indirectly, any non-sensory keys which a second specified factory does not have the ability to invoke.

5. An arrangement as set forth in claim 4, wherein

each of a plurality of said factories includes key identification (KID) means for maintaining a list of all non-sensory keys, if any, installed by a builder domain in said factory.

6. An arrangement as set forth in claim 5, wherein

said set of builder's functions includes the function of installing a requestor's key as a key component in said factory; and

said factory verification means function includes in the set of non-sensory keys that can be invoked by said first specified factory the non-sensory keys that can be invoked by each factory corresponding to a requestor's key installed as a key component in said specified factory.

7. An arrangement as set forth in claim 6, wherein

said set of builder's functions includes the function of installing a requestor's key as the program component of a factory; and

the factory product of a factory having a requestor's key as a program component will have as its program component the key produced by invoking said requestor's key.

8. An arrangement as set forth in claim 3, wherein

a plurality of said domains each have means for specifying a domain keeper to be called by said kernel means upon the occurrence of domain faults in said domain, said domain keeper comprising a domain having means for resolving domain faults and for restarting said domain;

said set of builder's functions includes the function of installing a domain keeper component defining the domain keeper for the factory products to be produced by said factory;

wherein if said domain keeper component of a factory is a requestor's key, then the factory products of said factory will each have as its domain keeper the domain produced by invoking said requestor's key.

9. An arrangement as set forth in claim 2, including

a factory creator for creating new factories, responsive to the invocation of corresponding key by a builder domain by creating a new factory and passing to the builder a builder's key to said new factory.

10. An arrangement as set forth in claim 2, wherein

said arrangement includes at least one domain creator, each said domain creator including domain tool means for creating new domains, and means for transmitting to the invoker of a key corresponding to said domain creator a key corresponding to a newly created domain;

whereby a domain with said key corresponding to said domain creator can request the creation of a new domain and obtain a key thereto.

11. An arrangement as set forth in claim 10, wherein

a plurality of said keys are domain keys, each domain key conveying the maximum amount of authority over a corresponding domain; and

at least one said domain creator having said key verification means includes means for responding to the invocation of a key corresponding to said domain creator, by returning the invoker a domain key if the specified key corresponds to a domain having the same brand as domains created by said domain creator, and by returning an error code otherwise.

12. An arrangement as set forth in claim 10, including

domain creator creator means for creating new domain creators, each new domain creator having a unique brand, responsive to the invocation of a corresponding key by a first domain by returning to said first domain a key to a new domain creator.

13. An arrangement as set forth in claim 2, wherein

a plurality of said domains comprise segment keepers;

said memory means includes a multiplicity of memory segments; and

a multiplicity of said memory segments each include segment keeper means for specifying a program to be performed upon the occurrence of a memory fault in said memory segment,

whereby said memory fault can be resolved and the domain that was interrupted by said memory fault can be restarted.

14. An arrangement as set forth in claim 2, wherein

a plurality of said domains comprise segment keepers;

said memory means includes a multiplicity of nodes for holding said keys; and a multiplicity of memory segments for storing data;

a plurality of said nodes comprise segment nodes that define a memory segment;

a plurality of said segment nodes contain an entry key to a segment keeper, said entry key to be invoked by said kernel means upon the occurrence of a memory fault in the memory segment defined by said segment node; and

a plurality of said segment keepers have a program for resolving memory faults and exiting back to the domain which was interrupted by the memory fault.

15. An arrangement as set forth in claim 14, wherein

at least one of said segment keepers is a virtual copy segment keeper (VCSK); and

said VCSK includes means for resolving memory faults caused by an attempt to write on a read-only memory area by making a write-enabled copy of said read-only memory area and replacing the portion of the memory segment corresponding to said segment keeper that comprises said read-only memory area with said write-enabled copy.

16. An arrangement as set forth in claim 15, wherein

at least one of said factories is a virtual copy segment keeper factory (VCSKF);

said VCSKF yielding a factory product comprising a memory segment (S1) with a corresponding VCSK.

17. An arrangement as set forth in claim 16, wherein

the VCSK produced by said VCSKF includes a function for producing, in response to the invocation of a entry key thereto, a copy (VCF) of said VCSKF, said VCF having a sensory key to the memory segment (S1) corresponding to said VCSK;

said VCF producing, in response to the invocation of a corresponding requestor's key, a predefined memory segment (S2) with a corresponding VCSK (VCSK1);

said predefined memory segment (S2) comprising a sensory copy of the memory segment (S1) corresponding to said VCSK;

said VCSK1 having a program for sending to the requestor of said VCF a key to said predefined memory segment (S2).

18. An arrangement as set forth in claim 2, wherein

a plurality of said domains each have means for specifying a domain keeper to be called by said kernel means upon the occurrence of domain faults in said domain, said domain keeper comprising a domain having means for resolving domain faults and for restarting a domain interrupted by a domain fault.

19. An arrangement as set forth in claim 1, wherein

a plurality of said domains each have means for specifying a domain keeper to be called by said kernel means upon the occurrence of domain faults in said domain, said domain keeper comprising a domain having means for resolving domain faults and for restarting said domain.

20. An arrangement as set forth in claim 1, wherein

each of a plurality of said factories contains a program component defined by a builder domain, said program component being useable for processing data by one or more requestor domains which hold a requestor key corresponding to said factory; wherein said requestor key does not provide the authority to obtain a copy of nor to otherwise inspect said program component in said factory and said builder domain has no authority to obtain a copy of nor to otherwise inspect the data processed by said program component in said factory for each said requestor;

whereby the combination of said factories and said requestor keys provide means for requestor domains to use program components provided by builder domains while protecting the confidentiality of both said program components and the data from said requestor domains processed thereby.

21. An arrangement as set forth in claim 20, wherein

each of a plurality of said factories includes factory product generation means for creating a new factory product domain when a requestor domain invokes a corresponding requestor key, said factory product domain having access to said program component of the corresponding factory for the processing of data provided by said requestor domain;

whereby the provision of separate factory product domains ensures that data from each said requestor domain can be kept confidential from other requestor domains.

22. An arrangement as set forth in claim 1, wherein each of a plurality of said factories includes

factory product generation means for creating a new factory product domain when a requestor domain invokes a corresponding requestor key; and

a start-up program component defining a start-up program which is invoked by each said factory product of said factory upon its formation for modifying the structure of said factory product and for returning to said requestor domain a key to the modified factory product.

23. In a capability based data processing system having at least one central processing unit, memory means and a multiplicity of keys, each key providing authority to its holder to use a specified portion of said system's resources, an arrangement comprising:

a plurality of domains for performing predefined processes, each including means for holding a plurality of keys; and

kernel means coupled to said domains for providing said domains with a predefined set of kernel functions, said kernel means having the exclusive means for creating keys and the exclusive means for resolving the authority conveyed by each said key;

wherein

a plurality of said domains comprise segment keepers;

said memory means includes a multiplicity of nodes for holding said keys; and a multiplicity of memory segments for storing data;

a plurality of said nodes are segment nodes, each segment node defining a memory segment of a specified size;

a plurality of said keys are memory keys;

a plurality of said memory keys are page keys, each said page key providing access to a page of memory, each said page comprising a preselected number of basic memory storage units;

a plurality of said memory keys are segmode keys, each said segmode key providing access to a segment node having a plurality of slots for holding memory keys;

a plurality of said domains each have means for defining a memory tree defining the virtual address space of said domain;

each said memory tree includes at least one memory key;

each said memory tree which includes more than one memory key includes at least one segmode key and at least one segment node;

a plurality of said segment nodes each include means for specifying a segment keeper to be called by said kernel means upon the occurrence of memory faults in the memory segment defined by said segment node, said segment keeper comprising a domain having means for resolving memory faults and for restarting the domain wherein the fault occurred.

24. An arrangement as set forth in claim 23, wherein

said segmode keys include a size parameter indicating the size of the address space defined by the corresponding segment node.

25. An arrangement as set forth in claim 24, wherein

said means for defining a memory tree includes a memory key at the root of said memory tree.

26. An arrangement as set forth in claim 25, wherein

each said memory tree can overlap at least a portion of another memory tree corresponding to a second domain, whereby access to the common portion of said memory trees is shared.

27. An arrangement as set forth in claim 26, wherein

said page and segment keys include an RO parameter indicating whether the key provides read-only or read-write access to the corresponding portion of said memory means.

28. An arrangement as set forth in claim 23, wherein

said memory means comprises core memory and disk memory;

an unprepared key comprises a key that specifies the location in disk memory of the object corresponding to the key;

a prepared key comprises a key that specifies the location in core memory of the object corresponding to said key; and

when an unprepared key is used by one of said domains to obtain access to an object, said kernel means either locates the corresponding object's location in core memory or moves said object into core memory, and replaces said unprepared key with a prepared key.

29. An arrangement as set forth in claim 28, wherein

said core memory and said disk memory each has a plurality of page frames for holding pages of information, and node frames for holding nodes;

each page frame and each node frame on disk has a corresponding unique disk address (CDA);

each page in core memory has a corresponding page frame on disk memory;

each node in core memory has a corresponding node frame on disk memory;

each key on disk memory, which corresponds to a node or page, and each key in core memory, which corresponds to a node or page not in core memory, is unprepared; and

said kernel means includes means for preparing an unprepared key when said unprepared key is used;

said kernel means includes means for calculating the location of a node or page in core memory corresponding to an unprepared key; and

a prepared key can remain prepared so long as both the key and the corresponding node or page remain in core memory;

whereby the location of an object in core memory corresponding to a key need not be recomputed once a key for said object is prepared until and unless said key is unprepared.

30. An arrangement as set forth in claim 29, wherein

said kernel means includes means for destroying all prepared keys corresponding to an object when said object is deleted;

each page frame and node frame on disk has a corresponding allocation count parameter (ALC);

each said ALC is incremented when the corresponding object is deleted if any keys to said deleted object were ever unprepared; and

said kernel means includes means for destroying unprepared keys corresponding to deleted objects, including means for determining when an unprepared key corresponds to a deleted object by comparing the ALC of said key with the ALC of the disk page or node frame at the disk address specified by said key's CDA;

whereby keys to deleted objects convey no authority.

31. In a capability based computer system,

first means serving as a factory for accepting a specific software program and using that program to process data; and

second means serving as a requestor for providing data to said factory and requesting that said data be processed in accord with said software program;

wherein said first and second means cooperate with one another such that the requestor can determine in advance, without inspection of said software program, that the data being processed and the processed data will be made available only to said requestor and such that said software program is not available to said requestor.

32. In a computer system having at least one central processing unit, memory means and a multiplicity of domains for performing predefined processes,

a plurality of first domains for running corresponding predefined software programs; and

a plurality of segment keeper domains for running a corresponding specific software program when one of said first domains suffers a memory fault;

wherein

said memory means includes a multiplicity of memory segments;

a multiplicity of said memory segments include means for specifying the segment keeper domain to be used upon the occurrence of a memory fault in said memory segment.

33. In a capability based computer system having a first means serving as a factory and second means serving as a requestor, a method comprising the steps of:

(a) verifying that said first means is capable of sending either data or processed data only to the provider of said data;

(b) accepting data from said requestor for processing by said first means in accord with a specific software program;

(c) processing said data; and

(d) returning the processed data to said requestor; wherein said step (a) is performed without inspection of said specific software program.

34. In a computer system having at least one central processing unit, memory means, a kernel, a plurality of domains, each domain comprising at least one node, each node providing slots for a plurality for keys, each key providing a token of authority to use a specified portion of said system's resources;

a method of securing the integrity of the data and the processes therein, the steps of the method comprising:

(a) filtering all uses of keys through said kernel, said kernel having the exclusive means for creating said keys and the exclusive means for resolving the authority conveyed by each said key, whereby domains can only indirectly manipulate and obtain keys through the invocation of said kernel functions;

(b) responding to the invocation by a (builder) domain of a first (factory creator entry) key by creating a factory and returning to the builder a builder's key;

(c) responding to the invocation by a builder of a builder's key corresponding to a specified factory, using a predefined parameter value, by installing in said factory a specified key as a specified component of said factory;

(d) responding to the invocation by a builder of a builder's key corresponding to a specified factory, using a predefined parameter value, by sealing said factory, thereby preventing the installation of any additional non-sensory keys in said factory;

(e) responding to the invocation by a (requestor) domain of a second (requestor's) key corresponding to a specified factory, using a first parameter value, by producing a predefined factory product, said factory product comprising a domain or a predefined memory structure having access to at least certain ones of the components installed in said factory; and

(f) responding to the invocation by a requestor of a requestor's key corresponding to a specified factory, using a second parameter value, by determining whether a specified factory has the ability to invoke, directly or indirectly, any non-sensory keys which are not included in a first predefined set, and returning to the requestor a parameter indicative of whether said factory has any such non-sensory keys.

35. A method as set forth in claim 34, wherein

said step (c) includes the step of installing a key defining a program component;

said step (e) includes the steps of

(e,1) creating a new (factory product) domain;

(e,2) defining the program component of said factory product and the starting address of said program component, said factory product's program component corresponding to the program component installed in the corresponding factory;

(e,3) providing access to certain predefined ones of the components installed in said factory; and

(e,4) starting the program in said factory product at said starting address;

whereby said program can modify the structure of said factory product and return a key to the modified factory product to said requestor.

36. A method as set forth in claim 35, wherein

said step (f) includes the step of comparing the set non-sensory components installed in a first (reference) factory with the set of non-sensory components installed in a second factory.

37. In a capability based data processing system having at least one central processing unit and memory means, said memory means including

a multiplicity of memory segments; and

means for holding a multiplicity of keys, each said key providing authority to its holder to use a specified portion of said system's resources;

an arrangement comprising:

a plurality of domains for performing predefined processes, each including means for holding a plurality of keys; and

kernel means coupled to said domains for providing said domains with a predefined set of kernel functions, said kernel means having the exclusive means for creating keys and the exclusive means for resolving the authority conveyed by each said key;

wherein

a plurality of said domains comprise factories for creating factory products comprising new domains for performing specified tasks;

a multiplicity of said keys are non-sensory keys, which convey the authority to directly or indirectly cause data to be transmitted to, or changed within, a domain other than the domain invoking said key;

a multiplicity of said keys are sensory keys, which convey the authority to directly or indirectly, sense or copy, data values or keys within specified objects in said system;

said arrangement includes factory setup means for a builder domain to install a software program and keys in a specified factory and to thereafter retain no keys which would provide access to the factory products produced by said specified factory; and

predefined ones of said kernel functions allow a requestor domain with a key to a specified one of said factories to determine whether said specified factory has any non-sensory keys not included in a first predefined set of keys;

whereby a requestor domain can determine if use of a specified factory could compromise the confidentiality of data provided by said requestor domain to said factory.

38. In a computer system having a multiplicity of domains for running specific software programs and memory means including a multiplicity of memory segments, a method comprising the steps of:

(a) defining for each of a multiplicity of said memory segments a segment keeper domain, including a predefined memory fault resolution software program, for resolving memory faults occurring in said memory segment;

(b) running in each of a plurality of said domains a process in accord with a corresponding specific software program;

(c) upon the occurrence of a memory fault in any of said plurality of domains during the operation of said running step, transferring the process from the domain in which said memory fault occurred to the segment keeper domain corresponding to the memory segment in which said memory fault occurred for running in accord with the memory fault resolution software program therein;

whereby said memory fault can be resolved and the process returned to the domain in which said memory fault occurred; and

the method of memory fault resolution can differ in accordance with the memory segment in which the memory fault occurs.

39. In a computer system having at least one central processing unit, a multiplicity of domains for performing predefined processes, and memory means including a multiplicity of memory segments, a method comprising the steps of:

running a process in accord with predefined software programs in each of a plurality of first domains; and

upon the occurrence of a memory fault in one of said first domains, transferring said process to another of said multiplicity of domains, selected in accord with the memory segment in which the memory fault occurred, for running a corresponding specific software program;

whereby said memory fault can be resolved and the process returned to the domain in which said memory fault occurred; and

the method of memory fault resolution can differ in accordance with the memory segment in which the memory fault occurs.

This invention relates generally to a data processing system and more specifically to an apparatus and method for ensuring the confidentiality of data and data processing in a data processing system.

BACKGROUND OF THE INVENTION

The security of data and processes in a data processing system depends on many features of the system. In one aspect, security is implemented through the use of usernames and passwords. In a more fundamental aspect, security is implemented through the design of the internal architecture of the computer system. This architecture is typically implemented with hardware, firmware and software. The present invention involves the use of a new fundamental architecture designed on the principal of "mutual distrust". That is, each user is assumed to have interests inimical to all other users of the computer system, including some of the system programmers. The structure of the system is such that a user can use system utilities without having to trust the author of the utility; i.e., the utility cannot steal a copy of the user's data, or make any other use thereof, without the user's permission.

Traditional prior art computer systems have three types of deficiencies which are addressed by the present invention: lack of protection between programs or users, the method of delegating authority to access facilities, and the method of implementing "policies", i.e. system rules about who can do what to whom.

The prior art has generally accorded each user a level, the lower levels providing services for the higher levels, and with a defined interface between the levels. Most contemporary systems are implemented in two or three (and sometimes four) distinct levels. The lowest level, often called the supervisor, interfaces directly with the hardware and input/output devices, supports multi-programming, and provides other "basic" services. The supervisor provides an execution environment for the higher levels, which are variously called an address space, job, virtual machine, partition, or virtual memory.

The (optional) second level runs within a protected part of this virtual memory and is often called a monitor. It usually contains such facilities as command language interpreters, access methods, directory support and debugging tools. In most systems the code that implements these facilities is common to all virtual memories, but each has private working storage provided by the supervisor. The third layer contains all user-level programs, including user written programs, compilers, and many system-provided utility functions that do not require the privileges of the lower layers. Note that the three layers exist in a hierarchical relationship. The second layer controls the third, and the first layer supervisor controls all occurrences of virtual memory.

Strong mechanisms provide firewalls between the three layers, but all programs within a layer run in a common area, with common authority to execute functions allocated to that layer. For example, if an application package contained several programs including some mathematical subroutines, an interface to a graphics system, and a data base management system interface, all the code supporting these functions would co-exist in a single virtual memory. Since all share the same memory, there is no assurance that the code in any one of these components will not destroy or alter data belonging to any of the other components.

The inability to protect programs from each other exists at each of the three levels of the operating system. In each case, the consequences are propagated throughout the level in which the failure occurs. At the third level an application program is terminated or produces incorrect results. At the second level a job or file is compromised. At the first level the entire computer system can be disabled by a simple error. As systems become more complex and interrelated, debugging and maintenance require an increased level of resources to reduce the frequency of these failures.

Reliability, integrity and security can be attained by separating each layer into individual isolated entities which can only communicate with each other through explicit and controlled interfaces. In such an environment, the graphics package, for example, could exist in its own virtual memory with its code and data completely protected. If any failure occurred in the graphics package, it would be possible to know with great certainty that the failure was due to a flaw in that graphics package, and those parts of the application that did not depend upon the performance of the graphics package would continue to run. This architecture is inherently more reliable because it provides a fail-soft capability, thus reducing the scope and intensity of any failure. If all levels of the data processing system are structured in this manner, the entire system will be more secure and flexible than the prior art systems.

The second problem referred to above is that the authority to do things (e.g. run programs, access files) is associated with an individual username or address space. Thus if the data base manager has the authority to access a data base, any part of the application may access that data base directly (if it knows the passwords), completely bypassing internal security mechanisms and filters of the data base manager. Similarly, all of a user's files are accessible by any program run by the user. While some systems install monitors to keep logs of who accessed what file in order to detect people doing things that they shouldn't, few, if any, prior art systems provide an explicit mechanism to prevent this kind of penetration and none are believed to be as effective as a system incorporating the invention described herein.

The third difficulty referred to above is that rules or system policies are often implemented in firmware or software that is diffused in many obscure modules. Examples of this class of rules are "any program which runs under a username may have access to all of the files owned by the user," or "anyone who can produce the correct password may access the file," or "no one except the owner may access the file." (Note that typically a file can be owned only by a user, not by a program.)

In each of these three areas--system organization, authority control, and policy implementation--prior art systems have built-in architectural barriers. It is generally not possible to correct them, retrofit them, or add selected facilities which remove the deficiencies without completely redesigning and reimplementing the systems. However, it should be noted that the problems addressed by the present invention are not necessarily inherent in three-layer supervisor-monitor-user type systems; rather they are generally found in prior art systems due to a common underlying viewpoint in their design.

At least some of the prior art concerning capability based computer systems and corresponding operating systems is described in the following articles: P. J. Denning, "Fault-Tolerant Operating Systems," ACM Computing Surveys, vol 8, no. 4, pp. 359-390 (Dec. 1976); T. A. Linden, "Operating System Structures to Support Security and Reliable Software," ACM Computing Surveys, vol. 8, no. 4, pp. 409-445 (Dec. 1976); G. Cox, W. Corwin, K. Lai, F. Pollack, "A Unified Model and Implementation for Interprocess Communication in a Multiprocessor Environment," Proc. Eighth Sympsm. Operating Systems Principles, vol. 15, no. 5, pp. 125-126 (Dec. 1981); K. C. Khan, W. M. Corwin, et al., "iMAX: A Multiprocessor Operating System for an Object-Based Computer," Proc. Eighth Sympsm. Operating Systems Principles, vol. 15, no. 5, pp. 127-136 (Dec. 1981); and F. Pollack, K. Kahn, R. Wilkinson, "The iMAX-432 Object Filing System," Proc. Eighth Sympsm. Operating Systems Principles, vol. 15, no. 5, pp. 137-147 (Dec. 1981). See also the sources cited in these articles.

The capability systems described in the above cited articles describe capability based structures and methods for at least theoretically preventing unauthorized use of system resources. As noted in the article by Denning, there has been a paucity of actually working capability based systems, and even fewer that have been used commercially, indicating that certain problems involved in the use or implementation of capability systems have either not yet been recognized or not yet solved. There is also the problem that computer designers and operating system programmers are generally less familiar with capability systems than with conventional computer architectures.

The present invention is directed primarily at one problem not even recognized as a problem in the cited articles and at several other problems involved in the practical implementation of a capability system. The major problem not recognized as such in the prior art is: that merely using a capability system to prevent unauthorized uses of system resources does not solve the practical problem that the user of an application may not trust the author of the application not to steal a copy of his data. In other words, in prior art systems either (a) a first user has to give to a second user a key (i.e., a capability) to the data that the first user wants to be processed by the second user's program, or (b) the second user has to pass to the first user a key to his program. In either case, if the two users do not trust each other, the result is entirely unsatisfactory because one user can steal a copy of the other user's proprietary information (i.e. data or program). In other words, the mere use of a capability system does not solve basic security problems because, in order to get anything useful done, the prior art systems required that users share their capabilities with others who they do not necessarily trust.

SUMMARY OF THE INVENTION

It is therefore a primary object of the present invention to provide a capability based computer system that permits mutually untrusting users to cooperate in well defined ways that do not compromise the security of any user's data and/or programs.

It is a second object to provide a capability based computer architecture of practical design that is capable of implementation in either hardware, firmware, software or a combination thereof.

In accordance with these objectives there is provided a capability based computer system including a plurality of domains, each including at least one node, where domains are the basic operational unit or virtual machine in the system. Each node has a number of slots for holding keys, also known as capabilities. Keys are used as tokens of authority to use a specified portion of the system's resources. A domain's capabilities are defined entirely by the keys it holds. Each key includes a pointer to an object in the system corresponding to the identity of the key and also includes a tag indicating its key type and the scope of authority provided thereby. A kernel has the exclusive means for creating keys and the exclusive means for resolving the authority conveyed by each key. A limited number of kernel functions are available to all domains; but the invocation of each kernel function requires the possession of a corresponding key. The kernel functions limit the generation of keys in accordance with predefined policies which guarantee the security of domains and other objects in the system. A plurality of factories, which are special domains having an ascertainable set of non-sensory keys, enable other domains to share resources without trusting one another. A "hole comparator" can be used to determine if a particular factory has the ability to invoke, directly or indirectly, any non-sensory keys which are not included in a first predefined set, whereby a domain can determine if the specified factory is trustworthy or at least potentially untrustworthy.

Additional objects and features of the invention will be more readily apparent from the following detailed description and appended claims when taken in conjunction with the drawings, in which:

DESCRIPTION OF DRAWINGS

FIG. 1 is a block diagram of a basic domain configuration.

FIG. 2a is a block diagram of a computer system incorporating the present invention. FIG. 2b is a block diagram of a memory structure called item space.

FIGS. 3a-3c are block diagrams of three basic key structures. FIG. 3d is a block diagram of a doubly linked list of keys, all of which point at the same object. FIG. 3e is a block diagram of a device i/o key.

FIG. 4a is a block diagram of a node frame. FIGS. 4b and 4c are block diagrams of a core table entry and a core annex entry. FIG. 4d is a block diagram of queue header.

FIG. 5a is block diagram of a memory tree. FIG. 5b is a block diagram of page and segment keys. FIG. 5c is a block diagram of an atypical memory tree. FIG. 5d is a block diagram of memory sharing. FIG. 5e is a block diagram of a red segment node. FIG. 5f is a block diagram of revocable memory sharing.

FIG. 6 is a block diagram of a derived information block.

FIG. 7 is a block diagram of the relationship between a domain and its meter, meter keeper, domain keeper and segment keeper.

FIG. 8a is block diagram of two domains in remote computer systems sharing a data base. FIG. 8b is a block diagram of two domains sharing memory using a copy-on-modify scheme.

FIGS. 9a through 9d are block diagrams of gate jumps between domains and of the exit and entry blocks used to effect gate jumps.

FIG. 10a is a block diagram of the process of forming new domains. FIG. 10b is a block diagram of the process of forming domain creators.

FIG. 11a is a block diagram of the relationship between a factory creator, a builder domain, a factory, a requestor domain, and a factory product. FIG. 11b is a detailed block diagram of a factory. FIG. 11c is a partial block diagram of a particular factory. FIG. 11d is a block diagram of a factory and its copies. FIG. 11e is a detailed block diagram of a factory product. FIG. 11f is a block diagram showing the use of a virtual copy segment keeper factory. FIG. 11g is a block diagram of two factory processes.

FIG. 12 is a block diagram of a new user domain with a womb key which references a supernode.

DESCRIPTION OF THE PREFERRED EMBODIMENT

Basic Concepts. The present invention falls in the class of data processing systems known as capability systems. As a capability system, however, the invention does not comprise an operating system in the conventional sense. The invention instead provides an architecture, including a set of primordial objects with which the architecture is implemented, upon which an operating system can be built.

In the following descriptions, the terms computer and data processing system are used interchangeably. The term "object" refers to any basic system construct, such as a key, node, domain, page, or segment.

Whenever bit or byte positions are described using numbers, position 0 is the leftmost and most significant position and the positions proceed rightwards and towards the least significant bit or byte as the position number increases.

The objects, methods and functions described herein can be implemented in either hardware, firmware or software or some combination thereof. It is anticipated, but without any intended limitation on the scope of the invention, that the most efficient implementation of the invention will be such a combination, with many of the kernel functions (described below) implemented in firmware and with some of the most fundamental kernel functions implemented in hardware.

For the purposes herein, the computer system's memory is considered to be split into two major portions: core memory and disk memory. The term core memory refers to high speed memory used by the data processing system for current calculations, i.e., memory to which the computer has relatively direct access. High speed memories currently have access times typically ranging from 3 nanoseconds to 250 nanoseconds. More generally, high speed or "core" memory has an access time of no more than 20 times (and typically no more than 3 times) the length of the basic instruction cycle of the computer's central processing unit (CPU). Using current technology, core memory typically includes 1 Megabyte (1 Mbyte) to 1 Gigabyte (i.e., 10.sup.9 bytes) of high speed semiconductor memory, possibly including a mix of very high speed cache memory and medium speed memory. The term core memory does not imply the use of magnetic core technology memories. Furthermore, the system's core memory may be either physically and/or logically divided into many components corresponding to different objects and sets of objects in the system.

The term disk memory refers to relatively slow memory, generally having an access time in excess of 20 times (and typically at least 1000 times) the length of the basic CPU instruction cycle. Using current technology, disk memory typically includes one or more magnetic disk memory units having a total capacity of anywhere from 20 to 10,000 megabytes. The term disk memory is not limited to magnetic disk technology and may include bubble memory, slow semiconductor memory, laser disks, magnetic tapes, and other storage technologies.

For most purposes herein, the preferred embodiment is described in the context of a single CPU computer system. However the architecture of the system lends itself to multiple CPU systems, and certain modifications for multiple CPU systems are described below.

The basic or primordial objects used in the invention are domains, nodes, keys and pages. A page is a unit of memory that is used to hold data or computer programs, but generally is not used to hold nodes or keys. A node is a memory array having a number of slots for holding keys. Keys are the basic unit for holding and conveying authority to use the system's resources. Each key has a key type indicating its general function. Most keys act as pointers to the object for which they convey authority. Domains are the basic operational unit in the system, similar in some ways to a virtual machine or user in conventional computer systems. However, domains are, at least initially, much smaller objects than conventional virtual machines. A typical user application will use more than one, and often many, domains to perform its functions. A well formed domain can comprise just a few linked nodes. More complicated domains are built up using keys to memory segments and keys to other domains.

Each domain is completely protected from unauthorized access or modification by programs in other domains. A first domain can be affected only by domains which have a key to the first domain or to one of that domain's objects. For domains without such keys, the first domain is not only an impervious black box, its very existence is not discernible.

All domain functions and key functions are supervised by a ker