帶時(shí)間特性的自動(dòng)信任協(xié)商

摘 要:自動(dòng)信任協(xié)商是陌生實(shí)體通過交替地披露屬性證書建立信任關(guān)系的一種方法。現(xiàn)有的研究僅僅考慮與時(shí)間特性無關(guān)的其他方面，沒有合理的信任協(xié)商會(huì)話調(diào)度方案，存在著拒絕服務(wù)攻擊。提出了自動(dòng)信任協(xié)商的基本組件，使用狀態(tài)變換系統(tǒng)形式化描述了一個(gè)自動(dòng)信任協(xié)商抽象模型。討論了自動(dòng)信任協(xié)商的時(shí)間特性，對原有安全策略擴(kuò)展了時(shí)間約束安全策略，構(gòu)造了一個(gè)帶時(shí)間特性的自動(dòng)信任協(xié)商狀態(tài)變化系統(tǒng)。同時(shí)分析了安全策略的可滿足性判定問題。

關(guān)鍵詞:自動(dòng)信任協(xié)商; 信任證; 圖靈機(jī); 不可判定性; 時(shí)間自動(dòng)機(jī)

中圖分類號:TP309文獻(xiàn)標(biāo)志碼:A

文章編號:1001-3695(2010)06-2304-05

doi:10.3969/j.issn.10013695.2010.06.089

Timed automated trust negotiation

YANG Qiuwei， ZHOU Jie， TANG Zhuo， LIU Ling

(School of Computer Communication， Hunan University， Changsha 410082， China)

Abstract:Automated trust negotiation is an approach to build trust relationship between strangers by disclosing attribute credentials alternately. However， the main work focuses on some aspects， which had nothing to do with the time character in recent research， without reasonable schedule scheme of ATN session and existing denial of service attack. This paper proposed the components of ATN and described an abstract ATN model with statetransition system. Extended the security policies so that it could describe the time character. Constructed a statetransition system with time character to simulate ATN. Discussed the satiability of security policies in ATN.

Key words:automated trust negotiation; credential; Turing machine; undecidable; timed automata

0 引言

在開放的互聯(lián)網(wǎng)中，以及新近出現(xiàn)的P2P(peer to peer)和grid環(huán)境下，迫切需求系統(tǒng)間的協(xié)同和資源共享。由于主體數(shù)量龐大、運(yùn)行環(huán)境動(dòng)態(tài)分散以及訪問控制自主性需求等特點(diǎn)，各主體往往隸屬于不同的管理域，使得傳統(tǒng)的訪問控制技術(shù)在跨域環(huán)境下進(jìn)行授權(quán)及訪問控制時(shí)顯得力不從心，暴露出許多弱點(diǎn)。

1996年，Blaze等人[1]首先提出了信任的概念，將信任引入到授權(quán)管理中，并在此基礎(chǔ)上開發(fā)了信任管理系統(tǒng)PolicyMaker[1]和KeyNote[2] 。Winsborough等人[3]稱這類信任管理系統(tǒng)為基于能力(capabilitybased)的授權(quán)系統(tǒng)，它們?nèi)孕枰埱蠓筋A(yù)先被服務(wù)方所熟知，無法與陌生方建立動(dòng)態(tài)的信任關(guān)系。在文獻(xiàn)[4，5]中，Li Ninghui等人提出了一種基于角色的信任管理框架(rolebased trustmanagement framework，RT)，RT模型族中的授權(quán)依賴于主體屬性，使得陌生方之間建立有效的信任關(guān)系成為可能。但是，陌生主體之間建立信任所依賴的屬性信任證和訪問控制策略中，均可能泄露交互主體的敏感內(nèi)容以及資源擁有信息，并且主體間的信任關(guān)系常常是動(dòng)態(tài)變化的。為了解決以上問題， Winsborough 等人[3]提出了自動(dòng)信任協(xié)商(automated trust negotiation， ATN)的概念，它是通過信任證、訪問控制策略的交互披露，資源的請求方和提供方自動(dòng)地建立信任關(guān)系[6~9]。

在現(xiàn)有的ATN研究中，均沒有對ATN抽象模型嚴(yán)格的形式化定義，也沒有引入時(shí)間概念，因而沒有嚴(yán)格的形式化模型來刻畫ATN的處理過程，并且沒有考慮隨時(shí)間變化而引起模型的動(dòng)態(tài)變化。例如，當(dāng)信任協(xié)商會(huì)話長時(shí)間占用系統(tǒng)資源(如CPU、內(nèi)存等系統(tǒng)資源)時(shí)，服務(wù)提供方?jīng)]有對多個(gè)信任協(xié)商會(huì)話合理的調(diào)度方案。另外，惡意主體發(fā)起大量無用的信任協(xié)商會(huì)話，構(gòu)成拒絕服務(wù)攻擊(denial of service attack)，最終導(dǎo)致系統(tǒng)癱瘓。

