Dw-03270

RR243

RIA

laboria

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
B. P. 105 78150 - Le Chesnay
France
Tél.: 954 90 20

laboratoire de recherche
en informatique
et automatique

<figure><img src="image_1.png" /></figure>

PROTECTION OF INFORMATION
IN RELATIONAL
DATA BASE
MANAGEMENT SYSTEMS

François M. BANCILHON
Nicolas SPYRATOS

Rapport de Recherche N° 243

Août 1977

25p
PROTECTION OF INFORMATION IN RELATIONAL
DATA BASE MANAGEMENT SYSTEMS

François Bancilhon*, Nicolas Spyratos**

<figure><img src="image_2.png" /></figure>

Résumé :

Nous étudions ici le problème de la protection des informations dans une base de donnée relationnelle. Nous supposerons que l'on se protège d'un usager dont le seul moyen d'accès à la base est un langage de requêtes relationnel.

Le but de cet article est de formaliser la notion de protection. Nous décrivons donc d'abord un système de protection de manière informelle, puis nous présentons un modèle formel pour ce même système. Les entités à protéger sont des propositions qui ont été déclarées confidentielles. Une requête de l'usager «viole» une proposition protégée si la réponse à cette requête modifie la «connaissance» que l'usager a de cette proposition. Pour finir, nous démontrons que ce modèle est un bon outil d'analyse et d'évaluation des systèmes de protection.

Abstract :

This paper is concerned with protection of information in a data base from disclosure to properly identified users. It is assumed that the only means of access the user has is through a relational query language.

The objective of the paper is to formalize the notion of protection. This is done by first describing intuitively a protection system and then by proceeding to present a formal model for this system. The objects to be protected are propositions that have been declared confidential. A user query violates a protected proposition if the answer modifies the knowledge the user has about this pro- position. Following this approach, we propose some protection systems and we discuss their im- plications. It would seem, however, that designing a «perfect» protection system is an almost im- possible task.

<footnote>* IRIA/LABORIA.</footnote>

<footnote>** IRIA/LABORIA - Post-Doctoral Fellow of the National Research Council of Canada.</footnote>
# 1 - INTRODUCTION

The increasing amount of valuable and private information processed by computers implies a longterm need for rigorous controls.

Personal information, as defined by privacy legislation, and financial or medical records, are examples of information which must be protected during computer processing. It is hard to give a precise definition of computer security because specific security requirements depend so strongly on the larger human, social and financial systems that are served by the computer processing. In general, "security is concerned with any unauthorized or undesirable modification, disclosure or destruction of information" [Linden 76].

Security must be concerned with any path by which information could be modified, disclosed, or lost. However, some aspects of the overall security problem are clearly beyond the control of a central computer system and can be regarded as separate problems. For example, communication security, identification of users, and physical protection of the computer site are distinct problems. Also, the security of most systems can easily be broken if an operator can be bribed. This might seem to be outside the control of the hardware/software system. However, if a system is designed for security, it is reasonable to expect that the operator's command language provides a protection environment that carefully limits his privileges.

This paper focuses on the problem of protection of information from unauthorized or undesirable disclosure. This problem can be very different according to whether we protect information from a non-programmer user, from a team of expert programmers or from a group of spies using bugging devices. It can also vary widely according to whether we protect a record in a file, a file in a software system or a large complex set of integrated files. Thus, it appears that in order to define a protection problem one must answer the following questions :
(1) Against whom do we protect ?

(2) What do we protect ?

(3) How do we protect ?

(4) What does "protect" mean ?

Note that question (4) addresses the problem of defining the protection function whereas question (3) addresses the problem of realizing that same function.

This paper is not concerned with the general study of protection of information. Rather, it focuses on a specific problem, namely, that of *protecting information in a data base from disclosure to a properly identified user*. It is assumed that the only means of access to the data base by the user is a relational query language.

The objective of the paper is to formalize the notion of protection. This is done by describing first, intuitively, a protection system and the proceeding to present a formal model for this system. Using this model it is shown that even in an "ideal" environment, designing a "perfect" protection system is an almost impossible task.

## 2 - DEFINITION OF THE PROBLEM

### 2.1 - Against whom do we protect ?

The problem considered here is that of protecting information against unauthorized or undesirable disclosure. The situation we are interested in is illustrated in Figure 1. On the one hand, we have a data base (which may be hierarchical, network, relational or any other type). On the other hand, we have a user with the following characteristics

