一種基于ＴＴＣＢ的容侵原子多播協(xié)議研究

摘 要：對(duì)基于可信實(shí)時(shí)計(jì)算基（TTCB）的分布式容侵系統(tǒng)的體系結(jié)構(gòu)進(jìn)行了研究，針對(duì)分布式容侵系統(tǒng)中的一致性問(wèn)題，實(shí)現(xiàn)了利用TTCB服務(wù)的容侵原子多播協(xié)議。在進(jìn)程總數(shù)大于兩倍惡意進(jìn)程個(gè)數(shù)的條件下，該協(xié)議可以滿(mǎn)足正確結(jié)果的一致性要求，達(dá)到了入侵容忍的目的。最后證明了該協(xié)議算法的正確性。

關(guān)鍵詞：入侵容忍；原子多播協(xié)議；一致性；可信實(shí)時(shí)計(jì)算基

中圖分類(lèi)號(hào)：TP309．2 文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695(2008)07-2174-03



Study on atomic multicast protocol for intrusiontolerance based on TTCB

ZHOU Hua，MENG Xiangru，ZHANG Li

(Telecommunication Engineering Institute， Air Force Engineering University， Xi’an 710077， China)

Abstract:This paper studied the architecture of a distributed intrusiontolerance system based on trusted timely computing base(TTCB)， and proposed an atomic multicast protocol for intrusiontolerance using TTCB services to solve the consensus problem in distributed intrusiontolerance system. When the total of processes is more than twice the number of malicious processes， the protocol can satisfy the consensus and achieve the intrusiontolerance. It proved the Correctness of the protocol.

Key words： intrusiontolerance; atomic multicast protocol; consensus; trusted timely computing base(TTCB)

世界范圍內(nèi)系統(tǒng)的廣泛互連在計(jì)算機(jī)服務(wù)行業(yè)產(chǎn)生了重要的社會(huì)經(jīng)濟(jì)價(jià)值，然而這種價(jià)值卻受到了網(wǎng)絡(luò)惡意攻擊的影響^[1]。傳統(tǒng)的網(wǎng)絡(luò)安全技術(shù)已不能完全保護(hù)網(wǎng)絡(luò)系統(tǒng)不受攻擊，因此產(chǎn)生了一種新的安全措施——入侵容忍。入侵容忍的主要思想就是承認(rèn)系統(tǒng)中存在可以被攻擊者利用的脆弱點(diǎn)，并構(gòu)建一種可以容忍一定數(shù)量故障（包括攻擊和入侵）的系統(tǒng)^[2]。目前許多容侵系統(tǒng)均采用了分布式的體系結(jié)構(gòu)。然而，分布式容侵系統(tǒng)的一個(gè)困難就是一致性問(wèn)題^[3]。一致性協(xié)議要求所有復(fù)制品的進(jìn)程均提議一個(gè)值，然后對(duì)最終決定某個(gè)值達(dá)成一致。但是系統(tǒng)中因入侵而產(chǎn)生的任意行為的惡意進(jìn)程可能會(huì)影響結(jié)果的一致性。假定分布式系統(tǒng)中進(jìn)程總數(shù)為 n，最大惡意進(jìn)程個(gè)數(shù)為 f。文獻(xiàn)[4]需要 n≥3f+1才能保證結(jié)果的一致性；文獻(xiàn)[5]要求 n≥2f+1，但其體系結(jié)構(gòu)中客戶(hù)端與服務(wù)器直接交互，存在惡意客戶(hù)端對(duì)服務(wù)器進(jìn)行攻擊的缺點(diǎn)；文獻(xiàn)[6]中進(jìn)程總數(shù)減少到 n≥f+2，但是沒(méi)有解決sender是惡意進(jìn)程以及各個(gè)進(jìn)程提交消息的全序（total order）問(wèn)題。

本文采用了基于TTCB的容侵分布式體系結(jié)構(gòu)，并在客戶(hù)端與服務(wù)器之間引入了代理服務(wù)器，可以有效阻止惡意客戶(hù)端對(duì)服務(wù)器的直接攻擊。系統(tǒng)中實(shí)現(xiàn)了容侵原子多播協(xié)議，在最大惡意進(jìn)程個(gè)數(shù)為 f的條件下，該協(xié)議只需要n≥2f+1就能保證結(jié)果的一致性。該協(xié)議還克服了sender是惡意進(jìn)程的問(wèn)題，并可以保證各個(gè)進(jìn)程以相同的順序提交消息。

