志愿計算中基于貝葉斯定理的信任模型

徐 玲,喬建忠,林樹寬,祁瑞華

(1.東北大學 計算機科學與工程學院,沈陽 110169; 2.大連外國語大學 軟件學院,遼寧 大連 116044)

0 概述

近年來,一些分布式計算模式如對等計算、志愿計算、云計算等被應用于文件共享、科學計算、企業IT建設等方面,給人們的生活方式帶來了巨大的變革,但這些分布式計算模式的發展仍然面臨很多問題和挑戰,其中一個關鍵問題就是系統安全性問題[1]。本文針對志愿計算中節點的非預期退出計算或蓄意破壞計算等影響系統的安全性行為[2],設計相應的模型來解決這些不可靠的捐獻資源的節點帶來的系統安全性問題。

志愿計算主要是通過網絡中節點捐獻自己閑置資源來進行大規模科學計算的求解[3],從而實現資源的深度共享。志愿計算主要基于主從分布式計算模型[4-5],其中主節點是中心服務器,負責任務的分發和結果的回收,子節點是志愿計算機,可以自愿選擇加入或隨時退出計算而不受主節點控制。如何在這些子節點中選擇可信節點從而提高系統的安全性,是亟需解決的問題。

傳統解決分布式計算系統安全性的方法為采用身份認證、信息加密、訪問控制等方法。這種安全機制被稱為硬安全機制。對于由系統內部節點的行為動態變化帶來的系統安全問題,硬安全機制的解決效果不佳,為此一些研究者[6-7]提出采用信任和信譽模型來提高分布式計算系統的安全性。然而在志愿計算中目前關于信任和信譽的研究工作較少。與本文工作較相關的研究為文獻[8],其利用信譽模型提高志愿計算系統的安全性,該文提出節點歷史表現中返回正確計算結果的概率值即為節點的信譽值,但是模型在計算信譽值時沒有考慮信譽值隨時間動態更新的情況。

針對文獻[8]模型存在的不足,本文構建志愿計算中基于貝葉斯定理的信任模型。對節點的非預期退出計算或蓄意破壞計算行為,利用BTMS模型[9]的二值邏輯描述節點行為,通過添加不確定性來更全面地描述節點的行為。在此基礎上,對節點的不確定行為采用貝葉斯定理預測節點返回正確計算結果的概率,并在計算節點信任值時加入處罰因子和調節函數,實現信任值慢增長快下降,從而有效防止節點通過連續幾次返回正確計算結果行為刷取信任值。此外,本文模型還采用基于時間的滑動窗口對節點的信任值進行更新。

1 相關工作

自從計算領域中信任模型被提出后,越來越多的研究學者對其進行研究,提出了多種信任模型。已有的信任模型主要可以分為集中式和分布式兩類。較典型的集中式信任模型主要應用于在線電子商務如e-bay[10]、阿里巴巴、京東,這類模型通過中心節點集中管理信任,雖然簡單、高效,但是可擴展性差,不適合在大型的分布式計算環境下使用。目前,國內外許多研究者針對分布式網絡環境如P2P網絡、無線傳感器網絡提出了多種分布式信任模型。文獻[11]提出的基于P2P網絡的Eigen Trust信任模型通過多次迭代求得節點的全局信任值,缺點在于通信開銷過大。文獻[12]提出的PeerTrust信任模型利用反饋評價計算節點的信任值,在模型中加入了用戶激勵機制,缺點在于沒有對節點惡意行為的懲罰。針對文獻[11-12]全局信任模型存在計算復雜性較高、收斂速度較慢的問題,文獻[13]提出了基于結構化P2P網絡的GeTrust信任模型,該文受人類社會建立信任關系的啟發,提出每個服務節點在向服務請求節點提供服務時,需要同時向服務請求節點提供服務信任值及其擔保節點的信任值做抵押,服務請求節點對每個服務節點綜合評價其信任值,選擇信任值高的服務節點提供服務。該模型在提高任務交互成功率和抵御攻擊方面具有一定的有效性,但是只適用于結構化的P2P網絡。文獻[14]提出的信任模型綜合考慮時間衰減、交互重要性和交互次數等上下文屬性計算P2P網絡中節點信任值。文獻[9,15-16]提出的基于無線傳感器網絡的信任模型,在信任評價時綜合考慮節點的直接信任和推薦信任,其中在計算直接信任值時是在文獻[17]基礎上加入對惡意節點的懲罰機制。文獻[18]提出的基于無線傳感器網絡的EDTM信任模型,其直接信任值的計算主要包括通信信任、能量信任和數據信任3個部分,EDTM信任模型可以更精確地評估傳感器節點的可信度。雖然現有的針對于其他分布式計算環境的信任模型提高了系統安全性,但無法直接用于志愿計算,這主要是因為志愿計算在以下兩點與其他分布式計算環境不一致:1)志愿計算存在中心服務器;2)節點可以不用負責隨時退出計算。

