Attacking Byzantine Robust Aggregation in High Dimensions

Attacking Byzantine Robust Aggregation in High Dimensions

Speakers: Sarthak Choudhary; Aashish Kolluri; Prateek Saxena

Conference: IEEE S&P

YouTube: https://www.youtube.com/watch?v=f_4LveqFl5I

Overview

This talk, presented by Aashish Kolluri, Sarthak Choudhary, and Prateek Saxena, delves into critical vulnerabilities within Byzantine robust aggregation mechanisms, particularly in high-dimensional settings. Byzantine robust aggregation is a fundamental problem in distributed computing and machine learning, focusing on how to compute an accurate average of data points when a fraction of those points might be arbitrarily corrupted by an adversary. This problem is particularly pertinent to the robustness of Stochastic Gradient Descent (SGD) algorithms, which are foundational to training machine learning models, especially in distributed environments where malicious actors can poison gradients to manipulate model behavior.

The core challenge addressed in the presentation revolves around the tension between computational efficiency and the ability to maintain dimension-independent bias in high-dimensional data, a pervasive characteristic of modern machine learning models like large language models (LLMs) and computer vision networks with millions or even trillions of parameters. While theoretical advancements have proposed robust aggregators with strong guarantees, their practical implementation often sacrifices these guarantees for speed.

The research unveils two significant contributions: first, a fundamental computational vulnerability proving that any deterministic robust aggregator promising statistically optimal, dimension-independent bias will inherently be as computationally expensive as finding the direction of maximum variance, effectively making linear-time solutions impossible with current algorithmic knowledge. Second, the talk introduces Hydra, a novel attack specifically designed to expose that practical, optimized implementations of state-of-the-art filtering-based robust aggregators fail to provide dimension-independent bias, instead exhibiting bias that scales with the square root of the dimension. This finding has profound implications for the security and reliability of robust machine learning systems.

Background

▶ Watch: Introduction to Byzantine Robust Aggregation and applications (0:00)

The problem of Byzantine robust aggregation is a classical one, essential for scenarios where data points, represented as D-dimensional real-valued vectors, need to be averaged, but an adversary can arbitrarily corrupt an epsilon fraction of these points. This corruption can bias the computed mean, potentially to an arbitrary degree, measured by the L2 distance between the corrupted and benign means. The objective of robust aggregation is to design functions that operate on this corrupted data to produce an estimate of the mean with minimal bias.

A crucial application of this problem is in robust machine learning, particularly in distributed Stochastic Gradient Descent (SGD). In distributed SGD, gradients are computed locally on multiple devices and then aggregated at a central server to update a global model. An adversary controlling an epsilon fraction of these devices can send arbitrary, poisoned gradients. Such model poisoning attacks can be untargeted (aiming to reduce overall training accuracy) or targeted (e.g., backdoor attacks). Robust aggregators are vital in these settings to limit the bias introduced by poisoned gradients and mitigate the impact of such attacks.

The advent of modern machine learning models, especially Large Language Models (LLMs) and sophisticated computer vision models, has dramatically increased the dimensionality (D) of data points, often ranging into millions or even trillions. This high dimensionality presents a significant challenge for robust aggregation: balancing the computational complexity of aggregators with their ability to achieve a low, ideally dimension-independent bias.

Historically, initial attempts like coordinate-wise mean and median aggregators offered linear time complexity (O(N*D), where N is the number of data points), making them fast. However, their major drawback is that their bias increases proportionally to the square root of the dimension (sqrt(D)), rendering them suboptimal in high-dimensional settings.

A significant theoretical breakthrough came in 1960 with the proposal of the Tukey median. This aggregator achieves statistically optimal bias, meaning its bias is independent of the dimension. However, its computational time complexity is exponential in the number of dimensions, making it entirely impractical for real-world high-dimensional applications.

