一種自適應Trie樹的云數據完整性驗證方案

潘洪志，劉 榮，祖 婷，劉 波，方 群，2，何 昕，2，王 楊，2

1(安徽師范大學 數學計算機科學學院，安徽 蕪湖 241002) 2(安徽師范大學 網絡與信息安全安徽省重點實驗室，安徽 蕪湖 241002) E-mail：asdphz2015@163.com

1 引 言

云存儲系統作為云核心服務能夠為用戶提供動態可伸縮的數據服務[1]，但數據完整性受到多方威脅.用戶存儲在云端的數據可能遭到其他用戶或云計算服務提供商的窺視、修改或損壞，而云服務提供商可能對用戶隱瞞數據丟失的問題，仍然聲稱正確持有用戶的數據，用戶數據的完整性無法保證[2].因此，如何及時有效地檢測云存儲數據完整性是云服務面臨的重大挑戰.

目前，研究者已經提出了很多面向云存儲服務的數據完整性審計方案[3-7].Erway等人[8]首先提出了一個支持全動態更新的數據持有性證明機制，針對用戶以塊為單位的數據更新操作，通過引入帶rank信息的認證跳表來維護和驗證這些數據塊標簽的有效性，但是對于大型數據，服務器構建的跳表結構存在認證路徑過長的問題.Zhu等人[9]提出了一個高效的云存儲數據完整性驗證方案，該方案基于同態驗證標簽和哈希索引層次結構，能夠減少用戶和云服務端的計算和存儲負擔.Yang等[10]提出了一個使用索引Hash表結構的動態審計方案，但后來該方案被Ni等[11]證明是不安全的.Wang等[12]提出了另一種支持全動態操作的數據完整性驗證機制，該機制利用BLS簽名通過使用Merkle Hash樹(Merkle Hash Tree，MHT)實現動態審計，但由于MHT構造過程復雜，為降低通信開銷減小塊長度也將導致MHT的深度增加，因此存儲和計算開銷難以接受.秦志光等[13]利用改進的MHT和雙線性對技術提出了一個層次化索引結構的動態審計協議，該協議支持用戶多粒度的動態操作，可以一定程度地減小通信開銷，但無法精確鎖定數據塊.Yao等[14]提出了一種基于多分支路徑樹的完整性驗證方案，簡化了動態更新流程但產生輔助信息過多，導致通信開銷較大.為解決云存儲服務的動態數據完整性檢測方案中計算開銷大，不能較好的支持高效的全動態更新的問題，本文提出了一個自適應Trie樹(Adaptive Trie Tree，AT)的云存儲數據完整性驗證方案，該方案通過改進Trie樹結構，使驗證樹的深度得到控制，能夠支持高效的全動態更新(插入，修改和刪除)，并降低系統的通信開銷和計算復雜度，優化云存儲數據完整性驗證機制的性能.

本文首先給出云環境下數據完整性檢測模型，通過分析傳統Trie樹結構的特點，引入輔助節點和特殊的標識編碼方式，設計一種自適應Trie樹結構.然后設計與實現本文檢測模型下AT結構的驗證方案.最后通過理論分析和仿真實驗證明方法的有效性.

2 系統模型

云數據完整性驗證模型由用戶(User)、可信第三方審計者(Trust Third Party Auditor，TTPA)和云服務提供商(Cloud Service Provider，CSP)組成.其中CSP中包含可信存儲(TCS)和不可信存儲(UCS)，可信計算(TCC)和不可信計算(UCC).用戶數據存放在不可信存儲中，數據的驗證輔助信息存放在可信存儲中；用戶數據的動態更新是不可信計算，用戶數據的檢測由可信計算實現.可信第三方審計者(TTPA)是通過用戶授權來負責檢測和管理云存儲中的用戶數據的機構.數據完整性驗證分為初始化階段、挑戰-應答階段、返回結果.首先初始化階段，對用戶數據進行預處理，同時和CSP、TTPA協商密鑰.挑戰-應答階段，完整性驗證工作交給TTPA和CSP去操作.TTPA首先向CSP發送挑戰信息，CSP接收挑戰信息，然后計算驗證證據P返回給TTPA，最后TTPA進行證據的驗證.其過程如圖1所示.

圖1 數據完整性審計模型Fig.1 Data integrity audit model

本文系統模型中，用戶將自己的數據存儲在CSP的不可信存儲服務中，同時TTPA接受用戶委托去定期檢測數據完整性.然后，TTPA要求CSP對用戶的數據執行數據完整性檢測請求，從而以便于可信計算模塊返回證據給TTPA；最后，TTPA驗證返回來的證據，并反饋結果給用戶.用戶通過反饋的結果可以得到自己的數據是否損壞.

3 基于AT樹的云存儲數據完整性驗證方案

3.1 AT樹