目前在志愿計算中關于信任和信譽模型的研究工作較少。文獻[8]提出利用信譽模型提高志愿計算系統的安全性,該文定義節點的信譽值為節點歷史表現中節點返回正確計算結果的概率值,同時通過設計簡單的調度算法來驗證所構建模型的有效性。但是該模型計算節點信譽值時僅考慮節點返回正確計算結果和錯誤計算結果2種行為對信譽值的影響,沒有考慮節點非預期退出計算行為對信譽值計算帶來的影響,同時由于信譽值是隨時間動態變化的,該模型也沒有考慮信譽值的動態更新過程。文獻[19]提出在任務調度時基于節點信譽提高系統可靠性,該文將節點信譽定義為節點能夠提供穩定計算時間間隔的能力,若節點能持續提供的計算時間間隔長,則認為該節點更可靠,但該模型也沒有考慮信譽隨時間動態更新。考慮上述不足,本文構建考慮節點非預期退出計算或蓄意破壞計算等行為動態變化的信任模型。

2 節點信任模型

2.1 信任評估基本框架

針對志愿計算環境自身的特點,本文構建的信任模型不考慮節點間的推薦信任值,節點信任值的計算主要來自于節點的歷史交互。模型中的信任機制框架如圖1所示。

圖1 信任機制框架Fig.1 Framework of trust mechanism

本文模型通過收集節點間的歷史交互記錄計算節點的信任值,通過計算節點信任值為選擇下次的交互對象提供依據。對于系統中新加入的節點,采用分配固定值的方法初始化信任值。由于志愿計算自身的特性,本文中VC-trust模型采用集中式管理,但也可以將其擴展應用于分布式管理中。

下文從信任值計算涉及的相關定義、信任值計算和更新、仿真分析模型的有效性等方面對模型進行詳細闡述。為描述方便,在表1中給出本文中所用符號的定義。

表1 符號定義Table 1 Definition of symbols

2.2 相關定義

定義1(信任) 信任是志愿網絡中心服務器server在歷史交互記錄基礎上對節點i針對計算任務t能提供滿意服務的主觀期望值。

定義2(信任值) 信任值表示志愿網絡中節點的可信程度。本文將信任值規范化為[0,1]區間上的值,越接近1代表節點的可信度越高,越接近0代表節點越不可信,0代表節點完全不可信,1代表節點完全可信。

定義3(交互) 節點i完成志愿網絡中心服務器server分發的一次計算任務稱為一次交互。

2.3 信任值

節點i的信任值用Ti表示,根據定義1,有:

(1)

其中,m為節點i在Δt時間內完成的計算任務的數目,f為節點i在Δt時間內返回正確計算結果行為的數目,s為節點i在Δt時間內返回錯誤計算結果行為的數目,u為節點i在Δt時間內出現了不確定性行為的數目。當m=0時,節點為新加入的節點,其信任值初始化為0.5。

在式(1)中,當節點出現不確定性行為時,為使信任計算計算結果更精確,用貝葉斯定理預測節點返回正確計算結果的概率值來替換式(1)中的u值,下文將詳細介紹這一過程。

2.4 貝葉斯定理預測

在VC-trust計算信任值時,當節點出現不確定性行為時,為消除不確定性使得信任值的計算更精確,本文使用貝葉斯定理計算節點出現不確定性行為時返回正確計算結果的概率:

(2)

(3)

其中,f′和s′分別代表節點在Δt時間內返回的正確計算結果數目和錯誤計算結果數目。

實際網絡中節點的行為動態變化,當節點的歷史交互記錄中出現多個不確定性行為時,本文假設志愿計算系統的容錯率為ε,則通過貝葉斯公式預測節點出現不確定性行為時返回正確計算結果的概率為p,如果p>1-ε,默認節點此次計算返回正確計算結果來進行下個不確定性行為的預測;反之,默認節點返回錯誤計算結果來進行下個不確定項的預測。通過貝葉斯定理消除節點不確定性行為后,式(1)中的u利用下式替換:

(4)

其中,pk為節點在第k次出現不確定性行為時返回正確計算結果的概率,可由式(3)計算得到。

例如:節點i在Δt時間內的歷史交互記錄集合ti={1,1,1,0,1,0},ε=0.01,根據式(1)計算得到節點i的信任值Ti=0.632。

2.5 信任值更新

由于信任是隨時間動態變化的,越舊的交互記錄對信任值的計算參考價值越小,越新的交互記錄對信任值的計算參考價值越大,因此本文使用基于時間的滑動窗口存儲最新的歷史交互記錄用于更新節點信任值。

假設每個時間滑動窗口大小為w,存儲的是最新w個單位時間內的歷史交互記錄信息,每當窗口向前移動r個單位時間,根據時間窗口內存儲的歷史交互記錄對每個節點i的信任值進行一次更新,則:

(5)

圖2 基于時間的滑動窗口Fig.2 Sliding window based on time

3 實驗與結果分析

本文通過仿真實驗對VC-trust模型進行有效性驗證。首先,在實驗中驗證信任值計算過程中調節函數和處罰因子對節點信任值變化的影響,判斷模型是否能針對節點動態行為變化調整其信任值,從而識別善意節點和惡意節點,抵御內部攻擊;然后,通過驗證在任務分配時優先分配給信任值高的節點對系統交互成功率的影響,判斷模型是否能提高系統安全性;最后,與BTMS模型進行對比分析,驗證本文模型的有效性和合理性。為實現對模型上述性能的驗證,本文仿真實驗采用C語言編程模擬實現不同類節點出現的3種行為情況。假設網絡中的節點分為以下2類:

1)善意節點。此類節點長期提供友好服務,且在歷史交互過程中很少有惡意破壞計算行為及不確定行為出現,但在實際網絡中服務良好的節點也無法100%提供真實可靠的服務。本文假設此類節點的歷史交互記錄中只有2%的不確性行為出現,95%返回正確的計算結果的行為。

2)惡意節點。此類節點長期提供較差服務,在歷史交互過程中存在較多破壞計算行為和不確定行為。本文假設此類節點的歷史交互記錄中20%返回錯誤計算結果的行為,10%有不確定性行為出現。

本文在計算節點信任值時加入了處罰因子和調節函數,實現節點信任值累積慢而下降快的目標。實驗驗證VC-trust模型中處罰因子和調節函數對信任值的影響,并與BTMS模型進行比較分析。由于志愿計算環境的特點,本文不考慮推薦信任值的計算,因此在計算BTMS模型的信任值時只考慮節點的直接信任值計算。仿真實驗默認參數設置如表2所示。

表2 實驗默認參數Table 2 Default parameters of experiment

3.1 調節函數與處罰因子對信任值的影響

為分析調節函數和處罰因子對信任值的影響,本文提取節點i的一組特殊仿真數據進行說明。節點i在同一時間段內出現3種節點行為的信任值如表3所示。通過對比可知,隨著節點返回正確計算結果行為次數的增加,由BTMS模型計算的信任值是逐漸增加的。本文模型綜合考慮了節點行為對信任值變化的影響,當節點總的計算次數增加使得返回正確計算結果行為增多時,節點信任值沒有增加反而下降,這是模型中處罰因子和調節函數共同作用的結果,因為調節函數使信任值增加的速度慢于處罰因子使信任值下降的速度,所以信任值沒有增加反而下降。同時可以注意到節點i表現出的行為屬于惡意節點,通過本文模型計算的惡意節點的信任值約為0.5,這樣更有利于區分善意節點和惡意節點。

表3 調節函數與衰減因子對信任值的影響Table 3 Effects of regulatory function and attenuation factor on trust value

3.2 與其他模型性能的比較分析

由于節點的信任值越高,節點返回正確計算結果行為出現的概率也越高,因此為更全面地衡量模型的性能,本文以系統交互成功率作為指標設計仿真實驗。

定義5(交互成功率) 每次仿真實驗由若干個單位時間組成,在一個單位時間內節點返回正確計算結果行為的數目和總的計算任務數目的比率即為交互成功率。

在本文實驗過程中,假設系統中活躍在線節點數目為100個,惡意節點比例為50%,服務器在選擇節點分配任務時,假設選擇信任值排名在前五十的節點分發計算任務。由于志愿計算環境的特點,本文不考慮推薦信任值的計算,因此利用BTMS模型計算交互成功率時只考慮節點直接信任值的計算。VC-trust模型和BTMS模型的系統交互成功率對比如圖3所示。可以看出,在第9 h后,由于節點行為變化,本文模型的交互成功率下滑后恢復較快,而BTMS模型恢復較慢,且由于BTMS模型適應環境與本文不同,因此在系統交互成功率上,本文模型的交互成功率整體要高于BTMS模型。

圖3 VC-trust模型與BTMS模型的交互成功率對比Fig.3 Comparison of interaction success ratio betweenVC-trust model and BTMS model

綜上可知,本文VC-trust模型在系統交互成功率和對節點行為變化的靈敏度2個方面要優于BTMS模型,表明該模型具有一定的合理性和有效性。

4 結束語

本文構建志愿計算環境中一種基于貝葉斯定理的信任模型。考慮到節點行為的不確定性,在模型中對節點的不確定性行為采用貝葉斯定理進行預測。在計算信任值更新時,利用基于時間的滑動窗口更新節點信任值,體現其隨時間的動態變化的特性。實驗結果表明,該模型在系統交互成功率和適應節點行為變化靈敏度方面性能優于BTMS模型。后續將把本文模型擴展應用到其他分布式計算系統中,同時考慮更多的上下文因素以進一步提升交互準確率。