本文提出了ATN抽象模型的基本組件，引入狀態(tài)變換系統(tǒng)定義ATN抽象模型。在此形式化基礎(chǔ)上，對ATN作時(shí)間特性上的擴(kuò)展，分析和討論了ATN的時(shí)間語義。構(gòu)造一個(gè)帶時(shí)間特性的狀態(tài)變化系統(tǒng)來描述擴(kuò)展了的ATN。最后對ATN中安全策略的可滿足性進(jìn)行了分析。

1 基本概念

1.1 自動(dòng)信任協(xié)商

ATN主要研究跨域的信任建立問題。它與傳統(tǒng)的訪問控制的主要區(qū)別在于協(xié)商雙方是否事先知道對方身份、擁有的權(quán)限和訪問控制策略。而在自動(dòng)信任協(xié)商里，通過逐步披露屬性證書，最終建立信任關(guān)系，協(xié)商過程一般強(qiáng)調(diào)自動(dòng)化，不需要或者需要少量的人工參與。

實(shí)例1 在線電子書城系統(tǒng)中，電子書店只對注冊了的用戶提供瀏覽書目以及訂購書籍服務(wù)。用戶Alice試圖訪問電子書店eBookMerket，整個(gè)信任協(xié)商過程如圖1所示:①Alice向eBookMarket發(fā)送訪問請求;②eBookMarket制定了策略只對注冊了的用戶提供服務(wù)，所以eBookMarket向Alice發(fā)送披露包含了注冊信息的證書(C1:register)的請求;③同時(shí)，Alice制定策略訪問注冊證書C1的主體必須首先披露營業(yè)執(zhí)照，所以Alice向eBookMarket發(fā)送披露營業(yè)執(zhí)照(C2:businesslicense)的請求;④eBookMarket認(rèn)為營業(yè)執(zhí)照C2是可以被任意用戶查詢驗(yàn)證的，所以eBookMarket披露營業(yè)執(zhí)照C2;⑤Alice接收到eBookMarket向Alice披露的營業(yè)執(zhí)照C2后，C1的保護(hù)策略被滿足，Alice向eBookMarket披露C1;⑥最后，Alice的訪問被批準(zhǔn)。 整個(gè)信任協(xié)商過程經(jīng)歷的時(shí)間長度為t。

1.2 ATN的抽象模型

在前面的部分簡單介紹了ATN的研究內(nèi)容。下面將給出ATN抽象模型的定義。

定義1 ATN抽象模型。該模型有如下組件:

U:主體集;AT:屬性集;P:策略集;S(信任協(xié)商)會(huì)話集。

UAT  U×AT，建立U到AT的關(guān)聯(lián)，指定哪些主體擁有哪些屬性。

PAT  P×AT，建立P到AT的關(guān)聯(lián)，使用哪些策略保護(hù)哪些屬性。

user:S→U×U，將每個(gè)會(huì)話映射到兩個(gè)協(xié)商者(資源提供者，資源請求者)的函數(shù)。

policy:AT→2P，將每個(gè)屬性映射到一個(gè)策略集合。policy(ti){p|(p， ti)∈PAT}。

attribute:S→2AT，將每個(gè)會(huì)話映射到一個(gè)屬性集合。attribute(si){t|((us，ur)∈user(si))[((us，t)∈UAT)∨(ur，t) ∈UAT]}。信任協(xié)商會(huì)話si需要滿足的策略集合為∪t∈attribute(si){p|(p，t)∈PAT}。

定義2 ATN抽象模型。用狀態(tài)變換系統(tǒng)M=〈K，Σ，P，δ〉來模擬ATN抽象模型。其中:K是狀態(tài)集;Σ是操作集;P是系統(tǒng)策略集;δ: K×Σ×2P→K狀態(tài)轉(zhuǎn)移函數(shù)。

K是狀態(tài)集，如k∈K，k是一個(gè)四元組〈urequestor， urecipient， UAT， PAT〉。Σ是操作集，例如，Σ是類似request(c)和disclosure(c)組成的集合。其中request(c)表示向協(xié)商對方發(fā)送披露信任證c的請求，disclosure(c)表示向協(xié)商對方披露信任證c。狀態(tài)變化函數(shù)δ定義了狀態(tài)變換系統(tǒng)的變化規(guī)則。如果在輸入a∈Σ，系統(tǒng)M從狀態(tài)k1到k2，這表示當(dāng)它在狀態(tài)k1時(shí)讀入a，轉(zhuǎn)移到狀態(tài)k2，記為k1δ a k2。k1δ* k2表示狀態(tài)系統(tǒng)M經(jīng)過零次或者多次狀態(tài)變化從k1變化到k2，并且稱在狀態(tài)變換系統(tǒng)M中狀態(tài)k2相對狀態(tài)k1是可到達(dá)的。P是系統(tǒng)策略集，如系統(tǒng)策略集包含了敏感屬性的保護(hù)策略。通常在信任協(xié)商的過程中，需要考慮諸如此類與時(shí)間相關(guān)的安全問題:a)是否有用戶長時(shí)間占用過多的系統(tǒng)資源?b)是否服務(wù)提供方接收的服務(wù)請求量超過了所能承受的負(fù)載?主要考慮如下兩個(gè)方面的安全策略:

a)單信任協(xié)商會(huì)話時(shí)間約束安全策略。該類安全策略約束單個(gè)信任協(xié)商會(huì)話的資源消耗問題，限制單個(gè)用戶的惡意行為能力，使得其他合法用戶的服務(wù)請求得到及時(shí)的響應(yīng)，并實(shí)施有效的會(huì)話調(diào)度。

b)多信任協(xié)商會(huì)話時(shí)間約束安全策略。該類安全策略約束系統(tǒng)中多個(gè)信任協(xié)商會(huì)話的資源消耗問題，限制多個(gè)用戶的惡意行為能力，保證服務(wù)提供方的正常運(yùn)行。

2 ATN中的時(shí)間約束特性分析

本章將對ATN的時(shí)間約束特性進(jìn)行分析。首先通過定義一個(gè)離散時(shí)間點(diǎn)序列來模擬現(xiàn)實(shí)世界中的連續(xù)時(shí)間序列。在此基礎(chǔ)上對多種時(shí)間約束提出了形式化的定義。

2.1 自動(dòng)信任協(xié)商系統(tǒng)中的時(shí)間約束

2.1.1 單信任協(xié)商會(huì)話時(shí)間約束

根據(jù)時(shí)間約束的特性，單信任協(xié)商會(huì)話時(shí)間約束可分為如下四類:

a)信任協(xié)商時(shí)間范圍約束。該類約束規(guī)定用戶只能在特定時(shí)間范圍內(nèi)可以建立信任協(xié)商會(huì)話。例如，一個(gè)有工作時(shí)間限制的企業(yè)組織中，在非工作時(shí)間的范圍內(nèi)，將不允許提供某些服務(wù)或者對某些資源的訪問，相關(guān)的信任協(xié)商會(huì)話將不被批準(zhǔn)。

b)信任協(xié)商時(shí)間長度約束。該類約束規(guī)定每個(gè)信任協(xié)商會(huì)話的時(shí)間跨度不能超過一個(gè)固定時(shí)間長度。可用該類約束防止因信任協(xié)商會(huì)話長時(shí)間占用系統(tǒng)資源(如CPU、內(nèi)存等系統(tǒng)資源)，而導(dǎo)致其他會(huì)話得不到及時(shí)響應(yīng)。

c)時(shí)間范圍內(nèi)信任協(xié)商時(shí)間長度約束。該類約束規(guī)定用戶建立信任協(xié)商會(huì)話的累計(jì)時(shí)間長度，在一定的時(shí)間范圍內(nèi)不超過一個(gè)規(guī)定的上限。其能夠有效地限制主體的惡意行為，可以控制在一定的時(shí)間范圍內(nèi)提供給主體的服務(wù)時(shí)間。

d)時(shí)間范圍內(nèi)信任協(xié)商累計(jì)次數(shù)約束。該類約束規(guī)定用戶建立信任協(xié)商會(huì)話的累計(jì)次數(shù)，在一定的時(shí)間范圍內(nèi)不超過一個(gè)規(guī)定的上限。其能夠有效地限制惡意主體的行為，可以限制主體在一定的時(shí)間范圍內(nèi)平均的信任協(xié)商會(huì)話次數(shù)。

2.1.2 多信任協(xié)商會(huì)話時(shí)間約束

從會(huì)話的時(shí)間長度和次數(shù)考慮，多信任協(xié)商會(huì)話時(shí)間約束又可分為以下兩類:

a)時(shí)間范圍內(nèi)信任協(xié)商總時(shí)間長度約束。該類約束規(guī)定服務(wù)提供方響應(yīng)所有信任協(xié)商會(huì)話的累計(jì)時(shí)間，在一定的時(shí)間范圍內(nèi)不超過一個(gè)規(guī)定的上限。其同時(shí)影響多個(gè)會(huì)話的時(shí)間。例如，為了防止過多的信任協(xié)商會(huì)話而導(dǎo)致服務(wù)方響應(yīng)能力的下降，可能要求限制服務(wù)提供方響應(yīng)的所有信任協(xié)商會(huì)話的累計(jì)時(shí)間。

b)時(shí)間范圍內(nèi)信任協(xié)商總數(shù)約束。該類約束規(guī)定服務(wù)提供方響應(yīng)信任協(xié)商會(huì)話的總數(shù)，在一定的時(shí)間范圍內(nèi)不超過一個(gè)規(guī)定的上限。同樣，如果不對響應(yīng)的會(huì)話數(shù)量進(jìn)行控制，那么就為惡意主體實(shí)施DoS攻擊提供了可能。

以上兩種分類方法是從不同的角度對會(huì)話相關(guān)的時(shí)間約束的考察，但單信任協(xié)商會(huì)話時(shí)間約束是以控制敵手行為能力為目的，而多信任協(xié)商會(huì)話時(shí)間約束通常是為了保護(hù)服務(wù)提供方的資源。一個(gè)信任協(xié)商會(huì)話可能既包含了單信任協(xié)商會(huì)話時(shí)間約束又包含了多信任協(xié)商會(huì)話時(shí)間約束。

