Secure databases: Constraints and inference channels

Information security policies in databases aim to protect the confidentiality and the integrity of data, while ensuring data availability. Direct violations of data confidentiality are usually prevented by mandatory access control mechanisms, such as those based on the Bell-LaPadula model. However, even in the presence of a properly functioning mandatory access control mechanism, illegal data accesses by inference channels may occur when constraints are combined with non-sensitive data to infer sensitive data.; This research investigates the problem of detecting and removing inference channels. Previous approaches to the problem of inference channels were based on over-classifying data, which led to unnecessary restrictions on the availability of data to legitimate users. This work is the first to introduce the idea of characterizing inference disclosure algorithms by the formal logic properties of soundness and completeness . Intuitively, soundness means that everything that is generated by the algorithm is disclosed, thus providing maximal data availability; completeness means that everything that can be disclosed is produced by the algorithm, thus guaranteeing confidentiality. Without such characterization we cannot formally compare disclosure inference algorithms and establish their properties with respect to confidentiality and data availability.; The technical core of this dissertation concentrates on the development of sound and complete disclosure inference algorithms for a variety of settings (relational, semi-structured and numeric databases) and constraints (functional, multi-valued and join dependencies, Horn-clause constraints, arithmetic constraints). The developed algorithms can be used in either database design or query processing time.; In summary, the primary contribution of this work to the field of database security is two fold: (1) it provides a much needed representation model of the inference channel problem that allows a security officer to formally assure protection against illegal inferences by the properties of completeness and soundness; (2) provides sound and complete disclosure inference algorithms to generate all the information that can be disclosed by a user.