基于动态布隆过滤器的云存储数据持有性验证方法

谢 丽 霞， 胡 立 杰

( 中国民航大学 计算机科学与技术学院， 天津 300300 )

0 引 言

大数据时代，作为云计算的基础，云存储发展迅猛．但是，日益严重的安全问题已经制约了云存储健康发展[1-2]．其中，云存储数据的完整性是不可忽略的一个重要问题．例如：外部攻击或云服务提供商内部人员恶意操作导致数据完整性遭到破坏；云服务提供商为维护自身名誉，隐瞒数据丢失或损坏．因此，研究一种可公开验证的云存储数据持有性验证方法是很有必要的[3]．

为保护云存储数据的完整性，国内外研究者们提出了多种数据持有性验证方案．Ateniese等[4]提出一种数据持有性证明(provable data possession，PDP)方案，该方案虽然可降低通信开销，但是仅适用于静态数据的验证，并未考虑动态数据的更新问题．Wang等[5]提出一种基于同态加密短消息签名的动态数据完整性验证方法，该方法支持公开验证和动态数据操作，但当校验元数据规模变大后插入操作的开销将十分巨大．Li等[6]提出一种基于双线性组的完整性验证方法，基于Hellman计算困难问题[7]构造双线性映射用于校验元数据计算，降低客户端执行验证协议初始化阶段的成本，但是由于验证过程使用的结构复杂导致验证效率降低．Hussien等[8]使用双块传输和加密散列函数的方式验证云存储数据的完整性，可减少客户端计算量，但是却导致辅助存储空间增大，隐私泄露的风险提高．Zhang等[9]使用rb2-3树作为验证工具实现数据公开验证和动态数据完整性验证，但该方法仍存在计算复杂、验证路径过长的问题．李勇等[10]和Zhang等[11]使用树状验证路径来确定数据块位置的正确性，减少各实体间的计算负担，简化动态更新过程，但是在云端计算持有证据时需要更多的辅助信息，导致云端与验证端的通信开销增加．

针对上述方法存在持有性证明计算复杂且验证过程需要大量辅助存储空间的不足，本文提出一种基于动态布隆过滤器(dynamic Bloom filter，DBF)的云存储数据持有性验证方法．该方法使用同态哈希函数处理验证数据并生成用于验证的校验元，基于数据块标签构造动态布隆过滤器且支持动态操作，以实现对云存储数据持有性的高效验证．

1 动态布隆过滤器

1.1 BTBF结构

本文提出的DBF为B-Tree状的布隆过滤器，即B-Tree布隆过滤器(B-Tree Bloom filter，BTBF)．BTBF不会因数据大规模增长而线性退化且有较高的查找效率，与现有云存储数据持有性验证方法相比，同样树高的BTBF可存储更多校验元．

BTBF每个节点包含i个BF，除根节点外，BTBF每个节点可存储多个关键字，一个4阶BTBF如图1所示．

图1 BTBF结构Fig.1 BTBF structure

本文提出的BTBF需满足以下7个条件：

(1) BTBF中节点的关键字由数据块标签、对应的验证签名构成，其中验证签名包括数据块签名和验证计数位；

(2) BTBF中节点按数据块标签从大到小排列；

(3) 任意非叶子节点最多只有M个子节点，且M>2，其中M为BTBF容度；

(4) 根节点的子节点数为[2，M]；

(5) 根节点外的非叶子节点数为[M/2，M]；

(6) 每个节点存放至少

M/2-1

个和至多M-1个布隆过滤器；

(7) 非叶子节点的关键字数量比对应子节点少1．

1.2 BTBF的错误率

本文提出的BTBF在云存储数据持有性证明中错误率为固定值．传统布隆过滤器存在错误率和饱和度的问题[12]，由于难以预知集合中的元素数量，随着插入元素的增多饱和度会增加，错误率也将随之提高并最终导致布隆过滤器不可用．BTBF错误率P可由特征值数量n、数位组长度m和选择哈希函数的数量k决定，P与各参数之间的关系为

(1)

云存储数据持有性证明中因为数据分块大小固定，因此通过选择适当的m、n和k，可保证BTBF 错误率变为一个可控的固定值，避免错误率升高．

2 云存储数据持有性验证方法

2.1 验证模型

传统的完整性验证模型不支持公开验证且需要在客户端存储大量数据[13]，因此本文在传统云存储验证模型的基础上引入第三方验证平台，云存储数据完整性验证模型结构如图2所示．

