利用工作量證明的P2P信譽(yù)女巫攻擊防范

李標(biāo)奇，付曉東，2，岳 昆，劉 驪，2，劉利軍，2，馮 勇，2

1(昆明理工大學(xué) 信息工程與自動(dòng)化學(xué)院，昆明 650500)2(昆明理工大學(xué) 云南省計(jì)算機(jī)技術(shù)應(yīng)用重點(diǎn)實(shí)驗(yàn)室，昆明 650500)3(云南大學(xué) 信息學(xué)院，昆明 650091)

1 引 言

對等網(wǎng)絡(luò)(Peer-to-Peer Network)是由許多具備高度匿名性的自治對等體，相互之間發(fā)生諸如文件共享等應(yīng)用而組成的網(wǎng)絡(luò)[1].P2P網(wǎng)絡(luò)通常引入信譽(yù)度量以幫助用戶在眾多不同的資源或服務(wù)中做出更好的選擇.但是，P2P網(wǎng)絡(luò)作為一種基于身份的系統(tǒng)，容易受到來自身份管理相關(guān)攻擊的威脅[2].例如，模仿攻擊是一種典型的基于身份的攻擊，攻擊者將自己偽裝成另一個(gè)身份來實(shí)施攻擊，以此獲利并隱藏真實(shí)身份.此外，攻擊者還可以創(chuàng)建并操縱多個(gè)身份實(shí)施攻擊以實(shí)現(xiàn)其目的，這種攻擊就是女巫攻擊[1，3](Sybil Attack).

女巫攻擊是分布式系統(tǒng)中基于身份的攻擊.攻擊者可以在P2P信譽(yù)系統(tǒng)中創(chuàng)建許多偽造的身份，以操縱目標(biāo)節(jié)點(diǎn)的評分或信譽(yù)值.例如，攻擊者可以通過控制大量女巫節(jié)點(diǎn)(偽造身份節(jié)點(diǎn))多次與目標(biāo)節(jié)點(diǎn)進(jìn)行交互且給予正面評價(jià)以提高目標(biāo)節(jié)點(diǎn)的信譽(yù)值，較高的信譽(yù)將會(huì)為目標(biāo)節(jié)點(diǎn)提供更多服務(wù)請求機(jī)會(huì).女巫攻擊會(huì)對P2P網(wǎng)絡(luò)信譽(yù)系統(tǒng)造成嚴(yán)重破壞.

因此，如何有效抵御P2P信譽(yù)系統(tǒng)中的女巫攻擊成為了一個(gè)重要的問題.目前主要可以通過兩種類型的方法來緩解此問題，分別為資源證明和行為檢測.資源證明要求節(jié)點(diǎn)執(zhí)行單個(gè)實(shí)體需要耗費(fèi)一定資源才能夠完成的任務(wù)，以證明其是擁有獨(dú)立資源的實(shí)體.行為檢測(如SybilGuard[4]和SybilLimit[5])通過關(guān)系網(wǎng)絡(luò)或圖論來檢測可疑節(jié)點(diǎn)，并將這些節(jié)點(diǎn)與正常節(jié)點(diǎn)隔離以消除攻擊者的影響.行為檢測通常需要與特定的場景(如無人駕駛網(wǎng)絡(luò)、社交網(wǎng)絡(luò))結(jié)合，以高效檢測攻擊者.比較而言，資源證明更適合于一般場景下的P2P信譽(yù)系統(tǒng).

為從源頭上抑制女巫攻擊，力圖使攻擊對攻擊者而言不經(jīng)濟(jì)，換言之即讓攻擊的效費(fèi)比最小化，最大限度抑制攻擊.鑒于行為檢測是在攻擊后生效并且依賴于特定的場景，且資源證明方案大多在節(jié)點(diǎn)注冊時(shí)執(zhí)行一次資源消耗驗(yàn)證，很難大幅度提升攻擊者的開銷.因此本文引入具備充分魯棒性PoW(Proof of Work)作為驗(yàn)證任務(wù)，讓新加入節(jié)點(diǎn)在系統(tǒng)接受其身份之前進(jìn)行驗(yàn)證，并設(shè)計(jì)了一種多輪驗(yàn)證機(jī)制來進(jìn)一步降低女巫攻擊的效用.同時(shí)考慮到多輪驗(yàn)證機(jī)制，部分女巫節(jié)點(diǎn)驗(yàn)證難度增加而被放棄，攻擊者采取注冊新節(jié)點(diǎn)的方式來洗白(whitewashing)其攻擊行為的影響.針對次生出的洗白攻擊，在攻擊者的效用函數(shù)中引入洗白攻擊影響因子，并通過理論分析和實(shí)驗(yàn)對比驗(yàn)證了本文防御模型的防范效果.

本文的工作主要包括以下幾點(diǎn)：