(1) The user has been properly identified, i.e., we know who the user is.
(2) The only way the user can access the data base is through a software interface, by means of a relational query language.

(3) The "knowledge" of the user consists of

(a) The data base schema (we assume here a relational schema),

(b) The answers to user's queries from the software interface,

(c) The protection mechanism,

(d) All that the user can deduct from the three preceding items of information.

By point (c) we mean that the user knows the general protection algorithm (but not necessarily the type of protected information). This will prove to be important since in some cases knowing the protection mechanism we can deduct some information from a refusal to answer. On the other hand it seems unrealistic to admit that an algorithm could be fully hidden from all users.

It is against such a user that we want to protect information from disclosure. Let us now look at the sort of information we are protecting.

## 2.2 - What do we protect ?

Generally speaking, what we protect is information that has been declared as confidential. It is the task of the software interface to protect this information from user's violations.

In most existing software systems, to specify the information to be protected one must take into account the structure of the data base. Thus, if the data base consists of a set of files the confidential information will consist of files, records in a file, or fields in a record. Similarly, in a data base with a network structure, the confidential information will consist of sets, records or items
and in a relational data base, the confidential information will consist of relations, tuples in a relation or attributes of a tuple.

One of the main contributions of the relational approach is the concept of data independence. It states that the way data is manipulated must be independent of the way it is structured and actually implemented. Another important contribution is the ability given to the user, by relation query languages, to formulate complex queries on a data base. What we propose here is to apply these two principles to the protection problem, that is, we require (i) that the protected information be specified independently of the data base structure and (ii) that the protection system must be capable of protecting complex information.

## 2.3 - How do we protect?

Now that we know what is to be protected and from whom, let us examine the means of protection that we have at our disposal. Referring back to Figure 1, we observe that the only means to control the user's "knowledge" and, therefore, to provide protection, is through the answers given by the software interface to queries.

The possible answers to a query can be :

(1) The correct answer

(2) A refusal to answer

(3) A false answer

(4) An incomplete answer

We shall restrict our study to the first two cases where the software provides the correct answer to a query or a refusal to answer.
## 2.4 - What is protection ?

As mentioned earlier, the "knowledge" of the user consists of the proper-
ties of the data base schema and the principles on which the protection mechanism
is based. The user can increase his knowledge through the answers provided by
the software interface to queries about the data base. He can also increase
his knowledge through deductive reasoning.

Generally speaking, the protection mechanism operates correctly, if all
the knowledge the user can acquire does not "violate" the protected information.
By violation we mean disclosure of this information or part thereof. As an
example consider the following confidential information

"John is 20 years old".

Moreover, suppose that, as a result of the properties of the data base schema,
the user knows that John's age lies between 1 and 100. In other words, the user
knows that chances that John's age is 20 are 1/100. On the other hand, as a result of
answers to one or more queries, the user may find out either that John's age is 20, or
-for instance- that John's age is between 15 and 25. The first case is a "complete
violation" of the protected information, as the user now knows that John's age
is 20. The second case is a "partial violation" as chances that John's age is
20 have now increased from 1/100 to 1/10.

In conclusion, the protection mechanism must decide whether to accept or
to refuse a query based on the protected information and the properties of the
data base schema.

# 3 - THE RELATIONAL MODEL

Before proceeding to the presentation of our model we shall discuss the
relational model [Codd 70, 72].
As this model has been widely discussed and studied (and in some cases implemented), we shall simply recall some notation and definitions that we shall need later.

A relation is described by a relation name r, its order n (denoted by $||r||$), and a set of n attribute names $A_1, A_2, ..., A_n$. A domain $DA_i$ is associated with each attribute $A_i$. In general, a relation description is denoted as follows :

$$r(A_1 : DA_1, A_2 : DA_2, ..., A_n : DA_n)$$

For instance, W2 (Employeur : Alphanumeric, Employee : Alphanumeric, Salary : Integer) describes a ternary relation with name W2, where the three attributes are : Employer, Employee, Salary. The associated domains are, respectively : Alphanumeric, Alphanumeric, Integer.

A value of the relation r ($A_1 : DA_1, ..., A_n : DA_n$) is a finite set of n-tuples $(x_1, x_2, ..., x_n)$, where each $x_i \in DA_i$. A value of the relation r will be denoted as $\tau(r)$. For instance,

