濮傳威 張功萱 周俊龍 付安民

(南京理工大學計算機科學與工程學院 南京 210094)

為了防止信息通過內(nèi)存總線泄露，研究者們已經(jīng)提出了安全處理器模型，例如XOM[1]，AEGIS[2]，SGX[3].安全處理器模型主要依靠數(shù)據(jù)加密確保系統(tǒng)安全性.

然而，單獨使用數(shù)據(jù)加密已經(jīng)不足以保護系統(tǒng)的安全性，因為每次內(nèi)存訪問仍然需要明文內(nèi)存地址.攻擊者仍然可以通過總線窺探訪問的內(nèi)存地址從而獲得隱式信息[4]，如圖1所示.因此，內(nèi)存地址被訪問的順序(即內(nèi)存訪問模式，簡稱訪問模式)可以暴露正在運行的程序和數(shù)據(jù)的大量敏感信息.例如，觀察指令的執(zhí)行順序可以揭示程序執(zhí)行的轉移方式、循環(huán)次數(shù)以及訪問某個內(nèi)存地址的頻率等.

圖1 窺探安全處理器的總線獲得隱式信息

鑒于此，有研究者們提出了不經(jīng)意隨機訪問機(oblivious random access machine, ORAM)[5-6].ORAM是一種加密原語，它將每次對存儲器的真實訪問轉換為一系列隨機訪問，從而隱藏真實訪問.ORAM最初作為一種軟件算法由Goldreich[5]提出，用于隱藏客戶端對遠程云存儲的訪問模式，該算法具有非常大的性能開銷.在ORAM的最初提議之后，研究者們一直在努力尋找一種在加密方面更安全、更可行的ORAM方案.

ORAM的概念也被考慮在處理器—內(nèi)存級別，以隱藏處理器對片外不可信內(nèi)存的訪問模式[7-10].處理器對內(nèi)存進行訪問時，集成在片上的ORAM控制器會生成對片外內(nèi)存的虛擬訪問，這些虛擬訪問從隨機內(nèi)存地址獲取加密的數(shù)據(jù)塊，對數(shù)據(jù)進行操作后重新加密并寫回內(nèi)存，使攻擊者無法發(fā)現(xiàn)真實訪問地址或訪問類型.因此，ORAM在完成訪問時會產(chǎn)生巨大的延遲，使得ORAM對于大多數(shù)應用程序都是不切實際的，尤其是在硬件級別實現(xiàn)到處理器中時.

針對具有片外不可信內(nèi)存的處理器系統(tǒng)，本文提出了一種可廣泛實際應用的處理器—內(nèi)存級的ORAM方案——分組ORAM(group ORAM).該方案在保證安全性的同時降低性能開銷.與現(xiàn)有技術相比，其性能開銷不會隨著內(nèi)存容量增加而增加，并與應用程序大小無關，因此對于大型應用程序具有高度可擴展性，從而降低了成本，并使ORAM概念實用化.同時，分組ORAM引入了參數(shù)化設計，可以調(diào)整參數(shù)以滿足對性能、安全性的不同需求.

1 相關工作

ORAM的概念最初由Goldreich[5]提出，以防止在訪問遠程不可信云存儲設備時通過訪問模式泄露信息.在現(xiàn)階段ORAM是隱藏用戶訪問模式的主要方法.當用戶訪問存儲在服務器的數(shù)據(jù)時，他們會同時訪問有效數(shù)據(jù)和虛擬數(shù)據(jù)，這將混淆用戶訪問的目標數(shù)據(jù)，從而隱藏用戶的訪問行為[11-12].然而，ORAM在提高安全性的同時，會顯著增加存儲空間的負擔和交互數(shù)據(jù)量，例如：為了混淆目標數(shù)據(jù)塊，需要添加部分虛擬數(shù)據(jù)塊，并且需要對不同數(shù)據(jù)塊進行多次訪問.如何在保證用戶訪問行為安全性的前提下提高ORAM的訪問效率是一個挑戰(zhàn)性問題.