1)通過引入工作量證明來實(shí)現(xiàn)在P2P信譽(yù)系統(tǒng)中抵御女巫攻擊以及次生的洗白攻擊，并通過實(shí)驗(yàn)和理論分析驗(yàn)證本方法的有效性.

2)提出了動(dòng)態(tài)調(diào)整難度的驗(yàn)證模型，讓驗(yàn)證時(shí)間隨著節(jié)點(diǎn)的當(dāng)前信譽(yù)動(dòng)態(tài)變化，以給攻擊者帶來更大的攻擊開銷，進(jìn)一步限制女巫攻擊.

3)對防御模型進(jìn)行了理論分析，并使用不同的實(shí)驗(yàn)參數(shù)設(shè)置對模型的防御效果進(jìn)行了全方位的評估.

2 相關(guān)工作

女巫攻擊的目的通常是篡改信譽(yù)系統(tǒng)中目標(biāo)節(jié)點(diǎn)的信譽(yù)值.分布式系統(tǒng)中抵御女巫攻擊的方法大體上可以分為兩種，一類是資源證明，另一類是行為檢測.

2.1 資源證明

中心化證書要求受信任的第三方作為證書頒發(fā)機(jī)構(gòu)(CA)在節(jié)點(diǎn)加入系統(tǒng)之前向其頒發(fā)證書，以確保系統(tǒng)中的每個(gè)節(jié)點(diǎn)都是單個(gè)實(shí)體.CA可能還要求提供現(xiàn)實(shí)世界身份證明，以確保每個(gè)實(shí)體僅持有一個(gè)唯一系統(tǒng)標(biāo)識(shí)符[6].此類解決方案必須是中心化的，由于維護(hù)開銷高，它們很難規(guī)?；瘮U(kuò)展.而且中心化網(wǎng)絡(luò)結(jié)構(gòu)易受單點(diǎn)攻擊或單點(diǎn)故障的影響.E.Friedman在注冊環(huán)節(jié)引入了押金或入場費(fèi)[7].一段時(shí)間后，當(dāng)節(jié)點(diǎn)沒有不良?xì)v史記錄時(shí)，押金將被退還.注冊的過程將給女巫攻擊者帶來較大的開銷，并削弱攻擊者持續(xù)攻擊的動(dòng)力.

2.2 行為檢測

Haifeng Yu基于社交網(wǎng)絡(luò)提出了SybilGuard[3].他們利用惡意節(jié)點(diǎn)可以創(chuàng)建許多身份而身份之間很少建立信任關(guān)系的特征，將女巫節(jié)點(diǎn)和正常節(jié)點(diǎn)之間的關(guān)系圖進(jìn)行切割以削弱攻擊者的影響.Haifeng Yu還提出了SybilGuard的改進(jìn)版本SybilLimit[4]，采用圖來表示社交網(wǎng)絡(luò)的特征以進(jìn)一步限制女巫節(jié)點(diǎn)的數(shù)量.Tianyu Gao通過基于內(nèi)容的方法結(jié)合深度學(xué)習(xí)技術(shù)在在線社交網(wǎng)絡(luò)中檢測到女巫節(jié)點(diǎn)[8].Martin Byrenheid提出了一種領(lǐng)導(dǎo)者選舉算法，以區(qū)分女巫節(jié)點(diǎn)和普通節(jié)點(diǎn)[9].G.Danezis 結(jié)合社交網(wǎng)絡(luò)和貝葉斯理論，提出了SybilInfer[10]，給定節(jié)點(diǎn)之間的關(guān)系結(jié)構(gòu)，使用貝葉斯理論將節(jié)點(diǎn)標(biāo)記為誠實(shí)或不誠實(shí).Pradhan.S提出了一種基于區(qū)塊鏈的P2P資源共享系統(tǒng)安全框架[11]，他們讓區(qū)塊鏈的礦工來監(jiān)視節(jié)點(diǎn)的活動(dòng)，并在區(qū)塊鏈中記錄活動(dòng)日志.這意味著所有活動(dòng)日志都向每個(gè)節(jié)點(diǎn)開放，沒有人可以篡改記錄.如果攻擊者嘗試實(shí)施女巫攻擊，則系統(tǒng)中的任何參與者都會(huì)發(fā)現(xiàn)異常活動(dòng).這些行為檢測模型通過在女巫攻擊期間或之后檢測女巫節(jié)點(diǎn)來抑制攻擊.

對于信譽(yù)系統(tǒng)中的洗白攻擊，主要有兩種方法可以防范[12-14]：

1)將假名與真實(shí)身份綁定.

2)對所有的新加入成員(包括whitewasher)采用無差別的懲罰機(jī)制，提高獲取假名的門檻.

對所有節(jié)點(diǎn)的無差別消耗性驗(yàn)證相當(dāng)于第二種方法中對成員的無差別懲罰，能夠在一定程度上抑制洗白攻擊.

