Auditing disclosure by relevance ranking

ABSTRACT

Numerous widely publicized cases of theft and misuse of private information underscore the need for audit technology to identify the sources of unauthorized disclosure. We present an auditing methodology that ranks potential disclosure sources according to their proximity to the leaked records. Given a sensitive table that contains the disclosed data, our methodology prioritizes by relevance the past queries to the database that could have potentially been used to produce the sensitive table. We provide three conceptually different measures of proximity between the sensitive table and a query result. One measure is inspired by information retrieval in text processing, another is based on statistical record linkage, and the third computes the derivation probability of the sensitive table in a tree-based generative model. We also analyze the characteristics of the three measures and the corresponding ranking algorithms.

REFERENCES

• 1: R. Agrawal, R. Bayardo, C. Faloutsos, J. Kiernan, R. Rantzau, and R. Srikant. Auditing compliance using a hippocratic database. In 30th Int'l Conf. on Very Large Data Bases, Toronto, Canada, August 2004.
• 2: Rakesh Agrawal , Peter J. Haas , Jerry Kiernan, Watermarking relational data: framework, algorithms and analysis, The VLDB Journal — The International Journal on Very Large Data Bases, v.12 n.2, p.157-169, August 2003 [doi>10.1007/s00778-003-0097-x]
• 3: Australian privacy act of 1998, 1998. http://www.privacy.gov.au/ACT/privacyact/.
• 4: T. R. Belin and D. B. Rubin. A method for calibrating false match rates in record linkage. Journal of the American Statistical Assocation, 90(430):694--707, June 1995.
• 5: Personal information protection and electronic documents act, second session, thirty-sixth parliament, 48-49 elizabeth ii, 1999-2000, statutes of canada, 2000.
• 6: M. Cochinwala, S. Dalal, A. K. Elmagarmid, and V. S. Verykios. Record matching: Past, present and future. Technical Report CSD-TR #01-013, Department of Computer Sciences, Purdue University, July 2001.
• 7: A. P. Dempster, N. M. Laird, and D. B. Rubin. Maximum likelihood from incomplete data via the EM algorithm. Journal of the Royal Statistical Society, 39(1):1--38, 1977.
• 8: European Union Directive on Data Protection, Official Journal of the European Communities, 1995.
• 9: I. P. Fellegi and A. B. Sunter. A theory for record linkage. Journal of the American Statistical Association, 64:1183--1210, December 1969.
• 10: L. A. Goodman. Exploratory latent structure analysis using both identifiable and unidentifiable models. Biometrika, 61:215--231, 1974.
• 11: R. L. Graham, M. Grötschel, and L. Lovász, editors. Handbook of Combinatorics, volume 2, chapter 21, page 1024. Elsevier Science B. V., 1995.
• 12: L. Gu, R. Baxter, D. Vickers, and C. Rainsford. Record linkage: Current practice and future directions. Technical Report 03/83, CSIRO Mathematical and Information Sciences, GPO Box664, Canberra 2601, Australia, April 2003.
• 13: H. O. Hartley. Maximum likelihood estimation from incomplete data. Biometrics, 14:174--194, 1958.
• 14: Health insurance portability and accountability act of 1996, united states public law 104-191, 1996. http://www.hhs.gov/ocr/hipaa.
• 15: M. A. Jaro. Advances in record linkage methodology as applied to matching the 1985 census of Tampa, Florida. Journal of the American Statistical Association, 84:414--420, 1989.
• 16: H. W. Kuhn. The hungarian method for the assignment problem. Naval Research Logistics Quaterly, 2:83--97, 1955.
• 17: M. D. Larsen and D. B. Rubin. Iterative automated record linkage using mixture models. Journal of the American Statistical Association, 96:32--41, 2001.
• 18: Yingjiu Li , Vipin Swarup , Sushil Jajodia, Fingerprinting Relational Databases: Schemes and Specialties, IEEE Transactions on Dependable and Secure Computing, v.2 n.1, p.34-45, January 2005 [doi>10.1109/TDSC.2005.12]
• 19: G. McLachlan and T. Krishnan. The EM Algorithmand Extensions. Wiley-Interscience, November 1996.
• 20: G. McLachlan and D. Peel. Finite Mixture Models. Wiley-Interscience, October 2000.
• 21: Gerome Miklau , Dan Suciu, A formal analysis of information disclosure in data exchange, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007633]
• 22: J. Munkres. Algorithms for the assignment and transportation problems. Journal of the Society of Industrial and Applied Mathematics, 5(1):32--38, March 1957.
• 23: A. Nanda and D. K. Burleson. Oracle Privacy Security Auditing. Rampant, 2003.
• 24: President's Information Technology Advisory Committee. Revolutionizing health care through information technology, June 2004.
• 25: J. Rissanen. Stochastic Complexity in Statistical Inquiry. World Scientific Publ. Co., 1989.
• 26: S. Ruggles, M. Sobek, T. Alexander, C. A. Fitch, R. Goeken, P. K. Hall, M. King, and C. Ronnander. Integrated public use microdata series: Version 3.0, 2004. Machine-readable database.
• 27: V. N. Sachkov. Combinatorial Methods in Discrete Mathematics, chapter 4.2. Cambridge University Press, 1996. Result found in the 2-nd edition, in Russian, 2004.
• 28: G. Salton. Automatic Text Processing: The Transformation, Analysis, and Retrieval of Information by Computer. Addison-Wesley, New York,1989.
• 29: Wikipedia.org. Hungarian algorithm, March 2006.
• 30: W. E. Winkler. Matching and record linkage. In B. G. Cox, editor, Business Survey Methods, pages 355--384. Wiley, 1995.

INDEX TERMS

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

General Terms:
Algorithms, Security

Keywords:
derivation probability, hippocratic database, information retrieval, privacy, record linkage