另一種減少性能開銷的方案是Goldreich等人[6]提出的分層ORAM(hierarchical ORAM).該方案將數(shù)據(jù)塊組織成層次結構.需要lbN層來存儲N個數(shù)據(jù)塊.第i層包含2i個桶，每個桶又包含lbN個數(shù)據(jù)槽用于存儲數(shù)據(jù).每個層級中的數(shù)據(jù)塊使用隨機選擇的散列函數(shù)存儲在相應的桶中.對于每次數(shù)據(jù)訪問，首先掃描2個頂部的桶，在其他每個較低層級上，只掃描1個桶(若數(shù)據(jù)未找到，則掃描該層級上由散列函數(shù)指定的桶；若數(shù)據(jù)已找到，則隨機掃描該層級上的1個桶).最后將找到的數(shù)據(jù)寫入第1層的桶內(nèi).該方案對于每次數(shù)據(jù)訪問的平均開銷為O(lb4N)，最壞情況下為O(Nlb3N).

分層ORAM方案由于客戶端存儲量小且層次結構中每個較高級別的數(shù)據(jù)塊數(shù)量呈指數(shù)增長，因此隨著層次結構中每個新層級的添加，數(shù)據(jù)打亂重組的開銷會顯著增加.這限制了分層ORAM的可伸縮性和性能.

實施和管理多個ORAM及其本地緩存的開銷是很大的.針對這個問題，Shi等人[15]對分層ORAM進行了改進，進一步提出了Path ORAM[16]，它以二叉樹的形式存儲數(shù)據(jù).每個葉子節(jié)點代表1條路徑，每個數(shù)據(jù)映射到1個葉子節(jié)點即1條路徑.數(shù)據(jù)可以存儲在該路徑上的任意節(jié)點之中.使用位置圖映射數(shù)據(jù)塊所在路徑；并用緩沖區(qū)暫時存放訪問的數(shù)據(jù)塊.對于每次數(shù)據(jù)訪問，Path ORAM找到該數(shù)據(jù)塊所在的路徑，并讀取該路徑上所有數(shù)據(jù)塊，然后將它們解密后緩存到緩沖區(qū)中，再將請求數(shù)據(jù)塊返回給處理器以進行讀取或更新.然后將請求的數(shù)據(jù)塊隨機映射到新的路徑上.Path ORAM對于每次數(shù)據(jù)訪問在最好和最壞情況下的開銷是相同的，即O(lbN).

基于Path ORAM算法，研究者們提出了多種Path ORAM原型系統(tǒng)(PHANTOM[7],Tiny ORAM[8],Secure Dimm[9],D-ORAM[10],Freecursive[17],ASCEND[18])，旨在實際環(huán)境中評估該算法的實用性.表1給出了現(xiàn)有ORAM原型系統(tǒng)的歸納.

表1 現(xiàn)有ORAM原型的歸納

盡管現(xiàn)有設計使ORAM實現(xiàn)成為可能，但它們的性能開銷仍然很大.在第2節(jié)將給出一種分組ORAM方案，它在最佳和最壞情況下都具有O(1)的性能開銷，即性能開銷與應用程序大小無關，這使得它在處理器級系統(tǒng)設計上具有高度可擴展性.并且針對不同平臺對安全性以及性能的要求，可以進行靈活配置.

2 分組ORAM方案

2.1 分組ORAM方案設計

圖2給出了帶有分組ORAM的處理器系統(tǒng)的抽象視圖.分組ORAM與處理器位于同一芯片上并被視為可信，而內(nèi)存位于片外并被視為不可信，攻擊者可以觀察到被訪問的數(shù)據(jù)及其地址.

圖2 使用分組ORAM的處理器系統(tǒng)的抽象視圖

圖3 分組ORAM體系結構

處理器在每次Cache未命中時通過分組ORAM訪問片外內(nèi)存.為了訪問數(shù)據(jù)塊，處理器指定其邏輯地址LA要執(zhí)行的操作op(讀/寫)和要寫入的數(shù)據(jù)data(如果操作是寫入).分組ORAM將內(nèi)存訪問請求的邏輯地址轉換為隨機物理地址訪問序列{PA1，PA2，…}.

分組ORAM所需的應用程序的邏輯存儲空間由2部分組成：應用程序空間(application space)和虛擬空間(dummy space).假設應用程序大小為N個數(shù)據(jù)塊,虛擬空間為D個數(shù)據(jù)塊，則對于該應用程序，分組ORAM所需的總內(nèi)存空間為N+D.虛擬空間僅對分組ORAM可見，而應用程序空間對處理器和分組ORAM均可見.類似地，包含應用程序數(shù)據(jù)的數(shù)據(jù)塊稱為真實塊(true block)，包含虛擬數(shù)據(jù)的數(shù)據(jù)塊稱為虛擬塊(dummy block).

