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.