Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

We investigate the subtle cues to user identity that may be exploited in attacks on the privacy of users in web search query logs. We study the application of simple classifiers to map a sequence of queries into the gender, age, and location of the user issuing the queries. We then show how these classifiers may be carefully combined at multiple granularities to map a sequence of queries into a set of candidate users that is 300-600 times smaller than random chance would allow. We show that this approach remains accurate even after removing personally identifiable information such as names/numbers or limiting the size of the query log.

We also present a new attack in which a real-world acquaintance of a user attempts to identify that user in a large query log, using personal information. We show that combinations of small pieces of information about terms a user would probably search for can be highly effective in identifying the sessions of that user.

We conclude that known schemes to release even heavily scrubbed query logs that contain session information have significant privacy risks.

REFERENCES

• 1: E. Adar. User 4XXXXX9: Anonymizing query logs. In Query Logs Workshop at the 16th WWW, 2007.
• 2: S. Argamon, M. Koppel, and G. Avneri. Routing documents according to style. In Proc. 1st Workshop on Innovative Information Systems, 1998.
• 3: S. Argamon, M. Koppel, J. Fine, and A. R. Shimoni. Gender, genre, and writing style in formal written texts. Text, 23(3):321--346, 2003.
• 4: Lars Backstrom , Cynthia Dwork , Jon Kleinberg, Wherefore art thou r3579x?: anonymized social networks, hidden patterns, and structural steganography, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada [doi>10.1145/1242572.1242598]
• 5: Dan Frankowski , Dan Cosley , Shilad Sen , Loren Terveen , John Riedl, You are what you say: privacy risks of public mentions, Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, August 06-11, 2006, Seattle, Washington, USA [doi>10.1145/1148170.1148267]
• 6: Luis Gravano , Vasileios Hatzivassiloglou , Richard Lichtenstein, Categorizing web queries according to geographical locality, Proceedings of the twelfth international conference on Information and knowledge management, November 03-08, 2003, New Orleans, LA, USA [doi>10.1145/956863.956925]
• 7: Jian Hu , Hua-Jun Zeng , Hua Li , Cheng Niu , Zheng Chen, Demographic prediction based on user's browsing behavior, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada [doi>10.1145/1242572.1242594]
• 8: Bernard J. Jansen , Amanda Spink , Tefko Saracevic, Real life, real users, and real needs: a study and analysis of user queries on the web, Information Processing and Management: an International Journal, v.36 n.2, p.207-227, Jan.1.2000 [doi>10.1016/S0306-4573(99)00056-4]
• 9: R. Jones, W. V. Zhang, P. Jhala, and B. Rey. Geographic intention and modification in web search. International Journal of Geographical Information Science, 2007.
• 10: Ravi Kumar , Jasmine Novak , Bo Pang , Andrew Tomkins, On anonymizing query logs via token-based hashing, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada [doi>10.1145/1242572.1242657]
• 11: F. Mosteller and D. Wallace. Inference and Disputed Authorship: The Federalist Papers. Addison-Wesley, 1964.
• 12: Jasmine Novak , Prabhakar Raghavan , Andrew Tomkins, Anti-aliasing on the web, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988678]
• 13: Pierangela Samarati , Latanya Sweeney, Generalizing data to provide anonymity when disclosing information (abstract), Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.188, June 01-04, 1998, Seattle, Washington, United States [doi>10.1145/275487.275508]
• 14: C. Silverstein, M. Henzinger, H. Marais, and M. Moricz. Analysis of a very large altavista query log. Technical Report 1998--014, Digital SRC, 1998.
• 15: Laura Mayfield Tomokiyo , Rosie Jones, You're not from 'round here, are you?: naive Bayes detection of non-native utterance text, Second meeting of the North American Chapter of the Association for Computational Linguistics on Language technologies 2001, p.1-8, June 01-07, 2001, Pittsburgh, Pennsylvania [doi>10.3115/1073336.1073367]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval

General Terms:
Algorithms, Experimentation, Measurement

Keywords:
k-anonymity, privacy, query log analysis