| Available via | http://dbpubs.stanford.edu/pub/2007-13 |
| Previous version | 2006-12 |
|
Submitted on |
21st of March 2007 |
|
Author |
Motwani, Rajeev; Nabar, Shubha U., Thomas, Dilys |
|
Title |
Auditing SQL Queries |
|
Date of publication |
2007 |
|
Citation |
Motwani, Rajeev; Nabar, Shubha U., Thomas, Dilys. Auditing SQL Queries, |
|
Number of pages |
12 |
|
Language |
English |
|
Project |
PORTIA (DB-Privacy) |
|
Type |
Conference or Journal Paper |
|
Subject group |
Miscellaneous |
|
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. |
|
Contact address |
sunabar@stanford.edu |
| Fulltext source |
PDF (pdf, pdf.gz, pdf.zip)
| Management of the document by | siroker@db.stanford.edu
| |