Securing Databases from Probabilistic Inference


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.

In 30th IEEE Computer Security Foundations Symposium.