王惠峰，李战怀，张晓，孙鉴，赵晓南

(西北工业大学计算机学院，陕西西安 710072)

支持多代理的云存储数据完整性审计方法

王惠峰，李战怀，张晓，孙鉴，赵晓南

(西北工业大学计算机学院，陕西西安 710072)

由于云存储服务面临许多损坏数据的风险，检验数据完整性便成为一个亟需解决的基本问题。数据持有性验证（provable data possession，PDP）是检验云存储数据完整性的重要方法。然而，在传统的PDP模型中，单审计代理易造成单点故障并且易形成性能瓶颈。为此，提出了一种支持多代理的数据完整性审计方法（multi-proxies PDP，MP-PDP）。该方法采用循环链表管理多代理节点，使用审计队列存储文件的审计任务，实现了审计任务分发、节点监控、失效节点切换和动态增加代理等功能，并且利用备份节点消除了系统的单点故障。实验结果表明，MP-PDP有效减少了文件的审计执行时间，并且能够快速增删审计代理。

多代理；数据持有性证明；数据完整性验证；云存储安全

随着云计算技术的日益发展，公共云存储服务已经得到普遍的应用，DropBox、Google Drive、金山快盘等公共云存储产品的用户数量飞速增长［1］。然而，云存储服务面临许多损坏数据的风险，数据丢失事故层出不穷，如2011年3月，谷歌Gmail邮箱出现故障，造成大约15万用户的数据丢失［2］；2012年8月，国内盛大云因物理服务器磁盘损坏造成用户的数据部分丢失。数据存储厂商EMC指出，64%的受调查企业在过去12个月中经历过数据丢失或宕机事故。及时发现数据损坏不仅可以打消用户疑虑，还能为数据恢复赢得宝贵的时间。因此，验证数据完整性是一个亟需解决的基本问题。

数据持有性验证(provable data possession， PDP)［2-3］是检验云存储数据完整性的重要方法。该方法采用抽样策略，对云中的文件发起完整性验证，在不下载整个文件的情况下，能够及时识别出云中损坏数据的行为。基本的PDP模型［2］仅仅允许文件所属用户执行完整性检测，但是用户资源有限，执行审计任务给用户造成计算负担，且基于数据拥有者的审计方式不利于云存储审计服务的推广。为了有效减少用户的审计负担，研究人员［4-7］提出基于第三方审计的公开验证模型，利用公开密码体制将审计任务委托给第三方审计者代为执行。

然而，在传统的PDP模型中，单审计代理易成为系统的性能瓶颈，限制了系统的横向扩展；并且单代理节点易造成单点故障，审计代理崩溃将导致整个审计系统崩溃。

针对以上问题，本文提出了一种支持多代理的数据完整性审计方法。该方法基于主从结构设计，主节点采用循环链表管理多代理节点，使用审计队列存储文件的审计任务，实现了审计任务分发、节点监控、失效节点切换和动态增加代理等功能。从节点执行审计任务，并且利用备份节点消除系统的单点故障。实验结果表明，MP-PDP能有效减少文件的审计执行时间，并且能够快速增删审计代理。

1　系统结构

1.1系统模型

基于审计代理的数据完整性验证模型，如图1所示，由用户、云存储服务提供商、第三方审计者组成。用户是云存储服务的使用者；云服务提供商为用户提供计算或者存储服务，具备强大的计算能力和存储能力；第三方审计者又称为审计代理，代替用户执行具体的审计任务，以减轻用户的审计负担。

图1　基于第三方审计的公开验证模型

1.2基础知识

文件M由n个数据块组成，每个数据块由s个数据扇组成，表示为M＝｛mij｜i∈［1，n］，j∈［1， s］｝。其中，数据块(data block)是验证文件完整性的基本单位，数据扇(data sector)是文件读写的基本单位。

双线性对映射是执行数据块认证的基础函数，定义如下［6⁃7］：存在2个阶数为p(p为大素数)的乘法循环群G1和G2，G1的生成元为g。若映射e：G1× G1→G2满足以下条件，则称e为双线性对映射：

1)可计算性，存在一个高效的算法可以计算出映射e；

2)双线性，对于所有u，v∈G1和a，b∈Zp， e(ua，ub)＝e(u，v)ab均成立；

3)非退化性，e(g，g)≠1。

1.3数据完整性的审计过程

