基于動態域劃分的MapReduce安全冗余調度策略

沈晴霓，卿斯漢,3，吳中海，張力哲，楊雅輝

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

1 引言

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

圖1 MapReduce并行計算模型

但是，使用 MapReduce的云服務系統是開放式、多租戶的基礎架構（租戶是指租賃云服務系統的計算/存儲服務的實體，一個租戶是一個組織/機構/個體，如銀行、企業、高校或個人），除了傳統的通信安全威脅，如數據竊聽、重放攻擊以及拒絕服務攻擊等，還存在自身安全的復雜性和特殊性[2～4]，特別地，在MapReduce中央節點對大規模不同租戶的作業進行調度的過程中，它可能面臨如下新的安全問題。

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

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

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

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

本文的創新之處在于以下3點。

1)提出一種動態域劃分模型。通過引入沖突關系、信任度和安全標簽等概念，以及為不同租戶作業定義3種域劃分策略，將每個待調度節點劃分為與租戶作業關聯的沖突域、調度域或可信域。

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

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

2 相關工作

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

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

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

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

3 動態域劃分模型

本節將提出一種動態域劃分模型。通過引入沖突關系、信任度和安全標簽等概念，以及為不同租戶作業定義的 3種域劃分策略，將每個待調度節點劃分為與租戶作業關聯的沖突域、調度域或可信域。

3.1 基本概念

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

為此，系統需要統一管理和維護一個沖突關系集合C(如表1所示)，并且在每個任務調度過程中檢查待調度計算節點上當前運行任務所屬租戶，檢查他們是否與待調度任務所屬的租戶之間存在沖突關系。

表1 模型元素和域劃分策略邏輯表達式的構造

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

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

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

圖2 位置屬性之間語義層次化樹型關系

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

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

因此，系統將通過可為計算節點標記的安全級別和位置集合等屬性，定義一個安全標簽集合L（如表1所示），用于標記每個計算節點的安全屬性。

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

3.2 模型元素及其相互之間的約束關系

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

圖3 動態域劃分模型元素及其關系

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

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

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

4)每一個任務可以分配給若干個計算節點，每一個計算節點可以同時運行多個任務。

5)每一個計算節點被賦予一個安全標簽，每一個安全標簽可以賦予若干個計算節點。

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

7)針對每一個租戶作業，一個計算節點能且只能劃分為一個域，同一個域劃分的計算節點可以有若干個。

8)針對每一個租戶作業，每一個域劃分策略關聯一個特定域，每一個域有一個對應的域劃分策略。

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

10)每一個租戶能為其特定作業申請若干個計算節點，每一個計算節點能承擔若干個租戶的特定作業。

3.3 沖突域、調度域和可信域的劃分策略和規則

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

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

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

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

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

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

可信域劃分規則 節點x被劃分為任務t的可信域節點，即nCurDom(x,t)=DT，當且僅當節點x當前安全屬性nBelief(u,x),rLable(x)能夠使租戶u的作業j對應的可信域劃分策略P(u,j)T的值為真,即P(u,j)T=true，且待調度任務t沒有分配給j對應的任何可信域節點，即tNode(t,DT)=φ。

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

4 MapReduce安全冗余調度策略

4.1 威脅模型和基本假設

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

1)調度策略仍然遵循本地化優先原則，即優先選擇本地保存了任務輸入數據塊副本的計算節點，否則按由近至遠的方式選擇距離任務輸入數據副本位置最近的計算節點，以優化任務的執行性能。

2)系統可分配的計算資源總是足夠的，即系統總是可以在原有調度策略基礎之上，采用上述動態域劃分模型，找到滿足作業調度域、可信域劃分屬性且足夠的計算節點。這樣，在租戶請求作業調度過程中，系統不會因找不到滿足屬性的節點而導致冗余調度失敗。這種假設在具有大規模節點云環境下是可行的。

3)系統的網絡傳輸是安全的。盡管網絡往往是分布式系統最薄弱的一環，入侵者多從網絡入手，但此處的網絡多特指系統內部節點之間進行數據傳輸的網絡。網絡是數據中心基礎設施的重要部分，對于網絡安全領域已有很多的研究，系統中可以通過多種手段保證網絡安全（如加密），網絡傳輸的安全可由計算框架之下的基礎架構實現，并不屬于本文討論的范疇，因此做此假設是合理的。

4)系統的中央節點是可信的。中央節點是系統的核心，負責整個系統任務的調度和分發，如果中央節點不可信，則基于中央節點的功能構建的整個系統就不可信，因此中央節點可信是必要條件。

4.2 基于動態域劃分的安全冗余調度策略

為了實現上述安全目標，將基于上述動態域劃分模型，并結合冗余調度方式，給出一種安全冗余調度策略，該策略的主要設計思想包括如下幾方面。

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

其次，為了防止2個沖突關系租戶的計算任務同時分配給同一個計算節點可能帶來的安全風險，如導致一方信息泄漏給另一方或被對方篡改，該策略將不允許一個任務分配給其沖突域節點。

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

1)執行環境的完整性驗證

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

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

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

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

經以上分析，下面具體給出本文安全冗余調度策略所包括的安全規則（如圖4所示）。

安全規則1 所有待調度計算節點都要求劃分為與待調度計算任務關聯的沖突域、可信域或調度域。

安全規則2 一個租戶作業Job的所有Task不允許被調度到屬于其沖突域劃分的計算節點X中運行。

安全規則3 一個租戶作業Job的所有Task都要求執行安全冗余調度(如圖4)，即Job的每個Task都要求產生2個副本(例如，圖4 Task A的副本1和副本2)，分別調度到Job關聯的可信域節點Y和調度域節點Z中分別執行。

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

1)對副本1在節點Y中的當前執行環境計算Hash校驗值Et，并提交中央節點。

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

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

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

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

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

安全規則4 一個租戶作業Job的所有Task都已經成功調度時，對成功/失敗分配了其中任何一個任務副本，而且屬于 Job調度域劃分的計算節點,更新這些節點針對Job所屬租戶U的信任度。

圖4 MapReduce安全冗余調度策略示意

5 實驗和分析

5.1 基于Hadoop MapReduce原型實現

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

5.2 性能分析

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

圖5 Hadoop MapReduce安全冗余調度策略原型實現系統結構

5.2.1 策略對Map/Reduce任務調度性能的影響

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

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

圖6 策略修改前后的Map/Reduce任務調度性能

可見，安全冗余調度策略會給MapReduce調度器帶來一些時間開銷。但是，如果可以選擇合適的MapReduce集群規模，使可調度計算資源足夠大，且每個作業的調度域節點和可信域節點總是能夠獲得情況下，可以適當減少由于計算資源不足而引起的動態域劃分重復計算帶來的開銷。

5.2.2 策略對系統資源利用率的影響

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

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

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

5.3 安全性分析

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

表2 系統中各待調度節點的當前狀態和待調度作業A的域劃分策略滿足情況

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

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

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

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

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

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

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

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

6 結束語

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

[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