[發明專利]針對Path ORAM的地址標簽分配調度與多路徑緩存寫回方法

有效

• 申請號: 202011152061.1
• 申請日: 2020-10-23
• 公開（公告）號: CN112181864B
• 公開（公告）日: 2023-07-25
• 發明（設計）人: 沈明華;肖儂;鄺金熙
• 申請（專利權）人: 中山大學
• 主分類號: G06F12/02
• 分類號: G06F12/02;G06F3/06
• 代理公司: 廣州三環專利商標代理有限公司 44202
• 代理人: 陳旭紅;吳落

本發明公開了一種針對Path?ORAM的地址標簽分配調度與多路徑緩存寫回方法，包括新數據進入ORAM樹的標簽分配、訪問路徑時的部分提前與合并、緩存中數據的寫回及數據寫回ORAM樹的標簽分配四個階段；在新數據進入內存或數據從緩存中寫回后對數據進行基于內存行的標簽分配或隨機分配；接著對路徑的訪問進入請求隊列，進行路徑提前或合并優化；執行對整條路徑的訪問，路徑中所有結點的數據被送入緩存；從緩存中返回數據時，選擇一條最優的路徑進行寫回，使得對于下一次隨機的路徑訪問中重疊的數據數量期望值最大。本發明提供的針對Path?ORAM的地址標簽分配調度與多路徑緩存寫回方法，在很小的硬件成本下，能快速訪問Path?ORAM，并降低執行時間，顯著提高系統性能。

技術領域

本發明涉及信息安全技術領域，尤其涉及一種針對Path?ORAM的地址標簽分配調度與多路徑緩存寫回方法及裝置。

背景技術

不可見存儲器(Oblivious?RAM，以下簡稱ORAM)是一種保護內存訪存模式的安全協議，該協議將對單個內存單元的訪問轉化為計算不可區分的含有固定數量訪存的訪問序列，從而掩蓋原有的訪問模式。其中，基于路徑的不可見存儲器(Path?Oblivious?RAM，以下簡稱Path?ORAM)是目前訪存效率最高，可行性最強的ORAM協議。但是，ORAM協議帶來的巨大的內存訪問開銷，會嚴重降低系統性能。

為了降低訪問開銷，現有技術通常采用以下幾種做法：第一，通過識別并丟棄路徑訪問之間的冗余請求部分，從而降低一部分開銷，但該方法在數據之間存在依賴性時具有一定的局限性，可實施性差；第二，根據fork?Path?ORAM的數據寫回后短時間內不會再讀取的這一現象，將“讀操作”提前到“寫操作”之前，該方法雖然能有效提升系統性能，但是降低的開銷占比很小，訪問成本依然很大；第三，通過給主ORAM樹設置一個小的ORAM樹作為其緩存，而該方法與第二種效果類似，Path?ORAM的訪存開銷仍然很大。因此，如何實現大幅降低Path?ORAM的訪存開銷，并且顯著提高系統的性能，是目前Path?ORAM訪存中亟待解決的問題。

發明內容

本發明的目的在于提供一種針對Path?ORAM的地址標簽分配調度與多路徑緩存寫回方法，該方法通過隱藏訪存模式進行調度優化，在很小的硬件成本下，就能夠快速訪問Path?ORAM，從而大幅降低Path?ORAM的訪存代價，同時降低系統執行時間，顯著提高系統性能。

為了克服上述現有技術中的缺陷，本發明實施例提供了一種針對Path?ORAM的地址標簽分配調度與多路徑緩存寫回方法，包括：

新數據進入ORAM樹的標簽分配階段、訪問路徑時的部分提前與合并階段、緩存中數據的寫回階段及數據寫回ORAM樹的標簽分配階段；

A.在新數據進入ORAM樹的標簽分配階段，執行如下操作：

A1.將新數據的地址記為addr，若與該新數據于同一內存行的地址中，存在在ORAM樹中未成對的內存單元，將該內存單元地址記為addr’，執行步驟A2；

A2.根據位置圖，獲得addr’地址對應單元的路徑標簽label’及所在層數l’；為新數據隨機分配一個與label’的二進制前l’位相同的新標簽label－k；

A3.根據位置圖，判斷label－k對應的path－k的前l’個節點中是否有空閑位置，若是，則執行步驟A4；若否，則返回執行步驟A2，并將隨機分配的新標簽記為label－k’；

A4.根據path－k中已配對數據的數量，判斷該數量是否達到第一預設閾值k；若否，則執行步驟A5；若是，則返回執行步驟A2，并將隨機分配的新標簽記為label－k’；

A5.將新數據的地址addr和標簽label－k的配對關系標記在位置圖中，并將該數據插入到ORAM樹中，更新該數據的配對狀態為已配對；

B.在訪問路徑時的部分提前與合并階段，執行如下操作：