差分隱私和現(xiàn)有的隱私保護(hù)方法相結(jié)合：從用戶群體中學(xué)習(xí)的系統(tǒng)架構(gòu)詳解

了解人們?nèi)绾问褂盟麄兊脑O(shè)備通常有助于改善用戶體驗(yàn)。但是，若想得到能洞察用戶行為的數(shù)據(jù)（例如用戶在鍵盤上打了什么字、訪問(wèn)了什么網(wǎng)站），可能會(huì)侵犯他們的隱私。

近日，蘋果公司開發(fā)了一個(gè)系統(tǒng)架構(gòu)，利用本地化差分隱私（local differential privacy）并結(jié)合現(xiàn)有的保護(hù)隱私的最佳方法，實(shí)現(xiàn)規(guī)模化學(xué)習(xí)（learning at scale）。研究人員設(shè)計(jì)了高效可擴(kuò)展的本地化差分隱私算法，經(jīng)過(guò)嚴(yán)謹(jǐn)?shù)姆治龃_定了應(yīng)用程序、隱私、服務(wù)器計(jì)算能力和設(shè)備帶寬四個(gè)要素的重要性應(yīng)如何分配。平衡這些因素將有助于成功地部署本地差分隱私。這一部署將覆蓋數(shù)以億計(jì)的用戶，例如在Safari中跟蹤最受歡迎的emoji、最常用的健康數(shù)據(jù)類型以及媒體播放偏好。后臺(tái)回復(fù)“dp”可查看完整版論文。

項(xiàng)目介紹

深入了解用戶的整體行為對(duì)于改善用戶體驗(yàn)至關(guān)重要，但所需的數(shù)據(jù)較為敏感私密，公司必須予以保密。除此之外，利用這些數(shù)據(jù)部署學(xué)習(xí)系統(tǒng)還必須考慮資源開銷、計(jì)算成本和通信成本。在本文中，作者概述了將差分隱私和現(xiàn)有的隱私保護(hù)方法相結(jié)合，然后從用戶群體中學(xué)習(xí)的系統(tǒng)架構(gòu)。

經(jīng)過(guò)嚴(yán)格的數(shù)學(xué)證明，差分隱私是目前最強(qiáng)的隱私保障法之一。它的原理在于用仔細(xì)調(diào)整過(guò)的噪聲掩蓋用戶的數(shù)據(jù)。當(dāng)許多人提交數(shù)據(jù)時(shí)，增加到其中的噪聲達(dá)到平衡，并產(chǎn)生有意義的信息。

在差分隱私框架內(nèi)，有兩種設(shè)定：中心（central）和本地（local）。在這套系統(tǒng)中，蘋果不收集中心化差別隱私所需的服務(wù)器上的原始數(shù)據(jù)，而是采用本地化差別隱私，這種形式更加可靠。本地差分隱私在數(shù)據(jù)被發(fā)送前就做了隨機(jī)處理，所以服務(wù)器無(wú)法看到或接收到原始數(shù)據(jù)。

該系統(tǒng)非常透明，用戶可以自愿選擇是否加入。若用戶不同意上報(bào)使用信息，則不會(huì)記錄或傳輸他們的私人數(shù)據(jù)。通過(guò)本地化的差分隱私，用戶的設(shè)備依據(jù)時(shí)間等級(jí)進(jìn)行加密。另外，該系統(tǒng)還限制上傳隱私事件的數(shù)量。將信息傳輸?shù)椒?wù)器每天只有一次，而且是在加密通道上進(jìn)行，沒(méi)有用戶ID。用戶信息最終會(huì)到達(dá)一個(gè)訪問(wèn)受限的服務(wù)器，其中沒(méi)有IP標(biāo)識(shí)符，也沒(méi)有與其他記錄相關(guān)聯(lián)的信息。所以，我們無(wú)法區(qū)分一個(gè)emoji和另一個(gè)Safari網(wǎng)頁(yè)記錄是否來(lái)自同一個(gè)用戶，也就是說(shuō)這些信息是完全保密的。這些記錄經(jīng)過(guò)處理后加入統(tǒng)計(jì)數(shù)據(jù)中，然后再由蘋果內(nèi)部相關(guān)團(tuán)隊(duì)進(jìn)行分析。

