基于動態(tài)域劃分的MapReduce安全冗余調(diào)度策略

沈晴霓，卿斯?jié)h,3，吳中海，張力哲，楊雅輝

(1. 北京大學(xué) 軟件與微電子學(xué)院，北京 102600；2. 北京大學(xué) 網(wǎng)絡(luò)與軟件安全保障教育部重點(diǎn)實驗室，北京 100871；3. 中國科學(xué)院 軟件研究所，北京 100190)

1 引言

MapReduce是Google設(shè)計的并行數(shù)據(jù)處理模型[1](如圖1所示)，它主要由一個中央節(jié)點(diǎn)(JobTracker)和若干計算節(jié)點(diǎn)(TaskTracker，也稱node，可以是物理機(jī)器，也可以是虛擬機(jī))組成，用戶提交的作業(yè)(Job)首先在中央節(jié)點(diǎn)被劃分成多個任務(wù)(Task,分為Map和Reduce 2個階段)，中央節(jié)點(diǎn)根據(jù)一定的調(diào)度策略將這些 Map/Reduce任務(wù)分配給不同的計算節(jié)點(diǎn)來完成，這些任務(wù)并行地對各自的輸入數(shù)據(jù)塊、中間結(jié)果進(jìn)行處理后產(chǎn)生最終輸出結(jié)果(均為Key-Value形式)。近年來，許多公司使用MapReduce模型處理自己的數(shù)據(jù)業(yè)務(wù)，包括網(wǎng)頁搜索、高端計算、數(shù)據(jù)分析和機(jī)器學(xué)習(xí)等。隨著目前云計算模式的推出和迅速發(fā)展，提供以MapReduce為基礎(chǔ)的可擴(kuò)展、低成本的海量數(shù)據(jù)處理開放式服務(wù)的需求成為了業(yè)界發(fā)展趨勢[1～4]。

圖1 MapReduce并行計算模型

但是，使用 MapReduce的云服務(wù)系統(tǒng)是開放式、多租戶的基礎(chǔ)架構(gòu)（租戶是指租賃云服務(wù)系統(tǒng)的計算/存儲服務(wù)的實體，一個租戶是一個組織/機(jī)構(gòu)/個體，如銀行、企業(yè)、高?；騻€人），除了傳統(tǒng)的通信安全威脅，如數(shù)據(jù)竊聽、重放攻擊以及拒絕服務(wù)攻擊等，還存在自身安全的復(fù)雜性和特殊性[2～4]，特別地，在MapReduce中央節(jié)點(diǎn)對大規(guī)模不同租戶的作業(yè)進(jìn)行調(diào)度的過程中，它可能面臨如下新的安全問題。

1)租戶X和租戶Y是競爭關(guān)系，但是X的任務(wù)Tx與Y的任務(wù)Ty可能在某個時刻被同時分配到同一個計算節(jié)點(diǎn)N，從而導(dǎo)致一方(Tx或Ty)信息被另一方(Ty或Tx)惡意竊取或篡改。

2)租戶X的任務(wù)Tx可能被分配到一個已被惡意控制的計算節(jié)點(diǎn)N上，導(dǎo)致節(jié)點(diǎn)N的控制者可以任意篡改 Tx的計算結(jié)果或者直接返回一個錯誤的結(jié)果，從而欺騙中央節(jié)點(diǎn)或者租戶X。

3)租戶X的任務(wù)Tx可能被分配到一個計算節(jié)點(diǎn)N，而節(jié)點(diǎn)N中正在運(yùn)行某個租戶Z的一個被注入了惡意代碼的任務(wù)Tz，導(dǎo)致Z可以利用Tz來破壞Tx的計算環(huán)境和類似2）的計算結(jié)果的完整性。

然而，在面向云服務(wù)的 MapReduce計算框架中，目前采用的調(diào)度策略重點(diǎn)關(guān)注的仍然是作業(yè)的優(yōu)先級、資源的利用率、資源分配的公平性、調(diào)度的實時性、異構(gòu)環(huán)境的支持能力等問題[5～11]，對其中可能面臨的上述安全性問題卻考慮很少。

本文的創(chuàng)新之處在于以下3點(diǎn)。

1)提出一種動態(tài)域劃分模型。通過引入沖突關(guān)系、信任度和安全標(biāo)簽等概念，以及為不同租戶作業(yè)定義3種域劃分策略，將每個待調(diào)度節(jié)點(diǎn)劃分為與租戶作業(yè)關(guān)聯(lián)的沖突域、調(diào)度域或可信域。

2)提出一種基于動態(tài)域劃分的安全冗余調(diào)度策略，包括：①根據(jù)動態(tài)域劃分模型和冗余方式[8～10]，將每個任務(wù)的2個副本（副本1和副本2）同時分配給與其作業(yè)關(guān)聯(lián)的調(diào)度域節(jié)點(diǎn)和可信域節(jié)點(diǎn)(但不允許是沖突域節(jié)點(diǎn))，從而保證沖突關(guān)系租戶的計算任務(wù)不會被同時調(diào)度到同一個計算節(jié)點(diǎn)；②通過任務(wù)副本1在可信域節(jié)點(diǎn)上執(zhí)行環(huán)境散列校驗值，以及它對隨機(jī)選取的小部分輸入的計算結(jié)果散列校驗值，對比任務(wù)副本2在調(diào)度域節(jié)點(diǎn)上的任務(wù)執(zhí)行環(huán)境和計算結(jié)果散列校驗值，如果不一致，則重新調(diào)度該任務(wù)，如果一致，則認(rèn)為調(diào)度域可以繼續(xù)完成當(dāng)前任務(wù)。從而保證合法租戶的計算任務(wù)不會調(diào)度到可能是惡意租戶的節(jié)點(diǎn)或可能運(yùn)行著惡意租戶任務(wù)的節(jié)點(diǎn)。

3)通過在Hadoop MapReduce調(diào)度器中的原型實現(xiàn)、性能測試和安全性分析論證了策略的有效性。

2 相關(guān)工作

目前，Hadoop MapReduce的調(diào)度策略主要分為3種類型：基于優(yōu)先級的調(diào)度策略(FIFO)[2]、基于資源利用率優(yōu)化的調(diào)度策略(capacity scheduler)[5]和基于資源分配公平性的調(diào)度策略(fair scheduler)[6,7]。其中，基于優(yōu)先級的調(diào)度策略按任務(wù)的優(yōu)先級高低調(diào)度計算節(jié)點(diǎn)；基于資源利用率優(yōu)化的調(diào)度策略通過設(shè)置多個作業(yè)隊列并行調(diào)度計算節(jié)點(diǎn)，提高資源的利用率；基于資源分配公平性的調(diào)度策略通過設(shè)置每個作業(yè)可調(diào)度的資源池相等，實現(xiàn)公平的調(diào)度。此外，為了避免同構(gòu)集群中少數(shù)任務(wù)落后導(dǎo)致整個作業(yè)進(jìn)度變慢問題，Hadoop調(diào)度器[2]提供一種冗余調(diào)度策略，它監(jiān)控每個任務(wù)的進(jìn)度，如果一個任務(wù)的進(jìn)度明顯落后于同類型任務(wù)進(jìn)度(如落后20%)，則把它當(dāng)成落后任務(wù)，為它啟動一個備份任務(wù)，二者同時執(zhí)行，誰先完成和提交，則采取誰的結(jié)果。LATE調(diào)度器[8]通過設(shè)置可同時執(zhí)行的備份任務(wù)上限等，解決異構(gòu)集群中同類型Task進(jìn)度差異大時的性能優(yōu)化問題。軟、硬實時調(diào)度器[9～11]保證有時間限制要求的作業(yè)在規(guī)定時限內(nèi)完成。但上述策略均很少考慮安全性問題。

