Databases Reference
In-Depth Information
and compromise future correctness assurances by omitting the updated data
from the results (causing an “universe split”). This drastically limits the ap-
plicability of these mechanisms.
We started to explore query correctness by first considering the query ex-
pressiveness problem. Thus, in [114] we proposed a novel method for proofs
of
actual
query execution in an outsourced database framework for
arbitrary
queries. The solution prevents a “lazy” or malicious server from incompletely
(or not at all) executing queries submitted by clients. It is based on a mech-
anism of runtime query “proofs” in a challenge - response protocol. For each
batch of client queries, the server is “challenged” to provide a
proofofquery
execution
that offers assurance that the queries were actually executed with
completeness, over their entire target data set. This proof is then checked
at the client site as a prerequisite to accepting the actual query results as
accurate.
The execution proofs are built around an extension to the
ringer
concept
first introduced in [67]. Its core strength derives from the non-“invertibility”
of cryptographic hash functions. In other words, a successful fake execution
proof requires the “inversion”
1
of a cryptographic hash or a lucky guess. The
probability of the lucky guess is known, controllable and can be made arbi-
trary small. If, as part of the response to a query execution batch, the server
includes a correct, verifiable query execution proof, the client is provided with
a (tunable) high level of assurance that the queries in the batch were exe-
cuted correctly. This constitutes a strong counter-incentive to “lazy”, (e.g.,
cost-cutting) behavior.
We implemented a proof of concept and experimentally validated it in
a real-world data mining application, proving its deployment feasibility. We
analyzed the solution and show that its overheads are reasonable and far
outweighed by the added security benefits. For example an assurance level of
over 95% can be achieved with less than 25% execution time overhead.
Future Work: Powerful Adversary. Arbitrary Queries. Data Up-
dates.
As the above query execution proofs only validate server-side
processing
but not also actual returned results, handling truly malicious adversaries will
require different mechanisms. Moreover, while compute-intensive query sce-
narios are extremely relevant in data-mining applications, a more general so-
lution should consider general types of queries with less computation load
per data tuple (e.g., aggregates such as SUM, COUNT). Handling these is
especially challenging due to the large size of the query space, the hardness of
building general purpose authenticators and the hardness of predicting future
query loads.
We believe future work should focus on two research directions: (1) the
design of secure query (de)composition techniques coupled with specialized
1
We informally define “inversion” of hash functions as finding at least one input
that hashes to a target output.
