|
|
|
The Secure Query Interface is a secure extension to legacy query interfaces guaranteeing proofs of query execution, correctness and completeness with reasonable execution overheads. It is extensible in that it allows for arbitrary plugins to be written for additional expression ability (e.g. a constraint plugin that could be used to handle privacy constraints and enforce inference controls). It allows for access to any arbitrary (set of) remote data sources.  Off-loading data management needs to specialized service providers is intuitively advantageous and significantly more affordable for parties with less experience, resources or trained man-power such as small companies and individuals. More-over, the resulting expertise consolidation at the service provider is likely to result in increased availability, better quality and cheaper service. 
Significant security issues are associated with such "outsourced database" frameworks, including communication-layer security and privacy, of both the data and associated access patterns. Of equal concern is the ability to provide assurances of service execution and correctness. For a batch of data queries, it is important to ensure result accuracy as well as authenticity of their input data sets; assurances are required for the fact that the serviced client queries were in fact executed correctly over the entire intended target data sets. This is important because server loads and associated costs (among others) are providing significant incentives for "lazy" (possibly malicious) behavior. 
In this work we propose and analyze a method for query execution assurance in an outsourced database framework. Our initial solution is not limited to simple selection predicate queries but handles arbitrary query types. The data being at the service provider's site makes this problem especially challenging; after all it is exactly the service provider that intermediates all access to the data. Our solution introduces query execution proofs; for each executed batch of queries the service provider is required to provide a cryptographic proof that shows the queries were actually executed. We implemented a preliminary proof of concept and experimented in a real-world data mining application, proving the deployment feasibility of our solution. We analyze the solution and show that its overheads are reasonable and are far outweighed by the significant added security benefits. For example an assurance level of over 95% can be achieved with less than 25% execution time overhead. |
|
(C) 2004. All Rights Reserved.
|