Towards Robustness in Query Auditing

Abstract

We consider the online query auditing problem for a database containing private information about individuals: given a sequence of queries posed by an attacker, when should queries be denied to prevent privacy breaches. Historically, all research in auditing has focused on static datasets and known algorithms do not work in the presence of updates. We consider a new auditing problem where records can be inserted, deleted or modified and obtain algorithms for auditing sum queries, max queries and bags of max and min queries in this scenario under the classical notion of compromise. In [11], a new probabilistic notion of compromise was proposed due to the limitations of classical compromise. Not much is known about auditing different kinds of queries under this definition and we present new algorithms for auditing max queries and bags of max and min queries under probabilistic compromise. We conclude with a study of a particular dimension of the utility delivered by an auditor and obtain initial results for the utility of sum auditing under classical compromise. We show a positive result for large datasets - in a sequence of random queries, the number of queries that will be answered before even the first denial occurs is a constant fraction of the size of the dataset. This implies that the auditor will not return answers that are riddled with denials.