System for multilevel secure database management using a knowledge base with release-based and other security constraints for query, response and update modification

Abstract

Apparatus for an integrated architecture for an extended multilevel secure database management system. The multilevel secure database management system processes security constraints to control certain unauthorized inferences through logical deduction upon queries by users and is implemented when the database is queried through the database management system, when the database is updated through the database management system, and when the database is designed using a database design tool.

Claims

We claim:

1. Apparatus for an integrated architecture for an extended multilevel secure database management system which processes security constraints to control unauthorized inference through logical deduction upon queries by users and implemented when the database is queried through the database management system, when the database is updated through the database management system, and when the database is designed, the integrated architecture comprising:

a knowledge base for storing the security constraints, application data and information on responses released from the multilevel secure database management system;

a multilevel database which contains data classified at different security levels;

a multilevel metadatabase to store schemes describing data in the multilevel database, the schemas classified at said different security levels;

the multilevel secure database management system utilized to access the multilevel database for queries and updates and to access the multilevel metadatabase for querying and updating the schemas by users cleared to said different security levels;

a query processor augmenting the multilevel secure database management system and accessing the knowledge base to examine the security constraints, application data and responses already released and to modify queries to prevent unauthorized inferences and to output a modified query for evaluation by the multilevel secure database management system, the multilevel secure database management system providing an output to the query processor which examines the security constraints, the application data, and responses already released, and modifies the responses to prevent unauthorized inferences,

an update processor augmenting the multilevel secure database management system for examining some of said security constraints and to assign security levels to the data;

the update processor complementing functions of the query processor such that if some of the constraints are processed during updates and the data is assigned appropriate security levels, said constraints need not be processed by the query processor, for performance enhancement the said update processor also being used as an off-line tool to determine the security levels of the data;

a multilevel database design tool which examines some of the security constraints and assigns security levels to the schemas, the schemas then being input to the multilevel secure database management system for storage in the multilevel metadatabase at the appropriate security levels, the design tool thereby complementing the functions of the query processor so that said some of the constraints need not be processed by the query processor for performance enhancement; and

a user interface which accepts query requests from the user and passes the query to the query processor and accepts update requests from the user and passes it to the update processor if operating on-line or the user interface accepts the request from the user and passes it to the multilevel database management system if it is off-line, the user interface accepting the schema query request from the user and passes the query request to the multilevel secure database management system, the user interface further accepting the schema update requests from the user and passes it to the multilevel secure database management system.

2. The apparatus of claim 1 wherein the query processor comprises:

a user interface manager to provide the user interface and to accept the query requests;

a constraint manager to manage the security constraints and the knowledge base;

a query modifier which receives query requests from the user interface manager, examines the security constraints by communicating with the constraint manager and subsequently modifies the query which is evaluated against the multilevel secure database management system;

a response processor which accepts the response from the multilevel secure database management system, examines the security constraints by communicating with the constraint manager, and determines which parts of the response are to be released to the user; and

a release database manager which manages the release information and provides input to the query modifier and the response processor to carry out their functions.

3. The apparatus of claim 1 wherein the update processor comprises:

a user interface manager for communicating with the user;

a constraint manager which manages the security constraints;

a security level computer which communicates with the constraint manager and computes the security level of data to be updated; and

a level upgrader which gets an input from the security level computer, creates an update process at the appropriate level and interfaces to the multilevel secure database management system.

4. The apparatus of claim 1 wherein the multilevel database design tool is a monolithic module whose inputs are the security constraints and initial schemas, and whose outputs are modified schemas and their security levels which can be entered into the multilevel metadatabase.

Description

BACKGROUND OF THE INVENTION

It is possible for the users of a database management system to draw inferences from the information that they obtain from the database. The inference process can be harmful if the inferred knowledge is something that the user is not authorized to acquire. That is, a user acquiring information which he is not authorized to know has come to be known as the inference problem in database security. In a multilevel operating environment, the users are cleared at different security levels as they access a multilevel database where the data is classified at different sensitivity levels. A multilevel secure database management system (MLS/DBMS) manages a multilevel database where its users cannot access data to which they are not authorized. Currently available multilevel secure database management systems cannot provide a solution to the inference problem, where users of the system issue multiple requests and consequently infer unauthorized knowledge.

Two distinct approaches to handling the inference problem have been proposed in the past. They are:

(i) Handling of inferences during database design.

(ii) Handling of inferences during query processing.

The work reported in Morgenstern, M., May 1987, "Security and Inference in Multilevel Database and Knowledge Base Systems," Proceedings of the ACM SIGMOD Conference, San Francisco, Calif.; Hinke, T., April 1988, "Inference Aggregation Detection in Database Management Systems," Proceedings of the IEEE Symposium on Security and Privacy, Oakland, Calif.; Smith, G., May 1990, "Modelling Security-Relevam Data Semantics," Proceedings of the 1990 IEEE Symposium on Security and Privacy, Oakland, Calif.; and Lunt, T., May 1989, "Inference and Aggregation, Facts and Fallacies," Proceedings of the IEEE Symposium on Security and Privacy, Oakland, Calif. focuses on handling inferences during database design where suggestions for database design tools are given.

In contrast, the work reported in Thuraisingham, B., December 1987, "Security Checking in Relational Database Management Systems Augmented with Inference Engines," Computers and Security, Volume 6, No. 6.; Thuraisingham, B., August 1990, The Use of Conceptual Structures in Handling the Inference Problem, Technical Report M90-55, The MITRE Corporation, Bedford, Mass.; Keefe, T., B. Thuraisingham, and W. Tsai, March 1989, "Secure Query Processing Strategies," IEEE Computer, Volume 22, No. 3, pp. 63-70 focuses on handling inferences during query processing.

Other work on handling the inference problem can be found in Buczkowski, L.J., and Perry, E.L., "Database Inference Controller," Interim Technical Report, Ford Aerospace Corporation, February 1989, where an expert system tool which could be used by the System Security Officer off-line to detect and correct logical inferences is proposed. Rowe, N., February 1989, "Inference Security Analysis Using Resolution Theorem-Proving," Proceedings of the 5th International Conference on Data Engineering, Los Angeles, Calif. investigates the use of Prolog for handling inferences.

In Thuraisingham, B., August 1990, The Use of Conceptual Structures in Handling the Inference Problem, Technical Report M90-55, The MITRE Corporation, Bedford, Mass. various strategies that users could utilize to draw inferences are identified. This set of strategies is more complete than the one proposed in Denning, D.E., et al., "Views as a Mechanism for Classification in Multilevel Secure Database Management Systems," Proceedings of the IEEE Symposium on Security and Privacy, Oakland, Calif. 1986. In Thuraisingham, B., August 1990, The Use of Conceptual Structures in Handling the Inference Problem, Technical Report M90-55, The MITRE Corporation, Bedford, Mass., some preliminary ideas on novel approaches to handling the inference problem are discussed. These include approaches based on mathematical programming, inductive inference, information theory and game theory. Further, in Thuraisingham, B., August 1990, The Use of Conceptual Structures in Handling the Inference Problem. Technical Report M90-55, The MITRE Corporation, Bedford, Mass. complexity of the inference problem is analyzed based on concepts in recursive function theory.

