Securing Databases from Probabilistic Inference

Abstract

Databases can leak confidential information when users combine query results with probabilistic data dependencies and prior knowledge. Current research efforts offer mechanisms that either handle a limited class of dependencies or lack tractable enforcement algorithms necessary for scaling. We propose a foundation for Database Inference Control based on PROBLOG, a probabilistic logic programming language. We leverage this foundation to develop ANGERONA, a provably secure enforcement mechanism that prevents information leakage in the presence of probabilistic dependencies. We then provide a tractable inference algorithm for a practically relevant fragment of PROBLOG. We empirically evaluate ANGERONA’s performance showing that it scales to relevant problems of interest.