$$\tau(W2) = \{ (Renault, Dupont, 20 000), (Renault, Maxime, 30 000), (IBM, Dupont, 25 000), (Government, Martin, 10 000) \}$$

is a value of the W2 relation.

A Data Base is described by a finite set R of relation descriptions. This set is called the relational alphabet. As an example, consider the following data base that we shall call the "Tax Data Base".
$$
R = \{ \text{ID} (\text{Name, Age, Address}), \\
\text{IRS} (\text{Name, Taxes}), \\
\text{W2} (\text{Employer, Employee, Salary}), \\
\text{TR} (\text{Name, Income}) \}
$$

There are two different notions that we must distinguish clearly : that
of a data base configuration and that of a data base schema. A configuration
C is a state of the data base at a given time. It will be denoted by (R, τ),
where R is the relational alphabet and τ associates with each relational name r
a value τ(r). The following is an example of a configuration of the tax data
base

$$
\tau(\text{ID}) = \left\{ \begin{array}{l} (\text{Dupont, 25, Paris}), \\ (\text{Maxime, 70, Lyon}), \\ (\text{Martin, 50, Paris}) \end{array} \right\}
$$

$$
\tau(\text{IRS}) = \left\{ \begin{array}{l} (\text{Dupont, 8 000}), \\ (\text{Maxime, 4 000}), \\ (\text{Martin, 0}) \end{array} \right\}
$$

$$
\tau(\text{TR}) = \left\{ \begin{array}{l} (\text{Dupont, 45 000}), \\ (\text{Maxime, 30 000}), \\ (\text{Martin, 10 000}) \end{array} \right\}
$$

$$
\tau(\text{W2}) = \left\{ \begin{array}{l} (\text{Renault, Dupont}, \ 20\ 000), \\ (\text{Renault, Maxime}, \ 30\ 000), \\ (\text{IBM, Dupont}, \ 25\ 000), \\ (\text{Government, Martin}, \ 10\ 000) \end{array} \right\}
$$

The *schema* S consists of all possible configurations that the data base
can take. It is usually described by some invariant properties that all confi-
gurations must satisfy. We shall not discuss here what these properties can be.
Functional dependencies [Codd 70] are important properties, but other integrity
constraints can also define a schema.

Another very important concept is that of a *relational algebra*. Given two
relations, we can build new relations by means of such operations as union,
intersection join, projection etc... Generalizing this process we can build new
relations starting from a given set of relations. Here again, we must be careful to
distinguish between two notions. First, given the relational alphabet R, we
can define new relation names using R.

For instance in the tax data base, we can define the relation IDC(Name, Address, Income, Taxes) by joining the relations ID, IRS and TR. What we have created, is merely a name. Now, given the values τ(ID), τ(IRS) and τ(TR) that these three relation names could take in some data base configuration we can compute the value τ(IDC) of that new name.

Thus, in the tax data base configuration the relation IDC would take the value :

$$ \tau(\text{IDC}) = \{ (\text{Dupont}, \text{Paris}, 45\,000, 8\,000), (\text{Maxime}, \text{Lyon}, 30\,000, 4\,000), (\text{Martin}, \text{Paris}, 10\,000, 0) \} $$

In [Codd 72] a relational algebra was introduced and in [Bancilhon 76] this algebra was shown to be powerful enough to define any new relations. We shall denote by R* the set of all new relation names that can be defined from R using Codd's algebra. The definition of that algebra will not be given here. The only important fact to remember is that R* includes every possible relation we could define from R.

A query on the data base is merely a relation name of R*. A query r ∈ R* is to be interpreted as : "give me the value τ(r) of the relation I have just defined".

A proposition about the data base is intuitively a statement which can be made about that data base. Depending on the actual configuration, that statement can have as a value either true or false. For instance, the statement "Dupont makes 45 000 a year" is true in the above data base configuration.
We shall define an *elementary proposition* as a couple $(\bar{x}, r)$ where $r \in R^*$ is a relation name defined on domains $(D_1, D_2, ..., D_n)$ and where $\bar{x} \in D_1 \times D_2 \times ... \times D_n$. This elementary proposition is true in a configuration $(R, \tau)$ if $\bar{x} \in \tau(r)$ and it is false otherwise.

We now define a *proposition* as a boolean expression of elementary propositions.

