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

有效

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

1.一種針對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.在訪問路徑時的部分提前與合并階段，執行如下操作：

B1.根據當前訪問路徑的周期終點標志判斷是否到達周期終點；若是，執行步驟B2；若否，執行步驟B3；

B2.將訪問隊列中最前面的兩個路徑請求需要訪問的路徑序號依次記為i，j，將每條路徑請求需要訪問的內存單元數量記為L，將路徑中已經配對的數據數量分別記為ri、rj，根據具體設定情況判斷是否進行訪問路徑時的部分提前與合并操作；

B3.重置周期計數器，將周期終點標志置反，且下一次路徑訪問不執行提前或合并操作；

C.在緩存數據的寫回階段，當緩存中有多條路徑時，將使得下一次隨機的路徑訪問中重疊的數據數量期望值最大的路徑作為最優路徑進行寫回；

D.在數據寫回ORAM樹的標簽分配階段，當所述數據為目標數據時，由ORAM控制器為之分配一個新的標簽，當所述數據為其他數據時，保持原標簽不變。

2.根據權利要求1所述的針對Path?ORAM的地址標簽分配調度與多路徑緩存寫回方法，其特征在于，在所述A.在新數據進入ORAM樹的標簽分配階段，還包括執行步驟A6；

其中，在所述步驟A1中，若與該新數據于同一內存行的地址中，不存在在ORAM樹中未成對的內存單元，則執行步驟A6.為該新數據隨機分配一個標簽后插入到ORAM樹中，更新位置圖，并將該新數據的狀態設置為未配對。

3.根據權利要求1或2所述的針對Path?ORAM的地址標簽分配調度與多路徑緩存寫回方法，其特征在于，所述D.在數據寫回ORAM樹的標簽分配階段，具體執行以下操作：

D1.根據當前目標數據的成對標識，判斷上一次目標數據是否已配對；若是，則執行步驟D2；若否，則執行步驟D3；

D2.隨機給當前目標數據一個新標簽，記錄當前狀態為未配對，并更新位置圖；

D3.將待寫回的目標數據作為新數據，返回執行A1－A6操作；

D4.當目標數據和其他數據在不與自身標簽沖突時，將其插入到ORAM樹的路徑中，并將所有數據寫回內存。