云计算中大数据的快速数据审计算法

郑英姿，刘 源，赵 鹏

(1.广东技术师范大学天河学院 计算机科学与工程学院, 广州 510540；2.桂林理工大学 信息科学与工程学院， 广西 桂林 541004；3.太原师范学院 计算机科学与技术系， 太原 030619)

随着电信4G网络与移动互联网的迅猛发展，许多用户与企业使用智能移动设备通过电信网络将本地的隐私数据保存于云存储中，从而降低本地的存储负担，同时有助于数据的分享[1-2]。由于云服务器是半可信的，所以用户需对云端数据进行定期审计，方可保证云端数据的完整性与安全性[3-4]。

为了提高云端数据的安全性，研究者提出了许多针对数据完整性的审计算法，主要包括2种类型：数据拥有性证明(PDR)[5]、数据可取回性证明(POR)[6]。数据拥有性证明允许用户随时知道其数据是否仍然有效地保存于云存储平台中，以及是否可以随时、随地访问该数据；数据可取回性证明验证云数据的完整性状态，并在损坏小于一定程度时修复数据。

WANG等[7]基于文献[8]提出了一种带隐私保护的审计方案，该方案既具有审计能力也保护了隐私，但其分块策略为每个数据块引入了验证标签，极大地提高了存储的成本。传统的完整性验证技术(hash函数、签名等)无法应用于云存储场景[9]，许多研究人员设计了远程数据审计(RDA)技术，通过生成随机的挑战验证数据持有的证明[10]。可靠的RDA应当具备以下5点性质[11]：① 计算成本、存储成本及通信成本较低；② 具备公/私钥2种验证模式；③ 应频繁使用不同的挑战进行验证；④ 可检测潜在数据占用的概率；⑤ 具有动态的远程更新能力。移动智能设备的计算能力、4G网络的通信能力都为有限资源，而已有的RDA方案需频繁地进行验证，为数据所有者带来了不可忽略的计算与通信负担。

针对上述问题，本文设计了一种新的数据结构CDDT(cloud data descriptor table)以提高大规模数据的动态更新效率，并采用代数签名方案实现云数据的数据持有性证明，其计算成本远低于基于同态加密系统的证明策略[12]。

1 问题模型与背景知识

1.1 RDA系统模型

图1所示是RDA模型的主要结构。RDA模型共包含4个主要实体：① 数据所有者DO：个人、企业将数据上传到云空间中，后期对外包数据进行修改、删除、插入与添加等更新操作；② 云存储服务器(CSP)：具有大量的计算资源与存储资源；③ 第三方审计单位(TPA)：对云存储内的信息进行审计有助于降低DO的数据审计开销；④ 用户：DO已认证的受信任用户，对外包数据具有预定的访问能力。

图1 RDA模型的主要结构

1.2 代数签名

代数签名是一种hash函数，代数签名的主要性质是对随机块总和的签名等价于各块签名之和[13]。文件F(包含n个数据块)的代数签名可如下计算：

(1)

式中:γ是伽罗华域的元素，包含多个元素γ=(γ1,γ2,…,γn)。

代数签名具有以下3个性质：

性质1长度为r的多个块f[i]的代数签名f[j]计算如下：

Sγ(f[i]|f[j])=Sγ(f[i])⊕rγSγ(f[j])

(2)

性质2文件F若干个块之和的签名等价于各块的签名再求和：

Sγ(f[1])+Sγ(f[2])+…+Sγ(f[m])=

Sγ(f[1]+f[2]+…+f[m])

(3)

证明假设文件F分为m个块，每个块包含n个扇区(sector)，可得：

Sγ(f[1])+Sγ(f[2])+…+Sγ(f[m])=

f[2][j]+…+f[m][j])=

Sγ(f[1]+f[2]+…+f[m])

(4)

式中：f[i][j]表示文件F中块i的第j个比特。

性质32个文件F与G之和的代数签名等价于2个文件签名再求和：

Sγ(F+G)=Sγ(F)+Sγ(G)

证明计算2个文件F与G的签名之和(分别包含n个块)：

Sγ(F+G)

2 算法设计与实现

2.1 远端数据审计(RDA)算法

假设输入文件F通过数据分段技术分为m个数据块，其中每个块包含n个扇区。如果最后一块的扇区数量小于n，则需增加该块的大小，增加的数据设为f[m][j]=0(j≤n)。本方案包含以下4个阶段：

1) 建立阶段：首先DO使用KenGen算法生成公钥与秘钥(KenGen(1k)→(pk,sk))，其中k是一个安全参数；然后，计算每个输入文件各块的唯一标签(metadata)，具体计算方法如下：

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

(5)

3) 证明：云服务器收到挑战消息后需产生证明消息，证明消息为块σ与验证模块标签(μ)的消息对。证明消息的计算方法如下式所示：

(6)

4) 验证：DO收到证明消息(μ,σ)后，基于块标签的代数签名DO验证块的完整性，如下式所示：

(7)

为了提高本方法的安全性，在建立步骤中DO使用DO的私钥对文件id签名，然后在验证步骤中使用DO的公钥对签名进行验证。