For instance "Dupont makes 15 000 a year and Martin's age is less than that of Maxime's" is a proposition.

We introduce the following notation : let $r$ be a question and let $a(r)$ denote the answer to this question. Then $(r, a(r))$ is a proposition. For instance, if the question is $r = \text{"Where does Dupont live ?"}$ and the answer to this question is $a(r) = \text{"Paris"}$ then $(r, a(r)) = \text{"Dupont lives in Paris"}$, is a proposition.

# 4 - THE MODEL

## 4.1 - Knowing and guessing

Generally speaking, what the user knows are properties of the data base schema. In a given configuration of the data base, the user will ask questions and, depending on the answers, the user will deduce that certain propositions are true. Thus, at a given time, the knowledge of the user consists of the knowledge $K_S$ of the properties of the schema and of a set of propositions $K = \{p_1, p_2, ..., p_n\}$ that the user knows to be true. For instance, in the tax data base one of the properties of the schema may be :

"Salaries are spread evenly from 0 to 75 000"

On the other hand, the user may have acquired -through answers to queries- the following knowledge of the tax data base configuration described earlier :
"Dupont makes more than 10 000"

"Martin paid no taxes"

We shall say then, that the knowledge of the user is the knowledge she/he has about the schema plus the knowledge she/he can acquire through queries. Hence, the following definition of user's knowledge.

**Definition 1 :**

The user's knowledge K of a given configuration at a given time is the knowledge $K_S$ that the user has about the schema plus the knowledge $K_a$ that the user can acquire through queries. That is, $K = K_S \cup K_a$.

Suppose now that the user's knowledge consists of the three propositions mentioned earlier. Based on this knowledge, and before asking the next question, the user can estimate the chances that any given proposition has to be true. Thus, the chances that the proposition

"Dupont makes more than 50 000"

is true are 50 000/(75 000-10 000) that is, 0.77. On the other hand, the chances that the proposition

"Martin makes more than 50 000"

is true are 50 000/75 000, that is, 0.66. Hence, the following definition of user's estimation.

**Definition 2 :**

The estimation made by a user with knowledge K is a function $E_K:P \to [0,1]$ from the set P of all propositions into the interval $[0, 1]$. This function associates with each proposition an (a-priori) probability of this proposition to be
true, given the knowledge K of the user. That is, $E_K(p) = \text{pr}(p|K)$.

Let us now define the probability $\text{pr}(p|K = K_S)$, that is, the probability that the proposition p is true, given that the knowledge of the user consists only of the properties of the schema. We shall assume that the schema S is defined on finite domains, that is, that the number of possible configurations in the schema S is finite. As all configurations of S are equally likely for the user, we can define:

$$ \text{pr}(p|K = K_S) = \frac{\text{Number of configurations for which p is true}}{\text{Total number of configurations of S}} $$

The assumption of finite domains was made in order to simplify matters. The general case can be treated in a similar manner (for a complete treatment see [Spyratos 77]).

As we mentioned earlier, there is no systematic way of describing schemas. Thus, there is no general formula to compute the total number of configurations in S. It is, therefore, the job of the user to estimate the probability $\text{pr}(p|K = K_S)$ for a given schema S. The example given earlier suggests one way to do this.

Suppose next that apart from the knowledge $K_S$ the user knows that a proposition $p_1$ is true. That is, suppose that $K = K_S \cup \{p_1\}$. Let us see now what the probability $\text{pr}(p|K)$ is in this case. We assume again that the schema S is defined on finite domains. We have:

$$ \text{pr}(p|K = K_S \cup \{p_1\}) = \frac{\text{Number of configurations for which p and } p_1 \text{ are true}}{\text{Total number of configurations in S where } p_1 \text{ is true}} $$

Now, think of the fact that proposition $p_1$ above is true, as knowledge acquired through a query $q_1$ to the data base. Also, think of the fact that
proposition p is true, as confidential information. Intuitively, the query $q_1$ does not violate this information if the user's estimate of the fact that p is true is the same before and after the query $q_1$. This approach is further explored later.

## 4.2 - The protected information

Let us consider the tax data base, described earlier by the relational alphabet $R = \{ID, IRS, W2, TR\}$. The following are examples of information that the data base administrator or a user entering data might want to keep confidential.

(1) "Dupont works for Renault"

(2) "Maxime's salary is 10 000"

(3) "Martin's income is three times higher than his taxes"

