Transcript multilevel_relationa..

The Multilevel Relational
(MLR) Data Model
Ravi Sandhu and Fang Chen
Rufus Knight
April 12, 2000
Introduction
• In multilevel data models data items and
subjects have their own access levels,
called classifications or clearances
• Accessing information by subjects is
restricted by mandatory access controls
Introduction (cont.)
• However, from a security standpoint, this
restriction should be strengthened by the
requirement that operations from any
given level should not be accepted or
rejected due to existence or absence of
any high-level data
• As a result of this, indirect methods of
communication from higher-level
processes to lower-level ones could occur
Introduction (cont.)
• MLR helps by significantly redefining the
strong points of older models (such as
polyinstantiation and referential integrity)
and introducing several new concepts,
such as data-borrow integrity and the
UPLEVEL statement
Introduction (cont.)
• Two other ways it helps:
– Semantic Ambiguity - When it is unclear
which data values from what classes should
be accepted at some access level
– Operational Incompleteness - When it is
uncertain how a tuple (or record) can be
instantiated when by a subject when some
of its classification attributes are unknown
The Basic Multilevel Relational Model
• Consists of these two parts:
– Multilevel Relation Scheme - Denoted by
R(A1, C1, A2, C2, . . ., An, Cn, TC), where each
Ai is a data attribute over domain Di, each Ci
is a classification attribute of Ai, and TC is
the tuple-class attribute
– Relation Instance - A set of distinct tuples of
the form (a1, c1, . . ., an, cn, tc), and is
denoted by r (A1, C1, A2, C2, . . ., An, Cn, TC)
The Basic Multilevel Relational Model (cont.)
• Also consists of a user-specified apparent
primary key (AK) that is composed of a
subset of the data attributes Ai
• Database - A collection of relations; a
database state is a collection of all
relation instances of a database at a
particular time
Ideas Behind Data-Based Semantics
• The data accepted by subjects (or
attributes of a tuple) at one level consists
of two parts:
– The data owned by the subject
– The data borrowed from lower-level subjects
(which can only be changed by the lower
level subjects who own them)
• The data that a subject can see are those
accepted by subjects at its level or at
levels below it
Ideas Behind Data-Based Semantics (cont.)
• Two methods to prevent inference
violations (or two methods of
polyinstantiation):
– Entity Polyinstantiation - When a relation
contains multiple tuples with the same AK
values, but different CAK values
– Element Polyinstantiation - When a relation
contains two or more tuples with identical AK
and CAK values, but with different values for
one or more Ai’s
Formal Description of Data-Based Semantics
• Apparent Primary Key A1 and its
Classification Attribute C1
– t[A1, C1] identifies an entity in r and also
gives the class level of the entity
– t[C1] = c1 means that the entity is created by
a c1-subject and can only be deleted by c1subjects; the entity is called a c1-entity
• Tuple-Class Attribute TC
– t[TC] = tc with t[C1] = c1 means that:
Formal Description of Data-Based Semantics (cont.)
• t is added by a tc-subject and all data in t are
accepted by tc-subjects; absence of t means
the c1-entity is not accepted by tc-subjects
• t can only be seen by subjects with level c’
>= tc (i.e. all a c’-subject can see are tuples
t’ with t’[TC] <= c’)
• t can be deleted either by tc-subjects or by
c1-subjects in cases where the entire entity is
deleted
– When t[TC] = t[C1], t is the base tuple of the
entity, all tuples t’  r such that t’[A1, C1] are
based on t, and t can only be deleted when
the entire entity is to be deleted
Formal Description of Data-Based Semantics (cont.)
• Data Attribute Ai and Classification
Attribute Ci (2 <= i <= n)
– t[Ai, Ci] with t[Ci] = ci and t[TC] = tc (ci <=
tc) indicates that:
• the data t[Ai] accepted by tc-subjects are
currently owned by ci subjects
• t[Ai, Ci] can be maintained (updated) either
by ci-subjects or by tc-subjects
– When t[Ci] < t[TC], t[Ai]  null is borrowed
from the t’[Ai] of t’ which has t’ [A1, C1] = t
[A1, C1] and t’[TC] = t’[Ci] = t[Ci], and is
subject to change when t’ [Ai, Ci] is changed
or t’ is deleted
Formal Description of Data-Based Semantics (cont.)
• Null Value
– t[Ai, Ci] = [null, ci] (ci < tc) means that for
attribute Ai, tc-subjects expect to borrow
data owned by ci-subjects, however, no data
are currently owned by them
– Both t[Ai, Ci] = [null, null] and t[Ai, Ci] =
[null, tc] means that for Ai no data are
available at level tc
Integrity Properties
• There are five integrity properties that
the model must follow:
– Entity Integrity - Contains three aspects that
must be met:
• No tuple in r has a null value for any attribute
in AK
• All attributes in AK have the same
classification in a tuple (or AK is uniformly
classified)
• In any tuple the class of non-key attributes
must dominate CAK
Integrity Properties (cont.)
• Polyinstantiation Integrity
– An instance r of a multilevel relation R
satisfies this integrity iff (for 1 <= i <= n):
• A1, TC 3 Ci
• A1, C1, Ci 3 Ai
• Data-Borrow Integrity
– A key property in data-based semantics and
ensures that the MLR can retain upward
information flow
Integrity Properties (cont.)
– Allows changes of data at a lower level to be
automatically submitted to higher levels
– An instance r of a multilevel relation R meets
this integrity iff for all t  r and 1<= i <= n,
if t[Ai]  null and t[Ci] < t[TC], there exists t’
 r such that t’ [A1, C1] = t[A1, C1] and
