Introduction: Outsourced Databases
Recent advance of network technology allows an increasing number of enterprises to outsource their IT functions or business processes to third parties that can provide these services for a much lower cost due to economy of scale. According to a recent survey, IT outsourcing has grown by a staggering 79% as companies seek to reduce costs and focus on their core competencies. Data processing service outsourcing is a major component as most of IT functions evolve around data processing.

Security is essential for outsourced data processing services. Because a third party service provider may not be trusted or may not be securely administrated, security properties must be assured at the infrastructure level. There are two aspects of security in outsourced databases: data privacy[3,4] and query integrity[5,6]. Data security is the science and study of methods of protecting data in computer and communication systems from unauthorized disclosure and modification. Query integrity means that query results returned by the service provider are both correct and complete.

Research work
  • Integrity Auditing of Outsourced Data
  • Providing integrity assurance is a new and challenging task for outsourced databases. Current approaches[6,7,8,9] for this problem require either changes to be made in DBMS kernels, or a significant subset of the data to be stored locally at the client site. Both of the approaches are costly, hard to implement, and ineffective at least in some scenarios. Particularly, a severe challenge is triggered by a rising trend in mobile computing – more and more clients are accessing database services from such devices as PDAs and cell phones, which have limited storage capacity and processing power. Thus, a protocol for integrity assurance needs to impose little storage or computation overhead in the client side. We propose a probabilistic integrity audit method[2]. We insert a small number of tuples into the outsourced database. For a query issued against this augmented database, there is certain probability that a small amount of the inserted tuples are returned with the original data. The integrity of the system can be effectively monitored by analyzing the inserted tuples in a reply. If an inserted tuple that satisfies the query is absent from the reply, then we know the integrity is breached; if all the inserted tuples that satisfies the query does appear in the reply, we can deliver a probabilistic assurance on query integrity.
  • Providing Freshness Guarantees for Outsourced Databases
  • While privacy issues of outsourced databases have been extensively studied, query integrity for outsourced databases has just started to draw attention from the database community. Currently, there still does not exist a solution that can provide complete integrity. In particular, previous studies have not examined the mechanisms for providing freshness guarantees, that is, the assurance that queries are executed against the most up-to-date data, instead of just some version of the data in the past. Providing a practical solution for freshness guarantees is challenging because continuously monitoring data's up-to-dateness is expensive. Current known schemes that provide query integrity over outsourced databases can be categorized into two types. The first type is based on authenticated data structures [6], and the second type uses a probabilistic approach [1]. We provide freshness guarantees for both types of approaches[1]. For the authenticated data structure based scheme, we add timestamps to data signatures to provide freshness guarantees. For the probabilistic approach, we add fake insertion, deletion, and update operations to provide freshness guarantees. In both of the schemes, there is a trade off between the level of the freshness guarantees and the overhead.
    Future Work
    With the rapid development of mobile devices, GPS services and Location Based Services(LBS), spatial dataset has undergone an exponential growth in its scale, which combined with the innate complexity of spatial query processing has made spatial data processing service amazingly expensive and impractical to be handled in-house. Luckily, recent advance of network technology allows an increasing number of enterprises, small companies and individuals to outsource their spatial data processing service to third parties (e.g. Google Maps and Microsoft MapPoint) that can provide these services for a much lower cost due to economy of scale. However, as a third party service provider may not be trusted or may not be securely administrated, security properties must be assured at the infrastructure level. In the future, we will focus on the integrity aspect of security problem which verifies the correctness of data processing service, and propose mechanisms that provide integrity assurance for spatial data processing services offered by third parties.
    • [1] X. Min, H. Wang, J. Yin, X. Meng: Providing Freshness Guarantees for Outsourced atabases. In Proceedings of 11th International Conference on Extending Database echnology(EDBT2008), Nantes, France, March 25-30, 2008.
    • [2] X. Min, H. Wang, J. Yin, X. Meng: Integrity Auditing of Outsourced Data. In Proceedings of 33th International Conference on Very Large Data Bases(VLDB2007), pages 782-793, Vienner, Austria, September 24-28, 2007.
    • [3] D. Denning. Cryptography and Data Security. Addison-Wesley, 1982.
    • [4] Douglas R. Stinson. Cryptography, Theory and Practice. CRC Press, 1995.
    • [5] Einar Mykletun, Maithili Narasimha, and Gene Tsudik. Authentication and integrity in outsourced databases. In NDSS. The Internet Society, 2004.
    • [6] Feifei Li, Marios Hadjieleftheriou, George Kollios, and Leonid Reyzin. Dynamic authenticated index structures for outsourced databases. In SIGMOD Conference, pages 121–132. ACM, 2006.
    • [7] Premkumar T. Devanbu, Michael Gertz, Charles U. Martel, and Stuart G. Stubblebine. Authentic third-party data publication. In DBSec, volume 201 of IFIP Conference Proceedings, pages 101–112. Kluwer, 2000.
    • [8] HweeHwa Pang, Arpit Jain, Krithi Ramamritham, and Kian-Lee Tan. Verifying completeness of relational query results in data publishing. In SIGMOD Conference, pages 407–418. ACM, 2005.
    Maintained by Zhongyuan Wang( ) Copyright ? 2007-2008 WAMDM, All rights reserved