隨著云存儲技術的發展，越來越多的客戶將數據存儲在云服務器上，數據的安全也越來越受到重視。數據加密技術可以保護數據的內容，但無法隱藏客戶對數據的訪問模式，攻擊者通過分析數據的訪問模式可能獲得存儲數據的信息。例如，攻擊者獲知醫生在診斷患者患有某種疾病時需要訪問某些記錄，當某人就診時，醫生對這些記錄進行了訪問，攻擊者即可推斷出該人患有某種疾病。為了保護客戶的隱私，需要隱藏客戶對存儲系統的訪問模式，實現數據訪問的無關性(obliviousness)。所謂數據訪問的無關性是指對任意兩次數據訪問(不管是讀還是寫)，所訪問的存儲位置的序列是等同的[1]。一種最簡單的解決方法就是每訪問一個數據時讀寫所有數據。每讀一個數據時先解密，寫回時再加密，每次加密所用的密鑰均不相同，使得攻擊者無法識別寫回的數據是原數據還是修改后的數據。但該方法的代價太大，因此，GOLDREICH O提出了無關RAM模型機(Oblivious RAM，簡稱O-RAM)[2]并解決這一問題。隨著云計算的飛速發展，在數據外包中O-RAM的應用有著重要作用。

1 相關研究
    參考文獻[1]提出最有效的隱藏訪問模式是采用分層結構算法。在分層結構算法中，如果洗牌算法采用AKS網絡排序[3]算法，則平均時間復雜度為O(clog4N)，其常數項c大約為6 000。當采用巴切排序網絡算法[4]時平均時間復雜度為O(clog4N)，其常數項c大小較為合理[5]。

    以上所提算法均由兩個階段構成，即訪問階段和洗牌階段，算法的瓶頸就在洗牌階段。在洗牌時，客戶與服務器之間需要進行大量的數據交換，使得客戶無法忍受洗牌過程占用的大量時間。如果能把洗牌過程分解到每次訪問操作中，對服務器的訪問時間保持在常數量級，這樣就能將理論應用于實踐中。因此，本文提出一種新的結構，在需要少量客戶端存儲空間和線性級服務器存儲容量的情況下，使得每次操作的代價為O(1)。典型算法的性能比較[9]如表1所示。

2 常量級訪問模式
    本文假設客戶端可信而服務器端不可信。O-RAM的目標就是對服務器完全隱藏數據訪問模式，即從服務器角度觀察，客戶端每次讀或寫數據塊請求將產生一個完全隨機的數據訪問序列。
2.1 數據結構
    假設客戶的數據大小為N塊，每塊大小為L字節，在云存儲中，L的典型值一般為64 KB～256 KB。本方案需要占用服務器存儲容量為3N塊，利用均勻隨機函數將N個數據塊均勻隨機地分布到3N個存儲塊中，其余2N個存儲塊存放啞元塊。
    在客戶端設置一個緩存隊列Q、兩張數據表SerMap和PosMap。
    緩存隊列Q用來管理從服務器讀取的數據塊，本文假定最多可存儲32個數據塊。對緩存隊列的操作有：Q.in(b)將數據塊b插入隊尾；Q.out()從隊首移出數據塊；Q.remove(b)將數據塊b從緩存隊列中移出；Q.getLen()返回緩存隊列中存放的數據塊數；Q.getSit(b)返回數據塊b在緩存隊列中的位置；Q.getSitF()返回隊首數據塊的塊號。
    SerMap[3N]用來表示存儲在服務器上各數據塊的存儲位置，它有3個域，分別是FlData、FlAcc和Fresh。FlData表示存儲類型，其值為1表示該塊為數據塊，否則為啞元塊；FlAcc表示其對應的存儲塊最近是否被訪問過。當讀/寫存儲塊后，該變量的值設置為1。在查找一個啞元塊時，若其值為0則選中該塊，若其值為1則改為0，繼續查找下一個啞元塊；Fresh表示服務器存儲塊的新鮮度，在對服務器的每次讀操作后都會使該變量的值增1，以保證相同數據在加密后結果不一樣。
    PosMap[N]用來表示用戶數據塊在服務器中存放的位置映射，包括flag和blockAdd兩個域。flag表示數據塊存放在服務器/本地的標志，若其值為1時，則表示數據塊存放在服務器端，否則存放在Q中；blockAdd指數據塊在SerMap/Q中的位置。
2.2 訪問模式
    定義1：設客戶對服務器的操作為(op，u，data)，其中，op表示read(u)或者write(u，data)操作，u表示將要讀或寫的數據塊標識，data表示要寫的數據塊。
    無論op是讀操作還是寫操作，其訪問服務器的序列由Lookup算法決定。
2.2.1 Lookup算法
    Lookup算法描述如下：
    Lookup(op,u,data*);
        1：Random read n ( n <= 6)
blocks from server;
        2：if (PosMap[u].flag=0) then
{//所讀塊在Q中
        3：ReadDummy();//隨機
讀一啞元塊
        4：Q.remove(u); Q.in(u);  //將該塊從Q中移出
再插入隊尾
        5：} else
        6：ReadBlock(u);  //從服務器端讀數據塊u
并插入Q中
        7：Random read 6-n blocks from server;
        8：if (op=write) then
        9：Q.bufs[PosMap[u].blockAdd]&larr;data*;
//將要寫的數據保存在Q中相應的緩沖區中
        10：Evict( ); //為避免Q溢出，將部分數據塊
