基于Reed-Solomon編碼的抗邊信道攻擊云數(shù)據(jù)安全去重方法

劉小梅, 唐 鑫, 楊舒婷, 陳 雄, 高語(yǔ)燦

國(guó)際關(guān)系學(xué)院網(wǎng)絡(luò)空間安全學(xué)院 北京 中國(guó) 100091

1 引言

隨著大數(shù)據(jù)時(shí)代的到來(lái), 用戶使用各式終端在互聯(lián)網(wǎng)上產(chǎn)生了海量、高冗余的數(shù)據(jù)。云存儲(chǔ)的出現(xiàn), 為這些數(shù)據(jù)的高效存放提供了一種有效的解決方案。然而, 大量冗余重復(fù)的數(shù)據(jù)為云服務(wù)商帶來(lái)了沉重的存儲(chǔ)和管理開(kāi)銷。據(jù)統(tǒng)計(jì), 當(dāng)前在云端保存的數(shù)據(jù)重復(fù)率高達(dá)60%左右[1]。為了將這些數(shù)據(jù)上傳到云端, 用戶也需要付出巨大的冗余通信開(kāi)銷。

跨用戶數(shù)據(jù)去重技術(shù)[2]是解決以上問(wèn)題的有效手段。在跨用戶數(shù)據(jù)去重技術(shù)中, 用戶僅需上傳云端不存在的副本, 以提高通信、存儲(chǔ)效率。具體地, 當(dāng)用戶上傳文件時(shí), 首先生成文件的哈希值[3]作為去重請(qǐng)求發(fā)送給云服務(wù)商。后者在接收到用戶請(qǐng)求后,檢查所請(qǐng)求文件副本是否在云端存在。如果云端已保存該文件副本, 則會(huì)向用戶端返回一個(gè)存在性響應(yīng)來(lái)指示文件的存在, 并在云端文件副本中添加該用戶的所有權(quán)信息。用戶將不再需要上傳文件。如果云端尚未保存該文件副本, 此時(shí)云服務(wù)商將通過(guò)響應(yīng)要求用戶上傳整個(gè)文件?？紤]到數(shù)據(jù)去重的粒度, 跨用戶去重可分為塊級(jí)去重和文件級(jí)去重。其中,前者目前的應(yīng)用較為普遍。在這個(gè)技術(shù)實(shí)施過(guò)程中,用戶將文件劃分固定大小或可變大小的塊, 上傳塊的哈希值給云服務(wù)商以確定塊存在性。相較于文件級(jí)去重, 這種方式可以進(jìn)一步提高去重效率。

盡管跨用戶數(shù)據(jù)去重技術(shù)可以有效地節(jié)約存儲(chǔ)空間和提高帶寬利用率, 然而, 該技術(shù)返回的確定性響應(yīng)為攻擊者提供了一個(gè)邊信道。后者可以通過(guò)發(fā)起邊信道攻擊[3], 觀察云端響應(yīng)來(lái)判斷所請(qǐng)求數(shù)據(jù)在云端的存在性。具體地, 攻擊者可以通過(guò)猜測(cè)目標(biāo)數(shù)據(jù)的內(nèi)容, 并向云端發(fā)起去重請(qǐng)求。如果云服務(wù)商不要求進(jìn)一步上傳數(shù)據(jù), 攻擊者即可知道所猜測(cè)的數(shù)據(jù)在云端存在, 存在性隱私暴露。這種隱私竊取的方法在現(xiàn)實(shí)場(chǎng)景中普遍可行。在真實(shí)攻擊案例中,攻擊者可能為了非法獲取目標(biāo)對(duì)象的薪資信息, 生成帶有已知目標(biāo)對(duì)象姓名、猜測(cè)工資金額的數(shù)據(jù), 以向云端發(fā)送去重請(qǐng)求的方式, 確定所請(qǐng)求文件的存在性, 以此判斷目標(biāo)對(duì)象的薪資情況。為了提高文件命中率, 攻擊者可更近一步的以字典攻擊等方式生成多個(gè)可能的數(shù)據(jù)文件, 重復(fù)向云端發(fā)送重復(fù)數(shù)據(jù)檢查請(qǐng)求, 以達(dá)到目的。

為了解決邊信道攻擊問(wèn)題, 當(dāng)前, 國(guó)內(nèi)外已開(kāi)展了大量的研究工作。一類方法是云服務(wù)商通過(guò)設(shè)置去重響應(yīng)閾值[4-6]的方式限制攻擊者獲取存在性隱私。當(dāng)用戶請(qǐng)求去重的數(shù)據(jù)在云端的副本數(shù)未達(dá)到閾值時(shí), 云服務(wù)商要求用戶上傳數(shù)據(jù), 從而使得攻擊者無(wú)法探查到數(shù)據(jù)存在性情況; 反之, 當(dāng)用戶請(qǐng)求去重的數(shù)據(jù)在云端的副本數(shù)量達(dá)到閾值時(shí), 云服務(wù)商返回存在性響應(yīng)阻斷數(shù)據(jù)的進(jìn)一步上傳。此時(shí), 即使攻擊者獲知數(shù)據(jù)的存在也不會(huì)產(chǎn)生危害, 因?yàn)閿?shù)據(jù)已經(jīng)在云端成為流行數(shù)據(jù)。該類方法雖然在一定程度上可以實(shí)現(xiàn)數(shù)據(jù)存在性隱私保護(hù), 但是在云端副本數(shù)量未達(dá)到閾值時(shí), 仍要求用戶上傳大量冗余數(shù)據(jù)。一方面給云服務(wù)商帶來(lái)了大量的存儲(chǔ)開(kāi)銷, 另一方面也使得用戶需付出額外的通信開(kāi)銷。另一類方法是采用混淆策略[7-11]來(lái)混淆攻擊者。該類方法的基本思路為: 將文件分為若干塊, 假定用戶姓名、證件號(hào)等敏感信息存在于其中一個(gè)或多個(gè)塊中。對(duì)云服務(wù)商來(lái)說(shuō), 無(wú)論敏感信息是否在云端存在, 其需要對(duì)請(qǐng)求者生成一個(gè)混淆的響應(yīng), 使得后者無(wú)法通過(guò)去重響應(yīng)區(qū)分存在性狀態(tài)。然而在真實(shí)場(chǎng)景中, 云服務(wù)商難以辨別敏感塊的位置, 在敏感塊命中的情況下, 仍然會(huì)出現(xiàn)隱私泄露的風(fēng)險(xiǎn)。盡管后續(xù)研究者們提出一些改進(jìn)方法, 但這些方法仍然存在缺陷, 難以實(shí)現(xiàn)完全混淆。近年來(lái),有研究者提出廣義去重方法[12-13], 并隨之發(fā)展出一套安全去重框架。在該框架下, 原始數(shù)據(jù)被分解為基和偏移量。為了實(shí)現(xiàn)混淆, 只對(duì)基進(jìn)行跨用戶去重, 對(duì)偏移量開(kāi)展云端去重。由于相似的數(shù)據(jù)可以一定概率提取出相同的基, 因此, 攻擊者無(wú)法根據(jù)基的去重響應(yīng)判斷目標(biāo)數(shù)據(jù)的云端存在性, 邊信道攻擊可被有效抵抗。然而, 如何以較高概率從相似數(shù)據(jù)提取出相同的基, 并且進(jìn)一步降低偏移量上傳的通信開(kāi)銷, 是該方法現(xiàn)階段面臨的重要挑戰(zhàn)。

針對(duì)以上問(wèn)題, 本文提出了一種基于Reed-Solomon編碼的跨用戶安全去重方法。具體地, 該方法采用基于廣義去重的新型跨用戶安全去重框架, 在基處理中引入Reed-Solomon糾刪碼編碼思想, 以較高概率從相似的數(shù)據(jù)中提取出相同的基, 從而提高去重效率。除此之外, 本文對(duì)偏移量引入字典壓縮算法以進(jìn)一步降低通信開(kāi)銷。具體的, 本文的主要貢獻(xiàn)如下:

(1) 本文提出了一種新型的基于Reed-Solomon糾刪碼的跨用戶安全去重框架。將原始數(shù)據(jù)從字節(jié)層面分解為基和偏移量, 對(duì)基進(jìn)行跨用戶去重, 對(duì)偏移量開(kāi)展云端去重。特別地, 該框架支持基于Reed-Solomon糾刪碼的基提取方案, 以及偏移量字典壓縮方法。在所提框架下, 數(shù)據(jù)存在性和去重響應(yīng)之間的確定性聯(lián)系被打破, 去重效率可得到有效提升。

(2) 本文設(shè)計(jì)了一種通用的基提取方法和偏移量壓縮算法。相較于目前主流算法對(duì)相似文件去重效率不高的問(wèn)題, 所提方法利用Reed-Solomon糾刪碼編碼思想, 提升了所提取基的泛化能力。此外, 針對(duì)偏移量上傳的開(kāi)銷問(wèn)題, 本文將數(shù)據(jù)壓縮算法引入偏移量計(jì)算中,在上傳前對(duì)偏移量進(jìn)行壓縮, 進(jìn)一步提高了通信開(kāi)銷。

(3) 最后, 本文對(duì)所提方法開(kāi)展了安全性分析和性能驗(yàn)證。通過(guò)在真實(shí)數(shù)據(jù)集中與當(dāng)前該領(lǐng)域的最新工作進(jìn)行對(duì)比, 驗(yàn)證了: 1)本文所提出的方法能夠有效抵抗邊信道攻擊, 防止存在性隱私泄露; 2)本文所提出的基提取方法可以較高概率從相似文件中提取出相同的基, 降低云端存儲(chǔ)開(kāi)銷; 3)本文所引入的偏移量壓縮方法可以有效降低通信開(kāi)銷。

接下來(lái), 我們將在第二節(jié)介紹云數(shù)據(jù)去重方面的相關(guān)工作, 并在第三節(jié)介紹系統(tǒng)模型與威脅模型等準(zhǔn)備工作, 本文所提出的方法及相應(yīng)的實(shí)驗(yàn)驗(yàn)證將在第四節(jié)和第五節(jié)展開(kāi)介紹, 最后將在第六節(jié)進(jìn)行總結(jié)和展望。

2 相關(guān)工作

2.1 數(shù)據(jù)去重方法及邊信道攻擊

云數(shù)據(jù)去重技術(shù)是解決冗余數(shù)據(jù)存儲(chǔ)的一種有效手段, 去重技術(shù)的效率受去重發(fā)生的位置以及數(shù)據(jù)處理單元大小等因素的影響。數(shù)據(jù)去重技術(shù)按照數(shù)據(jù)處理單元大小可以分為文件級(jí)數(shù)據(jù)去重和塊級(jí)數(shù)據(jù)去重。文件級(jí)數(shù)據(jù)去重是早期流行的一種服務(wù)類型, 其中每個(gè)文件只存儲(chǔ)一個(gè)副本。如果兩個(gè)或多個(gè)文件具有相同的哈希值, 則認(rèn)為它們是相同的[13],這種方法實(shí)現(xiàn)簡(jiǎn)單, 但去重粒度較粗, 性能較差。塊級(jí)數(shù)據(jù)去重[14]是指系統(tǒng)將文件分割成固定大小的塊或者可變大小的塊進(jìn)行操作, 每個(gè)塊只存儲(chǔ)一個(gè)副本。相比較于文件級(jí)數(shù)據(jù)去重, 塊級(jí)數(shù)據(jù)去重的粒度更新, 所以能夠?qū)崿F(xiàn)更好的去重效率。

為了提高云端數(shù)據(jù)的存儲(chǔ)效率, 云服務(wù)商往往會(huì)在云端進(jìn)行數(shù)據(jù)去重工作, 我們稱之為云端數(shù)據(jù)去重[15]。這種方法讓用戶無(wú)法察覺(jué)到數(shù)據(jù)去重的發(fā)生。云端數(shù)據(jù)去重提高了云端數(shù)據(jù)存儲(chǔ)的空間利用率, 但是不能節(jié)省帶寬, 用戶仍需要將所有數(shù)據(jù)上傳至云端。除此之外, 不僅同一用戶需要向云端上傳相同數(shù)據(jù)的多個(gè)副本, 不同用戶存儲(chǔ)的數(shù)據(jù)副本之間也可能存在冗余?？缬脩羧ブ豙16]是解決這些問(wèn)題的有效手段。具體地, 在上傳前, 用戶首先向云端發(fā)送數(shù)據(jù)去重請(qǐng)求, 例如將目標(biāo)數(shù)據(jù)的哈希值發(fā)送給云服務(wù)商。若數(shù)據(jù)已在云端存在, 則用戶無(wú)需進(jìn)一步上傳。反之, 若數(shù)據(jù)在云端不存在, 則要求用戶上傳數(shù)據(jù)。由此, 重復(fù)數(shù)據(jù)不用再通過(guò)網(wǎng)絡(luò)傳輸, 從而達(dá)到提高存儲(chǔ)和通信效率的目的。目前, 該類方法被廣泛應(yīng)用于云存儲(chǔ)服務(wù)中。然而, 跨用戶去重技術(shù)面臨邊信道攻擊的風(fēng)險(xiǎn)。邊信道攻擊區(qū)別于其他網(wǎng)絡(luò)安全威脅, 其不依賴于硬件設(shè)備和軟件環(huán)境, 主要通過(guò)與系統(tǒng)、服務(wù)交互, 觀察系統(tǒng)、服務(wù)的響應(yīng)來(lái)推測(cè)系統(tǒng)、服務(wù)內(nèi)部的敏感信息存在性, 這種攻擊方式有效性高于數(shù)學(xué)分析、暴力破解等傳統(tǒng)攻擊方式。在跨用戶去重技術(shù)中, 攻擊者可以利用數(shù)據(jù)確認(rèn)機(jī)制, 通過(guò)發(fā)起字典攻擊、附加塊攻擊等方式確認(rèn)特定文件或目標(biāo)塊的存在性, 從而導(dǎo)致隱私的泄漏[17]。除此之外, 云存儲(chǔ)中邊信道也可用于隱蔽通信[4], 被攻擊者操縱的云服務(wù)商通過(guò)與用戶端按照正常協(xié)議的交互, 可將秘密信息編碼傳輸出去。

2.2 抗邊信道攻擊的跨用戶去重方法

在跨用戶去重技術(shù)中, 云服務(wù)商針對(duì)特定去重請(qǐng)求返回的確定性響應(yīng)為攻擊者提供了一個(gè)邊信道。因此, 研究者們針對(duì)如何替代確定性響應(yīng), 混淆攻擊者上開(kāi)展了一系列的研究。Harnik等人[4]首先提出了一種基于門(mén)限去重的抗邊信道攻擊安全去重方法,由云服務(wù)商為每個(gè)目標(biāo)文件隨機(jī)設(shè)定一個(gè)去重閾值。去重閾值的定義為觸發(fā)數(shù)據(jù)去重所需的數(shù)據(jù)副本數(shù)。在云端副本數(shù)量未達(dá)到閾值時(shí), 云服務(wù)商不返回?cái)?shù)據(jù)存在性響應(yīng)。因此攻擊者在收到要求上傳數(shù)據(jù)的響應(yīng)時(shí), 無(wú)法確定對(duì)應(yīng)的目標(biāo)文件不存在還是未達(dá)到去重閾值。當(dāng)云端副本數(shù)量達(dá)到閾值時(shí), 由于目標(biāo)文件在云端已經(jīng)成為流行, 故不存在隱私泄露的風(fēng)險(xiǎn)。該方法的要點(diǎn)在于閾值的確定, 在上述方法中,閾值在指定范圍內(nèi)被預(yù)先分配。Lee等人[5]提出每次通過(guò)隨機(jī)指定閾值以提高抗統(tǒng)計(jì)攻擊的能力。除此之外, 也有研究者提出使用更為復(fù)雜的數(shù)學(xué)方法來(lái)設(shè)置閾值。Wang等人[6]通過(guò)模擬攻擊者與云端的博弈, 以數(shù)學(xué)建模的方式生成更符合真實(shí)場(chǎng)景的閾值。然而, 該類方法雖然在一定程度上可以實(shí)現(xiàn)數(shù)據(jù)存在性隱私保護(hù), 但是攻擊者很容易通過(guò)學(xué)習(xí), 破解閾值設(shè)置原理, 甚至變換博弈策略導(dǎo)致建模結(jié)果偏離真實(shí)性, 從而繼續(xù)發(fā)起邊信道攻擊。此外, 云端副本數(shù)量未達(dá)到閾值時(shí), 用戶仍需上傳大量冗余數(shù)據(jù),這給用戶也帶來(lái)了額外的開(kāi)銷。

