Error resilience in distributed storage via rank-metric codes.

Natalia Silberstein, Ankit Singh Rawat, Sriram Vishwanath

TL;DR

This paper introduces a novel coding scheme for distributed storage systems (DSS) that enhances resilience against adversarial errors. By combining Maximum Rank Distance (MRD) codes with optimal repair MDS array codes, the scheme effectively handles both static (single-instance) and dynamic (repeated) adversarial attacks, achieving optimal resilience capacity for static errors and providing robust solutions for dynamic ones.

What Problem Does This Paper Address?

Distributed storage systems (DSS) are increasingly vital for storing vast amounts of data. While traditional approaches focus on resilience against node failures (e.g., disk crashes), a growing concern is adversarial attacks where malicious nodes intentionally corrupt data. A critical challenge in DSS is the "node repair process." When a node fails, data is reconstructed from surviving nodes. If an attacked node participates in this repair process, it can propagate corrupted data, potentially infecting other nodes and leading to widespread data loss. This paper tackles the problem of designing coding schemes that can tolerate such adversarial errors, especially considering the propagation issue during node repair.

Methods

The core of the proposed solution is a concatenated coding scheme. This involves two layers of encoding:

  1. Outer Code: Maximum Rank Distance (MRD) Codes: These codes, particularly Gabidulin MRD codes, are central to the scheme. Unlike traditional codes that focus on Hamming weight (number of differing bits), MRD codes operate in the "rank metric," which quantifies errors based on the rank of an error matrix. This is crucial because adversarial errors can manifest as complex matrix operations, and rank-metric codes are adept at correcting such errors. The paper leverages the property that MRD codes can correct errors up to a certain rank.
  2. Inner Code: Optimal Repair MDS Array Codes: These codes are designed for efficient node repair in DSS. They ensure that when a node fails, its data can be reconstructed by downloading a minimal amount of data from a small subset of surviving nodes. The paper uses "bandwidth-efficient" MDS array codes that operate at the Minimum Storage Regenerating (MSR) point, meaning they balance storage and repair bandwidth.

The scheme combines these two by first encoding the data with an MRD code and then encoding the output of the MRD code with an MDS array code.

For static errors (where an adversary pollutes a node's content only once), the concatenated scheme is proven to achieve an optimal upper bound on resilience capacity.

For dynamic errors (where an adversary can repeatedly pollute data during repair or reconstruction), two approaches are proposed:

  • Naïve Scheme: This approach leverages the redundancy provided by the outer MRD code to perform error-free node repair even in the presence of adversarial nodes.
  • Subspace Signatures Approach: This more advanced method combines MRD codes with subspace signatures (a cryptographic technique) to restrict the rank of errors introduced by adversarial nodes. This effectively limits the damage an adversary can inflict, allowing for reliable data recovery.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Rank Metric is Key for Adversarial Errors: The paper highlights that traditional Hamming-weight-based error correction is insufficient for sophisticated adversarial attacks. The rank metric, which captures the algebraic structure of errors, is essential for robust defense.
  • Concatenation for Layered Defense: Combining MRD codes (for algebraic error correction) with MDS array codes (for efficient storage and repair) creates a powerful, layered defense against various attack scenarios.
  • Node Repair is the Vulnerability: The paper emphasizes that the node repair process is a critical juncture where adversarial errors can propagate. The proposed scheme specifically addresses this by ensuring that even during repair, the system can recover correct data.
  • Subspace Signatures for Dynamic Error Control: The introduction of subspace signatures as a mechanism to bound the rank of errors introduced by dynamic adversaries is a significant contribution, offering a practical way to manage more complex attack models.
  • Optimality Achieved: The paper demonstrates that their construction for static errors achieves the theoretical upper bound on resilience capacity, indicating it's as good as possible under those conditions.

Key Results

  • The proposed concatenated coding scheme achieves optimal resilience capacity for distributed storage systems under the static error model (where an adversary pollutes a node's content only once).
  • For the more challenging dynamic error model (where an adversary can repeatedly pollute data), the paper presents two solutions: a "naïve" method and a more robust "subspace signatures" approach, both of which enhance error resilience.
  • The scheme is shown to be optimal in terms of resilience capacity when using MDS array codes as the inner code.
  • The paper also presents a construction for optimal locally repairable scalar codes based on MRD codes that can tolerate adversarial errors.

Limitations and Future Work

  • Dynamic Error Model Complexity: While solutions are proposed for dynamic errors, the paper acknowledges that this model is more complex. The "naïve" method is optimal only for specific parameter choices, and the subspace signature approach relies on the existence of a trusted verifier.
  • Practical Implementation of Subspace Signatures: The practical implementation and overhead of subspace signatures for large-scale DSS might be a consideration.
  • Passive Eavesdropper Resilience: The paper mentions that resilience against a passive eavesdropper using the subspace signature scheme is a subject of future research.
  • Generalization to Other Repair Models: While the construction works for any regenerating code, the paper focuses on MSR codes. Exploring its applicability to other repair models (like MBR) could be a future direction.

Summary updated

Abstract

This paper presents a novel coding scheme for distributed storage systems containing nodes with adversarial errors. The key challenge in such systems is the propagation of erroneous data from a single corrupted node to the rest of the system during a node repair process. This paper presents a concatenated coding scheme which is based on two types of codes: maximum rank distance (MRD) code as an outer code and optimal repair maximal distance separable (MDS) array code as an inner code. Given this, two different types of adversarial errors are considered: the first type considers an adversary that can replace the content of an affected node only once; while the second attack-type considers an adversary that can pollute data an unbounded number of times. This paper proves that the proposed coding scheme attains an upper bound on resilience capacity for the first type of error. Further, the paper presents mechanisms that combine this code with subspace signatures to achieve error resilience for the second type of errors. Finally, the paper concludes by presenting a construction based on MRD codes for optimal locally repairable scalar codes that can tolerate adversarial errors.
BibTeX
@inproceedings{silberstein2012error,
  author = {Natalia Silberstein and Ankit Singh Rawat and Sriram Vishwanath},
  title = {{Error resilience in distributed storage via rank-metric codes.}},
  booktitle = {Allerton Conference},
  year = {2012},
  doi = {10.1109/allerton.2012.6483348},
}
Figure