Inference Detection in Database Systems

A threat to database security is the misuses of these databases by the authorized users, for example selling the personal information to outsiders. Various access control mechanisms have been proposed for protecting individual information in statistical database systems. These mechanisms are specifically designed for statistical databases, making them not applicable to general purpose database systems. In multilevel secure database systems, a type of attacks called inference is identified. An inference occurs when a user uses legitimate data to infer information without directly accessing it. Existing approaches to inference detection focus on analyzing functional dependencies in the database schema. However, it is possible to exploit data level functional dependencies to achieve inferences. For example, although in general the job title does not functionally determine salary (different vice-presidents may earn different salaries), the dependency may hold for lower rank jobs.

This research investigates the detection of attempts to access personal information in relational database systems. We identify five types of inferences: unique characteristic, logical implication, complementary, overlapping, and functional dependency. Algorithms for these inferences are developed. These inferences are detected by auditing both user queries and their return tables.

In general the inference problem is an NP-complete problem (for example, determining the equivalence between two logical expressions). We have no attempt to completely detect all possible types of inferences. The detection system essentially makes the inference attacks more difficult. This might result in having the user to issue more queries, which then could be detected by anomaly detection techniques.