Towards Trustworthy Database Systems

Principal Investigator: Feifei Li, supported by the Trustworthy Computing program from NSF, NSF link
Students: Wangchao Le, Justin DeBrabant, Steven Burgart, Cody Hansen

[Overview] [Papers and Talks] [Authenticated Index Structures] [PIRS] [Source Code and Library] [Acknowledgement] [Contacts]　

Overview

Answers to database queries often form the basis for critical decision-making. To improve efficiency and reliability, answers to these queries can be provided by distributed servers close to the querying clients. However, because of the servers' ubiquity, the logistics associated with fully securing them may be prohibitive; moreover, when the servers are run by third parties, the clients may not trust them as much as they trust the original data owners. Thus, the authenticity of the answers provided by servers in response to clients' queries must be verifiable by the clients. More generally, database responses are more useful if they contain the evidence of their own correctness. For example, this enables a consumer to provide her own credit report to a creditor without having the creditor request it from the reporting agency to establish the validity of the report. This project is developing methods for authenticating the validity and authenticity of a variety of database queries, including general relational, data cube, and spatio-temporal queries. Furthermore, techniques that use powerful cryptographic primitives are being developed for providing authentication and confidentiality. This research will enable utilization of this infrastructure in applications where users must rely on the authenticity of the answer, such as in financial systems, network monitoring, traffic control, or applications yet to be imagined. The results of this project will be disseminated through publications in journals and conferences. Furthermore, source code of these methods, in the form of libraries, will be made available over the web. This is a collaborative project with the Datbase Lab at Boston University, with Prof. George Kollios and Prof. Leonid Reyzin.

Papers and Talks

1. Rewriting Queries on SPARQL Views, In Proceedings of 20th International World Wide Web Conference (WWW 2011), accepted in 2011.

    Conference version:   Talk:

2. Query Access Assurance in Outsourced Databases, IEEE Transactions on Service Computing (IEEE TSC), To Appear, accepted in 2010.

    Journal version:  

3. Authenticated Index Structures for Aggregation Queries, ACM Transactions on Information and System Security (ACM TISSEC), Vol. 13, No. 4, pages 32:1-32:35, 2010.

    Preliminary draft: , Journal version:

4. Small Synopses for Group-By Query Verification on Outsourced Data Streams, ACM Transactions on Database Systems (ACM TODS), Vol. 34, No. 3, pages1--42, 2009.

    Journal version:  

5. Randomized Synopses for Query Assurance on Data Streams, In Proceedings of 24th IEEE International Conference on Data Engineering (IEEE ICDE 2008).

    Conference version:   Talk:  

6. Hiding in the Crowd: Privacy Preservation on Evolving Streams Through Correlation Tracking, In Proceedings of 23rd IEEE International Conference on Data Engineering (IEEE ICDE 2007).

    Conference version:   Talk:  

7. Proof-Infused Streams: Enabling Authentication of Sliding Window Queries on Streams, In Proceedings of 33rd International Confernce on Very Large Databases (VLDB 2007).

    Conference version:   Talk:  

8. Time Series Compressibility and Privacy, In Proceedings of 33rd International Confernce on Very Large Databases (VLDB 2007).

    Conference version:   Talk:  

9. Dynamic Authenticated Index Structures for Outsourced Databases, In Proceedings of  25th SIGMOD International Conference on Management of Data (SIGMOD 2006).

    Conference version with correction:   Talk:  

Authenticated Index Structures

 Please refer papers above for details. 

 Illustration of the authenticated index structures.   

　

　

PIRS: Polynomial Identity Random Synopses

 Please refer to papers above for details. 

 Illustration of the problem settings

Source Code and Library

1. Authenticated Index Structure Library , please follow this link.

2. Polynomial Identity Randomized Synopsis (PIRS) , please follow this link.

Acknowledgement

This project is supported by the National Science Foundation (NSF) under the project: CT-ISG: Collaborative Research: Towards Trustworthy Database Systems. Any opinions, findings, and conclusions or recommendations expressed in this project are those of author(s) and do not necessarily reflect the views of the National Science Foundation.

Contacts

(picture credits to here) Feifei Li     

Last modified 03/16/06