图2 云存储数据完整性验证模型Fig.2 Cloud storage data integrity verification model

第三方数据完整性验证模型包含客户端(Client Server，CS)、云服务提供商(Cloud Server Provider，CSP)和第三方验证平台(Third Party Verification，TPV)，CS将数据加密上传并生成校验证据，CSP存储数据和生成数据持有证据应答，TPV存储校验证据和进行数据完整性验证．

2.2 方法具体实现

基于DBF的云存储数据持有性证明方法包括3个阶段：初始化阶段、挑战阶段和应答阶段．3个阶段的具体设计如下：

(1)初始化阶段

首先，CS对存储数据进行预处理，然后，将数据和校验证据分别上传给CSP和TPV，过程设计如下：

(a)CS将数据F分割为大小固定的数据块m1，m2，…，mv，对数据块mi(i=1，2，…，v)进行预处理，生成对应数据块的特征值向量Ai=(ai1

ai2…aiv)(i=1，2，…，v)，通过k个同态哈希函数生成数据块验证签名bfi(bfi为BF生成的数位组，i=1，2，…，v)，然后将数据块m1，m2，…，mv和请求CREAT={(num1：bf1)，(num2：bf2)，…，(numv：bfv)}分别上传到CSP和TPV，上传结束对数据进行一次完整性校验，校验成功后CS将删除本地存放的数据．

(b)CSP存储CS上传的数据块m1，m2，…，mv，TPV接受CREAT请求后存储数据块验证签名集bf1，bf2，…，bfv，初始化验证计数位并生成BTBF，要求BTBF容度M≥4．BTBF的关键字由数据块验证签名bfi和数据块标签numi组成．

(2)挑战阶段

初始化完成后，CS可发起挑战请求CHL，TPV生成验证请求TPV_CHL．过程设计如下：

CS发起挑战请求CHL，TPV接受请求后在BTBF验证树中随机选择一条或多条验证路径S=(num1num2…nums)，其中numi(i=1，2，…，s)为数据块标签，数据验证率c≥80%，即验证块数量需大于数据块总数的80%．TPV将生成的随机路径S封装为验证请求TPV_CHL={S1,S2,…,Ss}发送给CSP，要求CSP提供验证请求中包含数据块的持有证据．

(3)应答阶段

CSP在接受验证请求后，根据TPV_CHL生成对应数据块持有证据交由TPV进行持有性验证，过程设计如下：

CSP接受TPV_CHL请求后，根据请求中包含的数据块标签numi查找对应的数据块mi，生成校验元向量Ai=(ai1ai2…aiv)(i=1，2…，v)，通过k个同态哈希函数生成长度为s的数据持有证据cfi，生成应答R=(cf1cf2…cfs)并反馈给TPV，TPV计算校验结果α：

(2)

其中s为随机验证路径长度．若α=0，则云存储数据完整性验证成功，TPV向CS返回结果“TRUE”，否则验证失败，返回结果“FALSE”，BTBF节点参与验证后需对该节点的校验计数位bc进行自增操作．

2.3 数据动态操作

基于DBF的数据持有性验证方法可支持包括更新、插入和删除的数据操作．

2.3.1 数据更新算法 当用户更新数据块mi(i=1，2，…，v)时，BTBF云存储数据持有性验证方法的处理过程设计如下：

(a)CS计算更新数据块mi的标签值numi和签名bfi，分别向云存储服务器和TPV发送更新请求Update_C={numi：mi}和Update_T={numi：bfi}．

(b)云存储服务器接收更新请求Update_C={numi：mi}后，根据标签值numi寻找存储在云端的数据块，用mi替换原有数据块m′i．

(c)TPV接收更新请求Update_T={numi：bfi}后，根据numi在BTBF中查找对应的校验数位组并替换为bfi，并将节点验证计数位bci初始化为0．

(d)当云存储服务器和TPV进行更新操作后，CS对云存储服务器进行一次数据完整性校验，校验成功后CS删除本地存储的mi．

(a)CS计算插入数据块mi的标签值numi以及签名bfi，分别向云存储服务器和TPV发送插入请求Insert_C={numi：mi}和Insert_T={numi：bfi}．

(b)CSP接收请求Insert_C={numi：mi}后，存储接收的数据块mi．

