「圖隱私攻擊與防御技術」最新2022研究綜述

來源：專知

摘要
如今，圖數(shù)據(jù)已經被廣泛地應用于現(xiàn)實生活與科學研究當中，有巨大的使用和研究價值. 但與此同時，針對圖數(shù)據(jù)的收集與發(fā)布中也存在巨大的隱私風險。如何在保護圖隱私的同時，發(fā)布與收集可用圖數(shù)據(jù)，是目前個人、企業(yè)、政府等面臨的重大挑戰(zhàn). 本文首先從隱私信息所包含的內容、不同的隱私泄露場景，以及敵手模型三個方 面深入地剖析了圖數(shù)據(jù)在使用中存在的隱私風險，然后重點從攻擊和防御兩個角度展開介紹. 針對攻擊而言，本文分析了當前可行的圖數(shù)據(jù)隱私攻擊與攻擊量化算法及其算法原理。針對防御而言，本文總結了簡單匿名、圖修改、 聚類，以及差分隱私四種圖數(shù)據(jù)隱私防御技術；分析了集中與分布兩種數(shù)據(jù)存儲場景下，不同類型圖數(shù)據(jù)使用的各類隱私防御算法，以及數(shù)據(jù)隱私性與可用性度量方法。最后本文綜合已有的研究成果，指出了圖數(shù)據(jù)上隱私保護研究當前存在的問題、面臨的挑戰(zhàn),及未來的研究方向。

http://cjc.ict.ac.cn/online/onlinepaper/002-%E5%88%98%E5%AE%87%E6%B6%B5-H-2022425163952.pdf

引言

圖數(shù)據(jù)目前已被廣泛應用于生活中的各個領域。相較于列表等其他數(shù)據(jù)類型，圖數(shù)據(jù)具有更強的表達能力：除通過結點表征實體屬性信息外，還可以通過邊清晰地表達結點實體間的鏈接關系，因此 被普遍應用于現(xiàn)實生活與科學研究中［1］。典型的圖數(shù)據(jù)包括社交網絡、通訊網絡、移動軌跡、傳染病與醫(yī)療數(shù)據(jù)、合作網絡、引用網絡、交易信息網絡、自治系統(tǒng)數(shù)據(jù)及其他拓撲圖等，被政府、科研機構及企業(yè) 應用于犯罪分子行為模式挖掘、疾病傳播研究、推薦 系統(tǒng)等政府數(shù)據(jù)挖掘、學術研究與商業(yè)應用當中.

然而圖數(shù)據(jù)中蘊含大量的敏感信息，一旦泄露，造成的后果極為嚴重。除如社交網絡中的個人資料、醫(yī)療數(shù)據(jù)中的診療記錄、交易信息網絡中的交易內容等圖結點上的敏感文本屬性外，圖數(shù)據(jù)中還包含社會關系、醫(yī)患關系、交易方式等邊上的敏感鏈接關系. 因此圖數(shù)據(jù)的隱私泄露事件往往涉及人數(shù)眾多、影響廣泛。2018 年，社交網絡 Facebook 超過5000萬用戶個人信息遭到泄露，除個人資料等用戶結點屬性信息外，還包括好友資料、點贊與轉發(fā)情況 等用戶結點間的關聯(lián)關系 . 數(shù)據(jù)公司通過分析用戶間的關聯(lián)關系，準確推測出了用戶的受教育情況、政治傾向、性取向，甚至是用戶兒童時期受過的創(chuàng)傷， 從而精準投放引導性信息，以達到左右用戶行為的目的。此外，數(shù)據(jù)分析者還利用用戶的好友列表，進一步擴大影響范圍。最終，該隱私泄露事件累計波及到了 8700 萬用戶。Facebook 也因此信譽受損、市值下跌，并面臨累計超過16億美元的罰款。

