帶權強分離信任委托路徑搜索

摘要：在委托證書路徑搜索和一致性證明時，在Keynote提出的證書圖的基礎上，采用有向圖中深度優先遍歷的思想以及圖的動態特性，提出了一種新的一致性驗證算法，通過找出一條最佳的帶權分離委托路徑可以表達否定安全憑證，同時通過有向圖的搜索邊標記提高搜索效率并有效避免回路循環搜索的問題。

關鍵詞：信任管理; 委托; 強分離路徑

中圖分類號：TP309

文獻標志碼：A

文章編號：1001-3695（2007）09-0127-03

分布式信任管理的一個關鍵是委托(delegation)。一個實體可以將對一個或更多資源的有限權限委托給其他實體，實體的委托形成證書圖。委托給可能僅是部分可信的實體一定程度的控制，一個安全考慮就是是否資源的主人對誰能訪問他的資源仍有一定保證。如果將所有實體的所有策略的合作看成是信任管理系統的狀態，那么資源的主人總是控制狀態的某一部分，但不必是全部，即信任管理系統狀態的預期變化將允許或阻止什么樣的訪問。

Policymaker通過將斷言寫入黑板的方式，最終找出是否符合特定策略的分析方式來實現一致性證明[1]；Keynote通過引入證書圖表達委托斷言，使用深度優先算法從policy開始試圖構造一個請求者到目標者之間的一條路徑[2]；RT通過角色方式實現證書鏈的表達與傳遞。這些信任管理系統在證書鏈的構造和搜索方面作了深入的研究，但仍不能處理否定憑證。本文提出基于信任委托證書圖中的帶權強分離信任路徑的搜索，從請求者開始找出到憑證授權源的有效最佳路徑，支持否定憑證的搜索，可實現多外部條件的委托路徑搜索。

1信任路徑與一致性證明

1.1信任路徑

定義1一個圖G=〈V，E〉。其中：V是有限頂點的集合;EV×V是圖G的邊。圖G的傳遞閉包G*=〈V*，E*〉定義是V*=V，且G*有一條邊(u，v)當且僅當在圖G中存在一條從u到v的路徑。

圖G中節點是信任參與者，邊代表節點間的信任關系，權代表節點間信任度。一條信任委托鏈可以為圖G中傳遞閉包的一條邊。

設圖G中節點A、B間有多條路徑，A將選擇一條最強路徑(strongest path)作為強信任路徑，即路徑上的信任度最大且路徑較短。路徑上的信任強度是指這條信任路徑上的所有節點中信任最小值。圖1中，節點A到F的路徑選擇ACF作為強信任路徑，A對F的信任強度是min{0.8，0.9}=0.8。

一個信任委托證書圖中節點間強信任路徑往往惟一，對于分布式訪問(如文件下載)將會使信任度高的路徑得到更多的通信，同時也會使其可信度進一步提高；而另一些路徑上則會負荷較低，不利于分布網絡通信節點的均衡，同時強信任路徑往往容易遭到惡意推薦和詆毀。帶權強分離信任路徑方式是參考多條分離路徑(disjoint path)，節點間的信任值除了與信任強度有關外，還與路徑上的平均信任度和路徑長度有關。圖1中ABDF是AF間的另一條分離路徑，AF間信任度是min{0.5，0.6，0.4}=0.4，分離路徑平均信任值是(0.5+0.6+0.7)/3=0.6。

在選擇信任路徑時，除了路徑的信任度、信任路徑的平均信任值外，還與信任路徑的長度、信任路徑上信任的抖動程度等有關。相同信任度的兩條信任路徑中，路徑長度越長，可靠性越低。信任路徑上信任的數學期望反映路徑上可信性，方差可表示信任的抖動性。

1.2一致性證明

信任管理語言指定策略陳述和疑問的語句和語義關系├，稱策略陳述的集合P為信任管理的一個狀態。已知狀態P和疑問Q，P├Q表示Q在P中為真。當Q由訪問請求產生，P├Q意味著Q在P中被允許。P├Q的證明即為一致性證明PoC(proof of compliance)。