同時(shí)，蘋果的研究人員還在估計(jì)各種記錄的頻率，例如emoji和網(wǎng)絡(luò)域名。他們有兩個(gè)想法：從已知的所有類別的記錄中生成直方圖，或者自己創(chuàng)造一個(gè)能表現(xiàn)出數(shù)據(jù)集中出現(xiàn)頻率最多的圖表。

系統(tǒng)架構(gòu)

該系統(tǒng)架構(gòu)由設(shè)備端和服務(wù)端的數(shù)據(jù)組成。在設(shè)備上，原始數(shù)據(jù)在加密階段分別進(jìn)行處理。受限訪問(wèn)的服務(wù)器在對(duì)數(shù)據(jù)處理后進(jìn)一步將其分為數(shù)據(jù)接入和數(shù)據(jù)聚合階段。下面就為大家詳細(xì)介紹每一個(gè)階段。

信息加密（Privatization）

用戶可在macOS或iOS的“系統(tǒng)偏好設(shè)置”里選擇是否同意共享個(gè)人記錄以供分析。對(duì)于不愿加入的用戶，系統(tǒng)將不會(huì)開啟服務(wù)。而對(duì)于愿意使用這項(xiàng)功能的用戶，蘋果內(nèi)部為每個(gè)用戶行為都設(shè)置了隱私參數(shù)?。

蘋果還對(duì)每天傳輸?shù)拿宽?xiàng)記錄設(shè)置了數(shù)量限制。而對(duì)于隱私參數(shù)?的選擇，則是基于每個(gè)記錄的基礎(chǔ)數(shù)據(jù)集的隱私特性。這些值與其他研究差分隱私的項(xiàng)目提出的參數(shù)是一致的。而且，由于hash沖突，下面的算法給用戶提供了進(jìn)一步的否認(rèn)條件。除了上述的方法，蘋果還會(huì)刪除用戶的ID和IP地址來(lái)進(jìn)一步加強(qiáng)隱私，服務(wù)器上所產(chǎn)生的的用戶ID和IP地址是分隔開的，所以多個(gè)記錄之間沒(méi)有關(guān)聯(lián)。

無(wú)論何時(shí)用戶使用了設(shè)備，數(shù)據(jù)會(huì)立即通過(guò)有特殊參數(shù)?的本地差分隱私進(jìn)行加密，并使用數(shù)據(jù)保護(hù)（data protection）臨時(shí)儲(chǔ)存在設(shè)備上，而不是立即傳輸?shù)椒?wù)器上。

系統(tǒng)會(huì)根據(jù)設(shè)備的情況進(jìn)行延遲，之后會(huì)隨機(jī)抽取不同的私人記錄，并將采樣記錄發(fā)送給服務(wù)器。這些記錄不包括設(shè)備ID或該行為發(fā)生的時(shí)間。設(shè)備和服務(wù)器之間的通信使用TLS進(jìn)行加密。

加密過(guò)程

在iOS中打開“設(shè)置”>“隱私”>“分析”>“分析數(shù)據(jù)”后可看到“差分隱私”（DifferentialPrivacy）的入口。在macOS上，這些記錄在“關(guān)于本機(jī)”的“系統(tǒng)報(bào)告”中可見(jiàn)。下圖是算法對(duì)最受歡迎的emoji使用情況的樣本記錄，記錄所涉及的算法和參數(shù)在下文會(huì)有體現(xiàn)。

加密記錄的樣本報(bào)告

數(shù)據(jù)接入和聚合

在數(shù)據(jù)接入之前，加密記錄會(huì)刪除掉IP地址，然后數(shù)據(jù)庫(kù)收集所有用戶數(shù)據(jù)后進(jìn)行批量處理。這一過(guò)程將刪除元數(shù)據(jù)，例如記錄發(fā)生的時(shí)間，并且根據(jù)記錄情況把它們分類。在將結(jié)果輸入到下一階段前，數(shù)據(jù)庫(kù)也會(huì)隨機(jī)對(duì)每個(gè)用戶行為記錄進(jìn)行排序。

聚合器收到來(lái)自數(shù)據(jù)庫(kù)的記錄后，根據(jù)算法為每個(gè)使用記錄生成個(gè)性化的直方圖。計(jì)算統(tǒng)計(jì)數(shù)據(jù)時(shí)，無(wú)需合并來(lái)自多個(gè)記錄的數(shù)據(jù)。在這些直方圖中，只有高于規(guī)定閾值T的域名才算入其中。

算法

下面就為大家介紹三種本地化差分隱私算法。

1.Private Count Mean Sketch（CMS）