可見，圖數(shù)據(jù)在收集與發(fā)布等使用過程中面臨著巨大的隱私風險。攻擊者可以結合各種背景知識對圖數(shù)據(jù)發(fā)起隱私攻擊。在圖的集中式存儲場景下，攻擊者可借助公開的人口統(tǒng)計數(shù)據(jù)、個體語義屬性信息、個體所在圖的局部結構信息、公開數(shù)據(jù)集、 網絡爬蟲爬取的圖數(shù)據(jù)等輔助信息，對匿名圖發(fā)起結點實體身份再識別攻擊，并進一步推斷實體的語義屬性、鏈接關系等隱私信息。在圖的分布式存儲 場景下，不可信的數(shù)據(jù)收集者可以在數(shù)據(jù)收集過程 中直接竊取用戶的隱私數(shù)據(jù) . 即便只發(fā)布或收集與原始圖相關的統(tǒng)計信息或隨機圖模型參數(shù)等，圖數(shù)據(jù)的隱私安全依然會遭到威脅。一則，發(fā)布的統(tǒng)計數(shù)據(jù)本身可能是敏感信息。二則，攻擊者可以通過發(fā)布的數(shù)據(jù)以較高的準確度還原原始圖，或者綜合利用各類統(tǒng)計數(shù)據(jù)對原始圖進行隱私推斷。

綜上所述，對圖數(shù)據(jù)隱私保護技術的研究迫在眉睫。然而圖數(shù)據(jù)蘊含信息豐富，實體間關聯(lián)關系復雜，給其上的隱私保護帶來了嚴峻的挑戰(zhàn)。首先，圖數(shù)據(jù)上信息的多樣性增大了隱私定義的難度。圖數(shù)據(jù)中結點所代表的實體身份、語義屬性、結點所在的子圖結構、結點本身在圖中的存在性，以及圖中邊上的語義屬性、邊的存在性，都可能是需要保護的敏感信息。如何選擇并綜合各類敏感信息進行合理的 隱私定義，是圖數(shù)據(jù)隱私保護上的一個難點。其次， 圖數(shù)據(jù)中結點之間復雜的關聯(lián)關系增大了隱私保護技術設計與應用的難度。同一個結點可能與大量其 它結點存在各種不同的鏈接關系，并且結點上的語義信息與結點所在子圖的結構特征也存在一定的關聯(lián)，對圖中任何一個結點、一條邊或一條語義信息稍做更改，都可能牽一發(fā)而動全身，大大降低圖數(shù)據(jù)整體的可用性。因此，如何在充分保護用戶隱私的前提下，同時保障圖數(shù)據(jù)的高可用性是研究者關注的焦點。

針對關系型數(shù)據(jù)的傳統(tǒng)隱私保護技術無法滿足圖數(shù)據(jù)發(fā)布與收集的隱私需求。傳統(tǒng)的k-匿名技術、 l-多樣性技術、t-接近技術等雖然可以直接應用于圖數(shù)據(jù)發(fā)布時，結點上語義信息的保護，但是無法同時保護結點間特殊的鏈接關系，以及結點所在的特殊子 圖結構等隱私信息。而傳統(tǒng)的差分隱私技術直接應用 于圖數(shù)據(jù)的發(fā)布與收集時，相關函數(shù)敏感度較高，會導致添加的噪聲過大，數(shù)據(jù)可用性急劇下降。此外，若 直接用傳統(tǒng)的差分隱私技術對結點上的語義信息、結點存在性、邊上的語義信息與邊存在性等進行全面的 隱私保護，不僅會引起添加噪聲過大問題，而且會破壞圖數(shù)據(jù)上信息之間的一致性，降低數(shù)據(jù)可用性。因此，為滿足圖數(shù)據(jù)上隱私保護的需求，需要在傳統(tǒng)隱私保護技術的基礎上結合圖數(shù)據(jù)的特點、針對圖數(shù)據(jù)上隱私保護的難點來進行創(chuàng)新。

本文第2節(jié)從圖數(shù)據(jù)隱私信息、泄露場景、與敵手模型三個方面綜合分析了圖數(shù)據(jù)在收集與發(fā)布中面臨的隱私風險。第 3 節(jié)分析了目前在圖數(shù)據(jù)模型 上各類攻擊算法及其量化方法，對攻擊者的能力進行直觀地說明。第4節(jié)介紹了圖數(shù)據(jù)中簡單匿名、圖修改、聚類，及差分隱私四種主流隱私保護技術，并梳理了針對不同應用場景與數(shù)據(jù)類型的隱私防御算法。同時介紹了圖數(shù)據(jù)隱私性與可用性度量及二者關系。第 5 節(jié)總結了當前圖數(shù)據(jù)隱私保護中仍然存在的問題，并展望了未來可能的研究方向與挑戰(zhàn)。第6節(jié)總結全文。

