A data-level database inference detection system
Raymond Wai-Man Yip, Karl Levitt · 1998
A Data Level Database Inference Detection System by Raymond Wai-Man Yip Doctor of Philosophy in Computer Science University of California at Davis Professor Karl Levitt, Chair Inference is a technique a user can employ to defeat access control mechanisms in a database system. It poses a con#dentiality threat to a database system, making it di#cult to control access to sensitive information. An inference detection system is needed to determine if users can use legitimately accessed data to infer sensitive information. The design of an inference detection system is a trade-o# among soundness, completeness, accessibility of the database, and e#ciency of the inference detection process. We describe six inference rules to determine if an adversary has collected enough data to perform inference, namely split query, subsume, unique characteristic, overlapping, complementary, and functional dependency. We prove our detection system is sound, thus it will not object to legitimate queries. Schema-based inference detection systems, which detect inference using functional dependencies, are unsound and incomplete, that is, they can generate false positives and negatives. Our system makes use of the database contents to detect inferences, making it more complete than schema-based inference detection systems. In this respect, our inference detection system detects a known inference attack called Tracker, not detectable by the schema-based approach. Our detection system can be ine#cient, as we need to keep track of all queries issued by users, and perform inference detection using them. A performance evaluation of our prototype shows that the system performance is a#ected by the size of the database, the amount of duplication of data in the database, the number of projected attri...