t’[TC] = t’[Ci] and t’ [Ai] = t[Ai]
Integrity Properties (cont.)
• Foreign Key Integrity
– Let FK be a foreign key of the referencing
relation R.
– An instance of a multilevel relation R satisfies
this integrity iff for all t  r, either the
referenced attributes of the tuple that FK
represents equal to null or not, and all
attributes in the foreign key have the same
classification
Integrity Properties (cont.)
• Referential Integrity
– The main issue of this integrity is avoidance
of semantic ambiguity, and is defined as
follows:
• Let FK1 be a foreign key in the referencing
relation R1 with primary key AK1
• Let R2 be the referenced relation with primary
key AK2
• Instances r1 of R1 and r2 of R2 meet this
integrity iff
Integrity Properties (cont.)
– For all t11  r1 such that t11[FK1]  null, there
exists t21  r2 such that t11[FK1] = t21[AK2]
and t11[TC] = t21[TC] and t11[CFK1] >=
t21[CAK2]
– For all t11, t12  r1 and t21, t22  r2 if t12[AK1,
CAK1] and t11[TC] = t21[TC] and t12[TC] =
t22[TC] = t11[CFK1] = t12[CFK1] and t11[FK1] =
t21[AK2] = t22[AK2], then t21[AK2, CAK2] =
t22[AK2, CAK2]
SQL Statements
• There are five data manipulation
statements used in the MLR data model
and executed by c-subjects
• Four of them are the traditional SQL
statements (INSERT, DELETE, SELECT,
and UPDATE) and the fifth is new to MLR
(UPLEVEL)
SQL Statements (cont.)
• INSERT Statement
– Each of these statements can insert at most
one tuple into the relation R and is
constructed as follows (for 1 <= i <= n):
• If Ai is in the data attribute list to indicate
that a value is to be entered into it, t[Ai, Ci] =
(ai, ci)
• If Ai is not in the attribute list then,
– if c lies in the range of the lowest classification
value to the highest, t[Ai, Ci] = (null, c)
– if c does not lie in the classification range, t[Ai, Ci]
= (null, null)
• Lastly, t[TC] = c
SQL Statements (cont.)
– The statement is executed iff:
• There is no t’  r such that t’[A1] = a1 and
t’[TC] = c
• The resulting database state satisfies EI
(Entity Integrity), FKI (Foreign Key Integrity),
and RI(1) (Referential Integrity - the first
condition)
SQL Statements (cont.)
• Delete Statement
– Only tuples t  r with t[TC] = c are
considered in this statement
– This statement can perform as follows:
• t is deleted
• If t[C1] = c, all t’  r with t’ [A1, C1] = t[A1,
C1] and t’[TC] > c are deleted from r
• If t[C1] < c, for t’  r with t’ [A1, C1] = t[A1,
C1] and t’[TC] > c and t’[Ci] = c (2 <= i <=
n), t’ [A1] is set to null
SQL Statements (cont.)
• SELECT Statement
– Only those tuples t  r1, r2, . . . that have
t[TC] as c will be taken into account when
searching for the tuples that meet the
desired criteria
– This statement is assumed to always
succeed, even though the returned tuple set
may be an empty set
SQL Statements (cont.)
• UPDATE Statement
– Only tuples t  r with t[TC] = c are
considered in this statement, and are
updated as follows when they meet the userspecified conditions:
• If no attribute of A1 is desired to be updated
and Ai is (2 <= i <= n):
– t[Ai, Ci] = (|si|, c)
– For tuples t’  r with t’[A1, C1] = t[A1, C1] and
t’[TC] > c and t’[Ci] = c, t’[Ai] = |si|
SQL Statements (cont.)
• If some attribute of A1 is needed to be
updated:
– If t[C1] = c, all tuples t’  r that have t’[A1, C1] =
t[A1, C1] and t’[TC] > c are deleted
– If t[C1] < c:
» For 2 <= i <= n, if Ai is not to be updated and t[Ci]
< c, t[Ai, Ci] = (null, c)
» For tuples t’  r with t’[A1, C1] = t[A1, C1] and t’[TC]
> c and t’[Ci] = c, t’[Ai] = null
– For 1 <= i <= n, if Ai is to be updated, t[Ai, Ci] =
(|si|, c)
– This statement is successful iff:
• The resulting database state satisfies EI, FKI,
and RI(1) (at level c)
• Where some attribute of A1 is to be updated:
SQL Statements (cont.)
– There is no t’  r such that for the resulting t[A1],
t’[A1] = t[A1] and t’[TC] = c
– t is not referenced by any other tuple
– When the A1 of a base tuple is to be
changed, all higher level tuples of the entity
will be deleted rather than acquiring a new
A1 value
SQL Statements (cont.)
• UPLEVEL Statement
– Only tuples t  r with t[TC] <= c are
considered in this statement
– For every entity that has at least one tuple t’
 r meeting the user-defined conditions, a ctuple is created as follows:
• t[A1, C1] = t’[A1, C1]
• For 2 <= i <= n
– If Ai is in the GET clause
» If there is a tuple t’’ with t’’[A1, C1] = t[A1, C1] and
t’’[TC] = t’’[Ci] = ci, set t[Ai, Ci] = t’’[Ai, Ci]
» If there is no tuple t’’ with t’’[A1, C1] = t[A1, C1] and
t’’[TC] = t’’[Ci] = ci, set t[Ai, Ci] = (null, ci)
SQL Statements (cont.)
– If Ai is not in the GET clause
– if c lies in the range of the lowest classification
value to the highest, t[Ai, Ci] = (null, c)
– if c does not lie in the classification range, t[Ai, Ci]
= (null, null)
• After these steps:
– If there is a tuple t’’ with t’’[A1, C1] = t[A1, C1] and
t’’[TC] = c:
» Replace t’’ with t
» For any tuple t’’ and any 2 <= i <= n such that
t’’[A1, C1] = t[A1, C1] and t’’[TC] > c and t’’[Ci] = c,
if t[Ai, Ci]  t’’[Ai, Ci], set t’’’ as t’’’[Ai] = null
– If there is no tuple t’’ with t’’[A1, C1] = t[A1, C1]
and t’’[TC] = c, add t into r
– This statement is successful iff the resulting
database state satisfies PI (Polyinstantiation
Integrity), FKI, and RI(1)
Soundness of the MLR model
• In order to verify if it is or is not sound,
soundness (in this case) must be
defined:
– In the MLR data model, a legal database
state is one in which all relation instances
satisfy the five integrity properties
– A sound data model is one in which any
sequence of provided operational statements
will transform any legal database state to a
legal database state
Soundness of the MLR Model (cont.)
• The proof of the model’s soundness was
based on proving that each of the
INSERT, DELETE, UPDATE, and UPLEVEL
statements transformed any legal
database state to a legal database state
• The SELECT statement was ignored since
it leaves the state of the database
unchanged
Soundness of the MLR Model (cont.)
• INSERT Statement
– Since EI, FKI, and RI(1) are already enforced
due to its semantics, only PI, DBI, and RI(2)
(Referential Integrity - the second condition)
need to be satisfied
• PI is satisfied because:
– There is no t’’ in the original r with t’’[A1, C1] =
t[A1, C1] and t’’[TC] = c, since the insertion of t is
permitted only if there is no t’  r such that t’[A1]
= t[A1] and t’[TC] = c
– There is no t’’ in the original r with t’’[A1, C1] =
t[A1, C1] and t’’[TC] > c, since the original r
satisfies DBI (Data-Borrow Integrity)
– There is no t’’ in the original r with t’’[A1, C1] =
t[A1, C1] and t’’[TC] < c, since the definition of
relation instance requires tc >= c1
Soundness of the MLR Model (cont.)
• DBI is satisfied because there is no t[Ai] (1
<= i <= n) in t with t[Ci] < t[TC]
• RI(2) is satisfied for the same reason as (1)
• Delete Statement
– Since RI(1) is enforced by its semantics, only
EI, PI, DBI, FKI, and RI(2) need to be
satisfied
• EI is satisfied because no tuple t’’ in the
original r, which satisfies EI, will change t’’[A1,
C1]
Soundness of the MLR Model (cont.)
• PI is satisfied because
– No new tuple is added
– All tuples t’ win the original r with t’[A1, C1] = t[A1,
C1] and t’[TC] > c and t’[Ci] = c (2 <= i <= n) will
either be deleted or set as t’[Ai] = null
– By the definition of relation instance, there is no
tuple t’’ with t’’[A1, C1] = t[A1, C1] and t’’[TC] < c
and t’’[Ci] = c (2 <= i <= n)
• DBI is satisfied because all tuples t’ in the
original r with t’[A1, C1] = t[A1, C1] and t’[TC]
> c and t’[Ci] = c (2 <= i <= n) are either
deleted or set as t’[Ai] = null
• FKI is satisfied because
– All tuples in the original r satisfy FKI
Soundness of the MLR Model (cont.)
– All tuples t’ in the original r with t’[A1, C1] = t[A1,
C1] and t’[TC] > c and t’[CFK] = c are either
deleted or set as t’[AFK, CFK] = (null, c)
• RI(2) is satisfied for the same reason as (1)
• UPDATE Statement
– Since EI, PKI, and RI are enforced by its
semantics, only PI and DBI need to be
satisfied
• PI is satisfied because
– no new tuple is added
– if t[A1] is updated:
» All tuples t’ in the original r with t’[A1, C1] = t[A1,
C1] and t’[TC] > c and t’[Ci] = c (2 <= i <= n) are
either deleted or set as t’[Ai] = null
Soundness of the MLR Model (cont.)
» For the resulting entity t[A1, C1], the proof is similar
to that for an INSERT statement
– If t[A1] is not updated, for every updated t[Ai] (2
<= i <= n), all t’ in the original r with t’[A1, C1] =
t[A1, C1] and t’[TC] > c and t’[Ci] = c is set to t’[Ai]
= t[Ai]
– By the definition of relation instance, there is no t’’
in the original r with t’’[A1, C1] = t[A1, C1] and
t’’[TC] < c and t’’[Ci] = c (2 <= i <= n)
• DBI is satisfied because:
– Every updated t[Ai] (1 <= i <= n) has t[Ci] = c
– If t[A1] is updated:
» All tuples t’ in the original r with t’[A1, C1] = t[A1,
C1] and t’[TC] > c and t’[Ci] = c (2 <= i <= n) are
either deleted or set as t’[Ai] = null
» For the resulting entity t[A1, C1], the proof is similar
to that for an INSERT statement
– If t[A1] is not updated, for every updated t[Ai] (2
<= i <= n), all t’ in the original r with t’[A1, C1] =
t[A1, C1] and t’[TC] > c and t’[Ci] = c is set to t’[Ai]
= t[Ai]
Soundness of the MLR Model (cont.)
• UPLEVEL Statement
– Since PI, FKI, and RI are enforced by its semantics,
only EI and DBI need to be shown that they are
satisfied
• EI is satisfied because for each added tuple t there
is t’ in the original r, which satisfies EI, such that
t[A1, C1] = t’[A1, C1]
• DBI is satisfied because:
– In the constructed c-tuple t:
» All t[Ai] (2 <= i <= n) with t[Ci] = c are either null or taken
from the original c-tuple that has t[Ci] = c
» All t[Ai] (2 <= i <= n) with t[Ci] = c’ < c are directly taken
from tuples at levels c’
– Where the original c-tuple t’’ is replaced by t, for any 2 <=
i <= n such that t’’[Ai, Ci]  t[Ai, Ci], every tuple t’’’ at
levels c’ (c’ > c) with t’’’[Ci] = c will have t’’’[Ai] set to null
Completeness of the MLR Model
• In order to verify if the MLR model is
complete, completeness must first be
understood
– A complete data model is one in which any
legal database state can be transformed by a
sequence of the provided data manipulation
statements to any other legal database state
Completeness of the MLR Model (cont.)
• To prove its completeness, two lemmas
need to be satisfied
– “Any legal database state can be
transformed by a sequence of the provided
data manipulation statements to an empty
database state”
• This can be proved using three points
provided by the DELETE statement’s
semantics:
– Any entity can be entirely deleted by deleting the
base tuple of the entity
– In deleting an entity, if A1 and C1 are specified in
the conditional statement, only those entities
referenced by the two will be changed
Completeness of the MLR Model (cont.)
– If entities with referencing tuples are deleted
before the entities with referenced tuples are, RI
will always be satisfied and the DELETE operation
will execute
– “An empty database state can be
transformed by a sequence of provided data
manipulation statements to any legal
database state”
• This can be proved by showing that any legal
database state can be constructed as follows:
– Entities with referencing tuples are added before
adding entities with referenced tuples
– A multilevel entity can be added as follows:
» All tuples of the entity are added in reverse
topologically sorted order of their TC values
» Each tuple is added by a subject at the level equal
to the TC value of the tuple, as follows:
Completeness of the MLR Model (cont.)
» The base tuple t1 is added by an INSERT statement
with all Ai that have t1[Ai]  null listed in the INTO
clause, and t1[Ai] in the VALUES clause
» Adding any additional tuple tm is done by an
UPLEVEL statement, possibly followed by an
UPDATE statement; all of the attributes and their
classifications in tm, the classifications being less
than tm‘s TC level, are included in the USE clause of
the UPLEVEL statement; whereas all of the
attributes that do not equal to null and whose
classifications equal to tm‘s TC level are included in
the SET clause of the UPDATE statement; also A1
and C1 and their values are included in the WHERE
clauses for both UPLEVEL and UPDATE
• This process is successful because:
– Adding one entity will not change any other entity
since A1 and C1 are placed in the conditional
statements (or WHERE clauses) for both UPLEVEL
and UPDATE
Completeness of the MLR Model (cont.)
– EI, FKI, and PI are always satisfied, since the
constructed database state is legal
– DBI is always satisfied, since the database is legal
and all tuples of an entity are added in reverse
topologically sorted by their TC values
– RI is always satisfied because the database is
legal, and entities with referencing tuples are
added before adding entities with referenced
tuples
Security of the MLR Model
• The security proof of the MLR data model
is concerned with whether or not MLR
satisfies the requirements of no
“downward” information flow
• To aid in the security proof of MLR, the
following notation was used:
– S: all subjects with varying clearance levels
– T: all tuples with varying tuple classes in a
database state
Security of the MLR Model (cont.)
• SV(c): the set of subjects with clearance
levels <= c
• SH(c): S - SV(c)
• TV(c): the set of tuples with classes lower
<= c
• TH(c): T - TV(c)
• A secure data model is one that is
noninterfering, or any action performed on
the input of a subject of a higher class will
not affect the output of one of a lower class
Security of the MLR Model (cont.)
• Two lemmas have to be proved to prove MLR
is secure
– “For any access level c, changing TH(c) does not
affect the output to any subject s  SV(c)”
• This can be proved by observing the semantics of
the INSERT, DELETE, UPDATE, and UPLEVEL
statements
– Any INSERT statement issued by s could be rejected iff:
» There is a tuple t’  r with t’[A1] = a1 and t’[TC] = c’
» The inserted tuple t violates EI or FKI
» t references some c’-tuple t’, which does not exist
– Any DELETE statement issued by s could be rejected iff
the deleted tuple is referenced by some c’-tuple t’
Security of the MLR Model (cont.)
– Any UPDATE statement issued by s could be rejected
iff:
»
»
»
»
There is a tuple t’  r with t’[A1] = t[A1] and t’[TC] = c’
t violates EI or FKI
The original t is referenced by some c’-tuple t’
t references some c’-tuple t’ that does not exist
– Any UPLEVEL statement issued by s could be rejected
iff:
» There is a tuple t’  r with t’[A1] = t[A1] and t’[C1] 
t[C1] and t’[TC] = c’
» t references some c’-tuple t’ that does not exist
– “For any access level c, deleting any input from
subject s  SH(c) does not change TV(c)”
• This can be proved by using the INSERT,
DELETE, UPDATE, and UPLEVEL statements
again
Security of the MLR Model (cont.)
– An INSERT statement issued by a c’-subject s  SH(c)
(c’ > c) can only generate a c’-tuple t’; since c’ > c, t’
 TV(c)