1 體系結(jié)構(gòu)與TTCB

本文的容侵系統(tǒng)主要由客戶(hù)端、代理服務(wù)器和服務(wù)器組成。主代理與服務(wù)器以及服務(wù)器之間通過(guò)負(fù)載網(wǎng)絡(luò)進(jìn)行連接。筆者認(rèn)為負(fù)載網(wǎng)絡(luò)是可靠通道，即如果發(fā)送方與接收方均是正確的，它滿(mǎn)足兩個(gè)條件：a）消息最終被接收;b）傳輸通道中的消息內(nèi)容不會(huì)被竄改。系統(tǒng)的時(shí)間模型總體上是異步的，除了服務(wù)器的本地安全內(nèi)核——可信實(shí)時(shí)計(jì)算基（TTCB）^[7]，所有的TTCB通過(guò)專(zhuān)有控制通道進(jìn)行連接。容侵系統(tǒng)的體系結(jié)構(gòu)如圖1所示。

1．1 TTCB

TTCB是一種安全的實(shí)時(shí)分布式模塊，它植入在主機(jī)內(nèi)部并與操作系統(tǒng)隔離，協(xié)助分布式協(xié)議的正確執(zhí)行。將每個(gè)主機(jī)內(nèi)部的TTCB叫做本地TTCB，所有本地TTCB通過(guò)控制通道進(jìn)行連接。本地TTCB是failsilent的，它們只會(huì)因?yàn)楸罎⒉攀АＨ魏螒?yīng)用進(jìn)程均不能破壞TTCB的正確運(yùn)行，TTCB之間的交互不會(huì)發(fā)生故障，也不會(huì)產(chǎn)生錯(cuò)誤結(jié)果。每個(gè)本地TTCB擁有一個(gè)時(shí)鐘，并且所有的時(shí)鐘均是同步的。

TTCB通過(guò)接口向進(jìn)程提供有限的服務(wù)，這些服務(wù)主要分為兩類(lèi)，即安全服務(wù)和時(shí)間服務(wù)^[7]。本文中的原子組播協(xié)議使用了TTCB的三個(gè)服務(wù)：

a）本地認(rèn)證服務(wù)（LA）。該服務(wù)允許進(jìn)程與本地TTCB安全通信。服務(wù)在進(jìn)程運(yùn)行之前認(rèn)證本地TTCB，并為T(mén)TCB與進(jìn)程建立一個(gè)共享的對(duì)稱(chēng)密鑰。這個(gè)密鑰可以作為兩者之間的安全通道，用來(lái)加密和認(rèn)證它們之間的通信。

b）可信塊協(xié)商服務(wù)（TBA）。該服務(wù)是安全協(xié)議的主要組成部分。在對(duì)一組進(jìn)程提議的值協(xié)商之后，該服務(wù)就將達(dá)成一致的某一個(gè)值提交給進(jìn)程。TBA服務(wù)只應(yīng)用于協(xié)議中的重要步驟。

c）可信絕對(duì)時(shí)間戳服務(wù)（TAT）。該服務(wù)提供了具有全局意義的時(shí)間戳。

1．2 代理服務(wù)器

任意選擇一個(gè)代理服務(wù)器作為主代理，用來(lái)接收客戶(hù)端的服務(wù)請(qǐng)求，并將請(qǐng)求轉(zhuǎn)發(fā)給服務(wù)器中的sender；接收所有服務(wù)器返回的結(jié)果，將f+1個(gè)不同服務(wù)器返回的相同值作為最終結(jié)果返回給客戶(hù)端。因?yàn)橄到y(tǒng)中最大惡意進(jìn)程個(gè)數(shù)為 f，所以 f+1個(gè)值中至少有一個(gè)是正確進(jìn)程返回的，保證了結(jié)果的正確性。主代理轉(zhuǎn)發(fā)給sender的消息格式為