另一類抗邊信道攻擊的重復(fù)數(shù)據(jù)刪除方法是采用混淆策略影響攻擊者判斷, 該類方法的基本思路為: 將文件分為若干塊, 對(duì)塊級(jí)去重請(qǐng)求的響應(yīng)中加入混淆, 使得攻擊者很難從返回值中竊取目標(biāo)塊的存在性隱私。Zuo等人[7]提出了一種塊級(jí)數(shù)據(jù)去重方法RRCS, 該方案假設(shè)目標(biāo)文件的所有敏感信息均存儲(chǔ)在一個(gè)數(shù)據(jù)塊中, 其余塊為公開(kāi)塊。當(dāng)云端判斷出所檢測(cè)文件的真實(shí)存在性后, 在命中文件和未命中文件的響應(yīng)中分別添加不同數(shù)量的冗余塊, 使兩種情況下要求檢測(cè)者上傳的數(shù)據(jù)塊數(shù)量一樣, 從而確保檢測(cè)者無(wú)法判斷所檢測(cè)文件中敏感信息塊的真實(shí)存在性。然而, RRCS仍然無(wú)法抵抗附加塊攻擊, 并且當(dāng)云端要求用戶上傳的文件塊里不包含敏感塊時(shí),存在性隱私仍然將暴露。在此基礎(chǔ)上, Tang等人[8]無(wú)論敏感塊是否存在, 均要求請(qǐng)求者上傳所請(qǐng)求的所有塊的異或值, 實(shí)現(xiàn)了響應(yīng)的無(wú)差異性。當(dāng)敏感塊未命中時(shí), 云服務(wù)商可結(jié)合已知的公開(kāi)塊和接收到的異或值, 恢復(fù)出敏感塊內(nèi)容。當(dāng)敏感塊存在時(shí), 要求用戶上傳的異或值作為實(shí)現(xiàn)混淆的冗余信息, 而開(kāi)銷僅相當(dāng)于一個(gè)塊的大小。此外, 他們提出了一種請(qǐng)求合并策略以應(yīng)對(duì)附加塊攻擊。然而, 該方法仍然假定敏感信息存在于一個(gè)塊中, 這與實(shí)際情況往往不一致。隨后, Yu等人[9]提出了一種數(shù)據(jù)塊對(duì)(即兩個(gè)相鄰數(shù)據(jù)塊)去重檢測(cè)方法ZEUS。該方法同時(shí)檢測(cè)一個(gè)數(shù)據(jù)塊對(duì)的存在性, 并根據(jù)檢測(cè)結(jié)果生成模糊化的去重響應(yīng)。該方法可確保攻擊者無(wú)法竊取目標(biāo)塊的存在性隱私, 但需要云服務(wù)方維護(hù)一個(gè)獨(dú)立的數(shù)據(jù)結(jié)構(gòu)以記錄所有用戶檢測(cè)過(guò)卻未上傳的數(shù)據(jù)塊,加大了云端的存儲(chǔ)和計(jì)算開(kāi)銷。此外, 該方案無(wú)法嚴(yán)格保護(hù)云端目標(biāo)文件的不存在性隱私。攻擊者一旦接收到云服務(wù)商發(fā)送的要求用戶上傳兩個(gè)完整的數(shù)據(jù)塊的去重響應(yīng), 則可以推斷出這兩個(gè)數(shù)據(jù)塊均為未命中塊。隨后, Pooranian等人[10]在此基礎(chǔ)上改進(jìn), 進(jìn)一步提高了云端數(shù)據(jù)存在性隱私的安全性。然而, 他們的工作面臨更大的開(kāi)銷。Vestergaard等人[11]中提出了一種新的基于編碼策略的跨用戶去重方案 CIDER,在CIDER中, 用戶能夠一次檢查兩個(gè)及以上的數(shù)據(jù)塊, 為實(shí)現(xiàn)混淆引入的通信開(kāi)銷最多僅為一個(gè)塊的長(zhǎng)度。然而, 這類方案仍然存在安全問(wèn)題。在攻擊者已知去重請(qǐng)求中未命中塊數(shù)的情況下, 若云服務(wù)商返回響應(yīng)中要求上傳的數(shù)據(jù)塊數(shù)量等于未命中塊數(shù), 則請(qǐng)求中其余目標(biāo)塊的存在性隱私仍將暴露。

近年來(lái), 有研究者提出廣義數(shù)據(jù)去重方法, 將原始數(shù)據(jù)分解為基和偏移量。Vestergaard等人在文獻(xiàn)[12]中成功驗(yàn)證, 可以從一組傳感器收集的時(shí)間序列數(shù)據(jù)的相鄰值中提取相同的基, 并將此成果應(yīng)用于數(shù)據(jù)壓縮領(lǐng)域?；谶@個(gè)工作, 文獻(xiàn)[13]首次提出一種基于廣義去重的安全去重框架SRGD, 在該框架中對(duì)目標(biāo)數(shù)據(jù)的基開(kāi)展跨用戶去重, 對(duì)偏移量開(kāi)展云端去重, 使得攻擊者不再可以從去重響應(yīng)中推斷出完整數(shù)據(jù)的存在性隱私, 從而徹底解決邊信道攻擊問(wèn)題。然而, 該方法在基的提取中, 使用了重復(fù)數(shù)據(jù)刪除、基于內(nèi)容的分塊方法等策略, 雖然提高了基的泛化能力, 但在客戶端消耗了較多的計(jì)算開(kāi)銷。除此之外, 該方法對(duì)于偏移量因采用云端去重, 上傳了大量冗余的偏移量數(shù)據(jù), 降低了客戶端的通信效率。因此, 在廣義去重方法中, 如何在保證數(shù)據(jù)安全的前提下, 設(shè)計(jì)一個(gè)泛化能力強(qiáng)且計(jì)算復(fù)雜度低的基提取算法, 并降低偏移量的通信開(kāi)銷仍是一個(gè)重要的挑戰(zhàn)。

3 準(zhǔn)備工作

本節(jié)將介紹本文所提出方法對(duì)應(yīng)的系統(tǒng)模型,并通過(guò)定義威脅模型來(lái)分析安全風(fēng)險(xiǎn)。此外, 本節(jié)也將介紹引入的Reed-Solomon糾刪碼編碼技術(shù)。

3.1 系統(tǒng)模型

在本文所提模型應(yīng)用的數(shù)據(jù)托管場(chǎng)景中, 涉及到用戶和云服務(wù)商兩個(gè)實(shí)體。在這個(gè)場(chǎng)景中, 云服務(wù)商需向用戶提供數(shù)據(jù)上傳及下載服務(wù), 承擔(dān)數(shù)據(jù)維護(hù)和安全保障服務(wù)。用戶需向云服務(wù)商支付數(shù)據(jù)保管費(fèi)用和承擔(dān)數(shù)據(jù)泄漏風(fēng)險(xiǎn)。因此, 對(duì)于云服務(wù)商來(lái)說(shuō), 首先需要具備充足的存儲(chǔ)空間, 滿足一定規(guī)模的用戶數(shù)據(jù)存儲(chǔ)需求。除此之外, 云服務(wù)商還應(yīng)具備較強(qiáng)的計(jì)算能力, 支持冗余數(shù)據(jù)管理、重復(fù)數(shù)據(jù)刪除和數(shù)據(jù)完整下載功能。最重要的是, 具備完善的數(shù)據(jù)安全保管方案, 保障用戶的數(shù)據(jù)完整性和敏感數(shù)據(jù)的隱私不被竊取和泄漏。