2 隱私風險 

隱私風險指的是在圖發(fā)布與收集的過程中可能 面臨來自多種攻擊者、對不同的攻擊對象發(fā)起的各類攻擊，從而導致圖中的敏感信息泄露。本節(jié)將從隱私信息、隱私泄露場景、敵手模型三個方面，評估 在圖收集發(fā)布的過程中所面臨的隱私風險。

2.1 隱私信息
隱私信息是圖中可能泄露的各類敏感信息。文獻［3］從結構上將圖上的隱私信息主要分為結點上的隱私信息與邊上的隱私信息兩大類。而本文則根據(jù)文獻［2］，從內容的角度將圖上的隱私信息分為身份信息、語義屬性與鏈接關系三大類，并豐富了定義內涵。

身份信息指圖數(shù)據(jù)中結點與結點所代表實體身份的一一對應關系，如：社交網絡中結點所代表用戶的用戶姓名、用戶 ID 等身份標識符。除結點與實體的對應關系外，在傳染病傳播圖等數(shù)據(jù)中，結點本身 在圖中的存在性也是一個敏感信息。

語義屬性指結點中除身份信息外其他可能泄露隱私的屬性信息，通常包括敏感屬性信息，如郵件通訊網絡中與用戶結點關聯(lián)的郵件內容；或一組可以唯一確定結點身份的非敏感屬性集合，即準標識符， 如職業(yè)社交網絡中用戶結點的職業(yè)、性別、年齡、所在地郵編等。鏈接關系指結點所代表實體之間的關聯(lián)關系， 在圖中用邊表示。

鏈接關系上的隱私信息包括邊上 的權重，如商業(yè)網絡中兩個實體間的交易額；邊上的 屬性，如社交網絡中兩個實體間的朋友、親友、醫(yī)患關系等；邊的存在性，如在通訊圖中結點所代表的實 體間是否存在****或電話往來等.

2.2 隱私泄露場景

隱私泄露場景是圖數(shù)據(jù)發(fā)布與收集中可能泄露隱私的環(huán)節(jié)，主要包括圖的集中式存儲與圖的分布式存儲兩種場景。圖1為隱私泄露場景示意圖。下面分別介紹兩種場景下圖數(shù)據(jù)面臨的隱私問題。

2. 3 敵手模型 
敵手模型通過敵手能力、敵手知識，以及敵手目標三個方面，全面刻畫攻擊者的特征。充分了解敵手模型，做到知己知彼，可以為圖數(shù)據(jù)隱私防御方法的研究提供指導依據(jù)。
3 隱私攻擊 
3. 1 攻擊算法 

在圖的分布式存儲場景下，當隱私泄露方式為直接泄露時，攻擊者無需復雜的攻擊算法；而當攻擊者試圖對用戶進行暴力入侵時，通常采用中間人攻擊等信息安全領域的攻擊方法，不在本文的討論范疇內。因此本節(jié)將主要介紹圖的集中式存儲場景下 的隱私攻擊算法。目前，圖的集中式存儲場景下的攻擊算法可分為兩大類，基于種子結點（seed-based）的攻擊算法以及非種子結點（seed-free）攻擊算法。本文進一步將 基于種子結點的攻擊算法分為基于種子結點的主動攻擊算法與被動攻擊算法兩個子類。此外，不同于［1，14］等文獻按照時間順序介紹相關算法細節(jié)，本文首次提煉各類圖隱私攻擊面臨的關鍵問題，明晰攻擊算法整體的發(fā)展脈絡。下文圍繞算法目標、針對的關 鍵問題，以及相應的解決方案，描述經典攻擊算法。

3. 2 攻擊量化 

除從實踐上證明算法的可行性外，還有一系列的研究致力于從理論上給出匿名圖可以被攻破的條件，以及不同背景知識對去匿名化的影響。不同于［1，14］等文獻，本文除量化算法所基于的隨機圖模 型外，還著重分析了各個經典量化算法針對的不同的去匿名化條件，并在表3中從理論模型假設、攻擊類型，以及量化攻擊時考慮的不同條件類型，全面總結了當前攻擊量化研究成果.

