PDM中基于cuckoo filter的數據完整性校驗算法設計與實現

叢麗暉 何國強 夏秀峰,2

1(沈陽航空航天大學計算機學院 遼寧 沈陽 110136)2(沈陽航空航天大學遼寧省通用航空重點實驗室 遼寧 沈陽 110136)

PDM中基于cuckoo filter的數據完整性校驗算法設計與實現

叢麗暉1何國強1夏秀峰1,2

1(沈陽航空航天大學計算機學院 遼寧 沈陽 110136)2(沈陽航空航天大學遼寧省通用航空重點實驗室 遼寧 沈陽 110136)

為滿足PDM海量數據存儲與高并發訪問要求，構建基于企業私有云的PDM系統成為未來的必然選擇。現有文件系統數據完整性校驗算法多是基于RSA公鑰密碼技術，但這種技術突出問題是需要大量的模指數運算，其計算開銷較大，尤其在大數據存儲的條件下。針對PDM文件的大數據校驗和數據動態性問題，提出基于cuckoo filter的數據完整性校驗算法，以cuckoo filter作為校驗標簽存儲結構，將基于哈希算法中的校驗哈希值進行壓縮，在滿足PDM動態數據校驗要求的前提下，實現輕量級的完整性校驗。最后論證了該方案的安全性，并通過性能分析和實驗驗證了該方法是高效可行的。

企業私有云 PDM 數據完整性 校驗 cuckoo filter

0 引 言

目前PDM系統仍采用集中式的存儲方式，但隨著制造企業數據量的快速增長，傳統集中式的存儲方式嚴重制約了PDM系統的整體性能。因此構建企業私有云環境下的PDM文件系統，為PDM提供更高效率文件存儲服務。

存儲在私有云環境中的PDM數據，并非安全可靠的，由于受人為誤操作、存儲介質損壞、磁盤讀寫錯誤、自然災害等多種因素導致重要數據的丟失，將會給企業帶來無法彌補的損失，維護數據完整性變得至關重要。

近年來，針對數據完整性的驗證方案已經取得了一些成果，文獻[1]提出基于赫爾曼密鑰交換協議的完整性驗證方案。該方案需要將要校驗的文件作為指數進行模冪運算，因此僅適用于小文件。文獻[2]將同態哈希函數應用在遠程數據完整性校驗中，使得后期驗證方案中同態函數被廣泛使用[3-4]。文獻[5]提出的基于RSA 的同態驗證標簽校驗方案是第一個同時兼具安全性與實用性的概率性校驗方案。該方案可以將數據塊及同態標簽很好地綁定在一起，但也正是這個特性，決定了該方案只能適用于靜態的文件數據。文獻[6]對原始跳表[7-9]在結構上進行了改造，提出第一個完全支持數據塊動態更新的完整性驗證方案，該方案將數據塊的標簽存儲在跳表的底層節點中來提供數據隱私保護，但這種處理比基于同態函數方案的操作開銷要大。文獻[10]提出一種針對數據塊的循環隊列校驗機制，雖然可動態增加隨機挑戰次數，但每次哈希都綁定多個數據塊，因此不適用于動態數據。綜上，現有方法主要有以下不足：(1) 有些方法不適用于私有云存儲環境；(2) 現有完整性驗證方案的研究多是基于長期歸檔的數據，但在PDM中，有些數據在其整個生命周期內由于修改或存儲空間的遷移呈現出動態性；(3) 現有方案多是基于RSA公鑰密碼技術，計算開銷很大。

本文針對以上不足，結合PDM數據的特點，提出一種支持公開驗證的云存儲數據完整性校驗方法，以高空間效率的cuckoo filter為每個塊校驗信息的存儲結構，將基于哈希算法中的校驗哈希值進行壓縮，在滿足校驗次數需求的同時降低校驗計算和存儲開銷。通過正確性和安全性分析，證明了該方法是高效可行的。

1 完整性校驗模型

企業私有云存儲校驗模型由3個實體組成：用戶、云存儲服務器CSS和第三方驗證者TPA，如圖1所示。其中用戶上傳數據文件到云服務器，云服務器管理用戶的數據文件，分配存儲空間和計算資源。為了確保遠程存儲數據的完整性，通過第三方驗證者對云服務器發送挑戰請求，協助用戶完成數據的驗證。

圖1 校驗模型