The present application discloses an apparatus and method for designing a multilevel secure database management system that can resolve the inference problem via the effective use of security constraints. In the new system, some security constraints are handled during the query operation, some during the update operation, some during the database design operation. The major advance achieved by the invention disclosed herein over prior art is the use of security constraints in a novel way to handle the inference problem. In addition, prototypes which effectively handle these constraints are also disclosed. Further advances relate to the use of conceptual structures for representing and reasoning about multilevel applications, the development of a logic for secure data/knowledge base management systems and the development of a knowledge base inference controller.

SUMMARY OF THE INVENTION

The invention disclosed herein is an apparatus and method for querying, designing and updating a multilevel secure database management system in order to resolve the inference problem.

A method for processing security constraints in a multilevel secure database management system are disclosed. Security constraints are rules that assign security levels to data. This method is based on specifying security constraints as horn clauses. The apparatus and method disclosed here uses nine types of security constraints:

1. Simple constraints that classify a database, a relation or an attribute;

2. Content-based constraints that classify any part of the database depending on the value of some data;

3. Event-based constraints that classify any part of the database depending on the occurrence of some real-world event;

4. Association-based constraints that classify associations between attributes and relations;

5. Release-based constraints that classify any part of the database depending on the information that has been previously released;

6. Aggregate constraints that classify collections of data;

7. Level-based constraints that classify any part of the database depending on the security level of some data;

8. Fuzzy constraints that assign fuzzy values to their classifications; and

9. Logical constraints that specify implications.

The method and apparatus disclosed are based on processing certain security constraints during query processing, certain constraints during database updates and certain constraints during database design. FIG. 1 shows a schematic view of the integrated architecture. The two main tasks involved in constraint handling are constraint generation and constraint enforcement. The constraint generator takes the specification of the multilevel application and outputs the initial schema and the constraints that must be enforced. The database design tool takes this output as its input and designs the database. The constraints and schema produced by the database design tool are used by the update processor and the query processor. Although the query processor, update processor and database design tool are separate modules, they all constitute the solution to constraint processing in multilevel relational databases; these three approaches provide an integrated solution to security constraint processing in a multilevel environment. In the architecture shown in FIG. 1, the constraints and schema which are produced by the constraint generator are processed further by the database design tool. The modified constraints are given to the constraint updater in order to update the constraint database. The schema is given to the MLS/DBMS to be stored in the metadatabase. The constraints in the constraint database are used by the query and update processors. We assume that there is a trusted constraint manager process which manages the constraints. In a dynamic environment where the data and the constraints are changing, the query processor will examine all the relevant constraints and ensure that users do not obtain unauthorized data.

Constraints that classify an attribute or collection of attributes taken together are handled during the database design operation. These include the simple and association-based constraints. When constraints are processed during the database design operation, the database design tool will determine the security levels to be assigned to the database schema (i.e., the information about the data in the database).

A query processor is disclosed that has the ability to handle all of the security constraints. Most users usually build their reservoir of knowledge from responses that they receive by querying the database. It is from this reservoir of knowledge that they infer unauthorized information. Moreover, no matter how securely the database has been designed or how accurately the data within is labeled, users could eventually violate security by inference because they are continuously updating their reservoir of knowledge as the world evolves. It is not feasible to have to :redesign the database or to have to reclassify the data continuously. When constraints are processed during the query operation, the query processor will compute the security levels of the data before release and ensure that only the data at or before the user's level is released.

The processor (also called an inference controller) protects against certain security violations via inference that can occur when users issue multiple requests and consequently infer unauthorized knowledge. The processor also uses security constraints as its mechanism for determining the security level of data. The security constraints are used as deviation rules. The architecture for a query processor is shown in FIG. 2. This architecture can be regarded as a loose coupling between a multilevel relational database management system and a deductive manager. The deductive manager is referred to as the query processor. It operates on-line.

An update processor prototype is disclosed. The processor utilizes simple and content-dependent security constraints as guidance in determining the security level of the data being updated. The use of security constraints can thereby protect against users incorrectly labelling data as a result of logging in at the wrong level, against data being incorrectly labelled when it is imported from systems of different modes of operation and against database inconsistencies as a consequence of the security label of data in the database being affected by data being entered into the database. The architecture for the update processor is shown in FIG. 3. This architecture can be regarded as a loose coupling between a multilevel relational database management system and a deductive manager. The deductive manager is referred to as the update processor. It can be used on-line where the security levels of the data are determined during database inserts and updates, or it could be used off-line as a tool that ensures that data entered via bulk data loads and bulk data updates is accurately labelled.

The security level of an update request is determined by the update processor as follows. The simple and content-dependent security constraints associated with the relation being updated and with a security label greater than the user log in security level are retrieved and examined for applicability. If multiple constraints apply, the security level is determined by the constraint that specifies the highest classification level. If no constraints apply, the update level is the Logan security level of the user. The update processor does not determine the security level of the data solely from the security constraints, but utilizes the constraints as guidance in determining the level of the input data.

In the disclosed apparatus and method, all constraints except for the release and aggregate constraints can theoretically be handled during the database update operation. When constraints are processed during the update operation, the update processor will compute the security levels of the data being updated and ensure that the data is stored at the appropriate level.

An MLS DBMS provides assurance that all objects in a database have a security level associated with them and that users are allowed to access only the data which they are cleared. Additionally, it provides a mechanism for entering multilevel data but relies on the user to Logan at the level at which the data is to be entered. The Update Processor will provide a mechanism that can operate as a standalone tool with a MLS DBMS to provide assurance that data is accurately labelled as it is entered into the database. This could significantly enhance and simplify the ability of an MLS DBMS to assure that data entered via bulk data loads and bulk data updates is accurately labelled.

Another significant use for an update processor is in operation with an Inference Controller which functions during query processing. The Inference Controller protects against certain security violations via inference that can occur when users issue multiple requests and consequently infer unauthorized knowledge. The Inference Controller Prototype also utilizes security constraints as its mechanism for determining the security level of data. The security constraints are used as derivation rules as they are applied to the data during query processing. Addressing all of the security constraint types mentioned above could add a significant burden to the query processor particularly if the number of constraints is high. To enhance the performance of the query processor, the Update Processor can be utilized to address certain constraint types as data is entered into the database, in particular, simple and content-based constraints, alleviating the need for the query processor to handle these constraint types. We assume that the security constraints remain relatively static, as reliance on the Update Processor to ensure that data in the database remains consistent would be difficult, particularly in a volatile environment where the constraints change dynamically. An additional concern is that database updates could leave the database in an inconsistent state. The Update Processor, however, is designed to reject updates that cause a rippling effect and thus leave the database in an inconsistent state.

A method and apparatus for handling constraints during database design is disclosed. The database design tool is shown in FIG. 4. The constraint generator takes the specification of the multilevel application and outputs the initial schema and the constraints that must be enforced. The database design tool takes this output as its input and designs the database. The constraints and schema produced by the database design tool are used by the update processor and the query processor.