(c)TPV接收插入请求Insert_T={numi：bfi}后，首先在BTBF中根据numi查找数据块签名bfi的插入位置，然后将bfi插入到节点中．插入完成后需对插入的节点进行判断，若该节点存放的数据块签名数量大于M，则需分裂该节点并对BTBF进行调整，保证在完成插入操作后仍能满足BTBF的7个条件．

(d)当CSP和TPV全部进行插入操作后，CS对云存储服务器进行一次数据完整性校验，校验成功后CS删除本地存储的mi．

2.3.3 数据删除算法 当用户删除数据块mi(i=1，2，…，v)时，BTBF云存储数据持有性验证方法的处理过程设计如下：

(a)CS查找删除数据的标签值numi，分别向云存储服务器和TPV发送删除请求Delete_C={numi}和Delete_T={numi}．

由于进化的观念所强调的时代性和进步性，“国故”终究只是过去式，无法真正从“古”来到“今”。胡适说文言文是“死文字”，决不能做出有生命有价值的现代文学。他主张“历史的真理论”，认为真理的价值只是“摆过渡，做过媒”，可以随时换掉、赶走。这样的“国故”即使被“整理”出来龙去脉，其价值最终也极易被“评判”为陈设在博物馆的、没有生命的展品。时间之流终究被“评判”之利刀斩断为古今的坚硬对峙，已“死”的过去走不进现在和将来的生命。所以，“评判的态度”不仅要求人们认清古今变易的大势所趋，更要做“反对调和”的“革新家”，将目光聚焦于现在与未来。在胡适看来，生乎今之世而反古之道，是有违进化之迹的背时逆流。

(b)云存储服务器接收Delete_C={numi}后，根据数据块标签numi查找数据块并删除．

(c)TPV接收Delete_T={numi}后，在BTBF 中查找数据块标签为numi的节点并删除该节点中对应的关键字．节点在数据块删除后，需要判断该节点关键字数量是否满足每个节点至少存放和至多M-1的条件．如果该节点不满足，BTBF树需要对该节点和邻近节点进行合并，使得树仍满足BTBF条件．

M/2-1

(d)当CSP和TPV分别进行删除操作后，CS对云存储服务器进行一次数据完整性校验，校验成功后CS删除操作完成．

本文提出的基于DBF的云存储数据持有性验证方法的动态操作与传统方法相比具有以下特点：

(1)更新操作不只在叶子节点处进行，BTBF树的内部均可进行更新操作，优化存储空间．

(2)删除操作只针对删除节点，不需对其他节点进行更新操作，减少删除造成的冗余计算．

(3)与常用的默克尔哈希树相比，BTBF的插入操作优化验证树的高度，避免大量执行插入操作后验证树退化为线性结构，提高数据完整性验证效率．

3 验证的安全性分析

对基于DBF的云存储数据持有性验证方法分别从验证正确性、数据保密性、持有证明不可伪造性和抗重放攻击等几方面进行分析．

3.1 正确性分析

BTBF在云存储数据持有性验证中存在由假阳性问题造成的错误率，因此本文采用多个数位组构成验证路径的方式降低错误率，使得验证的正确率达到100%，布隆过滤器的错误率[14]如表1所示．

设BTBF高为h，容度为M，随机验证路径S的长度为s，单个BTBF节点验证错误率为f．则数据验证率c=sh/(Mh-1)，单条验证路径错误率Ps=fsh．验证过程中，当sh≥3时，若f≤0.01，则Ps≤1×10-6．

表1 布隆过滤器错误率Tab.1 Bloom filter′s error rate

在本文方法中，f设为≤0.01的固定值，同时设定c≥80%，则sh≥0.8(Mh-1)．为提高验证效率设定M≥4，此时得到sh≥3．因此本文提出的方法错误率Ps≤1×10-6，趋近于0．

可见，本文方法使用BTBF验证正确率可达到100%．

3.2 保密性分析

第三方平台通过两种方式得到用户有效数据：方式一为第三方平台通过CS上传的校验证据，方式二为CSP提供的持有证据．

首先，CS将数据文件F分为固定大小的数据块m1，m2，…，mv，数据块mi生成校验元向量Ai=(ai1ai2…aiv)(i=1，2，…，v)，通过k个哈希函数生成长度为m的数据块签名bfi．由于Ai为mi的特征值并只含有部分原始数据，经过k个哈希函数生成数位组后，为仅包含0和1的序列．由于哈希过程不可逆，攻击方不能通过bfi逆向得到原始数据，因此可保证有效数据不被TPV获得．

