Research map / Learning theory and algorithms / Prediction and decision losses
From Counterfactuals to Trees: Competitive Analysis of Model Extraction Attacks
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes TRA, a divide-and-conquer model extraction attack that uses locally optimal counterfactual explanations to functionally equivalently reconstruct decision trees and tree ensembles, with a competitive-analysis framework bounding its query complexity.
Problem
Model extraction attacks on tree-based models often lack functional equivalence guarantees and rigorous query-complexity analysis, and counterfactual-based attacks use surrogates without fidelity guarantees.
Approach
Treat extraction as online discovery: a divide-and-conquer Tree Reconstruction Attack (TRA) splits the input space using locally optimal counterfactuals returned by an oracle, yielding provably perfect fidelity, and its query count is analyzed via competitive ratio against an omniscient offline algorithm.
Key results
- TRA reaches perfect functional equivalence on decision trees with orders of magnitude fewer queries than PathFinding (e.g., Adult depth-9 about 3.7e4 counterfactual queries vs. worst-case bound 2.45e14).
- On COMPAS random forests, TRA achieves fidelity 1.00 with about 74-148 queries, while CF and DualCF reach only fixed budgets of 3000 queries with fidelity below or near 1.00 on test data.
- TRA's competitive ratio is (2 prod(s_j+1) - 1)/(n+1), and no divide-and-conquer algorithm can beat this ratio.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use TRA instead of DualCF for random-forest extraction | COMPAS random forests · COMPAS random forests, 5–100 trees | queries: 73.60 vs 3000; 138.80 vs 3000; 147.60 vs 3000; 95.20 vs 3000; 129.60 vs 3000 | Helped |
| Use TRA instead of CF for random-forest extraction | COMPAS random forests · COMPAS random forests, 5–100 trees | queries: 73.60 vs 3000; 138.80 vs 3000; 147.60 vs 3000; 95.20 vs 3000; 129.60 vs 3000 | Helped |
| Use TRA instead of DualCF | COMPAS random forests · COMPAS random forests, 5–100 trees | uniform fidelity: 1.00 vs 1.00; 1.00 vs 0.99; 1.00 vs 0.99; 1.00 vs 1.00; 1.00 vs 1.00 | Mixed |
| Use TRA instead of CF | COMPAS random forests · COMPAS random forests, 5–100 trees | uniform fidelity: 1.00 vs 1.00 across the reported configurations | No clear effect |
| Use DiCE counterfactuals instead of OCEAN counterfactuals (ablation) | CF and DualCF surrogate attacks · Decision trees and random forests | fidelity | Helped |
| Use a surrogate from the target's hypothesis class instead of an MLP (ablation) | CF and DualCF · Decision trees and random forests | fidelity | Helped |
| Use target-matched hyperparameters instead of default surrogate hyperparameters (ablation) | CF and DualCF · Decision trees and random forests | fidelity | No clear effect |
| Enforce the target model's hyperparameters on the surrogate (ablation) | CF and DualCF · Some decision-tree and random-forest extraction experiments | fidelity | Hurt |
| Use locally optimal heuristic counterfactuals instead of globally optimal OCEAN counterfactuals (ablation) | TRA · Decision trees and random forests | anytime fidelity | Mixed |
| Use BFS query ordering (ablation) | TRA · Decision-tree extraction | anytime fidelity | Helped |
Surprising findings
- Non-optimal DiCE counterfactuals led to better surrogate fidelity than optimal OCEAN counterfactuals for CF and DualCF attacks.
- Knowing the target's hyperparameters did not help surrogate-based attacks (CF/DualCF) and could even slow convergence.
Limitations
- Worst-case query complexity is exponential in the number of splits (product over features), and empirical counts are far below it only on average.
- Results are limited to axis-parallel decision boundary models (trees and tree ensembles) and five binary classification datasets.
- Assumes the counterfactual oracle is reliable and returns locally optimal counterfactuals; the anytime guarantee depends on exploration order (BFS).
Experimental setup
Datasets: COMPAS Adult Income Default of Credit Card Clients German Credit Student Performance
Benchmarks: COMPAS Adult Income Default of Credit Card Clients German Credit Student Performance
Metrics: fidelity number of queries competitive ratio
Baselines: PathFinding CF DualCF
Builds on: PathFinding DualCF OCEAN
Closest papers by meaning
- SAME: Sample Reconstruction against Model Extraction Attacks (AAAI 2024 · similarity 0.86)
- Model Reconstruction Using Counterfactual Explanations: A Perspective From Polytope Theory (NeurIPS 2024 · similarity 0.85)
- HoneypotNet: Backdoor Attacks Against Model Extraction (AAAI 2025 · similarity 0.85)
- CEGA: A Cost-Effective Approach for Graph-Based Model Extraction and Acquisition (ICML 2025 · similarity 0.85)
- Exploring Query Efficient Data Generation Towards Data-Free Model Stealing in Hard Label Setting (AAAI 2025 · similarity 0.85)
- Reconstruction Attacks on Machine Unlearning: Simple Models are Vulnerable (NeurIPS 2024 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.