BRIEF DESCRIPTION OF THE DRAWING

FIG. 1 is a block diagram of the integrated architecture of the invention.

FIG. 2 is a block diagram illustrating the query processor of the invention.

FIG. 3 is a block diagram illustrating the update processor of the invention,

FIG. 4. is a block diagram illustrating a multi-level database design tool.

FIG. 5 is a block diagram illustrating constraint generation and enforcement.

FIG. 6 is a block diagram illustrating high-level architecture.

FIG. 7 is a schematic illustration of a constraint structure.

FIG. 8 is a schematic illustration of the major modules of the invention.

FIG. 9 is a block diagram illustrating another high-level architecture.

FIG. 10 is a block diagram illustrating the implementation architecture according to the invention.

PREFERRED EMBODIMENT

The theoretical approach to security constraint processing is first presented. Then we give the implementation details for the query processor, the update processor and the database design tool.

1. SECURITY CONSTRAINTS

1.1 OVERVIEW

Security constraints are rules which assign security levels to the data. They can be used either as integrity rules, derivation rules or as schema rules (such as data dependencies). If they are used as integrity rules, then they must be satisfied by the date in the multilevel database. If they are used as derivation rules, they are applied to the data during query processing. If they are used as data dependencies, they must be satisfied by the schema of the multilevel database.

We have defined various types of security constraints. They include the following:

(i) Constraints that classify a database, relation or an attribute. These constraints are called simple constraints.

(ii) Constraints that classify any part of the database depending on the value of some data. These constraints are called context-based constraints.

(iii) Constraints that classify any part of the database depending on the occurrence of some real-world event. These constraints are called event-based constraints.

(iv) Constraints that classify associations between data (such as tuples, attributes, elements, etc.). These constraints are called association-based constraints.

(v) Constraints that classify any part of the database depending on the information that has been previously released. These constraints are called release-based constraints. We have identified two types of release-based constraints. One is the general release constraint which classifies en entire attribute depending on whether any value of another attribute has been released. The other is the individual release constraint which classifies a value of another attribute depending on whether a value of another attribute has been released.

(vi) Constraints that classify collections of data. These constraints are called aggregate constraints.

(vii) Constraints which specify implications. These are called logical constraints.

(viii) Constraints which have conditions attached to them. These are called constraint with conditions.

(ix) Constraints that classify any part of the database depending on the security level of some data. These constraints are called level-based constraints.

(x) Constraints which assign fuzzy values to their classifications. These are called fuzzy constraints.

We will give examples of constraints to each category. In our examples, we assume that the database consists of two relations SHIPS and ASSIGNMENT where SHIPS has attributes S#, SNAME, CAPTAIN, and A# (with A# as the key), and ASSIGNMENT has attributes A#, MISSION, and DESTINATION (with A# as the key). Note that A# in SHIPS and A# in ASSIGNMENT takes values from the same domain. The constraints may be expressed as some form of logical rules. We have chosen horn clauses to represent the constraints. This way we could eventually take advantage of numerous techniques that have been developed for logic programs.