Wei W等[12]曾經(jīng)為MapReduce提出一種基于冗余計算方式的安全調(diào)度策略，設(shè)計了非集中式的委托協(xié)議和驗證協(xié)議，目標(biāo)是保證數(shù)據(jù)處理過程的完整性。它在為一個計算任務(wù)同時分配2個計算節(jié)點(diǎn)的調(diào)度策略中重點(diǎn)考慮2個方面的安全問題：一是，如何保護(hù)任務(wù)分配消息的完整性和機(jī)密性，防止惡意的節(jié)點(diǎn)竊取好的節(jié)點(diǎn)的任務(wù)分配信息或任意偽造任務(wù)信息達(dá)到拒絕服務(wù)攻擊(DoS)的目的；二是，如何通過時間戳和序列號自動生成的任務(wù)ID信息、簽名保護(hù)機(jī)制防止對分配消息的重放攻擊。盡管它給出的完整性驗證協(xié)議可以在檢測2個計算節(jié)點(diǎn)結(jié)果出現(xiàn)不一致的情況下，向中央節(jié)點(diǎn)報告它們可能存在潛在安全風(fēng)險，但它采用的是完全冗余計算方式，且并沒有給出如何將這種檢測結(jié)果應(yīng)用到安全調(diào)度策略中，以避免將后續(xù)的任務(wù)分配給這些惡意的節(jié)點(diǎn)。Roy I[13]等設(shè)計實現(xiàn)一個基于強(qiáng)制訪問控制和差分隱私保護(hù)機(jī)制的安全 MapReduce系統(tǒng)——Airavat，使得基于敏感數(shù)據(jù)上的MapReduce計算，不論其代碼(Jobs)是否可信，都可以保證數(shù)據(jù)提供者所要求的隱私保護(hù)策略強(qiáng)制執(zhí)行。但是Airavat重點(diǎn)考慮的是如何保證任務(wù)運(yùn)行過程中不同租戶數(shù)據(jù)的隱私性，而不是任務(wù)調(diào)度決策過程中的相互安全隔離性問題。Song S等[14]針對異構(gòu)網(wǎng)格計算環(huán)境中2種啟發(fā)式作業(yè)調(diào)度算法的可信性需求，提出了3種安全調(diào)度模型：第1種是安全(secure)模型，總是分配任務(wù)給可信的計算節(jié)點(diǎn)(一個計算節(jié)點(diǎn)是可信的，當(dāng)且僅當(dāng)計算節(jié)點(diǎn)的安全級(SL)不低于被調(diào)度作業(yè)的安全需求(DS))；第2種風(fēng)險(risky)模型，分配作業(yè)給任何可用的計算節(jié)點(diǎn)，無論會有什么樣的風(fēng)險；第3種是f風(fēng)險模型，嘗試將作業(yè)分配的冒險率限制在f以內(nèi)(其中，f=0為secure模型，f=1為risky模型)；但是這3個模型針對的是來自網(wǎng)格環(huán)境中不同組織的計算節(jié)點(diǎn)本身可能是惡意的或不可信的，目的是防止其導(dǎo)致的作業(yè)調(diào)度失敗或再分配等安全性問題。此外，針對 MapReduc任務(wù)計算結(jié)果易被篡改和偽造問題，Ruan A等[15]提出一種并行的遠(yuǎn)程證實機(jī)制來保證作業(yè)輸出結(jié)果的完整性。HUANG C等[16]提出一種水印植入和隨機(jī)抽樣相結(jié)合的方法來檢測具有惡意/欺騙行為的節(jié)點(diǎn)。KHAN S M[17]等采用可信環(huán)境對不可信環(huán)境的斷點(diǎn)檢查方法形成計算結(jié)果的完整性證據(jù)，BENDAHMANE A 等[18]采用副本投票方法和信任管理系統(tǒng)來保證計算結(jié)果的完整性。但是這些工作的主要目標(biāo)只是在計算任務(wù)的執(zhí)行過程中保證計算結(jié)果的完整性。

1989年，Brewer D等[19]提出一種中國墻模型，旨在同時解決當(dāng)時信息系統(tǒng)中的機(jī)密性和完整性保護(hù)問題。目前，該模型又被看成最適用云環(huán)境資源分配和管理的安全模型之一[20～23]。例如，已經(jīng)有一些研究者采用中國墻模型的利益沖突類思想給出云存儲中的強(qiáng)制訪問控制策略[20,21]，實現(xiàn)數(shù)據(jù)集合在不同物理機(jī)器之間的強(qiáng)隔離性[22]。特別地，Chen Y C[23]等提出一種基于中國墻模型競爭關(guān)系的虛擬機(jī)安全部署策略，通過禁止競爭關(guān)系企業(yè)的虛擬機(jī)被部署到同一臺物理機(jī)器上，防止云環(huán)境中的虛擬機(jī)之間產(chǎn)生信息泄漏等安全問題。但是，上述策略考慮的只是云計算環(huán)境部署過程中的虛擬機(jī)和被存儲數(shù)據(jù)的安全性問題。

因此，以上提出的方法主要針對的是作業(yè)調(diào)度信息本身和調(diào)度之后任務(wù)執(zhí)行過程中的信息安全性問題，或者依據(jù)安全級別保證作業(yè)被調(diào)度節(jié)點(diǎn)的可信性問題，或者云計算環(huán)境部署過程中的虛擬機(jī)和被存儲數(shù)據(jù)的安全性問題。這些方法均沒有在作業(yè)調(diào)度時考慮云環(huán)境中多租戶的動態(tài)安全隔離問題。本文策略重點(diǎn)解決這個問題，使存在沖突的多租戶計算任務(wù)不會同時被分配給同一個計算節(jié)點(diǎn)，使合法租戶的計算任務(wù)不會被分配給一個可能是惡意租戶的計算節(jié)點(diǎn)或者可能運(yùn)行著惡意租戶任務(wù)的計算節(jié)點(diǎn)。

3 動態(tài)域劃分模型

本節(jié)將提出一種動態(tài)域劃分模型。通過引入沖突關(guān)系、信任度和安全標(biāo)簽等概念，以及為不同租戶作業(yè)定義的 3種域劃分策略，將每個待調(diào)度節(jié)點(diǎn)劃分為與租戶作業(yè)關(guān)聯(lián)的沖突域、調(diào)度域或可信域。

3.1 基本概念

定義1 沖突(conflict)關(guān)系：是2個租戶之間的一種關(guān)系，指的是2個租戶ui的uj在請求各自的作業(yè)調(diào)度過程中，都不希望與對方的作業(yè)被同時分配到同一個計算節(jié)點(diǎn)上，即不希望雙方的計算任務(wù)在同一個時刻運(yùn)行在同一個計算節(jié)點(diǎn)上。同時，為了保證云環(huán)境計算資源具有較高的利用率，這2個租戶并不反對在不同時刻將它們的計算任務(wù)被分配到同一個計算節(jié)點(diǎn)上運(yùn)行。則將這2個租戶之間的關(guān)系(ui,uj)稱為沖突關(guān)系，且這種關(guān)系要求具有反自反性和對稱性，但不要求可傳遞性。如 Alice銀行和Bob銀行是同一個云計算環(huán)境的2個租戶，但是它們在業(yè)務(wù)上明顯存在利益競爭關(guān)系，那么Alice和Bob都不希望它們各自租用的計算節(jié)點(diǎn)在完成自己的業(yè)務(wù)（即作業(yè)）過程中有對方的任何業(yè)務(wù)在該節(jié)點(diǎn)上同時運(yùn)行，因為他們會擔(dān)心對方惡意竊取或篡改自己業(yè)務(wù)執(zhí)行過程中用到私有數(shù)據(jù)，則(Alice銀行、Bob銀行)就屬于這種沖突關(guān)系。如果(Alice銀行、Clark公司)也屬于沖突關(guān)系，則并不應(yīng)推導(dǎo)出(Bob銀行、Clark公司)是沖突關(guān)系。

為此，系統(tǒng)需要統(tǒng)一管理和維護(hù)一個沖突關(guān)系集合C(如表1所示)，并且在每個任務(wù)調(diào)度過程中檢查待調(diào)度計算節(jié)點(diǎn)上當(dāng)前運(yùn)行任務(wù)所屬租戶，檢查他們是否與待調(diào)度任務(wù)所屬的租戶之間存在沖突關(guān)系。

表1 模型元素和域劃分策略邏輯表達(dá)式的構(gòu)造

定義2 信任度(belief)：是關(guān)于一個計算節(jié)點(diǎn)在過去一段時間內(nèi)的行為是否滿足租戶的可信性期望的一種度量。其中，租戶的可信性期望是指分配租戶作業(yè)的計算節(jié)點(diǎn)總是能夠同時滿足相關(guān)的 2個可信性屬性，即任務(wù)執(zhí)行環(huán)境的完整性和計算結(jié)果的正確性(見第 4節(jié))。作業(yè)調(diào)度器在每次決定待調(diào)度節(jié)點(diǎn)應(yīng)分配的計算任務(wù)時，需要收集該節(jié)點(diǎn)的2個可信性屬性狀態(tài)，在完成了一個作業(yè)(多個任務(wù))的分配時，綜合評估和動態(tài)更新(增/減)相關(guān)計算節(jié)點(diǎn)的信任度。這里給出一種基于PTM信任模型[24,25]的信任度更新算法。系統(tǒng)需要設(shè)置每個節(jié)點(diǎn)針對不同租戶的初始信任度，并在作業(yè)j調(diào)度完成時，將其租戶u對被調(diào)度節(jié)點(diǎn)p的信任度(∈[0,1])更新為：