〈REQUEST，addr，num，cmd，vec〉。其中：REQUEST表示消息的類(lèi)型；addr表示客戶(hù)端的地址；num表示請(qǐng)求消息的序列號(hào)，在主代理中設(shè)置一個(gè)計(jì)數(shù)器，以連續(xù)遞增的方式給同一個(gè)客戶(hù)端的請(qǐng)求加上序列號(hào)；cmd表示需要執(zhí)行的請(qǐng)求命令；vec是消息認(rèn)證碼（MAC）^[5，8]向量。服務(wù)器向主代理返回的消息格式為〈REPLY，addr，num，rst〉。其中：REPLY表示消息類(lèi)型；addr表示服務(wù)器的地址；num表示請(qǐng)求消息的序列號(hào)；rst表示返回的結(jié)果。

若主代理在轉(zhuǎn)發(fā)請(qǐng)求消息之后，在時(shí)間 Ttimeout內(nèi)沒(méi)有收到 f+1個(gè)不同服務(wù)器返回的相同值，那么它就將請(qǐng)求消息發(fā)送給另外 f個(gè)不同的服務(wù)器。這樣可以保證至少有一個(gè)正確的服務(wù)器進(jìn)程接收到請(qǐng)求消息，因而在服務(wù)器之間轉(zhuǎn)發(fā)該消息。

為了防止惡意的sender竄改消息，在請(qǐng)求消息中加入了MAC向量。主代理通過(guò)MAC算法與它和各個(gè)服務(wù)器之間的共享密鑰計(jì)算出MAC值并加入到請(qǐng)求消息中，每個(gè)服務(wù)器通過(guò)驗(yàn)證自身的MAC值來(lái)判定消息是否被sender竄改。

代理服務(wù)器中存在安全檢測(cè)機(jī)制，用于檢測(cè)客戶(hù)端的惡意請(qǐng)求或攻擊行為，以及主代理是否出現(xiàn)故障或被攻克。若主代理出現(xiàn)故障或被攻克，則隨機(jī)選擇另一個(gè)代理服務(wù)器作為主代理。

1．3 服務(wù)器

將每個(gè)服務(wù)器抽象為一個(gè)進(jìn)程 pi，則 P={p0，p1，…，pn-1}表示所有服務(wù)器的集合。任意選擇 pk∈P為sender，用來(lái)接收主代理的請(qǐng)求消息，并采用多播方式將請(qǐng)求消息轉(zhuǎn)發(fā)給其他進(jìn)程。每個(gè)進(jìn)程接收到消息后，首先驗(yàn)證其有效性，然后采用同樣的方式轉(zhuǎn)發(fā)給除sender外的所有進(jìn)程。每個(gè)進(jìn)程發(fā)送od＋1次以保證所有正確進(jìn)程均能接收到請(qǐng)求消息。其中od稱(chēng)為冗長(zhǎng)度^[6]。如果一個(gè)進(jìn)程在發(fā)送者發(fā)送od+1次后還沒(méi)有收到消息，那么就認(rèn)為這個(gè)進(jìn)程出現(xiàn)了故障或受到攻擊。od的具體大小需要根據(jù)實(shí)際情況確定。關(guān)于進(jìn)程之間轉(zhuǎn)發(fā)消息的過(guò)程將在協(xié)議算法實(shí)現(xiàn)中具體論述。

2 可信塊協(xié)商服務(wù)（TBA）

可信塊協(xié)商服務(wù)由TTCB_propose，TTCB_decide和decision函數(shù)實(shí)現(xiàn)。現(xiàn)在詳細(xì)介紹一下服務(wù)中的前兩個(gè)接口函數(shù)。



進(jìn)程在提議一個(gè)值時(shí)調(diào)用TTCB_propose。其中：eid是進(jìn)程在調(diào)用之間通過(guò)本地認(rèn)證服務(wù)獲取的惟一標(biāo)志符；elist是所有參與該服務(wù)的進(jìn)程標(biāo)志符列表；tstart是通過(guò)時(shí)間服務(wù)獲取的時(shí)間戳（理想情況下服務(wù)應(yīng)該在elist中所有進(jìn)程均提議一個(gè)值之后才能執(zhí)行，但是惡意進(jìn)程可能無(wú)限期地延遲提議時(shí)間導(dǎo)致服務(wù)不能執(zhí)行。為了避免這種情況，在tstart時(shí)間后服務(wù)立即執(zhí)行并不再接受任何其他提議）；decision表示如何計(jì)算即將決定的值；value表示提議的值。TTCB_propose返回一個(gè)含有兩個(gè)字段的結(jié)構(gòu)體outp：outp.error表示返回的錯(cuò)誤碼；outp.tag表示服務(wù)執(zhí)行的惟一標(biāo)志符。TTCB通過(guò)(elist，tstart，decision)可知道不同進(jìn)程調(diào)用的TTCB_propose是否屬于同一個(gè)服務(wù)執(zhí)行。