現(xiàn)有的抗女巫攻擊模型存在著一些問題與局限.例如，中心化方法將遇到可擴(kuò)展性和單點(diǎn)故障的問題.行為檢測需要特定的場景依托且在攻擊發(fā)生之后才生效.本文考慮如何抵御一般情況下P2P網(wǎng)絡(luò)中針對信譽(yù)的女巫攻擊.從攻擊者的目的出發(fā)，提升攻擊者攻擊開銷的心理期望從而從源頭抑制攻擊的發(fā)生，因此我們可以采取一些機(jī)制來降低攻擊的經(jīng)濟(jì)性.此外，由于女巫攻擊基于身份的特性，現(xiàn)有方法只能抑制理性攻擊者.即要求攻擊回報(bào)大于開銷的攻擊者，對于不計(jì)開銷的攻擊者很難完全防御[2].因此本文的目標(biāo)是最大程度地減少攻擊的影響.

3 問題定義

在P2P系統(tǒng)中存在許多服務(wù)或資源可供用戶選擇.基于節(jié)點(diǎn)歷史行為的信譽(yù)可幫助用戶做出更好的選擇，越高的信譽(yù)意味著節(jié)點(diǎn)能夠提供越好的服務(wù)或資源.反之，低信譽(yù)節(jié)點(diǎn)將無人問津甚至被系統(tǒng)懲罰.女巫攻擊者的目的就是讓某一個(gè)(些)節(jié)點(diǎn)的信譽(yù)按照攻擊者的期望發(fā)生變化.本文研究中假設(shè)攻擊者的目的是讓某一個(gè)目標(biāo)節(jié)點(diǎn)的信譽(yù)值盡可能高，因此攻擊者將操控女巫節(jié)點(diǎn)與目標(biāo)交互并給予正面評價(jià)，以達(dá)到提升該節(jié)點(diǎn)信譽(yù)的目的.

本文考慮存在一個(gè)女巫攻擊者的P2P資源共享系統(tǒng).其中，系統(tǒng)中參與資源共享的節(jié)點(diǎn)總數(shù)為N，資源提供方定義為有限集P={p1，p2，…}，資源接收方定義為有限集R={r1，r2，…}，系統(tǒng)中的每個(gè)節(jié)點(diǎn)均可以是提供方或接收方.女巫攻擊者及其控制的女巫節(jié)點(diǎn)定義為有限集S={sA，s1，s2，…，sn}，其中s1，s2，…，sn是被sA所控制的女巫節(jié)點(diǎn)，且n?N.假設(shè)sA控制s1，s2，…，sn實(shí)施攻擊的開銷為C，sA，實(shí)施攻擊所 獲取的收益為B.作為攻擊者，期望開銷盡可能低的同時(shí)獲取更高的收益.為了方便量化sA的攻擊效用，我們定義攻擊效用E為：

(1)

隨著E的增長，sA將獲得更好的攻擊效果.我們的目的是要盡可能遏制E的增長，可以從兩個(gè)方面著手實(shí)現(xiàn)這一目標(biāo).一是提升sA的攻擊開銷C，另一方面降低sA的攻擊收益B.就注冊策略來說，大多數(shù)基于難題的驗(yàn)證方法僅提供單次驗(yàn)證(注冊時(shí)驗(yàn)證)，這就意味著攻擊者sA及女巫節(jié)點(diǎn)s1，s2，…，sn只需要付出一次性開銷，且這些開銷可以在未來的收益中均攤.Margolin[15]指出抑制女巫攻擊，執(zhí)行反復(fù)多次驗(yàn)證比僅執(zhí)行單次驗(yàn)證更高效.因此，如果想要提升sA的開銷C，我們需要采用多輪次驗(yàn)證的方式.對于降低攻擊收益B，行為檢測的方法可以找到sA，s1，s2，…，sn等女巫節(jié)點(diǎn)之間的聯(lián)系，以此來限制sA的收益B.同時(shí)通過在多輪驗(yàn)證中引入對攻擊規(guī)模限制的約束機(jī)制，來限制sA的收益，以此增加攻擊者的攻擊難度.

4 基于PoW的女巫攻擊防范模型

任何攻擊的效用都受成本(時(shí)間或金錢)規(guī)模的影響.具有無限資源的攻擊者可以破壞任何基于身份的系統(tǒng)[5].例如，如果女巫攻擊者擁有無限資源，則無論注冊過程中付出多高的代價(jià)，它都可以篡改任意節(jié)點(diǎn)的信譽(yù).因此，本文考慮的防范對象是通常的理智攻擊者，不會(huì)不計(jì)代價(jià)實(shí)施攻擊.