我們考慮數(shù)據(jù)上傳的整個(gè)流程。在一次完整的流程中, 請(qǐng)求上傳的用戶首先對(duì)數(shù)據(jù)進(jìn)行預(yù)處理,處理完后再向云端發(fā)起重復(fù)數(shù)據(jù)刪除請(qǐng)求。預(yù)處理的過(guò)程為: 首先對(duì)數(shù)據(jù)重新進(jìn)行ASCII碼編碼, 提取每個(gè)字節(jié)的基和計(jì)算恢復(fù)字節(jié)所需的偏移量, 并對(duì)基進(jìn)一步使用Reed-Solomon解碼生成標(biāo)準(zhǔn)基, 對(duì)標(biāo)準(zhǔn)基分組并計(jì)算每個(gè)塊的標(biāo)簽信息。然后將標(biāo)簽信息和所有偏移量數(shù)據(jù)上傳云端發(fā)起重復(fù)數(shù)據(jù)刪除請(qǐng)求。云服務(wù)商根據(jù)標(biāo)簽信息檢索數(shù)據(jù), 確定數(shù)據(jù)的存在性。如果某塊數(shù)據(jù)不存在, 則要求用戶端上傳對(duì)應(yīng)塊的標(biāo)準(zhǔn)基數(shù)據(jù), 在云端存儲(chǔ)數(shù)據(jù)副本且執(zhí)行云端數(shù)據(jù)去重工作, 并將用戶加入數(shù)據(jù)所有權(quán)列表中;如果某塊數(shù)據(jù)已存在, 則不再要求用戶上傳對(duì)應(yīng)塊基數(shù)據(jù), 隨后在云端進(jìn)行數(shù)據(jù)去重處理。在此場(chǎng)景中,即使數(shù)據(jù)副本已在云端保存, 用戶也需要上傳部分?jǐn)?shù)據(jù)。該模型通過(guò)分解數(shù)據(jù), 將數(shù)據(jù)去重工作分成兩部分, 分別在用戶端和云端進(jìn)行去重。

3.2 威脅模型

在本文考慮的場(chǎng)景中, 假設(shè)云服務(wù)商完全可靠,不考慮其竊取數(shù)據(jù)、丟失數(shù)據(jù)的可能, 并且能夠?yàn)橛脩籼峁┛煽康臄?shù)據(jù)存儲(chǔ)和去重服務(wù)。對(duì)于任意一個(gè)數(shù)據(jù)塊, 其威脅風(fēng)險(xiǎn)來(lái)源于試圖竊取其狀態(tài)和信息的外部攻擊者。對(duì)于攻擊者來(lái)說(shuō), 其通過(guò)使用邊信道攻擊試圖獲得該數(shù)據(jù)塊的存儲(chǔ)狀態(tài)。那么, 為了判斷該數(shù)據(jù)塊副本是否存在于云端, 攻擊者會(huì)發(fā)起去重請(qǐng)求, 隨后根據(jù)云端返回的去重響應(yīng)判斷該數(shù)據(jù)塊在云端存在或不存在。在傳統(tǒng)的跨用戶重復(fù)數(shù)據(jù)去重模型中, 對(duì)于具有固定模版格式的可預(yù)測(cè)文件,一旦攻擊者掌握部分文件內(nèi)容或文件模版規(guī)律, 極易通過(guò)字典攻擊猜測(cè)出剩余部分?jǐn)?shù)據(jù), 并通過(guò)去重響應(yīng)判斷其在云端的真實(shí)存在性。在這種場(chǎng)景下, 邊信道攻擊對(duì)云端數(shù)據(jù)的存在性隱私構(gòu)成了極大的安全威脅。

3.3 Reed-Solomon編碼

Reed-Solomon編碼(以下簡(jiǎn)稱RS編碼)[19]是定義在伽羅華域中的一種糾刪碼, 伽羅華域是RS編碼的重要理論基礎(chǔ)。在伽羅華域中, 代數(shù)運(yùn)算具有封閉性,即代數(shù)運(yùn)算的結(jié)果均在域內(nèi), 不存在數(shù)據(jù)溢出問(wèn)題,所以伽羅華域又稱為有限域[19]。在伽羅華域中加法等價(jià)于異或運(yùn)算, 乘法等價(jià)于邏輯與運(yùn)算, 負(fù)數(shù)與正數(shù)相同。二維碼是一種典型的RS編碼結(jié)果, 其使用GF(256)。在GF(256)域中包含0～255的數(shù)字, 如果計(jì)算結(jié)果超出這個(gè)范圍, 則繼續(xù)對(duì)計(jì)算結(jié)果進(jìn)行取模運(yùn)算, 直至結(jié)果在0～255范圍內(nèi)。為了減少代數(shù)計(jì)算量,GF(256)中執(zhí)行運(yùn)算所需要的生成值已生成保存, 使用中可直接在表中查詢, 無(wú)需反復(fù)計(jì)算。實(shí)驗(yàn)表明當(dāng)數(shù)據(jù)運(yùn)算量非常大時(shí), 查表的時(shí)間遠(yuǎn)遠(yuǎn)小于反復(fù)計(jì)算出值所用時(shí)間。

RS編碼會(huì)將需要編碼的流數(shù)據(jù)重新排列計(jì)算,其公式如下:

其中,k表示原始數(shù)據(jù)長(zhǎng)度,t表示糾錯(cuò)數(shù)據(jù)長(zhǎng)度,n表示RS編碼長(zhǎng)度且滿足n=k+t, 對(duì)于任意表示k個(gè)原始數(shù)據(jù)的數(shù)據(jù)值?,表示t個(gè)糾錯(cuò)數(shù)據(jù)的數(shù)據(jù)值。

RS編碼的過(guò)程包括消息多項(xiàng)式、生成多項(xiàng)式的構(gòu)造, 隨后利用兩個(gè)多項(xiàng)式計(jì)算糾錯(cuò)數(shù)據(jù)。解碼原理則相對(duì)簡(jiǎn)單, 根據(jù)編碼過(guò)程和矩陣運(yùn)算原理, 即可查找到出錯(cuò)位并恢復(fù)正確數(shù)值。接下來(lái)將詳細(xì)介紹RS編碼過(guò)程:

消息多項(xiàng)式: 消息多項(xiàng)式使用數(shù)據(jù)碼字作為系數(shù), 例如數(shù)據(jù): 00100000、01011011、00001011的十進(jìn)制值: 32、91、11, 那么其消息多項(xiàng)式為:

生成多項(xiàng)式: 生成多項(xiàng)式公式為:

使用GF(256),其中α取值為2, t表示糾錯(cuò)位數(shù)。

接下來(lái), 我們以t取2為例, 介紹生成多項(xiàng)式的計(jì)算過(guò)程:

1) 將變量系數(shù)轉(zhuǎn)為α表示, 查表可知α0=1, 故多項(xiàng)式可以寫(xiě)為

2) 展開(kāi)多項(xiàng)式, 并進(jìn)行系數(shù)合并

3) 在伽羅華域中, 負(fù)數(shù)等于正數(shù), 即減法等同于加法, 故

4) 查表可知α0=1,α1=2, 則

5) 再次查表可知α25=3, 用符號(hào)表示n取2時(shí)的生成多項(xiàng)式為

根據(jù)上述過(guò)程可知, 生成多項(xiàng)式與t的取值有關(guān),與原始數(shù)據(jù)碼字無(wú)關(guān)。