(4) "The name and address of people making more than 20 000 a year"

(5) "The salary and name of people making more than 8 000 and paying no taxes"

Taking a closer look at these examples we observe that (1), (2) and (3) are propositions, whereas (4) and (5) are relations from $R^*$. Propositions such as (1), (2) and (3) above are likely to be declared confidential by a user who knows that these facts are true. Therefore these propositions are to be protected in a given configuration. In a different configuration, their protection would possibly make no sense. For instance, if Maxime's salary is increased from 10 000 to 20 000 it makes no sense to protect proposition (2), in the new configuration. Relations (4) and (5) are, on the contrary, meant to be protected over the entire schema. That is, at the time the data base was created, the data base administrator decided that all values of these relations were to be protected.

Now, let $r \in R^*$ be a relation that we want to protect. Let $C$ be the actual data base configuration. In this configuration, $r$ takes a certain value $\tau(r)$, say,
$$ \tau(r) = \{\bar{x}_1, \bar{x}_2, \dots, \bar{x}_n\} $$

It should be clear that protecting r in this configuration is equivalent to
protecting the proposition

$$ p = (r, \bar{x}_1) \wedge (r, \bar{x}_2) \wedge \dots \wedge (r, \bar{x}_n) $$

For instance, in the tax data base configuration described earlier, we might want
to protect the information

p = "Martin gets 10 000 from the government and pays no taxes"

This information is to be protected only in this specific configuration. However,
we might also want to protect, the relation

"The name and address of people making more than 12 000 a year"

over the entire schema. In the particular configuration we are considering, this
relation is interpreted as follows

"Dupont lives in Paris and makes more than 12 000 and Maxime lives in Paris and makes more than 12 000"

Of course, this same relation may be interpreted differently in a different
configuration.

Now that we have described what is to be protected we shall see what protection
means.

## 4.3 - What is protection

Let us start our discussion by studying a very simple case. We have a
data base defined by its schema S and a configuration C. In this configuration
we have a proposition p that we want to protect from user violation. When a user query q is received, the problem of the software interface is to decide whether answering this query would violate the proposition p.

Let us first give a very strict definition of violation.

**Definition 3 :**

Let S be a schema on R and let C be a configuration of this schema. Let p be a true proposition in C which is to be protected, and let q be a query. We say that q is in **strict violation** of p if given q and its answer a(q), we know that p is true.

For instance, in the tax data base configuration, let $p = $"Dupont's income is 45 000"$. The question $q = $"Name, address and income of people making more than 20 000"$^{}$ is in strict violation of p, since given q and its answer a(q) we know that p is true. Another way to look at this situation is to say that user's estimate of the probability that p is true, is different before and after the answer a(q) is known to the user. That is, the knowledge about p has varied.

Based on this observation we can generalize the notion of violation. We shall say that a query q violates a protected proposition p, if it changes the user's knowledge about p, i.e., if it changes user's estimate of the probability that p is true. Hence the following definition of violation.

**Definition 4 :**

Let R, S, C, p, q be as defined earlier. We say that a question q is a **violation** of a protected proposition p, if the answer a(q) modifies user's knowledge about p, that is, if

$$ \text{prob}(p|K_S \uparrow (q,a(q))) \neq \text{prob}(p|K_S). $$
Examples :

Suppose we are protecting the proposition p = "Dupont makes 45 000"
and assume the user knows that salaries range from 5 000 to 100 000. Then the
user's estimate is : pr(p|Ks) = 1/95 000. Now, consider the question q₁ = "Who
makes less than 50 000" and the proposition p₁ = (q₁, a(q₁)) = "Dupont, Martin
and Maxime make less than 50 000". Proposition p₁ is a violation of p because
pr(p|Ks ∧ p₁) = 1/50 000, that is because p₁ modifies user's knowledge about p.

On the other hand, consider the question q₂ = "Is Dupont's income equal
to that of Maxime's?" and suppose the answer is a(q₂) = "Dupont's income is
different than Maxime's". The proposition p₂ = (q₂, a(q₂)) does not violate p
because pr(p|Ks ∧ p₂) = 1/95 000 = pr(p|Ks), that is, because it does not modify
user's knowledge of p.

It should be noted that in order to decide wether or not a question q
violates a protected proposition p, we need only consider the answer a(q) to that
question, no matter what the actual configuration of the data base is. Hence,
the following theorem.