如果沒有資源消耗的證明，那也將沒有辦法驗(yàn)證節(jié)點(diǎn)是否為真正的實(shí)體[16]；Dewan也指出，可以通過讓身份生成耗費(fèi)資源，讓攻擊者無力負(fù)擔(dān)生成多個(gè)身份的高昂代價(jià)，從而抵御女巫攻擊[17].為了使女巫攻擊變得不經(jīng)濟(jì)并通過資源證明抑制攻擊，可以通過要求節(jié)點(diǎn)完成消耗資源的任務(wù)來驗(yàn)證其作為單個(gè)實(shí)體的合法性.由于女巫攻擊者控制系統(tǒng)中的許多女巫節(jié)點(diǎn)，所有女巫節(jié)點(diǎn)單獨(dú)完成任務(wù)的開銷總和將非常大，能夠在很大程度上增加攻擊者的攻擊難度.因此，我們采用資源消耗型的難題作為驗(yàn)證任務(wù)，來防止單個(gè)實(shí)體創(chuàng)造多個(gè)虛假身份的女巫攻擊.采用難題來驗(yàn)證節(jié)點(diǎn)的身份需要滿足以下兩個(gè)原則[3]，一是難題必須同時(shí)發(fā)布給所有節(jié)點(diǎn)，二是難題必須具備難解和容易驗(yàn)證兩個(gè)屬性.此外難題一般分為存儲(chǔ)型和計(jì)算型兩類.存儲(chǔ)型難題要求節(jié)點(diǎn)存儲(chǔ)大量特殊不可壓縮的數(shù)據(jù)，但大量的數(shù)據(jù)傳輸會(huì)給網(wǎng)絡(luò)帶來負(fù)擔(dān)，不利于P2P網(wǎng)絡(luò)的效率；計(jì)算型難題可以采用本地計(jì)算的方式，計(jì)算結(jié)果為一個(gè)值，很容易驗(yàn)證其正確性.受分布式計(jì)算驗(yàn)證的啟發(fā)，我們利用區(qū)塊鏈中驗(yàn)證節(jié)點(diǎn)的方法實(shí)現(xiàn)了對信譽(yù)系統(tǒng)中節(jié)點(diǎn)的資源消耗驗(yàn)證.大多數(shù)區(qū)塊鏈，類似比特幣[注]https：//bitcoin.org/bitcoin.pdf采用了PoW和PoS(proof of stake)來驗(yàn)證節(jié)點(diǎn)的工作量或所持股權(quán)，這些協(xié)議同時(shí)還可以保障區(qū)塊鏈免受女巫攻擊的威脅[18].該類共識(shí)機(jī)制能夠保證節(jié)點(diǎn)在被系統(tǒng)接受之前執(zhí)行資源消耗的驗(yàn)證，基于SHA256散列算法的PoW具備魯棒性，攻擊者很難利用算法漏洞有效減少驗(yàn)證時(shí)間.

4.1 女巫攻擊防范模型框架

我們提出了一種基于PoW的防范女巫攻擊驗(yàn)證模型，模型的驗(yàn)證流程如圖1所示.

圖1 防范模型驗(yàn)證流程Fig.1 Process of Sybil resistant model

本文使用P2P資源共享系統(tǒng)作為研究對象，系統(tǒng)中的每個(gè)節(jié)點(diǎn)都可以作為資源的提供方或者接收方.首先，在系統(tǒng)中隨機(jī)生成初始節(jié)點(diǎn).其次，初始化所有節(jié)點(diǎn)的信譽(yù)值.由于使用布爾值表示信譽(yù)(如果rj成功下載，pi的信譽(yù)值將增加1，否則將增加0)，并使用取平均值法[19]作為信譽(yù)值的匯總方法.因此，最合適的節(jié)點(diǎn)信譽(yù)初始值為0.5(0和1的平均值).另一方面，為了使所有節(jié)點(diǎn)根據(jù)初始值公平地累積信譽(yù)，我們假設(shè)所有節(jié)點(diǎn)(正常節(jié)點(diǎn)，攻擊者和女巫節(jié)點(diǎn))的初始信譽(yù)值為0.5，即：

Repnormal=Repattacker=RepSybil=0.5

(2)

隨后，節(jié)點(diǎn)之間將隨機(jī)兩兩組合生成交易對.每個(gè)交易對都有提供方和接收方兩種角色.節(jié)點(diǎn)的交易對集為TX={tx1，tx2，…}，tx=(pi，rj)，每個(gè)tx將生成pi指向rj的信譽(yù)值Rep，Rep將獲取的實(shí)時(shí)信譽(yù)增長取平均自累計(jì).例如，如果某一個(gè)節(jié)點(diǎn)e作為提供方參與了m個(gè)交易對的生成，在每一次交易中e得到了Repi(i=1，2，…，m)的信譽(yù)值，按照信譽(yù)值平均計(jì)算法則，則e的當(dāng)前信譽(yù)為：