生成糾刪碼:從生成多項(xiàng)式最高項(xiàng)開(kāi)始重復(fù)操作, 首先對(duì)生成多項(xiàng)進(jìn)項(xiàng)乘法, 使其與消息多項(xiàng)式最高項(xiàng)系數(shù)相同, 然后消息多項(xiàng)式和變換后的生成多項(xiàng)式進(jìn)行異或運(yùn)算, 消去消息多項(xiàng)式最高項(xiàng)。重復(fù)多次, 結(jié)果完成后所剩余數(shù)項(xiàng)系數(shù)即為糾刪碼, 最后將生成的糾刪碼轉(zhuǎn)換為添加到原信息碼碼后面。

數(shù)據(jù)恢復(fù)過(guò)程: 根據(jù)編碼過(guò)程可知, 如果傳輸過(guò)程中不發(fā)生錯(cuò)誤, 則滿足RSx%gx=0 的要求,若余數(shù)不為0, 表明發(fā)生錯(cuò)誤。

其中,l表示可糾錯(cuò)的數(shù)據(jù)值個(gè)數(shù)且滿足t=2l,表示出錯(cuò)位置,表示原始正確數(shù)值。

4 基于Reed-Solomon碼的抗邊信道攻擊的云數(shù)據(jù)安全去重方法

4.1 算法框架

本文提出一種基于RS編碼的抗邊信道攻擊的云數(shù)據(jù)安全去重算法, 圖1所示為算法整體框架圖。假設(shè)文件F由其擁有者用戶X首次向云端請(qǐng)求上傳。在用戶端, 文件F的數(shù)據(jù)內(nèi)容首先轉(zhuǎn)為ASCII碼二進(jìn)制形式存儲(chǔ), 經(jīng)過(guò)基提取和偏移量計(jì)算算法處理后,文件F被分成c個(gè)塊即, F=C1,C2,C3,…,Cc, 每個(gè)塊由一組基和偏移量對(duì)組成, 即, C1=B1,D1,C2=B2,D2,…,Cc=Bc,Dc, 其中Bi,i∈1,c]表示塊Ci的基, Di,i∈1,c]表示塊Ci的偏移量?；崛『推屏坑?jì)算的過(guò)程如圖2所示, 我們將在4.2節(jié)基提取和偏移量計(jì)算中進(jìn)行介紹, 這里不再展開(kāi)介紹。隨后,我們計(jì)算B1,B2,B3,…,Bc的哈希結(jié)果tagB1,tagB2,tagB3,…,tagBc, 該哈希結(jié)果作為去重請(qǐng)求發(fā)送給云端。因文件F為首次上傳, 故云端收到哈希結(jié)果并檢查后, 發(fā)現(xiàn)云端不存在該數(shù)據(jù)備份。此時(shí), 云服務(wù)商要求用戶上傳全部數(shù)據(jù), 并在云端以數(shù)據(jù)塊形式存儲(chǔ)。假設(shè)用戶Y擁有一份與文件F數(shù)據(jù)內(nèi)容相似的文件F,其經(jīng)過(guò)算法處理后以F=C1,C2,C3,…,Cc的 形 式 存 儲(chǔ)。其 中, C1=B1,D1,C2=B2,D2,…,Cc=Bc,Dc。如上圖所示, 由于文件F和F內(nèi)容相似, 故兩個(gè)文件間存在數(shù)據(jù)內(nèi)容相同的文件塊, 圖1中具有相同顏色和花紋的塊代表相同的數(shù)據(jù)內(nèi)容, 因本方法所提基的泛化能力較強(qiáng), 可以從不同數(shù)據(jù)中提取出相同的基,故也存在數(shù)據(jù)塊中基相同, 而偏移量不同的情況。對(duì)文件F而言, 當(dāng)用戶Y生成基B1,B2,B3,…,Bc的哈希結(jié)果tagB1,tagB2,tagB3,…,tagBc并將其作為去重請(qǐng)求發(fā)送給云服務(wù)器時(shí), 云服務(wù)器不再要求其上傳與文件F相同的基塊并對(duì)重復(fù)部分添加F的引用, 但對(duì)于偏移量數(shù)據(jù)D1,D2,D3,…,Dc則被全部要求上傳。由上圖所示, B1和B1由于數(shù)據(jù)內(nèi)容相同故沒(méi)有上傳云端, 僅在存儲(chǔ)列表中追加D1。隨著文件F的上傳結(jié)束, 用戶端不再進(jìn)行操作, 云端將對(duì)偏移量數(shù)據(jù)進(jìn)行去重, 對(duì)相同的數(shù)據(jù)偏移量塊僅保留一個(gè)副本。如圖1所示, 數(shù)據(jù)偏移量塊D1和D1數(shù)據(jù)內(nèi)容相同, 故僅保留其中一個(gè)。云端去重完成后,文件F的上傳和去重流程結(jié)束。當(dāng)用戶請(qǐng)求下載文件F時(shí), 云端通過(guò)文件保存索引逐塊還原后將數(shù)據(jù)返回用戶。

圖1 算法框架Figure 1 The framework

4.2 基提取

本方法將字節(jié)分解為基和偏移量, 對(duì)基進(jìn)行用戶端去重, 對(duì)偏移量進(jìn)行云端去重。與基于塊的數(shù)據(jù)去重方法相比, 在數(shù)據(jù)塊重復(fù)的情況下, 增加了上傳偏移量的通信開(kāi)銷, 降低了數(shù)據(jù)哈希計(jì)算開(kāi)銷和通信開(kāi)銷。在保證抗邊信道攻擊的安全前提下, 本方法融合RS糾刪碼原理和數(shù)據(jù)壓縮方法, 設(shè)計(jì)了基提取和偏移量計(jì)算策略, 本小節(jié)首先介紹基提取策略。

假設(shè)文件F是由x1,x2,x3,…,xn,n個(gè)字節(jié)組成,對(duì)于每一個(gè)字節(jié)xi,i?n)都由基bi和偏移量di組成。其中, 基bi由4個(gè)比特組成, 偏移量di則由剩余的4個(gè)比特組成, 即文件F可以表示為:

F =b1,d1,b2,d2,b3,d3,…,bn,dn

我們用B來(lái)表示文件F的基集合,D代表文件F的偏移量集合, 即:

如圖2所示, 文件F的基集合B =0100,0110,0111,…,0010,…, 偏移量集合D =1101,0101,0011,…,0000,…。接下來(lái), 我們將按照基提取、數(shù)據(jù)分塊、偏移量壓縮的步驟, 對(duì)集合B和D分別進(jìn)行處理。

基于RS編碼的數(shù)據(jù)恢復(fù)原理, 假設(shè)集合B是可能出錯(cuò)的數(shù)據(jù)結(jié)果, 對(duì)其進(jìn)行數(shù)據(jù)恢復(fù)可以糾正出錯(cuò)位并將其還原為原始數(shù)值。那么, 對(duì)于B=b1,b2,b3,…,bn,其數(shù)據(jù)恢復(fù)的結(jié)果可表示為Brs=b1,b2correct,b3,…,bn, 其中b2correct是糾正后的正確數(shù)值。

根據(jù)第三節(jié)所介紹的RS數(shù)據(jù)編碼和數(shù)據(jù)恢復(fù)過(guò)程中, 需要事先約定編碼的長(zhǎng)度, 本文所使用的長(zhǎng)度為4, 即每4個(gè)基為一組。如圖2所示,{0100,0110,0111,0111}、{0110,0110,0110,0010}分別為一組基, 對(duì)其進(jìn)行數(shù)據(jù)恢復(fù)后, 第6個(gè)數(shù)值從0110轉(zhuǎn)為0000, 從而第二組基轉(zhuǎn)為{0110,0000,0110,0010}。此過(guò)程中, 可以看出相似文件可以提取出相同的基, 從而實(shí)現(xiàn)減少基的上傳,實(shí)現(xiàn)降低通信開(kāi)銷和存儲(chǔ)開(kāi)銷的目的。然而, 重復(fù)利用RS編碼原理進(jìn)行數(shù)據(jù)恢復(fù), 消耗了較多的計(jì)算開(kāi)銷, 且存在大量的重復(fù)計(jì)算。因此, 為了降低計(jì)算量,本方法預(yù)先建立了一個(gè)基數(shù)據(jù)多對(duì)一關(guān)系的索引字典, 該索引分別保存于云端和用戶端。在后續(xù)的數(shù)據(jù)上傳過(guò)程和下載時(shí), 僅需要查表代替重復(fù)計(jì)算, 索引構(gòu)建方法將在4.3節(jié)著重介紹。在索引構(gòu)建完成后,為每組基進(jìn)行編號(hào), 如上圖所示, 基{0100,0110,0111,0111}對(duì)應(yīng)序號(hào)為8, {0110,0000,0110,0010}對(duì)應(yīng)序號(hào)為976。