数据完整性的审计模型［7］由5个算法(KeyGen，TagGen，Chall，ProofGen，Verify)构成，分述如下：

1)密钥生成算法KeyGen其输入为系统安全参数λ，输出为密钥对(skt，pkt)和加密密钥skh。其中：密钥对(skt，pkt)用于生成数据块认证标签；skh用于加密文件摘要信息Minfo，如文件名、数据块总数等。

2)认证标签生成算法TagGen其输入为文件M和私钥(skt，skh)，输出为文件数据块的认证标签集合T＝｛ti｜i∈［1，n］｝和文件信息集合Minfo。其中：ti的计算方法如(1)式所示，Wi＝FID‖i是数据块位置信息，h(skh，∗)是文件信息加密函数，uj是G1类型的随机值。

3)挑战信息生成算法Chall其输入为文件的摘要信息Minfo，输出挑战信息C＝(｛i，vi｜i∈Q｝， R)。其中：i是被挑战数据块mi的索引，Q是i的集合，vi∈Zp是伴随mi的随机值，R＝gr是辅助值，r∈是随机值是小于p且与其互素的正整数。

4)数据持有性的证据生成算法ProofGen其输入为文件M、数据块的认证标签集合T和文件的挑战信息C；输出为数据持有性证据P＝(TP，DP)。TP是被挑战数据块的标签证据信息，其计算方法如(2)式所示；DP是被挑战数据块的证据信息，其计算方法如(3)式所示，而MPj是数据扇的线性组合，其计算方法如(4)式所示。

5)Verify算法用来验证服务器返回的数据持有性证据，输入为挑战信息C、数据持有性证据P、公钥pkt和文件摘要信息Minfo。若等(5)式成立，则输出0，表示文件完好；反之，输出1，表示文件损坏。其中，Hchal是被挑战数据块摘要信息的哈希值的连乘积，按(6)式计算。

数据完整性的审计过程分3个阶段执行：

阶段1：初始化阶段

用户使用KeyGen生成密钥对(skt，pkt)和加密密钥skh，使用TagGen生成数据块的认证标签集合T和文件摘要信息Minfo。用户发送(Minfo，skh，pkt)给审计者，发送(M，T)到云服务器。

阶段2：确认审计阶段

审计者使用Chall生成挑战信息C并将其发送给云服务器。云服务器使用ProofGen生成数据持有性证据P，并返回给审计者。审计者使用Verify验证接收到的证据信息P，若通过审计，表明文件已经完好存储到云服务器，可删除本地副本。

阶段3：抽样审计阶段

定期执行阶段2，抽样检测云端数据的完整性。

1.4支持多代理的数据完整性审计模型

支持多代理的数据完整性审计模型，是在原始模型［7］的基础上经扩展实现的，如图2所示。

图2　多代理结构示意图

多代理结构是由主代理节点、备份节点和审计代理等三部分通过网络连接构成。主代理节点是审计系统的管理者，主要完成审计任务分配、审计代理的监控、失效代理的切换和审计代理的动态扩展等功能。备份节点是主代理节点的备份，用于接管出现故障的主代理节点，消除审计系统的单点故障。审计代理是审计任务的实际执行者，接收主代理节点分配的审计任务并向其返回审计结果。

2　多审计代理的功能实现

本节首先介绍多审计代理结构所需的数据结构，然后介绍各个功能的实现过程。

定义1 审计任务(audit task，AT)是执行文件完整性审计的基本单位，可用一个二元组结构＜FID，rr＞描述。其中，FID(file identifier)是文件识别符，它规定了审计任务的执行对象；rr(recognion rate)是错误识别率，规定了审计的执行强度。

定义2 审计队列(audit queue，AQ)是审计任务的存储结构，如图3所示。每个执行代理对应一个审计队列，审计任务依次进入队列，审计任务执行完毕后，便从审计队列移除。审计队列结构包含队列头指针head和队列尾指针tail，队列长度length可以选择设置。

2.1审计任务分配

审计任务分配模块负责接收文件的审计任务，并执行分配算法(assignment algorithm，AA)将其插入到相应的审计队列。依据分配算法不同，分为任务平均分配算法(average AA，AAA)和最短队列优先任务分配算法(shortest queue first AA，SAA)。为方便描述，定义符号如表1所示。

图3　审计队列结构示意图

表1　符号定义