與其他現(xiàn)有方案類似，分組ORAM方案將執(zhí)行1組任務以隱藏訪問模式：選擇1組數(shù)據(jù)塊，解密該組數(shù)據(jù)塊(將其中真實訪問的數(shù)據(jù)塊返回給處理器)，將該組數(shù)據(jù)塊與ORAM緩存中的塊進行隨機排列，再將其重新加密，并寫入內(nèi)存.這組基本任務統(tǒng)稱為ORAM操作.ORAM操作將真實內(nèi)存訪問轉換為一系列虛擬訪問以覆蓋真實訪問從而隱藏訪問模式.

2.2 分組ORAM結構

圖3示出分組ORAM的體系結構.包括位置圖(position map)、組管理單元(group management unit, GMU)、加密單元(Enc-pipe)、解密單元(Dec-pipe)、隨機數(shù)生成器(random number generator, RNG)以及2個特殊緩沖區(qū)，數(shù)據(jù)緩存緩沖區(qū)(cache buffer, CBuffer)和組地址緩沖區(qū)(group address buffer, GAB).除了這些組件之外，還有1個讀緩沖區(qū)(read buffer, RBuffer)和1個寫緩沖區(qū)(write buffer, WBuffer)來保存內(nèi)存讀取和寫入操作的數(shù)據(jù).

位置圖：提供每個邏輯數(shù)據(jù)塊的當前物理地址.由于位置圖的目的是映射每個數(shù)據(jù)塊的當前位置，因此只要數(shù)據(jù)塊的位置改變，該表就會更新.

CBuffer：暫時存放從內(nèi)存讀取的真實數(shù)據(jù)塊，并且在對讀取的數(shù)據(jù)塊進行打亂重組時起關鍵作用.

GMU：保存每個數(shù)據(jù)塊對應的組，若分組ORAM需要從片外內(nèi)存訪問某個數(shù)據(jù)塊，則在GMU中找到該數(shù)據(jù)塊對應的組，位置圖將給出該組數(shù)據(jù)塊物理地址，并將其發(fā)送到GAB.

GAB：保留當前操作的1組數(shù)據(jù)塊的片外內(nèi)存地址.因此，GAB的大小與組大小相同.

加/解密單元(encryption/decryption pipelines)：為了保護數(shù)據(jù)機密性，每個數(shù)據(jù)塊在被發(fā)送到片外內(nèi)存之前都進行了加密.當從片外內(nèi)存獲取數(shù)據(jù)塊時，需要將其解密.

RNG：在ORAM操作過程中，有6種類型的隨機值r1～r6需要動態(tài)生成.

r1：位數(shù)為lb(N+D)(單位為b)，用于初始化GMU，從而為每個數(shù)據(jù)塊隨機構建相應的組.

r2：位數(shù)為lbG(單位為b)，用于在塊置換期間為將要移動到WBuffer中的塊選擇新位置.其中G是組大小.每個ORAM操作總共需要G個不同的r2值.

r3：位數(shù)為lbC(單位為b)，用于選擇CBuffer中的位置以緩存從內(nèi)存讀取的真實數(shù)據(jù)塊，其中C為CBuffer大小.每個ORAM操作都需要G個r3值.

r4：用于生成需要放入WBuffer的虛擬塊.

r5：位數(shù)為lbG(單位為b)，用于選擇GAB中的位置，以放置數(shù)據(jù)塊的物理地址PA.

r6：用于在重新加密相同明文數(shù)據(jù)塊.

2.3 分組ORAM算法

在分組ORAM設計中，任何時候，真實數(shù)據(jù)塊都位于片上CBuffer或片外內(nèi)存中的某個位置.在對數(shù)據(jù)塊進行訪問時，如果塊位于CBuffer，則不需要進一步的ORAM操作；否則，將執(zhí)行ORAM操作從片外內(nèi)存中獲取請求的塊.