其次，CSP提供的持有性证明cfi同样是经过哈希函数处理后的数位组，这是个不可逆的过程，因此攻击者无法通过持有性证明获得有效数据．

所以，本文方法可防止数据隐私泄露，保证TPV不能得到客户有效数据．

3.3 抗伪造攻击和抗重放攻击分析

首先，假设攻击方伪造数据持有证据(Rp=(cf′1cf′2…cf′s))，其中，cf′i(i=1，2，…，s，s为验证路径S长度)为数据标签．其中对于BTBF单个节点关键字伪造成功的成功率Pl=1/2m，那么单条随机验证路径S的持有证据伪造的成功率为Ps：

(3)

当攻击方对多条随机路径发起联合攻击时，多条路径的持有证据需同时通过TPV的持有验证，因此对于w条随机路径联合攻击成功概率Pc可通过Ps得到：

(4)

w条随机路径联合攻击的成功概率Pc会随着s和w的增大而逐渐减小，由于m≥6，则Pc远小于0.015 6，可认为攻击方对多条路径联合攻击的成功概率为0．因此，本文提出的方法，当验证的数据规模越大时，抵抗伪造攻击的能力越强．

本文的云存储数据完整性验证方法为动态验证方法，所以TPV存储的校验数据会随时间变化而变化．当攻击方在BTBF树更新后进行攻击时，由于BTBF验证树会因为更新操作发生改变，重放已有的持有证据并不能通过TPV的完整性验证；当攻击方在BTBF树未更新时进行重放攻击，由于BTBF关键字中包括验证计数位，在验证计数位未完全消耗的情况下，每次验证时验证计数位不同，因此重放已有的持有证据，并不能通过TPV的完整性验证．当在BTBF节点计数位未消耗完毕时，本文提出的方法可抵抗重放攻击．

4 实验与结果

本文主要针对基于DBF的云存储数据持有性验证方法进行实验，实验重点为持有性证明计算开销、辅助存储空间和BTBF性能．在Linux下使用Python语言实现本文模型的核心功能，其中动态操作和BF计算使用Python的Btrees模块和PybloomFiltermmap模块实现，实验数据集为47 000个随机生成的数据文件，数据集大小为2 048 MB．

4.1 计算开销

为验证数据持有性证明计算更简单，分析并计算BTBF方法、MHT方法[5]、rb2-3方法[9]以及UpdateTrees方法[11]的各项时间复杂度，记录如表2(其中n为数据块数量，K为常数，D为动态操作的数量)．

由表2所见，BTBF方法与rb2-3方法的CSP时间复杂度最小，都可以达到常量级；但是本文提出的BTBF方法在树操作时间复杂度上明显优于其他几种方法．

然后对BTBF和rb2-3两种方法CSP的计算时间进行对比，设置数据分块大小为5 MB，BTBF 数位组长度为20 000，单个BTBF节点错误率为0.1%．在实验中，统计并记录100、200、300、400和500块数据块下，两种方法CSP计算持有证据的时间，结果取10次平均值，实验结果如图3所示．

表2 验证方法时间复杂度对比Tab.2 Verification method′s time complexity comparison

图3 不同数据量的持有证据计算时间Fig.3 The calculation time of different data volume of provable data possession verification

由图3可见：本文提出的BTBF方法持有性证明的计算时间明显少于rb2-3方法，并且随着处理规模的增大，时间差异逐渐增大．本文提出的BTBF方法计算更加简单，计算时间开销更小．

4.2 辅助存储空间

对比BTBF方法和rb2-3方法的辅助存储空间，设置单个BTBF节点错误率为0.1%，数位组长度为20 000，数据分块大小为5 MB；分别统计BTBF方法和rb2-3方法在128、256、512、1 024和2 048 MB数据量下的辅助存储，结果如表3所示．

从表3可见：(1)相同数据规模下BTBF使用的辅助存储空间远小于rb2-3方法；(2)BTBF的辅助存储空间与所验证的数据规模大小呈线性相关，辅助存储空间大小可控．本文提出的BTBF方法具有更优的辅助存储，可提高云存储数据的完整性验证效率．

表3 辅助存储开销对比Tab.3 Auxiliary storage′s overhead comparison

4.3 BTBF性能

为验证BTBF的性能，分别对BTBF生成和查询时间进行实验，设置数据分块大小为5 MB，BTBF数位组长度为20 000，单个BTBF节点错误率为0.1%．在实验中，获取并统计BTBF生成和查询时间，结果取平均值，实验结果如图4所示．

