On the Robustness of LDP Protocols for Numerical Attributes under Data Poisoning Attacks

On the Robustness of LDP Protocols for Numerical Attributes under Data Poisoning Attacks

Speakers: Buhan, Assistant Professor, Purdue University (with Shao Shaangi Satali and Ningui)

Conference: NDSS Symposium

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

Overview

This talk, presented by Buhan from Purdue University, delves into a critical and emerging threat to Local Differential Privacy (LDP) protocols: data poisoning attacks. While LDP is a cornerstone for privacy-preserving data collection, enabling servers to gather aggregate statistics without ever seeing individual raw data, this research uncovers a significant vulnerability. The traditional LDP threat model assumes honest users, but in reality, attackers can compromise a small fraction of users to inject manipulated data, thereby skewing the final statistical results. This talk addresses the profound implications of such attacks, which can lead to server distrust in LDP mechanisms and even suppress the opinions of legitimate users.

The core contribution of this work lies in advancing the understanding of LDP protocol robustness under these adversarial conditions. The researchers propose novel metrics for robust measurement, identify key design factors that enhance LDP security, and provide a framework for fair comparison of protocol performance. Their findings offer practical recommendations for deploying LDP in real-world scenarios and explore effective mitigation strategies, including a novel zero-shot detection method. This research is crucial for the continued secure and trustworthy adoption of LDP in various applications, particularly for numerical attribute distribution estimation.

Background

▶ Watch: Introduction to LDP and data poisoning threat (0:00)

Local Differential Privacy (LDP) is a strong privacy notion designed for decentralized data collection. Formally, an LDP randomized algorithm is considered ε-LDP if, for any two inputs x1 and x2, the probability of outputting the same result t is bounded by e to the power of ε. Here, ε (epsilon) represents the privacy budget, where a smaller ε signifies stronger privacy through the injection of more noise. The fundamental premise of LDP is that users individually perturb their data before sending it to a central server, ensuring the server never observes the true, sensitive information.

The conventional threat model for LDP assumes that users are honest and submit truthful (though noisy) data, and only the central server is untrusted. However, this assumption often breaks down in practice. The rise of data poisoning attacks introduces a more realistic and concerning threat model: attackers can compromise a small group of users (β percentage) and leverage their control over local LDP instances to inject carefully crafted fake values directly into the output domain of the LDP perturbation. This subverts the privacy guarantees and manipulates the aggregate results, leading to significant harm. For example, a server might receive false statistical insights, leading to incorrect decisions or a reluctance to trust LDP in the future. Honest users, especially those belonging to targeted groups, could experience stealthy censorship or suppression of their opinions.

Prior work has largely focused on discovering such attacks; however, this research shifts the focus to understanding and enhancing the robustness of LDP protocols against these attacks. The specific area of interest is the distribution estimation of numerical attributes, which is fundamental for many analytical tasks. The attacker's goal in this study is straightforward: to push the estimated distribution towards a specific extreme, such as the rightmost bin of the data domain. To provide a baseline for comparison, the researchers also consider an input poisoning attack, where attackers behave like honest users but supply false input data to the LDP instance, representing the minimum damage an attacker can inflict without bypassing the LDP perturbation mechanism. This distinction is crucial for understanding the advanced nature of output-domain poisoning.

Key Findings

▶ Watch: Research goals: investigating LDP protocol robustness (2:40)

The research yielded several significant findings regarding the robustness of state-of-the-art LDP protocols under data poisoning attacks, particularly for numerical attribute distribution estimation:

1. Superior Robustness of SSW and Server-Side Hash Protocols: Among all tested protocols, the SSW (Smoothly Weighted) mechanism and protocols employing a server-controlled hash function (specifically OH server and HST server) demonstrated the highest robustness against data poisoning. This indicates that their design inherently provides stronger resilience.

1. Critical Role of Smoothing Post-Processing: The smoothing step incorporated into the SSW protocol was identified as a key factor contributing to its enhanced security. This post-processing technique averages the frequencies of polluted bins with their surrounding bins, effectively diluting the impact of injected malicious data. The study emphasizes that such smoothing should be a deliberate consideration in future LDP protocol designs.

1. Impact of Server-Side Hash Function Selection: For protocols like OH and HST, having the server (rather than individual users) select the hash function significantly improves robustness. This reduces the attacker's freedom to strategically choose hash functions that target specific bins for manipulation, making it harder to mount effective poisoning attacks.

1. Vulnerability of User-Side Hash Protocols: Conversely, protocols where users select the hash function, such as GRR (Generalized Random Response), OE (Optimal Encoding), and the user-setting versions of HST (Hadamard Sketch Transformation) and OH (Optimized Hashing), were found to be the least robust. These protocols allow attackers greater control, enabling them to achieve theoretical maximum attack gains even with a small percentage of compromised users.

1. Hash Bin Size as a Security Parameter: For the OH protocol, the hash bin size (G) was identified as a novel design factor influencing security. Smaller values of G were observed to make the protocol more robust, suggesting that G can be tuned to balance security and utility requirements.

