A Bayesian approach for on-line max and min auditing

ABSTRACT

In this paper we consider the on-line max and min query auditing problem: given a private association between fields in a data set, a sequence of max and min queries that have already been posed about the data, their corresponding answers and a new query, deny the answer if a private information is inferred or give the true answer otherwise. We give a probabilistic definition of privacy and demonstrate that max and min queries, without "no duplicates" assumption, can be audited by means of a Bayesian network. Moreover, we show how our auditing approach is able to manage user prior-knowledge.

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: Gerardo Canfora , Bice Cavallo, A Bayesian Approach for on-Line Max Auditing, Proceedings of the 2008 Third International Conference on Availability, Reliability and Security, p.1020-1027, March 04-07, 2008 [doi>10.1109/ARES.2008.94]
• 3: 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]
• 4: 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]
• 5: Inference Control in Statistical Databases, From Theory to Practice, January 2002
• 6: D. Heckerman. Causal independence for knowledge acquisition and inference. pages 122--127. Ninth Conference on Uncertainty in Artificial Intelligence, 1993.
• 7: Hugin. www.hugin.com.
• 8: 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]
• 9: 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]
• 10: 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]
• 11: 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
• 12: K. G. Olesen , U. Kjaerulff , F. Jensen , F. V. Jensen , B. Falck , S. Andreassen , S. K. Andersen, A munin network for the median nerve-a case study on loops, Applied Artificial Intelligence, v.3 n.2-3, p.385-403, 1989 [doi>10.1080/08839518908949933]
• 13: Judea Pearl, Probabilistic reasoning in intelligent systems: networks of plausible inference, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 14: Steven P. Reiss, Security in Databases: A Combinatorial Study, Journal of the ACM (JACM), v.26 n.1, p.45-57, Jan. 1979 [doi>10.1145/322108.322113]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Statistical computing

General Terms:
Design, Performance

Keywords:
Bayesian network, auditing, statistical database