論文鏈接：http://randomwalker.info/publications/browsing-history-deanonymization.pdf

關於作者

前三位作者都來自斯坦福大學，第四位作者 Arvind Narayanan（現為普林斯頓大學助理教授），是該研究的絕對核心。雖然 Narayanan 當時仍然在德克薩斯大學奧斯汀分校攻讀博士學位，但是他和他的導師 Vitaly Shimatikov（現康奈爾大學科技校區教授）在Netflix 舉辦的「Netflix 大獎賽」中（該比賽旨在尋找更好的協同過濾演算法 [1]），證明了對 Netflix 提供的匿名用戶信息進行「去匿名化」的可能性。因此，毫無意外地，熱衷於去匿名化技術的 Narayanan 博士，這一次又準備好展示是否可能對 web 瀏覽數據和社交文件的鏈接進行去匿名化處理。

論文亮點

1. 研究問題陳述

在本文中，作者提出了一個問題：是否可能對社交網路中的瀏覽歷史進行去匿名化呢？

令人生畏的是，答案是肯定的！而且「去識別化」之後的瀏覽數據仍然能夠反推出產生瀏覽歷史的原始文件。他們的研究還提出了應用層的匿名化之所以是 Tor（洋蔥路由）的阿基琉斯之踵（即要害）的另一個原因，這些現有的匿名系統本應該保護用戶的身份不被泄露。

他們的去匿名化方法基於以下的觀察：我們通常只在社交網路中關注一組與眾不同的用戶/賬號，並且 web 瀏覽歷史包含我們點擊過的鏈接和訪問過的頁面。通常情況下，我們更有可能點擊被我們所關注的用戶/賬號所分享的頁面。

我們點擊過的鏈接、關注的用戶/賬號會泄露我們的身份。

本文作者通過創建一個用戶瀏覽行為模型將這個去匿名化的問題形式化，接著推導出對於社交網路中個人資料的最大似然估計。

2. 本文貢獻

作者聲明他們已經做出了以下三個主要的貢獻：

2.1 去匿名化策略

在三個假設條件下，建立一個 web 瀏覽的程式化模型：

（1）一個用戶的 web 瀏覽歷史由一個獨立同分布的 URL 序列組成，我們將其表示為 H1, ... , Hn，其中 Ht 代表用戶 i 訪問的第 t 個 URL。

（2）每個用戶 i 有一組個性化的推薦鏈接 Ri，即在 feed 流中出現的鏈接的推薦集合，它是由用戶 i 已關注的人發布的。

（3）如果一個鏈接在用戶的推薦集合中出現，那麼該用戶就更有可能訪問它。並且一個對於用戶 i 來說特定的乘法因子 ri 描述了對於這個推薦集合的響應能力。

因此，用戶 i 的瀏覽行為由這個推薦集合 Ri（一組在用戶的 feed 中存在的鏈接）和推薦因子 ri 控制。

定理 1 ：以下是一個用戶瀏覽行為模型的形式化定義。

給定一個匿名瀏覽歷史 Ht，以及一組帶有推薦集合 C = {R1, ... , Rk} 的候選用戶，由此推導出最大似然估計 R^ 和 r^。並且 R^ 是最有可能生成給定的瀏覽歷史的候選者。

兩個可選的候選者排序策略

為了提供關於提出的最大似然估計策略（該策略試圖將給定的瀏覽歷史和候選用戶中最有可能的推薦集合關聯起來）的直觀思路，他們比較了最大似然估計和另外兩種可選方案，即文中所說的：交集大小方法（Intersection Size method）和 Jaccard 方法。

（1）交集大小方法

交集大小方法將一個給定的瀏覽歷史 H 賦給推薦集合 R，該集合包含了給定瀏覽歷史中最多的 URL。然而，這種方法可能偏向於選擇較大的推薦集合，即推薦集越大的話，它越有可能擁有給定瀏覽歷史匯總最多的鏈接。

找到使得下式最大的候選者集合

（2）Jaccard 方法

為了調整推薦集合的大小，Jaccard 方法將一個給定的瀏覽歷史 H 和一個推薦集合 R 相關聯，這個推薦集合 R 和瀏覽歷史 H 有最大的 Jaccard 相似度，記作：

正如我們在很多情況下所看到的那樣，這個推薦集合 R 往往比瀏覽歷史 H 規模大，換句話說，在用戶的 feed 中的鏈接通常都比用戶實際上點擊過的瀏覽歷史中的鏈接多。

因此，最大化 Jaccard 相似度就約等於找到了能夠最大化下式的候選者集合：

圖 3 說明了在給定瀏覽歷史中的 URL 的數量超過 10 的時候，我們將三種策略的準確率進行對比，發現定理 1 的最大似然估計策略的性能優於交集大小方法和 Jaccard 方法。

