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