為此，系統(tǒng)定義了租戶對計算節(jié)點(diǎn)的信任度集合B(如表1所示)，值域規(guī)約為：4(T∈(0.75,1)))，3(T∈(0.5,0.75))，2(T∈(0.25,0.5))和 1(T∈[0,0.25]))。

定義3 安全標(biāo)簽(label)：借鑒多邊安全思想[26]，這里的安全標(biāo)簽是指系統(tǒng)為計算節(jié)點(diǎn)(虛擬機(jī)或物理機(jī))標(biāo)記的安全屬性，由2部分組成：安全級別(S)和位置集合(G)，其中，安全級別S主要是指計算節(jié)點(diǎn)的軟件運(yùn)行環(huán)境的安全級別（根據(jù)系統(tǒng)的安全評估等級來劃分，可分為C1

圖2 位置屬性之間語義層次化樹型關(guān)系

如果說 L1=(S1,G1)包含 L2=(S2,G2)，記作L1≥L2，當(dāng)且僅當(dāng)它們能夠同時滿足：S1≥S2且G2?G1；其中，G1和G2是擴(kuò)展了繼承關(guān)系的位置集合，如：G1={北京}=> G1={北京，華北，中國，亞洲}。

例如：若一個計算節(jié)點(diǎn) X標(biāo)記為L1=(B1,{北京})，通過位置屬性的擴(kuò)展后，L1≌(B1，{北京，華北，中國，亞洲}))。當(dāng)系統(tǒng)希望調(diào)度安全標(biāo)簽為L2=(B1，{華北})(≌(B1，{華北，中國，亞洲})的計算節(jié)點(diǎn)時，L1和L2滿足包含關(guān)系定義中的2個條件，即L1≥L2。若系統(tǒng)希望調(diào)度安全標(biāo)簽為L2=(B1，{中國，韓國})(≌(B1，{中國，韓國，亞洲})的計算節(jié)點(diǎn)，則L1和L2之間不滿足條件，記作L1≤≥L2。3.3節(jié)將在作業(yè)調(diào)度過程應(yīng)用這種包含關(guān)系，以確定待調(diào)度計算節(jié)點(diǎn)的安全標(biāo)簽是否滿足租戶作業(yè)的域劃分策略。

因此，系統(tǒng)將通過可為計算節(jié)點(diǎn)標(biāo)記的安全級別和位置集合等屬性，定義一個安全標(biāo)簽集合L（如表1所示），用于標(biāo)記每個計算節(jié)點(diǎn)的安全屬性。

定義4 策略表達(dá)式（policy expression）：是指系統(tǒng)將為每個租戶作業(yè)定義的一種策略邏輯表達(dá)式E(如表1所示)，它由空集、信任度、安全標(biāo)簽，以及帶括號的邏輯表達(dá)式、邏輯表達(dá)式的與(&&)或(||)非(!)操作等構(gòu)造而成。由于云服務(wù)系統(tǒng)中存在大規(guī)模、多樣化的計算資源，并且每個租戶的作業(yè)都需要通過大量的計算資源來并行調(diào)度和執(zhí)行，如果系統(tǒng)僅分配嚴(yán)格受限的少量計算資源來完成，勢必影響租戶使用云服務(wù)的體驗。為此，系統(tǒng)應(yīng)該提供一種比較靈活的策略來保證計算資源的可用性，因此對動態(tài)域劃分使用的策略采用了具有靈活組合特點(diǎn)的邏輯表達(dá)式來構(gòu)造。例如：假設(shè)系統(tǒng)通過與租戶Alice協(xié)商之后，明確了Alice對其提交作業(yè)Job在調(diào)度過程中的安全需求，其中要求：1）節(jié)點(diǎn)的安全標(biāo)簽?zāi)軌虬?L=(C1，{中國})，而且 Alice對節(jié)點(diǎn)的信任度不低于2；2）節(jié)點(diǎn)的安全標(biāo)簽?zāi)軌虬?L=(C2，{韓國})或者包含 L=(C2，{日本})，而且Alice對節(jié)點(diǎn)的信任度不低于3。為此，系統(tǒng)將對應(yīng)的策略表示為：P=(‘2’&&(C1，{中國}))|| (‘3’&&((C2，{韓國})||(C2，{日本}))。如果待調(diào)度計算節(jié)點(diǎn)X實際標(biāo)記的2個屬性為：Alice對X的信任度為2，計算節(jié)點(diǎn)當(dāng)前標(biāo)記的安全標(biāo)簽為(C2，{北京})，則根據(jù)信任度線性關(guān)系和安全標(biāo)簽的包含關(guān)系定義，該策略邏輯表達(dá)式的計算結(jié)果為真(true)，這表示節(jié)點(diǎn)X滿足了Alice對Job調(diào)度的安全需求。

3.2 模型元素及其相互之間的約束關(guān)系

系統(tǒng)將通過策略表達(dá)式 E(如表 1所示)來表達(dá)租戶對作業(yè)待調(diào)度節(jié)點(diǎn)的安全需求。這也是本文動態(tài)域劃分模型的重要基礎(chǔ)（見3.3節(jié)和4節(jié)），域劃分策略表達(dá)式的結(jié)果將決定一個計算節(jié)點(diǎn)是否被調(diào)度。因此，如表1所示，動態(tài)域劃分模型相關(guān)的模型元素主要包括：租戶集合(U)、作業(yè)集合(J)、任務(wù)集合(T)、計算節(jié)點(diǎn)集合(N)、租戶之間的沖突關(guān)系(C)、信任度集合(B)、安全標(biāo)簽集合(L)、可劃分域集合(D)、域劃分策略集合P(U,J)等(具體涵義和主要操作見表1)。此外，這些模型元素之間的關(guān)系必須滿足以下要求（如圖3所示）。

圖3 動態(tài)域劃分模型元素及其關(guān)系

1)每一個租戶都可能和若干個其他租戶之間存在沖突關(guān)系。

2)每一個租戶可以提交若干個作業(yè)，每一個作業(yè)必須屬于一個租戶。

3)每一個作業(yè)可以劃分為多個任務(wù)，每一個任務(wù)必須屬于一個作業(yè)。

4)每一個任務(wù)可以分配給若干個計算節(jié)點(diǎn)，每一個計算節(jié)點(diǎn)可以同時運(yùn)行多個任務(wù)。

5)每一個計算節(jié)點(diǎn)被賦予一個安全標(biāo)簽，每一個安全標(biāo)簽可以賦予若干個計算節(jié)點(diǎn)。

6)針對每一個租戶，一個計算節(jié)點(diǎn)有且只有一個信任度，針對不同租戶，每個計算節(jié)點(diǎn)的信任度可以不同；針對同一個租戶，具有相同信任度的計算節(jié)點(diǎn)可以有多個。

7)針對每一個租戶作業(yè)，一個計算節(jié)點(diǎn)能且只能劃分為一個域，同一個域劃分的計算節(jié)點(diǎn)可以有若干個。

8)針對每一個租戶作業(yè)，每一個域劃分策略關(guān)聯(lián)一個特定域，每一個域有一個對應(yīng)的域劃分策略。

9)每一個租戶作業(yè)有3個域劃分策略，每一個域劃分策略屬于一個租戶作業(yè)。

10)每一個租戶能為其特定作業(yè)申請若干個計算節(jié)點(diǎn)，每一個計算節(jié)點(diǎn)能承擔(dān)若干個租戶的特定作業(yè)。

3.3 沖突域、調(diào)度域和可信域的劃分策略和規(guī)則

根據(jù)3.1節(jié)和3.2節(jié)的描述，下面具體給出動態(tài)域劃分模型的主要設(shè)計思想：首先，針對不同租戶對不同作業(yè)的安全需求，系統(tǒng)將為每個作業(yè)定義如下3個策略。

