淺析基于可驗(yàn)證計(jì)算的可信云計(jì)算優(yōu)秀論文

1 引 言

　　云計(jì)算作為一種新興的網(wǎng)絡(luò)計(jì)算商業(yè)服務(wù)模式，使得用戶可以隨時(shí)在遠(yuǎn)端的云服務(wù)器存儲(chǔ)數(shù)據(jù)和運(yùn)行程序.但這種新興的計(jì)算模式在給用戶帶來(lái)諸多便利性的同時(shí)，也帶來(lái)了一些新的安全挑戰(zhàn).用戶可能擔(dān)心云計(jì)算平臺(tái)本身的安全性，比如云平臺(tái)漏洞和錯(cuò)誤配置、管理員的惡意行為等等，而這都可能直接導(dǎo)致用戶數(shù)據(jù)的完整性和隱私性受到危害，導(dǎo)致用戶應(yīng)用程序無(wú)法正確執(zhí)行.這就產(chǎn)生了一個(gè)問(wèn)題：用戶如何相信云提供商執(zhí)行的程序結(jié)果是正確的?如何確保存儲(chǔ)在遠(yuǎn)端的數(shù)據(jù)的完整性和私密性?檢測(cè)遠(yuǎn)程服務(wù)器返回的結(jié)果是否正確的傳統(tǒng)解決方案有以下幾種：

　　(1)采用審計(jì)的方法，即隨機(jī)選取服務(wù)器執(zhí)行的一小部分程序進(jìn)行驗(yàn)證，這就可能發(fā)生錯(cuò)誤執(zhí)行的程序沒(méi)有被服務(wù)器驗(yàn)證的情況，所以說(shuō)這種方法必須假設(shè)錯(cuò)誤執(zhí)行的程序的發(fā)生頻率是很小的;

　　(2)利用可信硬件和遠(yuǎn)程證明來(lái)保證遠(yuǎn)程服務(wù)器運(yùn)行的程序是正確的，但是這種方法必須假設(shè)云提供商是完全可信的，由于硬件基礎(chǔ)設(shè)施是在云提供商的控制之下，如果云提供商內(nèi)部人員惡意控制了可信硬件(如CPU、TPM)，就無(wú)法保障云提供商運(yùn)行的程序的機(jī)密性和可驗(yàn)證性.而且還需要假設(shè)存在一個(gè)可信鏈，而運(yùn)行時(shí)可信鏈的建立在可信計(jì)算領(lǐng)域依然是一個(gè)難題.事實(shí)上，在實(shí)際的云計(jì)算應(yīng)用場(chǎng)景中這兩個(gè)假設(shè)通常是無(wú)法滿足的.在云計(jì)算場(chǎng)景中，用戶無(wú)法完全相信云提供商，即使用戶出于聲譽(yù)的考慮相信云提供商本身，也無(wú)法相信其內(nèi)部管理人員;

　　(3)采用冗余計(jì)算的方法，用戶可以讓多個(gè)遠(yuǎn)程服務(wù)器把相同的程序執(zhí)行多次，然后檢測(cè)他們返回的結(jié)果是否一致.但這在云計(jì)算中也是行不通的，云計(jì)算中的軟硬件平臺(tái)配置通常是相同的，而這違背了冗余計(jì)算中錯(cuò)誤必須是不相關(guān)的假設(shè)，且遠(yuǎn)程服務(wù)器很容易竄通，合謀返回一個(gè)錯(cuò)誤的程序執(zhí)行結(jié)果.