1. Effective Zero-Shot Detection: The proposed zero-shot detection method, which does not require prior knowledge of the underlying data distribution or the attacker's specific strategies, proved highly effective. It consistently outperformed baseline detection methods, particularly when the attacker's strength (higher β, lower ε) increased. While signals were weaker for inherently robust protocols, the method's ability to identify malicious behavior without pre-existing knowledge is a significant advancement.

Technical Deep Dive

▶ Watch: Detailed attack model for numerical attributes (4:00)

The research thoroughly investigates the robustness of LDP protocols by first defining the attack model and then introducing novel metrics for evaluation.

At its core, Local Differential Privacy (LDP) ensures individual privacy by requiring each user to perturb their data locally before transmission. For numerical attributes, this typically involves mapping the original value into a specific domain and then applying a randomized mechanism. A mechanism M is ε-LDP if for any two inputs x1, x2 and any output t in the range of M, Pr[M(x1) = t] ≤ e^ε * Pr[M(x2) = t]. The privacy budget ε directly dictates the level of noise injected; a smaller ε implies more noise and thus stronger privacy.

The data poisoning attack model considered here is sophisticated. Attackers control a β percentage of the total N users. Crucially, these attackers do not just feed false input data; they craft fake values directly in the output domain of the LDP perturbation. This is possible because compromised users control their local LDP instances and can bypass the honest randomization process. The attacker is assumed to know relevant system parameters, such as ε. The primary attack goal is to manipulate the aggregated distribution estimation, specifically by pushing the distribution towards an extreme, such as the rightmost bin. This is a targeted manipulation of the statistical outcome.

To quantify the impact of these attacks and assess protocol robustness, two key metrics were proposed:

1. Absolute Shift Gain (ASG): This metric directly measures the shift in the estimated data distribution before and after an attack. A higher ASG indicates a more effective attack and, consequently, lower protocol robustness. However, ASG is sensitive to the underlying data distribution and the percentage of malicious users (β), making direct comparisons across different settings challenging.

1. Shape Ratio: To overcome the limitations of ASG, the Shape Ratio was introduced. This metric normalizes the ASG of a given attack by the ASG achieved by a baseline input poisoning attack. The baseline represents the minimum damage an attacker can inflict by simply supplying false data to an honest LDP instance without bypassing the perturbation. By normalizing against this baseline, the Shape Ratio effectively measures the "attack gain" at a per-user level, making it independent of β and enabling fair robustness comparisons across diverse protocols and data distributions.

The study experimented with state-of-the-art LDP protocols for distribution estimation, broadly categorized into:

• Categorical Frequency Oracles with Binning: These include GRR (Generalized Random Response), OE (Optimal Encoding), HST (Hadamard Sketch Transformation), and OH (Optimized Hashing). For HST and OH, both "server setting" (server selects hash function) and "user setting" (user selects hash function) variants were evaluated, revealing a critical design choice.
• Direct Distribution Reconstruction: The SSW (Smoothly Weighted) mechanism falls into this category.

The analysis revealed compelling insights into protocol design:

• SSW's Robustness: The SSW protocol's strength against poisoning attacks largely stems from its smoothing step during post-processing. This step averages the frequencies of adjacent bins, effectively diffusing the impact of maliciously inflated bins. If an attacker pushes data into a specific bin, the smoothing process distributes this "pollution" across neighboring bins, reducing its concentrated effect.
• Server-Side Hash Selection: For protocols like OH and HST, having the server choose the hash function significantly restricts the attacker's ability. When the server dictates the hash function, the attacker loses the freedom to strategically select a hash that optimally maps their fake data to target bins, thus making the attack less precise and effective.
• User-Side Hash Vulnerabilities: Conversely, when users can select their hash functions (as in GRR, OE, and the user-setting variants of HST and OH), attackers gain a powerful lever. They can choose hash functions that maximize the impact of their injected data on specific target bins, leading to significantly higher attack gains and lower robustness. The talk notes that GRR, OE, and HST user can achieve the theoretical upper bound of the ASG, indicating maximum attack efficacy.
• Hash Bin Size (G) in OH: A novel finding was the influence of the hash bin size G in the OH protocol. The study demonstrated that a smaller G leads to greater robustness. This suggests that G is not merely a utility parameter but also a security dial that can be adjusted to achieve a desired balance between data utility and resilience against poisoning.
• Importance of Post-Processing: Beyond SSW, the general principle that post-processing steps, particularly those involving smoothing or aggregation across bins, can significantly boost security was highlighted. This is a crucial takeaway for future LDP protocol development.

Demo / Proof of Concept

▶ Watch: Experimental setup and state-of-the-art protocols (7:00)

