叢麗暉 何國強(qiáng) 夏秀峰,2

1(沈陽航空航天大學(xué)計算機(jī)學(xué)院 遼寧 沈陽 110136)2(沈陽航空航天大學(xué)遼寧省通用航空重點(diǎn)實(shí)驗(yàn)室 遼寧 沈陽 110136)

PDM中基于cuckoo filter的數(shù)據(jù)完整性校驗(yàn)算法設(shè)計與實(shí)現(xiàn)

叢麗暉1何國強(qiáng)1夏秀峰1,2

1(沈陽航空航天大學(xué)計算機(jī)學(xué)院 遼寧 沈陽 110136)2(沈陽航空航天大學(xué)遼寧省通用航空重點(diǎn)實(shí)驗(yàn)室 遼寧 沈陽 110136)

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

企業(yè)私有云 PDM 數(shù)據(jù)完整性 校驗(yàn) cuckoo filter

0 引 言

目前PDM系統(tǒng)仍采用集中式的存儲方式，但隨著制造企業(yè)數(shù)據(jù)量的快速增長，傳統(tǒng)集中式的存儲方式嚴(yán)重制約了PDM系統(tǒng)的整體性能。因此構(gòu)建企業(yè)私有云環(huán)境下的PDM文件系統(tǒng)，為PDM提供更高效率文件存儲服務(wù)。

存儲在私有云環(huán)境中的PDM數(shù)據(jù)，并非安全可靠的，由于受人為誤操作、存儲介質(zhì)損壞、磁盤讀寫錯誤、自然災(zāi)害等多種因素導(dǎo)致重要數(shù)據(jù)的丟失，將會給企業(yè)帶來無法彌補(bǔ)的損失，維護(hù)數(shù)據(jù)完整性變得至關(guān)重要。

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

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

1 完整性校驗(yàn)?zāi)Ｐ?/h2>

企業(yè)私有云存儲校驗(yàn)?zāi)Ｐ陀?個實(shí)體組成：用戶、云存儲服務(wù)器CSS和第三方驗(yàn)證者TPA，如圖1所示。其中用戶上傳數(shù)據(jù)文件到云服務(wù)器，云服務(wù)器管理用戶的數(shù)據(jù)文件，分配存儲空間和計算資源。為了確保遠(yuǎn)程存儲數(shù)據(jù)的完整性，通過第三方驗(yàn)證者對云服務(wù)器發(fā)送挑戰(zhàn)請求，協(xié)助用戶完成數(shù)據(jù)的驗(yàn)證。

圖1 校驗(yàn)?zāi)Ｐ?/p>

在數(shù)據(jù)存儲周期內(nèi)，客戶端根據(jù)數(shù)據(jù)的實(shí)際情況，與云服務(wù)器達(dá)成周期內(nèi)的數(shù)據(jù)校驗(yàn)次數(shù)。一次校驗(yàn)過程如下：TPA生成和發(fā)送一個挑戰(zhàn)到CSS，CSS根據(jù)接收到的挑戰(zhàn)，利用算法生成存儲數(shù)據(jù)的相應(yīng)證據(jù)返回給TPA。TPA再結(jié)合存儲的校驗(yàn)元信息判斷云服務(wù)器是否完好保存數(shù)據(jù)。

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

2 相關(guān)知識與設(shè)計目標(biāo)

2.1 cuckoo filter

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

圖2 cuckoo filter操作示意圖

通過如下公式計算關(guān)鍵字的兩個候選bucket：

k1=HASH(key)

(1)

k2=k1⊕HASH(tag)

(2)

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

k’=k⊕HASH(tag)

(3)

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

2.2 數(shù)據(jù)完整性校驗(yàn)要求

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

定義1 校驗(yàn)標(biāo)簽。校驗(yàn)標(biāo)簽是指針對文件F的每個數(shù)據(jù)塊fi，i∈[1，n]。在校驗(yàn)初始化時，生成的相關(guān)元信息Tfi。

分塊的校驗(yàn)標(biāo)簽?zāi)軌蚴剐ｒ?yàn)的粒度細(xì)化到數(shù)據(jù)塊級的范圍，有助于數(shù)據(jù)的恢復(fù)。并且多個數(shù)據(jù)塊可能存儲在多個服務(wù)器中，所以分塊的校驗(yàn)標(biāo)簽?zāi)芴岣卟l(fā)性。

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