**Theorem 1 :**

Let S be a schema and let C₁, C₂ be two configurations of S. Let p be a
proposition that is true in both C₁ and C₂. Let q be a query having the same
answer a(q) in both C₁ and C₂. Then, q violates p in C₁, if and only if, q
violates p in C₂.

This theorem can be interpreted as follows : the only information we need in
order to decide violation is the protected proposition p, the query q, and its answer
a(q). The rest of the actual data base configuration is irrelevant.

So far, we have seen the violation of *one* proposition by *one* question.
We shall now proceed to generalize this approach to a protection system.
### 4.4 - The protection system.

Figure 2 represents a protection system in all its generality. The data available to this system are the actual configuration C and the proposition p to be protected. The system takes as input a query, and decides whether to accept it (answer the query) or refuse to answer.

From this description we can say that a protection system is specified by:

(i) The set $P_C$ of "confidential propositions". This represents the set of propositions that the user (or the DBA) can declare confidential.

(ii) The set $Q_A$ of "allowable queries". This represents the set of queries that the user is allowed to ask.

(iii) The algorithm which decides whether to accept or to refuse a query $q \in Q_A$, given a protected proposition p $\in P_C$ and a configuration C $\in S$.

Let us now see what is the correct operation of a protection system. Let $L'$ be a possibly infinite set of queries from $R^*$, and let C be some data base configuration. Let $K(L',C)$ denote the knowledge given by $L'$ about C. This knowledge simply consists of all the propositions the user knows to be true after getting the answers to all the queries of $L'$, that is,

$$K(L',C) = \{(q,a(q))|q \in L'\}$$

A given protection system PS with $P_C$, $Q_A$ and some algorithm, defines for each p and C a set of "acceptable queries" i.e., a language that can be written as :

$$L_{PS}(p,C) = \{q|q \in Q_A \text{ and } q \text{ is accepted by PS}\}$$

We can now define a protection system as follows :

**Definition 5 :**

PS is a protection system iff for any C in S and for any p in $P_C$, $K(L_{PS}(p,C),C)$ does not violate p.
This simply states that the knowledge the user can get from _all_ the
possible queries does not violate the protected proposition.

Notice that a system that refuses to answer all the time _is_ a protection system.

Therefore protection systems will be characterized by the size of the sets $P_C$ and $Q_A$ and by the amount of information that can be obtained through the system.

Let us now see if we can build some of these systems. The first candidate,
that we shall call the "simple system" SS, is defined as follows :

$Q_A = R^*$, $P_C$ is the set of all propositions, and a query is accepted if and only if it does not violate $p$. The problem is that such a system is _not_ a protection system. That is, a user can ask two questions, none of which violates the protected information but the combination of both violates this information.

Suppose, for instance, that the following proposition of the tax data base configuration is to be protected :

$p = \text{"Dupont makes 45 000 a year"}$

Next, consider the questions :

$q_1 = \text{"Is Dupont's income equal to that of Maxime's?"}$

$q_2 = \text{"What is Maxime's income?"}$