4 隱私防御 

為抵御上述針對圖數(shù)據(jù)的隱私攻擊，研究者結合不同地隱私防御技術，提出了多種隱私防御的算法，本節(jié)將從圖上的隱私防御技術、隱私防御算法， 以及圖的隱私性與可用性三方面展開介紹。

4. 1 隱私防御技術 
目前，針對圖數(shù)據(jù)發(fā)布與收集的隱私防御技術主要可以分為簡單匿名技術、圖修改技術、聚類技術 以及差分隱私技術四類。下面將依次介紹上述隱私 防御技術及其實現(xiàn)機制.。

4. 2 隱私防御算法 

在針對圖數(shù)據(jù)的發(fā)布與收集過程中，最直接的方式是發(fā)布或收集原始圖的鄰居向量或鄰接矩陣，因此部分研究基于原始圖的拓撲結構、鄰接矩陣或鄰居向量設計隱私保護方案。然而原始圖的拓撲結構復雜， 鄰接矩陣維度較高，在算法設計與實現(xiàn)過程中存在算法時間復雜度高、噪聲添加大等困難。因此除原始圖外，還有研究針對圖上的統(tǒng)計特征、隨機圖模型參數(shù)，以及合成圖的收集與發(fā)布進行隱私保護。相比于以隱私技術為依據(jù)的傳統(tǒng)分類方式［1，14，］本文從實際應用的角度出發(fā)，分別介紹在集中式與分 布式數(shù)據(jù)存儲場景下，針對以上四種圖上數(shù)據(jù)類型的 隱私防御算法。同時，本文首次提煉出各類隱私防御算法面臨的關鍵問題，并圍繞算法的防御目標、采用的防御技術，以及算法針對的關鍵問題及其解決方案，對相關算法進行描述，明晰各類算法發(fā)展脈絡。

5 挑戰(zhàn)與展望 

隨著人們對個人隱私的逐步重視，各類新政策的出臺，個人隱私保護需求與高質量服務需求 之間的矛盾被持續(xù)激化，使得對圖數(shù)據(jù)的隱私風 險評估與隱私性度量、可用性度量、隱私保護技術、隱私保護算法等的深入研究空前迫切。目前， 已經有很多研究致力于解決圖上的隱私保護問題，相關研究已經廣泛涉及到了不同場景下的多種數(shù)據(jù)類型、隱私保護技術，取得了一定的進展。但由于圖數(shù)據(jù)具有蘊含信息豐富、數(shù)據(jù)之間關聯(lián)性強、現(xiàn)實中圖相對稀疏等特點，現(xiàn)有的研究還不 能滿足人們對圖數(shù)據(jù)上隱私保護的需求，當前還 有很多亟待解決的問題，限制了相關研究在現(xiàn)實應用中的推廣與普及。

5. 1 圖數(shù)據(jù)隱私發(fā)布與收集中的難點問題 
5. 1. 1 隱私性與可用性權衡問題 
數(shù)據(jù)隱私性與可用性的權衡問題是隱私保護領域的一個共性問題。如何找到可用性的犧牲與隱私性保證之間的平衡點是設計隱私保護算法的關鍵。然而，圖中隱私信息類型豐富，不同結點之間具有很強的關聯(lián)性，給圖數(shù)據(jù)隱私性與可用性的量化與隱私方案設計帶來了更大的挑戰(zhàn)。首先，對于數(shù)據(jù)隱私性而言，雖然針對不同采用不同隱私技術的匿名圖有不同的量化方式，但是缺乏統(tǒng)一的量化標準；對于數(shù)據(jù)可用性而言，雖然可以用特定的圖性質來度量，但同樣尚且沒有簡潔統(tǒng)一的量化標準。并且，不論是圖數(shù)據(jù)的隱私性度量還是可用性度量，目前都很難兼顧圖上結點的身份信息、鏈接關系及屬性信 息等多種隱私信息。而一旦可以綜合量化數(shù)據(jù)隱私性與可用性，就可以通過理論分析找到其平衡點，從而設計更有效的隱私防御方案。其次，在具體設計隱私方案時，不同的隱私信息類型需要采用不同的隱私保護技術，因此很難兼顧所有的隱私信息；圖中的同一個結點通過邊與很多其他結點相連，若對中心結點進行修改則會極大程度破壞圖結構可用性， 而不做修改則很難保障中心結點的結構隱私。基于此，無論是對圖數(shù)據(jù)隱私性與可用性的量化，還是對于具體的隱私保護方案設計，圖數(shù)據(jù)的隱私性與可用性權衡都將繼續(xù)是未來圖數(shù)據(jù)隱私保護的一個嚴峻的挑戰(zhàn)。

