Information leakage in Datalog-based trust management systems

Most trust management systems that specify authorization in a high-level policy language and support credential-based authorization are vulnerable to a little known class of attacks, so-called probing attacks. A probing attack is conducted by running probes against the system, i.e., by submitting access requests together with credentials, and observing the system’s reactions. This may enable an external adversary to gain knowledge about confidential facts in the policy. We present the first complete decision procedure for checking if an adversary, characterized by a set of probes available in an attack, is unable to gain knowledge about confidential information about a policy specified in Datalog (in which case the information is said to be opaque). This also positively answers the hitherto open question of whether the opacity problem in this setting is decidable. We describe a prototype implementation that is equipped with a number of optimizations to prune the search space, and empirical results from experiments, based on a realistic delegation policy, to test the scalability of the algorithm and the effectiveness of our optimization methods.