沖突域劃分策略P(U,J)C，除了沖突關(guān)系集合C之外，將通過專門定義的一種沖突域劃分策略表達(dá)式（見3.1節(jié)）來進(jìn)一步約束沖突計算節(jié)點(diǎn)的屬性。例如，租戶Alice與租戶Bob為沖突關(guān)系，即(Alice,Bob)∈C，同時，若定義P(Alice,Ja)C=‘1’&&(C1,φ)，則說明Alice不希望將它的作業(yè)Ja分配給任何正在運(yùn)行 Bob作業(yè)且具有這種屬性的計算節(jié)點(diǎn)，而不是正在運(yùn)行Bob作業(yè)的所有計算節(jié)點(diǎn)。反之，如果P(Alice,Ja)C=φ，則意味著Alice不希望將它的作業(yè)Ja分配給正在運(yùn)行Bob作業(yè)的所有計算節(jié)點(diǎn)。這樣沖突關(guān)系的約束就比較靈活。

調(diào)度域劃分策略P(U,J)S，也是通過專門定義的一種調(diào)度域劃分策略表達(dá)式來約束可調(diào)度節(jié)點(diǎn)的屬性，它只是希望從原有調(diào)度策略已經(jīng)篩選出來的待調(diào)度計算節(jié)點(diǎn)中進(jìn)一步找出符合租戶對作業(yè)安全需求的計算節(jié)點(diǎn)，通常地，P(Alice,Ja)S=φ，此時表示所有待調(diào)度節(jié)點(diǎn)都可以作為可調(diào)度節(jié)點(diǎn)，以保證計算資源的高利用率。當(dāng)然，系統(tǒng)也可以根據(jù)一些特殊租戶(如銀行、證券)的要求，對可調(diào)度節(jié)點(diǎn)的要求做出進(jìn)一步的約束，如 P(Alice,Ja)S=‘2’&& (C2,{中國})，則表示 Alice希望將它的作業(yè)Ja分配給位置在中國、安全級別為C2，而且租戶對它的歷史信任度已經(jīng)達(dá)到2的計算節(jié)點(diǎn)，從而提高租戶作業(yè)的安全性。

可信域劃分策略P(U,J)T，同樣將通過專門定義的一種可信域劃分策略表達(dá)式來約束可信節(jié)點(diǎn)(用于冗余計算，見第4節(jié))的屬性，其中會對表達(dá)式中的信任度進(jìn)行最小限制，比如：要求它不低于調(diào)度域表達(dá)式中的信任度最大值，同時也會對安全標(biāo)簽進(jìn)行最小限制，比如：要求它包含調(diào)度域表達(dá)式中最大安全標(biāo)簽。假設(shè) P(Alice,Ja)S=‘2’&& (C2,{中國})，則 P(Alice,Ja)T=‘1’&& (C1,φ)將不符合要求，但 P(Alice,Ja)T=‘3’&& (C2,{北京})則符合要求，因為‘3’>‘2’且(C2,{北京})≥(C2,{中國})，從而保證系統(tǒng)為Alice的作業(yè)Ja找到合適的可信節(jié)點(diǎn)。

再者，根據(jù)系統(tǒng)為租戶作業(yè)定義的上述3個策略、計算節(jié)點(diǎn)的當(dāng)前狀態(tài)以及待調(diào)度的計算任務(wù)，將計算節(jié)點(diǎn)劃分為與任務(wù)關(guān)聯(lián)的一個域，即沖突域DC、可信域DT或調(diào)度域DS。為了便于表達(dá)，將請求調(diào)度的作業(yè)表示為j∈J，租戶信息記為u=jUser(j)∈U，當(dāng)前待調(diào)度計算節(jié)點(diǎn)為x∈N，節(jié)點(diǎn)x的當(dāng)前狀態(tài)為：u對x當(dāng)前信任度nBelief(u,x)∈B,x安全標(biāo)簽 rLable(x)∈L，及其上正在運(yùn)行作業(yè)nJobs(x)?J等。系統(tǒng)為租戶u作業(yè)j定義的3個策略為P(u,j)C、P(u,j)S、P(u,j)T，假設(shè)節(jié)點(diǎn)屬性滿足的域劃分策略至少有一個，即|nDom(x,j)|≥1，且目前待調(diào)度任務(wù)為t∈Tasks(j)，則將 x節(jié)點(diǎn)劃分為與 t關(guān)聯(lián)的一個域的幾個規(guī)則如下。

沖突域劃分規(guī)則 節(jié)點(diǎn)x被劃分為任務(wù)t的沖突域節(jié)點(diǎn)，即nCurDom(x,t)=DC，當(dāng)且僅當(dāng)對于節(jié)點(diǎn)x上正在運(yùn)行的所有作業(yè)集合nJobs(x)，至少存在一個作業(yè) j’∈nJobs(x)，j’的租戶 u’=jUser(j’)與 u屬于沖突關(guān)系，即(u,u’)∈C，且節(jié)點(diǎn)x當(dāng)前安全屬性nBelief(u,x),rLable(x)能夠使租戶u的作業(yè)j對應(yīng)的沖突域劃分策略P(u,j)C的值為真，即P(u,j)C=true。

可信域劃分規(guī)則 節(jié)點(diǎn)x被劃分為任務(wù)t的可信域節(jié)點(diǎn)，即nCurDom(x,t)=DT，當(dāng)且僅當(dāng)節(jié)點(diǎn)x當(dāng)前安全屬性nBelief(u,x),rLable(x)能夠使租戶u的作業(yè)j對應(yīng)的可信域劃分策略P(u,j)T的值為真,即P(u,j)T=true，且待調(diào)度任務(wù)t沒有分配給j對應(yīng)的任何可信域節(jié)點(diǎn)，即tNode(t,DT)=φ。

調(diào)度域劃分規(guī)則 節(jié)點(diǎn)x被劃分為任務(wù)t的調(diào)度域節(jié)點(diǎn)，即nCurDom(x,t)=DS，當(dāng)且僅當(dāng)節(jié)點(diǎn)x當(dāng)前安全屬性nBelief(u,x),rLable(x)能夠使租戶u的作業(yè)j對應(yīng)的調(diào)度域劃分策略P(u,j)S的值為真，即P(u,j)S=true，且任務(wù)t已經(jīng)分配給了j對應(yīng)的一個可信域節(jié)點(diǎn)，即tNode(t,DT)≠φ。

4 MapReduce安全冗余調(diào)度策略

4.1 威脅模型和基本假設(shè)

目前，針對MapReduce的攻擊手段可以分為以下3類。第1類是魯莽攻擊，即攻擊者控制計算節(jié)點(diǎn)，總是返回錯誤的結(jié)果；第2類是普通攻擊，即攻擊者以一定的概率（而不是 100%）返回錯誤的結(jié)果，本類攻擊比較常見，比第1類攻擊有更高的成功率，也更難以識破；第3類是機(jī)智攻擊，即攻擊者假設(shè)MapReduce的Job調(diào)度策略中存在信任機(jī)制，在一段時間內(nèi)它一直返回正確的結(jié)果，直到系統(tǒng)放松對其的監(jiān)察，甚至完全信任攻擊者，會無保留的接受攻擊者提供的結(jié)果。此時，攻擊者才會返回錯誤的結(jié)果。本文策略的安全目標(biāo)包括：① 避免那些合法但互相沖突關(guān)系租戶之間因為同平臺運(yùn)行而帶來的潛在信息泄漏或篡改安全威脅（即第1節(jié)的第1類問題）；② 要在一定程度上避免或減少上述描述的幾類安全威脅，包括惡意攻擊者利用前面第1節(jié)提到的第2類和第3類安全問題形成非合謀方式下的魯莽攻擊、普通攻擊和機(jī)智攻擊。在給出MapReduce安全冗余調(diào)度策略之前，下面先給出該策略的一些基本假設(shè)。

1)調(diào)度策略仍然遵循本地化優(yōu)先原則，即優(yōu)先選擇本地保存了任務(wù)輸入數(shù)據(jù)塊副本的計算節(jié)點(diǎn)，否則按由近至遠(yuǎn)的方式選擇距離任務(wù)輸入數(shù)據(jù)副本位置最近的計算節(jié)點(diǎn)，以優(yōu)化任務(wù)的執(zhí)行性能。