2.2 动态数据更新操作

动态数据更新是RDA的关键需求，数据所有者可实时地更新外包数据。为了高效地实现动态外包数据更新，设计了一个新的数据结构CDDT，CDDT也可通过验证阶段抵御重放攻击。

CDDT包含两个关键部分：① 逻辑序号(Li)，表示了数据块的原序号；② 版本号(Vi)，表示块的当前版本号(更新次数)。如果DO更新一个数据块，CDDT中对应的Vi加1，表示该块被修改。DO在将数据上传至云服务器之前为各文件生成CDDT数据结构，然后通过更新操作管理CDDT或交给TPA管理。

如果需在数据库第i个块之后插入新数据，审计模块必须移动n-i个块，由此导致审计模块中过多的计算开销。为了解决该问题，将CDDT分为k个子CDDT，每个子CDDT大小为n/k，此时在第i块插入新块，DO仅需移位n/k-i个块。该设计方案降低了大型文件的动态更新成本。

2.2.1修改数据操作

数据修改是RDA的一个重要操作，允许DO仅改变少量的块来更新外包文件，从而避免下载整个文件。假设修改文件f[i]第i个块，修改后文件表示为f′[i]，DO的修改算法如下：

步骤1通过比较i与每个子CDDT的范围搜索请求块在CDDT中的准确位置，将块的版本号加1：Vi=Vi+1。

步骤2为修改的数据块生成一个新标签，具体方法如下式：

(8)

图2 数据所有者修改 f[7]情况下CDDT的变化结果

2.2.2插入数据操作

假设在文件第i个块f[i]之后插入一个新的数据块(f*[i+1])，DO的插入算法如下所示：

步骤1基于CDDT的范围搜索文件F的第i个块，识别出CDDT中新块l的准确位置。

步骤4将当前CDDT的最大范围加1。

(9)

CSP收到插入消息后，在外包文件中位置i之后插入对应的新块。图3描述了CDDT结构中插入操作的实例：在文件第7个块后插入一个新块，DO仅需将子CDDT最后3项向下移一位，插入的新块为CDDT2[3]={16,1}，然后增加该子CDDT的最大范围与下一个子CDDT的最小范围。

图3 CDDT结构中插入操作的实例

2.2.3添加数据操作

图4 CDDT中添加操作的结果实例

2.2.4删除数据操作

删除操作是插入操作的逆操作，将外包文件中第i个块删除。首先，DO基于各子CDDT的最大、最小范围，搜索第i个块的子CDDT位置(p)；然后，通过将所有的后续块(n/k-p)向上移一位来删除块p；最终，DO发送一个删除消息(IDF,i)至CSP。图5所示是CDDT删除操作的实例，将CDDT1[5]向上移位至CDDT1[4],并将CDDT1,CDDT2,…,CDDTn范围分别减一。

图5 CDDT删除操作的实例

3 安全性分析

Sγ(IDF‖i‖Li‖Vi)=

审计模块从CSP获得证明消息之后，验证证明消息以确保存储的正确性(使用式(7)验证)。基于代数签名的性质对式(7)进行如下的扩展：

Sγ(f[cs1]+…+f[csc])=

Sγ(f[cs1]+…+Sγ(f[csc]))=

本方案使用代数签名产生一个小数据量作为每个块的签名，但可追踪外包文件任意的修改操作。代数签名也可验证分布式存储系统中的分布式大数据，其计算与通信成本较低。另一方面，代数签名中产生冲突的概率是可忽略的，例如：如果签名的长度是64比特，产生冲突的概率仅为2-64。综上所述，代数签名技术对认证外包数据的正确性是有效的，对于DO为移动设备的情况，效果尤佳。

4 CDDT结构数量的优化设计

文献[15]插入或删除一个块，审计模块需将剩余的数据块依次移位，其审计模块的计算复杂度为O(n)。本文提出的新数据结构解决了该问题，将数据块保存于k个列表中。本方案审计模块的计算复杂度仅为O(n/k)，搜索块位置最差情况的计算复杂度为O(k)。本方案优于文献[15]的前提条件为：

因为k≥1，所以：

因此，子CDDT的最优数量可计算如下：

表1所示是1～100 GB文件的最小、最大与最优的子CDDT表数量(k)，假设每个块的大小为4 kB。

表1 不同大小文件的k最小值、最大值与最优值

5 仿真实验与结果分析

5.1 检测异常行为的性能

本方法采用随机采样的策略以降低CSP的负载，将输入文件F分为若干块m，随机选择少量的块c作为一个挑战。

假设CSP修改m个外包块中的y个块，则修改块的概率等于py=y/m。假设c是挑战步骤中DO需验证的外包数据块数，n是每块的sector(扇区)数量。假设x是离散的随机变量，表示DO选择的块数量，假设Px(x≥1)表示DO选择的块至少有一个被服务器修改的概率，可如下计算Px：

Px(x≥1)=1-Px(x=1)=

(10)

同时：

(11)

因为每个块包含n个sector(扇区)，则sector粒度的概率(ps)可如下计算：

py≥1-(1-ps)n⟹