　　而可證明數(shù)據(jù)持有(Provable Data Possession，PDP)方法和可恢復(fù)證明(Proof of Retrievability，POR)方法可以用來(lái)確保存儲(chǔ)在遠(yuǎn)端的數(shù)據(jù)的完整性，避免云提供商刪除和篡改數(shù)據(jù).相比PDP方法，POR除了能確保數(shù)據(jù)的完整性之外，還能確保數(shù)據(jù)的可恢復(fù)性，但是PDP和POR無(wú)法確保在云提供商端執(zhí)行的程序的正確性.另一方面，基于復(fù)雜性理論的交互式證明系統(tǒng)(Interactive Proof system，IPs)和概率可驗(yàn)證證明系統(tǒng)(Probabilistically Checkable Proof system，PCPs)以及密碼學(xué)理論構(gòu)造的可驗(yàn)證計(jì)算協(xié)議能以很高的正確率檢測(cè)出遠(yuǎn)程服務(wù)器返回的程序執(zhí)行結(jié)果是否正確并且不需要對(duì)遠(yuǎn)程服務(wù)器(云提供商)做任何假設(shè).可驗(yàn)證計(jì)算協(xié)議致力于設(shè)計(jì)驗(yàn)證者與證明者之間的協(xié)議，協(xié)議允許在計(jì)算能力上相對(duì)較弱的驗(yàn)證者(如云計(jì)算中的用戶)將其程序發(fā)送到一個(gè)計(jì)算能力強(qiáng)大的，但不可信的證明者(例如云提供商)，并要求證明者執(zhí)行其發(fā)送的程序.所設(shè)計(jì)的協(xié)議應(yīng)確保證明者不但返回程序的執(zhí)行結(jié)果給驗(yàn)證者，并且使得驗(yàn)證者相信這個(gè)程序執(zhí)行結(jié)果是正確的.其主要目標(biāo)是使得服務(wù)器在發(fā)送程序執(zhí)行結(jié)果的同時(shí)提供程序正確執(zhí)行的證據(jù)，而用戶驗(yàn)證證據(jù)的過(guò)程必須要比用戶自己執(zhí)行程序的開(kāi)銷小(當(dāng)然有時(shí)由于資源比如存儲(chǔ)的限制，用戶根本無(wú)法自己執(zhí)行程序，在這種情況下是指和假設(shè)用戶有足夠的資源執(zhí)行程序時(shí)的開(kāi)銷相比要小)。

　　2 問(wèn)題描述和協(xié)議設(shè)計(jì)原則問(wèn)題描述：

　　驗(yàn)證者V把程序f和輸入變量x發(fā)送給證明者P，P計(jì)算f(x)，并把f(x)賦值給變量y，返回y給V，然后V 和P 以如下方式進(jìn)行交互：

　　(1)如果y=f(x)，那么P 應(yīng)該能向V 證明y的正確性，即使得V 接受y.其中，證明可以通過(guò)回答V 提出的一些問(wèn)題完成，也可以通過(guò)給V 提供一個(gè)證書(shū)完成.

　　(2)如果y≠f(x)，V 能以很高的概率拒絕接受y.可驗(yàn)證計(jì)算協(xié)議的設(shè)計(jì)必須滿足3個(gè)基本原則：(1)協(xié)議應(yīng)該使得驗(yàn)證者的開(kāi)銷比其在本地執(zhí)行程序f(x)的開(kāi)銷要低，但可以允許證明者為達(dá)到協(xié)議的目標(biāo)產(chǎn)生合理的開(kāi)銷，因?yàn)樘峁┻\(yùn)行程序的正確性保障本身就需要用戶付出一定的代價(jià)，在云計(jì)算實(shí)際場(chǎng)景中，表現(xiàn)為云提供商可能會(huì)對(duì)需要提供程序正確執(zhí)行證據(jù)的用戶收取額外的費(fèi)用;

　　(2)不能假設(shè)證明者完全遵守協(xié)議，也就是說(shuō)證明者可能是惡意的，這和云計(jì)算中不能假設(shè)云提供商是完全可信的實(shí)際場(chǎng)景也是十分吻合的;

　　(3)f 應(yīng)該是通用程序，然而在具體的協(xié)議設(shè)計(jì)中，可能需要對(duì)f 表示的程序做一些假設(shè)，從而通過(guò)限制可驗(yàn)證計(jì)算協(xié)議適用的應(yīng)用程序種類使得協(xié)議的性能達(dá)到實(shí)際應(yīng)用場(chǎng)景的要求，但是可驗(yàn)證計(jì)算協(xié)議的設(shè)計(jì)原則依然是盡量能表示通用程序.

