Auditing SQL Queries

This is the latest version of this item.

Abstract

We study the problem of auditing a batch of SQL queries: Given certain forbidden views of a database that must be kept confidential, a batch of SQL queries that were posed over this database, and a definition of suspiciousness, determine if the queries are suspicious with respect to the forbidden views. We introduce two notions of suspiciousness - (1) semantic suspiciousness and (2) a database instance-independent notion of syntactic suspiciousness. We give a polynomial time algorithm for detecting if a batch of select-project-join queries is semantically suspicious with respect to a forbidden view. The algorithm is however polynomial in the size of the database and requires actual execution of the queries against the database. Since syntactic suspiciousness of queries is independent of the underlying database instance, it may seem more desirable since it can potentially enable us to gauge suspiciousness simply by looking at the structure of the queries. We show, however, that this is in fact NP-hard to achieve even when we restrict ourselves to the class of conjunctive select-project queries without inequalities. We therefore weaken the definition and provide an algorithm for auditing a large class of conjunctive queries that is polynomial in just the size of the input queries. The weaker definition has the added advantage of guaranteeing better privacy than semantic suspiciousness. In fact we show that while it may not provide as strong a guarantee as the notion of perfect privacy introduced in [8], it can be used to guarantee sufficiently strong privacy in certain commonly occurring situations. Further it can also be used for auditing queries on the fly in an online setting. Finally, we survey recent research on query auditing and access control and relate the above definitions of suspiciousness to the notion of unconditional validity of a query introduced in database access control literature.

Available Versions of this Item

• Achieving Anonymity via Clustering. (deposited 05 Jun 2006 17:00)
  • Auditing SQL Queries. (deposited 20 Mar 2007 17:00) [Currently Displayed]