2.2 時(shí)間點(diǎn)序列和時(shí)間區(qū)間的定義

定義3 時(shí)間點(diǎn)序列的定義。時(shí)間點(diǎn)序列就是一串時(shí)間變量…，tk，tk+1，tk+2，…所構(gòu)成的序列，或用tk(k=…，1，2，3，…)表示，對每個(gè)固定的整數(shù)k，tk是一時(shí)間變量，稱為時(shí)間點(diǎn)。要求時(shí)間點(diǎn)序列T 中的元素是按下標(biāo)k嚴(yán)格遞增的，即有時(shí)間點(diǎn)序列T={tk|k=…，1，2，3，…}，可以定義該時(shí)間點(diǎn)序列上的≤關(guān)系:

ti，tj∈T，i≤jti≤tjti

定義4 時(shí)間區(qū)間定義。時(shí)間區(qū)間是由兩個(gè)時(shí)間點(diǎn)ti，tj∈T(i≤j)所構(gòu)成的區(qū)間，用[ti，tj]表示。可以定義該時(shí)間區(qū)間的∈關(guān)系

t，ti，tj∈T，并且ti≤tj，t∈[ti，tj]ti≤t≤tj

定義5 t，ti，tj∈T，并且ti≤tj，對帶時(shí)間特性的自動(dòng)信任協(xié)商系統(tǒng)作如下規(guī)定:

a)st是一個(gè)信任協(xié)商會(huì)話，表示該會(huì)話在t時(shí)刻發(fā)起;

b)對任意實(shí)體發(fā)起的任意信任協(xié)商會(huì)話，該會(huì)話的發(fā)起時(shí)間是確定的，可以通過函數(shù)start(st)獲得:

start(st)=t

c)current_time，系統(tǒng)設(shè)置的時(shí)間約束檢查點(diǎn)所對應(yīng)的時(shí)間點(diǎn)，即系統(tǒng)檢查時(shí)間約束的時(shí)刻，系統(tǒng)檢查點(diǎn)可以是某個(gè)會(huì)話的發(fā)起時(shí)刻、定時(shí)循環(huán)查詢或異常發(fā)生時(shí)刻，這與具體應(yīng)用相關(guān);

d)對已經(jīng)結(jié)束了的信任協(xié)商會(huì)話，該會(huì)話的結(jié)束時(shí)間是確定的，并且可以通過函數(shù)end(st)獲得:

end(st)=t′t′≤current_timest complete at t′ timecurrent_time st does′t complete at currenttime

e)sA[ti，tj]是會(huì)話集，表示在時(shí)間區(qū)間[ti，tj]內(nèi)，由實(shí)體A發(fā)起的會(huì)話集，st∈sA[ti，tj]ti≤start(st)≤tj;

f)s[ti，tj]是會(huì)話集，表示在時(shí)間區(qū)間[ti，tj]內(nèi)，所有實(shí)體發(fā)起的會(huì)話集，st∈s*[ti，tj]ti≤start(st)≤tj。

2.3 自動(dòng)信任協(xié)商時(shí)間約束的語義

基于時(shí)間點(diǎn)序列和時(shí)間區(qū)間的定義，信任協(xié)商時(shí)間約束可用以下函數(shù)進(jìn)行定義:

a)信任協(xié)商時(shí)間范圍約束函數(shù):(st，[ti，tj])→{true，1}。其中:true表示信任協(xié)商會(huì)話在規(guī)定時(shí)間內(nèi)發(fā)起，1表示信任協(xié)商會(huì)話在規(guī)定時(shí)間外發(fā)起。具體定義如下:

(st，[ti，tj])=truestart(st)∈[ti，tj]1else

b)信任協(xié)商時(shí)間長度約束函數(shù)η:(st，l)→{true，1}。其中: l是常量，表示信任協(xié)商時(shí)間長度的上限，true表示信任協(xié)商會(huì)話的時(shí)間長度沒有超過上限 l，1表示信任協(xié)商會(huì)話的時(shí)間長度超過了上限l。具體定義如下:

η(st，l)=truecurrent_time-start(st)≤l1else

c)時(shí)間范圍內(nèi)信任協(xié)商時(shí)間長度約束函數(shù)ψ:(sA[ti，tj]，l)→{true，1}。其中:l是常量，表示在時(shí)間范圍[ti，tj]內(nèi)，允許單個(gè)用戶可以進(jìn)行信任協(xié)商會(huì)話總的時(shí)間長度上限，true表示單個(gè)用戶信任協(xié)商總的時(shí)間長度沒有超過上限l，1表示單個(gè)用戶信任協(xié)商總的時(shí)間長度超過了上限l。函數(shù)sum_time(sA[ti，tj])統(tǒng)計(jì)在時(shí)間范圍[ti，tj]內(nèi)，實(shí)體A總的信任協(xié)商時(shí)間長度。具體定義如下:

sum_time(sA[ti，tj])=∑st∈sA[ti，tj](min(tj，current_time，end(st))-start(st))ψ(sA[ti，tj]，l)=truesum_time(sA[ti，tj])≤l1else

d)時(shí)間范圍內(nèi)信任協(xié)商累計(jì)次數(shù)約束函數(shù)ω:(sA[ti，tj]，C)→{true，1}。其中:C是常數(shù)，表示在時(shí)間范圍[ti，tj]內(nèi)，允許單個(gè)用戶可以進(jìn)行信任協(xié)商會(huì)話總的次數(shù)上限，true表示單個(gè)用戶信任協(xié)商總的次數(shù)沒有超過上限C，1表示單個(gè)用戶信任協(xié)商總的次數(shù)超過了上限C。函數(shù)count(st，[ti，tj])判定某個(gè)會(huì)話是否出現(xiàn)在規(guī)定時(shí)間范圍[ti，tj]內(nèi)，并計(jì)數(shù)。sum_number(sA[ti，tj])統(tǒng)計(jì)在時(shí)間范圍[ti，tj]內(nèi)，實(shí)體A總的信任協(xié)商次數(shù)。具體定義如下:

count(st，[ti，tj])=1start(st)∈[ti，tj]0else

sum_number(sA[ti，tj])=∑st∈sA[ti，tj]count(st，[ti，tj])

ω(sA[ti，tj]，C)=truesum_number(sA[ti，tj])≤C1else

e)時(shí)間范圍內(nèi)信任協(xié)商總時(shí)間長度約束函數(shù)θ:(s*[ti，tj]，l)→{true，1}。其中:l是常數(shù)，表示在時(shí)間范圍[ti，tj]內(nèi)，允許所有用戶可以進(jìn)行信任協(xié)商會(huì)話總的時(shí)間長度上限，true表示所有用戶信任協(xié)商總的時(shí)間長度沒有超過上限l，1表示所有用戶信任協(xié)商總的時(shí)間長度超過了上限l。函數(shù)sum_all_time(s*[ti，tj])統(tǒng)計(jì)在時(shí)間范圍[ti，tj]內(nèi)，所有用戶總的信任協(xié)商時(shí)間長度。具體定義如下:

sum_all_time(s[ti，tj])=

∑st∈s*[ti，tj](min(tj，current_time，end(st))-start(st))

θ(s*[ti，tj]，l)=true sum_all_time(s[ti，tj])≤l1 else

f)時(shí)間范圍內(nèi)信任協(xié)商總數(shù)約束函數(shù)μ:(s*[ti，tj]，C)→{true，1}。其中: C是常數(shù)，表示在時(shí)間范圍[ti，tj]內(nèi)，允許所有用戶可以進(jìn)行信任協(xié)商會(huì)話總的基數(shù)上限，true表示所有用戶信任協(xié)商總的基數(shù)沒有超過上限C，1表示所有用戶信任協(xié)商總的基數(shù)超過了上限C。sum_all_number(s[ti，tj])統(tǒng)計(jì)在時(shí)間范圍[ti，tj]內(nèi)，所有用戶總的信任協(xié)商次數(shù)。具體定義如下:

sum_all_number(s*[ti，tj])=∑st∈s*[ti，tj]count(st，[ti，tj])

μ(s[ti，tj]，C)=truesum_all_number(s[ti，tj])≤C1else

3 構(gòu)造ATN的時(shí)間自動(dòng)機(jī)

在本文前面的部分介紹了自動(dòng)信任協(xié)商時(shí)間約束的特性，并定義了幾種類型的時(shí)間約束語義。在自動(dòng)信任協(xié)商系統(tǒng)中，協(xié)商雙方在交互過程中，將對方的響應(yīng)作為輸入，并且根據(jù)本地安全策略(包括了敏感屬性保護(hù)策略和時(shí)間約束安全策略)，決定會(huì)話是否繼續(xù)進(jìn)行。下面使用帶時(shí)間特性的狀態(tài)變換系統(tǒng)模擬帶時(shí)間約束的ATN抽象模型。

定義6 帶時(shí)間約束的ATN抽象模型。用帶時(shí)間特性的狀態(tài)變換系統(tǒng)M=〈K，Σ，P，C，δ〉來模擬帶時(shí)間約束的ATN抽象模型。其中:K是狀態(tài)集;Σ是操作集;C是一個(gè)有窮時(shí)鐘集合;P是系統(tǒng)策略集;δ: K×Σ×2P×2C→K狀態(tài)轉(zhuǎn)移函數(shù)。