– A DELETE statement issued by a c’-subject s  SH(c)
(c’ > c) can only:
» Delete c’-tuples t’, and may propagate changes to
tuples t’’ at levels c’’ (c’’ > c’)
» May either update or delete referencing tuples t1’’ at
levels c’’ (c’’ > c’), and possibly propagate changes to
tuples t1’’’ at levels c’’’ (c’’’ > c’’)
» Since c’’’ > c’’ > c’ > c, t’, t’’, t1’’, t1’’’  TV(c)
– An UPDATE statement issued by a c’-subject s  SH(c)
(c’ > c) can only
» Change c’-tuples t’, and may propagate the changes to
tuples t’’ at levels c’’ (c’’ > c’)
» May either update or delete referencing tuples t1’’ at
levels c’’ (c’’ > c’), and possibly propagate changes to
tuples t1’’’ at levels c’’’ (c’’’ > c’’)
» Since c’’’ > c’’ > c’ > c, t’, t’’, t1’’, t1’’’  TV(c)
Security of the MLR Model (cont.)
– An UPLEVEL statement issued by a c’-subject s 
SH(c) (c’ > c) can either add a new c’-tuple t’ or
change an original c’-tuple t’’, and propagate the
changes to tuples t’’’ at levels c’’’ (c’’’ > c’); since c’’’
> c’ > c, t’, t’’, t’’’  TV(c)
• Thus, deleting any input from subject s  SH(c)
does not change TV(c)