初始化時，CBuffer滯空，位置圖存儲每個數(shù)據(jù)塊的當前位置.GMU為每個數(shù)據(jù)塊構建其對應的組.圖4(a)為1個簡單的GMU存儲示例，每個數(shù)據(jù)塊都有其對應的組(在這個示例中，組大小G=3).并且每個數(shù)據(jù)塊與組內(nèi)其他數(shù)據(jù)塊的關系可以用有向圖表示，如圖4(b)所示.以數(shù)據(jù)塊A為例，數(shù)據(jù)塊C和D被分配在該組內(nèi)，在訪問數(shù)據(jù)塊A時，數(shù)據(jù)塊A,C,D將形成一小簇數(shù)據(jù)塊一同被ORAM控制器訪問.為了隱藏訪問模式，在數(shù)據(jù)塊A被訪問后，ORAM控制器將該組數(shù)據(jù)塊在WBuffer內(nèi)進行隨機排列并寫入片外內(nèi)存，同時更新位置圖以及GMU內(nèi)數(shù)據(jù)塊之間的關系.

為了從片外內(nèi)存訪問數(shù)據(jù)塊，處理器將請求access(A,op,D)發(fā)送到分組ORAM控制器，其中數(shù)據(jù)塊的邏輯地址是LA，op是讀或?qū)懖僮?，如果是寫操作，則D是要寫入的數(shù)據(jù).分組ORAM控制器遵循算法1中定義的數(shù)據(jù)訪問協(xié)議oram_access，以隱藏對片外內(nèi)存的真實訪問.

圖4 GMU存儲示例

對于處理器的1次訪問請求，ORAM控制器首先查找位置圖以確定數(shù)據(jù)塊的位置.如果塊在片上，則在CBuffer上執(zhí)行訪問——如果是讀操作，則將請求的數(shù)據(jù)發(fā)送給處理器進行讀取，否則使用新數(shù)據(jù)更新緩沖區(qū)中的塊.但是，如果塊位于片外內(nèi)存中，則執(zhí)行ORAM操作，具體操作步驟由算法1給出.

算法1.oram_access:用于數(shù)據(jù)訪問的分組ORAM協(xié)議.

輸入：處理器請求(A，op，D)、位置圖、組管理單元GMU、組大小G；

輸出：執(zhí)行對所請求的數(shù)據(jù)塊的操作op.

① 在位置圖中查找數(shù)據(jù)塊A所在位置;

② if 數(shù)據(jù)塊A在片上 then

③//片上訪問

④ ifop==讀操作 then

⑤ 在CBuffer內(nèi)查找數(shù)據(jù)塊A并將其返回給處理器;

⑥ else

⑦ 在CBuffer內(nèi)查找數(shù)據(jù)塊A并將其更新為D;

⑧ end if

⑨ goto end

⑩ else

3 方案可行性分析

3.1 安全性分析

由于數(shù)據(jù)塊之間形成關系圖保持不變，并且每次對1組數(shù)據(jù)塊訪問后，都將這組數(shù)據(jù)塊與ORAM緩存中的塊一同隨機排列，所以每個數(shù)據(jù)塊可以在整個關系圖中以相同的概率出現(xiàn)在任意位置.因此，在整個內(nèi)存空間的分配中，分組ORAM均勻隨機地將數(shù)據(jù)塊的邏輯地址映射到物理地址.此外，每個數(shù)據(jù)塊在內(nèi)存中都以密文的方式存儲，并且數(shù)據(jù)塊在被處理器訪問后都需進行重新加密.因此攻擊者在數(shù)據(jù)總線上窺探時不能得到任何顯示信息.

為了訪問某個數(shù)據(jù)塊，分組ORAM首先找到其所在的組，并將該組數(shù)據(jù)塊一并進行訪問.這組數(shù)據(jù)塊具有以下幾個性質(zhì)：1)內(nèi)存空間中的任意數(shù)據(jù)塊都以相同的概率可能出現(xiàn)在該組內(nèi)；2)組內(nèi)數(shù)據(jù)塊之間并無關聯(lián)；3)組內(nèi)數(shù)據(jù)塊以隨機順序被訪問.因此，攻擊者在窺探地址總線時無法知道請求塊的真實位置.此外，組內(nèi)的真實數(shù)據(jù)塊在被訪問后將以隨機位置保存在CBuffer中，并且這些位置原有的數(shù)據(jù)塊與虛擬數(shù)據(jù)塊將以隨機位置寫回內(nèi)存.這意味著，如果處理器再次請求相同的塊，它將直接從CBuffer中讀取，除非在訪問該數(shù)據(jù)塊時，該數(shù)據(jù)塊已經(jīng)被其他真實數(shù)據(jù)塊替換并寫回內(nèi)存.