5. 1. 2 個性化隱私保護 
圖數(shù)據(jù)在現(xiàn)實生活中圖數(shù)據(jù)有廣泛的應用，如基于社交網絡、購買記錄等的推薦系統(tǒng)，基于地理位置的路徑規(guī)劃，以及基于交易記錄的欺詐檢測等等。在不同類型的網絡中對隱私保護強度有不同的需求。而在同一個網絡中，同一個實體結點對不同的隱私信息也有不同的需求。以基于社交網絡的朋友推薦為例，社交網絡中的不同用戶哪些屬性為隱私屬性，或者哪些鏈接關系為隱私鏈接關系都有不同的定義。還有一些用戶不認為自己所在社交網絡中存在隱私信息，反而希望服務提供商利用自己在社交網絡中的信息，為自己提供更精準的好友推薦、社群推薦或者商品推薦等服務。在以往的研究中，還沒有發(fā)現(xiàn)能夠解決圖數(shù)據(jù)上個性化隱私保護的可行方案。因此，如何針對不同網絡中不同實體的隱私需求，在保護實體隱私的同時，為實體提供更好的服務是未來圖數(shù)據(jù)隱私保護一個研究趨勢。

5. 1. 3 圖數(shù)據(jù)的動態(tài)發(fā)布與多次收集 

在對圖的研究中，圖的演化是一個重要的研究方向。研究圖的演化可以對人的社交行為、疾病的傳播規(guī)律等具有更深刻的認識與理解。而研究圖的演化，往往需要對同一圖數(shù)據(jù)進行多次收集或者動態(tài)發(fā)布。一般的隱私防御方案無法保證在多次收集或者動態(tài)發(fā)布中數(shù)據(jù)的隱私安全。多次收集及動態(tài)發(fā)布時，在保證結點、邊及屬性隱私安全的同時，還需要保證同一時間序列下數(shù)據(jù)的一致性，如：同一時間序列下相同結點的身份代碼要一致；此外發(fā)布數(shù)據(jù)中邊的存在性、圖中的語義信息等要符合原始圖的演化規(guī)律等。隱私防御算法在保證數(shù)據(jù)的一致性同時，提高了數(shù)據(jù)的可用性，但同時也豐富了攻擊者對同一時間序列下的圖數(shù)據(jù)發(fā)起攻擊時的敵手知識，進一步增加了防御的難度。目前，已經有少量的研究關注該問題，但是鮮有有效的解決方案，因此該問題是仍然是未來圖數(shù)據(jù)隱私保護上的一個重要探索方向。

5. 1. 4 面向主動攻擊的隱私防御算法 
主動攻擊者具有很強的攻擊能力?，F(xiàn)實中，主動攻擊者可以通過在社交網絡中創(chuàng)建僵尸賬號并主動關聯(lián)目標用戶對用戶發(fā)起隱私攻擊。近年來有文獻提出一種具有魯棒性的主動攻擊算法，可以以較高的準確度一次性對大量結點進行去匿名化攻擊。該算法的提出，不僅使研究者更深刻認識到主動攻 擊者強大的攻擊能力，更進一步提高了類似于社交網絡等圖中用戶的隱私風險。然而，目前尚沒有攻擊算法可以有效緩解由此類攻擊帶來的隱私風險。因此如何在現(xiàn)有的隱私保護算法上進行提升，或者改進已有的隱私防御技術，使其能更好的應對具有主動攻擊能力的攻擊者是未來隱私保護技術發(fā)展一個可能方向.

