Computer security system

• US 4,584,639 A
• Filed: 12/23/1983
• Issued: 04/22/1986
• Est. Priority Date: 12/23/1983
• Status: Expired due to Term

• Current Assignee: Key Logic Incorporated
• Original Assignee: Key Logic Incorporated
• Inventors: Hardy, Norman
• Primary Examiner(s): Zache, Raulfe B.
• Application Number:
  US06/565,194
• Time in Patent Office: 851 Days
• Field of Search: 364/200 MS File
• US Class Current: 726/2
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores

Abstract

A capability based computer system includes means, called a factory, for allowing two domains to share resources in a secure manner. Factories are special domains which, in combination with corresponding kernel functions, allow a first domain (called a builder domain) to install a program and other components in a factory for use by other domains, and then to seal the factory, thereby leaving the builder domain with no keys to the factory except a special type of entry key called a requestor key.

The holders of requestor keys can use the program in the factory by invoking the requestor key. This causes the factory to set up a new special domain for the requestor which allows the requestor to use the program in the factory to process data without being able to inspect the program. Further, the factory mechanism includes means for the requestor to confirm that the factory includes no keys which could compromise the confidentiality of the requestor'"'"'s data.

A second aspect of the present invention is the ability to provide different memory fault resolution mechanisms (called segment keeper domains) for different memory segments.

Claims

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.