From Counterfactuals to Trees: Competitive Analysis of Model Extraction Attacks
Authors: Awa Khouna
Julien Ferry
Thibaut Vidal
Venue: NeurIPS 2025 spotlight ()
Keywords: Model extraction attacks
Decision Trees
Counterfactual explanations
Competitive analysis
Primary area: social_and_economic_aspects_of_machine_learning
TL;DR: We propose efficient and effective functionally equivalent model extraction attacks against tree-based models, along with new formal analysis methods to characterize their efficiency.

Abstract: 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.

From Counterfactuals to Trees:
Competitive Analysis of Model Extraction Attacks
Awa Khouna Polytechnique Montréal awa. khouma@pollytl..ccmmmmmmmmooomm. ca
Julien Ferry Polytechnique Montréal julien ferry@polymtI.ca
Thibaut Vidal
Polytechnique Montréal thibaut. vidal @oollmpplmmm1....
Abstract
The advent of Machine Learning 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 ex- traction attacks, enabling unauthorized replication of proprictary models. In this paper, 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 founda- tional framework evaluate their efficiency. Focusing models based additive decision trees (e.g., decision trees, gradient boosting, and random forests), we in- troduce 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 models, offering new insights into the security vulnerabilities of their deployment.
Introduction
Recent research has shown that sharing trained machine learning (ML. models lead to the reconstruction sensitive training data, posing significant privacy risks [see, e.g., -oe.isch et al.) 2023 Carlini et al. [2024] Ferry al., 2024]. Applications in fields such medical diagnostics, financial services, and personalized advertising often handle large amounts of private data, making them attractive targets for data reconstruction attacks. These attacks exploit vulnerabilities in the model to recover confidential information from the training dataset, thereby undermining the privacy guarantees that organizations seek uphold. Consequently, organizations may prefer to utilize Machine Learning as Service (MLaaS) to leverage powerful models without directly exposing them, balancing the benefits of advanced analytics with the need protect sensitive information.
While Las platforms provide accessible and scalable MI. solutions, they must address the growing demand for explainability in their decision-mate maiiiinnnmminng processes. Regulatory frameworks such the EU AI Act's Article 13( further mandate greater transparency across a wide range of applications. In response, MLaaS providers increasingly incorporate explainability techniques behavior and ensure fairness. Notably, counterfactual explanations specify the changes an input example must undergo alter its prediction, thereby directly offering form of recourse in many real-life applications. However, studies have shown that querying model's explanations can enable attackers to replicate its parameters and architecture, effectively copying the original model [Tramèr et al. 2016 Wang et al. 2022 Aīvodji et al. 2020 Öksüz et al. 2024]. This reveals a critical tension between the need for transparency and the protection of model integrity and intellectual property.
elucidate model
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Model extraction attacks were proposed against a variety of ML models in recent years [ al. 2023]. While very few of them are functionally equivalent (i.e., they provably reconstruct the black-box model's s decision boundary), they often rely on strong assumptions, such as access to leaf identifier in the case of decision tree models (Tramèr et al. 2016]. Moreover, the majority of the literature focuses solely on empirically evaluating the fidelity of the extracted model w.r.t. the target black-box, lacking a rigorous framework for analyzing attack complexities and thoroughly characterizing their worst-case scenarios. Finally, while counterfactual explanations constitute promising attack surface and were exploited to conduct model extraction attacks [Aīvodji et al. 2020 Wang et al. 2022, Dissanayake and Dutta 2024), existing approaches rely training surrogate models without functional equivalence guarantees.
In this study, we address these limitations through the following key contributions:
We define a rigorous framework to characterize the complexity of model extraction attacks, utilizing competitive analysis (a notion from online optimization) to evaluate the difficulty of reconstructing models under various conditions.
We introduce novel algorithm (TRA) specifically designed to efficiently extract axis- parallel decision boundary models (including, but not limited to, tree ensemble models) through locally optimal counterfactual explanations.
We provide comprehensive theoretical analysis of our proposed method, offering guaran- tees on query complexity and demonstrating 100% fidelity in the extracted models.
We conduct extensive experiments to validate our theoretical findings. presenting an average- case and anytime performance analysis of TRA compared to state of the art reconstruction methods. These experiments not only confirm our theoretical results, but also provide practical insights into the effectiveness and limitations of our approach.
These contributions collectively highlight and permit us to better characterize security vulnerabilities in deploying explainable tree ensembles.
2 Online Discovery, Model Extraction Attacks and Competitive Analysis
Online discovery problems have long been a focus of research in thcoretical computer science, where the goal is uncover the structure of unknown environment through sequence of queries or observations [Ghosh and Klein 2010 Deng et al.) 1991]. A classic example arises in map exploration: an agent (e.g., robot) navigates a space cluttered with obstacles, with only limited "line of sight" at each position. The agent's 's objective is to construct a complete representation (e.g., map) of its surroundings while minimizing resources such travel distance exploration time.
Model extraction attacks on MLaaS platforms exhibit striking parallels to these online exploration tasks. In a typical model extraction attack, an adversary queries predictive model (the "black box") to gain information about its internal decision boundaries, effectively learning the decision function through a limited set of inputs and outputs. Drawing analogy to the map exploration scenario, each query in a model extraction attack can be likened to a "probe" in the space of features that reveals partial information about the region- -aaelly the predicted label or a counterfactual explanation identifying the closest boundary capable of changing the prediction. Figure |illlstraaes this connection by contrasting a rover's sensor sweep in polygon exploration task with query to locate a counterfactual explanation in a machine-learning model.
Online discovery problems & Model extraction attacks. Online discovery typically assumes an agent that can move freely in the physical world while receiving feedback about obstacles in its vicinity. In model extraction, the "environment" is the model's input space, and the queries return a point that lies on the nearest decision boundary (or provides the counterfactual boundary itself). Thus, while map exploration may allow richer geometric observations (e.g., an entire sensor sweep of obstacles), counterfactual-basee only the nearest boundary for given input). Despite these differences, both problems share common hallmark: the true structure (environment or decision boundaries) is unknown a priori and must be inferred online via carefully chosen queries.
model extraction often yields more constrained information (e.g.,
Competitive Analysis. A central tool for analyzing online discovery problems is competitive analysis [Kallin et al. 1986), which compares the performance of an online algorithm one that
2

---

Robot exploration
Model extraction
"Line of sight"
"Counterfacttal query"
Figure 1: Illustration of the connection between online discovery problems and model extraction attacks. Left (adapted from Tee and Han 2021]): an autonomous robot maps unknown 2D environment (e.g., a house) with limited-range sensors (e.g., LIDAR and laser distance measurements). Right: model extraction attacks recover the model's decision boundary via counterfactual queries.
adapts its decisions based solely on information acquired far to an optimal offline algorithm with complete foresight. Formally, we measure the ratio between: (i) the complexity (e.g., number of queries, computational cost) incurred by the online algorithm achieve goal and (ii) the minimal complexity that an offline algorithm, with complete foresight, would require to accomplish the same task. constant ratio implies a constant conpteattiooeeiiiiive algorithm; in more complex settings, the ratio may grow with problem parameters.
By applying competitive analysis model extraction attacks, counterfactuals or label predictions) are needed to guarantee perfect fidelity in model reconstruction under worst-case conditions, complementing empirical investigations. Moreover, competitive analysis encourages us to ask: How many queries, relative to an all-knowing attacker, does one need in order to prove with certainty that specific model has been recovered? This yields a principled measure of the difficulty of extracting tree-based models, analogous to classic results in online map discovery (Deng
quantify how many queries (i.e.,
al. 1991 Hoffmann al. 2001 Ghosh and Klein 2010 Fekete and Schmidt 2010].
Overall, this perspective paves the way for unified view: model extraction attacks can be seen as online exploration in the feature space. Our work, therefore, provides theoretical results for tree-based model extraction, and invites cross-pollination between the literature on online discovery algorithms and emerging threats in machine learning security.
Method
3.1 Problem Statement
We consider an input as an m-dimensional vector in the input space X' = Xi x X Xm C Rm and the output belongs to the categorical space y. Let J denote the of all axis-parallel decision boundary models, including decision trees and their ensembles, such as random forests [Breiman 2001). A machine learning (ML) classification model f E defined For simplicity and without loss of generality, we focus our discussion on decision trees, as any axis-parallel decision boundary model can be represented
function f x V.
decision tree (Vidal and Schiffer 2020).
The input space X' may comprise both categorical and continuous features.
Definition 3.1. Let d be a distance function and P(X') denote the set of all subsets of X. A counterfactual explanation oracle Oa is defined as a function O₂ : Fx X x P(X) + X. For a given model f E F, instance E X, and an input subspace & C X, x' = Oa(f, xx, ε) is counterfactual explanation such that x' E and fxx) # (x) This counterfactual is locally optimal if:
E such that V e 12 (0). ||||| s, f(x) f(a' + v) or d(z, x' + 2 d(z,
Intuitively, this condition ensures that any small perturbation (v) of a' either gives invalid counter- factual (having the same label as r) or increases the distance to the original input x.
For an adversary with black-box access to a target model (i.e., through prediction API), a model extraction attack aims to retrieve the exact model's parameters (Tramèr al., 2016). However, this goal is often too strict as many models might encode the same prediction function and thus

---

remain indistinguishable through counterfactual or prediction queries. Consequently, a more tractable objective, known as functionally equivalent extraction (Definition (.2)). focuses on reconstructing a model encoding the exact same function over the input space [Jagielski et al. 2020].
Definition 3.2. functionally equivalent extraction attack aims to reconstruct a model f E such that it is functionally identical to the target model f E F across the entire input space A. Formally, using as few queries as possible.
the attack seeks to find satisfying Equation
[
V/2 E X. f(x)=
- f(x)
A common way to empirically evaluate such attacks is through the fidelity [Aīvodji et al. 2020 of the model reconstructed by the attacker, coined the surrogate model. It is defined as the proportion of examples (from a given dataset) for which the surrogate agrees with the target model. To theoretically bound the efficiency of model extraction attack, additionally rely the notion of c-competittivenes from the online discovery literature, formalized in Definition 3.3
Definition 3.3. Let A denote an online model extraction attack algorithm. Define Q' as the number
of queries required by A to extract the decision boundary of model f. and let Qupt represent the minimal (optimal) number of queries necessary to extract f by an omniscient offline algorithm. The algorithm A is said to be c-competitive if, for any model f E F:
e S c- C'ppt
In this work, we focus on functionally equivalent model extraction attacks of axis-parallel decision boundary models. We assume that for each query æ to the API, the attacker obtains (i) the label f() of the query and (ii) a locally optimal counterfactual explanation x'.
3.2 Tree Reconstruction Attack algorithm
We now introduce our proposed Tree Reconstruction Attack (TRA), detailed in Algorithm [ TRA is a divide-and-conguee based algorithm that aims to reconstruct a decision tree fn with n split levels by systematically exploring the input space X. using only black-box API returning predictions and locally optimal counterfactuals. A split level is defined as particular value for a given feature that divides the input space into two subspaces. Note that multiple nodes within different branches of decision tree can share the same split level.
Algorithm Overview. TRA operates by maintaining query list Q that initially contains the entire input space X. The algorithm iteratively processes each input subset & C X' from Q. until Q is empty, ensuring that all decision boundaries of the target model f are identified and replicated in the reconstructed tree. More precisely, at each iteration, TRA first retrieves the subset & on top of the priority queue Q. It computes its geometric center æ using the center function (line 5). then queries the oracle O₂ with the target model f. input x, and subset & to obtain a counterfactual explanation x' Oalf xr E) (line 8). The set of feature indices where x' differs from x. i.c., {i 2 # x;) is consequently identified. For each differing feature i, TRA splits the input subset & into two subspaces based on the split value x! (SPLIT function, detailed in Algorithm 2 in the Appendix B). The resulting subspaces are added to Q for further exploration (line 9). If no counterfactual explanation x' exists within& &, TRA assigns the label y f() to E, indicating that it corresponds to leaf node in the reconstructed tree (line 11).
Illustrative Example.
To illustrate TRA's operation, consider the axis-paralled decision boundary model illustrated on the right side of Figure 2b Initially. TRA begins with the entire input space
(1))) (0.5, 0.5) of X and queries the counterfactual explanation oracle O I-11a- which returns a counterfactual (11 = (0.5, 0.4) that differs from (1) in the second feature (xz). This results in the first split of the input space (to E = 10, 1) x 00.4 1] and & = X' ΣΙ based on the condition I2 < 0.4, as shown on the left side of Figure 2b In the subsequent iterations, TRA focuses on the resulting subspaces. For example, within the subset where x2 > 0.4, TRA identifies another split at S 0.7, further partitioning the space. After three iterations, the reconstructed decision tree (shown in Figure 2ab accurately captures part of the decision boundaries of the target model, effectively distinguishing between different regions in the input space. The gray hatched zones (or "?" nodes) represent regions that have not yet been explored and remain in the query list Q.
X = [0, 1J2. In the first iteration, the algorithm selects the center point

---

Algorithm Tree Reconstruction Attack (TRA)
1: Input: Oracle Os. target model f X' + y
2: - {X) (Initialize query list with the entire input space)
3: repeat
4: & 2.pop(0) (Retrieve the next imput subset to investigate)
5:
æ - center(E") (Compute the center point of E]
6:
y f(x) (Obtain the label of the center point]
7:
if O,(f,z,E) exists then
8:
0alf.x.8 (Obtain counterfactual explanation)
9:
Q - insert(SPLIT(E, x')) (Split & and add the resulting subspaces to Q (Alg. 2
10: else
11:
Assign label y to the subset (No counterfactual found; & is leaf node)
end if
13:
until
Q is empty
22 < 0.4
(2)
m2h
0.4
0.7
0.7
(a) Decision tree reconstructed by
(b) Decision boundary of the model extracted by TRA after 3 iterations (Left) and of the target model f [0, 1] + {cr C2 (Right).
TRA after iterations.
Figure 2: Illustrative example of the execution of TRA.
Proposition 3.4. Let fa be decision tree with split levels across m-dimensional input space X X1 x X2 x ... x Xm- Denote s; as the number of split levels in fa over the i-th feature such m that ===1 8 The worst-case complexity Algorithm is (II 1)).
Corollary 3.5. The worst-case complexity of Algorithm
((1+ "")
The proofs of Proposition and Corollary 3.5 establishes first simple upper bound on the complexity of Algorithm [ Intuitively, consider two-dimensional decision boundary that partitions the space in a chessboard-like pattern of size 81 X 82. A comprehensive mapping of such space necessitates at least 81 x 82 queries (one in each sub-square). a requirement that holds for multi-class classification scenarios and in high-dimension.
provided in the Appendix A Proposition 3.4
Query Selection Analysis. An important hyperparameter of TRA is the strategy used to select query points within the input space. By default, TRA selects the geometrical center of the current input subset as the query point. Alternatively, one could choose other points such as the lower/upper left/right corners, even random point. In the following, the impact different query selection strategies on the algorithm's 's performance. To this end, we leverage the notion of competitive analysis for online discovery problems discussed in Section 2
present theoretical results analyzing
Proposition 3.6. For (n,m) E N2, Algorithm achieves a competitive ratio of C(a..)) defined as:
211 (s, +1
(1+
(n.m) TTRA
n+1
n
where is the number of split levels along the i-th feature within the tree fa-
mn) Proposition 3.7. For all n > 0 and m 2 2, no sivide-andtcoonqee--bsees algorithm can achieve
competitive ratio better than C CTRA
The proofs of Propositions 3.6 and 3.7 are provided in Appendix A Proposition 3.6 provides the competitive ratio achieved by the TRA algorithm, while Proposition establishes that the choice of

---

query position does not affect the competitive ratio for any divide-and-conge conquer algorithm iteratively partitioning the imput space. These propositions demonstrate that TRA not only offers a competitive approach to tree reconstruction under various query selection strategies, but also sets a theoretical limit that cannot be surpassed by other methods with a similar cnn-quu structure.
Since the query budget is often not known in advance and may vary depending on the target model, crucial for an extraction attack to operate in an anytime fashion- -tht is, to produce a usable classifier even if interrupted before completion. TRA satisfies this property by assigning provisional labels at each input space split (line 9 of Algorithm [T]: one subregion inherits the query's 's label, the other the counterfactual's ss This guarantees that valid decision tree classifier available any point during execution. The quality of intermediate classifiers depends on the ordering of the priority queue Q. In practice, preliminary experiments suggested good anytime performance using breadth-first search (BFS), which distributes the exploration evenly. While the design of alternative priority strategies is promising research direction to enhance ARA's anytime performance, the choice of exploration order does not impact the total number of queries required for exact reconstruction -this is solely determined by the algorithm's divide-and-conquee structure. Finally, we note that the fraction total volume corresponding to the leaf regions that have already been fully explored by TRA at given iteration directly lower bounds the proportion of feature space for which functional equivalence can be guaranteed in an anytime manner. In the case uniform data distribution over the feature space, this value also lower bounds the anytime surrogate fidelity, and one could use it to early stop TRA as soon as a target fidelity level is achieved.
Anytime Behavior.
Experiments
We now empirically evaluate the efficiency and effectiveness of our proposed TRA extraction attack and benchmark it against existing model extraction techniques. We first introduce the experimental setup, before discussing the results.
4.1 Experimental Setup
Datasets. We use five binary classification datasets, selected from related works model extraction attacks [Aivodji et al., 2020 Wang et al. 2022 Tramer et al. [0166] and encompassing variety of feature types, dimensionalities, and classification tasks, as summarized in Table I More precisely, we consider the COMPAS dataset [Angwin et al. 2016). as well as the Adult Income (Adult), Default of Credit Card Clients (Credit Card) German Credit and Student Performance (SPerformance) datasets from the UCI repository (Dua and Graff 2017]. Categorical features are one-hot encoded, while numerical, discrete (ordinal) and binary ones are natively handled by both tree building procedures and reconstruction attacks. Each dataset is partitioned into training, validation, and test sets with proportions of 60%, 20%, and 20%, respectively.
Table 1: Summary of the datasets used in our experiments. For each dataset, m is the number of features after pre-processing, encompassing mv numerical, ma binary, mc categorical (before one-hot encoding) and mp discrete (ordinal) ones. Each of the mc categorical features one-hot encoded into e, binary dimensions, where ej is the number of categories of feature j. As result, the mmc
total number of features becomes: m mN + mB + mD + 2j=1 Cj.
Dataset
#Samples
mN
m.
MC
M.D
Adult COMPAS
45222
41
2
2
4
3
5278
0
Credit Card
29623
14
0
3
0
11
German Credit
1000
19
1
0
3
5
SPerformance
395
43
0
13
4
13
Training the target tree-based models. We train two types of tree-based target models implemented in the scikit-learn library [Pedregosa et al., 201T]: decision trees and random forests. For decision trees, we experiment with varying max_ max_h parameters ranging from 4 to 10, as well as trees without maximum depth constraint (max (max_depth set to None). The random forests experiments focus on the COMPAS dataset, employing different numbers of trees (5, 25, 50, 75 and 100) to assess

---

scalability and robustness. To prevent overfitting, we utilize the validation set for hyperparameter tuning and apply costccompyy pruning where applicable. All the details of training procedures and hyperparameters configurations are discussed in Appendix C.I
Baselines. We benchmark TRA against three state-of-the-art model extraction attacks. First, PATHFINDING (Tramèr et al., 2016) is the only functionally equivalent model extraction attack against decision trees. While it does not rely on counterfactual examples, it assumes access to a leaf identifier indicating in which leaf of the target decision tree the query example falls. It is thus not applicable to random forests. Second, CF [iivodji al. 2020] leverages counterfactual explanations to build a labeled attack set and train surrogate model mimicking the target one. Third, DUALCF (Wang et al.] [022] enhances the CF approach by additionally computing the counterfactuals of the countertactuals themselves, which has been shown to improve fidelity. We adapt the number of queries (which must be pre-fixed for both CF and DUAL.CF) to the complexity of the target model as it is set to 50 times the number of nodes in the target decision tree. PATHFINDING is configured with <= 10-5 (pre-fixed precision of the retrieved splits) to achieve approximate functional equivalence.
We evaluate three surrogate model variants for CF and DUALCF: a multilayer perceptron (MLP), and two models from the same hypothesis class as the target model (i.e., a decision tree a random forest), one of them sharing the exact same hyperparameters, and the other using default hyperparameter values. These variants reflect different levels of adversarial knowledge: the hypothesis class, the exact hyperparameters, or neither. Both CF and DUAL CF were originally evaluated using heuristic counterfactual explanations from the DiCE (Mothilal et al., 2020] algorithm. To assess the impact of explanation optimality on the attack's performance, and to ensure fair comparisons, we tested these baselines using either DiCE or the OCEAN framework (Parmentier and Vidal [202]] which formulates counterfactual search as mixed-integer linear program and guarantees optimality.
Complete experimental results across all configurations of CF and DUALCF are reported in Ap- pendix C.2 They demonstrate that fitting surrogate models of the same hypothesis class facilitates the extraction of both decision trees and random forests. However, knowledge of their hyperparameters does not provide any advantage to either attack. Finally, the non-optimal counterfactuals provided by DiCE lead to better fidelity results than the optimal ones computed by OCEAN for these two attacks. This can be explained by their heuristic nature, which leads to the building of more diverse counterfactuals, not necessarily lying next to a decision boundary. In the next section, we display results only for the best- pesst-erformin configuration for both CF and DUALCF, achieved by training a surrogate model of the same hypothesis class and using DiCE counterfactuals.
Evaluation. We assess each model extraction attack using two metrics: fidelity and number of queries made the prediction and counterfactual oracle API during the attack. Fidelity measures the proportion of inputs for which the extracted model agrees with the target model, quantifying attack success. We compute fidelity over 3000 points sampled uniformly from the input space, providing a broad evaluation across the entire feature domain. For completeness, we also report fidelity measured on a test set (i.e., drawn from the data distribution) for our experiments using random forest target models, in Appendix C.3 which shows the same performance trends.
Counterfactual oracle. As discussed in Section 3.2 TRA requires the use of locally optimal coun- terfactual oracle. Since global optimality is a sufficient condition, we use the popular OCEAN oracle for simplicity in our main experiments with TRA. In Appendix D we report the performance of TRA using a simple heuristic oracle that produces locally optimal explanations. These experiments show that the choice of oracle (optimal or heuristic) has minimal impact on reconstruction performance.
All experiments are run on a computing cluster with homogeneous nodes using Intel Platinum 8260 Cascade Lake @ 2.4GHz CPU. Each run uses four threads and up to 4GB of RAM each (multi- threading is only used by the OCEAN oracle). We repeat each experiment five times with different random seeds and report average values. The source code reproduce all our experiments and under an MIT license.
figures is accessible at lhttps:///e //tp:s:///httt..t// http://ddaattteeeeteeeeeeeeeeeee
4.2 Results
Result TRA outperforms existing approaches in terms of number of queries and anytime fidelity to extract decision trees. Figure 3 presents the average fidelity of surrogate models obtained from the four studied model extraction attacks on decision trees, as a function of the number of queries, for the Adult and COMPAS datasets. Here, each point curve is the mean fidelity over
7

---

10
0.
Moan Route
0.7
0.6
0.1
162
16P
16f
16
14
102
30
#Queries
(a) Adult dataset
(b) COMPAS dataset
DualCF
PathAnnding
Figure 3: Anytime performance of all the considered model extraction attacks against decision trees.
109
#Quarias
301
107
301
337
1.00
200
330
400
500
600
100
200
300
400
530
(a) Adult dataset
TRA
PathFinding
(b) COMPAS dataset
Figure 4: Performance of the functionally equivalent model extraction attacks against decision trees. We report the number of queries required fully reconstruct the trees function of their size.
all 40 extraction tasks (eight tree depths x five seeds), when reaches 1.00, all target trees were perfectly reconstructed. Results for additional datasets, provided in Figure T2) (Appendix C.4). exhibit the same trends. Across all cases, TRA consistently achieves higher fidelity for any fixed query budget and converges perfect fidelity orders of magnitude faster. Notably, unlike CF and DUALCF, TRÁ and PATHFINDING provide formal guarantees of functional equivalence.
Result 2. TRA achieves state-of-the-art performance for functionally equivalent extraction of decision trees. Figure shows the number of queries required by PATHFINDING and TRA to achieve functionally equivalent model extraction, as a function of the number of nodes in the target models. Results for the Adult and COMPAS datasets are presented, with additional datasets provided in Figure [3] (Appendix (C.4). TRA consistently requires orders of magnitude fewer queries than PATHFINDING reconstruct the target models with perfect fidelity.
Result 3. TRA theoretically and empirically out- performs existing approaches to extract random forests. Figure 5jprssenss the average fidelity of the three considered model extraction attacks against dom forests, plotted against the number of performed queries for the COMPAS dataset. The results show that TRA achieves higher fidelity with fewer coun- terfactual queries and converges significantly faster to perfect fidelity. Moreover, TRA is the only attack that certifies functional equivalence for tree ensem- bles. Additional results in Figure [4] (Appendix C.4 indicate that TRA scales efficiently with the size of the target random forest, as the number of required queries grows sub-linearly with the total number nodes. This is due to structural redundancies in large forests, allowing the extracted model to repre- sented with perfect fidelity as more compact decision tree Vidal and Schiffer 2020
TBA
DuakC
0.90
30
10
307
*Cuntee
Figure 5: Anytime performance of the consid- ered model extraction attacks against random forests, on the COMPAS dataset.

---

Result 4. TRA is effective with either globally or locally optimal counterfactuals. We report in Appendix AopendiiDDrestiee rrsullts from experiments where TRA is run with simple oracle generating heuristic counterfactuals that are only locally optimal. The results (also provided within Figure for the COMPAS dataset) show that TRA's performance largely unaffected by the lack of global optimality. In some cases, locally optimal counterfactuals even improve early-stage (anytime) performance by introducing greater diversity in the explored input space. This highlights the practical applicability of TRA in real-world scenarios. Indeed, any valid but possibly sub-optimal counterfactual explanation can post-processed (through bisection line-searches over each feature using simple prediction queries) into locally optimal one lying the decision boundary. Therefore, long the counterfactual oracle is reliable (i.e., returns a counterfactual whenever one exists), the returned explanation reveals direction in which the prediction changes, which is then sufficient to locate nearby decision boundary and conduct an efficient model extraction attack with TRA.
425
300
TRA HEURISTIC
TRA,
TRA_OCEAN
(a) Anytime performance of TRA: average surro- gate fidelity as a function of the number of per- formed queries.
(b) Performance of TRA to achieve functional equivalence: each point represents the number of queries needed to fully reconstruct the trees.
Figure 6: Comparison of the performance of TRA using either OCEAN or a simpler heuristic counterfactual oracle (Algorithm in Appendix D) extract decision trees (COMPAS dataset).
Result 5. TRA often requires far fewer queries in practice than its theoretical worst-case bound. Across all datasets we evaluated, the number of counterfactual queries TRA uses to recover functionally equivalent model is substantially below the worst case of Proposition 3.4 Table reports the empirical query counts and the corresponding theoretical worst-case numbers for depth-9 decision trees (means over multiple random seeds). As evidenced, the former are consistently orders of magnitude smaller than the latter, suggesting that TRA is, on average, considerably more efficient than its theoretical worst-case.
Table 2: Empirical counterfactual query counts used by TRA versus the theoretical worst-case bound from Proposition 3.4 decision trees of maximum depth 9. Empirical values averaged over multiple random seeds.
Dataset
Empirical # queries
Worst-case queries (Prop. 3.4
SPerformance
1.16e + 03
3.02e + 08
Adult German Credit
3.70e 04
2.45e + 14
5.18e
2.86e + 03
Credit Card
6.97e +
6.49e + 11
COMPAS
1.53e + 02
1.07e + 03
5
Related Works
The flourishing literature on privacy in machine learning encompasses a wide variety of inference attacks, considering different setups and objectives [Cristofaro] 2020 Rigaki and Gareíal 2024). This paper focuses on model extraction attacks [Tramèr et al. 2016), which aim at reconstructing the decision boundary of a black-box target model as accurately as possible, given prediction API. As highlighted in recent surveys [Gong et al. 2020 Oliynyk et al. 2023 various attacks have been

---

proposed in recent years, targeting a broad spectrum of hypothesis classes. Hereafter, we focus on those targeting axis-parallel decision boundary models or exploiting counterfactual explanations.
Tramèr et al. (2016] propose the only functionally equivalent model extraction attack targeting regression or decision trees: PATHFINDING. It assumes that each query reply contains unique identifier for the associated leaf. In nutshell, PATHFINDING identifies the decision boundaries of each leaf in the target tree by varying the values of each feature. While effective, this method requires a large number of queries, though partial input queries can sometimes mitigate this overhead. In contrast, TRA does not make strong assumptions regarding the target model's prediction API, is able to extract any axis- axis-parallel decision boundary model (beyond decision trees), and uses orders of magnitude fewer queries by exploiting counterfactual explanations.
While many recent works have focused on generating counterfactual explanations (Guidotti 2024] these explanation techniques have also been shown to facilitate privacy attacks (Pawelczyk et al. 2023). Aivoddi et al. [2020] introduce CF, a model extraction attack that leverages counterfactual explanations. Their approach constructs labeled dataset by querying both predictions and counter- factuals from the target model, which is then used to train a surrogate. |Wang et al. [2022] extend this method with DUALCF, which improves fidelity by additionally querying the counterfactuals of the counterfactual explanations. However, neither CF nor DUALCF provide fidelity guarantees, and they also do not leverage the structural properties of the target model. Dissanayake and Duttal [2024] employ polytope theory to show that a sufficient number of optimal counterfactual explanations can approximate convex decision boundaries. They propose a model extraction attack against locally Lipschitz continuous models, with fidelity guarantees dependent on the Lipschitz constants of the target and surrogate models. However, functional equivalence cannot be strictly certified, and as the authors acknowledge, these guarantees do not apply to axis axis-parallel models (such as decision trees), which lack local Lipschitz continuity and convexity. Also note that their approach relies on globally optimal counterfactuals (whereas TRA accommodates locally optimal ones).
Finally, while beyond the scope of this paper, other explanation-basee model extraction attacks have been explored, including those relving on gradient- based [Milli et al. 2019 Miura et al. 2024 and other feature-based methods [Oksüz et al. 2024].
Conclusions and Discussion
We introduced the first functionally equivalent model extraction attack against decision trees and tree ensembles, leveraging locally optimal counterfactual explanations. In addition to its rigorous functional equivalence guarantee, the proposed method achieves higher fidelity than prior approaches while requiring fewer queries. We also leveraged well-established tools from online discovery to enable a formal analysis of model extraction, drawing analogy between the two fields. We illustrated the applicability and relevance of this analysis by providing bounds on our attack's efficiency compared to the best achievable strategy, relying on the notion of competitive ratio. This perspective is essential for formally characterizing and comparing model extraction attacks.
Our study demonstrates that optimal counterfactual explanations can be systematically exploited to reconstruct tree ensembles via query APIs, as they inherently reveal decision boundaries. This raises significant concerns, especially as explainability is increasingly mandated by regulations. In many real-world applications, counterfactual explanations serve as a natural mechanism to meet transparency requirements by providing recourse information. We discuss the broader societal impacts of our work in Appendix E
The research perspectives connected to our work are numerous. First, we believe that competitive analysis provides a valuable foundation for studying model extraction attacks, and future work should adopt the same lenses to evaluate other target models. Besides this, both the algorithms and their theoretical bounds could be refined. Improving input space exploration while mitigating worst-case query complexity is key direction, including strategies such as dynamically reordering TRA's priority queue to avoid worst-case scenarios, or adopting completely different exploration methods (beyond divide-and wandd-onnuer-buee based algorithms). Finally, investigating the impacts of privacy-presery mechanisms for counterfactual explanations [Vo et al. [2023] on model extraction attacks' success is crucial direction towards conciliating trustworthiness and privacy through ML explainability APIs.
10

---

Acknowledgments
This research was enabled by support provided by Calcul Quétec and the Digital Research Alliance of Canada, as well as funding from the SCALE AI Chair in DriveDriven Supply Chains. It was also supported by the Fonds de recherche du Québec - Nature et technologies (FRQNT) through a Team Research Project (327090).
References
UIrich Aivodji, Alexandre Bolot, and Sébastien Gambs. Model extraction from counterfactual explanations. CoRR, abs/2009.018%% 2020.
Julia Angwin, Jeff Larson, Surya Mattu, and Lauren Kirchner. Machine bias: There's software used across the country to predict future criminals. and it's biased against blacks. propublica (2016). ProPublica, May, 23, 2016.
Boenisch, A. Dziedzic, R. Schuster, A.S. Shamsabadi, Shumailov, and N. Papernot. When the curious abandon honesty: Federated learning is not private. In 8th IEEE European Symposium on Security and Privucy, pages 175-199. IEEE, 2023.
Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, Cambridge, 2004. ISBN 078-0521833783.
Leo Breiman. Random forests. Mach. Learn., 45(1):5-32, 2001.
Nicholas Carlini, Daniel Paleka, Krishnamurthy Dj Dvijotham, Thomas Steinke, Jonathan Hayase, A. Feder Cooper, Katherine Lee, Matthew Jagielski, Milad Nasr, Arthur Conmy, Eric Wallace, David Rolnick, and Florian Tramèr. Stealing part of production language model. In Forty- first International Conference on Machine Learning, ICML 2024, volume 235 of Proceedings of Machine Learning Research. PMLR, 2024.
Emiliano De Cristofaro. An overview of privacy machine learning. CoRR, abs/2005.08677 2020.
X. Deng, T. Kameda, and C. Papadimitriou. How to learn an unknown environment. In Proceedings of the 32nd Annual Symposium of Foundations of Computer Science, pages 298-303, 1991.
Pasan Dissanayake and Sanghamitra Dutta. Model reconstruction using counterfactual explanations: perspective from polytope theory. Advances in Neural Information Processing Systems (NeurIPS), 2024.
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. http:/tt:://rrrhie.. uci. edu/ml
Sándor P. Fekete and Christiane Schmidt. Polygon exploration with time-discrete vision. Compu- tational Geometry, 43(2): 148-168, 2010. ISSN 0925-7721. Special Issue on the 24th European Workshop on Computational Geometry (EuroCG'Os 08).
Julien Ferry, Ricardo Fukasawa, Timothée Pascal, and Thibaut Vidal. Trained random forests completely reveal your dataset. In Forty-first International Conference on Machine Learning, ICML 2024, volume 235 Proceedings of Machine Learning Research. PMLR, 2024.
Subir Kumar Ghosh and Rolf Klein. Online algorithms for searching and exploration in the plane. Computer Science Review, 4(4):189 2019 2010. ISSN 1574-0137.
Xueluan Gong, Qian Wang, Yanjiao Chen, Wang Yang, and Xinchang Jiang. Model extraction attacks and defenses on cloud-based machine learning models. IEEE Commun. Mag., 58(12):83-89, 2020.
Riccardo Guidotti. Counterfactual explanations and how to find them: literature review and bench- marking. Data Min. Knowl. Discov. 38(5):2770-2887 2024.
Frank Hoffmann, Christian lcking, Rolf Klein, and Klaus Kriegel. The polygon exploration problem. SIAM Journal on Computing, 31(2):577-600, 1001.

---

Matthew Jagielski, Nicholas Carlini, David Berthelot, Alex Kurakin, and Nicolas Papernot. High accuracy and high fidelity extraction of neural networks. In 29th USENIX Security Symposium, USENIX Security 2020, pages 1345-1362. USENIX Association, 2020.
Anna R. Karlin, Mark S. Manasse, Larry Rudolph, and Daniel D. Sleator. Competitive snoopy caching. In 27th Annual Symposium on Foundations of Computer Science (sfcs 1986), pages 244-254, 1986.
Smitha Milli, Ludwig Schmidt, Anca D. Dragan, and Moritz Hardt. Model reconstruction from model explanations. In Proceedings of the 2019 Conference on Fairness, Accountability, and Transparency, FAT* 2019, pages 1-9. ACM, 2019.
Takayuki Miura, Toshiki Shibahara, and Naoto Yanai. MEGEX: data-free model extraction attack against gradient- based explainable AI. In Proceedings of the 2nd ACM Workshop on Secure and Trustworthy Deep Learning Systems, SecTL 2024, pages 56-66. ACM, 2024.
Ramaravind K. Mothilal, Amit Sharma, and Chenhao Tan. Explaining machine learning classifiers through diverse counterfactual explanations. In Proceedings of the 2020 Conference on Fairness, Accountability, and Transparency, FAT 2020, pages 607-617. ACM, 2020.
Abdullah Çaglar Öksüz, Anisa Halimi, and Erman Ayday. AUTOLYCUS: exploiting explainable artificial intelligence (XAD) for model extraction attacks against interpretable models. Proc. Priv. Enhancing Technol., 2024(4):684-699 2024.
Daryna Oliynyk, Rudolf Mayer, and Andreas Rauber. I know what you trained last summer: A survey on stealing machine learning models and defences. ACM Comput. Surv., 55(149):324:1 2023.
Axel Parmentier and Thibaut Vidal. Optimal counterfactual explanations in tree ensembles. In 38th International Conference on Machine Learning, ICML 2021, volume 139 of Proceedings of Machine Learning Research, pages 8422 8431. PMLR, 2021.
Martin Pawelezyk, Himabindu Lakkaraju, and Seth Neel. On the privacy risks of algorithmic recourse. In International Conference on Artificial Intelligence and Statistics, AISTATS 2023, volume 206 of Proceedings of Machine Learning Research, pages 9680-9696. PMLR, 2023.
F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Pretten- hofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-2830. 2011.
Maria Rigaki and Sebastian García. A survey of privacy attacks in machine learning. ACM Comput. Surv. 56(4): 101:)):001:1111::: 2024.
Yi Kiat Tee and Yi Chiew Han. Lidar-based 2d slam for mobile robot in indoor environment: A review. In 202/ International Conference on Green Energy, Computing and Sustainable Technology (GECOST), pages 1-7. IEEE, 2021.
Florian Tramèr, Fan Zhang, Ari Juels, Michael K. Reiter, and Thomas Ristenpart. Stealing machine learning models via prediction APIs. In 25th USENIX Security Symposium, USENIX Security 2016, pages 601-618 USENIX Association, 2016.
Thibaut Vidal and Maximilian Schiffer. Born-again tree ensembles. In 37th International Conference on Machine Learning, ICML 2020, volume 1 19 of Proceedings of Machine Learning Research, pages 9743-9753. PMLR, 2020.
Vy Vo, Trung Le, Van Nguyen. He Zhao, Edwin V. Bonilla, Gholamreza Haffari, and Dinh Phung. Feature-basee learning for diverse and privacy-preserving counterfactual explanations. In P Proceed- ings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD 2023, page 2211 1 1-2222. Association for Computing Machinery, 2023.
Yongjie Wang, Hangwei Qian, and Chunyan Miao. Dualef: Efficient model extraction attack from counterfactual explanations. Proceedings of the 2022 Conference on Fairness, Accountability. and Transparency. FAccT 2022, pages
ACM, 2022.
12

---

A Proofs
Proposition 3.4. Let fn be a decision tree with n split levels across a m-dimensional input space X' X1 X2 x... Xm- Denote as the number of split levels in fa over the i-th feature, such
that 2 8 = n. The worst-case complexity of Algorithm is O (1 (s,+))
Proof of Proposition 3.4 We prove the proposition by induction on the number of split levels n. For clarity and precision, denote the number of splits in the i-th dimension for decision tree with split levels as a!m) rather than simply using 85.
Base Case (n 1): For n = 1, there exists a single feature with jj and 8 for all + j. The number of queries required is at most = 2 += 0
Inductive Step: Assume the statement holds for all trees with up to split levels. Consider a tree fn+1 with n + split levels. Let S I m be the feature index of the first detected split (I, S a) where R, dividing X' into two subspaces:
X3 = fx E X x3 S a), X3 = E >a.
Each subspace contains subtrees fnz and fnz with R1; tively. By the inductive hypothesis, the number of queries for each subtree is respectively [II (s} (m) + +1) and O (II (s, (s/ma) +1)).
split levels, respec-
Since f-+1)= $) 8) + 1 and (ng) (a+1) for # (and q E {1,2}), the total (m1) (m2)
s;
number of queries for fn+1 is:
m ( [16+
(s(") Therefore, the query count for extracting fn is O (IIm (s + +1))
Corollary 3.S. The worst-case complexity of Algorithm
is O ((1 =
We build on the worst-case complexity demonstrated in Proposition 3.4 and we solve the following optimization problem:
Proof of Corollary
3.5
max
II 88
+1)
s.t.
= and a( 2 Vi (m...,mm
Since maximizing positive value is equivalent to maximizing its logarithm, we transform the objective into:
(n) + 1). log(s
Applying the Karush-Kull Kuhn- Tucker (KKT) conditions [Boyd and Vandenberghe [004], we find that the maximum occurs when sf (n) for all i. Substituting back, the worst-case complexity becomes ((th + ")
Proposition 3.6. For (n, m) N?, Algorithm achieves competitive ratio of CTRA defined as:
m)))
2 21I,-1s,
(s, + 1) (1
(a.m)
TTAA
n
n1 n+1
where s; is the number of split levels along the i-th feature within the tree fn-
13

---

Proof of Proposition 3.6. Let > 0, m 2 1, denote a,,..., On the tree split levels (decision thresholds) and for each feature = ...... m. let 8; represent the number of splits the j-th dimension, ordered such that 81 2 2 ... 8m. Without loss of generality, assume that the split levels are grouped by dimension. Specifically, splits aj to Os₁ occur in the first dimension, splits 011+1 to +21+ in the second dimension, and so on. Additionally, within each dimension, the split levels are sorted in increasing order, i.c.,
J-1 Σ ss
AA $i m,
Sir Op < aptl.
1. Proof of Upper Bound: In the best-case scenario, where each split level appears exactly once in the decision tree (i.e., there no redundancy among the tree nodes), the omniscient algorithm (a.k.a optimal algorithm) would require at least + queries to reconstruct the tree:
Q n
This includes one query for each leaf to verify its label and certify functional equivalence. Note that this assumes that the omniscient algorithm has correctly guessed the location of each split level and directly queried for counterfactuals over each leaf region.
Conversely, in the worst-case scenario, such as chessboard-like decision splits are evenly distributed across multiple features, the TRA algorithm must explore all possible regions created by these splits. For two-dimensional tree, this results in + (2( + 1) + (s1 + (s2 + 1) queries, where and are the number of splits along each feature. The 81 splits along the first dimension are first detected, then the 82 splits along the second dimension are re-discovered at every sub-division performed along the first dimension, and finally (81 + +)(222 1) queries are required individually verify each sub-square (leaf node). Extending this to m dimensions, the number of queries grows multiplicatively with the number of splits per feature, leading to:
where
m
m = 2 (8) = j=1
7
QTRA
81 II
(s)
+ 1) II
-1
Therefore, the competitive ratio CYRA is bounded above by:
@rua Qopt.
21I (8y 1) -1
(3)
n+1
2. Proof of Lower Bound: We hereafter build an adversarial example, i.e., one that maximizes the ratio of the number of queries that TRA must perform to extract the target decision tree, compared to what an optimal offline algorithm could achieve. This example therefore constitutes (feasible) lower bound for the competitive ratio of TRA.
Consider tree with splits. An adversary (dynamically building the worst-case instance the online algorithm is run on) can arrange the splits such that the first split detected by TRA is the last decision node in the tree. Specifically, the adversary ensures that the initial split does not reduce the complexity of identifying the remaining n splits.
Consider the following adversarial example: for each 1 S p S and S m, let the dimension that ap splits on be j. and set
if 1
0p
+1)+ + otherwise,
where >> 0. This adversarial example ensures that within any hyper-rectangle defined by split level boundaries, for I,... m 1 if there are splits both the j-th and j + 1-th dimensions, then there exists a split in the j-th dimension that is closer to the center of the hyper-rectangle than any split in the j+ 1-th dimension. As a consequence, TRA will always detect the splits of the j-th dimension before those of the + 1-th dimension. Therefore,
14

---

the adversary can design decision tree with a single branch (as illustrated in the right tree of Figure 7 that begins by splitting on the split levels in reverse (decreasing) order of dimensions (see 2D example in Figure 7 For this specific example, TRA will require
TR
II j=1
+1)
queries, whereas the optimal offline algorithm only needs n + queries. Therefore, by the definition of competitive ratio:
2 2 +
(n).m) TRA
(4)
n+1 1
Hence, by 33 and (4 have:
2 2 (3j + +1 -1
TRA
+1
T2
On
$2
[0x++ +1
F2 S Ou-
U2 S ac++
I Oz
m1 S m
022 Qa1
81
Figure 7: Adversarial example for TRA (displayed for = 2 dimensions). The classes C1
C2
and C3 For simplicity, we denote s (n) and $2 s2 (n) Here, the instance is dynamically built so that the number queries required by TRA 82(81 + 1) + 81 + (s) + 1)(82 + 1), whereas the optimal offline algorithm only needs + queries to check the leaf labels and certify functional equivalence, as shown in the right tree figure.
Proposition 3.7. For all n > and m 2 2, no divide-andd-ooquer-bbee algorithm can achieve a (n.m)
competitive ratio better than CTRA
Proof of Proposition 3.7 Key Idea. pure dividc-and-conquee (D&C) algorithm discovers a split along specific feature dimension upon querying point. This split divides the input space into two subproblems. An adversary can strategically arrange the splits so that the feature splits detected by the algorithm early on the "least helpful" ones, meaning they occur the last decisions along their respective feature branches. By doing this, the adversary ensures that these initial splits do not simplify the identification of the remaining splits. We demonstrate that this construction forces the D&C algorithm to perform poorly compared to an optimal strategy.
We define pure D&C-ba algorithm as one that divides the input space (problem) into subspaces pubb-problems) based on counterfactual explanations and recursively continues this process within each subspace until no counterfactuals are found. This class of algorithms encompasses all types of
15

---

querying strategies, such as selecting the geometrical center (as done by TRA), but also selecting the top-left comner bottom-rigee right corner, random point within the input space, among others.
Proof. Let m > be the number of dimensions and n. 2 m be the number of split levels. We prove this proposition by induction the number of split levels O.
2): Consider a two-dimensional tree with split levels oi and 0lg- Let q (91, 42) be the query made by the D&C algorithm. The adversary chooses 01 = 91 + 61 and 0r Q2 + Eg. where E2 > E1 > Consequently, the first counterfactual explanation returned by the oracle is o' = (01. 92) The algorithm then splits the input space into two subspaces, both containing the split at dz2, depicted Figure 8
Base Case (n 2.
T2 S
02
022
C3
C1
21
0
(a) Adversarial decision tree.
(b) Decision Boundary of the adversarial decision tree.
Figure 8: adversarial example for 2, triggering the worst-case competitive ratio of our algorithm.
In this adversarial example, the D&C algorithm requires least 7 queries reconstruct the exact decision tree, whereas an omniscient optimal algorithm can achieve this with only queries, one per leaf. Therefore, for this adversarial example, no D&C-based algorithm can attain a competitive ratio better than CTRA CTRA
Inductive Step: Assume the proposition holds for all trees with up to n split levels. Consider tree with n-+1 1 split levels, with split levels (a1,..., an+1). Let (41, . qm) X be the first query made by the D&C algorithm. The adversary sets an Q1 + e1 where 61 > and returns the counterfactual explanation q' (an, 02. 9m.. The adversary places this split as the last decision node in the tree. Consequently, the D&C algorithm splits the input space into subspaces, each containing all splits of the remaining dimensions, thereby containing at most n splits each.
By the induction hypothesis, the algorithm will require least:
m
Q 2 +1) (s) 11-1
f=2
for the first subspace, and
m Q2 2 + +1)
(1)
j=
for the second subspace, where 8f" and 1 are the remaining splits along the first dimension in the first and second subspaces, respectively.
16

---

Therefore, the total number of queries is:
+1 11)+)) (n + (m.)))
1 Q1 Q2 =
(5)
==1
given that sf" + - + $1. Hence, by and
((.m) (5, the best competitive ratio C
D&C
achievable by any DaC-based algorithm satisfies:
(n + L)CTRA
cdrm) D&C
cn.m)
TRA
B Details of the SPLIT Procedure (Used by TRA)
Given a region &, query x, and its counterfactual x', SPLIT partitions into disjoint subregions by iterating over features where x and æ' differ, peeling off the half that contains x and keeping the complementary half (the side toward x²). The exact pseudo-code of this procedure is provided in Algorithm
Algorithm 2 SPLIT(E, x.)
Require: Region E: vectors x, x'.
Ensure: List E of disjoint subregions whose union is &.
1: S f { (i, x a, f ot } (indices and thresholds where x' differ)
2: Eu 4 θ,
3: for vi, E do
4: if < v then
5:
& < { E Ep
2; S $
6:
else
7:
& < { = E Ep
24 >>>00 m}
8:
end if
9:
E + E } (peel off the side containing x)
En f Eo \ El (keep the remainder (toward x²))
11: end for
E E {Ea} (add the final remainder)
13: return E
Tie-handling.
To avoid overlaps v, we use consistent rule (e.g.. S on one side and > on the other). In numerical implementations, we replace the strict inequality (2; > v) with relaxed one z 2 u + for small
C Additional Experimental Results
C.1 Experimental Setup Details
Target Model Training. During the training process of both decision trees and random forests, we conduct grid search with 50 steps the range [0, 0.2] determine the optimal cost-complexity pruning parameter ccp_al that maximizes accuracy on the validation dataset.
Surrogate Model Training. For surrogate models (used by the CF and DUALCF attacks) that do not utilize target model's hyperparameters, we employ the default parameters provided by the scikit-learn Python library (Pedregosa et al. 2011]. Specifically for MIPs, we configure a scikit-learn ML.P with two hidden layers, each consisting of neurons, while keeping all other parameters at their default values.
17

---

Anytime Fidelity. The anytime fidelity was calculated each 20 queries during all attacks execution, except for PATHFINDING which not an anytime attack. Let N denote the number of target models f2, JN to extract (i.e., over all considered experimental configurations and random seeds) and D dataset with n samples. The anytime fidelity of given model extraction attack (at a given time step) over D is calculated as follows:
1
1 (((e)))
(6)
where fi; f2, f2,...,,ffr are the models extracted by the considered model extraction attack at the given time step.
C.2 Configuration of Surrogate-Basee Attacks
We report in Figure | (respectively, Figure TOp the anytime performance of the CF (respectively. DUALCF) model extraction attack against decision tree models, for the three considered types of surrogates and the counterfactual oracles, on all considered datasets. More precisely, depicted in Section 4.1 we run these two attacks using three different assumptions on adversarial knowledge, namely the hypothesis class of the target model, its hyperparameters, and none of them. In the first case, the adversary trains a decision tree surrogate with default parameters (DT). In the second case, he trains a surrogate decision tree with the exact same hyperparameters (DT+), Finally, in the third case, a multi-layer perceptron (MLP) is used as surrogate model. Both CF and DUALCF were originally tested using the DICE (Mothial al. 2020 counterfactual oracle, which provides heuristic-bar -bated (non-optimal) counterfactual explanations. To assess the impact of explanation optimality on the attack's performance, and ensure fair comparisons, we run CF and DUALCF both using DiCE and using optimal counterfactual explanations computed with the OCEAN framework [Parmentier and Vidal 202T
the target model
We also report in Figure the anytime performance of the CF and DUALCC model extraction attacks against random forest models, for the three considered types of surrogates and the two counterfactual oracles, on the COMPAS dataset.
We hereafter highlight the key trends of these results, focusing the impact of two dimensions: the adversarial knowledge (regarding the target model's architecture and hyperparameters) and the type of counterfactual oracle used.
Knowledge of the target model architecture and hyperparameters. One first important trend that is consistent across both CF and DUALCF, and for both decision trees and random forests, is that knowledge of the hypothesis class of the target model helps fitting a surrogate with high fidelity. Indeed, as can be observed in Figures 9 10 and IT the MLP surrogate always under- perforrss compared to the decision trees or random forests ones. Indeed, fitting a surrogate model of the same type facilitated by the fact that the shapes of its decision boundaries are the same as the target model, e.g., pirsalalllll splits for tree-based models. Interestingly, knowledge of the hyperparameters of the target decision tree or random forests does not seem to help fitting the surrogate. Indeed, in most experiments, the surrogate sharing the same hypothesis class as the target model (i.e., DT or RF) and the surrogate sharing both the hypothesis class and the hyperparameters (i.e., DT+ or RF+) have very close performances. Furthermore, imposing the target model's hyperparameters to the trained surrogate can even be counterproductive, as can be seen in Figures 9a and 9b for instance. In such cases, the fact that surrogate learning is more constrained due the enforced hyperparameters (e.g., maximum depth) seems to slow its convergence towards very high fidelity values. This is consistent with previous findings: for instance, [Aivodji et al. [2020) observed that knowledge of the architecture of a target neural network did not provide a significant advantage to the CF model extraction attack.
Optimality of the counterfactuals. The results in Figures 10 and suggest that the non-optimal counterfactual explanations returned by DiCE helped fitting the extracted surrogate models better than the optimal ones provided by OCEAN. Indeed, for a fixed query budget and surrogate type, the performances of the extracted model are often better when fitted with DiCE counterfactuals than with OCEAN ones. Although some variations appear, this finding generally verified for all the studied types of surrogates, for both decision trees and random forests target models, and for both the
18

---

0.9
09
0.7
0.7
0.6
Moan
0.4
0.2
02
#oueress
(a) Adult dataset
(b) COMPAS dataset
0.9
0.
0.8
Weat Poddlt
0.4
0.4
0.2
02
0.1
#Queries
Aquarress
(c) Credit Card dataset
(d) German Credit datasct
0.9
0.5
0.7
0.6
0.4
0.3
0.2
0.1
10c
#Quefees
(e) Student Performance dataset
CF 1MP_DiCE CF MLP 10MMMLPOOCER OCEAN
CF CF_ F__T++ DICE
CF FF_DT_DICE CF CF_DT_OCEAM
CF DT+JOCEAN
Figure 9: Anytime performance of the CF model extraction attack against decision trees. We report results for all datasets and studied configurations, including adversarial knowledge regarding the target model architecture (DT. DT+, and MLP) and counterfactual oracles (DiCE and OCEAN).
19

---

1.9
0.8
02
Maan PAAaRt
0.8-
0.
0.1
10F
18
167
16
0.1
107
10
16
#'uerees
(a) Adult dataset
(b) COMPAS dataset
1.2
1.0
0.8
08
0.5
Mean Role
0.6
0.3
03
0.1
10
13
10
01
12
10
10
10
#Queries
PQueress
(c) Credit Card dataset
(d) German Credit dataset
1.0
0.5
0.7
PM6
0.6
0.5
0.3
0.1
10F
16a
107
16a
Student Performance dataset
DualCF MLP DiCE DualCF DOuaIF_MLLPCCMM WLP_MCEPLL
DualCF DT+ DDCE DualCF DT+_OCEAN
DualCF DT DiCE DuaiCF_DT, DT_ DT_OCEAN
Figure 10: Anytime performance of the DUALCF model extraction attack against decision trees. We report results for all datasets and studied configurations, including adversarial knowledge regarding the target model architecture (DT, DT+, and MLP) and counterfactual oracles (DiCE and OCEAN).
20

---

1.0
1.0
0.9
0.9
0.7
0.6
0.6
0.5
CF MLP OCEAN
DualCr, MUP OCEAN
CF
DuolCF.
CF_RT+_OCEAM
DuaICE_RF
0.3
CF RRF__ICCE
0.3
DalCF_AP+__B DICE
0.2
CF OCEAN
0.2
DuafCF, RF OCEAC
DuslCT, _F__CCE
16a
10
107
10a
10
10a
107
@Queries
#Queries
Figure 11: Anytime performance of the CF (left) and DUALCF (right) model extraction attacks against random forests. We report results for the COMPAS dataset and all studied configurations, including adversarial knowledge regarding the target model architecture (DT, DT+, and MLP) and counterfactual oracles (DiCE and OCEAN).
CF and DUALCF extraction attacks. Intuitively, this can be attributed to a greater diversity in the non-optimal counterfactuals, which do not necessarily lie close decision boundary, unlike optimal ones. This also highlights a crucial insight: optimal counterfactuals only give an advantage to a model extraction attack if the attack is able leverage the information carries whole (including both the counterfactual example and its optimality) through a structured approach, as demonstrated by TRA.
C.3 Test Set Fidelity Results
As mentioned in Section 4.1 the results provided in Section measure fidelity on a dataset uniformly sampled over the input space, which accurately quantifies how well the extracted models fit the decision boundaries of the target ones over the whole input space. Another approach consists in evaluating fidelity on
set. In such cases, the results indicate how well the extracted models mimic the target ones for examples drawn from the actual data distribution. We report in Table 3 the results of our extraction attacks against random forests. More precisely, for random forests of varying sizes, we report the average fidelity (measured on the uniformly sampled dataset or on test set) achieved by all considered methods along with the required number of queries. For DUALCF and CF, these values are arbitrarily fixed to allow their surrogates to converge towards (near) perfect fidelity. For our proposed TRA, functional equivalence achieved using the reported number of queries, hence fidelity on both considered datasets is always 1.0. For CF and DUALCC, we report results for the random forest surrogate using default parameters, for both studied counterfactual oracles. Indeed, observed in Section C.2 that DiCE counterfactuals led to better anytime performances (in terms of uniform dataset fidelity) than OCEAN ones within the CF model extraction attack, in most experiments. However, this is not always the case, with a few setups in which the difference between both approaches becomes very small or shifts in favor the runs using OCEAN counterfactuals after sufficiently many iterations. This is the difference remains very subtle, it is also visible on the test set fidelity, illustrating the fact that the two values are often very well aligned.
the COMPAS dataset (Figure 9b). and although the
Overall, the superiority TRA is clear, both in terms of (uniform or test) fidelity and in terms of required numbers of queries, confirming the observations of Section 4.2
21

---

Table 3: Summary of our model extraction experiments against random forests, on the COMPAS
dataset. For random forests with varying numbers of trees, we report their total number of nodes and the average performances of the different considered model extraction attacks. FU and FTD denote respectively the Fidelity over the Uniform and Test Data.
IRA
OCEAN
DICE
OCLAN
DICE
OCEAN
Donsect
Virees
#Nodes
#Queries
FTD
#Quertes
FU
FTD
KQuenes
FU
FTD
*Queries
FTD
#Queries
FU
FTD
-36.00
75.00
1.00
1.00
1000
1.00
0.50
1000
1.00
1.000
3000
110)
1.00
5000
1.00
170
COMPAS
50
25
2569.00
9151.30
147.60
138.80
1.00
1,00
1.00
1.00
3000
1000
0.99
0.99
0.98
0.98
2000
3000
1.00
1.00
1,00
1.00
3000
3000
1.00
1.0
1.00
1.00
3000
3000
1,00
1.00
1.00
1.00
75
7317.00
95.20
1.00
1.00
3000
1,00
0.99
3000
1.00
1,00
5000
1.00
1.00
3000
1,00
1.00
100
18369 20
129.60
1.00
1.00
3000
1.00
0.58
2000
1.00
1,00
3000
1.00
1.00
3000
1,00
1.00
C.4 Detailed Experimental Results
We hereafter report all the results of our main experiments over the five considered datasets.
First, Figure [2 provides the anytime performances (in terms of average surrogate fidelity as function of the number of performed queries) of the four considered model extraction attacks when applied on decision tree target models. The findings highlighted in Section 4.2 (in particular, Result 1) are consistent across all considered datasets: TRA exhibits higher anytime fidelity than CF and DUALCF for all query budgets, while also providing funcctinal equivalence guarantees. While PATUFINDING also provides these guarantees, it necessitates orders of magnitudes more queries fit its surrogate.
Figure 13 focuses on functionally equivalent model extraction attacks, and relates the number of queries they require fully recover the target model to its size (quantified as its number of nodes). The logarithmic scale of the y-axis highlights that TRA usually requires orders of magnitudes fewer queries than PATHFINDING entirely extract given decision tree, confirming Result (Section 4.2) Interestingly, this trend is more subtle when reconstructing large trees trained on the datasets with the highest numbers of features (i.e., Adult and SPerformance).
Finally, Figure [4 reports the number of counterfactual queries required by TRA to conduct functionally equivalent extraction of random forests of various sizes, as function of the total number of nodes to be recovered within the target forest. Importantly, as quantified through the performed power-law regression, the number of queries required by TRA to entirely extract the target forests grows sub-linearly - in θ (##Nodes 0.38 -with with the total number of nodes to be retrieved. This empirically demonstrates the very good scalability of TRA with respect to the size of the target random forests, consistent with Result 3 (Section 4.2). Note that this behavior arises because large forests with many trees introduce redundancies, allowing the extracted model be represented with perfect fidelity more compact decision tree [Vidal and Schilfer 2020
22

---

1.0
0.9
0.3
Maan Fidelty
0.8
Maan
0.64
0.6
30
10
30
10
10a
(a) Adult datasct
(b) COMPAS dataset
1.0
0.9
Megn Fudelo
0.8
0.7
0,6
10'
10a
10
10'
10
10"
12
10'
Quaries
#Querles
(c) Credit Card dataset
(d) German Credit dataset
MWan Maan Fideltyy
0.7
0.5
10
AQueries
(e) Student Performance dataset
TRA
DualCF
CF
PathFinding
Figure 12: Anytime performance all the considered model extraction attacks against decision trees. We report results for all datasets and retain the best configuration for the surrogate- based attacks CF and DUALCE.
23

---

100
10
#Queries
1.0
10
100
200
300
400
500
600
100
200
300
400
500
(a) Adult dataset
(b) COMPAS dataset
1.0
10a
10
100
2.0
10a
1.0
200
#hoods
aMtooe
(c) Credit Card dataset
(d) German Credit dataset
10a
#Quatiss
60
10P
20
40
50
80
100
ANoodis
(e) Student Performance dataset
TRA
PathFinding
Figure 13: Performance of the PATHFINDING and TRA functionally equivalent model extraction attacks against decision trees. We report results for all datasets where each point represents the number queries needed to fully reconstruct the trees.
24

---

#Trees=5
#Trees=25
#Trees=50
#Trees-75
10a
#Trees=100
x.13*
#Queries
100
10a
Total Nodes
Figure 14: Number of queries required by TRA to perform functionally equivalent extraction of target random forests of various sizes on the COMPAS dataset, as a function the total number of nodes to be reconstructed within the target forest. As illustrated through the performed power-law regression, the number of required queries grows sub-linearly in @##Nodes 0.35, with the total number of nodes to be retrieved, suggesting good scalability of the extraction attack with respect to the forest size.
25

---

D Performances of TRA when used with Locally Optimal Counterfactuals
In the main body of the paper (Section 4.2) we employed the OCEAN counterfactual oracle for experiments using TRA. It supplies globally optimal counterfactual explanations. While such global optimality is sufficient for the TRA attack to succeed, it is not necessary. Indeed, as pointed out in Section 3.2 TRA requires counterfactuals that are locally optimal - i.e. positioned on (or infinitesimally close to) the decision boundary of the explained model f. To illustrate this distinction, we replicate all experiments, following exactly the same setup described in Section 4. using locally optimal counterfactuals.
The DiCE counterfactual oracle, used in our experiments for the CF and DUALCF model extraction attacks, could be good candidate. However, it frequently fails to return valid counterfactuals when restricted to given subspace of the input space making it difficult to use within TRA. This suggests that the counterfactuals found by DiCE often lie in different decision regions of the target model, rather far from the actual query. When the counterfactuals are used provide recourse information, this can be problematic- - for instance, by suggesting that a credit applicant must exert significantly more effort than actually necessary improve their application. For these reasons, in our experiments using TRA, we rather consider a lightweight heuristic (Algorithm producing locally optimal counterfactuals.
Algorithm 3 A simple heuristic to find locally optimal counterfactual explanations
1: Input: Query æ, model f. input space E, training data Dr, and maximum number of iterations for the uniform sampling process S.
2: Return: A locally optimal counterfactual explanation x' E & if it exists.
3: DE +- 'Dr n & (gets all the data points that are in the desired input space E
4: for x' E DDg do
5: if' f(x') + f(x) then
6: return linesearch(z, x²) (x' is counterfactual, we refine it via line search towards r}
7: end if
8: end for
9: for 0 OSiSs do
10: x' + sample(E) [sample point x' uniformly within E
if
+ f(x) then
12: return lineseurch(z, x²) (a' is counterfactual, we refine it via line search towards x)
13: end if
14:
end for
15: return None (no counterfactual found)
}
More precisely, Algorithm searches in the training dataset and then refines the first valid coun- terfactual it finds via a mne-dimnsiional line search (line O If no counterfactual is found, it tries another strategy by sampling a predefined number of points uniformly in E. In our experiments, the maximum number of such sampled points is fixed to S = 1000. If a valid counterfactual is found, it refined via line search and returned (line 12). Because the search is stochastic and local, may fail to return a counterfactual even when one exists, yet it satisfies local optimality whenever a solution is found.
Figures 15 and 16 contrast the performance of TRA to extract decision trees, using OCEAN (globally optimal counterfactuals) versus Algorithm 3 (simpler algorithm, producing locally optimal counterfactuals) as counterfactual oracle. The observed trends confirm that TRA A remains effective as long as the returned counterfactuals are locally, though not necessarily globally, optimal - thereby confirming Result 4 (Section 4.2). Interestingly, we observe in Figure 15 that in the early iterations, locally optimal counterfactuals may lead better anytime fidelity values which is likely the case due to their heuristic nature, enhancing diversity. We also observe pathological case in Figure [5a with the Adult dataset. In this particular experiment, when used with Algorithm 3 as counterfactual oracle. TRA converges close to near- cear-perfect- - but not exact fidelity. This is due to the fact that Algorithm fails to find feasible counterfactuals within the desired region, even one exists. Indeed, even if the counterfactuals provided by this simple oracle satisfy local optimality whenever one is found, there no guarantee that if none is found that no one actually exists. Performing a finer uniform sampling (via raising the number of sampled points S) could fix this issue. Nevertheless, the
26

---

performances of TRA with this weak oracle remain very robust, as evidenced through our large set of experiments.
The performances of TRA to extract random forests target models, with either the OCEAN or Algorithm counterfactua oracles, are provided in Table display the trends. TRA is able to achieve perfect fidelity for both counterfactual oracles, and there is no significant difference in the required number of queries (which remains very low compared the size of the reconstructed forests, as discussed in Section
Moan Rideloy
33
#Queries
#Queriss
(a) Adult dataset
(b) COMPAS dataset
1.4
Muan Fideltyy
#Queries
#uueriss
(c) Credit Card dataset
(d) German Credit dataset
Moan Moan Fidelty
Queriess
(c) Student Performance datasct
TRA HEURISTIC
TRA_OCEAN
Figure 15: Anytime performance of TRA with either OCEAN or simpler heuristic counterfactual oracle (Algorithm 3) to extract decision trees. We report results for all datasets.
27

---

#Nodes
(a) Adult dataset
(b) COMPAS dataset
XNodes
NNods
(c) Credit Card dataset
(d) German Credit dataset
4Quuries
Student Performance dataset
TRA HEURISTIC
TRA_00 OCEAN
Figure 16: Performance TRA with either OCEAN or a simpler heuristic counterfactual oracle (Algorithm 3) to achieve functionally equivalent model extraction attacks against decision trees. We report results for all datasets where each point represents the number queries needed to fully reconstruct the trees.
Table 4: Summary of our model extraction experiments against random forests, on the COMPAS dataset using both OCEAN and Heuristie, FÜ and FTD denote respectively the Fidelity over the Uniform and Test Data.
TRA
OCEAN
Heuristic
Dataset
#Trees
Nodes
#Queries
FU
FTD
#Queries
FU
FTD
486.60
73.60
1.00
1.00
74.20
1.00
1.00
25
4569.00
138.80
1.00
1.00
140.00
1.00
1.00
COMPAS
50
9151.20
147.60
1.00
1.00
149.20
1.00
1.00
75
7317.00
95.20
1.00
1.00
95.20
1.00
1.00
100
18369.20
129.60
1.00
130.40
1.00
1.00
28

---

E Broader Impact Statement
To meet ethical and legal transparency requirements, machine learning explainability techniques have been extensively studied in recent years. Among them, counterfactual explanations provide natural and effective approach by identifying how instance could be modified receive a different classification. In credit granting applications, for example, they can provide recourse to individuals whose credit was denied.
As result, MLaaS platforms increasingly integrate such explainability tools into their APIs. While attack surface malicious entities by
these explanations enhance user trust, they also expose revealing additional model information. In this work, we theoretically and empirically demonstrate that locally optimal counterfactual explanations of decision trees and ensembles can be exploited to conduct efficient model extraction attacks. These results highlight the critical tension between transparency and the protection of model integrity and intellectual property. By identifying and quantifying these vulnerabilities, we highlight the risks of releasing model explanations without thorough security assessment. Our research establishes a benchmark for evaluating method safety, advocating for the development of privacy-preserving approaches to explainability.
Finally, while previous evaluations of model extraction attacks have been predominantly empirical, we show that tools from online discovery provide a principled framework for characterizing attack efficiency. This perspective paves the way for more structured approaches assessing model attack budgets and risks.
29

---

NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Our main contributions are mentioned in the abstract and thoroughly listed the end of the introduction. They include:
A methodology to theoretically analyze the efficiency of model extraction attacks through the use of tools from the online discovery literature (Section
novel reconstruction attack against axis axis- parallel decision boundary models, leverag- ing locally optimal counterfactual explanations and providing functional equivalence guarantees (Section 3.2)
A formal analysis of our attack's 's efficiency using our proposed theoretical framework
(Section 3.2
A thorough experimental evaluation (Section 4 demonstrating the efficiency and effectiveness of our proposed approach and confirming our theoretical results (in particular, that our algorithm achieves functional equivalence)
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
(last paragraph) clearly states our core assumptions, and Section details the algorithm 's improvements perspectives.
Justification: Section 3.1
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
30

---

If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't It acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification:
All assumptions and full proofs are provided in Appendix
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: Section 4.1 and Appendix detaii the complete experimental protocols, and the supplementary material include the source code used to run all our experiments, along with the appropriate documentation.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm.
31

---

(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is new model (e.g.. a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We provide all our source code and data in the supplementary material, along with the appropriate documentation.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips... cc/
gublic/guidess httpi//ggundee//ooeuuusisssssss
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed run reproduce the results. See the NeurlPS code and data submission guidelines (https ctttps.cc/pubbll httpppplllpppppppppppppppppaaaep http:///niiddde//eeueubmmiseeee ssioiooliccyyyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Section 4.1 and Appendix [providee all necessary details regarding data splits, hyperparameters, optimizer settings, and selection procedures.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, appendix, or as supplemental material.
7. Experiment statistical significance
32

---

Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: We report results multiple training seeds, datasets, and target models' hyperparameters: since our attack algorithm is deterministic, variability stems only from the classifier initialization. We report results for wide range of different configurations. where variability and impact of the different parameters directly visible (e.g., in Figures [ and [3] each point corresponds to one configuration and random seed). Furthermore, our approach quickly reaches perfect extraction fidelity (in which case there is no variability as fidelity is exactly 100% across all runs).
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
Question:
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Answer: [Yes]
Justification: The last paragraph of Section 4.1 specifies the CPU types and memory usage for all experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurIPS Code of Ethics http:p/://oorrrpp.c////b//////ta htch
Answer: [Yes]
Justification: Our work adheres fully to the NeurlPS Code of Ethics.
33

---

Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there a special consid- eration due to laws or regulations in their jurisdiction)
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
We include dedicated broader impact statement in Appendix E
Guidelines:
The answer NA means that there no societal impact of the work performed.
the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g.. disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
Justification: Our research relies solely on publicly available datasets, and no trained models are released. The source code for our reconstruction attack intended strictly for research purposes, and the final release will include clear warnings to prevent misuse.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
34

---

12. Licenses for existing assets
Question:
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: All external code and data are cited with version and license details.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, pwwpsswipppsseeeeeeeeeeeee thcode. com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
Our primary codebase is fully documented and distributed with usage instruc-
tions.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
No crowdsourcing or experiments involving humans.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
35

---

15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: No crowdsourcing or human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
Declaration of LLM usage
Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: LLMs are not part of the core methodology.
Guidelines:
The answer NA means that the method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM for what should or should be described.
36


Reviews:
[{"review_id": "h5nlbYnrPO", "reviewer": "Reviewer_oRDk", "summary": "This paper proposes a novel model extraction attack for additive decision tree-based models. This attack provably achieves perfect fidelity while relying only on the availability of a locally optimal counterfactual explanation oracle, a commonly used explainability technique. The paper further analyzes the worst-case query complexity of the attack and develops a theoretical framework based on competitive analysis to evaluate the efficiency of model extraction attacks. This framework shows that the proposed algorithm is optimal among the class of divide and conquer algorithms. Experimental results evaluate the anytime performance of the attack and show that the algorithm is superior to existing tree-based model extraction attacks.", "questions": "-\tWhat is the reason that $m$ is not necessarily equal to $m_N + m_B + m_C + m_D$ in Table 1? \n-\tHow does the competitive ratio of Algorithm 1 compare to non divide and conquer based methods?\n-\tHave you thought about possible defense methods against the attack from Algorithm 1?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "$\\large \\textbf{Quality}:$\n\nThis paper is of a good quality and comprehensive in both its experimental evaluation and theoretical analysis. The experimental evaluation includes standard binary classification datasets from literature for tree-based models and provides results which demonstrate the perfect fidelity and compares the anytime performance. Theoretically, the idea to use competitive analysis is beneficial and simplifies the analysis while answering a fundamental question in model extraction attacks on the number of queries for perfect fidelity extraction. \n\nIt would be beneficial to also include some results on the competitive ratio to show experimentally the results from Propositions 3.6 and 3.7. Similarly, understanding if the results can be modified to account for some target level of fidelity as opposed to perfect fidelity would be helpful and correspond to more realistic model extraction attacks such as in the case of large models or models beyond trees. \n\n$\\large \\textbf{Clarity}:$\n\nThe paper is generally clear and easy to understand. The figures and numerical examples help clarify the theoretical results and the proofs are written in a way that they can be easily followed. The experimental results are organized nicely with the main conclusions listed and the corresponding figures referenced. \n\nProviding some more intuition for the definition of a counterfactual would be beneficial. As someone not too familiar with decision trees, I was able to understand from the numerical example and Figure 1 but clarifying or providing some more discussion in Definition 3.1 would be beneficial. \n\n$\\large \\textbf{Significance and Originality}:$\n\nThe results from the paper are helpful in developing a rigorous understanding for model extraction attacks against tree-based models which provide counterfactual explanations. The ideas used are original and it is interesting to see the concept of competitive analysis and online optimization be applied to model extraction. The algorithm, while based on a simple idea, is interesting and the properties of optimality and perfect fidelity make it superior to existing model extraction algorithms for decision trees. The theoretical results are helpful to benchmark the performance of model extraction algorithms and understand their limitations. While the scope of the paper is limited to decision tree-based models, these ideas and techniques may be carried over to standard machine learning models. Moreover, the motivation around counterfactual explanations is practically relevant as model explainability methods gain importance.", "was_revised": true, "final_justification": "The authors clearly answered the questions I and other reviewers had. Therefore, I am keeping the rating to be the same i.e. an Accept since I believe the paper meets the quality standard of NeurIPS.", "rebuttal": "Thank you for the insightful feedback! Below are our point‐by‐point responses (with planned edits highlighted).\n\n---\n\n> It would be beneficial to also include some results on the competitive ratio to show experimentally the results from Propositions 3.6 and 3.7.  \n  \nSure, as seen in our experiments, the number of counterfactual queries empirically required by TRA to achieve functionally equivalent model extraction is significantly smaller than its theoretical worst-case obtained through Proposition 3.6. For instance, the following table compares these values for each dataset and for decision trees of maximum depth 9 (average, over $5$ random seeds). We will include these additional comparisons in the Appendix with related comments in Section 4.2.\n\n| Dataset       | Empirical \\# queries   | Worst‐case \\# queries        |\n| ------------- | :-----------------------------------------: | :--------------------------------------------: |\n| SPerformance | $1.16e+03$ | $3.02e+08$ |\n| Adult | $3.70e+04$ | $2.45e+14$ |\n| German Credit | $5.18e+01$ | $2.86e+03$ |\n| Credit Card | $6.97e+04$ | $6.49e+11$ |\n| COMPAS | $1.53e+02$ | $1.07e+03$ |\n\n\n---\n\n> Understanding if the results can be modified to account for some target level of fidelity as opposed to perfect fidelity would be helpful [...].  \n\nIndeed, as discussed in Section 3.2, TRA is an anytime algorithm, i.e., it can return a surrogate model at any point during its execution. Figures 3 and 5 show how surrogate's fidelity improves over the iterations. Note that fidelity must be measured for a certain sample distribution. In the case of a uniform distribution over the feature space, we can lower-bound the fidelity by the fraction of total volume corresponding to the leaf regions that have already been fully explored by TRA at a given iteration, and stop whenever a given target is met. We will mention this possibility in the revised paper.\n\n---\n\n> Providing some more intuition for the definition of a counterfactual would be beneficial  \n \nSure, in the revised paper, we will better discuss the concept of counterfactual explanations at a high level right before Definition 3.1.\n\n--- \n\n> What is the reason that $m$ is not necessarily equal to $m_N + m_B + m_C + m_D$ in Table 1?  \n  \nIn Table 1 each of the $m_C$ categorical features is one-hot encoded into $c_j$ binary dimensions, where $c_j$ is the number of categories of feature $j$. As a result, the total number of features becomes:\n$$\n  m = m_N + m_B + m_D + \\sum_{j=1}^{m_C} c_j.\n$$  \n\nWe will clarify this point in the paper by adding a footnote to Table 1.\n\n---\n\n> How does the competitive ratio of Algorithm 1 compare to non divide and conquer based methods?  \n\nThanks, this is an interesting but very challenging question. Analyzing the competitive ratio of any given algorithm is a non-systematic and difficult task, as it requires bounding the worst-case performance gap between an online algorithm and an omniscient offline counterpart over all possible inputs. This is also why proofs of competitive ratio are valuable from a theoretical standpoint. \nTo the best of our knowledge, there are no known theoretical results regarding the competitive ratio of other model extraction attacks. Our work provides the first such theoretical result in this context.\n\n--- \n\n> Have you thought about possible defense methods against the attack from Algorithm 1?  \n\nThank you for raising this important point. As long as the counterfactual oracle reflects the true model, returns a valid explanation whenever one exists (a property typically required in practical applications), and the number of queries is not constrained, TRA will ultimately converge to a functionally equivalent model extraction. Nonetheless, service providers might be able to mitigate the attack by rate-limiting the number of queries per user, introducing human verification methods during queries (e.g., CAPTCHAs), or monitoring for algorithmically generated query patterns. When such patterns are detected, they could throttle responses or alter the oracle behavior to reduce the attack's effectiveness. We will include a brief discussion of potential countermeasures in the appendix.\n\n--- \n\nOverall, thank you for your comments and your appreciation of the paper, we hope our responses have helped clarify any remaining gap. We remain available to provide any further clarification should additional questions arise."}, {"review_id": "yfoIrcd25s", "reviewer": "Reviewer_349a", "summary": "The paper proposes an online model extraction attack based on counterfactual explanations, specifically designed for decision tree and random forest models. The attack involves sequentially recovering the decision splits over each input feature using counterfactual explanations. A query complexity analysis for the algorithm (in terms of the tree depth and the input dimension) has also been presented. Theoretical guarantees for the performance of the algorithm has been given in terms of c-competitiveness w.r.t. an optimal offline algorithm.", "questions": "Instead of popping out the next available subspace from the list Q, will there be an improvement for the anytime performance if we pop the subspace with the largest volume?\n\nAlso, please see the concerns I have raised in the weaknesses above.", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths:**\n\n1. The discussed vulnerability is very much related, specifically to the finance sector where decision trees and random forest models are used for reliability and transparency; which is also a context where counterfactual explanations play an important role. Therefore the problem discussed in the paper is highly relevant.\n2. Provides an interesting algorithm with a theoretical analysis on the complexity and performance.\n3. Experiments are comprehensive and intuitive. Experimental setups are clearly explained.\n4. The paper content is well-organized.\n\n**Weaknesses:**\n\n*On the algorithm*\n1. The algorithm relies strongly on the fact that the counterfactual explanations (CFs) provided by the oracle lie on the decision boundary (local/global optimality) which is usually a difficult factor to be satisfied (e.g.: robust counterfactual explanations – see [1]). Authors have mentioned this as a problem of DiCE in Appendix C (top of page 24), which, however should be thought of as a possible real-world scenario rather than an imperfection of CF generation.\n2. Since the line joining the CF and the query instance (x’---x) may not be exactly parallel to many feature dimensions, the number of splits will be extremely large.\n3. No clear definition of the splitting function. Does it exclude the boundaries of the original subspace and the split? Otherwise it seems like there can be situations where the algorithm will never reveal some splits.\n\n*On the proofs*\n1. Proposition 3.4: In the inductive step, authors mention that s_i^{(n_q)}=s_i^{(n+1)} for I \\neq j and q \\in {1,2}, which is not clear to me. Shouldn’t this be s_i^{(n_1)} + s_i^{(n_2)}=s_i^{(n+1)} ?\n2. Proposition 3.6 upper bound: On page 13 top, the worst-case number of queries required is computed to be s_1+….. based on the fact that a checkerboard-like split would be the worst-case split possible. However, can we say that the recovery algorithm, i.e., first detecting the splits along feature 1 and then detecting the splits along feature 2 etc. is the worst-case algorithm?\n\n*On the experiments*\n1. In the first few experiments, OCEAN has been used as the CF generator for the proposed TRA attack, whereas DiCE has been used as the CF generator for the CF [Aivodji et al.] and DualCF [Wang et al.]. It is not clear how comparable the generated Cfs are.\n\n*Other minor comments:*\n1. The definition of “split levels” is not clear\n2. In the proofs, re-iterating the statement (proposition or the corollary) might make it easier to read.\n3. Including the KKT conditions in the proof of Corollary 3.5 would be good for the reader.\n\n\n[1] Dutta, S., Long, J., Mishra, S., Tilli, C., & Magazzeni, D. (2022, June). Robust counterfactual explanations for tree-based ensembles. In International conference on machine learning (pp. 5742-5756). PMLR.", "was_revised": true, "final_justification": "Authors have clarified the questions that I had, and also have agreed to revised the manuscript to resolve all the concerns I have raised. In light of this, I am happy to increase the rating.", "rebuttal": "We appreciate your thorough review. Please see our point‐by‐point responses below.\n\n---\n> The algorithm relies strongly on the fact that the counterfactual explanations (CFs) provided by the oracle lie on the decision boundary (local/global optimality) which is usually a difficult factor to be satisfied (e.g.: robust counterfactual explanations – see [1]). Authors have mentioned this as a problem of DiCE in Appendix C (top of page 24), which, however should be thought of as a possible real-world scenario rather than an imperfection of CF generation.\n\nIndeed, this is an important point and application scenario, which can also be handled by TRA. As discussed in Appendix C, any valid counterfactual explanation can be post-processed (through bisection line-searches over each feature using simple prediction queries) into a locally-optimal explanation lying on the decision boundary. Consequently, as long as the counterfactual oracle is reliable (i.e., it returns a counterfactual whenever one exists), the returned example reveals a direction in which the prediction changes, which is sufficient to locate a nearby decision boundary. We will better clarify this important point and the line search process in the revised paper.\n\nImportantly, the key limitation of DiCE isn't that its counterfactuals lie off the boundary, but that it regularly fails to produce any counterfactual at all (even when one exists within the specified subspace).\n\n---\n> No clear definition of the splitting function. Does it exclude the boundaries of the original subspace and the split? Otherwise it seems like there can be situations where the algorithm will never reveal some splits.\n\n> Since the line joining the CF and the query instance ($x’$---$x$) may not be exactly parallel to many feature dimensions, the number of splits will be extremely large. \n\nThanks for pointing this out! Indeed, the paper provided limited details on the definition of the $split$ function, and we will improve this in the revision.\nThe purpose of the $split$ function is to partition the current region based on the counterfactual example $x'$ returned by the oracle. If no counterfactual is found, the region is homogeneous (i.e., the prediction is constant), and a leaf is created, this is the base case. Otherwise, any locally-optimal counterfactual (possibly after post-processing, if needed) lies on a hyperplane (or vertex of a hyperrectangle) delimiting distinct prediction regions.\nLet $k$ denote the number of features on which $x'$ differs from the query point $x$. The $split$ function then partitions the region along one of these features, enqueues one of the resulting subregions, and continues splitting the remaining region (that contains $x'$) along the remaining $k-1$ features. This process results in exactly $k+1$ subregions. Consequently, by enabling a single counterfactual query to reveal multiple decision boundaries, the procedure ensures that no relevant split is missed and improves query efficiency. Regarding your second point, it is also important to note that this division stays linear in $k$; therefore, even if a counterfactual example requires changes along several features, the procedure remains efficient. We will definitely clarify this aspect in the paper and include a pseudo-code of the $split$ function in the appendix.\n\n---\n\n> Proposition 3.4: In the inductive step, authors mention that $s_i^{(n_q)}=s_i^{(n+1)}$ for $i \\neq j$ and $q \\in {1,2}$, which is not clear to me. Shouldn’t this be $s_i^{(n_1)} + s_i^{(n_2)}=s_i^{(n+1)}$ ? \n  \nAs part of the inductive step, the feature space is divided along an arbitrary dimension $j$, and no new divisions are introduced in any other dimension $i\\neq j$. Each child problem, therefore, has exactly the same number of splits in each dimension $i$ as the parent when $i\\neq j$, so $s_i^{(n_q)} = s_i^{(n+1)} \\quad (i\\neq j,\\,q\\in\\{1,2\\})$.\n\n---\n  \n> Proposition 3.6 upper bound: On page 13 top, the worst-case number of queries required is computed to be $s_1+….$ based on the fact that a checkerboard-like split would be the worst-case split possible. However, can we say that the recovery algorithm, i.e., first detecting the splits along feature 1 and then detecting the splits along feature 2 etc. is the worst-case algorithm?\n\n\nThe objective of the first part of the proof of Proposition 3.6 is to establish an upper-bound on the competitive ratio of TRA, defined as $C_{TRA}^{(n,m)} = sup_{f \\in \\mathcal{F}} (Q_{TRA}^f / Q_{opt}^f)$. To this end, we determine the smallest possible value for $Q_{opt}^f$, and the largest possible one for $Q_{TRA}^f$. Notably, the worst case for TRA occurs when the target model has a checkerboard-like structure where each axis-aligned cell in the feature space points to a distinct class. In such a configuration, recovering the model requires the maximum number of region splits and counterfactual queries, as every cell must be visited to ensure label consistency. Importantly, in this setting, the order in which TRA discovers the feature splits does not affect the total number of queries. This is because any axis-aligned split along one feature dimension necessarily intersects all splits along the remaining dimensions, so the total number of resulting subregions remains the same regardless of the order, and every cell in the checkerboard has to be tested individually for uniformity in the base case. Finally, Proposition 3.7 shows that this bound is tight: any divide-and-conquer extraction algorithm will face the same worst-case behavior.\n\n---\n\n> In the first few experiments, OCEAN has been used as the CF generator for the proposed TRA attack, whereas DiCE has been used as the CF generator for the CF [Aivodji et al.] and DualCF [Wang et al.]. It is not clear how comparable the generated Cfs are.\n\nTo ensure a complete and fair comparison with our approach, we evaluated the CF and DualCF baseline attacks using both DiCE and OCEAN as counterfactual generators in our preliminary experiments, even though the original papers used only DiCE. Then, we retained the best configuration for the baselines to put them in the most favorable light (in this case, using DiCE, as discussed in Section 4.1, lines 250–255). Additionally, Appendix B.2 provides a detailed comparison of their performance with both counterfactual oracles.\n\n---\n\n> The definition of “split levels” is not clear.  \n\nThank you for pointing this out. For a given decision tree, the \"split levels\" of a feature refer to the set of threshold values used in split conditions involving that feature across the entire tree. For binary features, only a single split level is possible, while continuous features may involve multiple distinct threshold values. We will reformulate the definition (Section 3.2, lines 143-145) to clarify it.\n\n---\n\n> In the proofs, re-iterating the statement (proposition or the corollary) might make it easier to read.\n\nThank you for the suggestion. We agree that reiterating the statement can improve readability, and we will add a restatement of each proposition and corollary before its corresponding proof.\n\n---\n\n> Including the KKT conditions in the proof of Corollary 3.5 would be good for the reader. \n  \nSure, we will definitely add them in the paper.\n\n---\n  \n> Instead of popping out the next available subspace from the list Q, will there be an improvement for the anytime performance if we pop the subspace with the largest volume?\n  \nIndeed, while different orderings of the priority queue $\\mathcal{Q}$ do not impact the total number of queries needed by the algorithm, they can yield different anytime fidelity performances. This is precisely why we mentioned the design of \"alternative priority strategies\" as an insightful direction (Section 3.1, line 201-204). In particular, prioritizing subspaces by largest volume is one possibility, and is indeed likely to improve TRA's anytime performance.\n\n---\n\nOnce again, thank you for your comments, we hope our responses have helped clarify any remaining gap. If so, we kindly invite you to reconsider your evaluation of the paper. We remain available to provide any further clarification should additional questions arise."}, {"review_id": "mxPxXovdWV", "reviewer": "Reviewer_TuFm", "summary": "The authors present an approach for model extraction attacks based on counterfactual explanations underlying the fact that explainability techniques may undermine the security of ML models.\nThe approach addresses models based on additive decision trees.", "questions": "I'd suggest authors to introduce earlier what they mean by functional equivalence guarantees and fidelity. They are formally defined later on in the article, but as they insist on these elements in the introduction, it would be nice to clarify the concept (to a wide audience as that of the current venue).\n\nDoes the system only considers binary trees construction ?\n\nThe authors discuss about the choice of the query points in the input space, but they do not discuss the importance of the local optimality of the counterfactual. How the system behaves in absence of such constraint.\n\nRelated work should be introduced prior to experimental setup as the authors already discuss representative work from STAR. The reader would also appreciate a discussion of the current STAR and how qualitatively (beyond quantitative results) the current proposal pushes the STAR one step further. CF and DualCF attacks employing counterfactuals were already considered by the community.\n\nThe way the algorithm behaves in absence of local or generic optimal counterfactual artifact should be included in the main article as the quality of the counterfactual is a point that rise questions in reader's mind. The results on page 16 in the annex seems that the non-optimal counterfactual explanations retured by DiCE helped fitting the surrogate models better. So if non-optimal works better, why not considering also random sampled counterfactuals ?\n\nHow the complexity of the surrogate models varies with regard to the nature of the counterfactuals used ? I understand that the main criteria here are  functional equivalence guarantees and fidelity, but mastering the complexity of the surrogate model might also be a concern. There are elements in supplementary material, but I suggest to push them in the main paper as the choice of the couternfactual is an element part of the process.\n\nI suggest authors to reproduce the seeds used. In order to secure the conclusions, I would recommand to increase the number of runs conducted. Besides, variances for experiments were not reported.", "limitations": "N/A", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The approach yields good results in comparaison with the current SOTA, exploiting features that are pushed forward by explainibility techniques without other assumption when considering models based on additive decision trees.\nThe evaluation seems sound without major concerned raised by the protocol adopted.\n\nIt is unclear how this can be generalized to other family of models where decision boundaries are not parralel to the axis.\nIt is important to clearly pinpoint the issue in additive decision trees spectrum, but it would be interesting to account for the amount of ML as a service providing this kind of models. Does this vulnerability impact niche platforms or mainstream ones ?\n\nElements from the Annex should have had their place in the main paper (such as B2 and C in relation to counterfactual optimality and D) in order to offer a complete view on the main contributions.", "was_revised": true, "final_justification": "The rebuttal carefully addressed all my concerns.\n\nI m convinced now by the originality and the significance of the contribution. The clarity should also be improved considering promised updates to the final version.", "rebuttal": "We appreciate your thoughtful review!\n\n---\n> It is unclear how [...] or mainstream ones ?\n\nThank you for this interesting perspective! While most of the core ideas of our divide-and-conquer algorithm would still work in the case of models with non-axis-parallel decision boundaries recovered as oblique decision trees, a key challenge lies in the fact that the coordinates of a locally optimal counterfactual example no longer uniquely define a separating hyperplane. For instance, a counterfactual located at a corner of the decision boundary may correspond to multiple combinations of intersecting hyperplanes. In such cases, additional prediction queries would be needed to recover the decision boundaries, yet it remains unclear to us how to do this efficiently. This is, however, a very interesting research question that we will continue examining and mention explicitly in the perspectives of the paper. We are also not aware of any functionally equivalent approach targeting other families of models in the current literature.\n\nThat said, focusing on axis-parallel models already uncovers a highly relevant vulnerability. Most tree-based algorithms (e.g., boosting ensembles or random forests as studied in our Result 3) construct axis-aligned splits by default and are widely used in production. Furthermore, many mainstream MLaaS platforms (e.g., Microsoft Azure, Google Cloud AI) offer decision tree-based models and support counterfactual explanations, making them directly susceptible to the attack we study. As such, the vulnerability we expose applies very broadly.\n\n---\n> Elements from the Annex [...] on the main contributions.\n\nWe completely agree. Due to the NeurIPS page limit, we had to provide some detailed analyses (specifically Sections B2, C, and D) in the appendix. These sections are explicitly referred to in the main text to ensure a complete presentation of our contributions. Nevertheless, the page limit is typically increased a bit for camera-ready paper preparation, so we could definitely migrate some of this content back to the main paper.\n\n---\n> I'd suggest authors to introduce [...] the concept (to a wide audience as that of the current venue).\n\nSure, we will include informal definitions of these notions earlier in the introduction as suggested.\n\n---\n> Does the system only considers binary trees construction ?\n\nFormally, our proposed attack applies to any model with axis-parallel decision boundaries, which can always be represented by a decision tree, whether binary or not. While TRA encodes the extracted model as a binary decision tree, this is simply a representational choice: the resulting tree is guaranteed to be functionally equivalent to the target model, even if the latter uses a different tree structure (since multiple structurally different trees may provide the same prediction function).\n\nAs mentioned in connection with one of your previous comments, it is a very interesting research perspective to extend our work to models with non-axis-parallel or piecewise-linear decision boundaries (e.g., ReLU-based neural networks).\n\n---\n>The authors discuss about [...] of such constraint.\n \nAs mentioned in Appendix C, any valid but possibly sub-optimal counterfactual explanation can be post-processed (through bisection line-searches over each feature using simple prediction queries) into a locally-optimal explanation lying on the decision boundary. Therefore, as long as the counterfactual oracle is reliable (i.e., it returns a counterfactual whenever one exists), the returned example reveals a direction in which the prediction changes, which is then sufficient to locate a nearby decision boundary. Consequently, the proposed attack framework remains effective in this setting, requiring only a few additional prediction queries. We will strengthen the discussion in the paper to clarify this aspect.\n\n---\n>Related work should [...] by the community.\n\nIn the current version of the paper, we chose to streamline the presentation to rapidly progress towards the method description, i.e., by locating the comprehensive discussion on STAR in Section 5, just before the conclusion. That said, contextualization of the work, discussions on the relative merit and capabilities of each method in the current STAR, have been also added in introduction and when presenting the baselines in the experimental section. We remain open to adjusting the structure of the paper to present related work earlier.\n\nSure, we will also improve the discussions on both the quantitative and qualitative contributions of our approach. Empirically, TRA significantly outperforms existing counterfactual-based attacks such as CF and DualCF in terms of fidelity and query efficiency. From a theoretical and qualitative standpoint, TRA provides capabilities and formal guarantees achieved by no other approach:\n- Tramèr et al. [2016] do not leverage counterfactual explanations and make stronger assumptions about the model’s API. Their method is specific to decision-tree target models (e.g., excluding random forests) and often requires far more queries. In contrast, TRA uses orders of magnitude fewer queries by exploiting counterfactual explanations and can handle any model with axis-parallel decision boundaries.\n- Dissanayake and Dutta [2024] focus on target models with convex and Lipschitz-continuous decision boundaries, which excludes models with axis-parallel boundaries. Their approach relies on globally optimal counterfactuals (whereas TRA accommodates locally optimal ones) and, while it provides certified bounds on the decision boundary approximation error, it does not guarantee functional equivalence.\n\nFinally, note that neither CF nor DualCF provide any fidelity guarantees. We will strengthen the discussions in the paper to ensure these differences are very clearly stated.\n\n---\n>The way the algorithm [...] sampled counterfactuals ?\n\nCF and DualCF build a surrogate dataset using counterfactual queries to the target model and then train a surrogate model on this dataset. In that context, DiCE counterfactuals provided greater diversity, which slightly improved surrogate performance. In contrast, TRA takes a fundamentally different approach. It uses counterfactual queries strategically, selecting them one by one within specific subregions of the input space to uncover decision boundaries with guaranteed fidelity and high query efficiency.\n\nWhile TRA benefits from locally optimal counterfactuals, it does not strictly require them: even sub-optimal counterfactuals can be post-processed to recover locally optimal points lying on decision boundaries. Appendix C details how to use TRA when the counterfactuals are not optimal and presents some results using a simple counterfactual heuristic.  These experiments show that TRA's performance remains robust regardless of the counterfactual generation method, as long as the oracle returns a valid counterfactual when one exists. We will definitely highlight this further in the main paper.\n\n---\n> How the complexity [...] part of the process.\n\nYou are absolutely right that, even once functional equivalence is achieved, the resulting surrogate model can vary in size depending on the order in which the decision boundaries are discovered. We will include the experimental results related to this metric in Appendix C, along with a discussion in the main paper. Importantly, we note that once a functionally equivalent model is obtained, one can apply standard model reformulation and compression techniques (e.g., [\"Born-again tree ensembles\", ICML, 2020]) to reduce the model size further. This step can be performed entirely offline, requiring no additional access to the prediction or counterfactual oracle, and would remain invisible to a MLaaS model provider.\n\n---\n> I suggest authors to reproduce [...] were not reported.\n\nThank you for this suggestion. Sure, the source code we provide along with the paper (including the seeds) will allow complete reproducibility of the results. Regarding the number of runs and variance reporting, it is important to note that our Tree Reconstruction Attack (TRA) is fully deterministic: given a fixed target model and counterfactual oracle, the algorithm produces identical outputs across runs. Consequently, the only source of variability in our experiments stems from the training of the target models (decision trees or random forests).\n\nIn Figures 3 and 5, we plot **performance profiles** of fidelity vs.\\ number of queries. At each query-count $q$, the curve shows\n$$\\text{mean fidelity at }q = \\frac1N \\sum_{i=1}^N fidelity(\\hat{f}_i,f_i),$$\nwhere $N$ is the number of independent target models (each with a different seed or max depth). By design, performance profiles display only the mean across all runs at each $q$; error bars had to be omitted for clarity of the graph. Furthermore, our approach quickly reaches perfect extraction fidelity 100\\% across all runs, in that regime there is *no variability*, since fidelity is identically 1.0. We can complement these figures with additional tables in the Appendix, as illustrated here for TRA on the Adult dataset for target models of maximum depth 9:\n\n | \\# Queries|Mean fidelity $±$ Std Dev|\n|:-:|:-:|\n|$20$|$ 0.7053 ± 0.085$|\n|$60$|$0.8564 ± 0.044$|\n|$100$|$0.8942 ± 0.051$|\n|$500$|$0.9693 ± 0.010$|\n|$1000$|$0.9775 ± 0.010$|\n|$5000$|$0.9968 ± 0.003$|\n|$10000$|$0.9988 ± 0.001$|\n|$14920$|$1.0000 ± 0.000$|\n\nFinally, in Figure 4, each marker corresponds to a single independent extraction (i.e., a target model trained under one seed and configuration). Thus, variability is explicitly visualized via the scatter of individual data points rather than through aggregated statistics.\n\n----\nOnce again, thank you for your positive appreciation and comments, we hope our responses have helped clarify any remaining gap. If this is the case, please consider revising your evaluation of the paper. We are also available for further clarification if any other doubts remain."}, {"review_id": "vByoWZfuxj", "reviewer": "Reviewer_hAR3", "summary": "In this paper, the authors present a framework to understand model extraction attacks. They also introduce a new algorithm for mode extraction attacks. They suggest using the competitive ratio to analyze extraction attacks as their framework. They prove their algorithm is optimal in the number of queries with respect to the competitive ratio among divide-and-conquer algorithms.", "questions": "Yes, I am not very familiar with the area, and I come from algorithm analysis, so I have several questions: \n1. The competitive ratio in the algorithmic sense is based on the worst-case instance, while more modern literature, such as algorithms with predictions, sometimes uses the average case. In Definition 3.3, is the minimal number of queries for the worst-case instance? \n2. What is the analysis of the competitive ratios of the existing baselines (e.g., Pathfinding, CF, Dual CF): are your empirical results showing something or just validating your theoretical results? \n3. $m$, where most of the features are one-hot encoding vs $m$ when most features are continuous, seems like different levels of difficulty. I see Table 1 separates m into different features. How does this impact your analysis? Proposition 3.6 seems like a loose upper bound if all m features are one-hot encoding? \n4. What happens when the outputs of your oracle are noisy? E.g., if the counterfactual explanation is wrong with some probability.", "limitations": "Can the authors point me to their limitations section?", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths: \n1. Using the competitive ratio to analyze extraction attacks seems pretty natural. I am glad the authors suggested it. \n2. The authors provide empirical results across multiple datasets. \n3. The paper is high quality, and the proofs are detailed and easy to follow. \n4. The paper is clearly written, and the results are well communicated. Algorithms are clearly described and the empirical experiments are well explained.   \n\nWeaknesses: \n1. Motivation for the theoretical framework can be better described. \n2. Connections between theoretical results and empirical results can be strengthened. \n\nI am not familiar enough with the field to comment on Originality and Clarity.", "was_revised": true, "final_justification": "The authors sufficiently address my concerns. I will raise the score to accept. But I want to reiterate that I am not an expert in the area and defer to other reviewers for final decisions.", "rebuttal": "Thank you for your insightful comments.\n\n---\n> Motivation for the theoretical framework can be better described.  \n\nSure, we will strengthen the introduction by explicitly motivating our use of competitive analysis: it provides a rigorous, model-agnostic way to quantify the hardness of tree extraction attacks and bound the number of queries. This will clarify why our theoretical framework is both natural and important for this problem.\n\n---\n>  Connections between theoretical results and empirical results can be strengthened.  \n\nThank you for this suggestion, it aligns with a similar comment from Reviewer oRDk. In our revised manuscript, we will include a new table in Appendix C and reference it in Section 4.2. This table directly compares the **empirical** number of queries required by TRA to achieve functional equivalence against the **theoretical** worst-case bound derived from Proposition 3.6 on each dataset. This comparative view shows that, in practice, TRA is significantly more efficient than the pessimistic theoretical bound:\n|Dataset | Empirical \\# queries | Worst-case \\# queries|\n|--|:--:|:--:|\n|SPerformance | $1.16e+03$ | $3.02e+08$|\n|Adult | $3.70e+04$ | $2.45e+14$|\n|German Credit | $5.18e+01$ | $2.86e+03$|\n|Credit Card | $6.97e+04$ | $6.49e+11$|\n|COMPAS | $1.53e+02$ | $1.07e+03$ |\n\n---\n>  The competitive ratio in the algorithmic sense is based on the worst-case instance, while more modern literature sometimes uses the average case. In Definition 3.3, is the minimal number of queries for the worst-case instance?  \n\nYes, Definition 3.3 measures $Q_\\mathcal{A}^f / Q_{\\mathrm{opt}}^f$ per model $f$ and then takes the supremum over all $f$, i.e., the worst-case. Extending this to an average-case or learning-augmented framework, where one analyzes expected competitiveness under a distribution over models, is indeed a promising avenue, and will be highlighted as future work. However, note that very different methodological tools might be needed for such situations. In addition, note that our empirical study also provides average-case insights regarding the practical performances of our approach on real-world datasets.\n\n---\n> What is the analysis of the competitive ratios of the existing baselines (e.g., Pathfinding, CF, Dual CF): are your empirical results showing something or just validating your theoretical results?  \n\nDeriving formal competitive ratios for PathFinding, CF, or DualCF would require a detailed worst-case analysis for each method as well as a common target (a certain recovery threshold, or perfect fidelity). However, this is a non-systematic and difficult task. To compare these methods with our proposal, we rely on our empirical comparisons (e.g., Figures 3 to 5), which demonstrate that TRA consistently outperforms these baselines in query count and fidelity, thereby validating that TRA's competitive guarantees translate into practical superiority.\n\n---\n> $m$, where most features are one-hot vs $m$ when features are continuous, seems like different levels of difficulty. Table 1 separates feature types-how does this impact your analysis? Proposition 3.6 seems loose if all $m$ features are one-hot.  \n\nIndeed, the rightmost calculation in Proposition 3.6 corresponds to a \"looser\" (but more readable) worst-case estimate than the leftmost calculation, which explicitly models the possible number of split levels for each feature. This does not impact much the analysis since one can rely on the leftmost calculation for any specific case. Furthermore, Proposition 3.7 shows that this calculation is \"tight\" for any divide-and-conquer-based algorithm, by identifying a case in which this situation happens.\n\n---\n> What happens if the oracle outputs noisy counterfactuals (wrong with some probability)?  \n\nThank you for raising this point. First, it is important to note that any CF can be verified with a single prediction query to ensure that $f(x')\\neq f(x)$. If the counterfactual does not actually change the predicted class, it can be discarded and does not affect the algorithm’s operation. Note that in real-world deployments, unreliable counterfactual algorithms violate the \"right to explanations\" and should preferably not be used. Now, in cases where the counterfactual explanation is valid but suboptimal (i.e., it lies far from decision boundaries), TRA can still operate correctly. Specifically, such a counterfactual can be post-processed (through bisection line-searches over each feature using simple prediction queries) as mentioned in Appendix C into a locally-optimal explanation lying on the decision boundary. In summary, as long as the oracle is reliable (i.e., it returns a counterfactual whenever one exists), it provides a direction of change in prediction, which is sufficient to identify a nearby boundary. This mechanism enables TRA to function correctly even when the counterfactuals are noisy and sub-optimal.\n\n---\n\nOnce again, thank you for your positive appreciation and comments, we hope our responses have helped clarify any remaining gap. If so, we kindly invite you to reconsider your evaluation of the paper. We are also available for further clarification if any other doubts remain."}]

Author rebuttal:

Meta-review: This paper proposes a new framework for model extraction attacks against tree-based models, introducing Tree Reconstruction Attack, a divide-and-conquer method using counterfactual oracles. The paper contributes both a rigorous theoretical foundation via competitive analysis and an efficient practical algorithm achieving provable fidelity guarantees.

Strengths include the combination of novel theory and practical relevance, strong experiments across datasets, and clear articulation of vulnerabilities in MLaaS platforms. The unanimous positive ratings after discussion, combined with the authors' thorough responses and commitment to improvements, support acceptance.

The reviewers and AC encourage the authors to include their responses of the rebuttal in the camera-ready version, not limited to:
1. Move key content from the appendix into the main text
2. Clarify definitions of functional equivalence guarantees and fidelity
Decision: Accept (spotlight)