For a long time, there was no practical solution that combined optimal bias with feasible computation. This changed recently with the introduction of filtering-based aggregators in 2016. These methods were the first to achieve dimension-independent bias while maintaining polynomial time complexity (O(N*D^3)). The core idea behind these aggregators is to iteratively identify and filter out outliers along the direction of maximum variance. Despite being polynomial, the D^3 factor still makes them computationally demanding for extremely high dimensions. Consequently, even in contemporary high-dimensional machine learning, simpler coordinate-wise defenses are often still encountered due to the perceived impracticality of implementing filtering-based methods as-is. Nevertheless, recent practical implementations have claimed to significantly speed up these filtering-based defenses, running much faster than their theoretical O(N*D^3) bounds. It is these optimized implementations that the presented work critically examines.

Key Findings

▶ Watch: Filtering-based aggregators: theoretical breakthrough vs. practical limits (4:25)

The research makes two pivotal contributions that challenge the current understanding and implementation of Byzantine robust aggregation in high dimensions:

1. Uncovering a Fundamental Computational Vulnerability: The first key finding establishes a new, fundamental computational vulnerability inherent in the design of any deterministic strong robust aggregator that aims to provide statistically optimal, dimension-independent bias guarantees. The authors formally prove that such an aggregator, in the worst case, implicitly requires solving the problem of finding the direction of maximum variance of N D-dimensional vectors. Given the current state of knowledge, the best known algorithms for computing an almost exact maximum variance direction (e.g., finding the largest eigenvector of a covariance matrix) have a time complexity that is far from linear (e.g., O(D^3) in its direct form). This implies that designing a strong robust aggregator with a truly linear time complexity (O(N*D)) is not possible unless there is a significant, unforeseen breakthrough in algorithms for computing the direction of maximum variance. This finding provides a theoretical upper bound on the computational efficiency achievable by robust aggregators.

1. Hydra Attack Exposing Dimension-Dependent Bias in Practical Implementations: The second major finding directly addresses the claim that practical, optimized implementations of filtering-based robust aggregators provide dimension-independent bias. The authors demonstrate that these implementations do not uphold this crucial theoretical guarantee. To prove this, they developed a novel attack named Hydra.

• Hydra's Mechanism: Unlike prior attacks that often place corrupted points too far from the benign mean, causing them to be easily filtered out, Hydra strategically places corruptions within the filtering threshold of these aggregators. By analytically computing the precise position of these corruptions, Hydra ensures they do not increase the variance beyond the benign variance threshold, thereby evading detection and filtering. For untargeted attacks, Hydra chooses a corruption direction opposite to the estimated benign mean to maximize bias.
• Optimal Bias Generation: Hydra is provably capable of generating optimal bias against filtering-based robust aggregators, matching their theoretical upper bounds. Crucially, when applied to the practical implementations that employ optimizations like dimension chunking, Hydra generates a bias proportional to sqrt(D). This empirically demonstrates that these implementations, despite their speed, fundamentally fail to provide dimension-independent bias.
• Devastating Impact: Empirical evaluations on image classification tasks with CNNs (featuring millions of dimensions) show that Hydra can result in an over 70% drop in training accuracy with as little as 2% corrupted data points, significantly outperforming prior state-of-the-art attacks. This highlights the severe practical consequences of relying on these compromised implementations.

In essence, the research first establishes a theoretical barrier to designing perfectly robust and efficient aggregators and then proceeds to demonstrate that even the "efficient" versions currently in use fail to meet their advertised robustness guarantees in the face of a sophisticated, targeted attack.

Technical Deep Dive

▶ Watch: Two key research questions for robust aggregation (5:45)

Understanding the technical underpinnings of Byzantine robust aggregation requires grappling with the interplay of bias, variance, and computational complexity, especially when moving from one-dimensional to high-dimensional data.

At its core, Byzantine robust aggregation aims to estimate the true mean of a set of N D-dimensional vectors, despite an adversary corrupting an epsilon fraction of them. The adversary can manipulate these epsilon fraction of points arbitrarily, making the problem challenging. The quality of a robust aggregator is measured by the L2 distance (bias) between its estimate and the true benign mean.