進(jìn)程通過(guò)調(diào)用TTCB_decide函數(shù)獲取服務(wù)的結(jié)果值。Tag是由TTCB_propose返回的惟一標(biāo)志符，用于標(biāo)志一個(gè)服務(wù)執(zhí)行實(shí)例。Outd是由四個(gè)字段組成的記錄：outd.error是返回的錯(cuò)誤碼；out.value是決定的值；outd.proposedok是由Nelist（Nelist表示elist中進(jìn)程總數(shù)）位組成的掩碼，每一位表示elist中其相應(yīng)進(jìn)程提議的值是否就是最后決定的值；out.proposedany也是掩碼，但它表示的是哪些進(jìn)程提議的是任意值。

3 容侵原子多播協(xié)議的實(shí)現(xiàn)

3．1 容侵原子多播協(xié)議

服務(wù)器進(jìn)程通過(guò)原子多播協(xié)議提交消息。該協(xié)議具有以下四個(gè)特性：

a）有效性。如果一個(gè)正確進(jìn)程以多播方式發(fā)送消息M，所有的MAC均為有效，那么某一個(gè)正確進(jìn)程最終將提議M。

b）一致性。如果一個(gè)正確進(jìn)程提議消息M，那么所有正確進(jìn)程最終將提交M。

c）完整性。對(duì)于任意一個(gè)標(biāo)志符ID，每個(gè)正確進(jìn)程最多只能提交一次標(biāo)志符是ID的消息M。如果M的發(fā)送者是正確的，那么M先前就是由該發(fā)送者轉(zhuǎn)發(fā)的。

d）全序性。如果兩個(gè)正確進(jìn)程均提交消息M1和M2，那么這兩個(gè)進(jìn)程將以相同的次序提交這兩條消息。

協(xié)議算法主要由三部分組成，即初始化、sender協(xié)議以及接收方協(xié)議。

算法1 原子多播協(xié)議（對(duì)于所有 pi∈P，i=(0，1，…，n-1)）

Initialization:

1: elist ←all eids of processes in P

2: msg_id ←//set of MREQ.num

3: prepare_deliv ←//set of M preparing for delivery

4: minnum←1

Sender:

5: tstart ←TTCB_getTimestamp()+T0

6: M ← (elist， tstart， MREQ) //construct message M

7: propose ←TTCB_propose(elist， tstart， TTCB_TBA_RMULTICAST， H(M))//propose M

8: multicast M for od+1 times to elist except sender

9: Atomic_deliver(M)

Recipients:

10: Get_msg(M)//get message M

11: if verify_mac(MREQ.vec[pi]) then propose ≠TTCB_propose(M.elist， M.tstart， TTCB_TBA_RMULTICAST，⊥)

12: do decide ←TTCB_decide(propose.tag)//decide the result

13:while (decide.error ≠TTCB_TBA_ENDED)

14: while (H(M) ≠decide.value) do Get_msg(M) od

15: multicast M for od+1 times to elist except sender

16: Atomic_deliver(M)

When Atomic_deliver(M) is called do:

17: msg_id ←msg_id ∪{MREQ.num}

18: prepare_deliv ←prepare_deliv ∪{MREQ}

19: minnum ← min(msg_id)

20: while (MREQ.num=minnum) and (msg_id ≠) do

21: msg_id ←msg_id{MREQ.num}

22: prepare_deliv ←prepare_deliv{MREQ}

23: minnum ←minnum+1

24: deliver(M) od

初始化過(guò)程將所有進(jìn)程的eid存放在elist中，msg_id是存儲(chǔ)請(qǐng)求消息MREQ序列號(hào)MREQ.num的數(shù)組；prepare_deliv是存儲(chǔ)準(zhǔn)備提交的消息數(shù)組；minnum表示msg_id中序列號(hào)的最小值。

