Privacy preserving database application testing

ABSTRACT

Traditionally, application software developers carry out their tests on their own local development databases. However, such local databases usually have only a small number of sample data and hence cannot simulate satisfactorily a live environment, especially in terms of performance and scalability testing. On the other hand, the idea of testing applications over live production databases is increasingly problematic in most situations primarily due to the fact that such use of live production databases has the potential to expose sensitive data to an unauthorized tester and to incorrectly update information in the underlying database. In this paper, we investigate techniques to generate mock databases for application software testing without revealing any confidential information from the live production databases. Specifically, we will design mechanisms to create the deterministic rule set R, non-deterministic rule set N R, and statistic data set S for a live production database. We will then build a security Analyzer which will process the triplet <R',N R',S'> together with security requirements (security policy) and output a new triplet <R',N R',S'> The security Analyzer will guarantee that no confidential information could be inferred from the new triplet <R',N R',S'> The mock database generated from this new triplet can simulate the live environment for testing purpose, while maintaining the privacy of data in the original database.

REFERENCES

• 1: Nabil R. Adam , John C. Worthmann, Security-control methods for statistical databases: a comparative study, ACM Computing Surveys (CSUR), v.21 n.4, p.515-556, Dec. 1989 [doi>10.1145/76894.76895]
• 2: Rakesh Agrawal , Ramakrishnan Srikant, Privacy-preserving data mining, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.439-450, May 15-18, 2000, Dallas, Texas, United States
• 3: L. Brankovic, and V. Estivill-Castro. Privacy issues in knowledge discovery and data mining. In Proceedings of 1st Australian Institute of Computer Ethics Conference, July, 1999.
• 4: David Chays , Saikat Dan , Phyllis G. Frankl , Filippos I. Vokolos , Elaine J. Weber, A framework for testing database applications, Proceedings of the 2000 ACM SIGSOFT international symposium on Software testing and analysis, p.147-157, August 21-24, 2000, Portland, Oregon, United States
• 5: B. Chor , O. Goldreich , E. Kushilevitz , M. Sudan, Private information retrieval, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.41, October 23-25, 1995
• 6: Yael Gertner , Yuval Ishai , Eyal Kushilevitz , Tal Malkin, Protecting data privacy in private information retrieval schemes, Journal of Computer and System Sciences, v.60 n.3, p.592-629, June 2000 [doi>10.1006/jcss.1999.1689]
• 7: R. A. Davies, R. J. Beynon, and B. F. Jones. Automating the testing of databases. In Proceedings of the first International Workshop on Automated Program Analysis, Testing and Verification, June 2000.
• 8: Irit Dinur , Kobbi Nissim, Revealing information while preserving privacy, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.202-210, June 09-11, 2003, San Diego, California [doi>10.1145/773153.773173]
• 9: J. Domingo-Ferrer. Current directions in statistical data protection. In Proceeding of Statistical Data Protection, 1998.
• 10: Vladimir Estivill-Castro , Ljiljana Brankovic, Data Swapping: Balancing Privacy against Precision in Mining for Logic Rules, Proceedings of the First International Conference on Data Warehousing and Knowledge Discovery, p.389-398, September 01, 1999
• 11: Alexandre Evfimievski , Ramakrishnan Srikant , Rakesh Agrawal , Johannes Gehrke, Privacy preserving mining of association rules, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775080]
• 12: Oded Goldreich, Foundations of Cryptography: Basic Tools, Cambridge University Press, New York, NY, 2000
• 13: S. Goldwasser , S. Micali , C. Rackoff, The knowledge complexity of interactive proof systems, SIAM Journal on Computing, v.18 n.1, p.186-208, Feb. 1989 [doi>10.1137/0218012]
• 14: S. Goldwasser and S. Micali. Probabilistic encryption. Journal of Computer and System Science28 (2):270--299, 1984.
• 15: Arnaud Gotlieb , Bernard Botella , Michel Rueher, Automatic test data generation using constraint solving techniques, Proceedings of the 1998 ACM SIGSOFT international symposium on Software testing and analysis, p.53-62, March 02-04, 1998, Clearwater Beach, Florida, United States
• 16: Jim Gray , Prakash Sundaresan , Susanne Englert , Ken Baclawski , Peter J. Weinberger, Quickly generating billion-record synthetic databases, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.243-252, May 24-27, 1994, Minneapolis, Minnesota, United States
• 17: M. Kantarcioglu, and C. Clifton. Privacy preserving distributed mining of association rules on horizontally partitioned data. In ACM SIGMOD Workshop on Research Issues on Data Mining and Knowledge Discovery, pp. 24--31, June 2002.
• 18: J. J. Kim. A method for limiting disclosure in microdata based on random noise and transformation. In Proceedings of the section on survey research methods, American Statistical Association, 1986.
• 19: J. J. Kim, and W. E. Winkler. Masking microdata files. Report of Bureau of the Census, 1997.
• 20: S. Kirkpatrick, S. D. Gelatt, and M. P. Vecchi. Optimization by simulated annealing. Science 220(4958):671--680.
• 21: Yehuda Lindell , Benny Pinkas, Privacy Preserving Data Mining, Proceedings of the 20th Annual International Cryptology Conference on Advances in Cryptology, p.36-54, August 20-24, 2000
• 22: Niagara. http://www.cs.wisc.edu/niagara/datagendownload.html
• 23: William H. Press , Brian P. Flannery , Saul A. Teukolsky , William T. Vetterling, Numerical recipes in C: the art of scientific computing, Cambridge University Press, New York, NY, 1988
• 24: Quest. http://www.almaden.ibm.com/software/quest/
• 25: S. Rizvi, and J. Haritsa. Privacy preserving association rule mining. In Proceedings of 28th International Conference on Very Large Data Bases. Aug, 2002.
• 26: C. J. Skinner. On identification disclosure and prediction disclosure for microdata. Statistica Neerlandica, 44:21--32, 1992.
• 27: Michael Stonebraker , Lawrence A. Rowe, The design of POSTGRES, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.340-355, May 28-30, 1986, Washington, D.C., United States
• 28: B. Malin, L. Sweeney, and E. Newton. Trail re-identification: learning who you are from where you have been. Proc. LIDAP-WP12. Carnegie Mellon University, 2003.
• 29: Transaction Processing Performance Council. TPC-Benchmark C. 1998.
• 30: Edward Tsang. Foundations of constraint satisfaction. Academic Press, 1993.
• 31: Jaideep Vaidya , Chris Clifton, Privacy preserving association rule mining in vertically partitioned data, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775142]
• 32: Jaideep Vaidya , Chris Clifton, Privacy-preserving k-means clustering over vertically partitioned data, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956776]
• 33: G. Wiederhold , M. Bilello, Protecting Inappropriate Release of Data from Realistic Databases, Proceedings of the 9th International Workshop on Database and Expert Systems Applications, p.330, August 26-28, 1998
• 34: Gio Wiederhold , Michel Bilello , Chris Donahue, Web Implementation of a Securtty Mediator for Medical Databases, Proceedings of the IFIP TC11 WG11.3 Eleventh International Conference on Database Securty XI: Status and Prospects, p.60-72, August 10-13, 1997
• 35: A. Yao. How to generate and exchange secrets. In Proceedings of the 27th IEEE symposium on Foundations of Computer Science, pp. 162--167, 1986.
• 36: A. Yao. Theory and application of trap-door functions. In Proc. of 23rd IEEE Symposium on Foundation of Computer Science, page 80--91, 1982.

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Testing tools (e.g., data generators, coverage testing)

Additional Classification:
  H. Information Systems
  H.1 MODELS AND PRINCIPLES
      H.1.1 Systems and Information Theory
          Subjects: Information theory
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Statistical databases

General Terms:
Algorithms, Performance, Security, Theory

Keywords:
database application testing, indistinguishability, privacy