對云存儲中數(shù)據(jù)完整性校驗(yàn)的方案而言，校驗(yàn)力度H的值越高，可認(rèn)為所校驗(yàn)的數(shù)據(jù)塊的完整性驗(yàn)證結(jié)果越可靠。

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

校驗(yàn)過程中，如果p不小于某個閾值時，即認(rèn)為所校驗(yàn)數(shù)據(jù)塊的結(jié)果認(rèn)為是可靠的。

在企業(yè)私有云環(huán)境下，為了實(shí)現(xiàn)PDM文件生命周期內(nèi)輕量級的完整性校驗(yàn)，本文方案擬實(shí)現(xiàn)以下四個要求:

(1) 針對動態(tài)數(shù)據(jù)的低校驗(yàn)開銷。PDM數(shù)據(jù)文件在其存儲周期內(nèi)進(jìn)行增加、修改、刪除等頻繁操作，使得已生成的校驗(yàn)標(biāo)簽失效，而重新生成和更新校驗(yàn)標(biāo)簽會增加計算開銷和傳輸負(fù)擔(dān)。因此，生成的校驗(yàn)標(biāo)簽?zāi)軡M足數(shù)據(jù)塊生命周期內(nèi)校驗(yàn)次數(shù)需求即可。

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

(3) 公開審計。通過TPA去驗(yàn)證云數(shù)據(jù)的正確性，不給用戶帶來額外的負(fù)擔(dān)。

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

3 基于cuckoo filter的數(shù)據(jù)完整性校驗(yàn)方法

3.1 校驗(yàn)標(biāo)簽的生成和更新

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

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

(4)

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

(5)

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

(6)

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

3.2 校驗(yàn)算法描述

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

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

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

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

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

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

3.3 算法分析

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

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

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

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

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

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

(7)

假定基于cuckoofilter的校驗(yàn)標(biāo)簽的可驗(yàn)證度為P′，則有:

P′=P×(1-f)

即:

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

(8)

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

4 實(shí)驗(yàn)與性能分析

4.1 存儲開銷

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

4.2 計算開銷

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

實(shí)驗(yàn)1 校驗(yàn)初始化和校驗(yàn)標(biāo)簽生成的計算開銷

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

圖3 校驗(yàn)初始化和校驗(yàn)標(biāo)簽生成計算開銷對比

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

實(shí)驗(yàn)2 完整性校驗(yàn)過程的計算開銷

對于同一個文件F，選擇不同的數(shù)據(jù)塊大小對完整性校驗(yàn)計算實(shí)驗(yàn)開銷。實(shí)驗(yàn)過程中為以60%的校驗(yàn)力度隨機(jī)抽取數(shù)據(jù)塊，記錄每次所花費(fèi)時間，實(shí)驗(yàn)結(jié)果如下：

圖4 校驗(yàn)信息生成時間對比

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

圖5 數(shù)據(jù)完整性校驗(yàn)時間對比

在數(shù)據(jù)完整性校驗(yàn)階段，由圖5表明兩種方案計算開銷都比較穩(wěn)定，結(jié)果顯示符合預(yù)期目標(biāo)，但本文算法只需查找對應(yīng)校驗(yàn)標(biāo)簽中校驗(yàn)值，其查找過程的時間趨近于零。

5 結(jié) 語

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

[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] 周銳, 王曉明. 基于同態(tài)哈希函數(shù)的云數(shù)據(jù)完整性驗(yàn)證算法[J]. 計算機(jī)工程, 2014, 40(6): 64-69.

[4] 陳蘭香. 一種基于同態(tài)Hash的數(shù)據(jù)持有性證明方法[J]. 電子與信息學(xué)報, 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] 肖達(dá), 舒繼武, 陳康, 等. 一個網(wǎng)絡(luò)歸檔存儲中實(shí)用的數(shù)據(jù)持有性檢查方案[J]. 計算機(jī)研究與發(fā)展, 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。航空科學(xué)基金(2013ZG54032)。叢麗暉，副教授，主研領(lǐng)域：數(shù)據(jù)庫理論與技術(shù)。何國強(qiáng)，碩士生。夏秀峰，教授。

TP311.52

A

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