(3)

在評價(jià)模型防范性能前，需要量化攻擊者的攻擊效果.本文定義EA表示攻擊者sA的攻擊效用，假設(shè)單個(gè)節(jié)點(diǎn)的平均驗(yàn)證消耗時(shí)間為ti，攻擊者sA需要消耗nti(n為女巫節(jié)點(diǎn)的數(shù)量)完成所有女巫節(jié)點(diǎn)的驗(yàn)證，也即sA的攻擊開銷.sA通過控制女巫節(jié)點(diǎn)來提升目標(biāo)節(jié)點(diǎn)的信譽(yù)值，假設(shè)攻擊者sA自身為目標(biāo)節(jié)點(diǎn)，每當(dāng)女巫節(jié)點(diǎn)作為提供方與sA生成交易對時(shí)，無論交互結(jié)果如何，女巫節(jié)點(diǎn)都會(huì)給予sA的正面的信譽(yù)評價(jià)，以達(dá)到提升目標(biāo)節(jié)點(diǎn)信譽(yù)的目的.因此，sA的信譽(yù)增量ΔRepattacker即可表示攻擊者sA的攻擊收益，參照式(1)的效用函數(shù)，攻擊者sA的效用可以表示為：

(4)

隨著ΔRepattacker的增大或ti的減小，EA將增大，意味著sA的攻擊效果良好，模型防范效果不佳.通常，sA的攻擊開銷C隨著攻擊者控制的女巫節(jié)點(diǎn)數(shù)量n呈線性增長.為了更加有效防范女巫攻擊，本文采用多輪次動(dòng)態(tài)難度調(diào)整的PoW驗(yàn)證策略.

多輪次驗(yàn)證使用PoW每隔固定時(shí)間間隔T對所有節(jié)點(diǎn)同時(shí)執(zhí)行驗(yàn)證，并根據(jù)節(jié)點(diǎn)的當(dāng)前信譽(yù)值動(dòng)態(tài)調(diào)整驗(yàn)證難度.由于sA的目的是提高自身的信譽(yù)值，因此我們設(shè)置信譽(yù)值的不同梯度分化讓PoW的驗(yàn)證難度隨信譽(yù)增加而增加.隨著信譽(yù)的提高，開銷C會(huì)大幅度提升，EA會(huì)減小.該機(jī)制對于非女巫節(jié)點(diǎn)，只在合理范圍內(nèi)增加很少的時(shí)間消耗，不影響正常節(jié)點(diǎn)的活動(dòng).

為了盡可能減少驗(yàn)證難度的提升對普通節(jié)點(diǎn)的影響，每輪驗(yàn)證之間的時(shí)間間隔T應(yīng)設(shè)置為遠(yuǎn)大于節(jié)點(diǎn)執(zhí)行一次驗(yàn)證的平均時(shí)間.對于攻擊者sA，女巫節(jié)點(diǎn)幾乎不可能全部在T以內(nèi)完成驗(yàn)證，這將導(dǎo)致一部分女巫節(jié)點(diǎn)無法完成一輪內(nèi)的驗(yàn)證.在本模型中，在一輪時(shí)間間隔內(nèi)無法完成驗(yàn)證的節(jié)點(diǎn)將被標(biāo)記為可疑節(jié)點(diǎn).在下一輪的驗(yàn)證中，可疑節(jié)點(diǎn)的驗(yàn)證難度將提高一個(gè)單位，這將在下一輪驗(yàn)證中給予sA更大的驗(yàn)證開銷，并逐漸形成一個(gè)惡性循環(huán).算法描述如下：

算法1.多輪次動(dòng)態(tài)難度調(diào)節(jié)驗(yàn)證算法.

輸入：節(jié)點(diǎn)集合N，節(jié)點(diǎn)初始信譽(yù)Repnode=0.5，驗(yàn)證難度d=init_d，驗(yàn)證時(shí)間間隔T

輸出：通過驗(yàn)證節(jié)點(diǎn)集合N*，可疑節(jié)點(diǎn)集合S*

IFRepnode≥0.5THEN

d=init_d+1

FOREACHnodei∈NDO

PoW驗(yàn)證(難度init_d)

IF節(jié)點(diǎn)驗(yàn)證時(shí)間ti

d=init_d

ELSETHEN

S*←nodei

d=init_d+1

ENDIF

ENDFOR

IF本輪驗(yàn)證時(shí)間≥TTHEN

執(zhí)行下輪驗(yàn)證

ENDIF

RETURNN*ANDS*