图4 BTBF生成和查询时间Fig.4 BTBF generation and query time

从图4可见：(1)BTBF验证树的生成和查询时间降低到20 ms以下，计算时间有效降低；(2)BTBF的生成时间增长速率较缓慢，不会因需校验的数据量变大而导致生成时间快速增长．BTBF 避免了因为数据规模增大而线性退化最终导致验证效率降低的问题．

5 结 语

本文提出一种基于DBF的云存储数据持有性验证方法．该方法通过使用动态布隆过滤器处理特征值向量生成数据块标签，减少客户端计算量；使用随机验证路径对云存储数据进行持有性验证；将TPV存储空间变成与校验元数据规模相关的值，并且支持数据全动态操作．实验表明该方法提高了云存储数据持有性验证效率．

[1] 冯登国,张 敏,张 妍,等. 云计算安全研究[J]. 软件学报, 2011,22(1):71-83.

FENG Dengguo, ZHANG Min, ZHANG Yan,etal. Study on cloud computing security [J].JournalofSoftware, 2011,22(1):71-83. (in Chinese)

[2]ALI M, KHAN S U, VASILAKOS A V. Security in cloud computing: Opportunities and challenges [J].InformationSciences, 2015,305(1):357-383.

[3]谭 霜,贾 焰,韩伟红. 云存储中的数据完整性证明研究及进展[J]. 计算机学报, 2015,38(1):164-177.

TAN Shuang, JIA Yan, HAN Weihong. Research and development of provable data integrity in cloud storage [J].ChineseJournalofComputers, 2015,38(1):164-177. (in Chinese)

[4]ATENIESE G, BURNS R, CURTMOLA R,etal. Provable data possession at untrusted stores [C] //CCS′07:Proceedingsofthe14thACMConferenceonComputerandCommunicationsSecurity. NY :ACM Press, 2007:598-609.

[5]WANG Qian, WANG Cong, LI Jin,etal. Enabling public verifiability and data dynamics for storage security in cloud computing [J].LectureNotesinComputerScience, 2009,5789LNCS:355-370.

[6]LI Aiping, TAN Shuang, JIA Yan. A method for achieving provable data integrity in cloud computing [J].JournalofSupercomputing, 2016,72(1):1-7.

[7]ESCALA A, HEROLD G, KILTZ E,etal. An algebraic framework for Diffie-Hellman assumptions [J].LectureNotesinComputerScience, 2013,8043LNCS(PART 2):129-147.

[8]HUSSIEN Z A, JIN Hai, ABDULJABBAR A,etal. Public auditing for secure data storage in cloud through a third party auditor using modern ciphertext [C] //Proceedingsofthe201511thInternationalConferenceonInformationAssuranceandSecurity,IAS2015. Marrakesh: IEEE Press, 2015:73-78.

[9]ZHANG Jianhong, MENG Hongxin, YU Yong. Achieving public verifiability and data dynamics for cloud data in the standard model [J].ClusterComputing, 2017,20(3):2641-2653.

[10]李 勇,姚 戈,雷丽楠,等. 基于多分支路径树的云存储数据完整性验证机制[J]. 清华大学学报(自然科学版), 2016,56(5):504-510.

LI Yong, YAO Ge, LEI Linan,etal. LBT-based cloud data integrity verification scheme [J].JournalofTsinghuaUniversity(ScienceandTechnology), 2016,56(5):504-510. (in Chinese)

[11]ZHANG Yihua, BLANTON M. Efficient dynamic provable possession of remote data via update trees [C] //ASIACCS2013-Proceedingsofthe8thACMSIGSACSymposiumonInformation,ComputerandCommunicationsSecurity. NY: ACM, 2013.

[12]SATO F, WAKABAYASHI S. Bloom filters based on the B-tree [C] //ProceedingsoftheInternationalConferenceonComplex,IntelligentandSoftwareIntensiveSystems,CISIS2009. Fukuoka: IEEE Computer Society, 2009:500-505.

[13]SHIMBRE N, DESHPANDE P. Enhancing distributed data storage security for cloud computing using TPA and AES algorithm [C] //Proceedings—1stInternationalConferenceonComputing,Communication,ControlandAutomation,ICCUBEA2015. Piscataway: IEEE, 2015:35-39.

[14]BRODER A, MITZENMACHER M. Network applications of Bloom filters: a survey [J].InternetMathematics, 2004,1(4):485-509.