本文，主要梳理了女巫攻擊及其防禦進展。從現有的方法中，我們確定了三種主要抵禦攻擊的方式：可信認證、資源測試和社交網絡。通過可信認證防禦攻擊，這是使用可以代替中心化認證實體的密碼原語的中心化認證或分佈式認證來完成的。 通過資源測試來防禦攻擊，即可以通過 IP 測試、網絡協調、經常性成本以及要求客戶回答問題的形式。使用社交網絡則是通過結合用作引導安全的社交網絡和來自隨機遊走理論的工具來減輕攻擊，這些工具已證明在某些假設下可有效防禦攻擊。我們分別對三種主要抵禦攻擊的方法進行梳理和分析，總結優缺點，其中這些缺點提供了幾個值得研究的有趣方向和研究問題。
引言
點對點（p2p）計算範式比其他傳統範式有很多優勢。例如，帶寬、內存和數據等資源可供其他所有參與用戶使用 [1]。從廣義上講，這種範式包括結構化和非結構化系統。結構化疊加（例如 Kademlia [2] 和 Chord [3]）為數據和對等點發現提供確定性機制，而非結構化疊加（例如 Gnutella [4]）在隨機圖中組織對等點並使用泛洪算法進行對等點和數據發現。大多數流行的點對點系統都缺乏“中央權威”，這使得這種範式能夠抵禦故障攻擊。另一方面，缺乏這種中心化授權會導致許多具有挑戰性的安全問題：保護網絡系統所需的大多數安全服務都需要一種或另一種中心化授權，使得對等系統無法使用這些服務[5] ]。更糟糕的是，其中許多系統完全去中心化和開放的特性在其他分佈式系統中導致了大範圍的未知安全威脅，包括女巫攻擊 [6]。
女巫攻擊在點對點、有線和無線網絡環境中是眾所周知的。 在其基本形式中，代表攻擊者的對等點生成儘可能多的身份，並且表現得好像她是系統中的多個對等點 [6]，旨在干擾系統的正常行為。 攻擊者可以生成的身份數量僅取決於攻擊者的能力，該能力受限於響應系統中其他對等點併發請求所需的帶寬、存儲與每個生成的女巫身份相對應的節點的路由信息所需的內存，以及在沒有明顯延遲的情況下處理併發請求所需的計算資源。 隨着硬件的急劇增長（例如，在存儲容量和處理方面）以及具有高帶寬速率的寬帶互聯網的廣泛傳播，即使是在通用硬件上運行的攻擊者也可能對大型系統造成重大損害。
女巫攻擊出現在很多情況下，同樣的，在點對點系統以及其他通用分佈式系統和範式中必不可少的我的服務上也是常見的。此類環境包括投票系統、信譽系統、路由、分佈式存儲等。為了說明這種攻擊在現實的系統中是如何工作的，請想象一個建立在點對點覆蓋 [7] 上的推薦系統。在這樣的系統中，系統的目標是根據其他人的推薦過濾出用戶可能感興趣的信息。在這種情況下，可以通過偽造多個身份 (女巫) 充當多個用戶的攻擊者可以輕鬆地在合法用戶投票的合法對象上投票。
在任何現實的推薦系統中，通常對對象進行投票的合法用戶的數量始終不超過系統總用戶的 1%，這幾乎是可以保證的 [7]。鑒於此，這種攻擊對攻擊者很有吸引力，他們是系統中的潛在用戶，試圖攻擊提供高度激勵的系統。例如，線上市場eBay，使用客戶的推薦來確定其賣家、使用其平台銷售商品的人的聲譽，因此對於此類賣家進行不當行為以獲得更高聲譽的行為很有誘惑力。在許多其他情況中也會出現相同的情況，例如內容由用戶評級的點對點文件共享行為，以聲譽為依據分配帶寬的行為，在這一行為中，甚至該聲譽用於確定用戶分發的內容的好壞。在所有此類示例中，都存在用戶行為不端的誘因，而且女巫攻擊被證明是此類攻擊者實現其目標的強大工具。
為了防禦攻擊，已經有人嘗試了幾種防禦或緩解的形式來防禦或限制攻擊的影響。這種攻擊可以大致分為兩種思想流派：中心化和去中心式（即分佈式）防禦。在中心化防禦 [6, 8, 9, 10] 中，中央權威負責驗證系統中每個用戶的身份。雖然這種防禦在防禦攻擊方面有些有效，但它對系統做出了某些假設，其中一些假設在點對點的去中心化系統中不容易實現。首先，正如名稱和操作描述所表明的那樣，此類系統需要中心化權限，出於安全性和功能性原因，許多此類系統可能無法負擔得起。此外，即使存在這樣的中心化權威，也需要一些與系統中用戶相關的憑據，以便將用戶的這些憑據與其數字身份相匹配：在許多情況下，獲取此類憑據是非常有挑戰性的工作。
另一方面，去中心化防禦包括但不限於 [11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 7, 21, 22, 23] 中的工作，它們不需要系統中有中心化的權威，並為分散的點對點系統精心設計而成。在其操作的核心，此類防禦會權衡系統中用戶之間的協作，以接納或拒絕可能是攻擊者的用戶。用戶的接納或拒絕基於與用戶關聯的憑據，如加密分佈式防禦的情況，或合法誠實用戶的網絡屬性，如使用社交圖的女巫防禦的情況。 在任何一種解決方案中，防禦的最終目標都是以分散的方式模擬中央權威的力量，並使用這種力量來檢測女巫和誠實的節點。
防禦的另一種分類可能是根據這種防禦的運作方式。 因此，以往的工作中，女巫防禦可以分為使用可信認證的防禦——其中證書通常是為誠實用戶生成的，並根據受信任機構的公鑰進行驗證，產生成本——其中用戶受到一些成本的懲罰，從而限制他們的可用資源數量，減少他們的不當行為，以及基於社交網絡的女巫防禦。
這種防禦在它們的假設、所應用的網絡類型、提供的保證以及產生的成本方面有很大不同。 為此，本文主要回顧、總結、比較和展示現有的方法中，女巫防禦的不足之處。
2. 女巫攻擊模型和目標
在本節中，詳細說明了大多數女巫攻擊研究和防禦中通常假設的攻擊者模型，進一步探討了攻擊者的目標和防禦目標。
2.1 問題陳述和模型
該問題被表述為系統中的單個用戶在系統中具有一種能力，此能力讓她像是具有多個分身一般行動。 這對於如此多的應用程序來說是有問題的，因為此類應用程序的正確性取決於同行的行為、他們的數量以及在系統中誠實地參與協作的意願。 然而，試圖偏向系統整體行為的單個攻擊者的女巫身份不能滿足這樣的系統目標。
攻擊者的正式特徵是她可以在系統中注入的虛假身份的數量。 攻擊者的動機是最大化虛假身份的數量。 攻擊者生成並注入系統的身份數量的價值和意義取決於應用程序本身，並因應用程序而異。 例如，要攻擊一個推薦系統，將系統中 1% 的誠實用戶的匹配總和作為假身份就足夠了。 因為通常觀察到，即使對於該系統中非常受歡迎的對象，也只有 1% 的誠實節點投票支持它，所以這尤其是一個足以使系統的行為產生偏差並超過系統中的誠實節點。也就是說，通過擁有比系統中某個對象投票的誠實節點的確切數量更多的單一身份，女巫攻擊者將能夠超過誠實節點的投票。
另一方面，在其他系統中，例如用於通信匿名化的混合網絡（如 Tor 網絡），即使是少量的女巫身份可能會嚴重破壞系統中的承諾。 從理論上講，電路上兩個節點的妥協足以識別這種混合網絡上通信的發送方和接收方[24]。 另一方面，網絡中足夠多的身份的妥協將使攻擊者能夠監控任意數量的電路。身份數量本身很重要的其他應用程序包括對文件共享系統的攻擊 [25] ，這樣的例子有很多。
圖一 在P2P疊加環境中幾種不同的女巫防禦的方式
C/CA 代表中心化的認證機構
D/C 代表去中心化的加密原語
T/D 代表可信設備認證
IP/T 代表IP檢測
R/C 代表基於成本循環的檢測
S/G 代表基於社交圖譜的防禦方式
2·2 女巫防禦的目標和成功的標準
女巫防禦的最終目標是通過在覆蓋網絡中偵查並且孤立女巫身份，或者那些對等地能夠產生這些女巫身份的節點，來消除女巫攻擊。但是，這一終極目標並不總是能夠實現，因為大多數防禦，除了基於中心化可信認證的方案之外，大多數防禦在其檢測機制中都有誤報和漏報的可能性，可能會容忍某些女巫節點，同時錯誤地報告其他誠實的節點，就像我們在假陽性和假陰性報錯中看到的那樣。假陽性報告指女巫節點被報告為誠實節點。另一方面，假陰性誠實節點被報告為女巫節點。防禦機制的現實和實際可實現的目標是儘可能地減少假陰性率。
2.3 女巫防禦的深度
除了第 1 節所示將女巫防禦分為中心化和去中心化防禦的廣泛分類之外，本文調查的女巫防禦方式還包括兩大類技術：可信認證和資源測試類別，如圖 1 所示。在可信認證的列表中，我們梳理了使用中心化認證機構、去中心化加密原語或可信設備的相關工作。
3. 使用可信認證
可信認證方法可以說是當下最流行的方法之一，因為 Douceur [6] 已經證明它具有消除 Sybil 攻擊的潛力 [26]。 在這種方法的傳統形式中，中心化授權 (CA) 用於通過將這些身份與預先分配的憑據進行匹配來確保分配給每個對等方的身份是唯一且合法的。這些憑證可能包括加密密鑰、通常由一次性密碼生成器 (OTP) 生成的同步隨機字符串或由中心化認證頒發的數字證書。
雖然上述傳統形式的中心化證書頒發機構在文獻中有明確定義，但已經通過應用適用於分佈式多方模型的加密原語來定義分佈式證書方案，這些模型使假定誠實的對等方之間能夠協作以證明加入覆蓋的其他對等方.
3.1 中心化認證機構
中心化可信認證可能是唯一可以消除女巫攻擊的方法 [6]。 在 P2P 覆蓋的環境中，已經有一些關於使用中心化證書頒發機構進行憑證生成、分配和驗證的工作。 例如，使用第 5 節中解釋的社交圖並利用公鑰密碼學作為構建塊的研究，假定用戶公鑰的真實性通過在離線階段通過中心化授權分配給用戶的證書 [19]。 利用基於 CCA 的方法的其他方案示例包括 [8]、[9]、[6] 和 [10] 中的工作。
3.2 加密原語
最近，已經湧現了一些關於加密原語的工作 [11, 12, 13, 14, 15]。這些原語旨在提供用於驗證對等點的基礎設施，以便通過僅讓合法對等點參與覆蓋來使女巫攻擊更難發生。通常，這些工作試圖以去中心化方式利用公鑰基礎設施 (PKI) 並使用閾值加密成分（例如，秘密共享和閾值簽名），以確保所謂的誠實用戶之間的協作，以驗證加入覆蓋其上的對等方的操作時間。有趣的是，明確陳述的動機超出了其中一些原語（例如，[11, 12, 13, 14]），這是因為文獻中的許多非加密協議都假設存在用於覆蓋合法用戶的認證系統（例如 SybilGuard 和 SybilLimit）。因此，加密方法旨在確保此類協議的成功運行。
3.3 可信設備
與可信認證的想法類似，一些研究與實踐，建議使用可信設備或可信模塊來存儲先前由中心化機構分配給用戶的證書、密鑰或身份驗證字符串。 這種設備由於其潛在的高價而基本上很難獲得，因此可用於限制女巫攻擊者的機會。 在[27]和[28]中提出了這種機制的例子，儘管後來的工作是在無線傳感器網絡上。 理論上，當攻擊者意圖獲取儘可能多的女巫身份時，這些防禦措施可能會奏效。 然而，在匿名（例如 Tor）和推薦系統等情況下，考慮到較少的女巫身份就可能會造成很大的危害，所以這些防禦措施已經過時了。
4. 資源測試
除了用於防禦女巫攻擊的資源測試方法之外，基本思想是檢查與假定不同用戶相關聯的一組身份是否擁有與身份數量匹配的足夠資源。這些資源可能包括計算能力、帶寬、內存、IP 地址，甚至信任憑證。儘管 Douceur 證明了資源測試的想法是無效的 [6]，但一些研究人員認為它是一種最低限度的防禦。也就是說，該方法不能完全消除攻擊，但是會使其女巫攻擊更難發生。
理論上，此類防禦中的大多數方案將女巫身份的數量限制為比沒有防禦的情況下的數量少。然而，在實踐中，即使是更少數量的女巫身份也足以威脅許多系統的可用性和安全性。例如，如前所述，匿名系統（如 Tor）中的匿名性取決於每個電路的兩個節點。此外，在線聲譽系統中有 1% 的虛假身份就足以投票給合法節點。
4.1 IP 測試
通用測試方案包括測試對等方的 IP 地址，試圖確定他們的位置並將其與他們的活動相匹配。特別是，如果從同一特定地理區域產生大量活動，則其中一些活動很可能是由於女巫身份。此外，此類作品中的假設是獲取不同地理區域的 IP 地址，但這並不便宜。例如，弗里德曼等人 [29] 介紹了 Tarzan，其中根據節點在特定自治系統中的地理位置測試其 IP 地址。Cornelli 等人在 [30] 和 [30] 中介紹了類似的結果。
這些工作的主要假設是 IP 地址很難在廣泛的地理區域中獲得。然而，最近有跡象表明存在巨大的殭屍網絡 [31]，受感染的主機由單個管理實體控制並駐留在不同的自治系統中，可以肯定的是，這種防禦機制是無用的。
4.2 成本循環
一些研究及實踐，建議將經常性成本作為防禦女巫攻擊的一種方法。 特別是，計算難題 [16, 32] 和圖靈測試（例如 CAPTCHA [33]）被建議作為解決方案。 然而，出於同樣的原因，IP 測試對控制殭屍網絡的攻擊者不起作用，這些基於成本的方案也不會起作用。 此外，對於類似 CAPTCHA 的解決方案，已經表明 Sybil 攻擊者可能會在控制的站點上發布 CAPTCHA 測試，供用戶測試以訪問攻擊者提供的服務。
此外，某些版本的 CAPTCHA 容易受到某些圖像處理攻擊 [34]。
5. 基於社交圖譜的防禦
雖然之前針對分佈式系統中女巫攻擊問題提出的大多數解決方案都有局限性和缺點，但基於社交網絡的女巫防禦嘗試以優雅的方式克服這些問題。首先，基於社交網絡的女巫防禦大多是解決女巫攻擊問題的去中心化解決方案，這意味着這些設計在沒有任何中心授權的情況下運行——這是大多數分佈式系統中的重要特性。由於隨機遊走理論，這種去中心化的操作模型更加容易，隨機遊走理論是這些防禦中最常用的成分。其次，這些防禦利用社交節點之間社交鏈接的信任，使誠實節點之間的協作變得可能且容易。第三也是最後一點，這些防禦在幾項研究中得到了證明，它們能以低成本實用且有效地防禦女巫攻擊，而且它們現在進一步開發為許多服務的組件，包括分佈式哈希表 (DHT)、抗女巫攻擊投票，並用於移動網絡路由。
儘管它們在設計細節和操作上有很大不同，但所有基於社交網絡的女巫防禦都有兩個共同的假設：算法屬性即快速混合屬性以及信任。 首先，這些防禦基於社交圖的“快速混合”屬性。 非正式地，社交圖的快速混合屬性意味着此類圖中的“誠實”節點很好地嚙合，並且誠實區域不包含稀疏切割——一種將兩個大型誠實節點子集與一些社交網絡連接起來的切割。為簡單起見，社交圖的快速混合特性意味着來自社交圖中任意節點的隨機遊走將非常接近在幾步后該圖上定義的馬爾可夫鏈 (MC) 的平穩分佈。 在百萬節點的網絡中，建議這樣的步數為 10 到 15 步。
這種防禦脈絡的第二個共同假設是信任。 特別是，所有這些防禦都假定在底層社交圖中具有良好的信任值，例如，通過節點之間的面對面交互所表明的。 為了推斷任意多個攻擊者的社交鏈接滲透社交網絡的難度，這個特定的假設是必要的。 雖然用於正確識別社交圖中“誠實”節點的女巫防禦的操作是由快速混合假設保證的，並且使用這種算法屬性的相應方案的構建，識別 女巫節點的能力僅在假設以下條件下得到保證攻擊者，或攻擊者的集體，控制着自己與社交圖中其他誠實節點之間的一些鏈接（這種鏈接稱為攻擊邊）。
下面我們梳理了一些被廣泛引用和關注的基於社交網絡的女巫防禦的方法。
5.1 Sybil Guard
SybilGuard 的設計，歸功於 Yu 等人[19, 20]，它使用信任擁有社交網絡的快速混合特性來檢測女巫節點。從技術上講，SybilGuard 包括兩個階段：初始化階段和在線檢測階段。在初始化階段，每個節點構建它的路由表，作為其相鄰節點的隨機排列，用於輸入和輸出邊對。接下來，每個節點啟動一個長度為 w = O (根號n log n) 的隨機遊走，並按照使用隨機排列構建的路由表將其傳播到其相鄰節點。隨機遊走路徑上的每個節點都會註冊隨機遊走發起者的見證人，然後當該節點成為嫌疑節點時充當該節點的見證者。此外，利用隨機遊走的回溯性，隨機遊走的每個發起者都會收到“見證人”列表（即註冊發起者公鑰並位於發起者隨機遊走構建的路徑上的節點） .
在線上階段，驗證者確定嫌疑人是否誠實，如下所示。 首先，嫌疑人將其隨機路由上的“證人”的地址發送給驗證者。 因此，驗證者將見證人列表與其驗證者路由列表進行比較。 如果兩個集合之間沒有交集（一個非常有可能發生的事件），驗證者將中止並拒絕嫌疑人。否則，驗證者將繼續，要求比較兩個集合之間的交集上的節點來驗證嫌疑人是否有用它們註冊的公鑰。如果嫌疑人被交叉節點驗證，則驗證者接受嫌疑人或將其標記為女巫節點。
5.2 Sybil Limit
與使用單個長隨機遊走的 SybilGuard 不同，SybilLimit 建議使用多個較短的隨機遊走。此外，與 SybilGuard（驗證者和嫌疑人的公鑰註冊在社交圖中的節點上不同，SybilLimit [18] 建議在社交圖中的邊上註冊此類密鑰。 SybilLimit 由初始化階段和在線驗證階段組成。在初始化階段，每個節點使用 SybilGuard 中描述的相同方法構建其路由表，並執行 r = O (根號 n) 的隨機遊走，每次長度為 w = O (log n) 其中 O (log n) 是混合時間社交圖的 10 到 15 個社交圖 ，理論上假設足以從非常接近統計分佈的分佈中採樣節點。與 SybilGuard 不同，隨機路由路徑上的所有節點都用於註冊隨機遊走發起者的公鑰，r 次隨機遊走中每次遊走的最後一條邊用於註冊該發起者節點的公鑰（每個這樣的邊稱為尾部）。特別地，遊走發起者的公鑰註冊在隨機遊走到達的最後一條邊下的最後一個節點上。同樣利用隨機路由的回溯性，註冊發起者節點（可以是嫌疑人或驗證者）公鑰的見證人將他們的身份返回給該節點。社交圖中的每個節點都執行相同的過程，並且每個發起註冊隨機遊走的節點都收集一組見證人（或驗證節點）。
在線上階段，SybilLimit也與 SybilGuard 相同，嫌疑人將證人的標識符和地址發送到驗證者節點，該節點將比較嫌疑人列表中的證人，試圖找到衝突。 如果在驗證者端的兩個集合中發生衝突，驗證者會要求兩個集合中具有共同身份的見證人驗證嫌疑人的身份，並根據此過程的結果決定是接受還是拒絕嫌疑人。如果兩者之間沒有交集（這樣的事發生的可能性很小）驗證者通過將嫌疑人標記為攻擊者來中止並拒絕嫌疑人。
用於推理 SybilLimit 的可證明保證的主要成分與 Sybil Guard 中的相同。特別地，假設隨機遊走長度 w 是社交圖的混合時間，那麼在這種隨機遊走中選擇的最後一個節點是根據平穩分佈的。
此外，隨機遊走中的最後一條邊是從社交圖中的邊中“幾乎”均勻隨機選擇的。此外，假設 r = O（根號 n），如果正確選擇了隱藏常量 r0（其中 r = r0 ×根號 n），則驗證者和嫌疑人的採樣邊緣之間的交集將以壓倒性的概率存在。作者將這種條件稱為“交集”條件，用於保證誠實區域中節點隨機遊走的高概率交集。與 SybilGuard 一樣，假設有 g 個攻擊者邊緣，則允許攻擊者在最多 gwr = O (g ×根號 n× log n) 尾（稱為污染尾）上註冊其女巫身份的公鑰。在這種情況下，每個附加邊都會引入額外的 O (log n) 女巫身份（假設攻擊者通過在每個可能的受污染尾部註冊不同 Sybil 身份的不同公鑰來使用最佳攻擊策略）。
SybilLimit 的安全性也很大程度上依賴於 w。 由於沒有估計參數的確切值的機制，因此低估或高估這些參數都是有問題的，如上所示。 SybilLimit 還提供了一種用於估計該參數的“基準測試技術”，該技術也不對參數估計的質量提供任何可證明的保證。 最後，只要 g = o (n / log n)，Sybil Limit 就可以保證每個攻擊邊緣引入的女巫身份的數量。 請注意，SybilGuard 和 SybilLimit 都不需要對其運營的社交網絡有任何全局了解，並且可以以完全去中心化的方式實施。
5.3 Sybil Infer
SybilInfer 使用在隨機遊走（稱為軌跡）上定義的概率模型來推斷生成此類軌跡的一組節點 X 的真實程度。 SybilInfer 中的基本假設是每個節點都擁有社交網絡的全局視圖和知識，網絡是快速混合的，發起 SybilInfer 的節點是一個誠實節點。從技術上講，SybilInfer 試圖最終將圖中的不同節點標記為誠實節點或女巫節點。在 SybilInfer 中，n 個節點的網絡中的每個節點執行 s 次行走，因此通用跡中的行走總數為 s × n。這些跡中的每個痕迹由第一個節點（隨機遊走的發起者）和隨機遊走中的最後一個節點（即尾部）構成。與 SybilGuard 和 SybilLimit 中使用的統一（超過節點度）轉移概率不同，SybilInfer 定義了節點上統一的轉移矩陣，從而懲罰具有更高度的節點。 SybilInfer 操作的最終目標是計算概率 P (X = Honest | T)；也就是說，計算給定軌跡 T 的一組節點 X 是誠實的概率。這個概率是使用貝葉斯定理計算的。
SybilInfer 通過技術手段對誠實配置進行採樣，該配置最初用於從跟蹤中確定一組節點的誠實性。 這個採樣是使用 Metropolis-Hasting 算法進行的，它首先考慮一個集合 X0 並通過刪除或添加節點到集合中一次修改該集合：在每次，並且有概率從 X¯0 中填充一個新節點 x被添加到 X0 使 X ′ = X0 [x 或 X0 中的節點以概率 premove 被刪除。 該過程執行 n× log n 輪以獲得獨立於 X0 的良好樣本。
5.4 Sum Up
不像 SybilGuard 和 SybilLimit 是通用的節點准入問題，並且在不需要單個節點攜帶有關社交圖的全局信息的意義上去中心化，以及用於推斷節點誠實度的 Sybil-Infer，SumUp [35] 試圖在投票聚合的背景下解決女巫攻擊問題。在這種情況下，一個稱為投票收集器的節點希望以抗女巫的方式從網絡中的其他節點收集投票。這就是，在給定數量的對象投票中，投票收集者希望增加誠實節點接受的投票比例，減少攻擊者通過其攻擊邊緣投出的接受投票，並在攻擊者多次反覆行為不當時識別攻擊者。在 SumUp 的核心是，鏈接容量分配機制用於自適應地為信任擁有社交圖中的鏈接分配容量，並限制從投票者一側傳播到選票收集器的選票數量。 SumUp 的自適應投票流機制使用了傳統在線投票系統的兩個觀察結果：系統中的少數用戶對單個對象進行投票，並且——如果這種投票系統是在社交圖之上實現的——擁堵僅出現在靠近選票收集器的鏈上。因此，SumUp 建議根據它們與投票收集器的距離（根據使用廣度優先搜索算法計算的某些級別）在社交圖中的不同鏈接上分發大量票證。
該技術的一個明顯吸引力在於其高計算要求：典型算法（例如 Ford-fulkerson 算法）的運行時間將需要一個操作邊數的順序，以收集單個選民的投票。它的作者進一步提出了一種啟髮式方法，它僅使用圖直徑步數的順序，其中每個節點貪婪地選擇更高級別的節點，通過該節點使用非零容量連接並傳播投票，直到達到投票收集器。 在任何時間，考慮到貪婪步驟可能不會導致非零容量，每個節點都被允許探索其他節點以尋找相同或更低級別的路徑。
5.5 GateKeeper
GateKeeper [21] 借用了 SumUp 和 SybilLimit 的工具來實現高效操作。尤其是它試圖通過合併 SumUp 的票證分發組件來提高 SybilLimit 的性能。不像在 SumUp 中，節點通過從投票者到收集者的非零路徑被接納，如前所述，GateKeeper 只考慮 SumUp 的“票證分配”階段，其中票證被准入控制器用於接納節點。此類票證以與 SumUp 中相同的方式從控制器傳播到所有節點。但是，為了限制攻擊者獲得更多門票的機會並降低其整體優勢，GateKeeper 中的控制器隨機選擇 m 個不同的隨機節點；這些節點被稱為“有利節點”，當且僅當可疑節點從不同的有利位置收到 fadmitm 票證（其中 fadmit 是隨機選擇的有利位置的分數；在 GateKeeper 中使用 0.2）時，它才會被允許。因此，一旦一個節點被這個有利位置的一小部分允許，它就會被允許。為了防止雙花攻擊，Gate Keeper 建議使用門票的路徑的加密簽名鏈（傳播到控制器）。
5.6 其他基於社交網絡的 DHT
SPROUT [36] 是另一種 DHT 路由協議，它使用具有信任的社交圖的社交鏈接將信息路由到在社交網絡上操作的用戶。 SPROUT 實際上建立在 Chord [3] 之上，並在 Chord 中向任何給定節點的社交網絡中的其他用戶添加了額外的鏈接（路由表條目），這些用戶隨時在線。 通過這樣做，SPROUT 聲稱可以提高 Chord 本身的可靠性和負載分佈。
Whanau 最初在 [23] 中提出，其中 [22] 中的工作包括對性能和安全性的進一步分析和證明以及端到端保證的實施和演示。
在 [1] 中，作者使用引導圖——顯示了DHT 中引入關係的樹，以防禦 女巫攻擊。通過修改感興趣的 DHT Chord 的操作，使每個節點返回它知道的所有節點的地址（包括引入點），作者設計了幾種用於減少女巫攻擊影響的策略。與使用 Chord 上的接近度作為路由（查詢）度量的原始 Chord 不同，該解決方案考慮了多種路由策略，包括多樣性、混合和 zig-zag。作者通過實驗表明，當此類策略在女巫攻擊下運行時，它可用於更有效地執行抗女巫的DHT 查找，而且它的查詢次數將少於普通 Chord 設計所需的查詢數量。
MobID [37] 的設計是一種基於社交網絡的女巫防禦，聲稱可以為移動環境提供強大的防禦，而現有的防禦主要是為點對點網絡設計的，並且基於隨機遊走理論。此外，MobID 使用介數（社交圖中的一種圖論度量）來確定節點的優度，以防禦女巫攻擊。然而，這項工作似乎沒有提供任何可證明的保證。各種方案與文獻中的其他方案之間的比較見表 1 和表 2。
6. 結論
P2P 覆蓋網絡極易受到女巫攻擊，並且由於 P2P 覆蓋的性質，解決女巫攻擊這一問題比以往都難：它不鼓勵安全實施所需的中心化認證機構，而且甚至有時中心化認證機構在 P2P 覆蓋設計中不存在。 本文，主要梳理了用於防禦 P2P 覆蓋中的女巫攻擊的不同方法。 並對不同防禦的假設、特徵和缺點進行比較。
DAOrayaki DAO研究獎金池：
資助地址: 0xCd7da526f5C943126fa9E6f63b7774fA89E88d71
投票進展：DAO Committee 4/7 通過
賞金總量：170 USDC
研究種類：DAO, Social networks, Sybil defenses, Survey
原文作者: Aziz Mohaisen, Joongheon Kim
貢獻者： Natalie, DAOctor @DAOrayaki
原文: The Sybil Attacks and Defenses: A Survey
參考文獻：
[1] George Danezis, Chris Lesniewski-laas, M. Frans Kaashoek, and Ross Anderson. Sybil-resistant dht
routing. In In ESORICS, Lecture Notes in Computer Science, pages 305–318, Berlin, Heidelberg, 2005. Springer.
[2] Petar Maymounkov and David Mazi`eres. Kademlia: A peer-to-peer information system based on the xor metric. In Peter Druschel, M. Frans Kaashoek, and Antony I. T. Rowstron, editors, IPTPS, Lecture Notes in Computer Science, pages 53–65, Berlin, Heidelberg, 2002. Springer.
[3] Ion Stoica, Robert Morris, David R. Karger, M. Frans Kaashoek, and Hari Balakrishnan. Chord: A scalable peer-to-peer lookup service for internet applications. In SIGCOMM, pages 149–160, New York, NY, USA, 2001. ACM.
[4] Yong Wang, Xiao chun Yun, and Yifei Li. Analyzing the characteristics of gnutella overlays. In ITNG, pages 1095–1100, Washington, DC, USA, 2007. IEEE Computer Society.
[5] Vivek Pathak and Liviu Iftode. Byzantine fault tolerant public key authentication in peer-to-peer
systems. Computer Networks, 50(4):579–596, 2006.
[6] John Douceur and Judith S. Donath. The sybil attack. In IPDPS, pages 251–260, Washington, DC, USA, 2002. IEEE.
[7] Haifeng Yu, Chenwei Shi, Michael Kaminsky, Phillip B. Gibbons, and Feng Xiao. Dsybil: Optimal sybil-resistance for recommendation systems. In IEEE Symposium on Security and Privacy, pages 283–298, Washington, DC, USA, May 2009. IEEE Computer Society.
[8] Miguel Castro, Peter Druschel, Ayalvadi J. Ganesh, Antony I. T. Rowstron, and Dan S. Wallach. Secure routing for structured peer-to-peer overlay networks. In OSDI, Berkeley, CA, USA, 2002. USENIX Association.
[9] Atul Adya, William J. Bolosky, Miguel Castro, Gerald Cermak, Ronnie Chaiken, John R. Douceur, Jon Howell, Jacob R. Lorch, Marvin Theimer, and Roger Wattenhofer. Farsite: Federated, available, and reliable storage for an incompletely trusted environment. In OSDI, New York, NY, USA, 2002. USENIX Association.
[10] Jonathan Ledlie and Margo I. Seltzer. Distributed, secure load balancing with skew, heterogeneity and churn. In INFOCOM, pages 1419–1430, Washington, DC, USA, 2005. IEEE.
[11] Fran¸cois Lesueur, Ludovic M´e, and Val´erie Viet Triem Tong. An efficient distributed pki for structured p2p networks. In Proceeding of P2P, pages 1–10, Washington, DC, USA, 2009. IEEE
Computer Society.
[12] Fran¸cois Lesueur, Ludovic M´e, and Val´erie Viet Triem Tong. A distributed certification system for structured p2p networks. In David Hausheer and J¨urgen Sch¨onw¨alder, editors, AIMS, volume 5127 of Lecture Notes in Computer Science, pages 40–52, Berlin, Heidelberg, 2008. Springer.
[13] Fran¸cois Lesueur, Ludovic M´e, and Val´erie Viet Triem Tong. A sybil-resistant admission control coupling sybilguard with distributed certification. In WETICE, pages 105–110, Washington, DC, USA, 2008. IEEE Computer Society.
[14] Fran¸cois Lesueur, Ludovic M´e, and Val´erie Viet Triem Tong. A sybilproof distributed identity
management for p2p networks. In ISCC, pages 246–253, Washington, DC, USA, 2008. IEEE.
[15] Agapios Avramidis, Panayiotis Kotzanikolaou, and Christos Douligeris. Chord-pki: Embedding a
public key infrastructure into the chord overlay network. In Javier Lopez, Pierangela Samarati,
and Josep L. Ferrer, editors, EuroPKI, volume 4582 of Lecture Notes in Computer Science, pages 354–361, Berlin, Heidelberg, 2007. Springer.
[16] Nikita Borisov. Computational puzzles as sybil defenses. In Alberto Montresor, Adam Wierzbicki,
and Nahid Shahmehri, editors, Peer-to-Peer Computing, pages 171–176, Washington, DC,
USA, 2006. IEEE Computer Society.
[17] Haifeng Yu, Phillip B. Gibbons, and Michael Kaminsky. Toward an optimal social network
defense against sybil attacks. In Indranil Gupta and Roger Wattenhofer, editors, PODC, pages
376–377. ACM, 2007.
[18] Haifeng Yu, Phillip B. Gibbons, Michael Kaminsky, and Feng Xiao. Sybillimit: A near-optimal social network defense against sybil attacks. In IEEE Symposium on Security and Privacy, pages 3–17, Washington, DC, USA, 2008. IEEE Computer Society.
[19] Haifeng Yu, Michael Kaminsky, Phillip B. Gibbons, and Abraham Flaxman. SybilGuard: defending against sybil attacks via social networks. In Luigi Rizzo, Thomas E. Anderson, and Nick McKeown, editors, SIGCOMM, pages 267–278, New York, NY, USA, 2006. ACM.
[20] Haifeng Yu, Michael Kaminsky, Phillip B. Gibbons, and Abraham D. Flaxman. Sybilguard: defending against sybil attacks via social networks. IEEE/ACM Trans. Netw., 16(3):576–589, 2008.
[21] Nguyen Tran, Jinyang Li, Lakshminarayanan Subramanian, and Sherman S.M. Chow. Optimal sybil-resilient node admission control. In The 30th IEEE International Conference on Computer Communications (INFOCOM 2011), Shanghai, P.R. China, 2011. IEEE.
[22] Chris Lesniewski-Lass and M. Frans Kaashoek. Wh¯anau: A sybil-proof distributed hash table. In
7th USENIX Symposium on Network Design andImplementation, pages 3–17, Berkeley, CA, USA,
2010. USENIX Association.
[23] C. Lesniewski-Laas. A Sybil-proof one-hop DHT. In Proceedings of the 1st workshop on Social network systems, pages 19–24, New York, NY, USA, 2008. ACM.
[24] Paul F. Syverson, David M. Goldschlag, and Michael G. Reed. Anonymous connections and
onion routing. In IEEE Symposium on Security and Privacy, pages 44–54, Washington, DC, USA,
1997. IEEE Computer Society.
[25] Peng Wang, James Tyra, Eric Chan-tin, Tyson Malchow, Denis Foo Kune, and Yongdae Kim.
Attacking the kad network, 2009.
[26] B.N. Levine, C. Shields, and N.B. Margolin. A survey of solutions to the sybil attack. Technical
report, University of Massachusetts Amherst, Amherst, MA, 2006.
[27] Rodrigo Rodrigues, Barbara Liskov, and Liuba Shrira. The design of a robust peer-to-peer system. In 10th ACM SIGOPS European Workshop, pages 1–10, New York, NY, USA, 2002. ACM.
[28] James Newsome, Elaine Shi, Dawn Song, and Adrian Perrig. The sybil attack in sensor networks: analysis & defenses. In IPSN ’04: Proceedings of the 3rd international symposium on Information processing in sensor networks, pages 259–268, New York, NY, USA, 2004. ACM.
[29] Michael J. Freedman and Robert Morris. Tarzan: a peer-to-peer anonymizing network layer. In
Vijayalakshmi Atluri, editor, ACM Conference on Computer and Communications Security, pages 193–206, Washington, DC, USA, 2002. ACM.
[30] Fabrizio Cornelli, Ernesto Damiani, Sabrina De Capitani di Vimercati, Stefano Paraboschi, and Pierangela Samarati. Choosing reputable servents in a p2p network. In WWW, pages 376–386, New York, NY, USA, 2002. ACM.
[31] Brent ByungHoon Kang, Eric Chan-Tin, Christopher P. Lee, James Tyra, Hun Jeong Kang, Chris Nunnery, Zachariah Wadler, Greg Sinclair, Nicholas Hopper, David Dagon, and Yongdae Kim. Towards complete node enumeration in a peer-to-peer botnet. In Wanqing Li, Willy Susilo, Udaya Kiran Tupakula, Reihaneh Safavi-Naini, and Vijay Varadharajan, editors, ASIACCS, pages 23–34, New York, NY, USA, 2009. ACM.
[32] Frank Li, Prateek Mittal, Matthew Caesar, and Nikita Borisov. Sybilcontrol: practical sybil
defense with computational puzzles. In Proceedings of the seventh ACM workshop on Scalable trusted computing, pages 67–78. ACM, 2012.
[33] Luis von Ahn, Manuel Blum, Nicholas J. Hopper and John Langford. Captcha: Using hard ai problems for security. In Eli Biham, editor, EUROCRYPT, volume 2656 of Lecture Notes in Computer Science, pages 294–311, Berlin, Heidelberg, 2003. Springer.
[34] Jeff Yan and Ahmad Salah El Ahmad. Breaking visual captchas with naive pattern recognition algorithms. In ACSAC, pages 279–291, Washington, DC, USA, 2007. IEEE Computer Society.
[35] N. Tran, B. Min, J. Li, and L. Subramanian. Sybil-resilient online content voting. In NSDI, Berkeley, CA, USA, 2009. USENIX.
[36] Sergio Marti, Prasanna Ganesan, and Hector Garcia-Molina. Dht routing using social links. In IPTPS, pages 100–111, Washington, DC, USA, 2004. IEEE.
[37] Daniele Quercia and Stephen Hailes. Sybil attacks against mobile users: friends and foes to the
rescue. In INFOCOM’10: Proceedings of the 29th conference on Information communications, pages
336–340, Piscataway, NJ, USA, 2010. IEEE Press.
[38] Abedelaziz Mohaisen, Aaram Yun, and Yongdae Kim. Measuring the mixing time of social graphs. In Proceedings of the 10th annual conference on Internet measurement, IMC ’10, pages 383–389,
New York, NY, USA, 2010. ACM.
[39] Bimal Viswanath, Ansley Post, Krishna P. Gummadi, and Alan Mislove. An analysis of social network-based sybil defenses. In SIGCOMM, New York, NY, USA, August 2010. ACM.
[40] George Danezis and Prateek Mittal. SybilInfer: Detecting sybil nodes using social networks. In
The 16th Annual Network & Distributed System Security Conference, Lecture Notes in Computer Science, Berlin, Heidelberg, 2009. Springer-Verlag.
[41] Abedelaziz Mohaisen, Huy Tran, Nicholas Hopper, and Yongdae Kim. Understanding social networks properties for trustworthy computing. In ICDCS Workshops, pages 154–159. IEEE, 2011.
[42] Abedelaziz Mohaisen and Scott Hollenbeck. Improving social network-based sybil defenses by augmenting social graphs. In WISA, 2013.
[43] Abedelaziz Mohaisen, Nicholas Hopper, and Yongdae Kim. Keep your friends close: Incorporating trust into social network-based sybil defenses. In INFOCOM, pages 1943–1951. IEEE, 2011.
[44] Haifeng Yu. Sybil defenses via social networks: a tutorial and survey. ACM SIGACT News, 42(3):80–101, 2011.
本文鏈接：https://www.8btc.com/article/6663623
轉載請註明文章出處