在數據存儲周期內，客戶端根據數據的實際情況，與云服務器達成周期內的數據校驗次數。一次校驗過程如下：TPA生成和發送一個挑戰到CSS，CSS根據接收到的挑戰，利用算法生成存儲數據的相應證據返回給TPA。TPA再結合存儲的校驗元信息判斷云服務器是否完好保存數據。

在云存儲環境中，用戶面對CSS可能存在以下2種攻擊[11]：(1) 篡改攻擊：CSS損壞用戶的數據后偽造其數據校驗證據，以達到通過TPA驗證的目的； (2) 重放攻擊：CSS執行某個數據塊的校驗時采用校驗證據重放的方式蒙蔽校驗者。

2 相關知識與設計目標

2.1 cuckoo filter

cuckoo filter是一種結構簡單且具有高空間效率的隨機數據結構，它提供每個關鍵字兩個可能的存儲位置，動態的重定位已經存在的關鍵字，在插入操作時為新關鍵字騰出空間，查詢操作時快速定位關鍵字位置。雖然需要反復的重定位，但預期的cuckoo filter插入時間依然為O(1)[12]。插入過程如圖2(a)所示。圖2(b)所示為添加一個新元素之后的結果，圖2(c)將一個bucket擴展到四個槽的情況。每個槽對應一個摘要值tag。

圖2 cuckoo filter操作示意圖

通過如下公式計算關鍵字的兩個候選bucket：

k1=HASH(key)

(1)

k2=k1⊕HASH(tag)

(2)

式(2)中的異或操作確保了一個重要的性質：通過相同的公式及k2和tag值，反過來計算出k1的位置。也就是說，知道了當前的bucket，知道摘要值tag，就可以計算出另外一個bucket，計算公式如下所示。

k’=k⊕HASH(tag)

(3)

基于tag的插入算法，使插入操作只需運用bucket內的信息，無需再重新檢索關鍵字。通過式(1)和式(2)實現元素的動態增加和刪除操作，使用具有高效計算和存儲優勢的cuckoo filter應用到數據完整性校驗中可以很好地降低校驗標簽的存儲和計算開銷。

2.2 數據完整性校驗要求

本文所提方案中，文件是以數據塊作為基本單位存儲，一個文件F可看作由n個數據塊組成。

定義1 校驗標簽。校驗標簽是指針對文件F的每個數據塊fi，i∈[1，n]。在校驗初始化時，生成的相關元信息Tfi。

分塊的校驗標簽能夠使校驗的粒度細化到數據塊級的范圍，有助于數據的恢復。并且多個數據塊可能存儲在多個服務器中，所以分塊的校驗標簽能提高并發性。

定義2 校驗力度。設文件F劃分為n個數據塊F={f1,f2,…,fn}，若一次校驗過程中所校驗的實際數據塊數量為c={s1,s2,…,sc} ，則稱c與F的比值H為校驗力度。

對云存儲中數據完整性校驗的方案而言，校驗力度H的值越高，可認為所校驗的數據塊的完整性驗證結果越可靠。

定義3 可校驗度。數據完整性校驗過程中，數據塊損壞且能夠被檢驗出的概率p稱為可校驗度。

校驗過程中，如果p不小于某個閾值時，即認為所校驗數據塊的結果認為是可靠的。

在企業私有云環境下，為了實現PDM文件生命周期內輕量級的完整性校驗，本文方案擬實現以下四個要求:

(1) 針對動態數據的低校驗開銷。PDM數據文件在其存儲周期內進行增加、修改、刪除等頻繁操作，使得已生成的校驗標簽失效，而重新生成和更新校驗標簽會增加計算開銷和傳輸負擔。因此，生成的校驗標簽能滿足數據塊生命周期內校驗次數需求即可。

(2) 提高校驗力度。一次性對所有數據塊進行校驗代價很大，所以為了減少計算成本和計算時間。本文采用概率性的校驗算法在保證可校驗度p的情況下提高校驗力度。

(3) 公開審計。通過TPA去驗證云數據的正確性，不給用戶帶來額外的負擔。

(4) 減少對應用環境的依賴關系。固定分塊大小的存儲策略被應用于許多云存儲系統，而基于RSA公鑰密碼的方案建議分塊大小為4 KB[5]，對數據分塊大小限制較為嚴格。本文通過改進數據完整性校驗算法，可以減少數據分塊大小對用戶的限制。

3 基于cuckoo filter的數據完整性校驗方法

3.1 校驗標簽的生成和更新