考慮到sA會(huì)拋棄被標(biāo)記為可以節(jié)點(diǎn)增加了驗(yàn)證難度的女巫節(jié)點(diǎn)，轉(zhuǎn)而重新注冊新的女巫節(jié)點(diǎn)加入攻擊，實(shí)施洗白攻擊.本文將給出攻擊者實(shí)施洗白攻擊時(shí)重新生成女巫節(jié)點(diǎn)的速率作為模型考察洗白攻擊的指標(biāo)，并將生成節(jié)點(diǎn)速率納入到攻擊者效用函數(shù)中，進(jìn)而分析和實(shí)驗(yàn)驗(yàn)證模型防范洗白攻擊的效果.

4.2 女巫攻擊防范模型理論分析

我們將在接下來的部分中對上述過程作理論分析.我們假設(shè)P2P資源共享系統(tǒng)中的節(jié)點(diǎn)總數(shù)為N，女巫節(jié)點(diǎn)(包括sA)占節(jié)點(diǎn)總數(shù)的比例為S，ti，滿足驗(yàn)證難題函數(shù)f(d)，d為驗(yàn)證難度：

ti=f(d)

(5)

因此，sA控制所有女巫節(jié)點(diǎn)完成驗(yàn)證的平均時(shí)間開銷是：

Ts=NSti=NS·f(d)

(6)

為了降低對正常節(jié)點(diǎn)的影響且能夠一定程度限制sA，考慮極限情況，ti需滿足：

f(d)≤ti≤NS·f(d)

(7)

在單輪驗(yàn)證中，無法在ti時(shí)間內(nèi)完成驗(yàn)證的女巫節(jié)點(diǎn)個(gè)數(shù)為：

(8)

這部分節(jié)點(diǎn)將被系統(tǒng)標(biāo)記為可疑節(jié)點(diǎn)，并在下一輪驗(yàn)證中執(zhí)行增加1單位的驗(yàn)證難度，即以d+1難度執(zhí)行下輪驗(yàn)證.因此，在下輪驗(yàn)證中攻擊者sA的平均驗(yàn)證時(shí)間開銷是：

(9)

考慮與不引入難度增加機(jī)制比較，攻擊者的平均驗(yàn)證時(shí)間開銷增加了：

(10)

由于驗(yàn)證算法是PoW，隨著難度增加，驗(yàn)證時(shí)間近似指數(shù)級(jí)增長(實(shí)驗(yàn)部分給出)，故f(d+1)-f(d)也隨著d呈現(xiàn)指數(shù)增長.

(11)

(12)

(13)

此后sA的攻擊效用為：

(14)

Su=Vs·ti

(15)

等于sA新注冊的女巫節(jié)點(diǎn)數(shù)量，NS在后續(xù)輪次中為前次驗(yàn)證中剩余的女巫節(jié)點(diǎn)數(shù)量.因此，sA在每一輪驗(yàn)證后需要保證此時(shí)的Vs≥V°s才能夠在下一輪驗(yàn)證時(shí)維持本輪的攻擊規(guī)模.

從實(shí)際情況考慮，攻擊者實(shí)施攻擊的收益為正，B≥0，C<∞，且B作為信譽(yù)增量，存在一定范圍內(nèi)的隨機(jī)性，故E不存在確定的最小取值.為了達(dá)到更好的防范效果，可以讓攻擊者的開銷C盡可能大.通常文獻(xiàn)[6-8]方法對節(jié)點(diǎn)采用注冊時(shí)一次性驗(yàn)證的機(jī)制，其攻擊者開銷C隨著操控節(jié)點(diǎn)數(shù)量n呈線性增長，而多輪動(dòng)態(tài)驗(yàn)證難度調(diào)節(jié)機(jī)制讓C隨著n呈指數(shù)增長，由此我們可以獲得更大的C以及更小的EA.

這里將給出PoW作為驗(yàn)證函數(shù)的f(d)隨著d是呈現(xiàn)指數(shù)增長趨勢的證明.PoW方案是基于窮舉搜索目標(biāo)Hash值，采用的是十六進(jìn)制表示的SHA256.我們假設(shè)Hash值總共有l(wèi)位，查找目標(biāo)Hash的難度是d(目標(biāo)Hash前d位均為0)，考慮Hash函數(shù)的特性，查找目標(biāo)Hash的概率近似服從均勻分布，因此，找到目標(biāo)Hash的概率H可以表示為：

(16)

考慮極限情況：

·第1次嘗試就找到了目標(biāo)Hash，查找次數(shù)為1

·遍歷完所有的可能Hash值才找到目標(biāo)Hash，查找次數(shù)為24l-24(l-d)

(17)

因此，PoW函數(shù)的時(shí)間復(fù)雜度函數(shù)T(n)為：

(18)

綜上，PoW是一種指數(shù)規(guī)模的算法，時(shí)間規(guī)模隨著難度呈指數(shù)增長.這可以在正常節(jié)點(diǎn)和女巫攻擊者之間提供更多的時(shí)間消耗差異.另一方面，SHA256為PoW算法提供了足夠的魯棒性.攻擊者很難通過破解PoW來減少驗(yàn)證時(shí)間開銷.