給定N個數(shù)據(jù)塊的應用空間和D個數(shù)據(jù)塊的虛擬空間，組大小為G.假設y是處理器請求內(nèi)存的訪問序列，其中包含m個請求塊.對于y=(a1,a2,…,am)，分組ORAM生成實際訪問序列：

z=(G1,G2,…,Gm),

(1)

其中Gi表示數(shù)據(jù)塊ai對應的組，每個組中包含G個需實際訪問的數(shù)據(jù)塊.

在數(shù)據(jù)塊ai被訪問后，它將暫時存放于CBuffer中，由于它在CBuffer中的位置是隨機的，它被其他后續(xù)訪問的數(shù)據(jù)塊替換的順序也是隨機的，并且被替換后與組內(nèi)其他數(shù)據(jù)塊進行隨機排列，形成新的組Gj，因此數(shù)據(jù)塊ai下一次被訪問時所在組的可能性的總數(shù)為

(2)

假設數(shù)據(jù)塊ai下一次被訪問時所在的組為Gj，Gj被選擇的概率為

(3)

并且在組內(nèi)，每個塊都以概率1/G獨立映射，利用貝葉斯原理，可以得到：對于訪問序列y，分組ORAM根據(jù)y形成的2次實際訪問序列z=z′的概率為

(4)

這個概率非常小，以至于實際訪問序列z與z′在計算上無法區(qū)分，也就是說，對于某個訪問序列y，攻擊者幾乎不可能觀察到2次相同的實際訪問序列.因此，攻擊者無法知道真正的訪問模式y(tǒng).

3.2 開銷分析

如前所述，現(xiàn)有ORAM方案面臨的一個難題就是開銷.在保證安全性的同時，這里對分組ORAM在內(nèi)存帶寬使用、訪問延遲和內(nèi)存空間消耗3個方面產(chǎn)生的開銷進行分析.

內(nèi)存帶寬使用：從算法1可以看出，對于每次真實訪問，分組ORAM從片外內(nèi)存讀取G個數(shù)據(jù)塊，然后寫入相同數(shù)量的數(shù)據(jù)塊，導致每次真實訪問總共使用2G塊帶寬.由于它是1個常數(shù)，并且作為參數(shù)可以設置，所以無論片外內(nèi)存容量(或應用程序數(shù)據(jù)塊總數(shù))多大，內(nèi)存帶寬使用開銷均為O(1).

訪問延遲：對于每次真實訪問，分組ORAM僅訪問恒定的G個數(shù)據(jù)塊，同時位置圖以及GMU更新也都只針對常數(shù)量的數(shù)據(jù)塊.因此，分組ORAM算法的延遲開銷也為O(1).

由于內(nèi)存帶寬使用以及訪問延遲帶來的開銷都為O(1)，因此，分組ORAM的性能與應用程序或片外內(nèi)存的大小無關.然而，片外內(nèi)存的大小影響了位置圖以及GMU的大小.

內(nèi)存空間消耗：像大多數(shù)現(xiàn)有的ORAM方案一樣，分組ORAM需要消耗額外的內(nèi)存空間用于虛擬數(shù)據(jù)塊.理想情況下，虛擬空間越大塊位置越不可預測.但是，虛擬空間太大會導致片外和片上的大量存儲消耗.本文嘗試減少虛擬空間，同時為每次內(nèi)存訪問實現(xiàn)盡可能高的隨機性，如下所示.

由于分組ORAM中可以使用的不同組的總數(shù)為S，如式(2)所示，因此，分組ORAM具有足夠大的塊空間供數(shù)據(jù)塊打亂重組，并提供比其他現(xiàn)有ORAM方案更高的隨機化能力，例如數(shù)據(jù)塊只能打亂重組到N條路徑上的Path ORAM.

給定組大小G，1個組包含1個虛擬數(shù)據(jù)塊的概率為P1=D/(N+D)，包含2個虛擬數(shù)據(jù)塊的概率為P2=(D/(N+D))2，包含k個虛擬數(shù)據(jù)塊的概率為Pk=(D/(N+D))k，其中k

如2.1節(jié)所述，分組ORAM使用CBuffer和WBuffer將數(shù)據(jù)塊隨機打亂重組寫回內(nèi)存，并且對于隨機性，參與ORAM操作的虛擬塊具有重要作用.