在基于cuckoo filter生成校驗標簽時，假定一個PDM文件生命周期內數據的動態性使校驗過程需要支持t輪校驗，那么所有t輪校驗之前，需要確定cuckoo filter的長度L，每個數據塊的摘要值的位數w，以及每個bucket的大小b，其中b的值為4時，其空間效率和誤判率達到最優[12]。誤判率即指將一個不屬于集合的元素錯認為屬于此集合的概率ε。即:

ε=1-(1-1/2w)b≈b/2w

(4)

w=log2(b/ε)=log2(1/ε)+log2b

(5)

L≥t×[log2(1/ε)+log2b]

(6)

在校驗過程中，校驗標簽的更新會由以下兩種情況引起，一種是執行一輪校驗之后校驗標簽的更新，另一種是修改數據塊帶來的校驗標簽更新，對于前一種情況，每輪校驗開始時都會取一個新校驗值執行校驗，校驗結束后拋棄掉使用過的校驗值。而第二種情況，對任意數據塊的更新，算法只需刪除原來塊對應的校驗標簽重新生成即可。

3.2 校驗算法描述

基于cuckoofilter的完整性校驗由5個階段組成：初始化階段(setup)、標簽生成階段(tagBlock)、挑戰階段(challenge)、證據生成階段(proofGen)和驗證證明階段(proofVerify)。

(1)setup(t,p)→(sk,L,t)：客戶端通過校驗標簽的可校驗度p和文件的預校驗輪數t，根據式(4)、式(5)、式(6)確定校驗標簽的長度L、摘要值位數w，同時生成客戶端密鑰sk，該sk用于生成每輪的挑戰關鍵字。

(2) tagBlock(F,sk,L,t)→T：首先將原始文件F劃分為n個數據塊F={f1,f2,…,fn}，然后根據客戶端密鑰sk，生成t輪校驗關鍵字ckeyid,i=sig(sk‖id‖i)，i∈[1,t]，id∈[1,n]，其中sig為簽名函數。再對每個數據塊fid和關鍵字ckeyid,i通過安全哈希函數得出每一輪的摘要值vi=Hsk(fid‖ckeyid,i)，然后以vi為參數利用式(1)、式(2)計算出k1和k2，并得到第i輪的校驗值λi，通過k1和k2將λi插入到校驗標簽Ti中，共t輪。如此依次計算所有數據塊，輸出其校驗標簽集合T={Tid|id∈[1,n]}。最后將T傳輸給TPA，同時初始化校驗輪次{ri}1≤i≤n←{0}。

(3) Challenge(sk)→chall：TPA從集合{1，2，…，n}中隨機選擇c個元素組成集合I={s1,s2,…,sc}，然后根據客戶端密鑰sk，計算本輪關鍵字ckeyi=sig(sk‖i‖ri)，s1≤i≤sc，將挑戰信息chall={ckeyi,i}s1≤i≤sc發送給CSS，同時更新rsi=rsi+1。

(4) proofGen(chall，F)→ans：根據挑戰信息chall生成挑戰數據塊的摘要值vi=Hsk(fi‖sig(sk‖i‖ri))，s1≤i≤sc。最后把c個數據塊的摘要值組成證據集合{vi}s1≤i≤sc返回給TPA。

(5) proofVerify({vi}s1≤i≤sc，I)→(TRUE，FALSE)：TPA通過集合I，查找到相應的數據塊校驗標簽Ti，i∈[s1,sc]。同時根據集合I對應的數據塊證據集{vi}s1≤i≤sc，如果對?vi∈{vi}s1≤i≤sc通過式(1)、式(2)都有?λi∈Si與之相匹配，則數據塊fi通過驗證，同時更新校驗標簽。當所有數據塊通過校驗，輸出“TRUE”，否則輸出“FALSE”。

3.3 算法分析

定理1 基于cuckoo filter的完整性校驗方案具有不可篡改性。

證明：考慮到使用的安全哈希函數是安全的，則通過篡改校驗值而通過驗證的概率可歸為cuckoo filter的誤判率，則其可篡改的概率就是1/2w，如果ε=1%時，由式(4)得w=9，那么此時篡改概率只有0.2%。因此，服務器不使用正確數據塊而通過驗證的概率可以忽略，即該校驗方案具有不可篡改性。

定理2 基于cuckoo filter的完整性校驗方案具有不可重放性。

證明 在校驗過程中，每輪校驗開始都會使用一個新的校驗值，校驗值使用完畢后通過式(1)、式(2)更新校驗標簽，剔除過期的校驗值。因此，基于cuckoo filter的完整性校驗方案可防止重放攻擊。