2)系統(tǒng)可分配的計算資源總是足夠的，即系統(tǒng)總是可以在原有調(diào)度策略基礎(chǔ)之上，采用上述動態(tài)域劃分模型，找到滿足作業(yè)調(diào)度域、可信域劃分屬性且足夠的計算節(jié)點(diǎn)。這樣，在租戶請求作業(yè)調(diào)度過程中，系統(tǒng)不會因找不到滿足屬性的節(jié)點(diǎn)而導(dǎo)致冗余調(diào)度失敗。這種假設(shè)在具有大規(guī)模節(jié)點(diǎn)云環(huán)境下是可行的。

3)系統(tǒng)的網(wǎng)絡(luò)傳輸是安全的。盡管網(wǎng)絡(luò)往往是分布式系統(tǒng)最薄弱的一環(huán)，入侵者多從網(wǎng)絡(luò)入手，但此處的網(wǎng)絡(luò)多特指系統(tǒng)內(nèi)部節(jié)點(diǎn)之間進(jìn)行數(shù)據(jù)傳輸?shù)木W(wǎng)絡(luò)。網(wǎng)絡(luò)是數(shù)據(jù)中心基礎(chǔ)設(shè)施的重要部分，對于網(wǎng)絡(luò)安全領(lǐng)域已有很多的研究，系統(tǒng)中可以通過多種手段保證網(wǎng)絡(luò)安全（如加密），網(wǎng)絡(luò)傳輸?shù)陌踩捎捎嬎憧蚣苤碌幕A(chǔ)架構(gòu)實現(xiàn)，并不屬于本文討論的范疇，因此做此假設(shè)是合理的。

4)系統(tǒng)的中央節(jié)點(diǎn)是可信的。中央節(jié)點(diǎn)是系統(tǒng)的核心，負(fù)責(zé)整個系統(tǒng)任務(wù)的調(diào)度和分發(fā)，如果中央節(jié)點(diǎn)不可信，則基于中央節(jié)點(diǎn)的功能構(gòu)建的整個系統(tǒng)就不可信，因此中央節(jié)點(diǎn)可信是必要條件。

4.2 基于動態(tài)域劃分的安全冗余調(diào)度策略

為了實現(xiàn)上述安全目標(biāo)，將基于上述動態(tài)域劃分模型，并結(jié)合冗余調(diào)度方式，給出一種安全冗余調(diào)度策略，該策略的主要設(shè)計思想包括如下幾方面。

首先，第3節(jié)的動態(tài)域劃分模型說明：每個域劃分策略實際上表示的是租戶對其作業(yè)希望/不希望執(zhí)行環(huán)境的基本安全需求（包括不期望的沖突關(guān)系以及期望的信任度、安全標(biāo)簽等信息，其中后者包括期望的安全級別和位置范圍等），所以調(diào)度策略基于動態(tài)域劃分模型，就可以將每一個待調(diào)度計算節(jié)點(diǎn)先進(jìn)行沖突域、可信域和調(diào)度域的劃分，即找出符合租戶作業(yè)的基本安全需求的3類節(jié)點(diǎn)。

其次，為了防止2個沖突關(guān)系租戶的計算任務(wù)同時分配給同一個計算節(jié)點(diǎn)可能帶來的安全風(fēng)險，如導(dǎo)致一方信息泄漏給另一方或被對方篡改，該策略將不允許一個任務(wù)分配給其沖突域節(jié)點(diǎn)。

再者，為了防止動態(tài)域劃的調(diào)度域節(jié)點(diǎn)或者可信域節(jié)點(diǎn)仍然可能是惡意租戶控制的節(jié)點(diǎn)或者存在惡意租戶任務(wù)運(yùn)行的節(jié)點(diǎn)（假設(shè)這 2個計算節(jié)點(diǎn)同時是惡意節(jié)點(diǎn)且會同謀的概率很小），本文的策略將結(jié)合冗余方式，即對每個待調(diào)度計算任務(wù)產(chǎn)生 2個副本，分別分配給任務(wù)對應(yīng)的這2個域劃分的計算節(jié)點(diǎn)。為了能夠驗證這 2個計算環(huán)境中是否有一方是惡意的，將采用2種方法來一起驗證。

1)執(zhí)行環(huán)境的完整性驗證

首先，這里的執(zhí)行環(huán)境是指計算節(jié)點(diǎn)上為任務(wù)的運(yùn)行而提供的軟件系統(tǒng)及其配置，如Hadoop中JVM目錄的核心JAR包，租戶提交Task的JAR包，HDFS分布式緩存文件等。再者，對于執(zhí)行環(huán)境的驗證方法可以有2種：一種采用通用的軟件計算方式，即通過軟件實現(xiàn)的安全散列(MD5或SHA-1等)函數(shù)來計算和保存二者執(zhí)行環(huán)境的校驗值，并進(jìn)行簡單的一致性對比驗證；另一種采用安全性更強(qiáng)的硬件(如可信平臺模塊TPM或可信加密模塊TCM)支持方式，包括通過硬件來計算和保存二者執(zhí)行環(huán)境的散列校驗值，并通過硬件支持的遠(yuǎn)程證實[27]機(jī)制來進(jìn)行一致性對比驗證。這2種方法都使用了散列函數(shù)，在可信域或者調(diào)度域節(jié)點(diǎn)的執(zhí)行環(huán)境被惡意控制和篡改的情況下（假設(shè)散列值已經(jīng)通過軟件或硬件方式做了加密存儲和傳輸，不會被竊取或截獲），它要試圖偽造一個具有相同散列值的計算環(huán)境是困難的。

2)隨機(jī)選取小部分(1/a)原輸入進(jìn)行冗余計算和結(jié)果正確性驗證

由于執(zhí)行環(huán)境的完整性驗證只能保證計算節(jié)點(diǎn)的靜態(tài)運(yùn)行環(huán)境是正確的，但并不能保證任務(wù)運(yùn)行過程中出現(xiàn)的惡意行為（如惡意跳轉(zhuǎn)等）。因此對輸出結(jié)果進(jìn)行驗證將可以在一定程度上防止此類威脅。本策略將僅計算所分配任務(wù)原輸入（如 Hadoop每個任務(wù)的默認(rèn)輸入為一個數(shù)據(jù)塊64 MB）的1/a來完成驗證，如為Task設(shè)置實際讀取數(shù)據(jù)在原輸入中的位置(如偏移量)和比例(如1/a)。這樣做有兩點(diǎn)好處：一是可以減少完全冗余計算帶來的計算資源開銷大的問題，因為完全冗余會使系統(tǒng)中計算資源的利用率下降50%，而針對1/a原輸入的冗余計算，利用率僅下降1/a(如a=20時，僅為5%)，換句話說，若1/a足夠小，則策略帶來資源利用率的影響足夠??；二是可以保證結(jié)果正確性驗證的有效性，即系統(tǒng)能以足夠大概率驗證出計算結(jié)果是否被惡意篡改。例如，在大規(guī)模集群環(huán)境中，每一個作業(yè) Job通常會劃分成大量的Task并行處理。假設(shè)Job被劃分為n(如 n=100)個 Task，每個 Task只計算 1/a(如a=20)原輸入，則Job的輸出結(jié)果被篡改但不被發(fā)現(xiàn)的概率為(1?1/a)n≈0.6%，即只要n足夠大，則策略驗證出整個Job輸出結(jié)果被篡改的概率也足夠大。理論上，在指定的集群規(guī)模大小為N（即最大可劃分任務(wù)數(shù)）、資源利用率損耗要求不低于 U，和結(jié)果正確性驗證失效率要求不高于Q的云環(huán)境中，a的取值應(yīng)該不小于1/U和不大于

此外，由于上述 2種驗證結(jié)果能夠體現(xiàn)調(diào)度域節(jié)點(diǎn)和可信域節(jié)點(diǎn)的可信性，因此本策略將要求在作業(yè)完成時對所有任務(wù)涉及的計算節(jié)點(diǎn)的信任度進(jìn)行計算和更新。不選擇每個任務(wù)完成時計算，主要是為了減小頻繁更新給系統(tǒng)資源帶來過大的開銷。

經(jīng)以上分析，下面具體給出本文安全冗余調(diào)度策略所包括的安全規(guī)則（如圖4所示）。

安全規(guī)則1 所有待調(diào)度計算節(jié)點(diǎn)都要求劃分為與待調(diào)度計算任務(wù)關(guān)聯(lián)的沖突域、可信域或調(diào)度域。

安全規(guī)則2 一個租戶作業(yè)Job的所有Task不允許被調(diào)度到屬于其沖突域劃分的計算節(jié)點(diǎn)X中運(yùn)行。