5. 1. 5 隱私放大理論在圖隱私保護中的應用 
近年來，通過深入挖掘各類算法自身特征，有很多工作提出了一系列的隱私放大理論，從而提升隱私防御效果。上述工作利用算法本身的隨機性、下采樣、隨機打亂等方式，放大差分隱私預算，以取得更好的隱私防御效果。利用差分隱私進行圖的收集與發(fā)布普遍面臨噪聲添加過大，導致數(shù)據(jù)可用性降低等問題。若能深入研究圖的各類算法自身隱含的隱私性，或者采用基于混淆模型等的技術放大隱私， 將會極大提升數(shù)據(jù)收集與發(fā)布的質量。然而，在圖上應用隱私放大理論面臨諸多挑戰(zhàn)。圖上的結點之間存在關聯(lián)邊，因此不同數(shù)據(jù)之間不再具有獨立性， 無論是給相關方案的設計，還是給理論上的證明都 增加了難度。目前，還沒有相關工作將隱私放大相關的理論與技術應用于圖隱私保護相關的應用場景下，該技術的應用可能給未來圖上隱私保護技術的發(fā)展帶來新的突破。

5. 2 面向新應用場景的圖數(shù)據(jù)隱私保護 
5. 2. 1 面向圖數(shù)據(jù)機器學習中的隱私保護 
圖數(shù)據(jù)在機器學習領域有著非常廣泛的應用， 如基于神經網絡的結點分類、鏈接預測、社群發(fā)現(xiàn)，對異常檢測問題，商品及好友推薦問題等提供了巨大的幫助。然而，近年來越來越多的研究發(fā)現(xiàn)，機器學習中存在著巨大的隱私風險。攻擊者可以通過機器學習發(fā)布的模型參數(shù)、預測結果等對訓練集發(fā)起 重構攻擊、成員推斷攻擊等，導致訓練集中數(shù)據(jù)隱私泄漏。已有的針對圖數(shù)據(jù)的隱私保護算法只能用戶對圖數(shù)據(jù)訓練集進行輸入擾動，并且此類擾動算法由于添加的噪聲過大，可能嚴重影響訓練模型的可用性。而已有的針對機器學習的隱私保護策略，則面 臨著針對圖訓練數(shù)據(jù)隱私定義難，對關聯(lián)數(shù)據(jù)擾動難等問題。因此如何在保證模型可用性的同時提出可行的隱私保護方法是未來一個可能的探索領域。

5. 2. 2 隱私保護下的圖性質多方共同計算 

不同于分布式存儲場景下的數(shù)據(jù)收集，在隱私保護下的圖性質多方共同計算中，沒有數(shù) 據(jù)收集者，各方掌握部分子圖，及各子圖之間公共的邊鏈接狀況，但不了解其他各個參與方所掌握的隱私圖內部結構。各方希望借助彼此的信息共同計算完整圖中結點間的最短路徑、中心度等信息，實現(xiàn)計算結果共享，同時不泄露自己所掌握圖中的隱私信息 。借助密碼學技術，如秘密共享或多方安全計算等可以解決上述問題，但是存在通信開銷大、計算開銷大等弊端。差分隱私等圖隱私保護技術可以緩解開銷問題，但同時也可能面臨計算不準確等挑戰(zhàn)。目前有少量的工作關注該問題，但僅僅集中在兩方的共同計算上。能否將其擴展至多方共同計算，將會是未來可以探究的新場景。

6 總 結 

目前，圖數(shù)據(jù)在現(xiàn)實生活與研究中被廣泛的應用。與此同時，圖數(shù)據(jù)中也存在極高的隱私風險。而圖數(shù)據(jù)上豐富的信息，數(shù)據(jù)之間關聯(lián)性強，給圖數(shù)據(jù)上的隱私保護帶來了巨大的挑戰(zhàn)。本文分析了圖的發(fā)布與收集中的隱私風險，綜述了目前針對圖數(shù)據(jù) 隱私攻防的各類方案。綜合二者，本文在最后給出了目前圖數(shù)據(jù)上隱私保護研究的仍然存在的問題以及未來可能的研究方向?？傊瑘D數(shù)據(jù)上的隱私保護研究雖然已經取得了一定的進展，但未來依舊有很高的研究價值與廣闊的研究空間。