　　通常的安全保障工具比如說(shuō)病毒檢測(cè)關(guān)注的都是不正確的行為的識(shí)別和防范，可驗(yàn)證計(jì)算協(xié)議則有所不同，其不關(guān)心證明者可能的不正確行為，比如犯了什么錯(cuò)誤，出現(xiàn)了什么故障等等，而只關(guān)心其執(zhí)行程序的結(jié)果是否是正確的，卻無(wú)法推測(cè)程序錯(cuò)誤執(zhí)行的原因.這和云計(jì)算中用戶對(duì)于程序執(zhí)行的要求也是相符的.

　　3 協(xié)議流程和關(guān)鍵

　　3.1 可驗(yàn)證計(jì)算協(xié)議流程

　　可驗(yàn)證計(jì)算協(xié)議的流程主要包括編譯處理和證明系統(tǒng)，具體流程如圖1所示.首先是編譯處理階段，驗(yàn)證者V 和證明者P 將高級(jí)語(yǔ)言(比如C 語(yǔ)言)編寫的程序轉(zhuǎn)換成一組布爾電路集(根據(jù)協(xié)議的不同，也可以是其他計(jì)算模型比如算術(shù)電路集或者約束集等).接下來(lái)，P 和V 進(jìn)行一系列協(xié)議交互，不失一般性，這里用布爾電路集C表示程序f.V 把輸入變量x傳輸給P，P 計(jì)算C，輸出程序執(zhí)行結(jié)果y和C正確執(zhí)行的一組軌跡{C，x，y｝給V，{C，x，y｝也稱為C的一個(gè)可滿足性賦值z(mì).其中，C正確執(zhí)行的一組軌跡是指C的輸入線路被賦值為x，輸出線路被賦值為f(x)時(shí)，電路集中所有電路門的賦值集合.在程序執(zhí)行的過(guò)程中，證明者P 獲得了正確計(jì)算電路的執(zhí)行軌跡{C，x，y｝.如果P 聲稱的輸出y是不正確的，即y不等于f(x)，那么對(duì)于{C，x，y｝，就不可能存在一個(gè)有效的執(zhí)行軌跡(電路C正確計(jì)算的一個(gè)證明).因此，如果P 能夠?qū)C，x，y｝構(gòu)建一個(gè)有效的執(zhí)行軌跡，那么就一定能使得驗(yàn)證者V 相信它返回的結(jié)果是正確的.顯然，電路正確計(jì)算過(guò)程中的各個(gè)門的賦值本身就能說(shuō)明存在有效的執(zhí)行軌跡.但是，如果需要V 依次驗(yàn)證所有電路門在計(jì)算電路過(guò)程中的值，進(jìn)而確定程序是否正確執(zhí)行，這個(gè)工作量和V 本地執(zhí)行f 是相當(dāng)?shù)模@就違背了可驗(yàn)證計(jì)算協(xié)議設(shè)計(jì)的基本原則.所以，圖中第步就需要證明者對(duì)程序執(zhí)行軌跡編碼，生成一個(gè)很長(zhǎng)的字符串，并使得不同的執(zhí)行軌跡生成的編碼在所有不同的位置的取值是不相同的.這樣，驗(yàn)證者就可以通過(guò)檢查隨機(jī)選擇的編碼的特定的位置的取值，來(lái)驗(yàn)證執(zhí)行軌跡的有效性，進(jìn)而對(duì)返回的結(jié)果采取特定的測(cè)試來(lái)確定證明者返回的結(jié)果是否正確.

　　3.2 可驗(yàn)證計(jì)算協(xié)議的理論依據(jù)

　　理解可驗(yàn)證計(jì)算協(xié)議的原理和流程關(guān)鍵在于理解兩個(gè)等價(jià)關(guān)系，如3.1節(jié)所述，可驗(yàn)證計(jì)算協(xié)議的流程主要包括編譯處理和證明系統(tǒng).其中，編譯處理階段，編譯器完成高級(jí)語(yǔ)言程序到電路集或者約束集(可以看做方程組)等計(jì)算模型的轉(zhuǎn)化，其實(shí)現(xiàn)的理論依據(jù)在于等價(jià)關(guān)系：程序執(zhí)行的正確性等價(jià)于電路集或者約束集可滿足問(wèn)題.