INFERENCE SECURE MULTILEVEL DATABASES

An important component of database security is the inference problem. Inference problems arise whenever the security classifications of information are inconsistent with database structures. If the security label of a theorem (a derivable formula in formal system) is strictly higher than that of the information used in the formal proof, then logical inference problems arise. Similarly, if the security label of an algebraically derived data is higher than the labels of all the data used in the derivation, then there are algebraic inference problems. One of the main results of this paper is: A multilevel relational database is algebraic inference free iff it is a lattice model. A (relational) lattice model is a multilevel relational data model in which the security label of any collection is the least upper bounds of the labels of its elements. A lattice model is equivalent to an aggregation free data model. This paper formally confirms the belief of earlier researchers that aggregation and inference are the different faces of the same problem. The classical inference (second path inference) is a special form of algebraic inference, called join inference. Join inference free data model is also characterized in terms of some general form of lattice models.