定理3 基于cuckoo filter的完整性校驗方案在抽樣校驗中可達到其他方案相同的可校驗度。

證明 考慮一般抽樣校驗過程，假定文件F有n個數據塊，其中比例為a的數據塊，即n×a個數據塊發生損壞。假定一次校驗中抽取c個隨機且不重復的數據塊，則可校驗度P為：

(7)

假定基于cuckoofilter的校驗標簽的可驗證度為P′，則有:

P′=P×(1-f)

即:

P′≈[1-(1-a)c]×(1-f)

(8)

式(7)與式(8)表明采用基于cuckoofilter的校驗標簽時，由于f非常小，這樣只要在一次校驗過程中，通過抽取增加少量的數據塊即可達到相同的可校驗度。

4 實驗與性能分析

4.1 存儲開銷

本文算法中，主要存儲開銷在TPA和CSS端，其中，TPA端校驗標簽的存儲開銷為n×L比特，另外需要額外存儲信息{ri}1≤i≤n，用于記錄各塊已挑戰次數，其存儲開銷為n×log2(t+1)比特，所以TPA總的存儲量為n×(log2(1/ε)+log2b+log2(t+1))比特。而文獻[8]算法中單個校驗標簽存儲開銷為|N|(N≥1024bit)。對于CSS只需存儲數據文件F，沒有額外存儲負擔。

4.2 計算開銷

本文方案的計算開銷分兩部分：初始化階段的計算開銷和挑戰-應答-驗證過程的計算開銷。前者由客戶端初始化時進行，后者由TPA和CSS在文件校驗周期內進行。對于一個數據文件，客戶端將其存儲到云服務器時進行一次setup操作，執行時間記為Tsetup，以Tsig和Tv分別表示一次sig(·)和Hsk(·)的運算開銷，Th表示一次單向Hash函數的運算開銷。則對于客戶端主要的計算負載為Tsetup+(Tsig+Tv+2×Th)×t，計算時間復雜度為O(n)。在挑戰-應答-驗證過程中，TPA需要生成挑戰信息chall、計算c個數據塊的位置和校驗值λ，并且CSS需要生成c個數據塊證據集合{vi}1≤i≤c，其主要的計算負載開銷為(Tsig+Tv+2×Th+Tg)×c，其中Tg代表偽隨機函數運算時間，計算時間復雜度為O(c)。在更新過程中，主要計算負載開銷為數據塊校驗標簽的生成和一次校驗執行的更新過程，其計算時間復雜度為O(1)。

實驗1 校驗初始化和校驗標簽生成的計算開銷

實驗基于Linux系統平臺，使用一臺曙光A620r-G服務器、兩臺曙光A840r-G服務器搭建分布式環境，存儲設備為曙光DS200-N10磁盤陣列。單個文件校驗開銷測試過程為10 MB的文件，測試其在分塊大小為4 KB到 64 KB之間，通過給定一系列的校驗輪次，與文獻[8]的算法進行對比，計算開銷實驗結果如圖3所示。

圖3 校驗初始化和校驗標簽生成計算開銷對比

從圖3可見，本文算法中生成校驗標簽的時間與校驗輪數t呈線性關系。并且在同等分塊大小的條件下，本文算法能支持數百輪以上的校驗，保持計算開銷的優勢。另外，文獻[8]的算法隨分塊大小的變化與時間呈指數關系，而本文算法在初始化和校驗標簽生成過程中基本不受數據分塊的影響。

實驗2 完整性校驗過程的計算開銷

對于同一個文件F，選擇不同的數據塊大小對完整性校驗計算實驗開銷。實驗過程中為以60%的校驗力度隨機抽取數據塊，記錄每次所花費時間，實驗結果如下：

圖4 校驗信息生成時間對比

圖4突出了本文算法的優勢所在，在校驗信息生成階段的計算開銷幾乎不受數據塊大小的影響。這是由于本文方案和文獻[8]算法相比，避免了使用開銷較大的有限域上的指數運算，只用到了較為高效的單向Hash函數，校驗信息生成過程耗費時間很短，有效降低了算法的計算開銷。

圖5 數據完整性校驗時間對比

在數據完整性校驗階段，由圖5表明兩種方案計算開銷都比較穩定，結果顯示符合預期目標，但本文算法只需查找對應校驗標簽中校驗值，其查找過程的時間趨近于零。

5 結 語