Private Count Mean Sketch（CMS）算法聚合了設(shè)備提交的記錄，并在域名類別中輸出數(shù)量的直方圖，同時(shí)保留本地化差分隱私。這一過(guò)程分為兩個(gè)階段：客戶端處理和服務(wù)器端聚合。

舉個(gè)例子吧，假設(shè)一名用戶訪問(wèn)了 www.example.com 這個(gè)網(wǎng)站?？蛻舳怂惴◤囊唤M散列函數(shù)（hash function）{h1，h2，h3，…，hk}中隨機(jī)抽取一個(gè)，假設(shè)抽到了h2，然后用它將上述網(wǎng)站域名以m的大小編碼，即h2(www.example.com)=31。該編碼被寫成大小為m的one-hot向量，其中第31位被設(shè)置為1。為了確保隱私的差分性，one-hot向量的每一位獨(dú)立地以概率翻轉(zhuǎn)，其中?是隱私參數(shù)，它構(gòu)成了私有化的向量。這個(gè)向量和被選擇的散列函數(shù)一起被輸送至服務(wù)器。

服務(wù)器端的算法通過(guò)聚合加密向量組成了sketch矩陣M。該矩陣有k行、m列，每一行都代表一個(gè)散列函數(shù)，每一列代表從客戶端傳輸來(lái)的矢量大小。

當(dāng)記錄到達(dá)服務(wù)器時(shí)，算法將加密過(guò)的矢量添加到第j行的矢量，其中j是設(shè)備采樣的散列函數(shù)的指數(shù)。然后適當(dāng)?shù)卣{(diào)整m的值，以便每行都能為每個(gè)類別進(jìn)行無(wú)差別的頻率計(jì)算。

為了計(jì)算 www.example.com 的頻率，該算法通過(guò)讀取每個(gè)j行的M，然后計(jì)算這些結(jié)果的平均值。在原始論文中有詳細(xì)的分析過(guò)程。

2.Private Hadamard Count Mean Sketch（HCMS）

在完整版論文中，作者討論了如何通過(guò)增加設(shè)備帶寬讓CMS里的計(jì)算更精確。但是，這就增加了用戶的傳輸成本。蘋果希望在降低傳輸成本的同時(shí)把對(duì)準(zhǔn)確性的影響降到最小，于是就有了Private Hadamard Count Mean Sketch算法（HCMS），其優(yōu)點(diǎn)是設(shè)備可以以極小的精度損失進(jìn)行傳輸。

依然用上面的來(lái)舉例。與CMS類似，客戶端同樣是從一組散列函數(shù){h1，h2，h3，…，hk}中隨機(jī)抽取一個(gè)，假設(shè)抽到了h3。然后有h3(www.example.com)=42。編碼被寫成v=(0,0,…,0,1,0,…,0,0)的one-hot向量，這里第42位設(shè)置為1。因?yàn)槲覀冎幌雮鬏斠晃恍畔?，所以一個(gè)簡(jiǎn)單的方法就是從向量中抽樣并發(fā)送一個(gè)隨機(jī)坐標(biāo)。但是這可能導(dǎo)致結(jié)果直方圖的錯(cuò)誤或變化。為了減少誤差，研究人員用Hadamard將v進(jìn)行轉(zhuǎn)化，即v’=Hv=(+1,-1,…,+1)。同樣，為了確保隱私性，向量中的每一位以的概率翻轉(zhuǎn)。下圖展示了這一過(guò)程。

Hadamard Count Mean Sketch中客戶端的算法

同樣，服務(wù)端的算法與CMS的大致相同。

Hadamard Count Mean Sketch中服務(wù)端的算法

3.Private Sequence Fragment Puzzle（SFP）

上述兩種算法都假設(shè)有已知的域名集合，服務(wù)器可根據(jù)它來(lái)列舉樣本，以確定相應(yīng)的計(jì)數(shù)。

然而在某些情況下，一些域名非常大，由于計(jì)算能力有限無(wú)法全部列舉。例如，當(dāng)研究人員在研究常用單詞時(shí)，即使限制只能輸入10位區(qū)分大小寫的英文單詞，服務(wù)器也要進(jìn)行至少5210次循環(huán)。

所以，蘋果開發(fā)了一種名為Sequence Fragment Puzzle（SFP）的算法，并將其用于發(fā)現(xiàn)新單詞的任務(wù)中。由于一個(gè)流行字符串的子字符串使用也很頻繁，所以研究人員利用這一點(diǎn)，用客戶端的CMS算法對(duì)打出的字進(jìn)行加密。

