mlsanityData to 14 Oct 2026

From Counterfactuals to Trees: Competitive Analysis of Model Extraction Attacks

arXiv 2502.05325 ↗First posted 7 Feb 2025cs.LG cs.CRcited by 3

Not on the map. Why?

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.

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

20 of 34 references.

References · 20

  1. 2021Convex optimizationcited by 2,515
  2. 2016Stealing Machine Learning Models via Prediction APIscited by 619
  3. 2019Explaining Machine Learning Classifiers through Diverse Counterfactual Explanationscited by 614
  4. 2019High Accuracy and High Fidelity Extraction of Neural Networkscited by 214
  5. 2024Stealing Part of a Production Language Modelcited by 159
  6. 2020A Survey of Privacy Attacks in Machine Learningcited by 146
  7. 2021When the Curious Abandon Honesty: Federated Learning Is Not Privatecited by 127
  8. 2018Model Reconstruction from Model Explanationscited by 86
  9. 2022I Know What You Trained Last Summer: A Survey on Stealing Machine Learning Models and Defencescited by 75
  10. 2020Model extraction from counterfactual explanationscited by 47
  11. 2020An Overview of Privacy in Machine Learningcited by 39
  12. 2020Born-Again Tree Ensemblescited by 38
8 more
  1. 2021Optimal Counterfactual Explanations in Tree Ensemblescited by 36
  2. 2021MEGEX: Data-Free Model Extraction Attack against Gradient-Based Explainable AIcited by 35
  3. 2022DualCF: Efficient Model Extraction Attack from Counterfactual Explanationscited by 32
  4. 2022On the Privacy Risks of Algorithmic Recoursecited by 32
  5. 2024Model Reconstruction Using Counterfactual Explanations: A Perspective From Polytope Theorycited by 14
  6. 2022Feature-based Learning for Diverse and Privacy-Preserving Counterfactual Explanationscited by 11
  7. 2024Trained Random Forests Completely Reveal your Datasetcited by 11
  8. 2023AUTOLYCUS: Exploiting Explainable AI (XAI) for Model Extraction Attacks against Interpretable Modelscited by 9

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 3.

3 papers.

  1. 2026Linear Model Extraction via Factual and Counterfactual Queriescited by 2
  2. 2026RECAST: Model Reconstruction via Counterfactual-Aware Wasserstein Geometry under Limited Datacited by 0
  3. 2026SoK: Privacy Attacks on Machine Learning via Explainable AIcited by 0