Auditing sum-queries to make a statistical database secure

ABSTRACT

In response to queries asked to a statistical database, the query system should avoid releasing summary statistics that could lead to the disclosure of confidential individual data. Attacks to the security of a statistical database may be direct or indirect and, in order to repel them, the query system should audit queries by controlling the amount of information released by their responses. This paper focuses on sum-queries with a response variable of nonnegative real type and proposes a compact representation of answered sum-queries, called an information model in “normal form,” which allows the query system to decide whether the value of a new sum-query can or cannot be safely answered. If it cannot, then the query system will issue the range of feasible values of the new sum-query consistent with previously answered sum-queries. Both the management of the information model and the answering procedure require solving linear-programming problems and, since standard linear-programming algorithms are not polynomially bounded (despite their good performances in practice), effective procedures that make a parsimonious use of them are stated for the general case. Moreover, in the special case that the information model is “graphical.” It is shown that the answering procedure can be implemented in polynomial time.

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: Ahuja, R. K., Magnanti, T. L., and Orlin, J. B. 1993. Network Flows. Prentice Hall, Englewood Cliffs, NJ.
• 3: Meng Chang Chen , Lawrence McNamee , Michel A. Melkanoff, A model of summary data and its applications in statistical databases, Proceedings of the 4th international conference on Statistical and Scientific Database Management, p.356-372, June 21-23, 1988, Rome, Italy
• 4: M. C. Chen , L. P. McNamee, On the Data Model and Access Method of Summary Data Management, IEEE Transactions on Knowledge and Data Engineering, v.1 n.4, p.519-529, December 1989 [doi>10.1109/69.43426]
• 5: 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]
• 6: Chin, F. Y. and Ozsoyoglu, G. 1982. Auditing and inference control in statistical databases. IEEE Trans. Software Engineering 8, 574--582.
• 7: Chvátal, V. 1983. Linear Programming. Freeman, New York.
• 8: Cox, L. H. 1980. Suppression methodology and statistical disclosure control. J. American Statistical Association 75, 377--385.
• 9: Cox, L. H. and Zayatz, L. V. 1995. An agenda for research on statistical disclosure limitation. J. Official Statistics 11, 205--220.
• 10: Dobra, A. and Fienberg, S. E. 2000. Bounds for cell entries in contingency tables given the marginal totals and decomposable graphs. In Proc. Nat. Acad. Sci. USA 97, 11885--11892.
• 11: Duncan, G. T., Fienberg, S. E., Krishnan, R., Padman, R., and Roehrig, S. F. 2001. Disclosure limitation methods and information loss for tabular data. In Confidentiality, Disclosure and Data Access, P. Doyle, J. Lane, J. Theeuwes, L. Zayatz, Eds. Elsevier, New York, 135--166.
• 12: Dan Gusfield, A graph theoretic approach to statistical data security, SIAM Journal on Computing, v.17 n.3, p.552-571, June 1988 [doi>10.1137/0217034]
• 13: Jon Kleinberg , Christos Papadimitriou , Prabhakar Raghavan, Auditing Boolean attributes, Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.86-91, May 15-18, 2000, Dallas, Texas, United States [doi>10.1145/335168.335210]
• 14: David Maier, Theory of Relational Databases, Computer Science Pr, 1983
• 15: Francesco M. Malvestuto, A universal-scheme approach to statistical databases containing homogeneous summary tables, ACM Transactions on Database Systems (TODS), v.18 n.4, p.678-708, Dec. 1993 [doi>10.1145/169725.169712]
• 16: Malvestuto, F. M. and Mezzini, M. 2001. On the hardness of protecting sensitive information in a statistical database. In Proceedings of the World Multiconference on Systemics, Cybernetics and Informatics, vol. XIV. 504--509.
• 17: F. M. Malvestuto , M. Mezzini, A Linear Algorithm for Finding the Invariant Edges of an Edge-Weighted Graph, SIAM Journal on Computing, v.31 n.5, p.1438-1455, 2002 [doi>10.1137/S0097539700376068]
• 18: Francesco M. Malvestuto , Mauro Mezzini, Auditing Sum Queries, Proceedings of the 9th International Conference on Database Theory, p.126-142, January 08-10, 2003
• 19: Malvestuto, F. M. and Mezzini, M. 2004. Privacy preserving and data mining in an on-line statistical database of additive type. In Proceedings of the International Conference on Privacy in Statistical Databases, Barcelona.
• 20: F. M. Malvestuto , M. Moscarini, Query Evaluability in Statistical Databases, IEEE Transactions on Knowledge and Data Engineering, v.2 n.4, p.425-430, December 1990 [doi>10.1109/69.63254]
• 21: Malvestuto, F. M. and Moscarini, M. 1999. An audit expert for large statistical databases. In Statistical Data Protection, EUROSTAT. 29--43.
• 22: Francesco Malvestuto , Marina Moscarini, Privacy in multidimensional databases, Multidimensional databases: problems and solutions, Idea Group Publishing, Hershey, PA, 2003
• 23: Alexandeer Schrijver, Theory of linear and integer programming, John Wiley & Sons, Inc., New York, NY, 1986
• 24: Lingyu Wang , Duminda Wijesekera , Sushil Jajodia, Cardinality-Based Inference Control in Sum-Only Data Cubes, Proceedings of the 7th European Symposium on Research in Computer Security, p.55-71, October 14-16, 2002
• 25: Lingyu Wang , Duminda Wijesekera , Sushil Jajodia, Cardinality-based inference control in data cubes, Journal of Computer Security, v.12 n.5, p.655-692, September 2004
• 26: Willenborg, L. and de Waal, T. 1996. Statistical Disclosure Control in Practice. Lecture Notes in Statistics, vol. 111. Springer-Verlag, New York.
• 27: Willenborg, L. and de Waal, T. 2000. Elements of Statistical Disclosure. Lecture Notes in Statistics, 155. Springer-Verlag, New York.
• 28: Nan Zhang , Wei Zhao , Jianer Chen, Cardinality-based inference control in OLAP systems: an information theoretic approach, Proceedings of the 7th ACM international workshop on Data warehousing and OLAP, November 12-13, 2004, Washington, DC, USA [doi>10.1145/1031763.1031776]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications

General Terms:
Algorithms, Security

Keywords:
Additive data, sensitive information