Many works on secure databases state the Simple-Security-Property as a postulate the necessity of which for achieving confidentiality seems to be out of question. We show that this property is not a postulate but a conclusion the validity of which relies on the assumptions made about the underlying secure environment. We then demonstrate that it contradicts the assumptions made by relational and logic-based databases. This result indicates that the semantic problems secure databases struggle with can be partially attributed to the accession of the Simple-Security-Property.
Security-level-based mandatory controls of information dissemination were originally developed for information recorded on paper (Landwehr (1981):249). Today the security model developed by Bell/La Padula (1975) is generally accepted as the standard formalisation of the mandatory security policy. Since the establishment of this model’s non-disclosure properties is attributed to a large extent to two of its properties, the Simple-Security-Property and the *-Property, these two properties are regarded as the core of Bell and La Padula’s model.
Originally, this model has been developed for operating systems. But gradually the view has consolidated that the two core properties are also indispensable prerequisites for guaranteeing non-disclosure in any kind of multilevel database systems.
The following list gives some examples of recent publications on various multilevel databases that state the Simple-Security-Property and the *-Property as postulates:
The problem with this procedure is that the Simple-Security-Property is not a postulate and neither is the *-Property. They are only applicable to multilevel environments in which specific conditions hold. Examples of such environments are, of course, the operating system model chosen by Bell and La Padula and the assumptions made by, Feiertag/Levitt/Robinson (1977). In these environments both properties are formulated as implications of the — sometimes tacit — assumptions made there. Consequently, whenever a security-level-based mandatory security policy should be enforced in a new environment, these properties cannot be assumed to be valid in this environment unless their validity has been proven there. To demonstrate the non-primitiveness of the Simple-Security-Property, we restate the original intention of mandatory controls in paper-based environments and explicitly specify the additional assumptions that justify its validity.
Ever since its introduction by Denning et al (1987) and Denning et al (1988), the SeaView secure relational data model has been constantly plagued with troubles. Proceeding by analogy with operating systems, SeaView is designed as the sum of the relational data model and the Bell/La Padula mandatory access control model. The negative semantic consequences of this simple syntactical step are most often attributed to polyinstantiation, a phenomenon already observed by Denning et al (1988).
We show in this work that the accession of the Simple-Security-Property to the relational data model as a postulate is the reason for a part of the problems of the multilevel relational data model. The change in the conditions which occurs during a move from a multilevel operating system to a multilevel relational database leads to an environment in which the Simple-Security-Property can no longer be derived as a consequence of the underlying assumptions. More precisely, we show the following.
Lastly, in logic-based databases we propose to replace the Simple-Security-Property with a distortion-log that records the difference between the database’s intended model and the model at a security level.
Of the two properties, the necessity or usefulness of the *-Property has sometimes been questioned. In operating systems, it is motivated by the operational distinction between a user, who is a person, and a process, which runs on a user’s behalf. While a user who is granted the right to read some data is trusted not to pass it on to users who lack this right, a process cannot be trusted to behave in the same way. This makes, eg, discretionary access control models inherently prone to Trojan Horse attacks. A user can never be sure that one of his processes will abuse the ownership right to his objects. An often heard critique of the *-Property (Cf eg Bonyun (1980) or Landwehr (1981)) is its over-restrictiveness.
Although we believe that in logic-based databases a declarative definition-approach to the semantics of confidentiality provides a more appropriate characterisation of information-flows, such a definition still can be said to subsume the operational intention of the *-Property. In other words, even though the *-Property is no longer needed here, its inclusion does not contradict any other requirements.
We would also like to mention two attempts to define non-multilevel secure databases from a logical perspective.
One of the first formal studies on confidentiality is Sicherman/de Jonge/van de Riet (1983). The authors consider the problem of confidentiality in a database, which acts like a question-answering system. The database is a collection of closed first-order formulae and its semantics is given by an extension to a maximally consistent set of formulae. The unit of protection is a formula and confidentiality is defined as non-derivability, ie, if a formula A should be kept to be secret from a user, then he should be able to derive at most A .OR. B, with some formula B, but not A itself. The interface of the database can answer a user-question with ‘Yes’, ‘No’ or ‘I know the correct answer, but I will not tell it’. The decision on the answer is made by a censor who takes the user-knowledge and the dialogue up to now into account. The censor, who never lies, gives the third answer if he arrives at the conclusion that the user will be able to deduct a secret with the help of a yes/no-answer. The authors demonstrate that this can still be of little avail since the user can make use of the censor’s reasoning in his own one. One can moreover object that allowing the user to acquire knowledge of a secret up to a two-facts-disjunction is a quite weak form of secrecy. From our viewpoint, however, the main drawback of this interesting approach is that it prohibits updates of the database. In conclusion, the addition of a third answer is more difficult to handle than yes/no-answers. At the same time, the new attack-methods are hard to analyse in standard logic. Thus it seems that the benefits of an additional degree of freedom, viz a third answer, cannot compare with the increase of complexity in handling it.
In a database that is seen as a set of closed formulae with pure first-order logic semantics, Bonatti/Kraus/Subrahmanian (1992) define the confidentiality of a formula as non-derivability. The problem is that they do not make the closed world assumption — or any variant of it —, which, however, is made by most of the security-relevant applications, and they do not deal with integrity constraints nor with dynamic semantics.
The next section defines the basic notions of mandatory security and databases. Section three demonstrates the non-primitiveness of the Simple-Security-Property. It formalises the assumptions intended by a security-level-based mandatory security policy and shows that the Simple-Security-Property can be derived from them. Section four demonstrates its non-applicability to relational databases. It also formalises the assumptions intended by a security-level-based mandatory security policy and shows that as soon as there are integrity constraints the validity of the Simple-Security-Property implies a violation of the security policy. Section 5 interprets a security-level-based mandatory security policy in a logic-based relational database and shows that in this environment the Simple-Security-Property does not make sense. We propose to replace it with the distortion-log, a partition of the set of facts which adequately characterises the relationship between the database’s intended model and any other model. Lastly, the conclusion summarises the main results of this work and presents a brief outlook.
This section introduces the basic notions needed in this work. Section 2.1 defines some set properties. Section 2.2 states the primitive intention of a security-level-based mandatory security policy and examines its implications in the original paper-based environment. Section 2.3 briefly defines relational databases in the traditional algebraic manner. Lastly, section 2.4 presents a logic-based view on relational databases.
Let I and M be sets. P(M) denotes the set of all subsets of M and |M| the number of its elements. Let N be an element of P(M) and f a mapping from I to M such that f(I) = N, then I is an index on N and N is an indexed set. A subset B of P(M) is a base of the sequence O1, O2,... if for all i Oi is an element of B. A base B is free if it comprises all finite subsets of M. I is a name space for a sequence O1, O2,... if I is an index on all i Oi. I is a universal name space if it is infinite. An alphabet A is a finite set of symbols. A* denotes the set of all strings over A.
We represent an instance of a security-level-based mandatory security policy as the tuple
MSP = (S, O, SL, F)such that: S is a set of subjects, the active units, O is a set of objects, the protection units, SL is a set of security levels on which a partial order ‘.le.’ is defined, and F is a labelling-function that assigns a security level to each subject and object. The security level of a subject s, the value F(s), is denoted as the subject’s degree of trustworthiness and the security level of an object o, the value F(o), as the object’s degree of confidentiality.
In a paper-based environment, the set of subjects is a group of individuals. An object is a named document. A security level (l, C) of SL is composed of a sensitivity level l and a set of some compartments C such that l is an element of a totally ordered set and C is a subset of a set of compartments. Then
(l1, C1) .le. (l2, C2) iff l1 .le. l2 and C1 is a subset of C2defines a partial order on SL. The labelling-function imposes a common partial order on the subjects and objects and makes them comparable within this structure.
On the basis of this structure the following mandatory regulation is defined:
The dissemination of information of a particular security level (including sensitivity level and any compartments or caveats) to individuals lacking the appropriate clearances for that level is prohibited by law. (Landwehr (1981):249)This statement unmistakably expresses that the basic and primitive intention of a mandatory security policy is the determination of confidentiality demands — and not that of access restrictions. We therefore claim that the only and primitive relationship defined by a mandatory security policy is the following one.
Primitive mandatory requirement: Let o be an object and s a subject. Then o should be kept secret from s, denoted as o is an element of the set secret(s), if F(o) .le. F(s) does not hold.
It immediately implies the following proposition, which expresses a basic secrecy property of MSP.
Lemma 1 Let s1 and s2 be subjects such that F(s2) .le. F(s1). Then secret(s1) is a subset of secret(s2).
Therefore the central question we must ask in the first place is:
What is the intended meaning of the demand ‘o should be kept secret from s’ in a given environment?In a paper-based environment, this question requires us to answer the following two questions. Firstly, when is information about a document disseminated to an individual and, secondly, the dissemination of which kind of information is prohibited? Lastly, we must examine if and how the particular prohibitions can be enforced.
Documents are stored in a safe place and accessed by their names. An individual gains complete information of a document when it is handed out to him and he can read it. If he lacks the appropriate clearance for the document, then, obviously, access for reading it must be prohibited. If he possesses a sufficient clearance, then we also do not need to worry if he modifies this or other documents since ‘When a document is not in a safe, it is in the custody of some individual trusted not to distribute it improperly’ (Landwehr 1981:250). For the same reason we also do not need to worry if he destroys the document. And since the destruction of a document is independent of any other documents — irrespective of their accessibility — this action does not disseminate any information about other documents.
When an individual creates a document, he must give a name to it. If a document with this name does not already exist, then the creation is independent of any other documents and does not disseminate any information about them. To keep the names of the documents unique, an individual must be prevented from assigning a name to a newly created document which equals that of an existing one. The rejection of a naming attempt informs the individual of the existence of a document with the same name. If he can access the existing document for reading, then this access subsumes the information that is disseminated to him through the rejection. Otherwise, the rejection informs him of the existence of a document the contents of which should be kept secret from him. We cannot recognise whether the intended prohibition of the above-cited mandatory regulation extends also to this kind of information. There is nothing to do if it does not. However, if it does, then a naming strategy that avoids naming conflicts must be chosen. When an individual is admitted to the set of subjects, is he allowed to gain information on the existence of security levels incomparable with his clearance? An answer in the positive implies that the dissemination of information on the possible existence of secret documents is not precluded by the mandatory regulation. Although not explicitly stated, the way of introducing the level-based mandatory security policy suggests that an answer in the negative is not intended.
Lastly, there is the tacit assumption that there are no other ways of disseminating information on a document to an individual.
Let R be a name, A = {A1, ..., Ak} a set of names and D1, ..., Dk sets. Then R(A1:D1, ..., Ak:Dk) is a relation scheme. R is the relation name, A1, ..., Ak the attribute names of R, D1, ..., Dk the domains of A1, ..., Ak and D, the cartesian product of D1, ..., Dk, the domain of R. A finite subset r of D is a relation (instance) over R and an element t = (c1, ..., ck) of r is a tuple of r. Let X be a subset of A then t[X] is the projection of t on the attributef of X, and r[X] = {t[X] | t is an element of r}.
Let X and Y be two subsets of A. Then X and Y form a functional dependency if for any r and any two tuples t1 and t2 of r t1[X] = t2[X] implies t1[Y] = t2[Y]. Let R1 and R2 be relation schemes with the attributes A1 and A2, and X1 a subset of A1 and X2 a subset of A2 such that |X1| = |X2|. Then X1 and X2 form an inclusion dependency if for any relations r1 and r2 over R1 and R2 r1[X1] is a subset of r2[X2].
Let RS = {R1, ..., Rn} be a set of relation schemes, D a set of functional and inclusion dependencies (This choice comprises primary-key-constraints and foreign-key-constraints, which are often regarded as an integral part of the definition of relational databases — and which are only slightly less often also regarded as the only kind of integrity constraints. From our viewpoint, this choice is sufficient for the purpose of this section; otherwise it is arbitrary since it does not include many other important classes of constraints, eg, capacity-constraints.) defined over the elements of RS and RI = {r1, ..., rn} a set of relations over RS that satisfy the dependencies of D. Then DB = (RS, D, RI) is a relational database with set-based semantics. RS is the database scheme, D is the set of integrity constraints, RI is a valid present state and the intended semantics of RI is defined by the extension of RI’s elements.
Let FS be an infinite and countable set of function symbols, PS a finite set of predicate symbols and r a function from the union of FS and PS to the set of non-hegative integers that assigns a rank to each symbol. Then B = (FS, PS) is a (database) signature or a syntactical basis if r(FS) = 0, ie, if FS comprises only constant symbols. Let VA be an infinite and countable set of variables. If t is an element of FS or VA, then t is a term (over B), and TE is the set of all terms. A term t is ground, if t is an element of FS, and TEG is the set of all ground terms. a = p(t1, ..., tn) is an atomic formula (over B), if p is a predicate symbol of PS, r(p) = n and all ti are terms of TE; AF is the set of all atomic formulae. a is ground or a fact, if all ti are ground, and AFG is the set of all ground facts. The set of formulae or the language (over B), FO, is the smallest set such that:
Let D be a non-empty set and o a function on B such that there is a mapping o(FS) from FS to D, and for each predicate symbol p of PS such that r(p) = k there is a mapping o(p) from Dk to {True, False}. Then I = (D, o) is an interpretation for B. I is a Herbrand interpretation if D = TEG and o(FS) = id. We consider only Herbrand interpretations. The truth value of a closed formula depends only on an interpretation. We therefore regard I as a mapping from L to {True, False} and denote an element's w of L truth value with respect to I as I(w). Let X be a subset of L, then I is a model of X, denoted as I is an element of Mod(X), if I(w) = True for all elements w of X. Let Y be a subset of L. Y is a logical consequence of X, if Mod(X) is a subset of Mod(Y).
Let X be a finite set of facts, def(p, X) the definition of a predicate symbol p of PS in X, comp(p, X) the completion of p with respect to X and comp(X) the completion of X (over B).
Let B be a signature, C a finite set of closed formulae and I a finite set of facts such that C is a logical consequence of comp(I), then DB = (B, C, I) is a logic-based relational database with completion semantics. B defines the database language, C is the set of integrity constraints, I is a valid present state and the intended semantics of I is defined by the (unique) Herbrand model M of comp(I).
To demonstrate the non-primitiveness of the Simple-Security-Property, we formalise the assumptions of section 2.2 and show that the Simple-Security-Property can be derived from them.
Let MSP = (S, O, SL, F) be an instance of a security-level-based mandatory security policy, which expresses the primitive mandatory requirement.
(A1) Access to objects by their name assumes that there is an alphabet A and a function f from A* to the set of all possible objects O, and A* is an index for O. We call A* the name-space for O. f(v) is the object the name of which is v; to indicate this in an intuitive manner we set (v, f(v)) = ov.
(A2) O is a finite set, ie, there is a finite subset N of A* such that O = {ov | v is an element of N}. N comprises the names of actually existing objects.
Note that the only way to refer to an object is through the index-function by its name. Therefore it is possible to define secret(s) as a subset of N. However, confidentiality demands are intuitively applicable only to objects themselves and so are the other operations to be considered subsequently. We therefore assume that secret(s) is a set of named objects. Let us denote the fact that the subject s is granted permission to read ov as ov is element of read(s). Since an object can only be declared secret or read if it exists, we have the following assumption.
(A3) For a subject s of S secret(s) and read(s) are subsets of O.
According to the intended meaning of secret(s) and read(s), the confidentiality of an object and the read-access to it are irreconcilable properties.
(A4) The primitive mandatory requirement is violated if there is a subject s such that the intersetion of secret(s) and read(s) is non-empty.
The creation of a named object ov creates from O a new set of existing objects O' such that O' is the union of O and {ov}. Since the creation establishes a link between a name and an object, we can regard it as a function that manipulates the set of objects by indirectly referring to the objects’ names. There are still two ways of defining a create-operation. If the intended semantics of secret(s) does not object to informing s of an ov of O such that ov is not in read(s), then the creation can be defined as a function that replaces N with the union of N and {v} and O with the union of O and {ov} if v is not in N; and that leaves N and O unchanged otherwise. If this behaviour is considered unacceptable, then the outcome of the create-operation may only depend on the objects the acting subject is allowed to read, ie, on the contents of read(s). We state this assumption in an informal manner.
(A5) The outcome of an operation may only depend on the objects the acting subject is allowed to read, ie, on the contents of .
A common way of avoiding naming conflicts is the extension of the name-space with a component that is not under the control of the subject.
(A6) Let E be a set such that the intersection of E and A* is empty, |E| is greater or equal to |S| and there is an injective function h from S to E (We can show that these three conditions are sufficient to avoid naming condlicts if the create-function is defined as in (A7)). Let v.w denote the concatenation of v and w. Then
N = {v.e | v is in A* and e is in h(S)}is the global (extended) name-space of O. And for a subject s
Ns = {v.e | v is in A* and e = h(s)}is its local name space.
To remain consistent, we assume that N replaces A* in the assumptions (A1) and (A2).
(A7) Creation is represented as a function C such that C(s, v, o, N, f) = (N', f'), ie, given a set of objects determined by N and f, a subject’s s attempt to create a new object with the name v.h(s) and the contents o yields a new set of objects determined by N' and f'. If ov.h(s) is not an element of read(s), then the creation is accepted, ie, N' is the union of N and {v.h(s)}, f'(N) = f(N) and f'(v.h(s)) = o; otherwise the creation is rejected, ie, all components remain unchanged, N' = N and f' = f.
Note that although N is the name space for O, the name-parameter of the create-function is restricted to A*.
Given the nature of the subjects, it is an evident insight that a subject s identified in a create-operation can be assumed to know which object and name he uses. This implies that if this operation is accepted, then it does not make sense to require that the newly created object be kept secret from the creating subject. Instead of devising a formal proof, we take it that this reasoning provides the justification for the following lemma.
Lemma 2 Let C(s, v, o, N, f) = (N', f') be an accepted create-operation. Then ov.h(s) is not an element of secret(s).
An immediate consequence of this proposition and the primitive mandatory requirement is the following corollary.
Corollary 1 Let C(s, v, o, N, f) = (N', f') be an accepted create-operation. Then F(ov.h(s)) .le. F(s).
Since assumption (A7) comprises the complete definition of the create-operation, the only condition that controls its outcome is that ov.h(s) is not an element of read(s).
Lemma 3 A sequence of object-sets O1, O2,... resulting from a sequence of create-operations has a free base.
Proof [In the printed paper]
Corollary 2 Let s be a subject. A sequence of read-sets read1(s), read2(s), ... resulting from a sequence of create-operations attempted by a combination of any subjects has a free base.
Proof Follows from (A3) and Lemma 3.
The destruction of a named object from O creates a new set of existing objects O', which is the subtraction of {ov} from O.
(A8) Destruction is represented as a function D such that D(s, v, N) = N', ie, given a set of object-names N, a subject’s s attempt to destroy the object with the name v yields a new set of object-names N'. If ov is an element of read(s), then the destruction is accepted, ie, N' is the result of subtracting {v} from N; otherwise the destruction is rejected, ie, N' = N.
Note that in contrast to the creation of an object, the destruction does not take an index-function as a parameter. We can omit it since the destruction of an object does not affect its values. An accepted destruction implicitly reduces the set of objects O by the element ov and also removes the name v from all read-sets and secret-sets of which it is a member.
Lemma 4 A sequence of object-sets O1, O2,... resulting from a sequence of destroy-operations has a free base.
Proof [In the printed paper]
Corollary 3 Let s be a subject. A sequence of read-sets read1(s), read2(s), ... resulting from a sequence of destroy-operations attempted by a combination of any subjects has a free base.
Proof Follows from (A3) and Lemma 4.
Proposition 1 A sequence of object-sets O1, O2,... resulting from a sequence of create-operations and destroy-operations has a free base.
Proof Follows from Lemma 3 and Lemma 4.
(A9) The semantics of MSP are completely captured by the assumptions (A1) to (A8):
Assumptions (A1) to (A9) model the paper-based environment of section 2.2. At an abstract level they characterise a free system with universal local name-spaces.
Proposition 1 Suppose that assumptions (A1) to (A9) hold and let s be an element of S. Then read(s) is equal to the subtraction of secret(s) from O.
Proof [In the printed paper]
Since assumptions (A1) to (A9) express the intended semantics of the primitive mandatory requirement, Proposition 2 implies also that setting read(s) equal to the subtraction of secret(s) from O is congruous with the intention of this requirement.
The following corollary shows that SL induces an inclusion-relation on the sets read(s) whenever (A1) to (A9) hold.
Corollary 4 Suppose (A1) to (A9) hold. Let s1 and s2 be two subjects such that F(s2) .le. F(s1). Then read(s2) is a subset of read(s1).
Proof Follows immediately from Lemma 1 and Proposition 2.
Lemma 5 read(s) = {o | F(o) .le. F(s)}>.
Follows immediately from the primitive mandatory requirement and Proposition 2.
Lemma 5 establishes the form of the Simple-Security-Property as it is defined by Bell/La Padula (1975) and Proposition 2 establishes its validity in an environment in which assumptions (A1) to (A9) hold.
Lastly, we would like to mention that Corollary 1 and Corollary 4 imply that SL induces also an inclusion-relation on the local name-spaces of the subjects. It can be stated as follows.
Corollary 5 Suppose (A1) to (A9) hold. Then assumption (A6) can be relaxed to |SL| .le. |E| if h is a function from S to P(SL) and an accepted create-operation C(s, v, o, N, f) creates an object with a name v.e such that e is an element of h(s).
To demonstrate the non-applicability of the Simple-Security-Property to relational databases, we consider a relational database and a security-level-based mandatory security policy in which the tuples of the present state are the objects of protection. We then characterise it through assumptions analogous to those of the previous section and show that these assumptions do not allow the derivation of the Simple-Security-Property.
Let DB = (RS, D, RI) be a relational database with set-based semantics such that RS = {R1, ..., Rn} and RI = {r1, ..., rn, and let MSP = (S, O, SL, F) be an instance of a security-level-based mandatory security policy, which expresses the primitive mandatory requirement.
(A10) Objects are directly accessed and no index-function is used. The set of all possible objects O is the union of all Di, i = 1, ..., n. (As shown by Qian/Lunt (1992), this assumption subsumes also relational databases that use element-level classification.)
(A11) The set of objects O is the finite set of tuples in the present state, ie, O is the union of all ri, i = 1, ..., n. (Note that the distinction between an indexed object regarded as a named container and a tuple regarded as a piece of information is purely artificial. The obvious way of viewing a tuple as a container is to identify its primary-key attributes with the container’s name and its remaining attributes with its contents.)
(A12) For a subject s secret(s) and read(s) are subsets of O.
Note that (A12) does not allow to state confidentiality demands for presently non-existent objects, which corresponds to the inability to keep the absence of a fact secret. This is a noticeable shortcoming since the wish to do so is not unusual at all in practice. For example, a company can wish to keep secret that a certain product is not ready yet or that a certain flight does not take place.
(A13) The primitive mandatory requirement is violated if there is a subject s such that the intersection of secret(s) and read(s) is non-empty.
Corresponding to the operations of creating and destroying objects of section 3, a general transition should be modelled here with a transaction, which inserts and deletes tuples from the present state. However, to show the announced result it is sufficient to consider only deletions. We define it analogously to the destroy-operation.
(A14) Deletion is represented as a function t such that t(s, d, RI) = RI', ie, a subject’s s attempt to delete the tuples d from RI yields a new set of tuples RI' = RI \ (the intersection of d and read(s)). If RI' satisfies the dependencies of D, then the deletion is accepted and RI' becomes the new present database state; otherwise it is rejected and the state remains unchanged.
Proposition 3 A sequence of object-sets O1, O2,... resulting from a sequence of delete-operations has only a free base B if D is empty.
Proof [In the printed paper].
Corollary 6 Let s be a subject. A sequence of read-sets read1(s), read2(s), ... resulting from a sequence of delete-operations attempted by a combination of any subjects has a only free base B if D is empty
Proof Follows from (A12) and Proposition 3.
Proposition 3 states that only a degenerated database with no integrity constraints at all can have a sequence of states with a free base. Arguing by analogy to the create-operation of the previous section, we understand that if there are integrity constraints, then the primitive mandatory requirement is violated as soon as the decision of D to reject a delete-operation attempted by the subject s is based on elements of secret(s). Moreover, Corollary 6 states that since the deletion of a tuple from O implies its deletion from all read-sets, we must always be prepared to encounter the following situation — unless there are no integrity constraints. There is a subject s1 such that the accepted deletion of a tuple by a subject s2 modifies also the set read(s1) such that read(s1) has satisfied D before the deletion but no longer does so after it.
Let t(s, d, RI) = RI' be a rejected delete-operation by s. Then let reject(d, RI), a subset of RI, denote the smallest set of tuples of the present state which, if themselves deleted from it, t(s, d, RI) = RI' would be accepted. Formally, reject(d, RI) is the set of tuples such that with X = RI \ reject(d, RI) t(s, d, X) is accepted and for any subset Y of reject(d, RI) with X' = RI \ Y t(s, d, X') is still rejected. On these grounds we can say that a delete-operation is accepted if reject(d, RI) is empty.
(A15) Let t(s, d, X) be a delete-operation attempted by a subject s. The primitive mandatory requirement is violated if read(s) is not a subset of reject(d, Ok).
Lemma 6 Suppose that D contains an inclusion dependency. Then we can find a subject s, a sequence O1, O2,... and a k such that t(s, d, Ok) is rejected and read(s) is not a subset of reject(d, Ok).
Proof Simple but tedious.
The problem indicated by Lemma 6 is that a subject’s delete-operation is rejected and to him there are no visible reasons for this. An approach to solve it for a given state RI is to remove from all those tuples the deletion of which by s results in a reject-set not contained in the subject’s read-set. This idea is examined, eg, by Su/Ozsoyoglu (1987) and Su/Ozsoyoglu (1989). Whereas the possibly enormous reduction of the read-set can itself be considered regrettable yet tolerable, this method is not a solution if the subject has a need to know some of the removed tuples or when a transaction can also insert tuples. We cannot go in the opposite direction and adjust the read-set so that it comprises all tuples that a rejection may refer to — by doing so we would undoubtedly violate the primitive mandatory requirement. Various works have suggested the use of cover stories or aliases, the first of which to our knowledge is Graubart/Woodward (1982) (Graubart/Woodward (1982):35). This idea has been recently taken up by Spalka (1994), who already indicates that the use of aliases requires a modification of the Simple-Security-Property. We follow this direction and utilise aliases in a solution to the problem illustrated by Lemma 6.
Since by their very nature aliases must be non-modifiable by the subject for whom they are invented, we must first introduce a relation, delete(s), that limits a subject’s ability to delete tuples. We now proceed as follows. Given a database state RI = O1 and a subject s set delete(s) = read(s). This ensures that s is allowed to delete no fewer tuples after our manipulation than in the original state. Then compute the set reject(s, O1) as the union of reject(d, O1) over all d of P(read(s)) from which read(s) is subtracted.
Lemma 7 reject(s, O1) is empty only if any sequence of delete-operations attempted by s is either accepted or the rejection depends only on read(s).
Proof [In the printed paper].
Then find a set alias(s) such that:
Lemma 8 Suppose that reject(d, O1) is non-empty. Then alias(s) is also non-empty.
Proof Follows immediately from Lemma 7 and the definition of alias(s).
Lastly, extend the read-set with the alias-set, ie set Read(s) equal to the union of read(s) and alias(s). Note that if reject(d, O1) is empty, then alias(s) is also empty, viz, no aliases are needed for s. Well, if aliases are needed, how do we find them? This is obviously an important question, which, however, we do not answer in this work.
(A16) Let s be a subject. Then delete(s) comprises the objects s is permitted to delete and Read(s) the objects s is permitted to read.
Lemma 9 Let s be a subject. Then an attempted delete-operation by s satisfies the primitive mandatory requirement if read(s) is replaced by Read(s).
Proof Follows from the construction of alias(s).
We can now state the main result of this section.
Proposition 4 Let DB = (RS, D, RI) and suppose that (A10) to (A16) hold. If an alias-set can be found for each subject, then the primitive mandatory requirement is satisfied and the Simple-Security-Property does not hold.
Proof [In the printed paper].
We would like to mention that the following corollary holds, which we present without a proof here.
Corolarry 7 Let DB = (RS, D, RI and suppose that only (A10) to (A15) hold. Then the Simple-Security-Property is a valid assumption but the primitive mandatory requirement is violated.
In this section we present the reasons for our belief that the Simple-Security-Property has no obvious meaning at all in logic-based databases. By Corollary 4 the Simple-Security-Property implies that the partial order defined on SL induces an inclusion-relation on the subjects’ read-sets. In particular, two subjects’ read-sets form a proper inclusion as soon as their secret-sets form a proper inclusion, too. We show that in a logic-based relational database, all subjects have the same read-sets independent of the assignment or the ordering of the security levels. Thus, on the one hand, the read-sets can be said to form a trivial inclusion-relation. However, we think that such a view does not account for the Simple-Security-Property’s integral implication that
secret(s1) is a subset of secret(s2) implies that read(s2) is a subset of read(s1)We therefore claim that, because of the equality of all read-sets, the Simple-Security-Property does not make sense in logic-based databases.
Let DB = (B, C, I) be a relational database with completion-based semantics the intended model of which is the Herbrand interpretation M = (TEG, o) for B, ie o(FS) = id, and let MSP = (S, O, SL, F) be an instance of a security-level-based mandatory security policy, which expresses the primitive mandatory requirement.
(A17) Objects are directly accessed and no index-function is used. The unit of protection is a fact a of AFG (This corresponds to tuple-level labelling in the set-based view on relational databases.), ie a ground atomic formula, and the set of all possible objects is O = AFG.
(A18) The set of objects O is the infinite set of facts of the database language, ie O = O.
(A19) For a subject s the set secret(s) is a subset of O.
(A18) and (A19) imply that a confidentiality demand can be stated for any ground atomic formula independent of its present truth value in the intended database model. Informally, this allows us to express the wish to keep both the presence or the absence of a fact secret.
Lemma 10 With respect to the declaration of confidentiality demands, the expressive power of the logic-based view is greater than that of the set-based view on relational databases.
(A20) For a subject s the expression read(s) is identified with a Herbrand interpretation Ms = (TEG, os) for B.
Assumption (A20) expresses that any subject can query the database for, ie read, the truth value of any fact — the question of whether the database responds with the fact’s truth value of the intended model is partially answered by the following assumption.
(A21) The intended meaning of the primitive mandatory requirement for a fact is that
Ms(a) = .NOT. M(a)
But then, given two subjects s1 and s2 such that F(s2) .le. F(s1), what can we say about their read-expressions, ie their interpretations? Both interpret the same language. Since both positive and negative facts can be included in their secret-sets, the sets of facts to which their interpretations assign the same truth value need not form any inclusion at all, either. In respect of the Simple-Security-Property we interpret this situation as follows.
The combination of the logic-based view of relational databases with the security-level-based mandatory security policy requirements creates an environment in which the Simple-Security-Property has no obvious meaning.
On the other hand, there indeed is a relevant relationship between interpretations, which we believe can be adequately characterised by a construct we call the distortion-log. We only briefly describe it in this work, but our further investigations indicate that it can be used in place of the Simple-Security-Property.
Let M be the intended model and Ms the model of a subject s. Then the distortion-log of s with respect to M is the tuple
Ps = (As, Xs, Zs)such that:
The idea to replace the Simple-Security-Property with the distortion-log is motivated by the following proposition, which we present without a proof, and which concludes this work.
Proposition 5 Let s1 and s2 be two subjects, M1 and M2 their interpretations, and P1 and P2 their distortion-logs. Suppose that F(s2) .le. F(s1) then A2 is a subset of A1.
We have shown in section 3 that based on the partial order defined on SL, the Simple-Security-Property induces an inclusion-relation on the subjects’ read-sets. However, this property has not been stated as a postulate but derived from the specific assumptions made in this section. The result of section 4 shows that a (successful) alias-based enforcement of the primitive mandatory requirement in relational databases with set-based semantics leads to a definition of the read-sets such that SL’s partial order is unrelated to any inclusion that may possibly hold between the read-sets. That is, while we cannot be sure that the use of aliases guarantees the enforcement of the primitive mandatory requirement, we can definitely say that the accession of the Simple-Security-Property prevents its enforcement. In respect of the aim of this paper, the main result of section 5 is the motivation of the meaninglessness of the Simple-Security-Property in logic-based databases. However, this section comprises also a compressed definition of a secure logic-based database, including the definition of integrity enforcement and a formal definition of confidentiality demands. As a constructive proposal, we use the distortion-log — as a replacement of the Simple-Security-Property — to characterise the read-relationship between the database’s intended model and any other subject’s interpretation.
We are convinced that the approach presented in section 5 provides a promising new way for the understanding and the handling of confidentiality in databases which (also) have a logic-based definition.
Bell, David Elliott, and Leonard J. La Padula. (1975) Secure computer system: Unified exposition and multics interpretation. MITRE Technical Report 2997. MITRE Corp, Bedford, MA.
Bertino, Elisa, Luigi V. Mancini and Sushil Jajodia. (1995) ‘Collecting Garbage in Multilevel Secure Object Stores’. 1994 IEEE Symposium on Research in Security and Privacy. IEEE Computer Society Press. pp 106–120.
Bonatti, Piero, Sarit Kraus and V.S. Subrahmanian. (1992) ‘Declarative Foundations of Secure Deductive Databases’. Ed Joachim Biskup and Richard Hull. 4th International Conference on Database Theory – ICDT’92. LNCS, vol 646. Berlin, Heidelberg: Springer-Verlag. pp 391–406. [Also in: IEEE Transactions on Knowledge and Data Engineering 7.3 (1995):406–422.]
Bonyun, David A. (1980) ‘The Secure Relational Database Management System Kernel: Three Years After’. 1980 IEEE Symposium on Security and Privacy. IEEE Computer Society Press. pp 34–37.
Bourbaki, Nicolas. (1968) Theory of Sets. Paris: Hermann.
Cremers, Armin B., Ulrike Griefahn and Ralf Hinze. (1994) Deduktive Datenbanken. Braunschweig: Vieweg.
David, Rasikan, Sang H. Son and Ravi Mukkamala. (1995) ‘Supporting Security Requirements in Multilevel Real-Time Databases’. 1995 IEEE Symposium on Security and Privacy. IEEE Computer Society Press. pp 199–210.
Denning, Dorothy E., Teresa F. Lunt, Roger R. Schell, Mark Heckman and William R. Shockley. (1987) ‘A Multilevel Relational Data Model’. 1987 IEEE Symposium on Security and Privacy. IEEE Computer Society Press. pp 220–234.
-----, -----, -----, William R. Shockley and Mark Heckman. (1988) ‘The SeaView Security Model’. 1988 Symposium on Security and Privacy. IEEE Computer Society Press. pp 218–233.
Feiertag, R.J., K.N. Levitt and L. Robinson. (1977) ‘Proving multilevel security of a system design’. 6th ACM Symposium on Operating System Principles. ACM SIGOPS Operating System Review 11.5:57–65.
Graubart, Richard D., and John P.L. Woodward. (1982) ‘A Preliminary Naval Surveillance DBMS Security Model’. 1982 IEEE Symposium on Security and Privacy. IEEE Computer Society Press. pp 21–37.
Landwehr, Carl E. (1981) ‘Formal Models for Computer Security’. ACM Computing Surveys 13.3:247–278.
Qian, Xiaolei. (1994) ‘Inference Channel-Free Integrity Constraints in Multilevel Relational Databases’. 1994 IEEE Symposium on Research in Security and Privacy. IEEE Computer Society Press. pp 158–167.
----- and Teresa F. Lunt. (1992) ‘Tuple–level vs. element–level classification’. Ed Bhavani M. Thuraisingham and Carl E. Landwehr. Database Security VI. IFIP WG11.3 Workshop on Database Security 1993. Amsterdam: North-Holland, 1993. pp 301–315.
Sicherman, George L., Wiebren de Jonge and Reind P. van de Riet. (1983) ‘Answering Queries Without Revealing Secrets’. ACM Transactions on Database Systems 8.1:41–59.
Spalka, Adrian. (1994) ‘Formal Semantics of Confidentiality in Mutilevel Logic Databases’. 1994 ACM SIGSAC New Security Paradigms Workshop. IEEE Computer Society Press, 1994. pp 64–73.
Su, Tzong-An, and Gultekin Ozsoyoglu. (1987) ‘Data Dependencies and Inference Control in Multilevel Relational Database Systems’. 1987 IEEE Symposium on Security and Privacy. IEEE Computer Society Press. pp 202–211.
-----, -----. (1989) ‘Multivalued Dependency Inferences in Multilevel Relational Database Systems’. Ed David L. Spooner and Carl E. Landwehr. Database Security III. IFIP WG11.3 Workshop on Database Security 1989. Amsterdam: North-Holland, 1990. pp 293–300.