任务平均分配算法将审计任务平均分配给每个审计队列，如算法1所示。首先，使用循环链表串联审计队列，并将指针Y指向待分配的审计队列，如图4所示；然后，将审计任务分配给指针Y指向的审计队列，并后移指针Y；循环执行第二步，分配后续的审计任务。

图4　循环链表结构示意图

算法1任务平均分配算法

任务平均分配算法要求审计代理具备相同的审计性能，否则将造成审计代理负载失衡，即部分审计代理积压审计任务，部分审计代理因提前完成审计任务而闲置。

最短队列优先任务分配算法将审计任务总是分配给长度最短的审计队列，如算法2所示。首先，比较审计队列长度，移动指针P指向长度最短的审计队列；其次，将审计任务分配给指针P指向的审计队列，同时增加该队列长度；从审计队列移除已完成审计任务并减少该队列的长度；重新将指针P指向长度最短的队列；最后，重复执行第二步，分配后续的审计任务。

算法2 最短队列优先任务分配算法

2.2审计节点的状态监控

采用定期发送心跳信息方法，监控审计节点的状态。倘若被监控节点不能按时返回心跳信息，表明节点出现故障。如果主代理节点故障，则启动备份节点予以修复。如果审计代理故障，则执行失效审计节点的动态切换予以修复。

2.3失效审计节点的动态切换

切换失效的审计节点将重新分配该审计节点的审计任务，并由其他审计代理代为执行，如算法3所示。发现失效审计节点后，首先，找到对应于该失效节点的审计队列(假设为AQj)；其次，从循环链表中删除审计队列AQj；最后，按照审计任务分配算法重新分配审计队列AQj的审计任务。

算法3 失效审计节点的切换算法

2.4代理节点的动态增加

代理节点的动态增加过程如算法4所示。首先，生成新代理的审计队列，并将其插入到循环链表；然后，执行任务分配算法AA为其动态添加审计任务，使该队列的审计任务数与其他队列保持平衡。

算法4 代理节点的动态增加算法

3　实验结果分析

为了评估MP-PDP的性能，对MP-PDP进行了仿真实验，比较了MP-PDP模型与PDP模型的审计执行时间，并且测试了替换失效代理和增加审计代理的性能开销。

3.1实验环境

采用C语言实现了原型系统MP-PDP，将该系统运行于浪潮AS300N服务器，运行环境：Ubuntu 12.04.3 LTS，Linux 3.8.0-29(x86－64)，4x Intel(R) Xeon(R)CPU E5502＠1.87 GHz，内存16 GB，硬盘ATA Hitachi HTS54501 150 GB。

3.2实验结果与分析

1)审计文件执行时间

设置不同代理数，对不同数量的文件(100～500)执行数据完整性审计，审计周期为4 h，循环审计72 h，并统计审计执行的时间。从图5可以看出，与单代理模型(代理数为1)比较，采用多代理审计模型明显减少了审计执行时间，并且审计文件数量越大，执行时间减少得越明显。相较于任务平均分配算法AAA，最短队列优先分配算法SAA进一步减少了系统的审计执行时间。

图5　审计文件的执行时间

审计执行时间减少的原因，是多个审计代理分担了审计任务，使得同一时刻可以并行审计多个文件。由于存在通信和计算开销，审计执行时间不能随审计代理的数量增加而成倍减少。但是，在不同情况下，通信成本占总开销比重基本固定。因此，随着审计代理数量增加，审计执行时间的减少越显著。采用5个代理时，减少的审计执行时间约为80%。

2)切换失效代理的执行时间

对不同代理数的设定，比较不同任务分配算法(AAA和SAA)切换失效代理节点的执行时间。从图6可以看出，最短队列优先任务分配算法SAA所需时间，明显低于任务平均分配算法AAA，并且随着文件数量增加，SAA的执行时间减少得越显著。其原因是，SAA算法将失效代理节点未完成的审计任务，集中分配给审计任务数最少的节点，避免了与多个代理间建立连接和传输的性能开销，而AAA算法需要将审计任务平均分配给存活的多个审计代理，网络连接和传输会导致较大的性能开销。

图6　替换失效代理节点的执行时间

3)动态增加代理节点的执行时间

设定不同代理数，比较了不同任务分配算法动态增加审计代理节点的执行时间。