對于一個(gè)給定的帶時(shí)間約束的ATN抽象模型M=〈K，Σ，P，C，δ〉。其中K和Σ等同于定義2中的定義;C是一個(gè)有窮時(shí)鐘集合;P是系統(tǒng)策略集，包含了敏感屬性保護(hù)策略和時(shí)間約束安全策略;狀態(tài)變化函數(shù)δ定義了狀態(tài)變換系統(tǒng)的變化規(guī)則。例如，在輸入a∈Σ，首先判定系統(tǒng)M是否滿足了某個(gè)策略集合P′∈2P，如果滿足，系統(tǒng)從狀態(tài)從k1變化到k2，并且時(shí)鐘集合C′∈2C中的時(shí)鐘在這次狀態(tài)變化發(fā)生后全部復(fù)位(置零)，記為( k1， a， P′， C′)→k2。( k1， * ， P′， C′)→k2表示狀態(tài)系統(tǒng)M經(jīng)過零次或者多次狀態(tài)變化從k1變化到k2，并且稱在狀態(tài)變換系統(tǒng)M中狀態(tài)k2相對k1是可到達(dá)的。

在自動(dòng)信任協(xié)商系統(tǒng)中，每次在執(zhí)行系統(tǒng)操作之前作安全策略的可滿足性分析，判定當(dāng)前操作是否違反安全策略，并且存在一條安全的交互序列，使得協(xié)商能夠成功，進(jìn)而繼續(xù)或者終止協(xié)商。而安全策略包括了敏感屬性[10，11]的保護(hù)策略和時(shí)間約束安全策略，策略的可滿足性判定成為保證系統(tǒng)安全的關(guān)鍵環(huán)節(jié)。

4 安全策略的可滿足性分析

4.1 用圖靈機(jī)對安全策略進(jìn)行可滿足性分析

通常，一個(gè)時(shí)間約束安全策略表達(dá)的是這種意圖:在某個(gè)時(shí)間約束檢查點(diǎn)cp，檢查當(dāng)前會(huì)話集是否滿足本地設(shè)置的時(shí)間約束條件，如果沒有，將不批準(zhǔn)當(dāng)前的會(huì)話請求或停止正在進(jìn)行的會(huì)話。同樣，一個(gè)敏感屬性的保護(hù)策略表達(dá)的意圖是:信任協(xié)商的一個(gè)主體在披露某個(gè)敏感屬性at∈AT之前，信任協(xié)商的另一主體必須披露的屬性集，它是由AT的一個(gè)子集AT′中的元素以x，

瘙 綈 x，∧和∨操作形式組成的一個(gè)布爾表達(dá)式。換句話說，也就是只有敏感屬性at的安全策略被滿足了，才能披露at。

假設(shè)在會(huì)話過程中，每個(gè)用戶可以披露自己的保護(hù)策略，只有當(dāng)找到某個(gè)安全的交互序列保證信任協(xié)商的成功之后，才按此序列交互披露相關(guān)信任證;否則，此次會(huì)話將不繼續(xù)。

定義7 時(shí)間約束安全策略的可滿足性。在自動(dòng)信任協(xié)商系統(tǒng)中，用constrain_time表示時(shí)間約束安全策略集，如果在某個(gè)時(shí)間約束檢查點(diǎn)cp(時(shí)間約束檢查點(diǎn)可以是會(huì)話的發(fā)起時(shí)刻、定時(shí)循環(huán)查詢或者異常發(fā)生時(shí)刻)，時(shí)間約束安全策略p∈constrain_time保持為真(true)，那么稱時(shí)間約束安全策略p在檢查點(diǎn)cp是可滿足的。

定義8 敏感屬性安全策略的可滿足性。在自動(dòng)信任協(xié)商系統(tǒng)中，假定at∈AT，如果在協(xié)商雙方之間存在一個(gè)交互序列ai，ai+1， …，aj。其中al ∈{request(at′) | at′∈AT }∪{disclosure(at′) | at′∈AT }， l=i，…，j，使得在這些交互完成之后，屬性at能夠被披露，那么稱屬性at的安全策略是可滿足的。

可見，安全策略的可滿足性判定將直接影響信任協(xié)商的成功與否。本文引入符號“⊥”:at⊥AT′，表示是否披露at，取決于屬性集AT′中元素是否已經(jīng)被披露。對任意的at∈AT，都可以得到一個(gè)與之關(guān)聯(lián)的角色集合AT′。而at′∈AT′，可能同樣存在一個(gè)AT″(即協(xié)商對方也認(rèn)為屬性at是敏感屬性，制定了保護(hù)策略)，那么可以將集合AT′中的屬性用與之相關(guān)的AT″中的元素集取代。為了進(jìn)行可滿足性分析，這樣遞歸下去，試圖求解與at相關(guān)的AT的某個(gè)子集合ATat，而ATat是最終決定屬性at能否被披露的屬性集合，ATat  AT。對于決定關(guān)系at ⊥ ATat，如果ATat是可以惟一確定的，那么關(guān)于屬性at的可滿足性判定將被有效解決。本文把這個(gè)替代問題轉(zhuǎn)換為圖靈機(jī)(TM)的語言識別問題。首先描述TM M，它識別由AT集合中的元素組成的字符串w。

M=對于輸入字符串w:

a)從左到右掃描整個(gè)帶子，將字符at用與at 相關(guān)的集合T′中的所有元素組成的字符串代替。

b)如果a)之后，沒有進(jìn)行任何的置換操作，則接受。

c)讓讀寫頭返回帶子的最左端。

