Exact Detection of Information Leakage: Decidability and Complexity

Authors: Rada Chirkova and Ting Yu

Volume 32 (2017)


Elaborate security policies often require organizations to re- strict user data access in a ne-grained manner, instead of traditional table- or column-level access control. Not surprisingly, managing ne- grained access control in software is rather challenging. In particular, if access is not con gured carefully, information leakage may happen: Users may infer sensitive information through the data explicitly accessible to them. In this paper we formalize this information-leakage problem, by modeling sensitive information as answers to \secret queries," and by modeling access-control rules as views. We focus on the scenario where sensitive information can be deterministically derived by adversaries. We review a natural data-exchange based inference model for detecting information leakage, and show its capabilities and limitation. We then introduce and formally study a new inference model, view-veri ed data exchange, that overcomes the limitation for the query language under consideration. Our formal study provides correctness and complexity results for the proposed inference model in the context of queries belonging to a frequent realistic query type and common types of integrity constraints on the data.