Trie樹又稱字典樹、單詞查找樹或者前綴樹，是一種用于快速檢索的多叉樹結構，如英文字母的字典樹是一個26叉樹，數字的字典樹是一個10叉樹.Trie樹通過字符串的公共前綴可以有效的減少字符串的比較，從而提高查詢效率，節省了存儲空間.但若存在一個無公共前綴的長字符串將會導致整棵樹的失衡，易受到DoS攻擊造成安全隱患.另外，Trie樹用內存指針來連接節點且字符串以明碼存儲于樹中，更增加了安全隱患.

在傳統的Trie樹只有一類節點，以數組表示，每個index是指向子節點的指針.在AT樹中，新增兩個新節點-葉子節點和擴展節點，節點由key和value組成.key為帶標識id的十六進制前綴碼，標識id用于區分葉子節點和擴展節點.若終止符標記被打開，那么key對應的是葉子節點，value存儲數據的Hash值；若終止符標記被關閉，那么value值就是用于在數據塊中查詢對應的節點的地址.

圖2 自適應Trie樹節點結構Fig.2 Adaptive Trie tree node structure

如圖2所示，擴展節點和葉子節點的id位為1個4bit二進制數字，最低位表示key的奇偶性，第二低位編碼終止符狀態.

圖3是一個自適應Trie樹的結構圖.

圖3 自適應Trie樹的初始化結構圖Fig.3 Initialization of an adaptive Trie tree structure

如圖3所示，通過增加節點的種類，樹的深度可以得到有效控制，避免攻擊者操縱樹的深度，發起DoS攻擊；而且樹的根只取決于數據的內容，與其更新順序無關.另外為保護機密性，AT樹節點二元組只存儲經過特殊編碼的值，可有效保護數據隱私，提高安全性.

3.2 基本算法

本方案涉及到4個安全算法，分別說明如下：

1)KeyGen(1λ)→(pk，sk)：輸入安全參數λ輸出公鑰私鑰(pk，sk).

G1，G2是階為素數p的乘法群，令e：G1×G2→GT表示一個雙線性映射，u和g分別為G1和G2的生成元，哈希函數h(·)：G1→Zp.則私鑰sk∈G1，公鑰pk≡(u，g，usk，gsk).

2)SigGen(sk，F)→(Trust)：輸入私鑰sk和文件F，輸出數據塊簽名集合.

用戶將文件F劃分為n個數據塊{m1，m2，…，mn}，用戶分別為這n個數據塊生成標簽Ti=(H(ti)·umi)sk，其中ti=FID‖N‖h(mi)，“FID”表示文件F的身份標識，N為更新時間戳，h(·)為非碰撞(collision-free)哈希函數.通過上述計算，用戶生成一個同態標簽集合Trust={Ti|i∈{1，2，3，…，n}}.然后將標簽集合Trust和數據文件分塊集合{m1，m2，…，mn}發送給CSP，同時刪除本地的文件.當CSP接收到用戶數據后，構造圖2的自適應Trie樹.

3)GenProof(F，chal，Trust)→(P)：輸入文件F，簽名集合和挑戰信息chal，輸出chal中指定的數據塊的完整性證據P；

4)VerifyProof(pk，chal，P)→(TRUE，FALSE)：輸入步驟一中生成的公鑰pk，步驟三中的證據P和TPA發起的挑戰信息chal，如果驗證得到的結果通過，系統輸出TRUE，否則輸出FALSE.

審計者收到證據P后，審計者驗證公式(1)，如果驗證成功，輸出結果為“true”，否則系統輸出“false”.公式為：

(1)

3.3 動態數據操作

用戶對云存儲數據操作包括更新、刪除和查找，操作過程如圖4和圖5所示.

圖4 數據塊更新前Fig.4 Before the data block update

下面從AT樹的更新，刪除和查找過程來說明AT樹的操作.

3.3.1 更新

1)如果node是空節點，直接對key加上終止符，然后進行特殊前綴編碼.

2)如果節點是分支節點，且key為空，則說明更新的是分支節點的value，直接將node[-1]設置成value；如果key不為空，則遞歸更新以key[0]位置為根的子樹.

3)如果node是葉子節點或者擴展節點.令curr_key是node的key，找到curr_key和key的最長公共前綴，長度為prefix_length.key剩余的部分為remain_curr_key；若remain_key=[]=remain_curr_key，那么如果node是葉子節點，直接更新.如果node是擴展節點，那么遞歸更新node所連接的子節點；如果remain_curr_key==[]，則如果node是擴展節點，遞歸更新node所連接的子節點，如果node是葉子節點，那么創建一個分支節點，分支節點的value是當前node的value，分支節點指向一個葉子節點；如果key和curr_key有公共部分，則為公共部分創建一個擴展節點，此擴展節點的value鏈接到上面步驟創建的新節點，返回這個擴展節點，否則直接返回上面步驟創建的新節點.

圖5 數據塊更新后Fig.5 After the data block update

3.3.2刪除

1)如果node是空節點，直接返回空節點.

2)如果node為分支節點.如果key為空，表示刪除分支節點的值.如果key不為空，則遞歸查找node的子節點，然后刪除對應的value.

