Abstract
As predictive models are increasingly being employed to make consequential decisions, there is a growing emphasis on developing techniques that can provide algorithmic recourse to affected individuals. While such recourses can be immensely beneficial to affected individuals, potential adversaries could also exploit these recourses to compromise privacy. In this work, we make the first attempt at investigating if and how an adversary can leverage recourses to infer private information about the underlying model's training data. To this end, we propose a series of novel membership inference attacks which leverage algorithmic recourse. More specifically, we extend the prior literature on membership inference attacks to the recourse setting by leveraging the distances between data instances and their corresponding counterfactuals output by state-of-the-art recourse methods. Extensive experimentation with real world and synthetic datasets demonstrates significant privacy leakage through recourses. Our work establishes unintended privacy leakage as an important risk in the widespread adoption of recourse methods.
Introduction
Machine learning models are increasingly used for high-stakes decisions like loan approvals or medical diagnoses. When a user receives an unfavorable decision, fairness and transparency standards often require algorithmic recourse: providing actionable steps (e.g., "increase your income by $5,000") to reverse the outcome. These are typically presented as "counterfactual explanations."
However, a critical tension exists: the information intended to help users also leaks sensitive details about the model's training data. This paper identifies a significant privacy backdoor where the distance between a user's data and their suggested recourse can be exploited to launch Membership Inference Attacks (MIA). These attacks allow an adversary to determine if a specific individual was part of the model's private training set.
Methodology: Counterfactual Distance-based Attacks
The authors introduce a new class of Counterfactual Distance-based (CFD) attacks, assuming a practical scenario where an adversary observes the recourse once. Two primary methods are proposed:
- CFD (Threshold-based): A straightforward attack that classifies an instance as a "member" if the distance to its suggested recourse exceeds a specific threshold. This relies on the intuition that models often "push" decision boundaries away from training points, making them further from counterfactuals than unseen test points.
- CFD LRT (Likelihood Ratio Test): A more advanced attack using "shadow models" to estimate the probability distribution of recourse distances for members and non-members. This allows for high precision even at low false-positive rates.
The study evaluates these attacks across three popular recourse algorithms—SCFE (gradient-based), GS (random search), and CCHVAE (latent space search)—on datasets including Adult (census), Heloc (credit risk), and Diabetes (hospital records).
Key Insights: The Mechanics of Leakage
The effectiveness of these attacks stems from several phenomena:
- The "Boundary Push": During training, models tend to maximize the margin around training instances, pushing the decision boundary further away. Consequently, training points often require a "longer walk" to reach a counterfactual.
- Recourse as a Proxy for Loss: Traditional MIAs require access to model loss or confidence scores. Recourse distance serves as a powerful proxy for this information, enabling attacks even when internal model metrics are hidden.
- Generative Model Dynamics: For methods like CCHVAE, which utilize Variational Autoencoders, the trend can reverse. Since the generative model learns the training distribution, counterfactuals for training points may actually be closer than for test points.
Experimental Results
Extensive testing reveals substantial privacy risks. On the Heloc dataset, the CFD LRT attack achieved True Positive Rates (TPR) significantly higher than random guessing. Specifically, at a 1% False Positive Rate, the TPR was 35% to 413% higher than random.
The research also found that:
- Overfitting exacerbates leakage: Models that overfit their training data leak more distance-based information.
- Dimensionality increases risk: The success of these attacks scales with the number of features, outperforming standard loss-based attacks in high-dimensional settings.
Defense and Future Work
Differential Privacy (DP) can theoretically bound the success of these attacks. However, implementing DP often results in a significant "utility-privacy tradeoff," reducing both model accuracy and the quality of the provided recourse.
Current limitations include a focus on tabular data and the dependency on the optimization quality of the recourse algorithm. Future research is needed to explore these risks in image and text domains and to find a middle ground that preserves both user utility and data privacy.
Summary updated