王 闖,管 剛,焦樹國(guó)
(軍事經(jīng)濟(jì)學(xué)院襄樊分院計(jì)算機(jī)教研室,襄樊441118)
信譽(yù)機(jī)制的需求是伴隨著P2P的迅猛發(fā)展而產(chǎn)生的。在P2P應(yīng)用中,F(xiàn)reeRiding(搭便車)現(xiàn)象相當(dāng)突出,部分節(jié)點(diǎn)在節(jié)點(diǎn)間互享資源的時(shí)候,只享受服務(wù)而不提供服務(wù)。如在Gnutella中70%的節(jié)點(diǎn)不共享文件,而50%的文件請(qǐng)求由1%最好的節(jié)點(diǎn)提供服務(wù)[1]。這些最好的節(jié)點(diǎn)成了新形勢(shì)下的服務(wù)器,這顯然不符合研制P2P的初衷。因此,很早就有人提出需要建立一個(gè)可靠的信譽(yù)機(jī)制以限制或阻止FreeRiding,而這種機(jī)制必須要為正確服務(wù)的節(jié)點(diǎn)建立高的信譽(yù),獲得一些特權(quán),以鼓勵(lì)它繼續(xù)這種行為;與之對(duì)應(yīng),對(duì)惡意服務(wù)的節(jié)點(diǎn)進(jìn)行懲罰,直到將它完全屏蔽在P2P應(yīng)用之外。
當(dāng)前存在的信譽(yù)模型可以分為典型的四類。即CAs、社會(huì)網(wǎng)絡(luò)、概率估計(jì)和博弈理論[2]。CAs(Certificate Agents)模型以CA做類似中央服務(wù)器式的服務(wù),與P2P的分布式理念相左,可以基本排除;社會(huì)網(wǎng)絡(luò)的計(jì)算過程需要從所有節(jié)點(diǎn)獲取信息,雖然也通過某些近似方法作出改進(jìn),但開銷仍然太大;概率估計(jì)模型開銷相對(duì)較小,但在初始階段可靠性不高;博弈應(yīng)用于信譽(yù)模型的理論比較少,單次博弈可以簡(jiǎn)單實(shí)現(xiàn),但是連續(xù)博弈難度比較大,它需要仲裁機(jī)構(gòu)(中央服務(wù)器)的支持。后三類模型的優(yōu)劣比較見表 1[3]。
表1 三類信譽(yù)模型比較
通過以上的分析比較,筆者采用符合P2P特點(diǎn)的結(jié)構(gòu)化純分布式的概率估計(jì)模型——FTrust來構(gòu)建自己的信譽(yù)模型。
FTrust以極大似然估計(jì)理論作為理論基礎(chǔ),極大似然估計(jì)理論的工作原理如下:
節(jié)點(diǎn)Pi通過路由協(xié)議找到目標(biāo)節(jié)點(diǎn)Pj,想從Pj處獲得服務(wù),而Pj正確服務(wù)的概率為全局值θj。Pi詢問第三方節(jié)點(diǎn)Pk關(guān)于Pj的信譽(yù)值,Pk說謊的可能為1k,如果每一個(gè)被詢問的第三方節(jié)點(diǎn)回饋信息{0,1}用隨機(jī)變量Yk表示,則Yk符合公式1所示的分布率(1表示Pk聲明Pj會(huì)正確服務(wù),0表示不會(huì)):
一次對(duì)目標(biāo)節(jié)點(diǎn)Pj詢問的所有反饋事件為Y1、Y2…Yk這幾個(gè)隨機(jī)變量的取值,其聯(lián)合分布概率為 P(Y1=y1,Y2=y2,…Yk=yk),此式是關(guān)于自變量 θj的方程,記作 L(θj)。Zoran Despotovic[4]直接給出L(θj)的計(jì)算式如下:
當(dāng) θj變化時(shí),L(θj)跟著變化,當(dāng) L(θj)取得最大值時(shí),θj就是對(duì)Pi來說Pj正確服務(wù)的概率。θj的大小,就是Pi用來決定是否從Pj獲取服務(wù)的依據(jù)。但很明顯,公式2成立的條件是Y1、Y2…Yk這幾個(gè)隨機(jī)變量相互獨(dú)立。但在文獻(xiàn)[4]中,這種條件不明顯成立。
現(xiàn)實(shí)生活中,興趣愛好相同或相近的人很容易形成一個(gè)團(tuán)體,而這個(gè)團(tuán)體是自適應(yīng)的,既可以剔除舊成員,也可以增加新成員。當(dāng)某個(gè)成員變得對(duì)此團(tuán)體有所傷害的時(shí)候,會(huì)被其他成員探知,并通過一定的手段進(jìn)行懲罰,直到最后遭到團(tuán)隊(duì)的摒棄;當(dāng)外部節(jié)點(diǎn)通過它自身的努力,符合團(tuán)隊(duì)加入條件時(shí),可以獲取團(tuán)隊(duì)資格,而一旦成功,則可以享受與其他團(tuán)隊(duì)成員相同的便利;團(tuán)體成員之間,更傾向于坦誠(chéng)相待,互通有無,以增加團(tuán)體的吸引力,吸收新的團(tuán)員;團(tuán)隊(duì)成員更加傾向于真實(shí)服務(wù)和推薦。
基于以上的思考,F(xiàn)Trust引入團(tuán)體概念,設(shè)置團(tuán)員之間坦誠(chéng)相待,使公式2中的隨機(jī)變量互相獨(dú)立變成可能,等號(hào)可以成立。通過設(shè)立Trans鏈表,設(shè)置Friends節(jié)點(diǎn),保證各事件的獨(dú)立性。在此基礎(chǔ)之上,利用極大似然估計(jì)提供的計(jì)算方法,可以得到一個(gè)比較滿意的信譽(yù)機(jī)制效能。
FTrust重疊網(wǎng)絡(luò)從無到有的過程是這樣的。一開始網(wǎng)絡(luò)中只有若干獨(dú)立節(jié)點(diǎn),每個(gè)節(jié)點(diǎn)都可以看作一個(gè)最小形式的團(tuán)隊(duì)。節(jié)點(diǎn)對(duì)其他節(jié)點(diǎn)來說都是新的,沒有任何信譽(yù)值可言,為了使他們之間能產(chǎn)生交互,使FTrust運(yùn)轉(zhuǎn)起來,設(shè)有一個(gè)默認(rèn)的信譽(yù)值(TRUST_DEFAULT_VALUE)。當(dāng)新節(jié)點(diǎn)以這個(gè)默認(rèn)值進(jìn)行了一定次數(shù)的傳輸之后,就可以依據(jù)過往傳輸記錄,計(jì)算并存儲(chǔ)相應(yīng)節(jié)點(diǎn)的信譽(yù)值。依據(jù)信譽(yù)值大小是否超過閾值TRUST_THRESHOLD_FRIEND,決定目標(biāo)節(jié)點(diǎn)是否能成為自己的伙伴節(jié)點(diǎn)。這樣,慢慢的伙伴之間就構(gòu)成了一個(gè)團(tuán)隊(duì)。
在將來的傳輸過程中,同一團(tuán)隊(duì)成員之間相互完全信賴,而不同的團(tuán)隊(duì)成員之間的傳輸需求,則依靠本團(tuán)隊(duì)成員的推薦或默認(rèn)信譽(yù)值,以決定是否進(jìn)行傳輸。記錄傳輸結(jié)果,更新信譽(yù)值。團(tuán)隊(duì)通過其成員與外界的交互作用,可以吸納新的團(tuán)員。另外,本團(tuán)隊(duì)內(nèi)成員之間的傳輸也要記錄,當(dāng)出現(xiàn)錯(cuò)誤的傳輸時(shí),需要更新自己對(duì)目標(biāo)的信譽(yù)值,并廣播這種錯(cuò)誤,讓其它成員也對(duì)這種錯(cuò)誤傳輸有所感知,同時(shí)更新它們自己對(duì)目標(biāo)的信譽(yù)值。當(dāng)伙伴的傳輸錯(cuò)誤積累到一定程度時(shí),請(qǐng)求服務(wù)節(jié)點(diǎn)將目標(biāo)節(jié)點(diǎn)從伙伴列表中刪除,然后廣播通知其他的伙伴,將目標(biāo)節(jié)點(diǎn)的錯(cuò)誤行為廣播。接收到廣播的節(jié)點(diǎn)進(jìn)行自己的處理:或者完全信任廣播將目標(biāo)清除出團(tuán)隊(duì),或者降低目標(biāo)節(jié)點(diǎn)的信譽(yù)值。前者的作用比較直接,但容易被惡意節(jié)點(diǎn)利用;后者反應(yīng)雖然慢,但同樣能將錯(cuò)誤服務(wù)的節(jié)點(diǎn)驅(qū)除出團(tuán)隊(duì)。后者也伴生一個(gè)問題:如果惡意節(jié)點(diǎn)之間構(gòu)成共謀關(guān)系,互相協(xié)商對(duì)某個(gè)正常節(jié)點(diǎn)進(jìn)行詆毀。這種情況下,如果惡意節(jié)點(diǎn)占小部分,則它們會(huì)被驅(qū)除;否則,慢慢的會(huì)被其他正常節(jié)點(diǎn)與之發(fā)生傳輸時(shí)感知,從而主動(dòng)離開原團(tuán)隊(duì)。這樣,原團(tuán)隊(duì)就成了一個(gè)純的惡意節(jié)點(diǎn),對(duì)團(tuán)隊(duì)外部的節(jié)點(diǎn)無影響。
FTrust將作為信譽(yù)機(jī)制,實(shí)現(xiàn)P2P路由協(xié)議之上,構(gòu)成重疊網(wǎng)絡(luò)。Kademlia[5]是應(yīng)用于 eMule、Bit-Torrent、BitComet等軟件中成熟的一種結(jié)構(gòu)化純分布式P2P路由協(xié)議,經(jīng)受住了實(shí)際檢驗(yàn)。將FTrust構(gòu)建于Kademlia之上,控制文件下載的過程,幫助信譽(yù)值傳播。在安全性方面,Kademlia中節(jié)點(diǎn)經(jīng)過單向哈希生成ID標(biāo)記,在P2P應(yīng)用中自然就擁有了SHA-1單向哈希的保護(hù),防止惡意節(jié)點(diǎn)冒充,減少tamper的可能。同時(shí),因?yàn)镵ademlia中通過節(jié)點(diǎn)記錄相互存在的算法可以抵抗一些基本的DoS(拒絕服務(wù))攻擊。另外,F(xiàn)Trust通過團(tuán)隊(duì)的設(shè)立,降低collusion的發(fā)生。而 Free riding和 White washing(洗黑錢)節(jié)點(diǎn)跟新加入的節(jié)點(diǎn)一樣,沒有利用到團(tuán)隊(duì)提供給自己的便利,沒有利益可圖。
FTrust每個(gè)節(jié)點(diǎn)擁有一個(gè)Trans表,里面保存一定數(shù)目與之發(fā)生過傳輸?shù)墓?jié)點(diǎn)信息,包括正確傳輸和錯(cuò)誤傳輸?shù)拇螖?shù),以及一個(gè) Friends標(biāo)識(shí)位。Friends節(jié)點(diǎn)擁有很高的權(quán)限,本地節(jié)點(diǎn)無條件接受Friends節(jié)點(diǎn)的服務(wù)或推薦。一個(gè)包含 FTrust的P2P文件共享應(yīng)用流程如圖1所示。
圖1 FTrust流程
第①步,節(jié)點(diǎn)i發(fā)出一個(gè)文件搜索請(qǐng)求,請(qǐng)求關(guān)鍵字為fname的文件。第②步,Kademlia路由協(xié)議返回那些聲稱自己擁有fname文件的節(jié)點(diǎn)。節(jié)點(diǎn)i暫存這些節(jié)點(diǎn)信息,將這些節(jié)點(diǎn)記為集合[pa]。第③步,節(jié)點(diǎn)i向[pa]中的所有節(jié)點(diǎn)發(fā)送文件請(qǐng)求。第④步,[pa]中的節(jié)點(diǎn)返回文件名及該文件的SHA-1標(biāo)識(shí)碼。節(jié)點(diǎn)i比較這些標(biāo)識(shí)碼,剔除那些與大多數(shù)標(biāo)識(shí)碼不同的節(jié)點(diǎn),縮減備選節(jié)點(diǎn)集合記[pb]。第⑤步,詢問集合[pb]中各節(jié)點(diǎn)的信譽(yù)值。第⑥步,通過信譽(yù)機(jī)制,得到各節(jié)點(diǎn)信譽(yù)值。節(jié)點(diǎn)i取信譽(yù)值最大的幾個(gè)記為集合[pc]。第⑦步,節(jié)點(diǎn)i向[pc]中節(jié)點(diǎn)發(fā)送文件下載請(qǐng)求。第⑧步,目標(biāo)節(jié)點(diǎn)返回對(duì)應(yīng)文件或文件塊。第⑨步,節(jié)點(diǎn)i對(duì)獲得的文件或文件塊進(jìn)行單項(xiàng)哈希,得到SHA-1標(biāo)識(shí)碼,與之前得到的標(biāo)識(shí)碼進(jìn)行比較,若相同則表明是正確傳輸,提升目標(biāo)節(jié)點(diǎn)的信譽(yù)值;否則是錯(cuò)誤傳輸,則降低目標(biāo)節(jié)點(diǎn)的信譽(yù)值,然后從[pc]中選擇另外的節(jié)點(diǎn)執(zhí)行步驟⑦→⑨,如果仍然不成功,則選擇集合[pb]-[pc]中的節(jié)點(diǎn)執(zhí)行步驟⑦→⑨,若仍不成功,則放棄。
⑤⑥⑨是FTrust在一般P2P應(yīng)用基礎(chǔ)上新加入的步驟,其中⑤⑥兩步利用了極大似然估計(jì)的方法,第⑨步Renew表的時(shí)候,明確錯(cuò)誤付出的代價(jià)比成功得到的利益要大,目的是懲罰惡意行為。
設(shè)置50個(gè)節(jié)點(diǎn),其中10個(gè)惡意節(jié)點(diǎn),40個(gè)善意節(jié)點(diǎn)。善意節(jié)點(diǎn)總是正確服務(wù)并正確推薦,而惡意節(jié)點(diǎn)則相反。測(cè)試程序隨機(jī)讓兩個(gè)節(jié)點(diǎn)之間發(fā)生傳輸(節(jié)點(diǎn)1和節(jié)點(diǎn)2),統(tǒng)計(jì)數(shù)據(jù)total trans(總有效傳輸數(shù)目)加一。節(jié)點(diǎn)1用FTrust機(jī)制詢問它所知道的關(guān)于節(jié)點(diǎn)2的信譽(yù)值,然后根據(jù)FTrust的策略選擇是否從節(jié)點(diǎn)2獲取服務(wù)。如果決定獲取,又如果服務(wù)結(jié)果是成功,則統(tǒng)計(jì)數(shù)據(jù)succ增加一,若失敗,則統(tǒng)計(jì)數(shù)據(jù) fail增加一,節(jié)點(diǎn)1更新自己的TrustMap;如果決定不獲取,節(jié)點(diǎn)2如果是善意節(jié)點(diǎn),統(tǒng)計(jì)數(shù)據(jù)wrong decision增加一。顯然,如果沒有信譽(yù)機(jī)制的作用,那么應(yīng)該有10/50=20%的傳輸是失敗的。
圖2顯示了FTrust網(wǎng)絡(luò)中(默認(rèn)信譽(yù)值為0.5)各項(xiàng)統(tǒng)計(jì)數(shù)據(jù)占總有效傳輸數(shù)目的比例。可以看出,排除錯(cuò)誤傳輸和錯(cuò)誤決定所占的一成之外,其余九成是正確傳輸和正確決定的比例。
圖2 TRUST_DEFAULT_VALUE=0.5傳輸比例統(tǒng)計(jì)圖
進(jìn)一步的實(shí)驗(yàn)表明,不同的TRUST_DEFAULT_VALUE值對(duì)成功傳輸和錯(cuò)誤決定的影響只在收斂速度上,另外,其值越小,失敗傳輸比例越小。當(dāng)值為0.1時(shí),錯(cuò)誤傳輸比例降到0.02。所以TRUST_DEFAULT_VALUE越小,效果越好。因此,從長(zhǎng)遠(yuǎn)來看,選擇小值是比較好的。因?yàn)镕Trust擁有退出網(wǎng)絡(luò)時(shí),將TrustMap保存起來的功能。在這一層意義上,較小值造成收斂速度較慢的影響可以在一定程度上消減下來。后續(xù)實(shí)驗(yàn)中,該值取折中值0.3。
Zoran Despotovic[4]在極大似然估計(jì)實(shí)驗(yàn)中設(shè)置惡意節(jié)點(diǎn)總是錯(cuò)誤服務(wù),而一般的節(jié)點(diǎn)以一個(gè)隨機(jī)的固定概率值提供錯(cuò)誤服務(wù)。當(dāng)節(jié)點(diǎn)需要第三方的推薦時(shí),只用搜集到10-20個(gè)證據(jù)就可以進(jìn)行計(jì)算。第三方節(jié)點(diǎn)撒謊的概率是全局同一的,但是這個(gè)值并沒有在文中提供,所以不得而知,其結(jié)果如圖3所示。而在FTrust實(shí)驗(yàn)中,第三方節(jié)點(diǎn)撒謊的概率是依節(jié)點(diǎn)而不同的,為1-trust,其中trust是第三方在發(fā)起源看來的信譽(yù)值,因此如果第三方是發(fā)起源的伙伴,那么撒謊概率為0,也就是完全相信自己的伙伴。這也就要求對(duì)成為伙伴的要求要高一點(diǎn),TRUST_THRESHOLD_FRIEND(稱為伙伴的信譽(yù)值要求)設(shè)為0.8。實(shí)驗(yàn)中,一般節(jié)點(diǎn)不僅以一定的概率錯(cuò)誤服務(wù),而且以一定的概率錯(cuò)誤推薦,然后根據(jù)不同惡意節(jié)點(diǎn)的比例,跟蹤錯(cuò)誤服務(wù)的數(shù)目(錯(cuò)誤決定的數(shù)目趨向于0,因此不再列出),實(shí)驗(yàn)結(jié)果如圖4所示。
圖3 采用單純極大似然估計(jì)機(jī)制的實(shí)驗(yàn)結(jié)果圖
圖4 采用FTrust機(jī)制的實(shí)驗(yàn)結(jié)果圖
從上述兩圖可以看出,F(xiàn)Trust穩(wěn)定時(shí)錯(cuò)誤率在0.3到0.42之間,而極大似然估計(jì)最大則超過0.5。同時(shí),極大似然估計(jì)的一個(gè)典型特點(diǎn)是,當(dāng)惡意節(jié)點(diǎn)占到0.5以上時(shí),錯(cuò)誤率不會(huì)再增高,而相反會(huì)降低一些。當(dāng)網(wǎng)絡(luò)中節(jié)點(diǎn)不可信時(shí),它會(huì)采取相反的決定。而FTrust也繼承了這一優(yōu)點(diǎn)。
論文設(shè)計(jì)并實(shí)現(xiàn)了一個(gè)切實(shí)可行的信譽(yù)機(jī)制FTrust,使其工作在P2P環(huán)境中。通過社會(huì)學(xué)和計(jì)算機(jī)科學(xué)的結(jié)合,引入團(tuán)體的概念,構(gòu)造出的FTrust,具有不俗的性能表現(xiàn),同時(shí)通過Kademlia路由協(xié)議合理控制資源耗費(fèi)代價(jià)。通過構(gòu)造的實(shí)驗(yàn)場(chǎng)景對(duì)FTrust的性能分析可知,F(xiàn)Trust的作用明顯,特別是與單純極大似然估計(jì)機(jī)制相比。
[1]Eytan Adar and Bernardo A Huberman.Free Riding on Gnutella[R].Internet Ecologies Area and Xerox Palo Alto Research Center,2000.
[2]Zoran Despotovic,Karl Aberer.Trust and Reputation Management in P2P Networks[R].Swiss Federal Institute of Technology Lausanne,2004.
[3]Zoran Despotovic.Karl Aberer,Possibilities for Managing Trust in P2P Networks[R].Swiss Federal Institute of Technology Lausanne,2004.
[4]Zoran Despotovic, Karl Aberer.Maximum Likelihood Estimation of Peers'Performance in P2P Networks[J].The Second Workshop on the Economics of Peer-to-Peer Systems,2004:1 -6.
[5]Petar Maymounkov,David Mazi`eres.Kademlia:A Peerto-peer Information System Based on the XOR Metric[J].Proc.of the 1st Int'l Workshop on Peer - to - Peer Systems,2002:153 -161.