d)轉(zhuǎn)到a)。

容易看出，TM M能夠識別由集合AT中的元素組成的字符串w，只有一個(gè)停機(jī)狀態(tài)為接收狀態(tài):帶上剩下的字符，沒有被包含在任意一個(gè)置換規(guī)則中。這說明求解出與at相關(guān)的集合ATat，只要集合ATat中的元素都已經(jīng)被披露，at也將被披露。這說明在信任協(xié)商雙方之間，至少存在著一條交互序列，如果信任協(xié)商雙方按照這條序列進(jìn)行交互，屬性at的安全策略將被滿足。

4.2 時(shí)間約束安全策略可滿足性分析

定理1 信任協(xié)商會(huì)話時(shí)間約束安全策略可滿足性問題能在多項(xiàng)式時(shí)間內(nèi)得到有效解決。

證明 信任協(xié)商會(huì)話時(shí)間約束安全策略，判定用戶u(u∈U)所發(fā)起的信任協(xié)商的時(shí)間屬性是否滿足時(shí)間約束，通過定義5可知，任意的一個(gè)信任協(xié)商會(huì)話st的發(fā)起(終止)時(shí)間是惟一確定的，通過函數(shù)start(st)(或函數(shù)end(st))獲得，那么由這些時(shí)間點(diǎn)通過信任協(xié)商時(shí)間范圍約束函數(shù)、信任協(xié)商時(shí)間長度約束函數(shù)、時(shí)間范圍內(nèi)信任協(xié)商時(shí)間長度約束函數(shù)、時(shí)間范圍內(nèi)信任協(xié)商累計(jì)次數(shù)約束函數(shù)、時(shí)間范圍內(nèi)信任協(xié)商總時(shí)間長度約束函數(shù)和時(shí)間范圍內(nèi)信任協(xié)商總數(shù)約束函數(shù)進(jìn)行邏輯判斷得到的結(jié)果也是惟一確定的，進(jìn)而信任協(xié)商會(huì)話時(shí)間約束安全策略可滿足性問題的結(jié)果是惟一確定的，而時(shí)間復(fù)雜度分為兩種情況:a)對于單信任協(xié)商會(huì)話時(shí)間約束安全策略，要求獲取單個(gè)用戶建立的所有信任協(xié)商會(huì)話的發(fā)起(終止)時(shí)間。假定|sA[ti，tj]|=n(|A|表示集合A的基數(shù))，單信任協(xié)商會(huì)話時(shí)間約束安全策略可滿足性問題的計(jì)算復(fù)雜度為O(n)。b)對于多信任協(xié)商會(huì)話時(shí)間約束安全策略，要求獲取所有用戶建立的信任協(xié)商會(huì)話的發(fā)起(終止)時(shí)間。假定|U|=c1(c1是常量)，|s*[ti，tj]|=m，多信任協(xié)商會(huì)話時(shí)間約束安全策略可滿足性問題的計(jì)算復(fù)雜度為O(c1m)。可見，信任協(xié)商會(huì)話時(shí)間約束安全策略可滿足性問題能在多項(xiàng)式時(shí)間內(nèi)能被有效解決。

4.3 敏感屬性保護(hù)策略可滿足性判定分析

對于敏感屬性保護(hù)策略的可滿足性分析，在TM M上模擬w，本文定義了一類比較特殊的可滿足分析:使得TM M進(jìn)入接受狀態(tài)的可滿足性分析稱為與狀態(tài)無關(guān)的可滿足性分析，與狀態(tài)無關(guān)的可滿足性分析的實(shí)質(zhì)是屬性at對應(yīng)的ATat被惟一確定。

定理2 與狀態(tài)無關(guān)的敏感屬性保護(hù)策略可滿足性問題能夠在多項(xiàng)式時(shí)間內(nèi)得到有效解決。

證明 與狀態(tài)無關(guān)的敏感屬性保護(hù)策略可滿足性問題，因?yàn)榕卸▽傩詀t(at∈AT)的保護(hù)策略是否能夠被滿足，通過M識別輸入字符串w，最終能夠得到一個(gè)由屬性集ATat中的元素組成的字符串，那么由這些屬性通過∧、∨和

瘙 綈 操作得到的結(jié)果也是惟一確定的，進(jìn)而安全策略的可滿足性的結(jié)果是惟一確定的。這要求替換過程中用到所有決定關(guān)系at ⊥ ati…atj，右邊的符號未在之前用過的所有替換的左邊出現(xiàn)，否則出現(xiàn)循環(huán)，導(dǎo)致不停機(jī)。假定|w|=l，|P|=c2(c2是常量)，那么此遞歸操作的計(jì)算復(fù)雜度為O(c2l)，即能在多項(xiàng)式時(shí)間能被有效解決。