3)如果node為葉子節點或者擴展節點，curr_key是當前node的key；如果key不是以curr_key開頭，說明key不在node為根的子樹內，直接返回node；如果node是擴展節點，遞歸刪除node的子節點.

3.3.3 查找

1)如果node是空節點，返回.

2)如果node是分支節點，如果key為空，返回分支節點的value；否則遞歸查找node的子節點.

3)如果node是擴展節點，如果key以curr_key開頭，遞歸查找node的子節點；否則，說明key不在node為根的子樹里，返回空節點.

4 安全分析

4.1 重放攻擊

在云存儲中環境中，用戶存儲在云存儲中的數據遭到非人為的損壞，CSP通過利用原始的數據塊和對應數據標簽來欺騙TTPA.為了解決重放攻擊，本方案驗證數據塊時首先驗證數據塊對應標簽的更新版本.而且，本方案中的自適應Trie樹的每條路徑的索引中都增加了更新的標識，每當數據塊的編碼標識信息通過TTPA驗證之后，TTPA才進行下一步的數據完整性驗證工作.由Hash函數性質可知，重放的標簽通過審計者的驗證的概率是在完全可接受的范圍.

4.2 拒絕服務攻擊(DOS attack)

本方案的自適應Trie樹結構中，通過改進傳統的Trie樹結構，根據AT樹的特點，每個節點的key值通過十六進制前綴編碼，最壞的情況樹的深度為16，由于引入輔助節點，又將樹的深度控制到可靠的程度.如圖7所示，即使攻擊者故意偽造用戶向CSP發出大量的惡意存儲請求，也無法使該樹達到受攻擊的深度，這樣有效的保護了用戶存儲服務的安全高效的使用.

5 實驗分析

本文實驗環境在Windows操作系統中，編程語言為Java.利用PBC和OpenSSL庫實現哈希和雙線性運算.本文實驗輸入數據是總文件大小1GB，數據是1600個隨機數據文件，實驗結果分析是計算10次實驗的平均值作為最終結果.

5.1 方案檢測概率分析

本方案首先從概率上來分析檢測的準確性.首先假設用戶每次隨機挑戰總數據n塊中的c塊數據，若其中的c塊數據遭到惡意服務破壞.我們設隨機變量X表示可以檢測損壞數據塊的數量，其樣本空間X={0，1，2，…，k}.由概率基礎知識得到：

(2)

圖6 檢測數據塊損壞準確性分析Fig.6 Analysis of damage accuracy of data block

從圖中可以看出，隨著被破壞的數據塊數量的增多，則只需要抽取更少的數據塊就能成功檢測到數據是否被損壞.本方案通過改進傳統的Trie樹結構，保留了Trie查找的優勢，所以隨機抽取一定數量的數據塊進行驗證的效率比傳統的Merkle hash tree結構效率差不多，然后輔助信息的開銷卻小很多.

5.2 效率分析

1)分析數據塊的數量對本方案樹的深度的影響，對于文獻[12]中的MHT樹，假設數據分成n塊，則至少需要建立深度為「log2n?+1的二叉樹.方案[14]中的LBT結構是基于多分支路徑樹，它的深度是隨著出度的增加而改變.

圖7 數據塊數量—樹的深度Fig.7 Number of data blocks -tree depth

如圖7，隨著結點的增多，樹的深度隨數據塊n的增多呈增長趨勢.從圖中可以明顯看出，方案10的增長速度明顯高于本方案，由于方案10采用的是傳統的二叉樹結構，樹的平均深度為「log2n?+1 .由于本方案的AT樹結構的通過引入輔助節點致使樹的深度可控的，從圖中也可以看出本方案AT樹的深度隨著數據塊的增加趨于平穩.

2)為進一步分析方案性能，對CSP計算證據的時間開銷進行分析，我們取500塊數據，運行程序后輸入不同的數據塊大小，分別得到三種方案計算證據的時間如圖8所示.

圖8 CSP生成證據的時間開銷Fig.8 Proof generated time by CSP

從圖8中可以看出隨著數據塊大小的增加，CSP計算證據的時間都會逐漸增加，每次驗證的數據塊數量越多，CSP計算證據所花費的時間也越多，CSP的計算開銷越大.結合圖6，隨機抽取400個數據塊就已經能夠以一個很高的概率檢測出數據是否被破壞，從圖8中所示，隨機抽取500個數據塊，本文方案CSP計算證據的時間開銷保持在較低水平.

6 總 結

隨著云計算技術的發展，云數據的安全問題成為研究者關注的熱點.本文提出一種自適應Trie樹的動態數據完整性驗證方案，該方案通過引入兩個輔助節點，改善了傳統Trie樹的高度不可控的問題，保留了傳統Trie樹的高效查詢的優點，節點經過特殊編碼，有效地保護用戶數據機密性和完整性.通過實驗分析，該方案能夠有效的進行動態數據的完整性驗證.未來工作應研究高效的Trie樹存儲機制以減少驗證輔助數據占用的空間，以做到算法的時空最優化.