让云存储完整性检查协议更具经济效益

1 引言

过去十年中，云存储完整性检查受到了大量研究关注[1–15]随着越来越多的用户将数据外包给私营和公共部门的云存储服务提供商[16]。云存储完整性检查问题由此产生：当用户不再本地保存外包数据的副本时，如何检查其在云端的外包数据的完整性。这一问题对于那些依赖数据开展业务但内部存储预算有限的用户（例如新兴移动应用初创公司等）以及严格遵守法律法规的用户尤为重要。这是因为云中的外包存储可能由于各种经济动机或管理失误而面临被篡改、损坏甚至删除的风险。为解决此问题，研究人员提出了多种云存储完整性检查协议[1–15]以确保外包存储的完整性。

在这些提出的协议中，采用了两种方法。第一种是PoR（可恢复性证明）方法。该方法将云建模为

作为一个黑盒，仅使用云的开放API进行存储完整性检查。另一种是PDP（数据持有证明）方法。该方法在通信成本方面优于PoR方法；然而，这种方法需要云的配合，对外包存储执行计算。这两种方法都利用了抽样检查的思想，即将外包存储划分为数据块，然后随机检查选定/挑战的数据块的完整性。

尽管所提出的协议能够验证外包存储的完整性，但我们注意到这些协议并未考虑此类协议的实际经济成本。当前的云存储实践采用了一套定价策略，这意味着所提出的协议均会产生完整性检查成本。因此，本文旨在使云存储完整性检查协议在经济上更加智能。

在本文中，我们对云存储完整性检查协议的经济成本进行建模；同时提出了一种方法来推导所提出协议的最优参数。该结果有助于在将所提出的云存储完整性检查协议部署到当前云存储服务提供商时选择更优的参数[1–15]时。

我们通过两个步骤实现这一目标。首先，我们将云存储完整性检查协议的经济成本建模为三个部分：存储成本、数据传输成本以及数据访问请求/ HTTP请求成本。这三项成本根据当前云存储定价实践进行计算。我们的模型表明，总成本取决于存储大小、块大小、成功检测率、完整性检查过程中的挑战大小以及完整性检查总次数。其次，在获得总成本后，我们在其他参数固定的情况下，推导出关于块大小的最优参数。

接下来，我们针对不同参数选择进行模拟和成本分析。仿真结果验证了我们的成本模型。特别是，云存储完整性检查协议存在一个经济上最优的块数量。

本文其余部分结构如下。第2节建模云存储完整性检查协议，并回顾当前两种解决方案——PoR方法和PDP方法。第3节构建此类协议的成本模型，随后在第4节进行仿真与分析。第5节回顾云存储完整性检查的相关工作。最后，第6节总结全文。

2 云存储完整性检查模型

2.1 系统模型

图1说明了云存储完整性检查协议的工作原理；该基本模型是所有提出的云存储完整性检查协议的基础[1–15]。此类云存储完整性检查协议涉及两个实体：用户和云。用户可以是个人、组织、企业等；云可以是任何公共云服务提供商，例如亚马逊S3、微软Azure、谷歌云存储、阿里OSS等。用户首先对存储

通过嵌入一些秘密信息来外包数据，然后将其存储外包给云。之后，用户以挑战‐响应的方式与云交互，检查外包数据的完整性，例如数据是否受损、被修改甚至丢失。具体而言，用户向云发送完整性检查（或审计）查询，要求云证明外包数据仍然完整。在云返回证明后，用户通过检验该证明来验证数据的完整性。

2.2 建模提出的协议

我们简要地对先前已提出的云存储完整性检查协议进行建模，这些协议对应于图1中的系统模型。所提出的协议可分为两种方法：一种是PoR（可恢复性证明）方法；另一种是PDP（数据持有证明）方法。这两种方法具有相似的语法——它们都使用五个高效算法将云存储完整性检查（CSIC）协议建模为CSIC=(密钥生成, 外包, 审计, 证明, 验证) ，如下所示：

– KeyGen(λ) → K：在输入安全参数 λ后，用户运行该算法以生成一个密钥 K， 用于支持审计和验证。
– Outsource(F; K) → F′：在输入待外包的数据 F后，用户运行该算法，利用密钥 K得到经过处理的数据 F′。处理后的数据包含外包数据 F的一些认证信息，并随后被发送至云。
– Audit(K) → q：用户运行该算法生成一个审计查询 q，并将该查询发送至云。
– Prove(q, F′) → Γ：在输入审计查询 q后，云使用存储的数据 F′计算出一个证明 Γ。
– Verify(q, Γ; K) → δ：在输入审计查询 q和云的证明 Γ后，用户使用密钥 K检查云的证明是否正确。若证明正确则输出 δ= 1，否则输出 δ= 0。

