Bloom Cookies: Web Search Personalization without User Tracking

论文阅读笔记

课程 计算机系统安全分析

这篇文章出自NDSS2015，主要讨论了一种保护用户隐私信息在搜索引擎个性化过程中不被获取的技术。

• 出处：NDSS2015
• 作者：Nitesh Mor, Oriana Riva, Suman Nath, John Kubiatowicz
• 单位：加利福尼亚大学伯克利分校，微软研究院

Abstract & Introduction

搜索引擎已经成为我们日常生活中使用最多的WEB应用，然而在日常使用搜索引擎的过程中，会有很多由于检索关键词的二义性而导致的搜索结果的歧义。例如搜索“rock”，那么搜索引擎可能返回“石头”的搜索结果，也可能返回“滚石乐队”的搜索结果。

为了消除这种歧义性，给用户更好的企业，现在主流的搜索引擎都会根据用户过去的搜索记录来对搜索结果进行筛选和重新排序，将用户最可能想要的结果排在最前面。但是在进行搜索结果个性化化之前需要记录和获取用户的搜索日志，里面可能包含用户的一些个人隐私信息，比如最近访问过的部分网页。怎么在做到搜索结果个性化的同时又能保证用户的隐私不被侵犯是这篇文章主要解决的问题。

State Of The Art

目前对于这个问题有两种主要解决方法：

1. 用户个性化操作完全交给浏览器等客户端，同时客户端保存用户的搜索日志。
2. 在客户端生成包含噪声和经过特殊处理的用户属性文件作为搜索引擎进行搜索结果个性化的依据。

但是这两种方法的可行性都不高。首先第一种方法可能会造成大量的网络数据传输而产生网络拥堵，况且搜索引擎提供商不能容忍自己的个性化算法被共开并放在客户端。第二种方法是现有最好的方法，但仍有很多不足之处，比如不能解决“用户链接”的安全隐患，而且需要以来一个受信任的第三方噪声库。

Solution

在这种情况下，作者提出了一种新型的方法来解决这个问题，作者提出了一种叫做Bloom Cookies的数据结构，用它来编码用户的搜索记录。这种方法实际上是上述第二种现有解决方案的改进。

Bloom Cookies

Bloom Cookies实际上是一个固定长度的比特串，这个比特串每一位是一个0或1的值。下文假设这个比特串的长度为m。

其他部件

要生成Bloom Cookies这个比特串，还需要k个哈希函数。k的取值由其他一些参数决定：

链接编码

将一个链接编码进Bloom Cookies的方法如下：

1. 对一个链接的url使用k个哈希函数分别进行哈希操作得到k个哈希值。
2. 对这k个哈希值进行一下迭代：如果Bloom Cookies的第i个哈希值模m所对应的位值不为1，则把它置为1。
3. 重复步骤1、2直到所有的url全部迭代完毕

检测是否被编码

对于一个给定的链接，判断其是否被编码进Bloom Cookies的方法是：

1. 对这个链接的url使用k个哈希函数分别进行哈希操作得到k个哈希值。
2. 检查这k个哈希值模m后的结果所对应Bloom Cookies的位是否都为1。若是，则判断此链接地址被编码进Bloom Cookies，否则没有被编码。

Limitation

• 实验所用数据集不够大
• 缺乏实际的用户反馈
• 用户存在周期设置得比较短，没有对长期存在用户进行实验
• 针对应用的泛化能力比较弱
• 实验没有针对多角色服务器进行

Conclusion

主要贡献

• 第一次对现存的用户信息噪声添加、泛化操作的方法进行系统性的分析。
• 提出了Bloom Cookies这样一种数据结构。
• 提出了一种端用户编码Bloom Cookies的方法。