英语原文共 8 页
分布式存储的信息理论安全纠删码
摘要：分布式存储中的纠删码修复操作涉及大量的数据迁移。这可能会将数据暴露在被动窃听者或主动攻击者的恶意行为下，从而使系统的安全性处于危险之中。本文介绍了编码方案和修复算法，以确保在被动窃听者和主动攻击者存在的情况下数据的安全性，同时保持系统的高可用性，可靠性和资源效率。所提出的编码是最佳的，因为它们满足先前提出的对各种系统参数的存储和网络带宽要求的下限。因此建立了这种系统的安全存储容量。提出的编码基于称为生成矩阵编码的最佳编码类。为主动攻击者提供安全性的结构提供了“按需安全性”的附加吸引力特征，其中可以为每个修复实例单独选择所需的安全级别，并且所提出的算法对于所有可能的安全级别同时保持最佳。本文还提供了管理任何（非安全）编码转换为提供按需安全性的编码的必要和充分条件。
关键字：分布式存储，纠删编码，信息理论安全性，再生编码，节点修复，被动窃听者，主动攻击者，网络编码。
1.介绍
存储在大型分布式存储系统（如数据中心）中的数据量呈指数级增长。为了以低成本大规模扩展，数据中心采用廉价的商用硬件。由于这些组件容易出现故障[3]，[4]，系统必须具有足够的冗余，以确保数据在面对这些故障时仍然可靠且可用。有一种通过复制引入冗余的方法。然而，复制在存储空间利用方面是低效的，因此为了经济地扩展，数据中心越来越多地转向将纠删编码作为更有效的选择[5]，[6]。
考虑具有n个存储节点的分布式存储系统，在该存储节点上存储一些数据（称为信息）。这n个节点中的每一个仅存储一小部分数据。为了提供可靠性和可用性，本文考虑的纠删编码确保用户（称为数据收集器）能够从存储在n个节点中的任何k个中的数据中恢复消息。此属性称为数据重建或简单重建。重建属性为存储系统提供了容忍n个节点中任何n-k个节点故障的能力。
在存储节点发生故障时，指定替换节点以存储先前存储在故障节点中的数据。 替换节点通过下载（部分）存储在其余节点中的数据来恢复该数据。这被称为节点修复操作或简称修复操作。传统的纠删码通常通过下载和重建整个消息然后从中提取所需的数据来处理修复。这样的操作非常浪费网络资源[4]，[7]-[9]，最近的一些工作[7]-[30]提出了新的纠删码和修复算法来解决这个问题。
安全性是分布式存储系统的一个重要方面，最近的许多数据泄露事件（例如，[31]-[33]）强调了这一点。本文考虑了为分布式存储设计编码和算法的问题，除了保持其他属性（如可靠性，可用性和效率）之外，还要确保安全性。我们考虑了安全性的信息理论概念（而不是计算概念），没有假设对手的计算能力。
在设计安全的分布式存储系统时，必须特别注意修复操作，因为它们会造成安全隐患。例如，在使用传统纠删编码的系统中，故障节点的修复将需要在替换节点处下载整个数据。 因此窃听到替换节点的窃听者可以获得整个数据。 或者，在修复故障节点期间，已捕获一个或多个剩余节点的活动，对手可能传递损坏的数据。这样的行为会破坏存储在替换节点中的数据，并且这些错误可以在随后的其他节点的修复期间传播到整个系统。这使得修复操作成为严重的安全威胁，并激发了本文的研究目标。
图1 （n,k）为（4，2）的RS码的修复仿真示例
图1说明了使用具有n=4和k=2的Reed-Solomon编码的仿真示例的修复动态下的安全性问题。编码后将消息{a，b}存储在四个节点上，其中a和b都属于有限的F5场。通过下载存储在四个节点中任意k=2的数据，可以很容易地验证整个消息是否可以恢复。在任何节点发生故障时，替换节点连接到任何其他两个节点，下载存储在其中的所有数据，替换节点在发生故障之前从中恢复存储在节点中的数据。图1a展示出了具有被动窃听者的设置。具体而言，考虑一个能够读取存储在节点1中的所有数据的窃听者。在Reed-Solomon编码下，窃听者可以访问符号a。此外，如果窃听者还能够侦听在任何修复操作期间传递的数据，则它可以访问整个消息。图1b说明了具有活动对手的设置。假设一个活跃的攻击者获得对其中一个节点的访问权，比如节点3，并假设通过连接到节点2和3来执行节点1的修复。然后，如图所示，攻击者可以在修复中传递恶意数据处理（例如，（a b 1）而不是（a b）），使替换节点错误地存储（a 1）而不是a。反过来，该错误在进一步修复期间传播，并且还破坏涉及节点1的所有后续重建操作。
在本文中，我们基于Dimakis等人引入的再生编码模型对分布式存储系统进行建模[34]。除了前面介绍的参数n和k之外，该模型还有第三个参数d。在节点失效时，替换节点可以连接到剩余节点中的任何d个节点，并且能够通过从这些d个节点下载最少量的数据来恢复先前存储在故障节点中的数据。在[34]中显示，在每个节点存储的数据总量与为故障节点的修复而下载的数据之间存在折衷，这在第II-A节中有更详细的描述。权衡中的两个极端制度是最小存储再生（MSR）和最小带宽再生（MBR）制度。MSR制度旨在最小化每个节点所需的存储量，并且对于这个最小存储量，维修期间的数据下载量最小化。另一方面，MBR制度旨在将维修期间的数据下载量保持在绝对最小值，并且对于该最小数据下载量，最小化其所消耗的存储量。
关于再生编码的初始工作[34]认为修复是“功能性的”，其中替换节点不需要与故障节点相同，而应仅满足进一步的重建和修复。严格更强实用的要求是精确修复，其中替换节点必须获取和存储与故障节点中的数据相同的数据。在本文中，我们只考虑精确修复。本文考虑的威胁模型是[35]中为再生编码设置提出的威胁模型的扩展。本文考虑了两类威胁：
- 来自被动窃听者的安全性威胁：此威胁类涉及防止任何有关数据信息泄露给可能访问存储节点子集的被动窃听者。通过被动窃听，我们的意思是窃听者可以读取和存储它获得访问的任何数据，但不会破坏任何数据。 在我们的威胁模型中，两个参数zeta;和m确定要提供的安全级别：目标是确保被动窃听者能够访问存储在任何节点中的数据，并且还可以访问下载的数据以便在任何m中进行修复 这些节点获得有关消息的零信息。
- 来自主动（恶意）攻击者的安全性威胁：此威胁类涉及获得对存储节点子集的访问并且可能主动破坏数据的攻击者而并不会影响到系统的运行。 活跃的对手可能破坏存储在存储节点子集中的数据，并且还在修复操作期间将错误数据传递给其他节点。特别地，对于某些参数p确定要提供的安全级别，目标是防止p个节点被活动对手破坏。在这种情况下，如果替换节点（或数据收集器）连接到任何p个损坏的节点，则这些损坏的节点可以在修复操作中传递任意数据。这里的目标是成功即使存在这样的攻击，也可以完成节点修复和数据重建操作
在本文中，我们在MSR和MBR基础上提供了分布式存储的显式编码，以确保处于被被动窃听者或主动攻击者攻击威胁下的数据的安全性。这些编码构造基于产品矩阵框架[12]。 针对MBR部分呈现的安全编码适用于参数[n，k，d]的所有值，并且针对MSR部分呈现的安全编码适用于满足dge;2k-2的参数的所有值。提供的安全编码方案有两个吸引人的特点：
- 最优性：所提出的安全编码对于各种参数设置是最佳的，也就是说，它们满足[35]中建立的存储量和网络要求的下限。MBR的主动攻击者和被动窃听者的安全性编码对于参数的所有值都是最佳的。MSR的编码安全性对于满足dge;2k-2的所有参数都是最优的。 针对MSR的被动窃听者的安全性编码对于满足dge;2k-2且mle;1的所有参数是最佳的。因此，本文中提出的编码在这些方案中建立了安全存储容量。
- 来自活跃对手的按需安全性：在提议的编码构造下，当处理活动对手时，安全级别p不必先验地固定，并且可以在任何修复或重建操作时灵活选择执行。对于每个修复或重建实例，可以单独且独立地选择安全级别p。这种按需安全性赋予系统不必为最坏情况预设安全级别和相关系统资源的优点。这与传统的信息理论安全模型（例如，[35]）相反，传统的信息理论安全模型（即[35]）采用“静态”方法进行系统设计，其中支付价格，根据存储的消息大小的减少，对应于所需的“最坏情况”安全级别的大小。事实证明，可能令人惊讶的是，建议的编码不需要任何额外的存储来支持这种按需属性，并且对于所有p值同时是最佳的。
手头上的问题与安全网络编码问题密切相关[36]-[44]。关于安全网络编码的文献主要考虑多播设置，其中一个或多个接收器希望获得所传输的整个数据。 威胁模型通常会考虑网络中链路受损的情况。另一方面，我们考虑的问题属于更难的非多播设置[36]，此外，还需要处理攻击者或窃听者能够捕获网络中节点的更难的情况[42]。因此，本文的结果建立了具有危害节点能力的主动攻击者或被动窃听者存在的非多播网络类的能力。有趣的是，本文提出的能力实现编码是线性的，确定性的和明确的。
虽然本文的主要重点是信息理论安全性，但这篇文章的结果也与其他应用相关，例如纠正网络错误和擦除以及减少数据中心“降级读取”的延迟。这些应用将在第II-D节中详细讨论。
本文的其余部分安排如下：第二节规范了系统模型，并描述了我们对编码构造问题的处理方法。本节还讨论了所提出的编码的一些其他应用。第III节描述了相关文献。本文中提出的编码建立在我们之前提出的产品矩阵框架[12]的基础上，该框架在第IV节中进行了概述。第五节和第六节介绍了MBR编码的明确结构，它们分别为主动对手和无助的窃听者提供安全保障。第VII节和第VIII节明确构建了MSR编码，分别为主动攻击者和被动窃听者提供安全保障。第IX节提供了必要和充分的条件，用于管理将任何（非安全）擦除编码转换为提供按需安全性的编码。第十节提出了结论性讨论。
2.系统模型，方法和结果总结
我们将在没有安全要求（“再生编码”模型）的情况下首先描述系统模型，然后我们描述包含安全性提供的扩展。除此之外，我们还描述了构建安全分布式存储编码的方法，以及本文结果的摘要。
A.再生编码模型（在没有安全要求的情况下）
在再生编码模型[34]下，该系统包括n个存储节点，在其上存储包括B个符号的数据。这组B符号称为消息，并且假设这些符号中的每一个属于大小为q的有限字段Fq。n个存储节点中的每一个都具有存储alpha;符号的容量。要存储数据，使得用户（称为数据收集器）可以通过下载存储在这n个节点中的任何k个节点中的数据来恢复整个消息。该过程称为数据重建，或简称重建。因此，满足重建属性的任何系统都可以容忍任何n-k存储节点的故障而不会丢失任何数据。
现在让我们考虑修复操作。当存储节点发生故障时，它将被另一个节点（称为替换节点）替换，该节点存储与故障节点完全相同的数据。再生编码模型包含与修复操作相关联的两个附加参数d和beta;。允许替换节点连接到剩余n-1个节点中的任何d（dge;k）个节点，同时从每个节点下载beta;（beta;le;alpha;）个符号。 这组d节点被称为此修复实例的辅助节点。从如此获得的一组dbeta;符号中，替换节点必须恢复存储在故障节点中的alpha;符号。为修复目的而下载的数据总量dbeta;称为修复带宽。
在[34]中显示，与再生编码相关的参数必须满足界限B，
（1）
由于存储和带宽都是有代价的，因此自然希望最小化alpha;和dbeta;，并尝试以相等的方式实现边界（1），即，
（2）
可以推导出（参见[34]）对于B和[n，k，d]的固定值，实现（2）导致存储空间alpha;和修复带宽dbeta;之间的折中。 对于B和[n，k，d]的固定值，如果参数（beta;，alpha;，B）满足（a）方程（2），并且（b），则再生编码被认为是最优的。 如果alpha;或beta;减小，（2）不能保持。 这种权衡的两个重要制度是其极端，称为最小带宽再生（MBR）和最小存储再生（MSR）制度，如下所述。
1）最小带宽再生（MBR）制度：注意，如果beta;lt;alpha;d（即，如果alpha;gt;dbeta;），则可以在不违反（2）的情况下减小参数alpha;。 因此，最佳再生编码的参数必须满足
（3）
最小带宽再生（MBR）方案对应于beta;取最小值的情况，即
dbeta;=alpha; （4）
在（2）中代入dbeta;的这个值得到
（5）
MBR制度需要尽可能小的修复带宽：替换节点下载的数据量不超过故障节点中存储的数据量。
2）最小存储再生（MSR）制度：当alpha;lt;（d-（k-1））beta;时，可以在不违反（2）的情况下减小参数beta;。因此，最佳再生编码的参数必须满足
alpha;ge;（d-k 1）beta; （6）
最小存储再生（MSR）方案对应于alpha;取最小值的情况，
alpha;=（d-k 1）beta; （7）
将这个alpha;值代入（2）给出
（8）
在这里，尽管术语“修复带宽”在文献中通常用于指代数量dbeta;，但它实际上指的是在修复过程期间下载的数据的总量。因此我们继续使用修复带宽这个术语以与先前的文献保持一致。
MSR机制允许最小可能的存储容量：能够从任何k个节点恢复所有B消息
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
