基于优化分治表的远程数据审计方法研究

毛 颉 王红玉 陈 云

1(浙江工业职业技术学院 浙江 绍兴 312000)2(杭州电子科技大学信息工程学院 浙江 杭州 310018)

0 引 言

互联网时代海量数据需要存储和管理，而本地存储系统管理如此大的数据相当困难，成本也非常高。得益于云计算[1-2]的快速发展，大量数据外包到云端，以降低本地数据存储和维护的负担。虽然云服务为数据所有者带来了很大好处，但将数据外包到一个远程服务器，其安全性、完整性和可用性必须要得到保障[3]。这也是远程数据审计的研究目的和意义。关于远程数据审计的研究，特别是基于云端，已经有很多研究者给出了自己的见解。如文献[4]提出在不需要下载全部数据的情况下，对云端数据存储的完整性进行验证，基于RSA编码[5]的同态可验证标签，并通过合并数据块标签生成一个单一标签。然而，使用RSA编码会对整个文件产生较高的计算成本和通信成本。文献[6]通过结合哈希树和双线性聚合签名[7]，提出了一个动态远程数据审计方法。其主要工作是通过对叶节点进行从左到右的排序，改进了哈希树的结构，有助于更好地识别更新后的数据块位置。然而，该方法容易引起数据泄露，并且将给审核者带来较高的计算成本，特别是大型文件。文献[8]基于Merkle哈希树[9]和双线性对技术，提出一种能够支持动态操作的代理远端数据完整性审计方法[8]。该方法的缺点与文献[6]的类似。而且双线性对的计算成本比代数结构的更高[10]。文献[11]提出一种远程数据审计方法，利用双线性对的特性，生成一个仅能由审核者验证的加密证据。然而，该方法增加外包块的数量可能会导致审核者需要移动的块数量极大，将产生较高的计算成本。且由于节点再平衡的问题，其不支持高效的频繁动态更新操作。现有的远程数据审计方法要求频繁地进行审核，涉及多个进程以及频繁的数据传输。因此，给审核者带来额外的计算和通信成本，这对于许多数据所有者来说是一个沉重的负担，特别是当数据所有者的设备具有计算资源的较大限制。本文的远程数据审计方法主要有两个特点：一是使用代数签名，不同于双线性对结果，代数结构计算成本更低；二是使用分治表解决大规模数据的频繁更新，减少审核者和服务器的计算成本。

1 提出的远程大数据审计方案

远程大数据审计主要有四个实体：数据所有者、云存储供应商、第三方审计者和用户。1)数据所有者：将数据上传到云空间，并可能在随后通过执行修改、删除、插入和附加操作对外包数据进行更新的个人、公司或企业。2)云存储供应商：具有相当数量的计算资源和存储系统，并负责管理云服务器和数据。3)第三方审核者：帮助数据所有者减轻数据审核过程中的计算负担，其具有足够的技术和能力来完成审核任务。4)用户：必须被数据所有者验证为可信用户，并被授权可对外包数据发起特定的访问。主要组件及其相互作用如图1所示。

图1 远程大数据审计的网络体系结构

1.1 算法描述

假设使用数据分割技术，将输入文件F分为m个数据块，每个数据块包含n个区段。基于数据分割技术，如果最后一个数据块的区段数量小于n，则必须通过设置f[m][j]=0，j≤n以增大该数据块。本文提出的远程数据审计方案包括以下步骤：

设置：数据所有者首先通过使用KeyGen算法[9]，KeyGen(1k)→(pk,sk),式中k是一个安全性参数，生成公共密钥和秘密密钥。接着计算出输入文件的每个数据块的唯一标签(元数据)：

Ti=Sγ(f[i]‖(IDF‖i‖Li‖Vi))

(1)

质询：为对外包数据快的完整性进行验证，数据所有者需要生成一个质询消息。包含随机的c个数据块的一个质询消息，使用伪随机置换[12]生成一个新的密钥，以防止服务器预测数据块被索引。证据：当云服务器接收到质询消息时，基于该质询消息和相应的标签生成证据消息，该证据消息包括数据块的一个线性组合(σ)和认证者的标签聚合(μ)：

