Fine-Grained Access Control in Relational Databases

• Motivations
• Contributions
• Future Work

Databases are increasingly being used to store information covered by heterogeneous policies such as privacy policies, which require support for access control with great flexibility. This has led to increasing interest in using fine-grained access control, where different cells in a relation may be governed by different access control rules. Although several proposals have been made to support fine-grained access control, there currently does not exist a formal notion of correctness regarding the query answering procedure. In this work, we propose such a formal notion of correctness in fine-grained database access control, and discuss why existing approaches fall short in some circumstances.  We then propose a fine-grained access control solution that strives to meet the proposed criteria.

Motivations

There exist a number of approaches to specify and enforce fine-grained access control in relational databases, such as Virtual Private Database (VPD) in Oracle, label-based access control in DB2 and the recent limiting disclosure approach in Hippocratic database.  It is certain that fine-grained access control will affect results of queries.  However, there are no formal criteria to restrict to what extent an access control approach may affect query results.  In fact, existing fine-grained access control approaches could lead to misleading results for queries with negation.  In particular, tuples that do not satisfy the selection conditions of a query could be included in the answer of the query due to the way existing algorithms hide unauthorized information as well as the way they evaluate queries.

Contributions

In this work, we identify three criteria for enforcing fine-grained access control policies in databases. Ideally, an algorithm that enforces fine-grained access control policies should be sound, secure, and maximum.  Intuitively, the algorithm is sound if the answer returned by it is consistent with the answer when there is no fine-grained access control. The algorithm is secure if the returned answer does not leak information not allowed by the policy. The algorithm is maximum if it returns as much information as possible, while satisfying the first two properties.

Also, we propose a fine-grained access control solution, which is sound and secure and strives to be maximum.  Our solution consists of a labeling mechanism and a query evaluation algorithm.  On the one hand, our labeling mechanism uses variables instead of NULL to hide unauthorized values so as to preserve more information for query answering.  On the other hand, our query evaluation is specially-designed to handle negation so as to guarantee sound answers to queries with negation.

Finally, we have implemented our query evaluation algorithm using query modification.  In this case, our algorithm can be applied on existing DBMS.  Furthermore, we have performed experiments to compare the performance of our algorithm with other approaches and studied factors that affect the performance of our algorithm.

Please refer to our VLDB 2007 paper “On the Correctness Criteria of Fine-Grained Access Control in Relational Databases” for more details.

Future Work

Our next step is to implement our fine-grained access control solution in the DBMS-level.  Also, we would like to study how to express privacy policies in XACML and store such policies in relational database.  Finally, we will study how to perform aggregation on data that is protected by privacy policies.