(1-py)c≤((1-ps)n)c⟹

1-(1-py)c≥1-(1-ps)nc⟹

px(x≥1)≥1-(1-ps)nc

另一方面：

(12)

假设DO将1 GB文件分为125 000个块，块大小为8 kB，将各块上传到云存储。图6所示是检测不同数量的外包数据块所需的挑战块数量。如果服务器的Py=0.1，则DO需随机地选择98个块作为一个挑战，方可获得0.999 99以上的Px，因此在保持高检测率的前提下，可通过增加破坏块的数量降低挑战块的数量。

图6 检测不同数量的外包数据块所需的挑战块数量

5.2 RDA的通信与计算成本分析

RDA有3个重要的性能指标：① 通信成本；② 数据审计的计算成本；③ 动态数据更新的计算成本。将本方法与文献[16](EPA)、文献[15](ESDA)进行比较。EPA是一种动态的云计算数据审计技术，该技术考虑了TPA以及动态云存储的验证，与本算法考虑的要素较为接近。ESDA是一种考虑隐私保护的云计算数据审计技术，该技术也支持动态数据操作，并且实现了较好的审计效果。表2所示是3种RDA方案的比较结果。EPA在动态数据更新操作中的计算开销最大，原因在于EPA中使用MHT数据结构来检查外包数据块的完整性与更新操作，复杂度较高。ESDA在添加操作与修改操作的计算方面复杂度较低(O(c))，但在插入与删除操作中更新一个块，验证模块必须将数据结构中的m-i个实体进行移位，其计算复杂度为O(m)。本文设计了一种新的数据结构(CDDT)来降低计算成本，插入或删除一个数据块，审计模块仅移位一部分的外包数据块(n/k-i)，审计模块的计算成本为O(n/k)。

表2 3种审计算法不同模块的通信与计算成本

5.3 RDA的实验与分析

使用Eualyptus IaaS云对本文RDA进行实验。Eucalyptus是基于Linux的开源软件，可安装于linux操作系统上[17]。本文实验基于Intel 酷睿i3处理器，主频为3.7 GHz，采用C语言编程实现。使用PBC(版本0.5.14)仿真EPA与ESDA的数据审计方案，EPA与ESDA均使用160比特的椭圆曲线。每组实验独立运行20次，将平均值作为最终的结果。

首先，测试本方案对数据频繁更新的效果。选择1 GB的外包文件，共有125 000个数据块，将更新的块数量设为100～1 000，间隔设为8。图7所示是计算时间与更新块数量的关系，EPA的插入与删除操作中，审计模块需在MHT树中搜索目标块的精确位置，并重新计算新叶节点的hash值，导致审计模块的计算成本较高。ESDA搜索块i的位置后，对于插入与删除操作，审计模块需将剩下的n-i个块进行移位，如果多次进行该处理，则会导致较高的计算成本。本方案通过使用10个CDDT极大地降低了计算成本，效果优于其他两种算法。

图7 计算时间与更新块数量的关系

第2组实验测试了子表数量k对数据更新计算成本的影响。图8所示是不同k值下计算时间与更新块数量的关系，k值越高，计算时间越低。当更新数据块数量较高时，审计模块产生不可忽略的计算开销。可通过最优k值降低计算成本，例如：当k=100时，插入1 000个块所需的计算时间为0.156 s，k值提高为353时，其计算时间降为0.140 s。

图8 不同k值下计算时间与更新块数量的关系

第3组实验测试了文件大小对动态数据更新计算成本的影响。将文件大小设为1～10 GB，对外包文件随机地插入或删除100个块。图9所示是3种RDA方案对大型文件审计的计算时间。对于10 GB的文件，EPA需管理MHT中大量的数据集，其计算时间最高；ESDA的审计模块在插入与删除一个数据块时需对大量的块进行移位操作，消耗了较高的计算时间；本方法受益于子CDDT划分的设计，使用10个子CDDT与代数签名方案提高了计算效率，可看出本算法对大规模文件具有较好的效果，明显优于EPA与ESDA两种算法。

图9 3种RDA方案对大型文件审计的计算时间

第4组实验测试了本方法对大型文件的效率。图10所示是本方案随着数据块数量与文件大小增加的计算时间。对于1 GB的文件，更新 1 000个块所需的时间为0.218 s；对于100 GB的文件，更新 1 000个块所需的时间为10.811 s。图10的结果显示，若保持k值与文件大小同步增加，可保持较低的计算时间，可见本算法适用于大数据审计的场景。

6 结束语

移动智能设备的普及使得云存储成为电信网络的一个重要应用。为了保证云端外包数据的完整性与安全性，移动智能设备需对外包数据进行频繁的审计，为了降低移动智能设备在审计操作中的计算与通信成本，设计了一种针对云存储大数据的RDA算法。提出了CDDT代替对云端数据的直接操作，通过将CDDT分为若干子CDDT降低CDDT操作的搜索与计算成本。此外，使用代数签名简单有效地完成了RDA的挑战与证明操作。实验结果表明，本算法极大地降低了云端外包数据审计的计算与通信成本，优于其他的审计算法。