12-10-2010, 10:46 AM
[attachment=5640]
Database Systems
Inference Detection in Database Systems:
================================
1. 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.
2. 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.
3. 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.
4. 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.
5. NP is the set of decision problems solvable in polynomial time by a non-deterministic Turing machine.
6. Anomaly Detection refers to detecting patterns in a given data set that do not conform to an established normal behavior Bayesian network: A Bayesian network (or a belief network) is a probabilistic graphical model that represents a set of variables and their probabilistic independencies. For example, a Bayesian network could represent the probabilistic relationships between diseases and symptoms. Given symptoms, the network can be used to compute the probabilities of the presence of various diseases. Formally, Bayesian networks are directed acyclic graphs whose nodes represent variables, and whose missing edges encode conditional independencies between the variables. Nodes can represent any kind of variable, be it a measured parameter, a latent variable or a hypothesis.