While the talk did not feature a live software demonstration or a traditional proof-of-concept exploit of a real-world system, the speakers presented a comprehensive attack-driven robustness evaluation framework. This framework was used to simulate adversarial environments by implementing the proposed data poisoning attacks against various LDP protocols. The results of this rigorous experimental evaluation, using both synthetic and real-world datasets, served as the empirical proof of concept for the vulnerabilities and robustness characteristics discussed. The framework allowed for the quantitative measurement of attack efficacy using the ASG and Shape Ratio metrics, demonstrating the practical impact of data poisoning and the relative resilience of different LDP designs.

Furthermore, the research included the development and evaluation of a zero-shot detection mechanism to identify these attacks. This detection method acts as a proof of concept for a practical defense strategy. The core idea is to detect the statistical difference between the randomness introduced by legitimate LDP perturbation and the statistical properties of the fake data injected by attackers. The method involves conducting two rounds of reconstruction and measuring W1 distances between the perturbed results. By forming two groups of distances and using one as a benchmark (representing no attack), a two-sample Kolmogorov-Smirnov (KS) test is applied to detect malicious behavior. The results, presented as detection rates, clearly demonstrated that this zero-shot approach outperforms baseline detection methods across various scenarios, effectively proving its viability as a practical defense.

Defensive Implications

▶ Watch: Key findings: Most robust LDP protocols identified (8:00)

The findings of this research offer critical insights for defenders and LDP system designers aiming to build more secure and resilient privacy-preserving data collection systems.

First, protocol selection is paramount. When deploying LDP for numerical attribute distribution estimation, and especially when data poisoning attacks are a concern, practitioners should prioritize protocols demonstrated to be more robust. The study strongly recommends SSW and the server-setting variants of OH and HST (OH server, HST server). These protocols inherently offer greater resilience due to their design choices, such as post-processing smoothing or centralized control over hash function selection. Conversely, protocols like GRR, OE, and user-setting HST/OH should be approached with caution in high-risk environments, or their deployment should be coupled with robust detection and mitigation strategies.

Second, the research highlights key design factors that should be actively considered during the development of new LDP protocols or the refinement of existing ones. The importance of a smoothing step in post-processing cannot be overstated; it acts as a crucial defense mechanism by averaging out localized malicious data injections. Furthermore, for protocols employing hashing, the hash bin size (G) (as seen in OH) is not just a utility parameter but a security knob. Designers should experiment with smaller G values to enhance robustness, understanding the potential trade-off with data utility. The general principle of having the server control sensitive randomization parameters (like hash functions) rather than individual users is a significant security booster.

Third, the proposed zero-shot detection method provides a powerful tool for real-time or near real-time monitoring. Its "zero-shot" nature means it requires no prior knowledge of the underlying data distribution or the specific attack strategies, making it highly adaptable to unknown threats. Defenders can integrate this statistical detection mechanism into their LDP aggregation servers. By performing two-round reconstructions, calculating W1 distances, and applying a KS test, unusual statistical shifts indicative of data poisoning can be identified. This allows for early warning and potential intervention, even in environments where attack patterns are unpredictable. While detection signals might be weaker for inherently robust protocols, the method still provides valuable assurance.

Finally, the talk issues a broader call to action for the research community: to rethink the role of security in LDP design from its inception. Security considerations should not be an afterthought or a patch applied to existing protocols. Instead, they must be an integral part of the initial design phase. Beyond mere detection, the research emphasizes the need to systematically explore data recovery mechanisms. In scenarios where recollecting data is impossible, effective post-processing techniques could play a vital role not only in utility boosting but also in recovering as much useful information as possible from poisoned datasets. This proactive and holistic approach to security is essential for LDP to fulfill its promise of privacy-preserving data collection in a truly adversarial world.

Key Takeaways

• LDP is vulnerable to data poisoning attacks: Attackers controlling a small percentage of users can inject fake data in the LDP output domain, significantly manipulating aggregate results and eroding trust in LDP systems.
• SSW and server-controlled hash protocols are most robust: The SSW mechanism and protocols where the server selects the hash function (e.g., OH server, HST server) demonstrate superior resilience due to post-processing smoothing and reduced attacker control.
• Critical design factors for LDP security: The inclusion of a smoothing step in post-processing and considering hash bin size (G) as a security parameter (smaller G for more robustness) are crucial for enhancing LDP protocol security.
• Effective zero-shot detection is possible: A novel detection method, leveraging statistical differences between legitimate LDP randomness and fake data, can effectively identify poisoning attacks without prior knowledge of data or attack strategies, outperforming baseline approaches.
• Security must be foundational in LDP design: Future LDP protocols need to integrate security considerations from the outset, not as an add-on. This includes exploring systematic defenses like data recovery mechanisms in addition to attack detection.

About the Speaker(s)

The talk was presented by Buhan, an Assistant Professor at Purdue University. This research is a collaborative effort, with Buhan acknowledging his colleagues Shao Shaangi Satali and Ningui as co-authors on this joint work. Their collective expertise in privacy and security research contributes to the deep technical analysis presented in the talk.