成果

通過(guò)這三種新穎的算法，蘋果在提升用戶體驗(yàn)方面有了很大的收獲。以下是三個(gè)典型案例：

發(fā)現(xiàn)流行的emoji

emoji是聊天中必不可少的要素，蘋果公司想要知道用戶最常用的emoji都有哪些，以及地區(qū)的相對(duì)分布。于是，他們?cè)阪I盤語(yǔ)言環(huán)境中部署了算法。CMS的中的參數(shù)設(shè)置為：m=1024，k=65536，?=4，本地emoji庫(kù)中含有2600個(gè)emoji。

數(shù)據(jù)顯示，鍵盤設(shè)置不同，emoji使用也有差異。下圖是英文和法語(yǔ)兩個(gè)語(yǔ)言環(huán)境下的emoji使用情況。根據(jù)這一結(jié)果，蘋果可以對(duì)emoji的快捷輸入做本地化調(diào)整。

英法兩種鍵盤下人們使用emoji的區(qū)別

找到Safari中占用大量?jī)?nèi)存的網(wǎng)站

有些網(wǎng)站真的是非常消耗資源，蘋果公司想找到這些網(wǎng)站，以優(yōu)化用戶體驗(yàn)。他們的目標(biāo)有兩類：瀏覽時(shí)占用大量?jī)?nèi)存的以及大量占用CPU拖慢速度的。在iOS11和manOS High Sierra中，Safari可以自動(dòng)檢測(cè)到這些域名，并通過(guò)差分隱私上報(bào)這些域名。

利用算法，研究人員發(fā)現(xiàn)，最常見(jiàn)的需要消耗大量資源的網(wǎng)站有視頻網(wǎng)站、購(gòu)物網(wǎng)站和新聞網(wǎng)站。

擴(kuò)充詞匯庫(kù)

為了優(yōu)化“自動(dòng)糾錯(cuò)”功能，蘋果不斷地尋找詞庫(kù)中沒(méi)有的詞語(yǔ)。這里就用到了上面說(shuō)的SFP算法。

該算法不僅能用在英語(yǔ)環(huán)境中，還能用于法語(yǔ)和西班牙語(yǔ)。拿英語(yǔ)來(lái)說(shuō)吧，算法學(xué)習(xí)到的新單詞可以被分為以下幾類：

縮寫：wyd（what you doing），wbu（what about you），idc（I don’t care）；

習(xí)慣表達(dá)：bruh（bro），hun（honey），bae（baby），tryna（trying to）；

流行語(yǔ)：Mayweather，McGregor，Despacito，Moana，Leia；

外文詞匯：dia，queso，aqui，jai…

蘋果正是利用這些數(shù)據(jù)不斷更新在線詞典，改善鍵盤體驗(yàn)。

他們還發(fā)現(xiàn)，現(xiàn)在很多人在打字時(shí)都會(huì)省去結(jié)尾的“e”或者“w”，比如lov（love），th（the）或者kno（know）。所以如果用戶不小心選擇了第一個(gè)預(yù)測(cè)詞語(yǔ)，也就是你目前所打出來(lái)的所有字符，那么系統(tǒng)會(huì)自動(dòng)在單詞后面添加一個(gè)空格，而不是自動(dòng)替換成你想要輸入的那個(gè)單詞。這一功能正是本地化差分隱私算法帶來(lái)的。

這篇文章介紹了蘋果公司為改善用戶體驗(yàn)，同時(shí)保護(hù)用戶隱私推出的一種新穎的學(xué)習(xí)系統(tǒng)架構(gòu)，將本地化差分隱私算法覆蓋到各個(gè)使用層面。同時(shí)還提出了三種獨(dú)特的算法——CMS、HCMS和SFP。這些工具幫助公司看到在不同語(yǔ)言環(huán)境下人們使用emoji的差異，并且搜索當(dāng)下最流行的詞語(yǔ)，促進(jìn)他們改善軟件的體驗(yàn)。

研究人員希望這一項(xiàng)目能夠彌合隱私理論與實(shí)踐之間的差距，同時(shí)他們相信這一工作將繼續(xù)推進(jìn)大規(guī)模學(xué)習(xí)問(wèn)題的研究，同時(shí)進(jìn)一步增強(qiáng)用戶隱私保護(hù)。