Neither $q_1$ nor $q_2$ violates $p$ (the reader should convince her/himself that the answer to $q_1$ does _not_ modify user's knowledge about $p$). However, having the answers to both questions clearly violates $p$. In the simple system SS, both queries would have been accepted and the proposition would have been violated. We have thus proved the following theorem.

**Theorem 2**

The simple system SS is _not_ a protection system.

Since that system does not operate correctly we are faced with three types
of solutions : (i) a protection system which keeps track of user's knowledge,
(ii) a protection system with a more powerfull algorithm, (iii) a protection system
in which one or both sets $Q_A$ and $P_C$ are restricted. Let us now study these three
solutions.
(1) **System with memory** In this system, we record in a Journal every new query of the user. Thus, at time t, the journal consists of a list of queries $(q_1, q_2, ..., q_n)$ and if a query $q$ is received at time $t+1$, the system checks whether the proposition

$$ (q_1, a(q_1)) \wedge (q_2, a(q_2)) \wedge \dots \wedge (q_n, a(q_n)) \wedge (q, a(q)) $$

violates $p$ or not.

Consider for instance the two queries $q_1$ and $q_2$ of the simple system example, and assume the user asks $q_1$, then $q_2$. After he/she asks $q_1$, the journal is $(q_1)$. Then he/she asks $q_2$ and the system checks whether

$$ (q_1, q(q_1)) \wedge (q_2, a(q_2)) $$

violates $p$, which it does, hence $q_2$ is rejected, which shows that the system is correct.

Although this system provides total protection, it is an unrealistic one as storage and processing requirements are prohibitively high.

(2) **Total respect system** Before describing this system let us define the concept of total respect.

**Definition 6:** Let $p$ be a protected proposition. A query $q$ **totally respects** $p$ iff $q$ does not violate $p$ and for every $q'$ that does not violate $p$ we have : $q$ and $q'$ does not violate $p$.

The total respect system can now be described as follows. A query $q$ is accepted, if $q$ totally respects the protected proposition $p$. This system is more efficient than the system with memory, in terms of storage requirements. However, checking whether a given query totally respects the protected information appears to be an extremely difficult task.

(3) **The restricted protection system** Finally the most realistic solution seems to be the restriction of $Q_A$. In fact most of the difficulty in designing the PS algorithm comes from the complexity of the queries of $R^*$. An interesting case, presently under study by the authors is when $Q_A = R$
5 - ANALYSIS OF A PROTECTION SYSTEM

In the preceding section we have shown that designing a perfect protection
system is an almost impossible task. Therefore, we shall not pursue this question
any further. Rather, we propose to use our model to evaluate the efficiency of a
protection system. We shall do so by studying a specific protection system with
the following characteristics.

(i) The system protects a relational DBMS.

(ii) The confidential propositions consist of tuples of relations, that is, given a configuration, the DBA can decide to protect such and such tuple in such and such relation.

(iii) The permissible queries are all the queries from $R^*$, (i.e. $Q_A = R$)

(iv) The protection algorithm operates as follows :

All the protected tuples are flagged. When the PS receives a query, it executes that query, i.e. it searches the data base (by the usual means of the DBMS) for the answer relation. If, during this search, no flagged tuple is accessed, the query is accepted. If a flagged tuple is read, the search is aborted and the query is rejected.

Let us now see what is wrong with such a system. For this we shall use the
"Tax Data Base" example.

(1) The confidential propositions do not include any complex information. We
cannot for instance protect the fact that "Martin makes more than 5000" or
the fact that "Dupont does not work for IBM", even though such items of
information are likely to become confidential. Because of this restriction
the user must decide himself what tuples should be flagged to protect
his information. To do so, the user must take into account the actual structure of
W2 file is sorted on Employer (and that the user knows it) and consider the query $q = \text{"Does Dupont work for Renault ?"}$. Since the query attempts to read the tuple (Renault, Dupont, 20 000), which is flagged, it will be rejected. However the user knows that this query has been rejected because that tuple was read (to see this assume Dupont does not work for Renault, then the query is accepted and the answer is no!). Therefore, the user has managed to know the truth from a refusal !

## 6 - CONCLUSION

As data bases increase in size and complexity so does the problem of protecting confidential information. And although there is a lot of concern about this problem, very little seems to have been done to provide tools for its solution.

What we have done, was to study some intuitively important aspects of the problem. Also, to formalize some of the key concepts involved. The goal was to provide a rigorous framework for meaningful discussion. We have proposed some protection systems and discussed their implications. We have shown that this framework was adequate to evaluate protection systems and prove their correctness.
REFERENCES

CODD 70

E.F. Codd, "A Relational Model for Large Shared Data Banks", CACM N° 6 June 1970, pp 377-387.

CODD 72

E.F. Codd, "Relational Completeness of Data Base Sublanguages", in : Data Base Systems, Prentice Hall 1972 (R. Rustin Ed.)

LINDEN 76

T.A. Linden, "Operating System Structures to Support Security and Reliable Software", Computing Surveys Vol. 8 N° 4 December 1976, pp 409-445.

BANCILHON 76

F.M. Bancilhon, "Data Structures : Specification and Realization", Ph.d. Thesis, The University of Michigan, 1976.

SPYRATOS 77

N. Spyratos, F.M. Bancilhon, "Name Independence in the Relational Model", Rapport de Recherche IRIA-Laboria, n° 241, 1976.
<figure><img src="image_3.png" /><figcaption>**Figure 1.** The user can access the data base through a software interface only by means of a query language.</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>**Figure 2.** The protection system decides whether to refuse or to accept a query depending on whether or not the protected information is violated.</figcaption></figure>