安全規(guī)則3 一個租戶作業(yè)Job的所有Task都要求執(zhí)行安全冗余調(diào)度(如圖4)，即Job的每個Task都要求產(chǎn)生2個副本(例如，圖4 Task A的副本1和副本2)，分別調(diào)度到Job關(guān)聯(lián)的可信域節(jié)點(diǎn)Y和調(diào)度域節(jié)點(diǎn)Z中分別執(zhí)行。

安全規(guī)則3.1 Task的第一個副本(簡稱副本1)將被優(yōu)先分配到Job的可信域節(jié)點(diǎn)Y中，并有如下要求。

1)對副本1在節(jié)點(diǎn)Y中的當(dāng)前執(zhí)行環(huán)境計算Hash校驗值Et，并提交中央節(jié)點(diǎn)。

2)節(jié)點(diǎn)Y中的副本1僅需對隨機(jī)選取的小部分(如1/a)原輸入執(zhí)行冗余計算，對產(chǎn)生的輸出結(jié)果計算Hash校驗值Pt，并提交中央節(jié)點(diǎn)。

安全規(guī)則3.2 Task的第2個副本(簡稱副本2)將被分配到Job的調(diào)度域節(jié)點(diǎn)Z中，并有如下要求。

1)在副本 2執(zhí)行之前，必須先對它在節(jié)點(diǎn) Z中的執(zhí)行環(huán)境計算散列校驗值 Es，并提交中央節(jié)點(diǎn)，由中央節(jié)點(diǎn)完成 Es與可信域節(jié)點(diǎn) Y提交的 Et對比驗證。

2)若Es和Et相等，即判定節(jié)點(diǎn)Z可以滿足執(zhí)行環(huán)境的完整性要求（即執(zhí)行環(huán)境沒有被惡意篡改），則允許Z執(zhí)行副本2。一旦它對同樣1/a源輸入數(shù)據(jù)產(chǎn)生了輸出結(jié)果，則要求它計算該結(jié)果的散列校驗值 Os，并提交中央節(jié)點(diǎn)，由中央節(jié)點(diǎn)完成Os與Ot對比驗證。

3)若Os和Ot相等，即可判定節(jié)點(diǎn)Z可以滿足結(jié)果正確性要求（即沒有惡意租戶的篡改或偽造），則判定Task已經(jīng)成功分配給計算節(jié)點(diǎn)Z，否則調(diào)度失敗。此時可信域節(jié)點(diǎn)Y的副本1完成，Y將供其他任務(wù)調(diào)度。

安全規(guī)則4 一個租戶作業(yè)Job的所有Task都已經(jīng)成功調(diào)度時，對成功/失敗分配了其中任何一個任務(wù)副本，而且屬于 Job調(diào)度域劃分的計算節(jié)點(diǎn),更新這些節(jié)點(diǎn)針對Job所屬租戶U的信任度。

圖4 MapReduce安全冗余調(diào)度策略示意

5 實驗和分析

5.1 基于Hadoop MapReduce原型實現(xiàn)

原型系統(tǒng)是基于Hadoop 0.20.2修改實現(xiàn)的，主要是在Hadoop MapReduce的JobTracker調(diào)度器和TaskTracker中增加了相關(guān)的安全機(jī)制，如圖5所示。主要包括安全標(biāo)簽管理、節(jié)點(diǎn)信任度管理、沖突關(guān)系管理、域劃分策略管理、散列值校驗和安全冗余調(diào)度等 6個新的安全模塊。1）安全標(biāo)簽管理模塊主要負(fù)責(zé)安全級別和位置屬性的管理和維護(hù)，以及對計算節(jié)點(diǎn)進(jìn)行安全標(biāo)簽的標(biāo)記管理，并為域劃分策略管理模塊提供安全標(biāo)簽之間包含關(guān)系的計算功能等。2）節(jié)點(diǎn)信任度管理模塊主要負(fù)責(zé)收集、驗證和記錄散列值校驗?zāi)K提交的每個計算節(jié)點(diǎn)的2個可信屬性情況，在一個作業(yè)完成時計算和更新對應(yīng)的信任度。3）沖突關(guān)系管理模塊主要負(fù)責(zé)系統(tǒng)中租戶之間沖突關(guān)系集合的管理和維護(hù)，并提供給域劃分策略管理模塊使用。4）域劃分策略管理模塊主要負(fù)責(zé)對不同租戶作業(yè)的域劃分策略表達(dá)式進(jìn)行管理和維護(hù)，以及根據(jù)安全標(biāo)簽管理、節(jié)點(diǎn)信任度管理和沖突關(guān)系管理等模塊提供的待分配 TaskTracker當(dāng)前狀態(tài)信息，計算出域劃分策略表達(dá)式的值，并根據(jù)沖突域、可信域或調(diào)度域優(yōu)先順序決定TaskTracker的域劃分。5）散列值校驗?zāi)K主要負(fù)責(zé)對可信域節(jié)點(diǎn)和調(diào)度域節(jié)點(diǎn)的執(zhí)行環(huán)境、部分結(jié)果的散列值進(jìn)行計算和通過心跳機(jī)制提交給中央節(jié)點(diǎn)。6）安全冗余調(diào)度模塊則主要是在租戶提交作業(yè)Job的調(diào)度請求時，在現(xiàn)有調(diào)度策略基礎(chǔ)之上，結(jié)合域劃分判定策略管理模塊的決策結(jié)果，從符合條件的調(diào)度域和可信域(但不選擇沖突域)劃分的 TaskTracker中各選擇一個，將Job的任務(wù)Task生成2個副本分配給他們，并通過節(jié)點(diǎn)信任度管理模塊的2個可信性屬性校驗結(jié)果，決定該任務(wù)是否重新調(diào)度。

5.2 性能分析

Hadoop MapReduce實驗集群包括局域網(wǎng)中4個節(jié)點(diǎn)，其中在一臺華碩A8JR(1.5 GB內(nèi)存，1.8 GHz CPU)機(jī)器上同時部署了 JobTracker(JT)節(jié)點(diǎn)和JobClient(JC)節(jié)點(diǎn)，它們是通過VMWare Workstation 7.1安裝了Ubuntu 8.1(512 MB)的2個虛擬機(jī)；在3臺聯(lián)想M7100(3 GB內(nèi)存，3.5GHz CPU)機(jī)器上分別部署了3個節(jié)點(diǎn)：TaskTracker1 (TT1)、TaskTracker2(TT2)、TaskTracker3 (TT3)，它們都是通過 VMWare Workstation 7.1安裝了Ubuntu 8.1(1GB)的一個虛擬機(jī)。

圖5 Hadoop MapReduce安全冗余調(diào)度策略原型實現(xiàn)系統(tǒng)結(jié)構(gòu)

5.2.1 策略對Map/Reduce任務(wù)調(diào)度性能的影響

