Data level inference detection in database systems

Existing work on inference detection for database systems mainly employ functional dependencies in the database schema to detect inferences. It has been noticed that analyzing the data stored in the database may help to detect more inferences. We describe our effort in developing a data level inference detection system. We have identified five inference rules that a user can use to perform inferences. They are "subsume", "unique characteristic", "overlapping", "complementary", and "functional dependency" inference rules. The existence of these inference rules confirms the inadequacy of detecting inferences using just functional dependencies. The rules can be applied any number of times and in any order. These inference rules are sound. They are not necessarily complete, although we have no example that demonstrates incompleteness. We employ a rule based approach so that future inference rules can be incorporated into the detection system. We have developed a prototype of the inference detection system using Perl on a Sun SPARC 20 workstation. The preliminary results show that on average it takes seconds to process a query for a database with thousands of records. Thus, our approach to inference detection is best performed offline, and would be most useful to detect subtle inference attacks.