承認實體或合作實體的聯合可能僅控制全局狀態的一部分。假設有一個限制規則R定義了狀態可能的不受控制的變化，如實體可以將由完全可信實體所控制的狀態部分看做是固定的，而認為其他實體可能刪除或增加一些策略陳述。已知狀態P和限制規則R，如果從P到P′的變化被R允許，則記為P|→RP′；如果有零個或更多的被允許的變化導致從P到P′，則記為P|→RP′。如果P|→RP′，則稱P′是從PR可達的。

定義2設P是一個狀態，R為限制規則，Q是疑問。存在的安全分析采取如下形式：存在一個狀態P，使得P|→*RP′，且P′├Q嗎？如果回答是肯定的，則說已知P和R，Q是可能的。

當信任管理系統的狀態在將來可能改變時，需要安全分析；當信任管理系統的全局狀態是固定的，但僅僅是部分已知時，安全分析也是有用的。例如，以前不知道的陳述可能隨著新的訪問請求被遞交上來，因此盡管全局狀態沒有改變，人對狀態的看法卻在改變。為了理解候選委托行動的潛在結果，需要考慮可能存在但還不知道的策略陳述。

安全分析采取如下形式：對于每個P′，P|→*RP′均有P′├Q嗎？如果是，則稱對已知P和R，Q是必需的。

2證書路徑搜索

信任管理系統的核心是 PoC算法。一致性證明器將請求策略和一些憑證集合作為輸入，通過證明是否請求與策略相一致以返回“是”或“非”。因此，建立一個信任管理系統的核心問題就是找到一致性證明的有效算法。

Blaze等人[2]提出了PolicyMaker信任管理。系統中采用一種完全可編程的機制來描述安全策略和安全證書，所有安全策略和安全證書均可歸結為憑證，每個憑證可表達為一個（f，s)對。其中:s表示授權源SA(source of authority)；f則是一段用于描述實際授權內容或委托授權內容的程序。在一個安全策略憑證中，s被賦予關鍵字policy。策略憑證是信任管理引擎不可少的輸入參數，描述了應用系統判斷請求是否可接收的最終權威根源。在一個安全證書憑證中，s被賦予安全證書簽發者的公鑰，在采納某個安全證書時，公鑰用于驗證該安全證書的可靠性。

PolicyMaker采用向黑板輸出的方式進行PoC。首先，建立一個僅包含請求字符串r的黑板；隨后調用憑證，同一憑證可以根據需要調用多次，另外憑證由本地運行環境解釋。當憑證(fi，si)運行時，先讀黑板中的內容并根據內容加入一條或多條接收記錄(i，si，Rij)，但不能夠刪除其他憑證已寫入黑板的接收記錄。其中：Rij表示一個被權威源Sij所證明的特定應用操作，可以是一個輸入請求r，也可以是一些用于憑證間交互的操作。算法本身不需要理解和處理Rij，由面向特定應用的憑證程序fi來處理Rij。當所有憑證調用完畢，若黑板中存在一條能證明請求r的接收記錄，則一致性證明驗證成功。

文獻[1]中證明了PolicyMaker的一致性驗證算法是NP難題的。實際一致性證明器中考慮一些實際參數，如斷言長度l、每個斷言處理時間c、接收記錄集長度s，以及動作串的長度m等。每個斷言(fi，si)是單調的和可認證的，且運行時間不超過O（nc)；輸出最多m個行為串，接收的行為集長度s為一定范圍時的證明算法，稱為局部邊界的單調認證算法LMBAPOC，也稱CCA1算法。算法如下：

CCA1(request r，

assertion*{(f0，POLICY)，(f1，s1)，…，(fn-1，sn-1)}，

int c，int m， int s)

{

s←{(∧，∧，R)}

I←{}

for; ← 1 to m*n

{

if (fi，si)I，then S′←(fi，si)(S)

if Illformed(fi，si) then I←I∪{(fi，si)}

else S←S∪S′

}

if(0，POLICY，R)∈S then Output(Accept)

else output(Reject)

}