Limits on Achievable Bias:

The talk highlights fundamental limits on the bias an aggregator can achieve. In one dimension, if the variance of the benign distribution is unbounded, an adversary can place a corrupted point arbitrarily far, causing an arbitrarily large mean shift. Therefore, it's critical that the benign distribution has a finite and small variance.

A known theoretical lower bound states that robust aggregators can never achieve a bias lower than order sqrt(Epsilon) times the benign variance. This can be intuitively understood by considering two benign input distributions that are statistically indistinguishable to an aggregator (i.e., they share 1 - 2*Epsilon fraction of points but differ in Epsilon fraction), yet their true means are separated by sqrt(Epsilon) times the variance. An aggregator cannot distinguish between these, thus cannot achieve lower bias.

The Failure of Coordinate-Wise Aggregation in High Dimensions:

A natural extension from single-dimension robust aggregation to high dimensions is coordinate-wise aggregation. This involves computing a robust estimate (e.g., median) for each dimension independently. While conceptually simple, this approach accumulates bias. If each dimension contributes order sqrt(Epsilon) bias, then across D dimensions, the total bias accumulates to be proportional to sqrt(D). This dimension-dependent bias makes coordinate-wise defenses highly suboptimal for high-dimensional data, as the bias grows with the data's inherent complexity.

Tukey Median's Optimal but Impractical Approach:

The Tukey median (1960) was a theoretical breakthrough because it achieved the statistically optimal, dimension-independent bias (order sqrt(Epsilon)). Its strategy was to consider projections onto all possible directions to find the mean. While robust, this comprehensive approach inherently leads to a computational time complexity that is exponential in D, rendering it infeasible for any practical high-dimensional application.

Filtering-Based Aggregators: The Polynomial Time Solution:

More recently, a line of work introduced filtering-based aggregators (e.g., in 2016) that promised dimension-independent bias in polynomial time. Their core insight is that instead of examining all possible directions, it might be sufficient to focus on top variance directions. The rationale is that corrupted points are more likely to appear as outliers along these directions.

The key idea of these aggregators is an iterative filtering process:

1. Compute Maximum Variance Direction: In each iteration, the aggregator computes the largest eigenvector of the current set of points' D-by-D covariance matrix. This eigenvector represents the direction of maximum variance.
2. Outlier Removal: Points whose projections onto this maximum variance direction exceed a predefined threshold are identified as outliers and removed. This threshold is typically proportional to the benign variance.
3. Iteration: Steps 1 and 2 are repeated with the remaining set of points until the maximum variance of the resulting set falls below the threshold.

The primary computational cost of these filtering-based aggregators stems from repeatedly computing the largest eigenvector of the covariance matrix. While this is polynomial, it typically results in a time complexity of O(N*D^3), which is still prohibitively high when N and D are in the millions, common in modern ML.

The Computational Vulnerability:

The researchers' first contribution directly addresses the feasibility of designing linear-time strong aggregators. They prove that any deterministic strong robust aggregator capable of providing dimension-independent bias will, in the worst case, be at least as computationally expensive as computing the almost exact largest eigenvector. This is shown through a reduction proof, where they construct specific "hard instances." If one had access to a deterministic strong aggregator, it could be used to compute the largest eigenvector for these instances. Since the best-known algorithms for this task have a complexity like O(D^3) (or similar, depending on the desired precision), this implies that achieving linear time complexity (O(N*D)) for a strong robust aggregator is fundamentally limited by the complexity of finding the maximum variance direction.

Practical Implementations' Optimization (and Vulnerability):

To circumvent the high O(N*D^3) theoretical cost, state-of-the-art implementations of filtering-based aggregators employ an optimization: dimension chunking. Instead of processing all D dimensions at once, they divide the total dimensions into smaller, manageable "chunks" (e.g., 1000 dimensions per chunk). The robust aggregation algorithm is then run independently on each chunk. This significantly speeds up the practical runtime, making these aggregators appear efficient. However, this optimization fundamentally changes the problem structure, and as Hydra demonstrates, it sacrifices the dimension-independent bias guarantee.