从图7可以看出，随着文件数量的增加，任务平均分配算法AAA的执行时间呈线性增长，而最短队列优先任务分配算法SAA的执行时间增长较为平缓。其原因是，AAA算法将调动所有代理向新审计代理转移审计任务，而SAA算法只需将新来的审计任务转移给新审计代理，保持其他审计代理不变，因此节省了大量的网络开销。

图7　动态增加代理节点切换的执行时间

4　结 论

针对现有的数据完整性模型中单代理节点易造成单点故障并易形成性能瓶颈等问题，本文提出了一种支持多代理的数据完整性审计方法MP-PDP。该方法采用主从结构，实现了审计任务分发、节点监控、失效代理的替换和审计代理的动态增加等功能，并且利用备份节点消除了系统的单点故障。实验结果表明，该方法可有效提高系统的审计效率，并且能够快速增删审计代理。

［1］ 李晖，孙文海，李凤华，等.公共云存储服务数据安全及隐私保护技术综述［J］.计算机研究与发展，2014，51(7)：1397-1409

Li Hui，Sun Wenhai，Li Fenghua，et al.Secure and Privacy-Preserving Data Storage Service in Public Cloud［J］.Journal of Computer Research and Development，2014，51(7)：1397-1409(in Chinese)

［2］ 谭霜，贾焰，韩伟红.云存储中的数据完整性证明研究及进展［J］.计算机学报，2015，38(1)：164-177

Tan Shuang，Jia Yan，Han Weihong.Research and Development of Provable Data Integrity in Cloud Storage［J］.Chinese Journal of Computers，2015，38(1)：164-177(in Chinese)

［3］ Ateniese G，Burns R，Curtmola R，et al.Remote Data Checking Using Provable Data Possession［J］.ACM Trans on Information and System Security，2011，14(1)：12

［4］ Wang Cong，Chow S S M，Wang Q，et al.Privacy-Preserving Public Auditing for Secure Cloud Storage［J］.IEEE Trans on Computers，2013，62(2)：362-375

［5］ Zhu Y，Hu H，Ahn G J，et al.Cooperative Provable Data Possession for Integrity Verification in Multicloud Storage［J］.IEEE Trans on Parallel and Distributed Systems，2012，23(12)：2231-2244

［6］ Wang Boyang，Li Baochun，Li Hui.Oruta：Privacy-Preserving Public Auditing for Shared Data in the Cloud［C］//IEEE Trans on Cloud Computing，2014，1：43-56

［7］ Yang K，Jia X.An Efficient and Secure Dynamic Auditing Protocol for Data Storage in Cloud Computing［J］.IEEE Trans on Parallel and Distributed Systems，2013，24(9)：1717-1726

An Audit Method of Data Integrity for SuPPorting MultiPle Proxies in Cloud ComPuting

Wang Huifeng，Li Zhanhuai，Zhang Xiao，Sun Jian，Zhao Xiaonan
(Department of Computer Science and Engineering，Northwestern Polytechnical University，Xi′an 710072，China)

Since cloud storage service faces many security risks that can damage data，checking data integrity has become increasingly urgent.Provable Data Possession(PDP)is an important method for verifying data integrity in cloud computing.But the single proxy in the traditional PDP models easily becomes the single point of failure and catches the performance bottleneck.So we propose an improved PDP，called MP-PDP by us，for supporting mutiple proxies in cloud computing.It adopts a circular linked list and uses audit queues to store the audit tasks.It achieves such functions as assigning audit tasks，monitoring nodes，switching failed node and dynamically adding proxy and uses the backup node for eliminating the single point of failure.The experimental results indicate that MP-PDP can efficiently reduce the audit time for files and quickly add or delete the audit proxy.

algorithms，big data，conceptual design，cost reduction，design of experiments，dynamic models，dynamical systems，efficiency，fault tolerance，mathematical models，monitoring，scalability，software reliability，switching frequency；cloud storage security，data integrity checking，multiple proxies， PDP(provable data possession)

TP309.2

A

1000-2758(2016)02-0343-06

2015-04-17基金项目：国家“863”高技术研究发展计划基金(2013AA01A215)、国家自然科学基金(61472323)、中央高校基本科研业务费专项资金(3102015JSJ0009)与华为创新基金(YB2014040023)资助

王惠峰(1986—)，西北工业大学博士研究生，主要从事云存储安全、云存储评测的研究。