為了實現(xiàn)每個組中虛擬數(shù)據(jù)塊數(shù)量的隨機性，組中具有不同數(shù)量虛擬塊的概率應盡可能接近.也就是說，概率比例r=Pi/Pi+1=(N+D)/D應盡可能小.該比例隨著虛擬空間D的增加而減小，但存在1個肘點，如圖5中的r曲線所示.肘點為最佳(最小)虛擬空間提供了良好的折中方案.

給定r曲線，要找到肘點，首先創(chuàng)建1條連接曲線2個端點的直線.肘點則位于從該直線到曲線形成最長直角距離的位置，如圖5所示：

圖5 r值與虛擬空間的關系

r曲線可以寫成:

(5)

其中y1表示比例，x表示虛擬空間大小，N作為常數(shù)表示應用程序數(shù)據(jù)空間大小.

2個端點可以近似為(0,N)，(N,0)，它們之間的連線可以表示為

y2=-x+N.

(6)

由于r曲線的導數(shù)為y′=-N/x2，其中N>0，x2>0，所以y′<0.則r曲線單調(diào)遞減.在r曲線上任意一點的切線，都與該點的曲率半徑相垂直，而斜率相等的2條直線相互平行.因此，在r曲線y1上找一點，如果該點的切線的斜率與直線y2的斜率相等，那么該點的曲率半徑垂直于直線y2，因此，該點就是所求的肘點.

(7)

將式(7)代入式(5)，得

(8)

(9)

4 實驗結果及對比

對于給定的應用程序，使用處理器模擬工具Simplescalar[19]對其在處理器上的執(zhí)行進行模擬，從中獲得處理器的內(nèi)存訪問序列(Las)，分組ORAM使用Verilog HDL實現(xiàn)，并使用Xilinx vivado對Xilinx xc7vx330t FPGA平臺進行仿真和綜合.通過Xilinx仿真，可以得到分組ORAM輸出的實際訪問序列(PAs)，然后使用NIST[20]測試套件檢測內(nèi)存總線上地址訪問的隨機性.

在實驗中，將內(nèi)存塊大小B設置為128 b，內(nèi)存塊地址大小設置為18 b(N+D=218).加密算法選擇國密算法SM2[21]進行加密和解密，SM2是基于基本橢圓曲線(ECC)密碼的公鑰密碼算法標準，其安全強度比RSA高，且運算速度快于RSA.同時采用與文獻[8]中使用的片外內(nèi)存相同的模型，并使用線性反饋移位寄存器(LFSR)進行隨機數(shù)生成.

下面將首先評估分組ORAM的性能開銷，然后討論生成的訪問序列的隨機性.

4.1 性能評估

在實驗中，研究了配置不同組大小和CBuffer大小時的性能開銷.對于每種配置都執(zhí)行Mibench基準測試程序組[22]的子集.對于每個基準測試，獲得了沒有分組ORAM的處理器系統(tǒng)以及集成了分組ORAM的處理器系統(tǒng)的執(zhí)行時間.性能開銷用執(zhí)行速度降低μ來衡量，即使用分組ORAM時的執(zhí)行時間與不使用分組ORAM時的執(zhí)行時間之比，μ值越高說明執(zhí)行速度的降低越明顯.

如2.3節(jié)所述，如果在CBuffer中發(fā)現(xiàn)請求的數(shù)據(jù)塊，分組ORAM不會執(zhí)行片外內(nèi)存訪問.因此，除了數(shù)據(jù)打亂重組，CBuffer的大小C影響應用程序的總體執(zhí)行時間.為了探究這種影響，測試了不同CBuffer大小的執(zhí)行性能.從圖6可以觀察到，對于給定的組大小和CBuffer大小，執(zhí)行時間之比μ都不同，具有良好局部性或較小工作數(shù)據(jù)集的基準測試程序(如CRC32)會產(chǎn)生較少的內(nèi)存訪問，因此它們的性能不會受到ORAM的太大影響.但對于一些基準測試程序，如Rijndael，執(zhí)行速度會大幅降低.其次，執(zhí)行各種基準測試程序時，對于不同CBuffer大小，μ值都有所變化，其中組大小G固定為16個數(shù)據(jù)塊.可以觀察到，每當CBuffer大小增加1倍，μ值會隨之降低，當CBuffer大小較大時，μ值降低更明顯.當CBuffer大小從256塊增加到512塊時，μ值降低了23.6%.