進(jìn)程之間轉(zhuǎn)發(fā)的消息M由（elist， tstart， MREQ）組成。其中：elist是符合TTCB服務(wù)格式的eid列表，列表中第一個(gè)元素是sender的eid，其他元素為接收方的eid；tstart是服務(wù)的時(shí)間戳；MREQ表示請(qǐng)求消息。協(xié)議的每一次執(zhí)行實(shí)例由惟一的標(biāo)志符（elist， tstart）表示。Get_msg()從消息M中讀取（elist， tstart， MREQ）。假定存在一個(gè)垃圾消息處理器，其作用就是銷(xiāo)毀已經(jīng)提交過(guò)的相同消息。

Sender協(xié)議首先計(jì)算tstart，并根據(jù)主代理的請(qǐng)求消息MREQ以及elist，構(gòu)建消息M（5、6行）。一個(gè)服務(wù)執(zhí)行由elist、tstart和decision函數(shù)決定（7行）。Sender和所有接收方均使用相同的decision函數(shù)TTCB_TBA_RMULTICAST。這個(gè)函數(shù)表示將選擇由elist中第一個(gè)進(jìn)程提議的值作為結(jié)果值（即sender提議的值）。Sender提議的值是消息M的哈希值H（M），并通過(guò)控制通道發(fā)送給接收方。哈希函數(shù)是一種單向加密函數(shù)，根據(jù)哈希函數(shù)的性質(zhì)^[8]，攻擊者是不能夠通過(guò)哈希值獲取原始消息的。Sender將消息以多播方式轉(zhuǎn)發(fā)給其他進(jìn)程，然后執(zhí)行atomic_deliver()提交消息M（8、9行）。接收方調(diào)用get_msg()函數(shù)等待接收消息，并通過(guò)MAC來(lái)驗(yàn)證消息的合法性（10、11行）；然后調(diào)用函數(shù)TTCB_propose獲取標(biāo)志服務(wù)的tag，接著循環(huán)調(diào)用TTCB_decide，確保協(xié)議等待服務(wù)結(jié)束（12、13行）。如果接收到的消息與sender轉(zhuǎn)發(fā)的消息不同，那么H（M）就會(huì)與服務(wù)返回的值decide.value不同。在這種情況下，協(xié)議需要等待接收到正確的消息（14行）；然后采用多播方式將消息轉(zhuǎn)發(fā)給除sender外的所有進(jìn)程，最后執(zhí)行atomic_deli_ver()提交消息M（15、16行）。當(dāng)執(zhí)行atomic_deliver()提交消息M時(shí)，先將MREQ.num和MREQ分別存放在數(shù)組msg_id和prepare_deliv中，然后找出msg_id中的最小值（17~19行）。如果MREQ.num是最小值，則從數(shù)組msg_id和prepare_deliv中移出MREQ.num和MREQ，同時(shí)將minnum加1，最后提交消息M（20~24行）。

3．2 正確性證明

下面對(duì)算法1所描述的協(xié)議是否滿(mǎn)足原子多播協(xié)議的四個(gè)性質(zhì)進(jìn)行證明。

定理1 有效性。如果一個(gè)正確進(jìn)程以多播方式發(fā)送消息M，其中所有的MAC都是有效的，那么某一個(gè)正確進(jìn)程最終將提議M。

證明 設(shè)消息M＝（elist， tstart， MREQ），任意一個(gè)正確進(jìn)程 pi∈P， pi以多播方式發(fā)送消息M給其他進(jìn)程（8行或15行）。設(shè)另一個(gè)任意的正確進(jìn)程 pk∈P，根據(jù)可靠通道的性質(zhì)， pk最終接收到消息M。 pk通過(guò)驗(yàn)證其MAC可以證明消息MREQ沒(méi)有被竄改（11行），又因?yàn)?pi是正確進(jìn)程，那么消息M是正確的，所以可以執(zhí)行12~16行。根據(jù)23行，數(shù)組msg_id中MREQ.num最終會(huì)成為最小值，所以消息M最終將會(huì)被 pk提交（24行）。

定理2 一致性。如果一個(gè)正確進(jìn)程提議消息M，那么所有正確進(jìn)程最終將提交M。