(2)

(3)

验证：一旦接收到作为证据的数据对(μ,σ)，数据所有者就可以基于数据块标签的代数签名验证数据块的完整性：

Sγ(σ)?=μ

(4)

为提高提出方法的安全性，数据所有者可以通过在设置步骤中使用其专用密钥对文件序号进行标记，并在随后的验证步骤中使用该专用密钥对签名进行验证。

1.2 分治表及其数据操作

动态数据更新是数据审计的一个重要特征，允许数据所有者在不需要下载数据的情况下，对外包数据进行更新。然而，很多现有方法并不支持这一特征。本小节将描述提出的数据结构，即分治表DCT结构，此数据结构可以高效地执行动态更新操作。此外，分治表还能够防止服务器进行重放攻击，因为在通过验证的阶段，使用服务器中先前版本的存储数据，而非更新后的版本。

分治表包括2个重要组件。(1)逻辑索引(Li)：表示数据块的原始索引；(2)版本号(Vi)：数据块的当前版本。如果数据所有者更新了一个数据块，那么分治表中的Vi则加1，以表示修改后的数据块。因此，外包数据块的物理位置与分治表中每个数据块的索引相匹配。数据所有者在将文件外包到云端之前，需为每个文件生成分治表数据结构。同时，数据所有者也可在更新操作或将该任务委托给第三方审计者的过程中，对分治表进行管理。

在数据操作过程中，当文件较大时，会因为节点再平衡的问题，为审计者带来较大的计算成本。例如，要在第i个数据块之后插入一个新数据块，审计者必须移动n-i个数据块，这会给审计者带来相当大的计算开销。为解决该问题，本文将DCT分为大小为n/k的k个独立数据结构，并缓解节点再平衡的问题。因此，使用新的DCT结构在第i个数据块之后插入一个新的数据块，数据所有者只需移动(n/k-i)个数据块。实验结果表明：提出的数据结构能够高效地管理较大文件的动态数据更新操作。下面简要介绍修改、插入、删除等动态数据操作的。

1.2.1 数据修改

数据修改是数据审计的重要要求，以允许数据所有者通过改变一定数量的数据块，而不用下载所有的数据块，以完成对外包文件的更新。假设将文件的第i个数据块f[i]修改为f′[i]，数据所有者需执行以下步骤：

1) 通过将i与每个分治表的范围进行比较，以找到请求修改的数据块在DCT中的位置，同时必须增加该数据块的版本号。

2) 为修改后的数据块生成一个新标签：

(5)

(6)

1.2.2 数据插入

(7)

(8)

1.2.3 附加数据

1.2.4 数据删除

删除操作与插入操作相反，即对外包文件的第i个数据块进行移除。因此，为删除一个数据块，数据所有者首先必须基于每个DCT的最大和最小范围，找到存储着第i个数据块的那个DCT。然后，找到该数据块在确定DCT中的位置(p)，并将其后的所有数据块(n/k-p)向上移动一位，移除该数据块。最后，数据所有者将包含(IDF,i)的一个删除信息传送到云存储供应商。

2 分析与优化

2.1 安全性和正确性分析

(9)

(10)

提出的方法依靠代数签名为每个数据块生成作为签名的较小实体，并显示出外包文件中的任何改动。代数签名也能够在分布式存储系统中验证大量的存储数据，同时仅产生最小限度的计算成本和通信成本。另一方面，代数签名中的碰撞概率可以忽略不计。例如，如果签名的长度是64位，其碰撞概率将是一个非常小的数字(2-64)。因此，代数签名技术有助于对外包数据的正确性进行验证，特别是在数据所有者使用移动设备的情况下。

2.2 DCT优化