在重復(fù)數(shù)據(jù)刪除請(qǐng)求中, 我們需要對(duì)基集合進(jìn)行哈希計(jì)算, 然后以哈希結(jié)果上傳云端發(fā)起請(qǐng)求。為了避免過(guò)多的哈希計(jì)算次數(shù), 我們?cè)O(shè)計(jì)了一個(gè)簡(jiǎn)單直接的分塊方法, 選擇若干組基組成一個(gè)塊, 塊的長(zhǎng)度為固定值。由此, B=B1,B2,B3,…,Bc, 其中變量c表示分塊數(shù)量, 為了節(jié)約存儲(chǔ)空間, 每個(gè)塊中保存每組基的序號(hào)代替原始數(shù)值, 如圖2所示數(shù)據(jù)中,B1=8,976,472,…, 接下來(lái)計(jì)算每個(gè)塊的哈希值用以進(jìn)行跨用戶去重。這里, 我們用tagB表示計(jì)算后的哈希值集合:

tagB=tagB1,tagB2,tagB3,…,tagBc

4.3 偏移量計(jì)算

在上一節(jié)中, 本方法利用RS編碼糾刪原理, 提取基數(shù)據(jù)并通過(guò)多對(duì)一關(guān)系, 最大可能地從相似數(shù)據(jù)中提取出相同的基, 從而可以提高基數(shù)據(jù)的去重效率, 然而對(duì)偏移量數(shù)據(jù)進(jìn)行云端去重, 仍然消耗了較多的通信開(kāi)銷。在本算法中, 為了降低通信開(kāi)銷,我們引入數(shù)據(jù)壓縮算法。針對(duì)數(shù)據(jù)文件的規(guī)模和特點(diǎn), 選擇合適的壓縮算法可以極大的節(jié)約通信開(kāi)銷。在本方法中, 使用了ZSTD壓縮算法[21], 它是一種輕量級(jí)的字典壓縮算法, 尤其適用于小規(guī)模數(shù)據(jù)樣本,其壓縮效率在使用有效字典后可提升至80%左右,字典無(wú)效時(shí)壓縮率為50%左右。未來(lái), 可以利用機(jī)器學(xué)習(xí)算法, 引入效率更高、適應(yīng)性更好的壓縮手段。

4.2節(jié)中, 算法會(huì)對(duì)基數(shù)據(jù)進(jìn)行分組, 對(duì)應(yīng)的偏移量數(shù)據(jù)也分為若干塊, 在發(fā)起重復(fù)數(shù)據(jù)刪除請(qǐng)求之前, 先對(duì)每個(gè)偏移量塊內(nèi)數(shù)據(jù)進(jìn)行壓縮, 壓縮處理完成后其形式為:

如上圖2所示的壓縮過(guò)程中, 虛線部分表示不再存儲(chǔ)的數(shù)據(jù)。

如圖1所示, 我們處理后的哈希值集合tagB和偏移量集合D上傳云端, 云服務(wù)商在接收到它們后,將tagB與云端存儲(chǔ)的基副本標(biāo)簽進(jìn)行比較。根據(jù)第4.1節(jié)介紹的設(shè)計(jì)框架, 云端將對(duì)基執(zhí)行跨用戶數(shù)據(jù)去重, 對(duì)偏移量開(kāi)展云端去重。因此, 云端根據(jù)tagB檢索結(jié)果, 判斷是否需要用戶上傳基集合B中的未命中基塊, 同時(shí), 對(duì)偏移量集合D中的每個(gè)塊與云存儲(chǔ)中的偏移量數(shù)據(jù)開(kāi)展云端去重。在這個(gè)過(guò)程中, 如果文件F是首次上傳的全新文件, 則會(huì)在云端會(huì)建立一個(gè)新的數(shù)據(jù)存儲(chǔ)字典dicFB]=D,存儲(chǔ)基和偏移量。如果所請(qǐng)求的文件F中有一個(gè)數(shù)據(jù)塊與云存儲(chǔ)中的目標(biāo)文件F的標(biāo)簽重復(fù), 則認(rèn)為F與F為相似文件, 故滿足以下要求時(shí), 不再為F=C1,C2,C3,…,Cc重新建立字典, 而將數(shù)據(jù)直接索引在文件后。

4.4 索引構(gòu)建

本小節(jié)將介紹索引構(gòu)建方法, 基數(shù)據(jù)對(duì)應(yīng)關(guān)系的索引為了降低計(jì)算開(kāi)銷, 本方法利用RS糾刪碼思想預(yù)先構(gòu)建索引, 為每一組基構(gòu)建一對(duì)一和一對(duì)多的對(duì)應(yīng)關(guān)系, 可以實(shí)現(xiàn)以下作用:

(1) 避免大量的重復(fù)計(jì)算。云數(shù)據(jù)的每次上傳均需要對(duì)其進(jìn)行基的提取, 這個(gè)過(guò)程中需要大量的編碼運(yùn)算, 根據(jù)基數(shù)據(jù)的特點(diǎn)發(fā)現(xiàn), 該運(yùn)算過(guò)程存在較大重復(fù)計(jì)算, 通過(guò)索引結(jié)果, 可以將計(jì)算轉(zhuǎn)為查詢, 從而降低客戶端的計(jì)算開(kāi)銷。

(2) 預(yù)先處理特殊結(jié)果。對(duì)于一組基數(shù)據(jù), 本方法假設(shè)其是RS編碼后的結(jié)果進(jìn)行數(shù)據(jù)恢復(fù), 故存在一定概率的無(wú)解情況, 在索引構(gòu)建的過(guò)程中, 可提前定義無(wú)解情況, 避免客戶端中的無(wú)效計(jì)算。

本方法所考慮的數(shù)據(jù)為標(biāo)準(zhǔn)ASCII碼二進(jìn)制形式, 將字節(jié)轉(zhuǎn)為ASCII碼后對(duì)其補(bǔ)零, 而后后對(duì)8位‘01’串進(jìn)行劃分為高四位和低四位。對(duì)于高四位即為上文所指基, 第四位為偏移量。索引構(gòu)建主要構(gòu)建基之間的關(guān)系。

通過(guò)觀察ASCII碼編碼規(guī)則, 字節(jié)的高四位分別為0000、0001、0010、0011、0101、0100、0111、0110, 8種情況。0000和0001分別對(duì)應(yīng)使用頻率較低的控制字符和通信專用字符, 其余分別對(duì)應(yīng)常見(jiàn)的大寫(xiě)字母、小寫(xiě)字母、符號(hào)、數(shù)字等。

根據(jù)RS編碼和數(shù)據(jù)恢復(fù)原理, 在有限范圍內(nèi),一組數(shù)值出錯(cuò)后可以恢復(fù)回正確結(jié)果, 簡(jiǎn)單來(lái)說(shuō)則是, 正確數(shù)值序列和出錯(cuò)數(shù)值序列間存在對(duì)應(yīng)關(guān)系。利用這一原理, 即將多組數(shù)值序列對(duì)應(yīng)為一組數(shù)值序列, 即上文所述相似數(shù)據(jù)內(nèi)容可提取出相同的基。

因此, 我們預(yù)先計(jì)算出每組基之間的對(duì)應(yīng)關(guān)系,可避免每次文件上傳時(shí)的重復(fù)計(jì)算。這里我們選取RS編碼的長(zhǎng)度為4, 即每四個(gè)基為一組, 多個(gè)基組可以轉(zhuǎn)為一個(gè)相同的源, 從而進(jìn)一步提高基的泛化能力。