證明 任意一個(gè)正確進(jìn)程 pi∈P，若 pi提議一條消息M，那么 pi在提議之前以多播方式發(fā)送了消息M。根據(jù)定理1，存在一個(gè)正確進(jìn)程 pk∈P最終提交M，而 pk在提交之前同樣會(huì)轉(zhuǎn)發(fā)M，因此所有正確進(jìn)程都會(huì)接收到來(lái)自其他正確進(jìn)程的消息M，并且最終提交M。

定理3 完整性。對(duì)于任意一個(gè)標(biāo)志符ID，每個(gè)正確進(jìn)程最多只能提交一次標(biāo)志符是ID的消息M。如果M的發(fā)送者是正確的，那么M先前就是由該發(fā)送者轉(zhuǎn)發(fā)的。

證明 消息M的標(biāo)志符ID是（elist， tstart， MREQ），一個(gè)TBA服務(wù)執(zhí)行實(shí)例由惟一的標(biāo)志符（elist， tstart）表示，所以標(biāo)志符是ID的消息M只能由TBA執(zhí)行一次，正確進(jìn)程只能提交一次消息M。根據(jù)可靠通道的性質(zhì)可知，定理后半部分是正確的。

定理4 全序性。如果兩個(gè)正確進(jìn)程均提交消息M1和M2，那么這兩個(gè)進(jìn)程以相同的次序提交這兩條消息。

證明 因?yàn)樗羞M(jìn)程都提交msg_id中最小序列號(hào)所對(duì)應(yīng)的消息，若M2.MREQ.num>M1.MREQ.num，那么這兩個(gè)進(jìn)程將均先提交M1然后提交M2，所以它們以相同次序提交這兩條消息。

4 結(jié)束語(yǔ)

入侵容忍作為信息安全領(lǐng)域的前沿研究課題，正越來(lái)越受到各方面的重視。入侵容忍的基本體系結(jié)構(gòu)是分布式的，但是在存在入侵的情況下，如何對(duì)分布式結(jié)果達(dá)成一致是一個(gè)重要問(wèn)題。本文在分布式容侵系統(tǒng)中利用TTCB服務(wù)實(shí)現(xiàn)了容侵原子多播協(xié)議，有效地解決了一致性問(wèn)題。在最大惡意進(jìn)程個(gè)數(shù)為 f的情況下，該協(xié)議只需分布式系統(tǒng)中進(jìn)程總數(shù) n≥2f+1就可以滿(mǎn)足正確結(jié)果的一致性要求，達(dá)到了入侵容忍的目的。

參考文獻(xiàn)：

［1］ VERíSSIMO P， NEVES N F， CACHIN C. Intrusiontolerant middleware: the road to automatic security[J]. IEEE Security Privacy， 2006， 4(4):54-62.

［2］CORREIA M， NEVES N F， LUNG L C， et al. Byzantineresistant consensus based on a novel approach to intrusion tolerance[C]//Proc of the 10th Pacific Rim International Symposium on Dependable Computing. Tahiti， French Polynesia:[s.n.]，2004.

［3］MONIZ H， NEVES N F， CORREIA M. Randomized intrusiontolerant asynchronous services[C]// Proc ofInternational Conference on Dependable Systems and Networks.2006:568-577.

［4］REITER M K. A secure group membership protocol[J].IEEE Trans on Software Engineering， 1996， 22(1):31-42.

［5］CORREIA M， NEVES N F， VERíSSIMO P. How to tolerate half less one Byzantine nodes in practical distributed systems[C]// Proc of the 23rd IEEE Symposium on Reliable Distributed Systems. 2004:174-183.

［6］LUNG L C， CORREIA M， NEVES N F， et al. A simple intrusiontolerant reliable multicast protocol using the TTCB[EB/OL]．(2003). http:∥www.di.fc.ul.pt/～nuno/PAPERS/ SBRC03.pdf.

［7］CORREIA M， VERíSSIMO P， NEVES N F. The design of a COTS realtime distributed security kernel[C]// Proc of the 4th European Dependable Computing Conference. 2002:234-252.

［8］MENEZES A J， OORSCHOT P C， VANSTONE S A. Handbook of applied cryptography[M]. [S.l.] : CRC Press， 1996.

注：“本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文。”