5 實(shí)驗(yàn)研究

本節(jié)展示實(shí)驗(yàn)結(jié)果，以說明本文提出的女巫攻擊防范模型的有效性.所有實(shí)驗(yàn)均在配備Intel Core i7 3.6 GHz CPU和16 GB RAM的PC上進(jìn)行，該算法的開發(fā)語言為Python3.7，開發(fā)平臺(tái)為為PyCharm CE.

本文主要通過攻擊者的效用EA和開銷C來研究模型的防范效果.實(shí)驗(yàn)中，設(shè)置了10000個(gè)節(jié)點(diǎn)模擬P2P資源共享系統(tǒng)下的女巫攻擊.在攻擊模型中，假設(shè)一次攻擊中僅存在一個(gè)攻擊者.且基于簡單的女巫攻擊策略，即女巫節(jié)點(diǎn)之間不相互交流.

實(shí)驗(yàn)首先生成10000個(gè)節(jié)點(diǎn)，包括普通節(jié)點(diǎn)，攻擊者和女巫節(jié)點(diǎn).參考Tien Tuan[20]的女巫攻擊防范模型的參數(shù)設(shè)置，我們假設(shè)只有一個(gè)攻擊者sA，而女巫節(jié)點(diǎn)的比例S在1%～5%之間變化.信譽(yù)值初始化后，隨機(jī)選擇兩個(gè)節(jié)點(diǎn)來構(gòu)建交易對tx=(pi，rj)，并為資源提供方P={p1，p2，…}生成信譽(yù)值.

在生成tx的同時(shí)，每個(gè)節(jié)點(diǎn)將每隔固定時(shí)間執(zhí)行一次PoW驗(yàn)證.為了確保每個(gè)正常節(jié)點(diǎn)都可以在合法時(shí)間內(nèi)完成驗(yàn)證，增加模型的容錯(cuò)性，同時(shí)能夠有力限制女巫攻擊的規(guī)模，本模型中取間隔時(shí)間T=50ti作為多輪時(shí)間間隔驗(yàn)證的限制指標(biāo).

5.1 效用函數(shù)設(shè)置

ti的值由多次實(shí)驗(yàn)求平均值獲得.如圖2所示，虛線是通過線性回歸擬合散點(diǎn)圖得到的時(shí)間隨難度增長變化趨勢，R2接近1.0表示PoW難度與ti的關(guān)系近似指數(shù)分布.

圖2 PoW驗(yàn)證時(shí)間與驗(yàn)證難度的關(guān)系Fig.2 Relationship between verification time and verification difficulty

在NS=500(女巫節(jié)點(diǎn)數(shù))的情況下，第1輪驗(yàn)證Su=450；f(d)在d=5的情況下驗(yàn)證平均時(shí)間為2s(100次實(shí)驗(yàn)平均值).因此，攻擊者注冊效率臨界值為V°s=225；由于NS∈(100，200，300，400，500)，即V°s∈(25，225)，考慮實(shí)際實(shí)驗(yàn)值EA∈(0，2)，故a=0.004規(guī)格化Vs較為合適，此時(shí)用于評估模型的效用函數(shù)為：

(19)

5.2 女巫攻擊防范效果

為了驗(yàn)證防范模型對攻擊者sA的防范效果，本文先考察了隨著攻擊規(guī)模的增長(女巫節(jié)點(diǎn)占比1%～5%).如圖3所示，當(dāng)sA未采取洗白攻擊策略時(shí)(Vs=0)，攻擊者效用EA的變化.

圖3 攻擊效用隨攻擊者控制節(jié)點(diǎn)占比的變化Fig.3 Effectiveness changes with the proportion of Sybil nodes

攻擊者sA提升女巫節(jié)點(diǎn)數(shù)量能夠更有效地實(shí)施攻擊，然而在本模型中，隨著S的增加，EA表現(xiàn)出顯著的下降趨勢.由于每個(gè)女巫節(jié)點(diǎn)都必須執(zhí)行驗(yàn)證難題，因此女巫節(jié)點(diǎn)的時(shí)間消耗都將累加到攻擊者sA上，故C將隨著S線性增長，但sA的信譽(yù)值不可能隨時(shí)間消耗而線性增長，因此EA將呈現(xiàn)下降趨勢.

5.3 洗白攻擊防范效果

為驗(yàn)證模型對女巫攻擊中的洗白攻擊防范效果，對比不同Vs下防御模型對EA的影響，我們選取Vs=0，112.5，225，337.5，500 5種情況，(S=0.05，V°s=225)，如圖4所示，在sA經(jīng)歷5輪驗(yàn)證下觀察EA的變化.