在索引構(gòu)建過(guò)程中, 首先計(jì)算出0000、0001、0010、0011、0101、0100、0111、0110, 這8種情況的所有排列組合結(jié)果, 而后利用數(shù)據(jù)恢復(fù)原理, 計(jì)算其源碼, 圖3展示了相關(guān)數(shù)據(jù)的存儲(chǔ)形式, 表示基源碼和原始數(shù)據(jù)的對(duì)應(yīng)結(jié)果。為了便于表述和理解,在圖3中, 我們以a,b,c,d,e,f表示{0010, 0011,0100, 0101, 0110, 0111}, 例如值為{0010001101000111}的基, 源碼值為{0010001101000101}編碼而來(lái)。同樣值為{0010001101000100}的基, 源碼值也為{0010 001101000101}。如此, 原本兩個(gè)不同的基{00100011 01000111}和{0010001101000100}轉(zhuǎn)為同一個(gè)源碼{0010001101000101}。將基通過(guò)所示表結(jié)構(gòu)轉(zhuǎn)為源碼后, 經(jīng)過(guò)測(cè)試, 存儲(chǔ)解碼前與解碼后基對(duì)應(yīng)關(guān)系所示表結(jié)構(gòu)所需存儲(chǔ)空間為184512B , 為了便于基提取和數(shù)據(jù)恢復(fù), 用戶端和云端均需維護(hù)這個(gè)表結(jié)構(gòu)數(shù)據(jù)。

圖3 數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)圖Figure 3 Data storage structure

5 實(shí)驗(yàn)驗(yàn)證及結(jié)果分析

為了驗(yàn)證本方法的安全性和性能, 我們選擇了兩個(gè)特點(diǎn)不同的真實(shí)數(shù)據(jù)集: Enron 電子郵件數(shù)據(jù)集[22]和 Sakila 樣本數(shù)據(jù)集[23]。其中, Enron電子郵件數(shù)據(jù)集包含517401個(gè)文件, 每個(gè)文件具有相同的模版,主要包含發(fā)件人、收件人、時(shí)間、郵件內(nèi)容等記錄。圖4展示了該數(shù)據(jù)集文件大小的分布狀況。從圖中可見(jiàn), 大部分文件規(guī)模較小。Sakila樣本數(shù)據(jù)集則是由16049條數(shù)據(jù)記錄組成, 是典型的數(shù)據(jù)庫(kù)類型數(shù)據(jù)集。其中, 每條記錄表示一筆支付數(shù)據(jù), 包括訂單時(shí)間、金額等信息。在這部分, 我們驗(yàn)證了所提方法的抗邊信道攻擊能力和去重效率。驗(yàn)證本方法的性能。具體地, 我們?cè)O(shè)計(jì)了如下三個(gè)實(shí)驗(yàn):

圖4 Enron郵件數(shù)據(jù)集文件大小分布圖Figure 4 Enron file size distribution

1)計(jì)算性能驗(yàn)證: 通過(guò)與SRGD[13]在相同文件提取基的計(jì)算開(kāi)銷和存儲(chǔ)開(kāi)銷, 驗(yàn)證本方法在邊信道攻擊下的安全性和高效性;

2)去重效率驗(yàn)證: 通過(guò)與其他三種最新的跨用戶數(shù)據(jù)去重方案 ZEUS[9]、RARE[10]和CIDER[11]在上傳相同文件時(shí)的通信開(kāi)銷和存儲(chǔ)開(kāi)銷, 驗(yàn)證本方法可以提高去重效率, 節(jié)約帶寬和存儲(chǔ)空間;

3)在本實(shí)驗(yàn)中, 本方法所使用的RS編碼長(zhǎng)度為4個(gè)基, 文件塊大小為200個(gè)基。在 ZEUS、RARE 和CIDER中, 文件被分成了固定長(zhǎng)度為128字節(jié)的文件塊, 并引入填充策略保證最后一個(gè)塊的長(zhǎng)度與其他文件塊保持一致。

5.1 計(jì)算性能驗(yàn)證

本方法提出一種字節(jié)級(jí)的數(shù)據(jù)去重框架, 對(duì)每一個(gè)字節(jié)提取基和偏移量, 對(duì)于基按照跨用戶去重方法進(jìn)行去重, 對(duì)于偏移量開(kāi)展云端去重。當(dāng)攻擊者對(duì)于某一數(shù)據(jù)塊發(fā)起邊信道攻擊時(shí), 假設(shè)云端的相應(yīng)基不存在, 那么不會(huì)發(fā)生數(shù)據(jù)存在性隱私的泄漏。假設(shè)云端對(duì)應(yīng)的基存在, 云服務(wù)商返回確定性響應(yīng)阻止用戶對(duì)基的上傳。即使如此, 攻擊者仍然無(wú)法判斷目標(biāo)數(shù)據(jù)的云端存在性。這歸結(jié)為本方法可以高概率從相似文件中提取出相同的基, 即使基數(shù)據(jù)不需要上傳, 偏移量也仍然需要上傳, 故攻擊者無(wú)法僅通過(guò)基的存在性判斷其多對(duì)應(yīng)字節(jié)數(shù)據(jù)的存在性。

在本實(shí)驗(yàn)中, 我們首先將對(duì)算法的安全性進(jìn)行實(shí)驗(yàn)驗(yàn)證。具體地, 我們?cè)贓nron郵件數(shù)據(jù)集中, 將發(fā)件人地址設(shè)定為敏感信息, 并將其替換為其他地址, 然后分別計(jì)算替換前后的文件數(shù)據(jù)基和偏移量。實(shí)驗(yàn)結(jié)果如圖5所示。其中, 圖5(a)和(b)分別表示郵件地址替換前后的兩個(gè)相似文件。圖5(c)和(d)分別展示了圖5(a)和(b)兩個(gè)文件前128個(gè)字節(jié)對(duì)應(yīng)的基的情況。經(jīng)過(guò)對(duì)比, 可以看出兩個(gè)結(jié)果完全一致, 說(shuō)明這兩個(gè)相似文件按照所提方法可提取出相同的基。圖5(e)和(f)分別展示了兩個(gè)文件前128個(gè)字節(jié)的偏移量計(jì)算結(jié)果。經(jīng)過(guò)對(duì)比可以看出, 圖5(e)和圖5(f)在第119～124字節(jié)的偏移量計(jì)算結(jié)果不同, 對(duì)應(yīng)兩個(gè)文件原文的不同之處。經(jīng)過(guò)該實(shí)驗(yàn), 我們發(fā)現(xiàn)本方法可以從相似文件中提取出相同的基和不同的偏移量, 對(duì)于基數(shù)據(jù)可以有效的實(shí)現(xiàn)跨用用去重, 并通過(guò)偏移量的上傳, 有效抵抗邊信道攻擊。

圖5 安全性分析實(shí)驗(yàn)結(jié)果Figure 5 Security analysis experiment results

接下來(lái), 我們隨機(jī)從Enron數(shù)據(jù)集中抽選100個(gè)文件, 分別采用本方法和SRGD算法提取基和偏移量, 對(duì)比基和偏移量大小, 以及所消耗的時(shí)間開(kāi)銷。驗(yàn)證本方法在時(shí)間開(kāi)銷和存儲(chǔ)開(kāi)銷上的優(yōu)勢(shì)。實(shí)驗(yàn)結(jié)果如圖6所示。圖6(a)展示了對(duì)每個(gè)文件提取基和偏移量的計(jì)算時(shí)間對(duì)比情況, 從結(jié)果看出本方法明顯優(yōu)于SRGD方法。這是由于本方法將計(jì)算量大的索引構(gòu)建結(jié)果預(yù)先保存在本地和云端, 避免了重復(fù)大量的重復(fù)計(jì)算, 在提取基和偏移量時(shí)直接查表即可, 而SRGD方法對(duì)于每個(gè)文件均需要重新進(jìn)行計(jì)算, 計(jì)算復(fù)雜度較大。圖6(b)和(c)分別展示了每個(gè)文件所提取基大小和偏移量大小的對(duì)比情況, 從結(jié)果看出本方法所需存儲(chǔ)開(kāi)銷較小, 說(shuō)明所提取基具有更強(qiáng)的泛化能力, 且偏移量數(shù)據(jù)間存在較多冗余,通過(guò)壓縮可以提高存儲(chǔ)效率。

