Detecting information leakage in database access control with help from data exchange
Rada Y. Chirkova, Ting Yu · NCSU Libraries Repository (North Carolina State University Libraries) · 2013
We study the following problem: Given a set of answers, M V , to some fixed queries, V, on an (unavailable) database instance of interest, I, and given another query, Q: Which of the answer tuples to Q on I are "deterministically assured" by the contents of M V ?That is, which tuples t must necessarily be present in the answer to the query Q on the instance I, based on the information in V, in M V , and (optionally) in the set Σ of integrity constraints that must hold on I? (We say that there is information leakage of Q via M V and V iff at least one such tuple t exists.)Note that the instance I is not available for making the determination.We perform a theoretical investigation of the above problem of information-leak disclosure.We focus on the relational setting, and assume that Q and the queries in V are conjunctive queries, and the set Σ of integrity constraints (when present) is "weakly acyclic" [18].We use data-exchange techniques to develop a sound and complete algorithm for solving the problem in this setting.The results of this paper are applicable to fundamental problems in information management, especially in database security and privacy.One immediate application is in contexts where database users are assigned data-access privileges using fine-grained access control, intuitively via view definitions.In such contexts, our algorithm would permit database owners to detect information leakage in cases where a database user, or a group of possibly colluding users, are given privileges that will enable the users to deterministically derive some sensitive information contained in the database.