本文方法的主要贡献之一是降低动态数据更新操作中的计算开销。一般情况下，进行数据块的插入或删除操作，审计者必须移动剩余的所有数据块，而这将给审计者带来相当大的计算开销(O(n))。本文提出了一个新的数据结构，通过将数据块存储在k个数组中，而非存储在一个集成数据结构中，以克服这一问题。由此，本文方法在审计时仅产生O(n/k)的计算开销。在最差的情况下，本文方法会产生O(k)的计算开销。因此，当且仅当满足以下条件时，本文方法才具备高效性：

(11)

由于k≥1，则：k2+n-nk≤0⟹

(12)

(13)

当外包文件的大小在1 GB至100 GB之间，每个数据块大小为4 KB时，提出方法中DCT的最小、最大以及最佳时的数量，计算结果如表1所示。

表1 对于不同长度文件，最小、最大和最优的DCT数量

3 性能评估与分析

本节对异常行为的检测概率进行分析，并对实验结果进行评价。与文献[8]和文献[11]的数据审计方法进行比较。

3.1 不良行为检测概率分析

本文基于随机采样策略，以减少云存储供应商的工作量。即将输入文件(F)分为大量数据块(m)，并随机选择一些数据块(c)作为执行批处理的一个质询。下面基于这一技术，对数据审计方法的不良行为检测概率进行分析。

假定云存储供应商对m个外包数据块中的y个数据块进行了修改，那么数据块的受损概率等于py=y/m。设c为数据所有者在质询步骤中为验证外包数据而要求的数据块数量，n为每个数据块中的区段数量。设x为一个离散型随机变量。则计算数据所有者至少挑选出一个与服务器修改后的某个数据块相匹配数据块的概率，如下：

px(x≥1)=

(14)

(15)

图2 不同数量的受损数据块与质询消息数据块的数量

(16)

假设数据所有者将1GB的文件分为125 000个数据块，每个数据块大小为8KB，并将数据块上传至云存储。当从px的一个集合px={0.7,0.8,0.9,0.99,0.999 99}中采集出不良行为检测概率时，不同数量的受损数据块和质询消息数据块的数量关系如图2所示。如果在外包数据块(m)中服务器进行了修改的数据块py=0.1，那么数据所有者需要随机选择98个数据块作为一个质询，以实现至少0.999 99的px。因此，通过增加受损数据块的数量，为实现这一检测概率而需要的质询数据块数量则相对较小，即对于py=0.4仅需要22个数据块。随着不同量的数据受损率，所需的质询数据块数量会有所不同。如果服务器对0.01%的外包数据块进行修改，则数据所有者必须随机选择520个数据块作为一个质询，以使受损数据块的检测概率达到0.989 9。同时，当数据块的受损率超过0.1%时，使用最小数量的质询数据块对外包数据进行审计。

3.2 实验评价与比较

本文与其他方法比较的参数如下所示：

(1) 通信成本：体现在审计方案的不同阶段中，审计者和服务器之间的数据传输量。

(2) 数据审计中的计算成本：从验证者角度看，数据审计的计算成本表示审计者为验证外包数据的完整性而使用的计算资源。从服务器角度看，数据审计的计算成本表示在响应阶段、处理和生成证据消息所需的时间。

(3) 动态数据更新的计算成本：动态数据审计方法允许数据所有者使用插入、删除、附加和修改操作，对外包数据进行更新。执行这些操作所需的时间。

不同远程大数据审计方法比较结果如表2所示，其中，m表示数据块数量，n表示一个数据块的区段数量，c表示每个审计查询中质询数据块的数量，k表示分治表数量。

表2 不同的远程大数据审计方法的比较

图3 频繁数据更新的计算成本比较

