Secure databases: Constraints, inference channels, and monitoring disclosures

This paper investigates the problem of inference channels that occur when d atabase constraints are combined with nonsensitive data to obtain sensitive information. We present an integrated security mechanism, called the Discl osure Monitor, which guarantees data confidentiality by extending the stand ard mandatory access control mechanism with a Disclosure Inference Engine. The Disclosure Inference Engine generated all the information that can be d isclosed to a user based on the user's past and present queries and the dat abase and metadata constraints. The Disclosure Inference Engine operates in two modes:data-dependent mode, when disclosure is established based on the actual data items, and data-independent mode, when only queries are utiliz ed to generate the disclosed information. The disclosure inference algorith ms for both modes are characterized by the properties of soundness (i.e., e verything that is generated by the algorithm is disclosed) and completeness (i.e,, everything that can be disclosed is produced by the algorithm). The technical core of this paper concentrates on the development of sound and complete algorithms for both data-dependent and data-independent disclosure s.