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

摘 要：對基于可信實時計算基（TTCB）的分布式容侵系統的體系結構進行了研究，針對分布式容侵系統中的一致性問題，實現了利用TTCB服務的容侵原子多播協議。在進程總數大于兩倍惡意進程個數的條件下，該協議可以滿足正確結果的一致性要求，達到了入侵容忍的目的。最后證明了該協議算法的正確性。

關鍵詞：入侵容忍；原子多播協議；一致性；可信實時計算基

中圖分類號：TP309．2 文獻標志碼：A

文章編號：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)

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

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

1 體系結構與TTCB

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

1．1 TTCB

TTCB是一種安全的實時分布式模塊，它植入在主機內部并與操作系統隔離，協助分布式協議的正確執行。將每個主機內部的TTCB叫做本地TTCB，所有本地TTCB通過控制通道進行連接。本地TTCB是failsilent的，它們只會因為崩潰才失效。任何應用進程均不能破壞TTCB的正確運行，TTCB之間的交互不會發生故障，也不會產生錯誤結果。每個本地TTCB擁有一個時鐘，并且所有的時鐘均是同步的。

TTCB通過接口向進程提供有限的服務，這些服務主要分為兩類，即安全服務和時間服務^[7]。本文中的原子組播協議使用了TTCB的三個服務：

a）本地認證服務（LA）。該服務允許進程與本地TTCB安全通信。服務在進程運行之前認證本地TTCB，并為TTCB與進程建立一個共享的對稱密鑰。這個密鑰可以作為兩者之間的安全通道，用來加密和認證它們之間的通信。

b）可信塊協商服務（TBA）。該服務是安全協議的主要組成部分。在對一組進程提議的值協商之后，該服務就將達成一致的某一個值提交給進程。TBA服務只應用于協議中的重要步驟。

c）可信絕對時間戳服務（TAT）。該服務提供了具有全局意義的時間戳。

1．2 代理服務器

任意選擇一個代理服務器作為主代理，用來接收客戶端的服務請求，并將請求轉發給服務器中的sender；接收所有服務器返回的結果，將f+1個不同服務器返回的相同值作為最終結果返回給客戶端。因為系統中最大惡意進程個數為 f，所以 f+1個值中至少有一個是正確進程返回的，保證了結果的正確性。主代理轉發給sender的消息格式為

〈REQUEST，addr，num，cmd，vec〉。其中：REQUEST表示消息的類型；addr表示客戶端的地址；num表示請求消息的序列號，在主代理中設置一個計數器，以連續遞增的方式給同一個客戶端的請求加上序列號；cmd表示需要執行的請求命令；vec是消息認證碼（MAC）^[5，8]向量。服務器向主代理返回的消息格式為〈REPLY，addr，num，rst〉。其中：REPLY表示消息類型；addr表示服務器的地址；num表示請求消息的序列號；rst表示返回的結果。

若主代理在轉發請求消息之后，在時間 Ttimeout內沒有收到 f+1個不同服務器返回的相同值，那么它就將請求消息發送給另外 f個不同的服務器。這樣可以保證至少有一個正確的服務器進程接收到請求消息，因而在服務器之間轉發該消息。

為了防止惡意的sender竄改消息，在請求消息中加入了MAC向量。主代理通過MAC算法與它和各個服務器之間的共享密鑰計算出MAC值并加入到請求消息中，每個服務器通過驗證自身的MAC值來判定消息是否被sender竄改。

代理服務器中存在安全檢測機制，用于檢測客戶端的惡意請求或攻擊行為，以及主代理是否出現故障或被攻克。若主代理出現故障或被攻克，則隨機選擇另一個代理服務器作為主代理。

1．3 服務器

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

2 可信塊協商服務（TBA）

可信塊協商服務由TTCB_propose，TTCB_decide和decision函數實現。現在詳細介紹一下服務中的前兩個接口函數。



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

進程通過調用TTCB_decide函數獲取服務的結果值。Tag是由TTCB_propose返回的惟一標志符，用于標志一個服務執行實例。Outd是由四個字段組成的記錄：outd.error是返回的錯誤碼；out.value是決定的值；outd.proposedok是由Nelist（Nelist表示elist中進程總數）位組成的掩碼，每一位表示elist中其相應進程提議的值是否就是最后決定的值；out.proposedany也是掩碼，但它表示的是哪些進程提議的是任意值。

3 容侵原子多播協議的實現

3．1 容侵原子多播協議

服務器進程通過原子多播協議提交消息。該協議具有以下四個特性：

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

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

c）完整性。對于任意一個標志符ID，每個正確進程最多只能提交一次標志符是ID的消息M。如果M的發送者是正確的，那么M先前就是由該發送者轉發的。

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

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

算法1 原子多播協議（對于所有 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

初始化過程將所有進程的eid存放在elist中，msg_id是存儲請求消息MREQ序列號MREQ.num的數組；prepare_deliv是存儲準備提交的消息數組；minnum表示msg_id中序列號的最小值。

進程之間轉發的消息M由（elist， tstart， MREQ）組成。其中：elist是符合TTCB服務格式的eid列表，列表中第一個元素是sender的eid，其他元素為接收方的eid；tstart是服務的時間戳；MREQ表示請求消息。協議的每一次執行實例由惟一的標志符（elist， tstart）表示。Get_msg()從消息M中讀取（elist， tstart， MREQ）。假定存在一個垃圾消息處理器，其作用就是銷毀已經提交過的相同消息。

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

3．2 正確性證明

下面對算法1所描述的協議是否滿足原子多播協議的四個性質進行證明。

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

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

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

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

定理3 完整性。對于任意一個標志符ID，每個正確進程最多只能提交一次標志符是ID的消息M。如果M的發送者是正確的，那么M先前就是由該發送者轉發的。

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

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

證明 因為所有進程都提交msg_id中最小序列號所對應的消息，若M2.MREQ.num>M1.MREQ.num，那么這兩個進程將均先提交M1然后提交M2，所以它們以相同次序提交這兩條消息。

4 結束語

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

參考文獻：

［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.

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