Inference channel detection in multilevel relational databases: A graph‐based approach

Abstract

In a multilevel relational (MLR) database, users are not allowed to access data classified at a level higher than their own security classification. However, it may be possible for a low‐level user to infer high‐level data. This article provides methods to detect and eliminate such inference channels. A graph‐based representation of the database schema developed provides a convenient method for inference channel detection by reducing the problem to one of connectivity in the network. Inference channels are eliminated while imposing minimum restrictions on legitimate access using an algorithm based on minimum cut set identification. This approach is then extended to address the problems of abductive and probabilistic inference channels. An abductive inference channel is said to exist when information external to the database is used in the inference process. By demonstrating that only arcs between nodes in different strongly connected components may lead to abductive inference channels, the complexity of the problem of abductive inference channel detection is reduced. The uncertainty about the nature and extent of external information used in the inference process is captured by assigning subjective probabilities. Under the assumption of statistical independence, an algorithm based on identification of paths bounded in length is developed that is adequate for probabilistic inference channel detection. When this assumption is relaxed, upper bounds on the probability of the existence of inference channels is provided.

Keywords:

• database security
• multilevel relational databases
• network optimization