Demo / Proof of Concept

▶ Watch: Introducing Hydra: A new attack on filtering-based aggregators (8:00)

The talk's most compelling empirical contribution is the demonstration of Hydra, an attack specifically designed to expose the vulnerabilities in the practical implementations of filtering-based robust aggregators. Hydra's effectiveness lies in its sophisticated approach to evading the very filtering mechanisms designed to protect against such attacks.

Hydra's Key Idea: Evading Filtering Thresholds

Traditional attacks against robust aggregators often involve placing corrupted points far from the benign mean. However, filtering-based defenses are designed to detect and remove such extreme outliers. Hydra's innovation is to place corruptions within the threshold that these aggregators use for filtering. The threshold is typically proportional to the benign variance. By ensuring that the corrupted points do not increase the overall variance beyond this threshold, Hydra effectively bypasses the outlier detection mechanism. The researchers analytically compute the precise positions of these corruptions to achieve this stealth.

For an untargeted attack, which aims to reduce the training accuracy of the model, Hydra chooses the direction of corruption to be opposite to the estimated benign mean. This maximizes the bias in a direction that harms model performance.

Exploiting Dimension Chunking in Practical Implementations

The practical implementations of filtering-based aggregators, as discussed, achieve their speed by chunking the high-dimensional data into smaller, independent segments. Hydra exploits this. It applies its corruption strategy independently to each dimension chunk. If Hydra can generate a certain amount of bias within each chunk, and there are D / chunk_size chunks, the total bias generated by Hydra will scale proportionally to the number of chunks. Since the number of chunks scales linearly with the total dimension D (assuming constant chunk size), this means the total bias generated by Hydra scales with sqrt(D). This directly contradicts the theoretical claim of dimension-independent bias for filtering-based aggregators.

Empirical Evaluation and Devastating Results

The researchers rigorously evaluated Hydra against these optimized strong aggregators in various image classification tasks using Convolutional Neural Networks (CNNs). These models operate on data with dimensions ranging up to millions, providing a realistic testbed.

The evaluation had two primary goals:

1. To confirm that Hydra generates a large bias when strong aggregators are used as defenses during training.
2. To quantify the performance drop (e.g., training accuracy reduction) caused by this bias.

The results were stark:

• Optimal Bias Generation: The experiments empirically confirmed that Hydra successfully generates optimal bias against the implementations, and this bias indeed scales with sqrt(D). A presented graph vividly illustrates this, showing the bias increasing with the number of dimensions, with Hydra's performance closely matching the theoretical upper bound for dimension-dependent bias. This directly validates the claim that the implementations do not provide dimension-independent bias.
• Significant Performance Degradation: Perhaps most alarming for practitioners, Hydra demonstrated its ability to destroy model performance even at very low corruption rates. At just 2% corruptions, Hydra caused an astonishing 70% drop in training accuracy against these defenses. This level of reduction is substantially higher than what prior state-of-the-art attacks could achieve, underscoring the severity of the vulnerability exposed by Hydra.

The authors note that these observations were consistent across many other classification tasks, reinforcing the generalizability of Hydra's effectiveness.

In summary, Hydra serves as a powerful proof-of-concept, demonstrating that the pursuit of practical efficiency through optimizations like dimension chunking in robust aggregators comes at a significant security cost, fundamentally compromising their core promise of dimension-independent robustness.

Defensive Implications

▶ Watch: Hydra's impact: significant training accuracy drop and bias (9:00)

The findings presented in "Attacking Byzantine Robust Aggregation in High Dimensions" carry critical implications for defenders, particularly those involved in securing distributed machine learning systems against model poisoning attacks. The research highlights a crucial discrepancy between theoretical guarantees and practical realities, demanding a re-evaluation of current defense strategies.