圖 3: 三種候選者排序方法在合成的瀏覽歷史上的去匿名化準確率：定理 1 的最大似然估計、在候選者的 feed 中出現的歷史鏈接數（交集大小方法）、Jaccard 相似度方法。

而圖 4 則描繪了當瀏覽歷史充滿雜訊時最大似然估計的準確率，即瀏覽歷史中混入了一個確定比例的形如「朋友的朋友」的鏈接。在這種設定下，我們提出的最大似然估計方法的準確率仍然較高。

圖 4： 在不同的雜訊水平下，我們在合成的瀏覽歷史上獲得的去匿名化準確率。

2.2 去匿名化系統設計

實時去匿名化系統

圖2描繪了我們提出的這個系統的架構。首先，該系統從 Twitter 上接受一個匿名瀏覽歷史，然後搜索包含接收到的歷史中任意鏈接的所有 tweet（用戶的帖子）。搜索結果會被發送給負責尋找搜索結果中所找到博主的所有粉絲的爬蟲。然後，我們會使用去匿名化策略計算每一個粉絲產生接收到的瀏覽歷史的最大似然。

為了收集網路數據，即粉絲列表，我們採取了一種貪婪的緩存策略：後台監聽器監聽推文（tweet）的數據流，並選擇那些擁有 1 萬到 10 萬粉絲的用戶。接著，將這些用戶添加到網路緩存中，並且通過實時去匿名化過程爬取數據。因此，我們提出的去匿名化策略同時依賴於緩存的（或預取的）網路數據和實時信息。

圖 2：web 瀏覽歷史的實時去匿名化系統架構圖。

2.3 模擬和實驗

作者在模擬的瀏覽歷史數據上評估去匿名化策略，並且證明了給定一個由超過 30 個 Twitter 鏈接組成的瀏覽歷史，我們可能在超過 50%的情況下推斷出相應的用戶畫像。

除了模擬之外，他們還對大約 400 位用戶貢獻的真實世界瀏覽數據進行了實驗，其中超過 70% 的用戶都被準確識別。作者進一步指出，許多網站都嵌入了在線追蹤器，旨在識別具有特定瀏覽歷史的用戶，一邊進行去匿名化攻擊，這使用戶的隱私受到威脅。

作者指出，他們提出的去匿名化策略可用於「任意類型的事務性數據，並且對帶雜訊的觀測值有很強的魯棒性，可以推廣到大範圍的早期去匿名化攻擊」。此外，他們成功地從超過 3 億候選者中識別出正確的 Twitter 信息。據作者所知，這是目前最大規模的去匿名化挖掘案例。

圖 5 展示了作者進行的在線去匿名化實驗的三張截圖。用戶可以上傳他/她的瀏覽歷史進行去匿名化，並且作者所提出的最大似然估計系統會返回瀏覽歷史中有匹配的鏈接的候選用戶的測試結果。

圖 5：在線實驗的截圖。

相關工作

在去匿名化領域有大量的文獻，作者發現了「連鎖攻擊」，即根據用戶行為證明其獨特性/特異性，和他們的研究最為相似。

許多類型的數據容易受到電影評論歷史的事物記錄 [2]、位置軌跡 [3,4]、信用卡元數據 [5]，以及寫作風格 [6] 等的連瑣攻擊。

作者發現，之前唯一研究瀏覽歷史獨特性的研究是 Olenjnik 等人 [7] 所做的，這項研究被記錄在《Why Johnny can』t browse in peace: On the uniqueness of web browsing history patterns》一文中。當只有 50 個鏈接時，他們可以在擁有約 370,000 名用戶的數據集中識別出 42%的用戶身份/指紋，並且這種用戶的「行為指紋」在一段時間內是穩定的。

評論

作者十分慷慨地提醒我們：「只要每個用戶的訂閱列表可以被推斷、內容是公開的、並且用戶訪問的（web）站點上的鏈接足夠多，任何社交媒體網站可以被用於這樣的（去匿名化）攻擊。」

對於我們來說，事先知道我們在社交網路上分享的哪些內容是可以推斷或者去匿名化的是十分困難的。而且在當下的信息時代，僅僅因為潛在的攻擊而不去點擊鏈接也是不可能的......但是有一件事，也可能是我們唯一能做的一件保護我們的隱私免於侵害的事，就是通過編輯我們的社交網路隱私設置保持私人生活「隱私化」：在向公眾發布個人信息之前三思，以防被躲在暗處的惡意攻擊者識別出身份。你給出的每一個贊，每條你留下的評論，甚至是你在社交網路上的關注列表，都可能揭示出你的身份。

保持低調可能是一種美德，在虛擬世界中更是如此，這全是為了安全！

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！