圖6 計(jì)算性能分析實(shí)驗(yàn)結(jié)果Figure 6 Computational performance analysis experiment results

5.2 去重效率驗(yàn)證

在本實(shí)驗(yàn)中, 我們比較本方法與ZEUS、RARE和 CIDER這3種最新的跨用戶去重方案對(duì)相似文件去重的性能。具體地, 我們從 Enron郵件數(shù)據(jù)集中隨機(jī)選取了大小為14～26KB的1000個(gè)文件, 數(shù)據(jù)總量為19135KB。從Sakila樣本數(shù)據(jù)集中選取支付數(shù)據(jù)記錄生成另一個(gè)長(zhǎng)度為2241B的文件開(kāi)展實(shí)驗(yàn)。在本實(shí)驗(yàn)中, 假設(shè)這兩個(gè)文件均在云端存在, 分別替換部分?jǐn)?shù)據(jù)內(nèi)容進(jìn)行上傳, 測(cè)試上傳過(guò)程中的通信開(kāi)銷和存儲(chǔ)開(kāi)銷。具體地, 由于Enron郵件數(shù)據(jù)集文件較大, 我們分別替換掉10%、15%、20%、25%、30%隨機(jī)選定的數(shù)據(jù)內(nèi)容作為敏感信息, 生成對(duì)應(yīng)的相似文件, 分別對(duì)處理后的文件生成對(duì)應(yīng)的去重請(qǐng)求, 并根據(jù)4種方法生成的響應(yīng)上傳數(shù)據(jù)后比較所需的通信開(kāi)銷和存儲(chǔ)開(kāi)銷。

圖7(a)和圖7(b)分別展示了Enron數(shù)據(jù)集上的存儲(chǔ)開(kāi)銷和通信開(kāi)銷實(shí)驗(yàn)結(jié)果。對(duì)于所選用的Sakila樣本數(shù)據(jù)集, 因其數(shù)據(jù)規(guī)模較小, 數(shù)據(jù)模版特征較為清晰, 我們分別替換掉10%, 20%, 30%, 40%, 50%,60%, 70%, 80%, 90%, 100%的數(shù)據(jù)作為敏感信息, 對(duì)這些信息篡改替換后生成去重請(qǐng)求發(fā)送給云端。圖8(a)和圖8(b)分別展示了Sakila數(shù)據(jù)集上的存儲(chǔ)開(kāi)銷和通信開(kāi)銷實(shí)驗(yàn)結(jié)果。如圖所示, 在兩個(gè)數(shù)據(jù)集中,隨著文件敏感信息占比的上升, 4個(gè)比較方案的通信開(kāi)銷和存儲(chǔ)開(kāi)銷均逐步上升, 但本方法所需開(kāi)銷增長(zhǎng)趨勢(shì)較為緩慢。主要原因在于CIDER, ZEUS,RARE都是塊級(jí)數(shù)據(jù)去重方案, CIDER的返回值隨機(jī)在區(qū)間[未命中塊數(shù), 未命中塊數(shù)+1]中隨機(jī)選取,ZEUS和RARE方案均對(duì)請(qǐng)求中的相鄰塊配對(duì)生成響應(yīng), 當(dāng)其中至少一個(gè)塊命中時(shí), ZEUS方案在響應(yīng)中要求上傳的塊數(shù)為1, 而RARE為1或2, 因此CIDER的開(kāi)銷小于ZEUS和RARE, RARE的開(kāi)銷最大。而本方法僅對(duì)基開(kāi)展跨用戶去重, 對(duì)偏移量則開(kāi)展云端去重, 所以在不同的敏感信息占比下, 需要的通信開(kāi)銷主要來(lái)源為偏移量數(shù)據(jù)和基數(shù)據(jù)哈希值上傳, 存儲(chǔ)開(kāi)銷主要來(lái)源為敏感信息的偏移量數(shù)據(jù), 因此增加趨勢(shì)較為平緩。與其他3種算法相比, 本方法字節(jié)級(jí)的去重方式, 可以降低敏感信息中基的存儲(chǔ)開(kāi)銷, 且對(duì)偏移量數(shù)據(jù)壓縮后可進(jìn)一步降低開(kāi)銷, 因此,在存儲(chǔ)開(kāi)銷和通信開(kāi)銷結(jié)果中均表現(xiàn)出顯著的優(yōu)勢(shì)。

具體的, 在Enron郵件數(shù)據(jù)集中, 隨著敏感信息占比從10%增加到30%, 本文所提方法的存儲(chǔ)開(kāi)銷從1417KB增加至1878KB, 低于ZEUS、RARE、CIDER 3個(gè)方案的存儲(chǔ)開(kāi)銷, 同時(shí)通信開(kāi)銷從3006KB增加至4155KB, 也低于ZEUS、RARE、CIDER三個(gè)方案的通信開(kāi)銷。本方法在Sakila樣本數(shù)據(jù)集中表現(xiàn)出更優(yōu)的去重效率, 相較于ZEUS、RARE、CIDER 3個(gè)方案, 存儲(chǔ)開(kāi)銷可節(jié)約50%至90%。當(dāng)敏感信息占比的較大時(shí), 表現(xiàn)出更為顯著的優(yōu)勢(shì), 這是因?yàn)椴糠炙崛〉幕呀?jīng)存在于云端且具有較強(qiáng)的泛化能力, 即使敏感信息占比增大, 仍然可以實(shí)現(xiàn)數(shù)據(jù)的有效去重。而ZEUS、RARE、CIDER 3個(gè)算法均為塊級(jí)去重策略, 無(wú)法從字節(jié)級(jí)別提取相似的文件內(nèi)容。對(duì)于圖7和圖8實(shí)驗(yàn)結(jié)果,發(fā)現(xiàn)本方法在Sakila樣本數(shù)據(jù)集上具有更加顯著的優(yōu)勢(shì)。這是因?yàn)镾akila樣本數(shù)據(jù)集中數(shù)據(jù)內(nèi)容更加規(guī)范, 所提取出的基之間重復(fù)度更高, 表明本方法更適合用于類似數(shù)據(jù)庫(kù)等數(shù)據(jù)模版特征更為清晰的文件。

圖7 Enron郵件數(shù)據(jù)集去重效率驗(yàn)證實(shí)驗(yàn)結(jié)果Figure 7 The experimental results of the deduplication efficiency verification on the Enron dataset

圖8 Sakila樣本數(shù)據(jù)集去重效率驗(yàn)證實(shí)驗(yàn)結(jié)果Figure 8 The experimental results of the deduplication efficiency verification on the Sakila Sample dataset

6 小結(jié)

本文提出了一種通用的跨用戶重復(fù)數(shù)據(jù)安全去重方案, 可以有效的保護(hù)云端文件或塊的存在性隱私在邊信道攻擊下的安全性。更進(jìn)一步的, 本文所提出的基提取策略, 能夠從相似的文件或塊中提取以較高概率提取出相同模板, 具有良好的泛化能力。除此之外, 本文對(duì)偏移量在上傳前進(jìn)行壓縮處理, 能夠有效降低偏移量上傳的通信開(kāi)銷。通過(guò)在兩個(gè)真實(shí)數(shù)據(jù)集中的實(shí)驗(yàn)結(jié)果表明, 與現(xiàn)有技術(shù)相比, 本文所提方法具有更高效的去重效率和存儲(chǔ)效率。由于本文所提方法中數(shù)據(jù)分塊方法為固定大小, 可能存在邊界平移問(wèn)題, 后續(xù)我們將在數(shù)據(jù)分塊方法上進(jìn)行進(jìn)一步的優(yōu)化。