First and foremost, the core message for defenders is to re-evaluate the robustness claims of practical implementations of filtering-based aggregators in high-dimensional machine learning settings. While filtering-based aggregators theoretically offer dimension-independent bias, their optimized implementations, which often employ techniques like dimension chunking to achieve faster runtime, demonstrably fail to uphold this guarantee. Defenders relying on these "fast" versions should be aware that their models are susceptible to attacks like Hydra, which can induce bias proportional to sqrt(D) and lead to severe performance degradation (e.g., 70% accuracy drop with only 2% corruption). The perceived efficiency gain comes at a significant, and often unacknowledged, security cost.

Secondly, the talk underscores the fundamental trade-off between computational complexity and robust guarantees. The finding that any deterministic strong robust aggregator inherently requires solving the maximum variance direction problem implies that achieving truly linear time complexity (O(N*D)) alongside dimension-independent bias is likely impossible with current algorithmic paradigms. This means defenders cannot simply expect to find a "silver bullet" aggregator that is both lightning-fast and perfectly robust in high dimensions. Instead, they must carefully consider this trade-off when selecting or designing aggregation mechanisms. This might involve accepting a higher computational cost for stronger robustness, or exploring new algorithmic approaches that can overcome the identified computational bottleneck without compromising security.

Thirdly, the nature of the Hydra attack provides valuable insights. Hydra is designed to expose a vulnerability by strategically placing corruptions within the filtering threshold. This suggests that simply increasing filtering thresholds or relying on basic outlier detection might not be sufficient. Defenders need to develop more sophisticated outlier detection mechanisms that are not easily bypassed by subtle, analytically computed corruptions. This could involve multi-dimensional outlier detection techniques or methods that are less reliant on variance-based thresholds alone.

Finally, while Hydra itself is an untargeted attack designed to demonstrate a vulnerability, its principles could potentially inform more targeted attacks. Defenders should recognize that if a sophisticated attacker can bypass the core filtering mechanism, they might be able to steer the model in arbitrary, malicious ways. Therefore, the focus should not just be on preventing accuracy drops but on ensuring the integrity and predictable behavior of the model. This necessitates a proactive approach to research and development of new, genuinely robust aggregation techniques, or significantly improving the security of existing practical implementations to truly deliver dimension-independent bias.

Key Takeaways

• Fundamental Computational Barrier: Achieving statistically optimal (dimension-independent) bias in deterministic robust aggregators is computationally expensive, requiring algorithms at least as complex as finding the maximum variance direction, making linear-time solutions currently infeasible.
• Practical Implementations Lack Robustness: Optimized, fast implementations of filtering-based robust aggregators, despite theoretical claims, do not provide dimension-independent bias; instead, they exhibit bias that scales with sqrt(D).
• Hydra Exploits Filtering Gaps: The Hydra attack bypasses filtering mechanisms by analytically placing corruptions within the defense's variance threshold, preventing their removal and maximizing bias.
• Chunking is a Vulnerability: Practical optimizations like dimension chunking, used to speed up aggregators, are critically exploited by Hydra, leading to dimension-dependent bias accumulation across chunks.
• Severe Performance Impact: Hydra can cause a drastic reduction in model performance, demonstrated by over a 70% drop in training accuracy with only 2% corrupted data points in high-dimensional image classification tasks.
• Re-evaluation of Defenses Needed: Defenders must re-evaluate the true robustness of deployed filtering-based aggregators in high-dimensional ML, acknowledging the significant trade-off between practical speed and security guarantees.

About the Speaker(s)

The research presented in this talk was a collaborative effort. Aashish Kolluri, a PhD student from the National University of Singapore, served as the primary presenter. He collaborated with Sarthak Choudhary and his adviser, Prateek Saxena, both also affiliated with the National University of Singapore. Their collective work focuses on advancing the understanding of security and robustness in complex computational systems, particularly within the domain of machine learning.