CCA1算法對序列(fn-1，sn-1)，…，(s1，n1)，(f0，POLICY) 作m×n次迭代。其運行時間復雜度為O(mn2(nms)c)。

Keynote在PolicyMaker的基礎上，引入證書圖表達委托斷言，使用深度優先算法從policy開始試圖構造一個請求者到目標者之間的一條路徑。但Keynote和PolicyMaker一樣不能處理否定憑證，證書鏈發現問題仍沒有得到有效解決。

3新的一致性驗證算法

3.1算法思想

本方案在Keynote引入證書圖的基礎上，采用有向圖中深度優先遍歷的思想以及圖的動態特性，提出了一種新的一致性驗證算法。它可以在一致性證明過程中加入外部搜索條件，同時解決了否定安全憑證的問題，有效避免了回路循環搜索的問題。該思想中在證書圖中引入節點間的信任度T、路徑信任均值閾值N和路徑長度L作為信任路徑搜索的重要參數。證書圖中的節點代表授予權限或接受權限的點，圖中的有向邊代表授權的內容，權值代表節點間信任度。在信任路徑搜索過程中，信任路徑可以帶權值，采用帶權強分離信任路徑的方法找出一條滿信任路徑長度不大于L、路徑可信度不低于T、且路徑上平均信任值不低于閾值N的一條分離路徑。

算法總體思路如下:

a)將發出請求r的請求者存儲于鄰接表存儲的圖中。

b)調用斷言，如果有包含請求r的斷言，將其記錄于圖中。

c)從請求點u0出發，沿它的反方向用深度優先遍歷的方法尋找一條通向policy目標節點的路徑，搜索過程中有如下的可能。

(a)如果路徑長度超過L則重新搜索，標記此路徑，重復c);

(b)如果搜索過程中中間節點間的可信度低于可信度T，標記此路徑，正方向后退繼續搜索;

(c)如果找到路徑并計算平均信任值小于閾值N，標記此路徑，正方向后退繼續搜索;

(d)節點搜索完成，如果不存在滿足policy斷言的目標節點，則繼續增加斷言，直到所有斷言調用完，轉d);

(e)找到安全策略policy和滿足外部條件參數N、T、L的目標節點，轉d)。

d)找到目標節點則找到一條分離路徑，輸出成功；如果通過目標節點的標記搜索后，返回起始點則目標節點沒有找到，輸出不成功。

算法參數有請求r、策略POLICY、斷言集合f，以及限定參數路徑信任度T、路徑上信任均值N以及路徑長度L。搜索算法CertPathSearch描述如下：

CertPathSearch(request r，

policy POLICY，

assert*f，

int T， int N， int L)