Simple constraints: R(A1, A2, . . . An).fwdarw.Level(Ai1, Ai2, . . . Ait)=Secret [Each attribute Ai1, Ai2, . . . Ait of relation R is Secret]Example: SHIPS (S#, SNAME, CAPTAIN, A#).fwdarw.Level (CAPTAIN)=Secret

Content-based constraints: R(A1, A2, . . . An) AND COND (Value (B1, B2, . . . Bm)).fwdarw.Level (Ai1, Ai2 . . . Ait) =Secret [Each attribute Ai1, Ai2, . . . Ait of relation R is Secret if some specific condition is enforced on the value of some data specified by B1, B2, . . . Bm]Example: SHIPS (S#, SNAME, WEIGHT, A#) AND (Value (SNAME)=CHAMPION).fwdarw.Level (CAPTAIN)=Secret.

Association-based constraints (also called context or together constraints): R(A1, A2, . . . An).fwdarw.Level (Together (Ai1, Ai2, . . . Ait))=Secret [The attributes Ai1, Ai2, . . . Ait of relation R taken together are Secret]Example: SHIPS (S#, NAME, CAPTAIN, A#).fwdarw.Level (Together (SNAME, CAPTAIN))=Secret.

Event-based constraints: R(A1, A2, . . . An) AND Event(E).fwdarw.Level (Ai1, Ai2, . . . Ait)=Secret [Each attribute Ai1, Ai2, . . . Ait of relation R is Secret if event E has occurred]Example: SHIPS (S#, SNAME, CAPTAIN, A#) AND Event (Change of President).fwdarw.Level (CAPTAIN), A#)=Secret.

General release-based constraints: R(A1, A2, . . . An) AND Release(Ai, Unclassified) CONG.fwdarw.Level(Aj)=Secret The attribute Aj of relation R is Secret if the attribute i has been released at the Unclassified level] Example: SHIPS(S#, SNAME, CAPTAIN, A#) AND Release(SNAME, Unclassified).fwdarw.Level(CAPTAIN)=Secret.

Individual release-based constraints: R(A1, A2, . . . An) AND Individual-Release(Ai, Unclassified).fwdarw.Level(Aj)=Secret The individual release-based constraints classify elements of an attribute at a particular level after the corresponding elements of another attribute have been released. They are more difficult to implement than the general release-based constraints. In our implementation, the individual release-based constraints are handled after the response is assembled while all of the other constraints are handled before the response is generated.

Aggregate constraints: Aggregate constraints classify collections of tuples taken together at a level higher than the individual levels of the tuples in the collection. There could be some semantic association between the tuples. We specify these tuples in the following form: R(A1,A2, . . . An) AND Set(S,R) AND Satisfy(S,P).fwdarw.Level(S)=Secret This means that if R is a relation and S is a set containing tuples of R and S satisfied some property P, then S is classified at the Secret level. Note that P could be any property such as "number of elements is greater than 10."

Logical constraints: Logical constraints are rules which are used to derive new data from the data in the database. The derived data could be classified using one of the other constraints. Logical constraints are of the form: Ai==>Aj if condition C holds. This constraint can be instantiated as follows: The location of a ship implies its mission if the location is the Persian Gulf.

Other constraints:

There are several other types of constraints which could be incorporated into our design fairly easily. These include level-based constraints and fuzzy constraints. We describe them below.

Level-based constraints: R(A1,A2, . . . An) AND Level(Ai)=Unclassified .fwdarw.Level(Aj)=Secret (The attribute Aj of relation R is Secret if the attribute Ai is unclassified) Example: SHIPS(S#,SNAME,CAPTAIN,A#) AND Level(SNAME)=Unclassified.fwdarw.Level(CAPTAIN)=Secret

Fuzzy Constraints: Fuzzy constraints are constraints which use fuzzy values. They can be associated with any of the other types of constraints. An example of a fuzzy constraint which is associated with a content-based constraint is given below. R(A1,A2, . . . An) AND COND(Value(B1,B2, . . . Bm)).fwdarw.Level(Ail,Ai2, . . . Ait)=Secret and Fuzzyvalue=r (Each attribute Ai1,Ai2, . . . Ait of relation R is Secret with a fuzzy value of r if some specific condition is enforced on the values of some data specified by B1,B2, . . . Bm)

Example: SHIPS(S#,SNAME,CAPTAIN, A#) AND (Value(SNAME )=CHAMP I 0 N)->Level(CAPTAIN)=Secret and Fuzzyvalue=0.8.

Complex constraints

The examples of constraints that we have given above are enforced on a single relations only. Note that constraints can also be enforced across relations. We call such constraints complex constraints. An example is given below:

R1(A1,A2, . . . An) & R2(B1,B2, . . . Bm) & R1.Ai=R2.Bj(1<i<n,i<j<m).fwdarw.Level(Together(Ak,Bp))=Secret where 1<k<n,1<p<m)

This constraint states that pair of values involving the kth attribute of R1 and the pth attribute of R2 are Secret provided the corresponding values (i.e. in the same row) of the ith attribute of R1 and the jth attribute of R2 are equal.

1.2 APPROACH TO SECURITY CONSTRAINT PROCESSING

Security constraints enforce a classification policy. Therefore it is essential that constraints are manipulated only by an authorized individual. In our approach constraints are maintained by the SSO. That is, constraints are protected from ordinary users. We assume that constraints themselves could be classified at different security levels. However, they are stored at system-high. The constraint manager, which is trusted, will ensure that a user can read the constraints classified only at or below his level.

Our approach to security constraint processing is to handle certain constraints during query processing, certain constraints during database updates and certain constraints during database design. The first step was to decide whether a particular constraint should be processed during the query, update or database design operation. After some consideration, we felt that it was important for the query processor to have the ability to handle all of the security constraints. Our thesis is that inferences can be most effectively handled, and thus prevented during query processing. This is because most users usually build their reservoir of knowledge from responses that they receive by querying the database. It is from this reservoir of knowledge that they infer unauthorized information. Moreover, no matter how securely the database has been designed, users could eventually violate security by inference because they are continuously updating their reservoir of knowledge as the world evolves. It is not feasible to have to redesign the database simultaneously.

The next step was to decide which of the security constraints should be handled during database updates. After some consideration, we felt that except for some types of constraints such as the release and aggregate constraints, the others could be processed during the update operation. However, techniques for handling constraints during database updates could be quite complex as the security levels of the data already in the database could be affected by the data being updated. Therefore, initially our algorithms handle only the simple and content-based constraints during database updates.

The constraints that seemed appropriate to handle during the database design operation were those that classified an attribute or collections of attributes taken together. These include the simple and association-based constraints. For example, association-based constraints classify the relationships between attributes. Such relationships are specified by the schema and therefore such constraint could be handled when the schema is specified. Since a logical constraint is a rule which specifies the implication of an attribute from a set of attributes, it can also be handled during database design.

Note that some constraints can be handled in more than one way. For example, we have the facility to handle the content-based constraints during query processing as well as during database updates. However, it may not be necessary to handle a constraint in more than one place. For example, if the content-based constraints are satisfied during the database update operation, then it may not be necessary to examine them during query processing also. Furthermore, the query operation is performed more frequently than the update operation. Therefore, it is important to minimize the operations performed by the query processor as much as possible to improve performance. However, there must be a way to handle all of the constraints during query processing. This is because, if the real-world is dynamic, then the database data may not satisfy all of the constraints that are enforced as integrity rules, or the schema may not satisfy the constraints that are processed during database design. This means that there must be a trigger which informs the query processor that the multilevel database or the schema is not consistent with the real-world; in which case the query processor can examine the additional constraints. A schematic representation of the approach to constraint generation and enforcement disclosed here is shown in FIG. 5.

2. DESIGN AND IMPLEMENTATION OF THE QUERY PROCESSOR

2.1 OVERVIEW

We first describe a security policy for handling inferences during query processing and then discuss our implementation approach.

2.1.1 SECURITY POLICY

A security policy for query processing that we propose extends the simple security property in Bell, D., and L. La Padula, July 1975, "Secure Computer Systems: Unified Exposition and Multics Interpretation," Technical Report NTIS AD-A023588, The MITRE Corporation to handle inference violations. This policy is stated below.*

Such a policy was first proposed in the LDV design [HONE87].

1. Given a security level L,E(L) is the knowledge base associated with L. That is, E(L) will consist of all responses that have been released at security level L over a certain time period and the real world information at security level L.

2. Let a user U at security level L pose a query. Then the response R to the query will be released to this user if the following condition is satisfied:

For all security levels L* where L* dominates L, if (E(L*)UR)==>X (for any X) then L* dominates Level(X). Where A==>B means B can be inferred from A using any of the inference strategies and Level(X) is the security level of X.

We assume that any response that is released into a knowledge base at level L is also released into the knowledge bases at level L*.sup..gtoreq. L. The policy states that whenever a response is released to a user at level L, it must be ensured that any user at level L*.sup..gtoreq. L cannot infer information classified at a level L+>L* from the response together with the knowledge that he has already acquired. Note that while we consider only hierarchical levels in specifying the policy, it can be extended to include non-hierarchical levels also.

2.1.2 FUNCTIONALITY OF THE QUERY PROCESSOR

The strength of the query processor depends on the type of inference strategies that is can handle. Our prototype handles a limited set of inference strategies. Nevertheless it is a useful prototype which enhances the security of existing multilevel secure relational database management systems. In this section, we discuss the techniques that we have used to implement the security policy. They are: query modification and response processing. Each technique is described below.

Query modification

Query modification technique has been used in the past to handle discretionary security and views. Stonebraker, M., and E. Wong, 1974j, "Access Control in Relational Database Management Systems by Query Modification," Proceedings ACM National Conference, New York, N.Y. This technique has been extended to include mandatory security in Dwyer, P., G. Jelatis, B. Thuraisingham, Juen 1987, "Multilevel Security in Database Management Systems," Computers and Security, Volume 6, No. 3, pp. 252-260. In our design of the query processor, this technique is used by the inference engine to modify the query depending on the security constraints, the previous responses released, and real world information. When the modified query is posed, the response generated will not violate security.

Consider the architecture for query processing illustrated in FIG. 1. The inference engine has access to the knowledge base which includes security constraints, previously released responses, and real world information. Conceptually one can think of the database to be part of the knowledge base. We illustrate the query modification technique with examples. The actual implementation of this technique could adapt any of the proposals given in Gallaire, H., and J. Minker, 1978, Logic and Databases, Plenum Press for deductive query processing. Our implementation is described in section 2.2.

Consider a database which consists of relations SHIPS and ASSIGNMENT where the attributes of SHIPS are S#,SNAME,CAPTAIN and A# with S# as the key; and the attributes of ASSIGNMENT are A#, MISSION and DESTINATION with A# as the key. Let the knowledge base consist of the following rules:

1. SHIPS(X,Y,Z,D) and Z=Smith.fwdarw.Level(Y,Secret)

2. SHIPS(X,Y,Z,A) and A=10.fwdarw.Level(Y,Top Secret)

3. SHIPS(X,Y,Z,A).fwdarw.Level((Y,Z),Secret)

4. SHIPS(X,Y,Z,A) and Release(Z,Unclassified).fwdarw.Level(Y,Secret)

5. SHIPS(X,Y,Z,A) and Release(Y,Unclassified).fwdarw.Level(Z,Secret)

6. NOT(Level(X,Secret) or Level(X,Top Secret)).fwdarw.Level(X,Unclassified)

The first rule is a content-based constraint which classifies a ship name whose captain is Smith at the Secret level. Similarly, the second rule is also a content-based constraint which classifies a ship name whose assignment number is 10 at the Top Secret level. The third rule is an association-based constraint which classifies ship names and captains taken together at the Secret level. The fourth and fifth rules are additional restrictions that are enforced as a result of the context-based constraint specified in rule 3. The sixth rules states that the default classification level of a data item is Unclassified.

Suppose an Unclassified user requests the ship names in SHIPS.

This query is represented as follows:

SHIPS(X,Y,Z,A)

Since a ship name is classified at the Secret level if either the captain is "Smith" or the captain name is already released at the Unclassified level, and it is classified at the TopSecret level if the assignment is "10" , assuming that the captain names are not yet released to an Unclassified user, the query is modified to the following:

SHIPS(X,Y,Z,D) and Z.noteq.Smith and A.noteq.10.

Note that since query modification is preformed in real-time, it will have some impact on the performance of the query processing algorithm. However, several techniques for semantic query optimization have been proposed recently for intelligent query processing in a non-secure environment (see, for example, Minker, J., "foundations of Deductive Database," Morgan Kaufman, 1988). These techniques could be adapted for query processing in a multilevel environment in order to improve the performance.

Response Processing

For many applications, in addition to query modification, some further processing of the response such as response sanitization may need to be performed. We will illustrate this point with examples.

EXAMPLE

Consider the following release constraints discussed earlier. That is,

(i) all ship names whose corresponding captain names are already released to Unclassified users are Secret, and

(ii) all captain names whose corresponding ship names are already released to Unclassified users are Secret.

Suppose an Unclassified user requests the ship names first. Depending on the other constraints imposed, let us assume that only certain names are released to the user. Then the ship names released have to be recorded into the knowledge base. Later, suppose an Unclassified user (does not necessarily have to be the same one) asks for captain names. The captain name values (some or all) are then assembled in the response. Before the response is released, the ship names that are already released to the Unclassified user need to be examined. Then the captain name value which corresponds to a ship name value that is already released is suppressed from the response. Note that there has to be a way of correlating the ship names with the captains. This means the primary key values (which is the S#) should also be retrieved with the captain names as well as be stored with the ship names in the release database.

EXAMPLE

Consider the following aggregate constraint

Suppose an Unclassified user requests the tuples in SHIPS. The response is assembled and then examined to see if it has more than 10 tuples. If so, it is suppressed.

There are some problems associated with maintaining the release information. As more and more relevant release information gets inserted, the knowledge base could grow at a rapid rate. Therefore efficient techniques for processing the knowledge base need to be developed. This would also have an impact on the performance of the query processing algorithms. Therefore, one solution would be to include only certain crucial release information in the knowledge base. The rest of the information can be stored with the audit data which can then be used by the SSO for analysis.

2.2. DESIGN AND IMPLEMENTATION

In section 2.2.1, we describe the various architectures that we considered for the implementation and the selected architecture. In section 2.2.2, we describe the representation of the constraints. In section 2.2.3, we describe the modules of the query processor. In section 2.2.4, we discuss some other issues concerning our prototype.

2.2.1 ARCHITECTURE COMPARISON

Alternate Architectures

We examined three different architectures for the implementation. A description of each architecture is given below.

(i) In the first architecture, the database as well as the knowledge base is considered to be a set of Prolog clauses. Query processing would then amount to thereon proving. Many expert system have been developed using Prolog (see, for example, Merritt, D., 1989, Building Expert Systems in Prolog, Springer Verlag, New York). These systems take advantage of the backward chaining mechanisms provided by Prolog. In addition, several other reasoning mechanisms have also been implemented using Prolog. Implementing the query processor in Prolog. would produce a fairly powerful system.*

the implementations described in [ROWE89] use such an architecture.

(ii) The second alternative is to augment a relational database management system with a theorem prover implemented in Prolog. The advantages of augmenting a relational database system with an inference engine are discussed in Li, D., 1984, A Prolog Database System, Research Studies Press, John Wiley and Sons. Many commercial relational systems already have a Prolog interface.

(iii) As the third alternative, we considered an architecture where a multilevel relational database system was augmented with an inference engine. Such an architecture would be useful as the multilevel relational database system would ensure the enforcement of a basic mandatory security policy. The inference engine then needs to implement only the policy extensions which are enforced in order to handle inferences.

After examining the three architectures, we decided to select the third one. This was because we are interested in handling security violations via inference for database systems which are already considered to be secure. Commercial multilevel relational systems are already available. Therefore, we feel that in order to produce a useful prototype we need to use such a system which will enforce the basic mandatory security policy.

Implementation Architecture

Once we had settled on the architecture, the next task was to select a multilevel relational database system for the implementation. After investigating the various systems that were available, we selected the Secure SQL Server Sybase Inc. "Secure SQL Server," 1989 for the following reasons:

(i) for system was already available for our use,

(ii) we had prototyping experiences with the nonsecure version of SYBASE DataServer,

(iii) the system provided the basic security features that we needed.

A detailed discussion on Secure SQL Server is given in Rougeau, P., and E. Stearns, "The Sybase Secure Database Server: A Solution to the Multilevel Secure DBMS Problem," Proceedings of the 10th National Computer Security Conference, Baltimore, Md., 1987. Note that Secure SQL Server enables the use of sixteen security levels numbered 1 through 16. The basic mandatory security policy enforced is read at or below your level and write at your level.

A high level implementation architecture is shown in FIG. 6. In this architecture, the Secure SQL Server is augmented with an Inference Engine. We have stored the knowledge in the database. This way, the knowledge in the knowledge base can also be protected by the Secure DataServer. The Inference Engine does query modification as well as response processing.

We implemented the Inference Engine in "C" because of the C programming language interface that already exists for the Secure SQL Server. In the long-term, we envisage replacing such an Inference Engine with a more powerful logic-based theorem prover.

2.2.2 REPRESENTATION OF SECURITY CONSTRAINTS

We assume that the constraints are maintained by the SSO. Constraints themselves could be classified at different levels. However they are stored at system-high. The constraint manager, which is a trusted process, will ensure that a constraint classified at level L can only be read by a user cleared at level L or higher.

The constraints are entered in a format that is a simplified version of the rules that we described in section 1. The constraints entered by the SSO are then processed by a module of the Query processor and stored in a graphical structure. We found this an efficient way to represent the constraints. We have developed algorithms to scan the graph structure in order to obtain the relevant constraints during query processing. The algorithms also perform some optimization for efficiency. The graph structure is illustrated in FIG. 7. The relations are combined to form a linked list. Each relation has sixteen pointers emanating from it; one for each security level. Associated with each level is a lined list of constraints. Each constraint has a set of attributes that it classifies, constraint specific information such as events and conditions, and a pointer to the next constraint. Our implementation allows for the specification of events and conditions which are quite complex. Each constraint that is associated with a level classifies a set of attributes at that level.*

An alternate representation of constraint is discussed in section 5.

2.2.3 MODULES OF THE QUERY PROCESSOR

An overview of the major modules is shown in FIG. 8. The query processor consists of five modules P1 through P5. Each module is implemented as an Ultrix process.* The processes communicate with each other via the socket mechanism. A brief overview of the functions of each module is given below. We also identify the trust that must be placed on each process.

although operating system used in the implementation is not secure, our design assumes a the use of a multilevel secure operating system.

Process P1: The User Interface Manager

This process asks for password and security level from the user. Since we assume that the operating system is secure, we rely on the identification and authentication mechanism provided by the operating system. Due to this feature, P1 need not be a trusted process. It operates at the user's level. P1 accepts a query from the user and performs syntax check. It then sends the query to process P2 and returns the response received from P2 to the user. It then waits in idle state for a request from the user.

Process P2: The Central Inference Controller

This process first sets up communication with P1. It then waits in idle state for requests from P1. When a request arrives from P1, it logs into the database server at the user's level. It then requests process P3 (via socket) to return applicable constraints. The query is then modified based on the constraints (if any). The modified query is then sent to the MLS/DBMS. The response is then sent to process P4 for further processing. When P4 returns the sanitized response, a request is sent to process P5 to update the release database and the response is given to P1. P2 then returns to idle state. If constraints classified at a higher level are not processed by P3 or if the response from the MLS/DBMS is first given to P4 and P5 for sanitization and release database update, then P2 need not be a trusted processes. However, in our implementation, since P2 could have access to higher level information it must be trusted.

Process P3: The Constraint Gatherer

This process first sets up socket for communication with P2 and then logs into the database server at system-high. This is because P3 examines not only the security constraints classified at or below the user's level, but also higher level constraints. These higher level constraints are examined to ensure that by releasing a response at level L, it is not possible for users cleared at a higher level to infer information to which they are not authorized. P3 builds and maintains the constraint table whenever the constraints are updated. It waits in idle state for requests from P2. When a request arrives, it builds a list of applicable constraints and sends the constraint structure to P2 and then returns to idle state. Since P3 maintains the security constraints it is a trusted process.

Process P4: The Sanitizer

This process sets up socket for communication with P2 and logs into the database server at system high. It waits in idle state for a request to arrive from P2. When a request arrives, which consist of the response and the applicable release constraints, it sanitizes the response based on the information that has previously been released. It reads the release database maintained at various levels in order to carry out the sanitization process. It then returns the sanitized response to P2 and returns to idle state. Since response sanitization is a security critical function, P4 must be trusted.

Process P5: The Release Database Updater

This process sets up communication with P2. It waits in idle state for requests from P2. When a request arrives, it logs into the database server at all levels from system-high to the user's level and updates the release database at each level depending on the release constraints for that level. Note that this is necessary only if higher level constraints are examined by P3. If not, P5 can log into the database server only at the user's level. After each update to the release database, it logs out of the database server at each level. It returns a status message to P2 upon completion and returns to idle state.

2.2.5 GENERAL DISCUSSION

Over 8500 lines of C code have been implemented in the development of this prototype. We first developed the infrastructure of the query processor program. This involved the creation of the five processes and establishing the necessary communications between them. Some of these processes also had to log into Secure SQL Server at the appropriate security levels. The program was set up in such a way as to leave hooks for the easy addition of more features. Since this project is a preliminary prototype of a system which could conceivably be extended in the future, we have tried to continue this approach of flexibility and modularity to make further expansion of the program easier.

It appears that there is a noticeable performance degradation when individual release constraints are handled. Large amounts of data need to be recorded. There are possibilities for optimization and this will be part of our future work. From the experiments that we have carried out so far, the performance impact of handling all of the other constraints is marginal. That is, there is hardly any visible difference between the execution times of the query processing strategy with or without the query processor.

It should be noted that in our implementation we have assumed that the process P3 examines constraints not only classified at or below the user's level, but also the higher level constraints. That is, the higher level constraints have an impact on the query modification. From the responses received a user may be able to infer the constraints at the higher level. If on the other hand the higher level constraints are not processed by P3, the response may contain sensitive information. One way to overcome this problem is to analyze the constraints before they are enforced so that it is not possible for higher level constraints to have an impact on lower level query processing. More research needs to be done on constraint analysis.

2.3 TEST SCENARIOS

In this section we illustrate the processing of the query processor with some examples.

Let the database consist of two relations SHIPS and GROUPS. The attributes of SHIPS are Number, Name, Class, Date, and Assignment. Its primary key is Number. The attributes of GROUPS are Number, Location, Mission, and Siop. Its primary key is Number. We assume that SHIPS.Assignment and GROUPS.Number take values from the same domain. Also, SHIPS.Assignment is a foreign key. The database is populated as shown below. To simplify the discussion we assume that both SHIPS and GROUPS are assigned level 1. Furthermore, all of the tuples are also stored at level 1. Note that the usual DOD classification levels do not exist as such in the secure DBMS that we have used. We assume that the number I denotes the Unclassified level, the number 10 denoted the Secret level, and the number 16 (which is system-high) denoted the TopSecret level, and 10=secret, 16=top secret, i.e. system high. The user is assumed to be logged in at level 1. The table #filter temp 1 is a temporary work table used to store the result.

    __________________________________________________________________________
    Relation SHIPS
    Number
          Name       Class      Date
                                    Assignment
    __________________________________________________________________________
    CVN 68
          Nimitz     Nimitz     May 75
                                    003
    CV 67 John F Kennedy
                     John F Kennedy
                                Sep 68
                                    001
    BB 61 Iowa       Iowa       Feb 43
                                    003
    CG 47 Ticonderoga
                     Ticonderoga
                                Jan 83
                                    005
    DD 963
          Spruance   Spruance   Sep 75
                                    006
    AGF 3 La Salle   Converted Raleigh
                                Feb 64
                                    003
    WHEC 715
          Hamilton   Hamilton   Feb 67
                                    003
    FFG 7 Oliver Hazard Perry
                     Oliver Hazard Perry
                                Dec 77
                                    001
    FF1052
          Knox       Knox       Apr 69
                                    001
    LSD 36
          Anchorage  Anchorage  Mar 69
                                    009
    LHA 1 Tarawa     Tarawa     May 76
                                    003
    MCM 1 Avenger    Avenger    Sep 87
                                    003
    AOR 1 Whichita   Whichita   Jun 69
                                    003
    AFS 1 Mars       Mars       Dec 63
                                    001
    AE 21 Suribachi  Suribachi  Nov 56
                                    009
    AE 23 Nitro      Nitro      May 59
                                    005
    AO 177
          New Cimarron
                     New Cimarron
                                Jan 81
                                    001
    SSN 706
          Albuquerque
                     Los Angeles
                                May 83
                                    006
    CVN 65
          Enterprise Enterprise Nov 61
                                    009
    MSO 427
          Constant   Aggressive Sep 54
                                    001
    __________________________________________________________________________
    Relation Groups
    Number Location   Mission     Siop
    __________________________________________________________________________
    001    North Atlantic
                      naval exercises
                                  001
    002    South Atlantic
                      falklands patrol
                                  002
    003    Mediterranean
                      iraq crisis 006
    004    Philippines
                      stabilize government
                                  005
    005    Persian Gulf
                      iraq crisis 004
    006    Indian Ocean
                      naval exercises
                                  004
    007    North Sea  soviet reconnaissance
                                  003
    008    North Atlantic
                      oceanographic research
                                  003
    009    North Pacific
                      oceanographic research
                                  001
    __________________________________________________________________________
    TEST SCENARIO 1: No Constraints
    Constraints active: NONE
    Original query: select * from Ships
    User's level: 1
    Final modified query: Same as the original query (that is, query is not
    modified)
    select ships.number, ships.name, ships.class, ships.data,
    ships.assignment
    into #filter.sub.-- temp1 from ships
    Note that the asterisk is a wildcard indicator which means the query is
    for
    all attributes (fields) in a record. When the Inference Engine sees this
    character it replaces it with all the field names in any tables specified
    in the
    from clause.
    Result: All of the tuples in SHIPS
    TEST SCENARIO 2: Content constraints
    Constraints active:
    ships.class = `Belknap` .fwdarw. Level(ships.class) = 16;
    ships.class = Ticonderoga` .fwdarw. Level(ships.class) = 16;
    ships.class = `Leahy` .fwdarw. Level(ships.class) = 16;
    ships.class = `Charles F Adams` .fwdarw. Level(ships.class) = 16;
    ships.class = `Ohio` .fwdarw.  Level(ships.class) = 16;
    ships.class = `Spruance` .fwdarw. Level(ships.class) = 16;
    ships.class = `Iowa` .fwdarw. Level(ships.class) = 16;
    ships.class = `Aggressive` .fwdarw. Level(ships.class) = 16;
    ships.class = `Mars` .fwdarw. Level(ships.class) = 16;
    ships.class = `Nimitz` .fwdarw. Level(ships.class) = 16;
    ships.class = `Los Angeles` .fwdarw. Level(ships.class) = 16;
    ships.class = `John F Kennedy` .fwdarw. Level(ships.class) = 16;
    ships.class = `Enterprise` .fwdarw. Level(ships.class) = 16;
    ships.class = `Anchorage` .fwdarw. Level(ships.class) = 16;
    Original query: select * from ships
    User's level: 1
    Final modified query:
    select ships.number, ships.name, ships.class, ships.date,
    ships.assignment
    into #filter temp1 from ships where
    (not (ships.class = `Belknap`)) and
    (not (ships.class = Ticonderoga`)) and
    (not (ships.class = `Leahy`)) and
    (not (ships.class = `Charles F Adams`)) and
    (not (ships.class = `Ohio`)) and
    (not (ships.class = `Spruance`)) and
    (not (ships.class = `Iowa`)) and
    (not (ships.class = `Aggressive`)) and
    (not (ships.class = `Mars`)) and
    (not (ships.class = `Nimitz`)) and
    (not (ships.class = `Los Angeles`)) and
    (not (ships.class = `John F Kennedy`)) and
    (not (ships.class = `Enterprise`)) and
    (not (ships.class = `Anchorage`))
    Result:
    Number
          Name       Class      Date
                                    Assignment
    __________________________________________________________________________
    AGF 3 La Salle   Converted Raleigh
                                Feb 64
                                    003
    WHEC 715
          Hamilton   Hamilton   Feb 67
                                    003
    FFG 7 Oliver Hazard Perry
                     Oliver Hazard Perry
                                Dec 77
                                    001
    FF1052
          Knox       Knox       Apr 69
                                    001
    LHA 1 Tarawa     Tarawa     May 76
                                    003
    MCM 1 Avenger    Avenger    Sep 87
                                    003
    AOR 1 Whichita   Whichita   Jun 69
                                    003
    AE 21 Suribachi  Suribachi  Nov 56
                                    010
    AE 23 Nitro      Nitro      May 59
                                    005
    AO 177
          New Cimarron
                     New Cimarron
                                Jan 81
                                    001
    __________________________________________________________________________
    TEST SCENARIO 3: Logical Constraints
    Constraints active:
    Logical(groups.location .fwdarw. groups.mission);
    Level(groups.mission) = 16
    Original query: select ships.name, groups.location, groups.siop from
    ships,
    groups where ships.assignment = groups.number
    Final modified query:
    select ships.name, groups.siop into #filter.sub.-- temp1 from ships,
    groups where
    ships.assignment = groups.number
    Results:
    Name       Siop
    __________________________________________________________________________
    Nimitz     006
    John F Kennedy
               001
    Iowa       006
    Ticonderoga
               004
    Spruance   004
    La Salle   006
    Hamilton   006
    Oliver Hazard Perry
               001
    Knox       001
    Anchorage  001
    Tarawa     006
    Avenger    006
    Whichita   006
    Mars       001
    Suribachi  001
    Nitro      004
    New Cimarron
               001
    Albuquerque
               004
    Enterprise 001
    Constant   001
    __________________________________________________________________________
    TEST SCENARIO 4: Association Constraint (or Together Constraint)
    constraints active:
    Level(Together(groups.mission, groups.location)) = 10
    Original query: select * from groups
    User's level: 1
    Final modified query:
    select groups.number, groups.location, groups.siop into #filter.sub.--
    temp1 from
    groups
    Results:
    Number      Location
                        Siop
    __________________________________________________________________________
    001         North Atlantic
                        001
    002         South Atlantic
                        002
    003         Mediterranean
                        006
    004         Philippines
                        005
    005         Persian Gulf
                        004
    006         Indian Ocean
                        004
    007         North Sea
                        003



    008         North Atlantic
                        003
    009         North Pacific
                        001
    __________________________________________________________________________
    TEST SCENARIO 5: Content and Logical Constraints
    Constraints Active:
    Logical(Groups.Mission .fwdarw. Groups.Location)
    Groups.Location = Persia Gulf .fwdarw. Level(Groups.Location) = 16
    Original query: select * groups
    Final modified query:
    Select groups.number, groups.location, groups.mission, groups.siop into
    #filter.sub.-- temp1 from groups where (not(groups.location = `Persian
    Gulf`))
    Number Location   Mission     Siop
    __________________________________________________________________________
    001    North Atlantic
                      naval exercises
                                  001
    002    South Atlantic
                      falklands patrol
                                  002
    003    Mediterranean
                      iraq crisis 006
    004    Philippines
                      stabilize government
                                  005
    006    Indian Ocean
                      naval exercises
                                  004
    007    North Sea  soviet reconnaissance
                                  003
    008    North Atlantic
                      oceanographic research
                                  003
    009    North Pacific
                      oceanographic research
                                  001
    __________________________________________________________________________
    TEST SCENARIO 6: Release Constraint
    Constraints active: Release(ships.assignment:1) .fwdarw. Level(ships.name)
     = 10
    (i.e. if ships.assignment is released at level 1, then ships.name is
    classified
    at level 10)
    Original query: select * from ships
    User's level: 1
    Results released previously were cleared before executing this query.
    Release constraint triggered by the release of:
    ships.assignment at level 1, ships.name can't appear in query.
    Final modified query:
    select ships.number, ships.class, ships.date, ships.assignment into
    #filter.sub.-- temp1 from ships
    Result:
    Number   Class         Date
                               Assignment
    __________________________________________________________________________
    CVN 68   Nimitz        May 75
                               003
    CV 67    John F Kennedy
                           Sep 68
                               001
    BB 61    Iowa          Feb 43
                               003
    CG 47    Ticonderoga   Jan 83
                               005
    DD 963   Spruance      Sep 75
                               006
    AGF 3    Converted Raleigh
                           Feb 64
                               003
    WHEC 715 Hamilton      Feb 67
                               003
    FFG 7    Oliver Hazard Perry
                           Dec 77
                               001
    FF1052   Knox          Apr 69
                               001
    LSD 36   Anchorage     Mar 69
                               010
    LHA 1    Tarawa        May 76
                               003
    MCM 1    Avenger       Sep 87
                               003
    AOR 1    Whichita      Jun 69
                               003
    AFS 1    Mars          Dec 63
                               001
    AE 21    Suribachi     Nov 56
                               010
    AE 23    Nitro         May 59
                               005
    AO 177   New Cimarron  Jan 81
                               001
    SSN 706  Los Angeles   May 83
                               006
    CVN 65   Enterprise    Nov 61
                               010
    MSO 427  Aggressive    Sep 54
                               001
    __________________________________________________________________________
    Release Table contents:
    Name    Level
    __________________________________________________________________________
    ships.number
            1
    ships.class
            1
    ships.date
            1
    ships.assignment
            1
    __________________________________________________________________________
    TEST SCENARIO 7: Aggregate Constraint
    Constraints active: Aggregate(10) .fwdarw. Level(ships.name) = 12;
    Original query: select * from ships
    User's level: 1
    Final query: Same as original query
    select ships.number, ships.name, ships.class, ships.date,
    ships.assignment
    into #filter.sub.-- temp1 from ships
    Result: No result returned for the query since more than 10 ship names
    would have been returned.
    TEST SCENARIO 8: Aggregate Constraint
    Constraints active: Aggregate(10) .fwdarw. Level(ships.name) = 12;
    Original query: select * from ships where number like `% CV %`
    final query as modified
    select ships.number, ships.name, ships.class, ships.date,
    ships.assignment
    into #filter.sub.-- temp1 from ships were number like `% CV %`
    Result:
    Number
          Name       Class      Date
                                    Assignment
    __________________________________________________________________________
    CVN 68
          Nimitz     Nimitz     May 75
                                    003
    CV 67 John F Kennedy
                     John F Kennedy
                                Sep 68
                                    001
    CVN 65
          Enterprise Enterprise Nov 61
                                    010
    __________________________________________________________________________

                  TABLE 1
    ______________________________________
    CONSTRAINT Table
    ______________________________________
    C.sub.-- ID
           C.sub.-- LEVEL
    RESULT.sub.-- REL.sub.-- NAME
                   CONDITION   RESULT.sub.-- LEVEL
    1  6   class = "Georgia
                       10          SHIPS
    2  6   name = "Florida"
                       11          SHIPS
    3  6   name = "Georgia"
                       12          SHIPS
    4  6   1 = 1        8          SHIPS.sub.-- CLASS
    ______________________________________

    __________________________________________________________________________
    sec.sub.-- label
                  number
                       name class
                                 date
                                     assignment
    __________________________________________________________________________
    0x060000000000000000000000
                  SSBN 28
                       Lafayette
                            Lafayette
                                 Jun 83
                                     009
    __________________________________________________________________________

    __________________________________________________________________________
    sec.sub.-- label
                  number
                        name class
                                  date
                                      assignment
    __________________________________________________________________________
    0x060000000000000000000000
                  SSBN 728
                        Lafayette
                             Lafayette
                                  Jun 83
                                      009
    __________________________________________________________________________

    __________________________________________________________________________
    sec.sub.-- label
                  number
                        name class
                                  date
                                      assignment
    __________________________________________________________________________
    0x060000000000000000000000
                  SSBN 728
                        Lafayette
                             Lafayette
                                  Jun 83
                                      009
    0x0b0000000000000000000000
                  SSBN 729
                        Florida
                             Lafayette
                                  Jun 83
                                      009
    __________________________________________________________________________

    __________________________________________________________________________
    sec.sub.-- label
                  number
                        name class
                                  date
                                      assignment
    __________________________________________________________________________
    0x060000000000000000000000
                  SSBN 728
                        Lafayette
                             Lafayette
                                  Jun 83
                                      009
    0x0b0000000000000000000000
                  SSBN 729
                        Florida
                             Lafayette
                                  Jun 83
                                      009
    0x0c0000000000000000000000
                  SSBN 730
                        Georgia
                             Ohio Jun 85
                                      006
    __________________________________________________________________________

    __________________________________________________________________________
    sec.sub.-- label
                  number
                        name class
                                  date
                                      assignment
    __________________________________________________________________________
    0x0b0000000000000000000000
                  SSBN 729
                        Florida
                             Lafayette
                                  Jun 83
                                      009
    0x0c0000000000000000000000
                  SSBN 730
                        Georgia
                             Ohio Jun 85
                                      006
    0x0b0000000000000000000000
                  SSBN 728
                        Florida
                             Lafayette
                                  Jun 83
                                      009
    __________________________________________________________________________

    __________________________________________________________________________
    sec.sub.-- label
                  number
                        name class
                                  date
                                      assignment
    __________________________________________________________________________
    0x0b0000000000000000000000
                  SSBN 729
                        Florida
                             Lafayette
                                  Jun 83
                                      009
    0x0c0000000000000000000000
                  SSBN 730
                        Georgia
                             Ohio Jun 85
                                      006
    0x0b0000000000000000000000
                  SSBN 728
                        Florida
                             Lafayette
                                  Jun 83
                                      009
    0x060000000000000000000000
                  SSBN 728
                        Lafayette
                             Lafayette
                                  Jun 83
                                      009
    __________________________________________________________________________

    ______________________________________
    sec.sub.-- label name   classification
                                       length disp
    ______________________________________
    0x0c0000000000000000000000
                     Ohio   nuclear    17
    ______________________________________
    (Attributes Continued)
                 speed    missile torpedo  gun
    ______________________________________
                 187      20      Tri I    Mk68
    ______________________________________