圖6 當分組ORAM配置不同CBuffer大小時執(zhí)行時間之比

決定性能開銷的另一主要因素是組大小G.組大小與ORAM操作的延遲成正比.因此，在評估中納入了分組ORAM組大小.圖7示出給定CBuffer大小C=256的條件下，隨著組大小的變化，執(zhí)行時間之比μ的變化.從圖7可以看出，當組大小增加時，μ值隨之增加，即執(zhí)行性能下降.這一趨勢再次證實了預期的結果，即增加組大小會增加每個基準測試程序的完成時間.然而，由于處理器緩存中的高命中率，具有良好數(shù)據(jù)局部性或較小工作集的應用程序受到的影響相對較小.

圖7 當分組ORAM配置不同組大小時執(zhí)行時間之比

圖8 當分組ORAM配置不同CBuffer大小時訪問序列隨機性變化

從圖7還可以觀察到，當組大小G從16增加到32時，執(zhí)行時間之比μ會大幅增加，這意味著ORAM訪問效率大幅下降，在4.3節(jié)將對最佳組大小G的選擇進行分析.

4.2 安全性評估

分組ORAM生成的實際訪問序列的隨機性同時受組大小和CBuffer大小的影響.在執(zhí)行每個基準測試程序期間，通過配置不同的組大小G和CBuffer大小C，獲得了分組ORAM生成的內(nèi)存訪問序列.每個訪問序列中的隨機性都是通過NIST隨機性測試套件評估的.對于每個內(nèi)存訪問序列，執(zhí)行NIST測試套件中的所有測試，從而獲得該訪問序列的平均隨機性通過率.更高的通過率意味著序列的隨機性更高.

圖8示出在給定組大小G為16個塊時，CBuffer大小C如何影響生成的訪問序列的隨機性.同樣，在給定CBuffer大小為256塊時，圖9顯示了組大小G如何影響生成的訪問序列的隨機性.從圖8可以看出，隨機性與組大小和CBuffer大小成正比.這是因為增加組大小會在每次ORAM操作中打亂重組更多數(shù)據(jù)塊，而增加CBuffer大小會提供更多的片上數(shù)據(jù)打亂重組空間.

從圖9還可以發(fā)現(xiàn)，組大小G從16增加到32時，隨機性通過率的變化并不明顯.這意味著當組大小達到16時，安全性已經(jīng)到達瓶頸，再增加組大小只會造成性能大幅下降，如4.1節(jié)所述.

圖9 當分組ORAM配置不同組大小時訪問序列隨機性變化

4.3 比 較

下面，將分組ORAM與目前最先進的設計方案Tiny ORAM[8]進行比較.表2示出兩者在FPGA資源消耗方面的開銷——查找表(LUT)、觸發(fā)器(FF)和塊RAM(BRAM)數(shù)量.表3示出兩者在每次內(nèi)存訪問時操作效率方面的比較.

表2 2種方案在FPGA資源消耗方面的比較

表3 2種方案在1次內(nèi)存訪問時操作效率方面的比較

從表2可以看出，分組ORAM消耗較少的為FF，LUT和BRAM相對較多.而從表3可以看出，對于每次內(nèi)存訪問，分組ORAM需要0.29～0.34 μs.與Tiny ORAM相比，延遲降低了75.7%～79.3%.

5 總 結

本文提出了一種ORAM方案——分組ORAM，它將真實內(nèi)存訪問隱藏在對一小簇內(nèi)存地址的虛擬訪問中，從而達到隱藏內(nèi)存訪問模式的目的.該方案使用緩沖區(qū)來解耦讀取和寫入之間的塊，從而使每個組不相關.此外，該方案引入了參數(shù)化設計，可以調(diào)整參數(shù)以滿足不同平臺對性能、安全性的需求.通過執(zhí)行Mibench基準測試程序來評估該方案的性能，并使用NIST測試生成的片外內(nèi)存訪問序列的隨機性評估該方案的安全性.實驗結果表明，相較之前的工作，分組ORAM方案能顯著減少性能開銷.同時，針對組大小為8～32個數(shù)據(jù)塊和CBuffer大小為64～512個數(shù)據(jù)塊的不同配置，其生成的內(nèi)存訪問序列隨機性測試通過率達到94.6%～98.5%.與現(xiàn)有方案相比，分組ORAM在性能、安全性和內(nèi)存消耗方面的表現(xiàn)都有所提升.