由表2，文献[8]的最大计算开销出现在动态数据更新阶段，因为该方法使用了哈稀树结构，对外包数据块的完整性进行验证。文献[11]对一个数据块进行修改或附加操作时具有较高效率，但若要在i之后插入一个数据块，或者删除某个特定的数据块(f[i])时，验证者必须在数据结构中移动(m-i)个实体。因此，该方法在插入和删除操作过程中的计算开销为O(m)。为解决这一问题并改善审计方法，本文利用分治表以减少计算开销。要插入或删除一个数据块，验证者必须移动一部分的外包数据(n/k-i)，这将给验证者带来O(m/k)的计算开销。要在DCT结构中找到一个数据块(f[i])，验证者仅需要将一个数据块的位置划分为k个部分，并找到合适的DCT。为证明本文提出的方法在频繁的数据更新中具有高效性。实验中对一个1 GB大小的外包文件，以及125 000个数据块进行更新，其中更新数据块的数量范围为100至1 000，更新间隔为8个数据块。结果如图3所示，这证明了本文方法通过使用10个大小为12 500个数据块的DCT，显著降低了审计者的计算开销。当文件大小在1 GB至10 GB的范围间，在每个外包文件中随机插入或删除100个数据块时，文件大小对动态数据更新计算成本的影响如图4所示。当文件大小增加至10 GB时，文献[8]的方法所产生的计算时间从0.8 s增加到2.3 s，这一显著增加的原因是需要在哈希树中管理数量非常大的数据块。与之类似，在文献[11]提出的方案中，随着数据块数量的增加，为完成对一个数据块的插入或删除，审计者必须移动大量的数据块，这给审计者带来较高的计算成本。本文方法对于10 GB的文件，最大计算时间为0.2 s，因为本文使用了10个DCT而非一个大的分治表，并使用了代数签名。因此，本文方法适用于对具有动态特性的大型文件进行审计。

图4 从1 GB至10 GB不同大小文件的计算成本比较

4 结 语

本文提出了一种用于云存储系统的高效远程数据审计方法，并最大限度减少了计算和通信成本。提出的数据结构设计“分治表”能够有效地支持动态数据操作，例如附加、插入、修改和删除等操作。提出的数据结构可应用于大规模数据存储，且计算成本较小。实验结果表明所提方法具备安全性，并能够以较高的效率降低服务器和审计者的计算成本和通信成本。未来将着眼于对现有方法进行扩展，以用于在分布式云存储系统中对大型存档文件的完整性进行审计。

参考文献

[1] 王登科,李忠.基于粒子群优化与蚁群优化的云计算任务调度算法[J].计算机应用与软件,2013,30(1):290-293.

[2] 张建勋,古志民,郑超.云计算研究进展综述[J].计算机应用研究,2010,27(2):429-433.

[3] Sookhak M,Talebian H,Ahmed E,et al.A review on remote data auditing in single cloud server:Taxonomy and open issues[J].Journal of Network & Computer Applications,2014,43(5):121-141.

[4] Lee N Y,Chang Y K.Hybrid Provable Data Possession at Untrusted Stores In Cloud Computing[C]// International Conference on Parallel and Distributed Systems.Tainan,Taiwan,China:IEEE press,2011:638-645.

[5] 梁小英.RSA快速实现算法的研究与改进[D].北京:北京邮电大学,2010.

[6] Wang Q,Wang C,Ren K,et al.Enabling Public Auditability and Data Dynamics for Storage Security in Cloud Computing[J].IEEE Transactions on Parallel & Distributed Systems,2011,22(5):847-859.

[7] 杜红珍,温巧燕.一个高效的基于身份的聚合签名方案[J].四川大学学报(工程科学版),2011,43(1):87-90.

[8] 赵洋,王士雨,吴松洋,等.一种代理远程数据完整性审计协议[J].电子科技大学学报,2016,46(1):80-85.

[9] 李玲,刘汝焯.计算机数据审计[M].北京：清华大学出版社,2014.

[10] Catalano D,Fiore D,Gennaro R,et al.Algebraic (trapdoor) one-way functions and their applications[C]// Theory of Cryptography Conference on Theory of Cryptography.2013:680-699.

[11] Yang K,Jia X.An Efficient and Secure Dynamic Auditing Protocol for Data Storage in Cloud Computing[J].IEEE Transactions on Parallel & Distributed Systems,2013,24(9):1717-1726.

[12] 余昭平,王晓东.基于循环移位置换的超伪随机置换的构造[J].电子与信息学报,2006,28(5):832-835.