# From Counterfactuals to Trees: Competitive Analysis of Model Extraction Attacks

arXiv: https://arxiv.org/abs/2502.05325 · HTML: https://mlsanity.com/paper/2502.05325/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 34 references that are in the map.
- First posted on arXiv 7 Feb 2025.

## Builds on (most cited first, 20 of 20)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Stealing Machine Learning Models via Prediction APIs](https://mlsanity.com/paper/1609.02943/) (2016)
- [Explaining Machine Learning Classifiers through Diverse Counterfactual Explanations](https://mlsanity.com/paper/1905.07697/) (2019)
- [High Accuracy and High Fidelity Extraction of Neural Networks](https://mlsanity.com/paper/1909.01838/) (2019)
- [Stealing Part of a Production Language Model](https://mlsanity.com/paper/2403.06634/) (2024)
- [A Survey of Privacy Attacks in Machine Learning](https://mlsanity.com/paper/2007.07646/) (2020)
- [When the Curious Abandon Honesty: Federated Learning Is Not Private](https://mlsanity.com/paper/2112.02918/) (2021)
- [Model Reconstruction from Model Explanations](https://mlsanity.com/paper/1807.05185/) (2018)
- [I Know What You Trained Last Summer: A Survey on Stealing Machine Learning Models and Defences](https://mlsanity.com/paper/2206.08451/) (2022)
- [Model extraction from counterfactual explanations](https://mlsanity.com/paper/2009.01884/) (2020)
- [An Overview of Privacy in Machine Learning](https://mlsanity.com/paper/2005.08679/) (2020)
- [Born-Again Tree Ensembles](https://mlsanity.com/paper/2003.11132/) (2020)
- [Optimal Counterfactual Explanations in Tree Ensembles](https://mlsanity.com/paper/2106.06631/) (2021)
- [MEGEX: Data-Free Model Extraction Attack against Gradient-Based Explainable AI](https://mlsanity.com/paper/2107.08909/) (2021)
- [DualCF: Efficient Model Extraction Attack from Counterfactual Explanations](https://mlsanity.com/paper/2205.06504/) (2022)
- [On the Privacy Risks of Algorithmic Recourse](https://mlsanity.com/paper/2211.05427/) (2022)
- [Model Reconstruction Using Counterfactual Explanations: A Perspective From Polytope Theory](https://mlsanity.com/paper/2405.05369/) (2024)
- [Feature-based Learning for Diverse and Privacy-Preserving Counterfactual Explanations](https://mlsanity.com/paper/2209.13446/) (2022)
- [Trained Random Forests Completely Reveal your Dataset](https://mlsanity.com/paper/2402.19232/) (2024)
- [AUTOLYCUS: Exploiting Explainable AI (XAI) for Model Extraction Attacks against Interpretable Models](https://mlsanity.com/paper/2302.02162/) (2023)

## Built on by (most cited first, 3 of 3)

- [Linear Model Extraction via Factual and Counterfactual Queries](https://mlsanity.com/paper/2602.09748/) (2026)
- [RECAST: Model Reconstruction via Counterfactual-Aware Wasserstein Geometry under Limited Data](https://mlsanity.com/paper/2606.27948/) (2026)
- [SoK: Privacy Attacks on Machine Learning via Explainable AI](https://mlsanity.com/paper/2609.10627/) (2026)

## Abstract (arXiv)

The advent of Machine Learning as a Service (MLaaS) has heightened the trade-off between model explainability and security. In particular, explainability techniques, such as counterfactual explanations, inadvertently increase the risk of model extraction attacks, enabling unauthorized replication of proprietary models. In this paper, we formalize and characterize the risks and inherent complexity of model reconstruction, focusing on the "oracle'' queries required for faithfully inferring the underlying prediction function. We present the first formal analysis of model extraction attacks through the lens of competitive analysis, establishing a foundational framework to evaluate their efficiency. Focusing on models based on additive decision trees (e.g., decision trees, gradient boosting, and random forests), we introduce novel reconstruction algorithms that achieve provably perfect fidelity while demonstrating strong anytime performance. Our framework provides theoretical bounds on the query complexity for extracting tree-based model, offering new insights into the security vulnerabilities of their deployment.