在實驗集群環(huán)境中，對計算節(jié)點(diǎn)進(jìn)行動態(tài)的域劃分，加上計算任務(wù)非本地直接讀取輸入的情況增加，都會帶來時間開銷；且每個作業(yè)的Map/Reduce任務(wù)都要求執(zhí)行冗余計算，也會帶來時間開銷。如何測試這些開銷呢？首先，測試Map/Reduce階段的時間開銷，以評估作業(yè)調(diào)度策略帶來的時間開銷，原因是Hadoop采取調(diào)度和處理并行的方式[5]。再者，以輸入數(shù)據(jù)大小為基準(zhǔn)來測試策略修改前后Map/Reduce階段時間開銷，原因是Hadoop對作業(yè)劃分任務(wù)數(shù)與輸入數(shù)據(jù)大小有關(guān)，如一個Map任務(wù)輸入通常對應(yīng)一個數(shù)據(jù)塊(默認(rèn)64 MB），在輸入數(shù)據(jù)為100個數(shù)據(jù)塊時，要調(diào)度的Map任務(wù)為100個。

圖6給出了實驗數(shù)據(jù)，其中：①時間開銷測試數(shù)據(jù)是通過在系統(tǒng)中增加審計日志信息計算獲得，并沒有專門實現(xiàn)一種自動化的性能分析工具；②MapReduce的日志時間可以精確到毫秒，但是由于實驗集群數(shù)量有限，相對于工業(yè)環(huán)境使用的大規(guī)模集群，其總體運(yùn)行性能更慢，所以測試得到的相關(guān)時間開銷僅精確到秒。這些數(shù)據(jù)表明：策略修改后(a選取20)，Map任務(wù)階段調(diào)度時間開銷平均增加了 20%～30%，如在策略修改前，待處理輸入數(shù)據(jù)為900個數(shù)據(jù)塊(每塊64 MB)時，Map任務(wù)階段時間開銷為320 s，在策略修改后，時間開銷為415 s，增加約29%的開銷；策略修改后，Reduce任務(wù)階段時間開銷增加比較小，基本在10%以下，如在策略修改前，待處理輸入數(shù)據(jù)為100個數(shù)據(jù)塊時，Reduce任務(wù)階段的時間開銷為14 s，在策略修改后，時間開銷為15 s，僅增加7%的開銷。這是因為策略只要求Reduce Task對中間結(jié)果執(zhí)行散列值校驗，而散列值的計算本身不會帶來過大的開銷。但是隨著輸入數(shù)據(jù)的增加，Map階段產(chǎn)生的中間結(jié)果增多，Reduce開銷也略有增加。

圖6 策略修改前后的Map/Reduce任務(wù)調(diào)度性能

可見，安全冗余調(diào)度策略會給MapReduce調(diào)度器帶來一些時間開銷。但是，如果可以選擇合適的MapReduce集群規(guī)模，使可調(diào)度計算資源足夠大，且每個作業(yè)的調(diào)度域節(jié)點(diǎn)和可信域節(jié)點(diǎn)總是能夠獲得情況下，可以適當(dāng)減少由于計算資源不足而引起的動態(tài)域劃分重復(fù)計算帶來的開銷。

5.2.2 策略對系統(tǒng)資源利用率的影響

現(xiàn)有Hadoop MapReduce將整個集群中的計算節(jié)點(diǎn)都看作是可以被調(diào)度的資源，但是在系統(tǒng)中采用了本文策略之后，整個集群中的計算節(jié)點(diǎn)都將動態(tài)劃分為沖突域、調(diào)度域和可信域，而且只有調(diào)度域和可信域的計算資源對用戶來說是可用的，這就可能造成可利用的計算資源減少的缺點(diǎn)。根據(jù) 4.2節(jié)給出的a值選擇方法，圖7給出了策略修改前，策略修改后可保證資源利用率損耗不高于5%的2個a值（20和50）條件下的CPU資源占用率測試數(shù)據(jù)。測試方法是，按順序提交10個作業(yè)，在第一個作業(yè)提交之后直到所有作業(yè)全部完成的這段時間內(nèi)，每隔40 s測試一次各個節(jié)點(diǎn)的CPU資源占用率，并計算其平均值(縱坐標(biāo))。實驗數(shù)據(jù)表明：策略修改前，CPU資源占用率為23.5%，策略修改后，其占用率上升。例如：a為20時，CPU資源占用率為27.9%；a為50時，其占用率為26.5%，但是可以發(fā)現(xiàn)，隨著 a值的增長，整個系統(tǒng)中資源占用率的上升比在減小，即策略帶來的影響在減小。

此外，沖突域劃分對資源利用率也有影響。如果沖突集合C足夠小，即存在沖突關(guān)系的租戶數(shù)量與系統(tǒng)總租戶數(shù)量的比率足夠小，則對系統(tǒng)中可用資源的影響將足夠小。但是，如果出現(xiàn)沖突租戶同時提交作業(yè)的概率很高的情況，則會導(dǎo)致系統(tǒng)可用的計算資源出現(xiàn)較明顯減少的現(xiàn)象。

圖7 策略修改前后的CPU資源占用率

5.3 安全性分析

在實驗集群環(huán)境中，模擬建立了3個租戶(Alice銀行、Bob銀行、Clark公司)，且設(shè)置(Alice銀行，Bob銀行)是沖突關(guān)系。如表2所示，為待調(diào)度節(jié)點(diǎn)TT1～TT3的當(dāng)前狀態(tài)，包括其當(dāng)前運(yùn)行的各租戶的任務(wù)數(shù)、信任度、標(biāo)簽等，Alice待提交作業(yè)A的域劃分策略滿足情況。實驗的結(jié)果是：作業(yè)A的任務(wù)被分配到了其調(diào)度域節(jié)點(diǎn) TT2和可信域節(jié)點(diǎn)TT3，但未被分配給其沖突域節(jié)點(diǎn) TT1。這個結(jié)果與3.3節(jié)的動態(tài)域劃分規(guī)則和4.2節(jié)的調(diào)度策略是一致的。

表2 系統(tǒng)中各待調(diào)度節(jié)點(diǎn)的當(dāng)前狀態(tài)和待調(diào)度作業(yè)A的域劃分策略滿足情況

可見，本文策略可以在一定程度上避免第1節(jié)提及的3類安全問題，具體分析如下。

1)本文策略不允許將計算任務(wù)分配給其沖突域節(jié)點(diǎn)，使2個沖突關(guān)系租戶的計算任務(wù)不會同時運(yùn)行在同一個計算節(jié)點(diǎn)上(即防止出現(xiàn)第 1節(jié)提到的第1類安全問題)，從而保證云環(huán)境中2個沖突關(guān)系租戶計算任務(wù)之間的強(qiáng)安全隔離。

2)本文策略在對計算任務(wù)進(jìn)行調(diào)度時，是將任務(wù)的 2個副本同時分配給可信域節(jié)點(diǎn)和調(diào)度域節(jié)點(diǎn)，并通過軟件/硬件支持方式對二者執(zhí)行環(huán)境散列值進(jìn)行對比驗證。這樣做可以防止將任務(wù)分配給可能已經(jīng)被惡意控制的可信域/調(diào)度域節(jié)點(diǎn)(即防止出現(xiàn)前面第1節(jié)提到的第2類安全問題)，從而保證云環(huán)境中合法租戶計算任務(wù)與被惡意租戶控制的節(jié)點(diǎn)上的任務(wù)之間安全隔離。

3)本文策略在對計算任務(wù)進(jìn)行調(diào)度時，要求可信域節(jié)點(diǎn)和調(diào)度域節(jié)點(diǎn)僅對隨機(jī)選取的小部分(1/a)輸入的計算結(jié)果的散列校驗值進(jìn)行對比驗證，這樣做可以防止 Task分配到一個可能運(yùn)行了可植入惡意代碼的任務(wù)可信域/調(diào)度域節(jié)點(diǎn)(即防止出現(xiàn)前面第1節(jié)提到的第3類安全問題)，從而保證云環(huán)境中的合法租戶計算任務(wù)與惡意的租戶任務(wù)之間的安全隔離。

再者，本文策略可以在一定程度上避免第2類和第3類問題導(dǎo)致的非合謀方式下的攻擊手段，具體分析如下。

① 對于魯莽攻擊手段，由于攻擊者控制了計算節(jié)點(diǎn)，并總是(即概率100%)返回錯誤的結(jié)果，而本文策略采取對每個任務(wù)都冗余調(diào)度的方式進(jìn)行結(jié)果一致性驗證，能夠以極高的概率防范這種攻擊手段。

② 對于普通攻擊手段，由于攻擊者僅以一定概率（小于 100%）返回錯誤的結(jié)果，但它所控制節(jié)點(diǎn)的執(zhí)行環(huán)境通常會不同，本文策略對任務(wù)執(zhí)行環(huán)境的完整性驗證將使檢測概率較高。但是，如果攻擊者對任務(wù)的執(zhí)行環(huán)境不做改變，并且僅以 x%概率返回錯誤的結(jié)果，則本文策略由于只對1/a輸入進(jìn)行結(jié)果驗證，無法檢測出單個任務(wù)錯誤的概率會達(dá)到 1?x/a%（如 x=20，a=20時為99%），但對于大規(guī)模集群環(huán)境下整個作業(yè)的大量（n=100）任務(wù)來說，無法檢測的概率僅為(1?x/a%)(1?1/a)n?1（約0.617%，只比不正常情況下(1?1/a)n高出約0.025%）。即使攻擊者控制了一個作業(yè)的 50%任務(wù)節(jié)點(diǎn)，無法檢測的概率也只有(1?1/a)n/2(1?x/a%)n/2(約4.7%)。而且，一旦它返回錯誤結(jié)果被檢測到，策略就會降低其信任度，使得其攻擊目標(biāo)租戶的下一個作業(yè)無法分配到這個被控制的計算節(jié)點(diǎn)。

