Abstract
In a database system, disclosure of confidential private data may occur if users can put together the answers of past queries. Traditional access control mechanisms cannot guard against such breaches to private data. Online auditing techniques have been advanced to limit such disclosure of private data. Essentially, before answering any query, these techniques inspect the answers of the past queries to determine whether answering this query would compromise the stated data disclosure policies. While the primary requirement for online auditing is high efficiency, existing auditing approaches are expensive with respect to both computational time and space. Specifically, this cost is excessive in the general case of auditing arbitrary aggregate queries over real-valued confidential attributes with respect to interval-based privacy disclosure.
In this paper, we model this problem as the well-studied linear programming (LP) problem and propose an efficient online auditing solution for constantly monitoring the bounds of protected attributes. The previously proposed approaches in this direction repetitively employ the LP. Consequently, for each new query, they require evaluation of the entire set of answers to past queries. In this paper, we propose a novel approach to employ LP that keeps the prior evaluation state in a concise form and conducts an incremental evaluation. Basically, our approach treats the online auditing problem as a series of updation problems. Each time when a new query is issued by a user, instead of solving a new LP problem with up-to-date log of all queries, we modify the existing bounds obtained in auditing previous queries based on certain rules so as to get the updated bounds with the new query added. Since it significantly reduces the computation time and storage space, our approach offers the first practical solution for the interval-based online auditing problem. Our experimental results demonstrate that our solution is about 30 times faster than the existing solutions.