An efficient online auditing approach to limit private data disclosure

ABSTRACT

In a database system, disclosure of confidential private data may occur if users can put together the answers of past queries. Traditional access control mechanisms cannot guard against such breaches to private data. Online auditing techniques have been advanced to limit such disclosure of private data. Essentially, before answering any query, these techniques inspect the answers of the past queries to determine whether answering this query would compromise the stated data disclosure policies. While the primary requirement for online auditing is high efficiency, existing auditing approaches are expensive with respect to both computational time and space. Specifically, this cost is excessive in the general case of auditing arbitrary aggregate queries over real-valued confidential attributes with respect to interval-based privacy disclosure.

In this paper, we model this problem as the well-studied linear programming (LP) problem and propose an efficient online auditing solution for constantly monitoring the bounds of protected attributes. The previously proposed approaches in this direction repetitively employ the LP. Consequently, for each new query, they require evaluation of the entire set of answers to past queries. In this paper, we propose a novel approach to employ LP that keeps the prior evaluation state in a concise form and conducts an incremental evaluation. Basically, our approach treats the online auditing problem as a series of updation problems. Each time when a new query is issued by a user, instead of solving a new LP problem with up-to-date log of all queries, we modify the existing bounds obtained in auditing previous queries based on certain rules so as to get the updated bounds with the new query added. Since it significantly reduces the computation time and storage space, our approach offers the first practical solution for the interval-based online auditing problem. Our experimental results demonstrate that our solution is about 30 times faster than the existing solutions.

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: Dakshi Agrawal , Charu C. Aggarwal, On the design and quantification of privacy preserving data mining algorithms, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.247-255, May 2001, Santa Barbara, California, United States [doi>10.1145/375551.375602]
• 3: 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
• 4: Greg J. Badros , Alan Borning , Peter J. Stuckey, The Cassowary linear arithmetic constraint solving algorithm, ACM Transactions on Computer-Human Interaction (TOCHI), v.8 n.4, p.267-306, December 2001 [doi>10.1145/504704.504705]
• 5: Leland L. Beck, A security machanism for statistical database, ACM Transactions on Database Systems (TODS), v.5 n.3, p.316-3338, Sept. 1980 [doi>10.1145/320613.320617]
• 6: Keke Chen , Ling Liu, Privacy Preserving Data Classification with Rotation Perturbation, Proceedings of the Fifth IEEE International Conference on Data Mining, p.589-592, November 27-30, 2005 [doi>10.1109/ICDM.2005.121]
• 7: Francis Chin, Security problems on inference control for SUM, MAX, and MIN queries, Journal of the ACM (JACM), v.33 n.3, p.451-464, July 1986 [doi>10.1145/5925.5928]
• 8: Chin, F. Y. L., Kossowski, P., and Loh, S. C. Efficient inference control for range sum queries. Theor. Comput. Sci. 32 (1984), 77--86.
• 9: Francis Y. Chin , Gultekin Ozsoyoglu, Statistical database design, ACM Transactions on Database Systems (TODS), v.6 n.1, p.113-139, March 1981 [doi>10.1145/319540.319558]
• 10: F. Y. Chin , G. Ozsoyoglu, Auditing and Inference Control in Statistical Databases, IEEE Transactions on Software Engineering, v.8 n.6, p.574-582, November 1982 [doi>10.1109/TSE.1982.236161]
• 11: Cox, L. H. Suppression methodology and statistical disclosure control. Journal of American Statistical Association 75 (1980), 377--385.
• 12: Cox, L. H. Network models for complementary cell suppression. Journal of the American Statistical Association 90 (1995), 1453--1462.
• 13: D. E. Denning , J. Schlorer, Inference Controls for Statistical Databases, Computer, v.16 n.7, p.69-82, July 1983 [doi>10.1109/MC.1983.1654444]
• 14: David Dobkin , Anita K. Jones , Richard J. Lipton, Secure databases: protection against user influence, ACM Transactions on Database Systems (TODS), v.4 n.1, p.97-106, March 1979 [doi>10.1145/320064.320068]
• 15: J. Domingo-Ferrer , J. M. Mateo-Sanz, Practical Data-Oriented Microaggregation for Statistical Disclosure Control, IEEE Transactions on Knowledge and Data Engineering, v.14 n.1, p.189-201, January 2002 [doi>10.1109/69.979982]
• 16: Csilla Farkas , Sushil Jajodia, The inference problem: a survey, ACM SIGKDD Explorations Newsletter, v.4 n.2, p.6-11, December 2002 [doi>10.1145/772862.772864]
• 17: Matteo Fischetti , Juan José Salazar, Solving the Cell Suppression Problem on Tabular Data with Linear Constraints, Management Science, v.47 n.7, p.1008-1027, July 2001 [doi>10.1287/mnsc.47.7.1008.9805]
• 18: Matteo Fischetti , Juan-José Salazar-González, Partial cell suppression: A new methodology for statistical disclosure control, Statistics and Computing, v.13 n.1, p.13-21, February 2003 [doi>10.1023/A:1021927424942]
• 19: Goldman, A. J., and Tucker, A. W. Linear programming. Princeton Unviersity Press (1956).
• 20: Zhengli Huang , Wenliang Du , Biao Chen, Deriving private information from randomized data, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066163]
• 21: Vijay S. Iyengar, Transforming data to satisfy privacy constraints, 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.775089]
• 22: Hillol Kargupta , Souptik Datta , Qi Wang , Krishnamoorthy Sivakumar, On the Privacy Preserving Properties of Random Data Perturbation Techniques, Proceedings of the Third IEEE International Conference on Data Mining, p.99, November 19-22, 2003
• 23: Krishnaram Kenthapadi , Nina Mishra , Kobbi Nissim, Simulatable auditing, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland [doi>10.1145/1065167.1065183]
• 24: Jon Kleinberg , Christos Papadimitriou , Prabhakar Raghavan, Auditing Boolean attributes, Journal of Computer and System Sciences, v.66 n.1, p.244-253, 01 February 2003 [doi>10.1016/S0022-0000(02)00036-3]
• 25: Li, N., Li, T., and Venkatasubramanian, S. t-closeness: Privacy beyond k-anonymity and l-diversity. In ICDE (2007), pp. 106--115.
• 26: Yingjiu Li , Haibing Lu , Robert H. Deng, Practical Inference Control for Data Cubes (Extended Abstract), Proceedings of the 2006 IEEE Symposium on Security and Privacy, p.115-120, May 21-24, 2006 [doi>10.1109/SP.2006.31]
• 27: Li, Y., Wang, L., and Jajodia, S. Preventing interval-based inference by random data perturbation. In Privacy Enhancing Technologies (2002), pp. 160--170.
• 28: Yingjiu Li , Lingyu Wang , Xiaoyang Sean Wang , Sushil Jajodia, Auditing Interval-Based Inference, Proceedings of the 14th International Conference on Advanced Information Systems Engineering, p.553-567, May 27-31, 2002
• 29: Kun Liu , Hillol Kargupta , Jessica Ryan, Random Projection-Based Multiplicative Data Perturbation for Privacy Preserving Distributed Data Mining, IEEE Transactions on Knowledge and Data Engineering, v.18 n.1, p.92-106, January 2006 [doi>10.1109/TKDE.2006.14]
• 30: Ashwin Machanavajjhala , Johannes Gehrke, On the efficiency of checking perfect privacy, Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 26-28, 2006, Chicago, IL, USA [doi>10.1145/1142351.1142375]
• 31: Ashwin Machanavajjhala , Johannes Gehrke , Daniel Kifer , Muthuramakrishnan Venkitasubramaniam, \ell -Diversity: Privacy Beyond \kappa -Anonymity, Proceedings of the 22nd International Conference on Data Engineering, p.24, April 03-07, 2006 [doi>10.1109/ICDE.2006.1]
• 32: Francesco M. Malvestuto , Mauro Mezzini , Marina Moscarini, Auditing sum-queries to make a statistical database secure, ACM Transactions on Information and System Security (TISSEC), v.9 n.1, p.31-60, February 2006 [doi>10.1145/1127345.1127347]
• 33: Gerome Miklau , Dan Suciu, A formal analysis of information disclosure in data exchange, Journal of Computer and System Sciences, v.73 n.3, p.507-534, May, 2007 [doi>10.1016/j.jcss.2006.10.004]
• 34: Motwani, R., Nabar, S. U., and Thomas, D. Auditing sql queries. In Proceedings of the 21th International Conference on Data Engineering (2008).
• 35: Krishnamurty Muralidhar , Rahul Parsa , Rathindra Sarathy, A General Additive Data Perturbation Method for Database Security, Management Science, v.45 n.10, p.1399-1415, October 1999 [doi>10.1287/mnsc.45.10.1399]
• 36: Nabar, S. U., Kenthapadi, K., Mishra, N., and Motwani, R. A survey of query auditing techniques for data privacy. In In Privacy-Preserving Data Mining: Models and Algorithms, Springer, 2008 (to appear).
• 37: Shubha U. Nabar , Bhaskara Marthi , Krishnaram Kenthapadi , Nina Mishra , Rajeev Motwani, Towards robustness in query auditing, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 38: Rakesh Agrawal , Roberto Bayardo , Christos Faloutsos , Jerry Kiernan , Ralf Rantzau , Ramakrishnan Srikant, Auditing compliance with a Hippocratic database, Proceedings of the Thirtieth international conference on Very large data bases, p.516-527, August 31-September 03, 2004, Toronto, Canada
• 39: Samarati, P., and Sweeney, L. Protecting privacy when disclosing information: k-anonymity and its enforcement through generalization and suppression. Technical report, SRI International, 1998.
• 40: Jan Schlörer, Security of statistical databases: multidimensional transformation, ACM Transactions on Database Systems (TODS), v.6 n.1, p.95-112, March 1981 [doi>10.1145/319540.319555]
• 41: Schlörer, J. Information loss in partitioned statistical databases. Comput. J. 26, 3 (1983), 218--223.
• 42: Latanya Sweeney, Achieving k-anonymity privacy protection using generalization and suppression, International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, v.10 n.5, p.571-588, October 2002 [doi>10.1142/S021848850200165X]
• 43: J. F. Traub , Y. Yemini , H. Woźniakowski, The statistical security of a statistical database, ACM Transactions on Database Systems (TODS), v.9 n.4, p.672-679, Dec. 1984 [doi>10.1145/1994.383392]
• 44: Vanderbei, R. J. Linear Programming: Foundations and Extensions (3rd edition). Springer, 2008.
• 45: Ke Wang , Philip S. Yu , Sourav Chakraborty, Bottom-Up Generalization: A Data Mining Solution to Privacy Protection, Proceedings of the Fourth IEEE International Conference on Data Mining, p.249-256, November 01-04, 2004
• 46: Wang, L., Jajodia, S., and Wijesekera, D. Securing olap data cubes against privacy breaches. In IEEE Symposium on Security and Privacy (2004), pp. 161--175.
• 47: Wang, L., Li, Y., Wijesekera, D., and Jajodia, S. Precisely answering multi-dimensional range queries without privacy breaches. In ESORICS (2003), pp. 100--115.
• 48: Willenborg, L., and de Waal, T. Statistical Disclosure Control in Practice. Springer Verlag, 1996.