Feifei Li, Marios Hadjieleftheriou, George Kollios and Leonid Reyzin
[Overview] [Papers and Talks] [Authenticated Index Structures] [Source Code] [Acknowledgement] [Contacts]
In outsourced database (ODB) systems the database owner publishes its data through a number of remote servers, with the goal of enabling clients to access and query the data more efficiently. As servers might be untrusted or can be compromised, the client cannot trust servers, query authentication becomes an essential component of ODB systems. Clients should be given the capability to verify that the answers provided by the servers are correct with respect to the actual data published by the owner.
Three main entities exist in the ODB model: the data owner, the database service provider (a.k.a.server) and the client. In practice, usually there is a single or a few data owners, a few servers, and many clients. The data owner first creates the database, along with the associated index and authentication structures and uploads it to the servers. It is assumed that the data owner might update the database periodically or in an ad-hoc manner, and that the data management and retrieval happens only at the servers. Clients submit queries about the owner's data to the servers.
It is much cheaper to maintain ordinary servers than to maintain truly secure ones, particularly in the
distributed setting. To guard against malicious/compromised servers, the owner must
give the clients the ability to authenticate the answers they receive without having to trust the servers.
In that respect, query authentication has three important dimensions: correctness,
completeness and freshness. Correctness means that the client must be able to validate that
the returned records do exist in the owner's database and have not been modified in any way. Completeness means that no answers have been omitted from the result. Finally,
freshness means that the results are based on the most current version of the database, that
incorporates the latest owner updates.
In this project, we investigate the design of efficient authenticated index
structures in such system to enable the client to authenticate the query results
and meanwhile reduce the associated costs, taking into account not only the usual structural maintenance overheads, but
the cost of cryptographic operations as well. The ultimate goal is to design and
implement a secure authenticated database system that supports the majority (or
all) of the standard SQL query operations. We start with the general selection
and projection queries, and extend our study into more involved
type of queries, such as the important aggregation queries.
1. Authenticated Index Structures for Aggregation Queries,To Appear in ACM Transactions on Information and System Security(ACM TISSEC) 2010.
Journal version:
2. Dynamic Authenticated Index Structures for Outsourced Databases, In Proceedings of 25th SIGMOD International Conference on Management of Data (SIGMOD 2006), Chicago, Illinois, USA, June 2006.
Conference version with
correction:
Talk:
3. Authenticated Index Structures for Aggregation Queries in Outsourced Databases, Technical Report, July, 2006.
Preliminary draft:
Please refer papers above for details.
Illustration of the authenticated index structures.
Important Notice
The current version of codes is still in "experimental" shape. It is not an official release. The insertions for various index structures have been thoroughly tested. However, the deletions are not fully tested and not guaranteed to work. We are still further testing and working on that aspect. If you find any bugs or any suggestions/comments, we are very happy to hear from you! Please send email to lifeifei@cs.bu.edu or mhadji@gmail.com.
Library Description
The library is developed based on the framework of Spatial Index Library. It is very easy to compile and install in a Linux system, as long as you have Automake , Autoconf and LibTool libraries installed. The library depends on:
Tools Library and two cryptography libraries: OpenSSL and Crypto++.
The library is designed to support configuration such that it could be installed in any directory. The default path is set to /usr/local/lib. So in default installation, you need to have root access. OpenSSL and Crypto++ also support configuration of installation path, however we recommend to install them with default path (i.e. with root access) to avoid any conflict/confusion to our library. We will further test flexible install configuration in the official release.
Our library is tested with the following version of corresponding dependent libraries (already included in the authenticated index structures library download-link below):
1. Tools Library : [tar.gz]
2. OpenSSL: [tar.gz]
3. Crypto++: [tar.gz]
4. Automake: [tar.gz]
5. Autoconf: [tar.gz]
6. LibTool: [tar.gz]
It should have no problem to compile the latest version of these libraries if you get them from their original sources. However, we do not guarantee that.
Features
Our authenticated index structures library has fully implemented the authenticated index structures described in the papers. Our implementation includes a disk manager that supports serializing the indexes and also measures the disk I/Os. Detail description will be available soon.
Download
1. Standard Authenticated Index Structures Library [tar.gz]
This version includes the followings: MB Tree, EMB Tree, EMB- Tree, EMB* Tree and their corresponding bulk loading versions. It also includes an implementation of B+ tree. In addition, it includes various generators for testing the library. Please use the generators in the regressiontest folder of normal_bree_spatialindex. Over there you may also find some test data sets that have been already generated.
2. Authenticated
Aggregation Index Structures Library [tar.gz]
This version includes the followings: APS Tree, AAB Tree and AAR Tree. (In the library, the NwayTree is the implementation of APS tree, we will fix the naming issue in the official release version.) In addition, it includes the various generators to test the library. Please find the generators under generator folder in regressiontest. Over there, sample test data sets have already been generated.
3. Everything Together [tar.gz]
The complete Authenticated Index Structures Library.
Quick Install
1. Make sure you have root access
2. Install LibTool, Autoconf, Automake if your system does not have these libraries.
3. Install OpenSSL and Crypto++
4. Install Tools library
Go into tools directory, type (in sequence): aclocal, autoconf, automake, ./configure, make, make install.
5. Install the target library
Go into the library's directory, type (in sequence): aclocal, autoconf, automake, ./configure, make, make install.
We thank Maithili Narasimha and Gene Tsudik for helping us identify a discrepancy associated with measuring the cost of signing operations with the signature chaining approach in our camera ready version. The paper has then been updated and the version with the correction could be found in the paper download link above.
(picture
credits to here) Feifei
Li