{

u←{u0}，v←{u0}， s←u0，t←0

while(s有未標注的邊斷言處理完畢）

選擇一條與s相連的未標注的有向邊（s，t)

if(t∈u)

u←u-{t} //回溯搜索，將節點從u中刪除

Else

{u←u+{t}，v←u+{t}}//擴展搜索，增加到u，v中

{

if(s，t)間的策略函數=POLICY CARD(U)≤L u中路徑均值≥N u中每對節點權≥T）

exit//找到分離強連通路徑

else

{

remark((s，t)) //對邊(s，t)做標志

if(與s的邊標注完成）

s←t

}

}

if(u中只有一個元素u0)

output(Rejected)

else

{

output(Accepted)

print(u) //u中元素序列即帶權強分離信任路徑

}

本算法采用帶權有向圖的搜索，避免了PolicyMaker中主要以集合為核心的算法，可以處理信任路徑的外部條件限定問題，同時也可以處理否定憑證問題。

實例1在圖1中請求者F要求找出到授權源A的路徑長度不大于2的信任委托路徑。圖2顯示算法搜索過程，虛線代表的是委托形成的委托信任關系圖；圖中*表示對搜索到的路徑進行標注。搜索過程如下： {F}→{F，D}→{F，D，B}→{F，D，B，A}→{F，D，B}→{F，D}→{F}→{F，C}→{F，C，B}→{F，C，B，A}→{F，C，B}

{F，C}→{F，C，A}。

本例中，在搜索的第四步已經有{F，D，B，A}這樣一條A到F的分離路徑，但不滿足路徑長度不超過2的要求，需要進一步搜索。通過搜索的條件限定可以找出最優的信任路徑。

實例2在圖中，找出節點A到F的路徑信任度T>0.9的信任路徑，搜索過程(為方便起見將路徑可信度寫于路徑后)如下：{F}→{F，D：0.7}→{F，D，B：0.6}→{F，D，B，A:0.5}→{F，D，B:0.6}→{F，D:0.7}→{F}→{F，C:0.9}→{F，C，B:0.8}→{F，C，B，A:0.5}→{F，C，B:0.8}→{F，C:0.9}→{F，C，A:0.8}→{F，C:0.9}→{F}→{F，E:0．9}→{F，E，B:0.7}→{F，E，B，A:0.5}→{F，E，B:0.7}→{F，E:0.9}→{F，E，C:0.9}→{F，E，C，A:0.8}→{F，E，C:0.9}→{F，E:0.9}→{F}。

在上述搜索過程中，搜索路徑分別有FDBA、FCBA、FEBA、FECA等幾條路徑，但均無符合限定條件T>0.9的路徑。最后搜索過程在搜索所有的節點分離路徑后，回到了起始點F。由于對與F相連的邊均已做標記，搜索過程結束，此時返回，搜索不成功。

3.2算法復雜度分析

設證書圖G中頂點數為n，邊數是e，斷言數為l，此算法的時間復雜度為O(l×n3)。在最壞情況，一個斷言每次要搜索所有的邊，其時間復雜度為O（n2×l)；再假設每個點均帶條件的話，就是O(n2×n×l)，即時間復雜度O(l×n3)。空間復雜度為O(n+2e)很小，相對PolicyMaker系統中提出的CCA1算法來說提高了效率。 證書圖中的點與邊存儲方式可用兩種方式來組織，即鄰接矩陣和鄰接表。

在整個過程中，每讀入一條斷言集中的新斷言都會使圖中的點以及授權關系動態改變。所以每當輸入否定憑證的斷言時，PolicyMaker和Keynote算法只能處理滿足單調性的策略斷言，不能刪除其他斷言已寫入黑板的接收記錄。此算法只須將對應的授權關系的邊刪除，然后重新搜索，解決了否定安全憑證的問題。

4結束語

本文采用基于有向圖的委托授權圖來描述分布式信任系統中的委托關系，并通過帶權強分離路徑的深度優先搜索方式，從信任委托圖中找出符合特定條件的有效路徑。它對于多信任委托路徑的優化有較好的效果，并能支持否定憑證和外部限定條件的搜索。

參考文獻：

［1］BLAZE M， FEIGENBAUM J，STRAUSS M. Compliance checking in the policymaker trust management system[C]//Proc of the 2nd Financial Crypto Conference. Berlin:SpringerVerlag， 1998:251-265.

[2]BLAZE M，FEIGENBAUM J，IOANNIDIS J， et al. The role of trust management in distributed systems[C]//Secure Internet Programming， Issues for Moloile and distributed Objects. Berlin:SpringerVerlag， 1999:185-210.

[3]王曉峰，王尚平，王育民.公鑰基礎設施中的證書路徑構造方法及驗證算法[J]. 計算機工程與應用， 2002，38(12):72-74，88.

[4]饒懿璇.信任管理中的算法設計和模型分析[D].西安：西安電子科技大學， 2005.

[5]TRCEK D. Towards trust management standardization [J].Computer Standards Interfaces，2004， 26(6): 543548.

[6]SHERWOOD R，LEE S，BHATTACHARJEE B. Cooperative peer groups in NICE[J].Computer Networks， 2006，50(7):523544.

注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”