可用有向圖表示屬性間的決定關(guān)系“⊥”，如T⊥={at1⊥{at4}， at2⊥{at3}， at3⊥{at5}， at5⊥{at2at4}}。那么屬性間的決定關(guān)系“⊥”轉(zhuǎn)換為有向圖2。由圖2可以看出屬性at1能否被披露，取決于屬性at4是否已經(jīng)被披露，at1⊥{at4}。同樣地，從圖2中可以看到，at2、at3和at5在決定關(guān)系上形成了一個(gè)環(huán)，即在圖上表示為有一個(gè)有向環(huán)路。TM M的帶子是無限長的，有向環(huán)路在TM M識別字符串w的過程中體現(xiàn)為循環(huán)，導(dǎo)致不能停機(jī)。

定理3 一般的敏感屬性保護(hù)策略可滿足性問題是不可判定的。

證明 將一般的敏感屬性保護(hù)策略可滿足性問題轉(zhuǎn)換為通用圖靈機(jī)語言識別的停機(jī)問題。當(dāng)TM M停機(jī)時(shí)，帶上剩下由屬性集ATat中的元素組成的字符串，那么由它們用x、

瘙 綈 x、∧和∨操作形式組成的表達(dá)式可以被確定，所以存在著一條交互序列使得at的保護(hù)策略被滿足。當(dāng)TM M不停機(jī)時(shí)，帶上還保留有這樣的字符集:它們之間存在著一個(gè)循環(huán)替換。

若at∈AT，且at ⊥ {ati … atj}，讓TM M識別語言w= ati … atj。根據(jù)前面的分析，在迭代替換過程中，M是否停機(jī)不能判斷，那么判定屬性at的保護(hù)策略可滿足性問題就等價(jià)于TM M識別語言的停機(jī)問題[12]，即HALT問題。TM M識別的語言的HALT問題是不可判定的，導(dǎo)致一般的敏感屬性保護(hù)策略可滿足性問題是不可判定的。

5 結(jié)束語

本文首先提出了ATN抽象模型的基本組件，引入狀態(tài)變換系統(tǒng)定義ATN抽象模型。在此形式化基礎(chǔ)上，對ATN作了時(shí)間特性方面的擴(kuò)展，定義了時(shí)間點(diǎn)序列和時(shí)間區(qū)間，并形式化分析了幾類時(shí)間約束的語義，解決了DoS攻擊、會(huì)話調(diào)度等問題。構(gòu)造了一個(gè)帶時(shí)間特性的狀態(tài)變化系統(tǒng)，能夠更全面、更安全地描述ATN抽象模型。同時(shí)，對ATN中安全策略的可滿足性判定進(jìn)行了分析。但在敏感屬性的保護(hù)策略以及策略的可滿足性判定方面仍有很多工作需進(jìn)一步研究。

參考文獻(xiàn):

[1]BLAZE M， FEIGENBAUM J， LACY J. Decentralized trust management[C]//Proc of the 17th Symposium on Security and Privacy. Okaland:IEEE Computer Society Press， 1996: 164173.

[2]BLAZE M， FEIGENBAUM J， KEROMYTIS A D. Trust management for publickey infrastructures[C]//Cambridge 1998 Security Protocols International Workshop， 1999. Berlin:SpringerVerglag， 1999: 5963.

[3]WINSBOROUGH W H， SEAMONSS K E， JSONES V E. Automate trust negotiation[C]//DARPA Information Survivability Conf and Exposition. 2000: 88102.

[4]LI Ninghui， MITTCHELL J C， WINSBOROUGH W H. Design of a rolebased trust management framework[C]//Proc of IEEE Symposium on Security and Privacy. 2002:114130.

[5]LI Ninghui， WINSBOROUGH W H， MITCHELL J C. Distributed credential chain discovery in trust management[C]//Proc of the 8th ACM Conference on Computer and Communications Security. 2001: 156165.

[6]李建欣，懷進(jìn)鵬，李先賢.自動(dòng)信任協(xié)商研究[J].軟件學(xué)報(bào)， 2006，17(1):124133.

[7]AJSYI O， SINNOTT R， STELL A. Trust realisation in multidomain collaborative environments[C]//Proc of the 6th IEEE/ACIS International Conference on Computer and Information Science (ICIS’07). Melbourne， Australia:[s.n.]， 2007:906-911.

[8]廖振松， 金海， 李赤松， 等. 自動(dòng)信任協(xié)商及其發(fā)展趨勢[J]. 軟件學(xué)報(bào)， 2006，17(9):1933-1948.

[9]YU T， WINSLETT M. A unified scheme for resource protection in automated trust negotiation[C]//IEEE Symposium on Security and Privacy. 2003:245-257.

[10]IRWIN K， YU Ting. Preventing attribute information leakage in automated trust negotiation[C]//Proc of the 12th ACM Conference on Computer and Communications Security. 2005:36-45.

[11]劉志遠(yuǎn)， 楊秋偉， 洪帆， 等. 一種基于標(biāo)志的隱私資源保護(hù)方案[J]. 計(jì)算機(jī)應(yīng)用， 2008， 28(2):418-421.

[12]SIPER M. 計(jì)算理論導(dǎo)引[M]. 張立昂， 王捍貧， 黃雄，譯. 北京: 機(jī)械工業(yè)出版社， 2000:107-109.