Detecting privacy leaks using corpus-based association rules

ABSTRACT

Detecting inferences in documents is critical for ensuring privacy when sharing information. In this paper, we propose a refined and practical model of inference detection using a reference corpus. Our model is inspired by association rule mining: inferences are based on word co-occurrences. Using the model and taking the Web as the reference corpus, we can find inferences and measure their strength through web-mining algorithms that leverage search engines such as Google or Yahoo!.

Our model also includes the important case of private corpora, to model inference detection in enterprise settings in which there is a large private document repository. We find inferences in private corpora by using analogues of our Web-mining algorithms, relying on an index for the corpus rather than a Web search engine.

We present results from two experiments. The first experiment demonstrates the performance of our techniques in identifying all the keywords that allow for inference of a particular topic (e.g. "HIV") with confidence above a certain threshold. The second experiment uses the public Enron e-mail dataset. We postulate a sensitive topic and use the Enron corpus and the Web together to find inferences for the topic.

These experiments demonstrate that our techniques are practical, and that our model of inference based on word co-occurrence is well-suited to efficient inference detection.

REFERENCES

• 1: Rakesh Agrawal , Heikki Mannila , Ramakrishnan Srikant , Hannu Toivonen , A. Inkeri Verkamo, Fast discovery of association rules, Advances in knowledge discovery and data mining, American Association for Artificial Intelligence, Menlo Park, CA, 1996
• 2: Rakesh Agrawal , Ramakrishnan Srikant, Fast Algorithms for Mining Association Rules in Large Databases, Proceedings of the 20th International Conference on Very Large Data Bases, p.487-499, September 12-15, 1994
• 3: M. Ahlers. Blueprints for terrorists? On the Web at http://www.cnn.com/2004/US/10/19/terror.nrc/index.html.
• 4: Apache Lucene project. On the Web at http://lucene.apache.org/.
• 5: Margherita Berardi , Michele Lapi , Pietro Leo , Corrado Loglisci, Mining generalized association rules on biomedical literature, Proceedings of the 18th international conference on Innovations in Applied Artificial Intelligence, p.500-509, June 22-24, 2005, Bari, Italy [doi>10.1007/11504894_68]
• 6: W. Broad. U. S. web archive is said to reveal a nuclear primer. On the Web at http://www.nytimes.com/2006/11/03/world/middleeast/03documents.html.
• 7: Philipp Cimiano , Steffen Staab, Learning by googling, ACM SIGKDD Explorations Newsletter, v.6 n.2, p.24-33, December 2004 [doi>10.1145/1046456.1046460]
• 8: Mike Dowman , Valentin Tablan , Hamish Cunningham , Borislav Popov, Web-assisted annotation, semantic indexing and search of television and radio news, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1060745.1060781]
• 9: Enron corpus. On the Web at http://www.cs.cmu.edu/~enron/.
• 10: 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]
• 11: Natalie S. Glance, Community search assistant, Proceedings of the 6th international conference on Intelligent user interfaces, p.91-96, January 14-17, 2001, Santa Fe, New Mexico, United States [doi>10.1145/359784.360293]
• 12: Health Privacy Project. On the Web at http://www.healthprivacy.org/.
• 13: Inboxer. On the Web at http://www.inboxer.com/.
• 14: Inboxer's Enron demonstration site. On the Web at http://www.enronemail.com/.
• 15: Łucja M. Iwańska , Stuart C. Shapiro, Natural language processing and knowledge representation: language for knowledge and knowledge for language, MIT Press, Cambridge, MA, 2000
• 16: D. P. Lopresti and A. L. Spitz. Information leakage through document redaction: attacks and countermeasures. In DRR, pages 183--190, 2005.
• 17: Christopher D. Manning , Hinrich Schütze, Foundations of statistical natural language processing, MIT Press, Cambridge, MA, 1999
• 18: Preslav Nakov , Marti Hearst, Using the web as an implicit training set: application to structural ambiguity resolution, Proceedings of the conference on Human Language Technology and Empirical Methods in Natural Language Processing, p.835-842, October 06-08, 2005, Vancouver, British Columbia, Canada [doi>10.3115/1220575.1220680]
• 19: Lisa Singh , Peter Scheuermann , Bin Chen, Generating association rules from semi-structured documents using an extended concept hierarchy, Proceedings of the sixth international conference on Information and knowledge management, p.193-200, November 10-14, 1997, Las Vegas, Nevada, United States [doi>10.1145/266714.266895]
• 20: Jessica Staddon , Philippe Golle , Bryce Zimny, Web-based inference detection, Proceedings of 16th USENIX Security Symposium on USENIX Security Symposium, p.1-16, August 06-10, 2007, Boston, MA
• 21: L. Sweeney. AI technologies to defeat identity theft vulnerabilities. In AAAI Spring Symposium on AI TEchnologies for Homeland Security, 2005.
• 22: N. Terry and L. Francis. Ensuring the privacy and confidentiality of electronic health records. Illinois Law Review, 2007(2).
• 23: Peter D. Turney, Mining the Web for Synonyms: PMI-IR versus LSA on TOEFL, Proceedings of the 12th European Conference on Machine Learning, p.491-502, September 05-07, 2001
• 24: Ke Wang , Yu He , Jiawei Han, Pushing Support Constraints Into Association Rules Mining, IEEE Transactions on Knowledge and Data Engineering, v.15 n.3, p.642-658, March 2003 [doi>10.1109/TKDE.2003.1198396]
• 25: Yahoo! Web Search API. On the Web at http://developer.yahoo.com/search/web/.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.7 Database Administration
          Subjects: Security, integrity, and protection

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.3 Deduction and Theorem Proving
          Subjects: Inference engines
      I.2.6 Learning
          Subjects: Knowledge acquisition

  K. Computing Milieux
  K.4 COMPUTERS AND SOCIETY
      K.4.1 Public Policy Issues
          Subjects: Privacy

General Terms:
Algorithms, Experimentation, Performance, Security

Keywords:
association rule mining, inference control, inference detection, search engine, web mining