Vs=0即sA未實(shí)施洗白攻擊的情況相較于其它實(shí)施洗白攻擊的情況，EA在顯著更高水平范圍內(nèi)波動(dòng)；當(dāng)Vs>V°s以后，EA波動(dòng)范圍水平更低，由于此時(shí)sA生成新女巫節(jié)點(diǎn)后，女巫節(jié)點(diǎn)數(shù)量大于原始規(guī)模，控制更多的節(jié)點(diǎn)意味著更高的時(shí)間開銷，在ΔRepattacker變化不大的情況下，EA相較于之前會(huì)更低.

圖4 不同Vs情況下5輪驗(yàn)證內(nèi)的效用變化Fig.4 Effectiveness changes within 5 rounds of verification under different Vs situations

5.4 動(dòng)態(tài)難度變化防范效果

在引入驗(yàn)證難度動(dòng)態(tài)變化機(jī)制時(shí)，要避免對正常節(jié)點(diǎn)的驗(yàn)證產(chǎn)生過大影響.因此，本文考察隨著攻擊規(guī)模S的增長，正常節(jié)點(diǎn)和女巫攻擊者的時(shí)間消耗變化趨勢(如圖5所示).

圖5 攻擊者與正常節(jié)點(diǎn)的時(shí)間消耗變化Fig.5 Changes in time consumption between attacker and normal nodes

隨著S的增加，正常節(jié)點(diǎn)的驗(yàn)證時(shí)間消耗保持在較低的穩(wěn)定水平，女巫攻擊者的時(shí)間消耗顯著增加.說明了動(dòng)態(tài)驗(yàn)證難度調(diào)整機(jī)制對正常節(jié)點(diǎn)的影響微乎其微.

另一方面，我們需要研究動(dòng)態(tài)難度調(diào)整機(jī)制是否有效地影響攻擊者sA.如圖6所示，這里我們使用恒定難度和動(dòng)態(tài)難度兩種情況下的攻擊者效用進(jìn)行比較.在動(dòng)態(tài)難度的情況下，我們假設(shè)如果當(dāng)前節(jié)點(diǎn)實(shí)時(shí)的信譽(yù)值大于或等于0.5，則該節(jié)點(diǎn)的下輪驗(yàn)證難度將增1個(gè)單位.

圖6 動(dòng)態(tài)難度與難度不變的情況下攻擊效用變化Fig.6 Changes of effectiveness in dynamic difficulty and static difficulty

實(shí)驗(yàn)結(jié)果表明，在攻擊規(guī)模變化的過程中，采用動(dòng)態(tài)難度調(diào)節(jié)時(shí)的攻擊者效用顯著低于采用恒定難度時(shí)的攻擊者效用.因此，動(dòng)態(tài)難度調(diào)節(jié)機(jī)制對攻擊者sA的效用有著更為顯著影響.

5.5 多輪驗(yàn)證防范效果

為了驗(yàn)證多輪驗(yàn)證相較于傳統(tǒng)單次驗(yàn)證的優(yōu)勢，本文在這兩者之間進(jìn)行了對比實(shí)驗(yàn).我們在單次和多輪驗(yàn)證情況下采集了不同難度值下的平均效用(如圖7所示).

圖7 單次驗(yàn)證與多輪驗(yàn)證情況下攻擊效用變化Fig.7 Changes of effectiveness in once and multiple rounds of verification

隨著攻擊規(guī)模增長，多輪驗(yàn)證下的攻擊效用始終維持在較低水平，單次驗(yàn)證隨著S增長，效用將逐步降低，多輪驗(yàn)證在攻擊規(guī)模不是很高的情況下對攻擊者有更顯著的防范效果.綜合考慮，多輪驗(yàn)證較單次驗(yàn)證能夠更好地防范女巫攻擊.

6 總 結(jié)

本文針對P2P信譽(yù)系統(tǒng)中防范女巫攻擊存在的驗(yàn)證力度不足及防御滯后的問題，通過引入PoW作為驗(yàn)證難題來增加女巫攻擊者的攻擊開銷，提出了一種針對P2P信譽(yù)系統(tǒng)的女巫攻擊以及次生的洗白攻擊的防范模型.我們采用固定時(shí)間間隔和動(dòng)態(tài)難度調(diào)整的多輪驗(yàn)證來進(jìn)一步限制攻擊者，增加其攻擊開銷，并從理論和實(shí)驗(yàn)的角度驗(yàn)證了模型的有效性.

盡管我們進(jìn)行了多次實(shí)驗(yàn)以獲取平均數(shù)據(jù)，但由于Hash計(jì)算的隨機(jī)性，仍然存在一些實(shí)驗(yàn)誤差.未來的工作包括合理地調(diào)整間隔時(shí)間以更有效地限制攻擊者的行為，以及調(diào)整模型以應(yīng)對系統(tǒng)中存在多個(gè)不同的女巫攻擊者的情況.