我们注意到，可恢复性证明（PoR）方法与数据持有证明（PDP）方法存在显著差异。PoR方法将云视为一个无需要求其

了解云如何存储和处理数据；相比之下，数据持有证明（PDP）方法要求云在向用户证明外包数据完整性时进行计算。可恢复性证明（PoR）方法更易于部署，而数据持有证明（PDP）方法在通信上更高效。

尽管存在差异，PoR 和 PDP 方法都采用了相同的语法和抽样检查思想，即以概率方式随机选择数据块来检查数据完整性。这一思想体现在 CSIC.Audit、CSIC.Prove 和 CSIC.Verify 算法中。我们仅需理解上述语法即可读懂本文；PoR 和 PDP 的具体细节与本研究无关。

2.3 局限性

我们注意到所提出的云存储完整性检查协议存在一个重要局限性。当前云存储服务提供商对其服务收费。但所提出的 PoR方法 和 PDP方法 协议启发式地将外包数据划分为数据块，这会产生不同的成本。应当有一种方法能够从经济角度最优地参数化总数据块数量，本文中我们将展示这一点。

3 云存储完整性检查协议的成本模型

3.1 当前云存储定价实践

我们通过了解云服务的收费方式来评估云存储完整性检查协议的成本。在调研了一些国内外企业以及中国本土的大型云存储服务提供商后，我们发现这些服务提供商通常根据外包数据的存储大小、从云端下载数据时的数据传输量（或通信成本）以及数据访问请求次数（以HTTP请求计）进行收费。1列出了部分大型中国云存储服务提供商的示例。

云存储提供商	阿里OSS	百度BOS Ten	centCOS
存储（/GB/月）	0.158	0.15	0.156
数据传输（/GB）	0.64	0.61	0.4
数据访问请求 (/10000次请求)	0.01	0.01	0.01

我们还发现，不同的提供商收费不同；但差异仅体现在如表1所示的具体数值上。我们将在成本模型中将这些价格统一为变量。

让云存储完整性检查协议更经济高效 301

3.2 构建成本模型

我们现在评估云存储完整性检查协议的总成本。根据当前云存储实践，该成本由三部分组成，即存储成本、数据传输成本和数据请求成本。我们分别计算这些成本。

我们给出一些符号以便于表述。设 M表示云存储完整性检查协议的总成本，m1, m2, m3分别表示存储、数据传输和数据请求成本，其标准单价分别为 p1,p2,p3。设 s表示外包存储大小（字节）， n表示数据块总数， s′表示每个数据块的认证信息大小。设 i表示外包数据在云端存储的月数， j表示完整性检查的总次数， k表示数据损坏率， p表示成功检测率， c表示一次完整性检查查询中的挑战数据块数量。设 g为一个常数，用于表示云是否存储每个数据块的认证信息；若每个数据块都经过认证，则为 g= 2，否则为g= 1。

存储成本 。该成本包括外包数据以及每个数据块附带的认证数据（如有）。请注意，外包数据的大小以字节为单位，而云服务收费按千兆字节计算。我们计算 i 个月内的存储成本为

$$
m_1 = \frac{s’ \times n + s}{2^{30}} \times p_1 \times i.
$$

数据传输成本 。该成本包含云返回的每次挑战中的数据块及其认证信息。与存储成本相比，这种通信成本要高得多，因为通过互联网进行通信时，云服务提供商需要向互联网服务提供商购买带宽，从而产生费用。因此，当一次完整性检查查询包含 c次挑战时， j次完整性检查查询的成本为

$$
m_2 = \frac{(s’ + s/n) \times c}{2^{30}} \times p_2 \times j.
$$

数据访问请求成本 。当用户从云中获取/上传数据块时会产生此成本，通常发生在HTTP请求中。频繁的读取/上传操作会显著影响云的性能，因此这是一项成本。当用户将数据外包给云时，成本为 $ g \times n \times p_3 / 10000 $。对于完整性检查中的 c次挑战，成本为 $ g \times c \times p_3 / 10000 $。因此，对于 j次完整性检查，成本为

$$
m_3 = \frac{g \times n \times p_3}{10000} + \frac{g \times c \times p_3}{10000} \times j.
$$

总成本 。最后，通过将存储、数据传输和数据访问请求的成本相加，可以得到总成本。因此，云存储完整性检查协议的总成本如下

$$
M = \frac{s’ \times n + s}{2^{30}} \times p_1 \times i + \frac{(s’ + s/n) \times c}{2^{30}} \times p_2 \times j + \frac{g \times n \times p_3}{10000} + \frac{g \times c \times p_3}{10000} \times j. \quad (1)
$$

3.3 推导最优参数

根据公式(1)中的总成本，云存储完整性检查协议的最优参数存在。我们对总成本简化如下

$$
M = \alpha n + \frac{\beta}{n} + \gamma
$$