寫入服務器
        11：return (PosMap[u].blockAdd);
    在該算法中第1行和第7行共讀服務器6次，其中隨機讀取2個數據塊和4個啞元塊，需要把所讀的數據塊保存在Q中。第2行至第6行讀取指定的數據塊u并保存在Q中。如果數據塊u已在Q中，則隨機讀一啞元塊。根據程序局部性原理可知，最近訪問的數據塊在最近的將來仍有可能再被訪問到，因此對Q的管理并不按照嚴格意義上的先進先出策略，而是當訪問的數據塊在Q中時，將該塊從Q中移出并放到隊尾，以保證從Q中踢出的數據塊是不常用的數據塊。
    當op是寫操作時，將要寫的內容覆蓋Q中保存數據塊u的緩沖區(第9行)。在每一次Lookup調用中，不停地有數據塊存入Q中，Q總會變滿，因此需要定期將Q中的數據塊寫入服務器以防止Q溢出，第10行是調用Evict將Q中的最久未用的數據塊寫入服務器。
2.2.2 Evict算法
    Q中最多可存放32個數據塊，調用一次Lookup最多有3個數據塊進入Q中。因此，在Evict算法中，當Q的長度超過29時，則將超出的數據塊寫入服務器以保證Q在下一次Lookup操作時不會溢出。Evict算法描述如下：
    Evict( )    //寫數據塊或啞元塊到服務器
        1:m&larr;0
        2:while (Q.getLen()>29) do {
        3:WriteBlock(); //將Q中隊首數據塊寫入服務器
        4:m&larr;m+1
        5:}
        6:for i=m+1 to 6 do
        7:WriteDummy( ); //隨機寫啞元塊到服務器中
        8:return;
    第1行至第5行將數據塊寫入服務器。Evict踢出算法每次寫6次服務器，先將緩存隊列中的數據塊寫入服務器，然后用啞元塊補足6塊（第6行至第7行）。
2.3 洗牌
    每執行一次Lookup都會將任意兩個數據塊讀入Q中，當Q長度超過29時，就將超出的數據塊寫到服務器端的任意位置，實現洗牌操作，這樣可將整個洗牌操作分攤到每次Lookup中，避免了集中洗牌造成的突發訪問。
2.4 性能
    假定存儲塊大小為64 KB，參考文獻[9]與本文性能對比如表2所示。當數據文件小于等于16 TB時，所用客戶存儲空間小于參考文獻[9]，當數據文件大于16 TB時，所需客戶存儲量超過參考文獻[9]。本文算法的優勢在于所需服務器存儲空間較少，實際性能恒定。參考文獻[9]采用集中洗牌，當洗牌時需要大量的數據交換，當客戶在讀寫操作時，若正好遇上洗牌操作，則需要等待很長時間。

2.5 安全
    定義2：設y=((op1，u1，data1)，(op2，u2，data2)，&hellip;，(opM，uM，dataM))是客戶請求訪問數據塊的一個序列，其長度為M。設A(y)表示存取訪問模式，當客戶的請求序列是y時，用A(y)表示存取訪問服務器的序列。如果對于任何兩個客戶訪問序列y和y&prime;，只要其長度相等，對任何人（除客戶本人）來說A(y)和A(y&prime;)都是計算上不可區分的，則稱該O-RAM結構是安全的。
    在Lookup中，數據塊u在服務器上的存儲位置是隨機分布的，讀取u和6次隨機讀數據塊操作混在一起，攻擊者很難猜到哪一塊是真實的塊，并且攻擊者很難知道下一次它將存放在哪一個位置。
    在訪問服務器的過程中可能出現剛被淘汰出的數據塊又要被訪問的情況。這種情況下，攻擊者仍然無法獲取有用的信息，因為至少有2/3的數據塊是隨機選取讀到Q中的，最多有1/3的數據塊是客戶所讀的數據塊，但Evict算法采用最久未用塊淘汰策略，攻擊者無法知道所讀的塊是否為所需的數據塊，也無法知道什么時間該塊會寫入服務器，即攻擊者從被踢出后又要被訪問的數據塊中無法獲取有用的信息，因此系統是安全的。
    本文提出的常量級訪問模式僅需占用線性級服務器存儲量就可實現無關訪問服務器，但它需要占用客戶端存儲空間，當文件長度超過16 TB時，比參考文獻[9]的算法占用更大的客戶端存儲空間。下一步工作將在減少占用客戶端存儲空間方面進行研究，找到一個需求客戶空間更少的算法。
參考文獻
[1] GOLDREICH O，OSTROVSKY R.Software protection and  simulation on oblivious RAMs[J].Journal of the ACM，1996，43(3)：431-473.
[2] GOLDREICH O.Towards a theory of software protection and  simulation by oblivious RAMs[C].New York：STOC，1987.
[3] AJTAI M，KOLMOS J，SZEMEREDI E.An O(nlogn) sorting  network[C].Boston：STOC，1983.
[4] BATCHER K.Sorting networks and their applications[C]. NJ：AFIPS Spring Joint Computing Conference.1968.
[5] PINKAS B，REINMAN T.Oblivious ram revisited[C].California：CRYPTO.2010.
[6] GOODRICH M T，MITZENMACHER M.  Privacy-preserving access of outsourced data via oblivious ram simulation[J]. Automata，Languagesand Programming，2011(6756)：576-587.
[7] BONEH D，MAZIERES D，POPA R A.Remote oblivious storage：Making oblivious ram practical[EB/OL].[2011-3-30].http：//dspace.mit.edu/bitstream/handle/1721.1/62006/MIT-CSAIL-TR-2011-018.pdf.
[8] STEFANOV E，SHI E，SONG D.Towards practical oblivious ram[C].California:NDSS，2012.
[9] SHI E，CHAN T H H，STEFANOV E，et al.Oblivious RAM with o((logn)3) worst-case cost[C].Seoul：ASIACRYPT，2011.