本文通過分析PDM文件的大數據校驗和數據動態性方面的特點，提出基于cuckoo filter的數據完整性校驗算法。通過哈希算法避免了對文件做模指數運算，降低了計算開銷。采用cuckoo filter作為校驗標簽將生成的校驗哈希值壓縮，降低存儲空間的代價，并通過校驗輪數滿足PDM數據動態性的校驗需求，從而達到在文件的生命周期內可以進行無限次校驗。最后通過實驗分析，證明算法在適用的校驗周期下保持計算開銷的優勢，且文件分塊的大小對校驗過程中的計算開銷幾乎沒有影響。該算法能夠更好地適用于PDM文件系統，實現PDM文件系統輕量級的數據完整性校驗，降低服務器的負載。

[1] Deswarte Y, Quisquater J J, Saidane A. Remote integrity checking[C]//Sixth Working Conference on Integrity and Internal Control in Information Systems, 2003: 1-11.

[2] Filho D L G, Barreto P S L M. Demonstrating data possession and uncheatable data transfer[DB/OL]. http://www.iacr.org/cryptodb/data/paper.php?pubkey=21643.

[3] 周銳, 王曉明. 基于同態哈希函數的云數據完整性驗證算法[J]. 計算機工程, 2014, 40(6): 64-69.

[4] 陳蘭香. 一種基于同態Hash的數據持有性證明方法[J]. 電子與信息學報, 2011, 33(9): 2199-2204.

[5] Ateniese G, Burns R, Curtmola R, et al. Provable data possession at untrusted stores[C]//Proceedings of the 14th ACM Conference on Computer and Communications Security. New York, NY, USA: ACM Press, 2007: 598-609.

[6] Shacham H, Waters B. Compact proofs of retrievability[C]//Proceedings of the 14th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology. Springer-Verlag, 2008: 90-107.

[7] Chang E C, Xu J. Remote integrity check with dishonest storage server[C]//Proceedings of the 13th European Symposium on Research in Computer Security. Springer-Verlag, 2008: 223-237.

[8] Hao Z, Zhong S, Yu N. A privacy-preserving remote data integrity checking protocol with data dynamics and public verifiability[J]. IEEE Transactions on Knowledge and Data Engineering, 2011, 23(9): 1432-1437.

[9]AtenieseG,PietroRD,ManciniLV,etal.Scalableandefficientprovabledatapossession[C]//Proceedingsofthe4thInternationalConferenceonSecurityandPrivacyinCommunicationNetworks.ACM, 2008: 1-10.

[10] 肖達, 舒繼武, 陳康, 等. 一個網絡歸檔存儲中實用的數據持有性檢查方案[J]. 計算機研究與發展, 2009, 46(10): 1660-1668.

[11]WangC,WangQ,RenK,etal.Privacy-preservingpublicauditingfordatastoragesecurityincloudcomputing[C]//Proceedingsofthe29thConferenceonInformationCommunications.IEEE, 2010: 525-533.

[12]FanB,AndersenDG,KaminskyM,etal.Cuckoofilter:practicallybetterthanbloom[C]//Proceedingsofthe10thACMInternationalonConferenceonEmergingNetworkingExperimentsandTechnologies, 2014: 75-88.

DESIGN AND IMPLEMENTATION OF THE DATA INTEGRITY CHECK ALGORITHM BASED ON CUCKOO FILTER IN PDM

Cong Lihui1He Guoqiang1Xia Xiufeng1,2

1(SchoolofComputerScience,ShenyangAerospaceUniversity,Shenyang110136,Liaoning,China)2(LiaoningGeneralAviationLaboratory,ShenyangAerospaceUniversity,Shenyang110136,Liaoning,China)

The PDM system based on enterprise private cloud is essential to be built to satisfy both massive data storage and high concurrency access. Existing file system data integrity check algorithm is commonly based on the RSA public key cryptography technology, but this technology requires lots of modular exponentiation, which has high overhead, especially in the large data storage environment. For the problem of large data validation and data dynamics of PDM file, a checking algorithm based on cuckoo filter is proposed, which utilizes cuckoo filter as the storage structure of tags. Then, in the condition of satisfying the PDM dynamic data validation requirements, the checking hash value based on checking algorithm is compressed to realize the lightweight integrity checking. In the end, the security of the scheme is proved, and the experiment shows that this method is efficient and feasible through performance analysis.

Enterprise private cloud PDM Data integrity Check Cuckoo filter

2015-09-19。航空科學基金(2013ZG54032)。叢麗暉，副教授，主研領域：數據庫理論與技術。何國強，碩士生。夏秀峰，教授。

TP311.52

A

10.3969/j.issn.1000-386x.2017.02.021