其中 $\alpha = \frac{s’}{2^{30}} \times p_1 \times i + \frac{g \times p_3}{10000}$, $\beta = \frac{s \times c}{2^{30}} \times p_2 \times j$, $\gamma = \frac{s’}{2^{30}} \times p_2 \times j + \frac{g \times c \times p_3}{10000} \times j$。

在实践中，首先根据假设的数据损坏率 $k$ 预先确定成功检测率 $p$，如下所示

$$
p = 1 - (1 - k)^c. \quad (2)
$$

然后可以确定完整性检查中的挑战总数；通常它是常数，或者仅在变量中呈对数变化 $n$ [1,2,12]，具体取决于 $k$ 的假设。因此，当固定 $\alpha$ 时，我们近似有 $\beta$ 为常数，且当 $i$ 和 $n$ 较大时成立。

因此，最小成本为 $M \approx 2\sqrt{\alpha\beta} + \gamma$，在 $n \approx \sqrt{\beta / \alpha}$ 时大致实现。值得注意的是，实际成本还取决于数据在云端存储的时间长短以及进行完整性检查的次数。

4 分析与仿真

在本节中，我们通过仿真分析云存储完整性检查协议的成本；旨在了解如何选择数据块总数以及总成本的增长情况。我们的方法是，在固定其他参数不变的情况下，研究某些变量对总成本和最优块数的影响。仿真中采用了阿里OSS定价策略[17]。我们使用 $p_1 = 0.0053$, $p_2 = 0.75$, $p_3 = 0.01$。

4.1 挑战大小与最优块数

我们研究挑战大小如何影响最优块数。我们固定 $i = 1$, $j = 1$, $s = 100 \times 1024 \times 1024$。假设数据损坏率 $k$ 为1%，完整性检查准确率要求分别为99%、95%和90%。根据公式(2)，对应的挑战大小 $c$ 分别为459、299和230。图2描述了总成本 $M$ 如何依赖于 $n$ 和 $c$。

从图2可以看出，总成本通常随着块数和挑战大小的增加而增长。对于不同的挑战大小，用户需要选择不同的最优块数。

4.2 存储大小与最优块数

我们转而研究外包存储大小如何影响最优块数。假设数据损坏率为 $k$ 1%，完整性检查准确率要求为90%，因此我们取 $c = 230$。我们将$s$的值分别设为100 MB、200 MB和300 MB。图3显示了结果。

从图3中可以看出，此处出现了与挑战大小类似的现象。文件大小越大，总成本越高。并且当存储大小变化时，最优块数量也有所不同。

4.3 持续时间与完整性检查频率对最优块数的影响

我们现在研究持续时间与完整性检查频率如何影响最优块数。与上述相同，我们假设数据损坏率为 $k$ 1%，且检查准确率要求为90%。此时挑战大小为 $c = 230$。我们对 $i$ 和 $j$ 分别模拟三组不同的取值，即$i = 1, j = 1$； $i = 3, j = 1$； $i = 1, j = 3$。图4展示了这种依赖关系。

从图4中可以看出，当我们将外包数据在云中存储的时间越长，以及完整性检查频率越高时，总成本会变得更大。最优块数也会随着持续时间和完整性检查频率的变化而变化。

本节中的仿真结果共同表明，总成本和最优块数取决于多种因素。在实际应用中，用户可根据自身需求和公式(1)计算总成本和最优块数。

5 相关工作

本节回顾了大部分相关工作。云存储完整性检查问题最早由Juels, A.和Kaliski Jr., B.S.于2007年提出[1]，以及Ateniese, G.等人[2]。前者提出了首个PoR方法解决方案，而后者提出了首个PDP方法解决方案。尽管这两种方案在理论上能够解决云存储完整性检查问题，但其功能有限。后续的研究工作通过支持数据动态性、第三方审计[3–15]对此进行了扩展。与具体方案并行的是，研究人员还探讨了云存储完整性检查与其他问题之间的关系，例如网络编码[10],分布式字符串相等性检查[12]。此外，研究人员也致力于使所提出的方案更适用于当前的云存储实践[18–20]。

据作者所知，与以往的工作相比，本文首次研究了如何使云存储完整性检查协议在经济上更高效，这可能使云存储完整性检查更易于实际部署。

6 结论

为了使云存储完整性检查协议更适用于当前的云存储实践，本文建立了一种针对此类协议的成本模型。该模型综合了存储成本、数据传输成本和数据请求成本，推导出总成本。我们表明，根据该总成本模型，云存储完整性检查协议存在最优成本和最优参数选择。我们基于一家中国云存储服务提供商阿里OSS的仿真结果进一步验证了我们的成本模型。最后，我们希望本文提出的成本模型能为其他云安全问题提供有益的启示。