③ 對于機(jī)智攻擊手段，即它在一段時間內(nèi)一直返回正確的結(jié)果，甚至通過本文策略中的信任機(jī)制獲取了大多租戶對它較高的信任度(如將其劃分為可信域），之后才開始返回錯誤結(jié)果。但策略并不假設(shè)可信域是完全可信的，總會在調(diào)度過程中先驗證二者計算結(jié)果是否一致(除非二者合謀)，一旦它認(rèn)為將自己的信任度提高而開始發(fā)錯誤結(jié)果，就會被檢測到，概率取決于它采取魯莽/普通攻擊手段。

6 結(jié)束語

本文針對目前 MapReduce調(diào)度策略無法解決云計算環(huán)境中多租戶計算任務(wù)的安全隔離問題，提出一種基于動態(tài)域劃分的安全冗余調(diào)度策略。首先，它通過計算節(jié)點(diǎn)動態(tài)標(biāo)記的信任度、安全標(biāo)簽等信息，以及給出與租戶作業(yè)關(guān)聯(lián)的3個域劃分策略，對每一個作業(yè)的計算節(jié)點(diǎn)進(jìn)行動態(tài)的沖突域、調(diào)度域和可信域的劃分，保證沖突租戶的計算任務(wù)安全隔離，即它們不允許被同時調(diào)度到同一個計算節(jié)點(diǎn)。其次，它通過部分冗余計算和驗證，即基于可信域節(jié)點(diǎn)和調(diào)度域節(jié)點(diǎn)上相同任務(wù)副本執(zhí)行環(huán)境的完整性及部分(1/a)輸入數(shù)據(jù)的計算結(jié)果的一致性驗證，使合法租戶的計算任務(wù)在調(diào)度決策時與其不期望的惡意租戶的計算任務(wù)和惡意租戶控制的計算節(jié)點(diǎn)安全隔離。本文策略也適用于 Master/Slave分布式處理架構(gòu)的其他云計算系統(tǒng)。在未來工作中，將研究如何防止惡意節(jié)點(diǎn)按較小的概率來提交錯誤結(jié)果，甚至2個惡意節(jié)點(diǎn)合謀欺騙，導(dǎo)致驗證結(jié)果誤報等問題，并參考策略領(lǐng)域相關(guān)成果[28]研究如何有效地表達(dá)和運(yùn)行策略。

[1]DEAN J,GHEMAWAT S. Mapreduce: simplified data processing on large clusters[A]. Proceedings of USENIX 6th Conference on Symposium on Operating Systems Design and Implementation (OSDI’04)[C]. Berkeley,CA,USA,USA: USENIX Press,2004.137-150.

[2]Hadoop tutorial[EB/OL]. http://public.yahoo.com/gogate/hadooptutorial/start-tutorial.html.

[3]Amazon elastic mapreduce[EB/OL]. http://docs.amazonwebservices.com/Elastic-MapReduce/latest/DeveloperGuide/index. html.

[4]MATHER T,KUMARASWAMY S,LATIF S. Cloud Security and Privacy: an Enterprise Perspective on Risks and Compliance[M]. USA,O'Reilly Media,2009.

[5]Capacity scheduler[EB/OL]. http://hadoop.apache.org/common/docs/r0.20.0/capacity_scheduler.pdf.

[6]Fair scheduler[EB/OL]. http://hadoop.apache.org/common/docs/r0.20.2/fair_scheduler.html.

[7]ZAHARIA M,BORTHAKUR D,SARMA J S,et al. Job Scheduling for Multi-user Mapreduce Clusters[R]. EECS Department,University of California,Berkeley,USA,2009.

[8]TIAN C,ZHOU H,HE Y,et al. A dynamic mapreduce scheduler for heterogeneous workloads[A]. Proceedings of 20098th International Conference on Grid and Cooperative Computing(GCC’09)[C].Lanzhou,China,2009.218-224.

[9]POLO D,CARRERA Y,BECERRA J,et al. Performance-driven Task co-scheduling for mapreduce environments[A]. Proceedings of 2010 IEEE/IFIP Network Operations and Management Symposium(NOMS)[C]. Osaka,Japan,2010.373-380.

[10]KC K,ANYANWU K. Scheduling hadoop Jobs to meet deadlines[A].Proceedings of 2nd IEEE International Conference on Cloud Computing Technology and Science(CloudCom)[C]. Indianapolis,Indiana,USA,USA: IEEE CS Press,2010.388-392.

[11]LI X,JIA Z,JU L,et al. Energy efficient scheduling and optimization for parallel Tasks on homogeneous clusters[J]. Chinese Journal of Computers,2012:35(3):591-602.

[12]WEI W,DU J,YU T,et al. Securemr: a service integrity assurance framework for mapreduce[A]. Proceedings of the 2009 annual computer security applications conference(ACSAC’09)[C]. Washington,DC,USA,2010.73-82.

[13]ROY I,SETTY S T V,KILZER A,et al. Airavat: security and privacy for mapreduce[A]. Proceedings of the 7th conference on networked systems design and implementation(NDSI’10)[C]. Berkeley,CA,USA,USA: USENIX Press,2010.20-20.

[14]SONG S,KWOK Y,HWANG K. Security-driven heuristics and a fast genetic algorithm for trusted grid Job scheduling[A]. Proceedings of 19th IEEE international parallel and distributed processing symposium(IPDPS'05)[C]. Denver,Colorado USA,USA: IEEE CS Press,2005.65-74.

[15]RUAN A,MARTIN A. TMR: towards a trusted mapreduce infrastructure[A]. Proceedings of the 2012 IEEE 8th World Congress on Services[C]. Hawaii,USA,2012.141-148.

[16]HUANG C,ZHU S,WU D. Towards trusted services: result verification schemes for MapReduce[A]. Proceedings of 12th IEEE/ACM International Symposium on Cluster,Cloud and Grid Computing (CCGrid)[C]. 2012.41-48.

[17]KHAN S M,HAMLEN K W. Computation certification as a service in the cloud[A]. Proceedings of 13th IEEE/ACM International Symposium on Cluster,Cloud and Grid Computing (CCGrid)[C].2013. 434-441.

[18]BENDAHMANE A,ESSAAIDI M,EL MOUSSAOUI A,et al. Result verification mechanism for mapreduce computation integrity in cloud computing[A]. Proceedings of International Conference on Complex Systems (ICCS)[C]. Agadir,MAROCCO,IEEE CS,2012.1-6.

[19]BREWER D,NASH M. The chinese wall security policy[A].Proceedings of the Symposium on Security and Privacy[C]. Los Alamitos,Calif,1989.215-228.

[20]WU R,AHN G J,HU H,et al. Information flow control in cloud computing[A]. Proceedings of IEEE 6th International Conference on Collaborative Computing: Networking,Applications and Worksharing(CollaborateCom)[C]. Chicago,Illinois,USA,2012.1-7.

[21]SHEN Q,YANG X,YU X,et al. Towards data isolation and collaboration in storage cloud[A]. Proceedings of the 2011 IEEE asia-pacific services computing conference(APSCC2011)[C]. DJeju,Korea,2011.139-146.

[22]KESARWANI A,GUPTA C,TRIPATHI M M,et al. Implementation of Chinese wall model in cloud computing for enhanced security[A].Proceedings of IEEE International Conference on Emerging Trends in Networks and Computer Communications(ETNCC)[C]. 2011.411-413.

[23]CHEN Y,HUANG H,HUANG P,et al. A practical Chinese wall security model in cloud computing[A]. Proceedings of 201113th Asia-pacific Network Operations and Management Symposium(APNOMS)[C].2011.1-4.

[24]ALMENAREZ F,MARIN A,DIAZ D,et al. Developing a model for trust management in pervasive devices[A]. Proceedings of the 3rd IEEE Int’l Workshop on Pervasive Computing and Communication Security(PerSec 2006)[C]. Washington,USA,2006.267-272.

[25]LI X,GUI X. Research on dynamic trust model for large scale distributed environment[J]. Journal of softwar,2007,18(6):15510-1521

[26]ANDERSON R. Security Engineering: A Guide to Building Dependable Distributed System[M]. Indiana,USA: Wiley Publishing Inc.,2008.

[27]SAILER R,ZHANG X,JAEGER T,et al. Design and implementation of a TCG-based integrity measurement architecture[A]. Proceedings of the 13th USENIX Security Symposium[C]. San Diego,CA,USA,2004.223-238.

[28]HAN W,LEI C. A survey on policy languages in network and security management[J]. Computer Networks(COMNET),2012,56(1):477-489