# Model Reconstruction Using Counterfactual Explanations: Mitigating the
Decision Boundary Shift

Pasan Dissanayake, Sanghamitra Dutta

###### Abstract

Counterfactual explanations find ways of achieving a favorable model outcome
with minimum input perturbation. However, counterfactual explanations can also
be exploited to steal the model by strategically training a surrogate model to
give similar predictions as the original (target) model. In this work, we
investigate model extraction by specifically leveraging the fact that _the
counterfactual explanations also lie quite close to the decision boundary._ We
propose a novel strategy for model extraction that we call Counterfactual
Clamping Attack (CCA) which trains a surrogate model using a unique loss
function that treats counterfactuals differently than ordinary instances. Our
approach also alleviates the related problem of _decision boundary shift_ that
arises in existing model extraction attacks which treat counterfactuals as
ordinary instances. We also derive novel mathematical relationships between
the error in model approximation and the number of queries using polytope
theory. Experimental results demonstrate that our strategy provides improved
fidelity between the target and surrogate model predictions on several real
world datasets.

##  1 Introduction

Counterfactual explanations (Wachter, Mittelstadt, and Russell 2017) are well-
known for providing guidance on how to obtain a more favorable outcome from a
machine learning model, e.g., increase your income by 10K to qualify for the
loan. Given an input instance, a counterfactual explanation (also called _a
counterfactual_) finds another instance that belongs to a different output
class. Typically, the counterfactual is selected based on certain desirable
criteria such as proximity to the original instance, limited feature changes,
etc.

While counterfactuals provide several benefits, it has also been shown
(Aïvodji, Bolot, and Gambs 2020) that counterfactuals have the potential to
leak sensitive information about the underlying model, causing privacy
concerns. It can become a serious threat, especially in Machine Learning as a
Service (MLaaS)platforms (Gong et al. 2021; Tramèr et al. 2016) that are
emerging as a popular alternative to learning models on site, allowing users
to query the model for a specified cost (Gong et al. 2020; Juuti et al. 2019).
Preserving the privacy of these models is a huge concern for the operators of
such services because by strategically querying the model, an adversary may be
able to “steal” the model (Wang, Qian, and Miao 2022; Gong et al. 2021; Tramèr
et al. 2016; Pal et al. 2020; Juuti et al. 2019). Stealing usually involves
training a surrogate model to provide similar predictions as the target model,
a practice also referred to as _model extraction_. In this work, our main
question is: _How can counterfactuals be leveraged to perform model extraction
attacks?_

One existing approach is to treat counterfactuals as ordinary labeled points
and use them for training the surrogate model (Aïvodji, Bolot, and Gambs
2020). While this may work for a well-balanced query dataset with queries from
the two classes lying roughly equidistant to the decision boundary, it is not
the same for unbalanced datasets. The surrogate decision boundary might not
always overlap with that of the target model (see Fig. 1), a problem also
referred to as _a decision boundary shift_. This is a result of the learning
process where the boundary is kept as far as possible from the training
examples (margin) to achieve better generalization (Shokri, Strobel, and Zick
2021). This issue is aggravated when the system provides only _one-sided
counterfactuals_ , i.e., counterfactuals only for queries with unfavorable
predictions which is a common use case, e.g., only for rejected applicants in
a loan application. This is because the counterfactuals are typically quite
close to the decision boundary. _Hence, when treated as ordinary labeled
points for training the surrogate model, one-sided counterfactuals make the
dataset unbalanced in terms of the distance from the decision boundary._

Figure 1: Decision boundary shift in model extraction when counterfactuals are
treated as ordinary labeled instances.

In this work, we analyze how model extraction attacks can be refined by
specifically leveraging the fact that the counterfactuals are quite close to
the decision boundary. We demonstrate strategies that alleviate the decision-
boundary-shift issue. We provide novel theoretical guarantees for the attacks,
addressing an important knowledge gap in the existing literature. In contrast
to existing attacks Aïvodji, Bolot, and Gambs (2020) and Wang, Qian, and Miao
(2022) which require the system to provide counterfactuals for queries from
both sides of the decision boundary, our methods require only one-sided
counterfactuals (from one side of the decision boundary). Our contributions
can be listed concisely as follows:

  * •

Fundamental guarantees on model extraction using closest counterfactuals: We
first demonstrate how the closest counterfactuals can provide a linear
approximation of the decision boundary around the counterfactuals (Lemma 3.1).
Our key contribution lies in analyzing the goodness of this linear
approximation _using polytope theory_. We provide a novel theoretical
characterization of the relationship between the number of queries and the
average agreement of the surrogate model (obtained using linear
approximations) with the target model (see Theorem 3.2).

  * •

An attack based on the proximity of the counterfactuals to the target decision
boundary: Noting the practical challenges associated with generating the
closest counterfactual, we focus on an alternative strategy where we exploit
only the fact that counterfactuals _lie reasonably close to the decision
boundary, but need not be exactly the closest._ We first observe that the
Lipschitz continuity of the target and surrogate models would constrict the
deviations of their prediction probabilities around matching points (Theorem
3.4). To be precise, if $m_{1}$ and $m_{2}$ are two Lipschitz continuous
classifiers (with Lipschitz constants $\gamma_{1}$ and $\gamma_{2}$,
respectively) and $\boldsymbol{w}$ is a matching point, i.e., an input
instance such that $m_{1}(\boldsymbol{w})=m_{2}(\boldsymbol{w})$, then for any
$\boldsymbol{x}$ in the input space, $m_{1}(\boldsymbol{x})$ and
$m_{2}(\boldsymbol{x})$ differ at most by
$(\gamma_{1}+\gamma_{2})||\boldsymbol{x}-\boldsymbol{w}||_{2}$. This
observation motivates a refined way of utilizing counterfactuals for model
extraction. By forcing the surrogate model to match the prediction
probabilities of the target model at a sufficiently large number of points
along the decision boundary, we can force the decision boundaries of the
target and surrogate models to overlap significantly. Furthermore, this can be
precisely achieved with counterfactuals because they lie closer to the target
decision boundary where the prediction probability of the target model is
roughly 0.5. Accordingly, we propose a novel model extraction attack – that we
call _Counterfactual Clamping Attack (CCA)_ – which introduces a novel loss
function for training the surrogate model by clamping its decision boundary to
the target decision boundary at the counterfactuals (see Equation 3.2).

  * •

Empirical validation: We conduct experiments on both synthetic datasets, as
well as, four real-world datasets, namely, Adult Income (Becker and Kohavi
1996), COMPAS (Angwin et al. 2016), DCCC (Yeh 2016), and HELOC (FICO 2018).
Our strategy outperforms the existing strategy in Aïvodji, Bolot, and Gambs
(2020) over all these datasets (Section 4) using one-sided counterfactuals,
i.e., counterfactuals only for queries from the unfavorable side of the
decision boundary. We also include additional experiments to observe the
effects of model architecture, Lipschitzness, and other types of
counterfactual generation methods as well as an ablation study to experiment
with other loss functions.

Related Works: A plethora of counterfactual-generating mechanisms has been
suggested in existing literature (Guidotti 2022; Barocas, Selbst, and Raghavan
2020; Verma et al. 2022; Karimi et al. 2022, 2020; Mothilal, Sharma, and Tan
2020; Dhurandhar et al. 2018; Deutch and Frost 2019; Mishra et al. 2021).
Related works that focus on leaking information about the dataset from
counterfactual explanations include membership inference attacks (Pawelczyk,
Lakkaraju, and Neel 2023) and explanation-linkage attacks (Goethals, Sörensen,
and Martens 2023). Shokri, Strobel, and Zick (2021) examines membership
inference from other types of explanations, e.g., feature-based. Instead, we
focus on model extraction from counterfactual explanations.

Model extraction attacks (without counterfactuals) have been the topic of a
wide array of studies (see surveys Gong et al. (2020) and Oliynyk, Mayer, and
Rauber (2023)). Various mechanisms such as model inversion (Gong et al. 2021),
equation solving (Tramèr et al. 2016), as well as active learning have been
considered (Pal et al. 2020). Milli et al. (2019) looks into model
reconstruction using other types of explanations, e.g., gradient-based. Yadav,
Moshkovitz, and Chaudhuri (2023) explore algorithmic auditing using
counterfactual explanations, focusing on linear classifiers and decision
trees. Using counterfactual explanations for model extraction has received
limited attention, with the notable exception of Aïvodji, Bolot, and Gambs
(2020) and Wang, Qian, and Miao (2022). Aïvodji, Bolot, and Gambs (2020)
suggest using counterfactuals as ordinary labeled examples while training the
surrogate model. This suffers from the issue of decision boundary shift,
particularly for unbalanced query datasets (one-sided counterfactuals). Wang,
Qian, and Miao (2022) introduces a strategy of further querying for the
counterfactual of the counterfactual. However, both these methods require the
system to provide counterfactuals for queries from both sides of the decision
boundary. Nevertheless, a user with a favorable decision may not usually
require a counterfactual explanation, and hence a system providing one-sided
counterfactuals might be more common, wherein lies our significance. While
model extraction attacks (without counterfactuals) have received interest from
a theoretical perspective (Tramèr et al. 2016; Papernot et al. 2017; Milli et
al. 2019), model extraction attacks involving counterfactual explanations lack
such a theoretical understanding. Our work proposes and theoretically analyzes
model extraction attacks by explicitly utilizing the fact that the
counterfactuals are close to the decision boundary. We provide novel
performance guarantees in terms of query complexity for the proposed attacks,
leveraging polytope theory, and also address the decision-boundary shift
issue.

##  2 Preliminaries

Notations: We consider binary classification models $m$ that take an input
value $\boldsymbol{x}\in\mathbb{R}^{d}$ and output a probability between $0$
and $1$. The final predicted class is denoted by
$\left\lfloor{m(\boldsymbol{x})}\right\rceil\in\\{0,1\\}$ which is obtained by
thresholding the output probability at $0.5$ as follows:
$\left\lfloor{m(\boldsymbol{x})}\right\rceil=\mathds{1}[m(\boldsymbol{x})\geq
0.5]$ where $\mathds{1}[\cdot]$ denotes the indicator function. Throughout the
paper, we denote the output probability by $m(\boldsymbol{x})$ and the
corresponding thresholded output by
$\left\lfloor{m(\boldsymbol{x})}\right\rceil$. Consequently, the decision
boundary of the model $m$ is the $(d-1)$-dimensional hypersurface
(generalization of surface in higher dimensions; see Definition 2.4) in the
input space, given by
$\partial{\mathbb{M}}=\\{\boldsymbol{x}:m(\boldsymbol{x})=0.5\\}$. We call the
region where $\left\lfloor{m(\boldsymbol{x})}\right\rceil=1$ as the _favorable
region_ and the region where $\left\lfloor{m(\boldsymbol{x})}\right\rceil=0$
as the _unfavorable region_. We always state the convexity/concavity of the
decision boundary with respect to the favorable region (i.e., the decision
boundary is convex if the set
${\mathbb{M}}=\\{\boldsymbol{x}\in{\mathbb{R}}^{d}:\left\lfloor{m(\boldsymbol{x})}\right\rceil=1\\}$
is convex). We assume that upon knowing the range of values for each feature,
the $d-$dimensional input space can be normalized so that the inputs lie
within the set $[0,1]^{d}$ (the $d-$dimensional unit hypercube), as is common
in literature (Liu et al. 2020; Tramèr et al. 2016; Hamman et al. 2023; Black,
Wang, and Fredrikson 2022). We let $g_{m}$ denote the counterfactual
generation mechanism corresponding to the model $m$.

######  Definition 2.1 (Counterfactual Generating Mechanism).

Given a cost function
$c:[0,1]^{d}\times[0,1]^{d}\rightarrow{\mathbb{R}}^{+}_{0}$ for measuring the
quality of a counterfactual, and a model $m$, the corresponding counterfactual
generating mechanism is the mapping $g_{m}:[0,1]^{d}\rightarrow[0,1]^{d}$
specified as

$g_{m}(\boldsymbol{x})=\operatorname*{\arg\;\min}_{\begin{subarray}{c}\boldsymbol{w}\in[0,1]^{d},\
\left\lfloor{m(\boldsymbol{x})}\right\rceil\neq\left\lfloor{m(\boldsymbol{w})}\right\rceil\end{subarray}}c(\boldsymbol{x},\boldsymbol{w}).$
(1)

The cost $c(\boldsymbol{x},\boldsymbol{w})$ is selected based on specific
desirable criteria, e.g.,
$c(\boldsymbol{x},\boldsymbol{w})=||\boldsymbol{x}-\boldsymbol{w}||_{p}$, with
$||\cdot||_{p}$ denoting the $L_{p}$-norm. Specifically, $p=2$ leads to the
following definition of the closest counterfactual (Wachter, Mittelstadt, and
Russell 2017; Laugel et al. 2017; Mothilal, Sharma, and Tan 2020).

######  Definition 2.2 (Closest Counterfactual).

When
$c(\boldsymbol{x},\boldsymbol{w})\equiv||\boldsymbol{x}-\boldsymbol{w}||_{2}$,
the resulting counterfactual generated using $g_{m}$ as per Definition 2.1 is
called the closest counterfactual.

Problem Setting: Our problem setting involves a target model $m$ which is pre-
trained and assumed to be hosted on a MLaaS platform (see Fig. 2). Users can
query it with a set of

Figure 2: Problem setting

input instances ${\mathbb{D}}\subseteq[0,1]^{d}$ through an Application
Programming Interface (API). The API will provide the users with the set of
predictions, i.e.,
$\\{\left\lfloor{m(\boldsymbol{x})}\right\rceil:\boldsymbol{x}\in{\mathbb{D}}\\}$,
and a set of _one-sided_ counterfactuals for the instances whose predicted
class is $0$, i.e.,
$\\{g_{m}(\boldsymbol{x}):\boldsymbol{x}\in{\mathbb{D}},\left\lfloor{m(\boldsymbol{x})}\right\rceil=0\\}$.
Note that, by the definition of a counterfactual,
$\left\lfloor{m(g_{m}(\boldsymbol{x}))}\right\rceil=1$ for all
$\boldsymbol{x}$ with $\left\lfloor{m(\boldsymbol{x})}\right\rceil=0$. An
adversary, while appearing to be a normal user, can query with an attack
dataset ${\mathbb{D}}_{\text{attack}}\subseteq[0,1]^{d}$ and use the returned
labels and counterfactuals to train their own _surrogate model_ $\tilde{m}$.
The goal of the adversary is to achieve a certain level of performance with as
few queries as possible. In this work, we use _fidelity_ as our performance
metric for model extraction111Performance can be evaluated using accuracy or
fidelity (Jagielski et al. 2020). Accuracy is a measure of how well the
surrogate model can predict the true labels over the data manifold of
interest. Fidelity measures the agreement between labels predicted by the
surrogate and the target models. While attacks based on both measures have
been proposed in literature, fidelity-based attacks have been deemed more
useful as a first step in designing future attacks (Jagielski et al. 2020;
Papernot et al. 2017)..

######  Definition 2.3 (Fidelity (Aïvodji, Bolot, and Gambs 2020)).

With respect to a given target model $m$ and a reference dataset
${\mathbb{D}}_{\text{ref}}\subseteq[0,1]^{d}$, the fidelity of a surrogate
model $\tilde{m}$ is given by

${\rm
Fid}_{m,{\mathbb{D}}_{\text{ref}}}(\tilde{m})=\frac{1}{\left|{\mathbb{D}}_{\text{ref}}\right|}\sum_{\boldsymbol{x}\in{\mathbb{D}}_{\text{ref}}}\mathds{1}\left[\left\lfloor{m(\boldsymbol{x})}\right\rceil=\left\lfloor{\tilde{m}(\boldsymbol{x})}\right\rceil\right].$

Background on Geometry of Decision Boundaries: Our theoretical analysis
employs arguments based on the geometry of the involved models’ decision
boundaries. We assume the decision boundaries are hypersurfaces. A
hypersurface is a generalization of a surface into higher dimensions, e.g., a
line or a curve in a 2-dimensional space, a surface in a 3-dimensional space,
etc.

######  Definition 2.4 (Hypersurface, Lee (2009)).

A hypersurface is a $(d-1)$-dimensional sub-manifold embedded in
${\mathbb{R}}^{d}$, which can also be denoted by a single implicit equation
$\mathcal{S}(\boldsymbol{x})=0$ where $\boldsymbol{x}\in\mathbb{R}^{d}$.

We focus on the properties of hypersurfaces which are “touching” each other,
as defined next.

######  Definition 2.5 (Touching Hypersurfaces).

Let $\mathcal{S}(\boldsymbol{x})=0$ and $\mathcal{T}(\boldsymbol{x})=0$ denote
two differentiable hypersurfaces in $\mathbb{R}^{d}$.
$\mathcal{S}(\boldsymbol{x})=0$ and $\mathcal{T}(\boldsymbol{x})=0$ are said
to be touching each other at the point $\boldsymbol{w}$ if and only if
$\mathcal{S}(\boldsymbol{w})=\mathcal{T}(\boldsymbol{w})=0$, and there exists
a non-empty neighborhood $\mathcal{B}_{\boldsymbol{w}}$ around
$\boldsymbol{w}$, such that
$\forall\boldsymbol{x}\in\mathcal{B}_{\boldsymbol{w}}$ with
$\mathcal{S}(\boldsymbol{x})=0$ and $\boldsymbol{x}\neq\boldsymbol{w}$, only
one of $\mathcal{T}(\boldsymbol{x})>0$ or $\mathcal{T}(\boldsymbol{x})<0$
holds. (i.e., within
$\mathcal{B}_{\boldsymbol{w}},\mathcal{S}(\boldsymbol{x})=0$ and
$\mathcal{T}(\boldsymbol{x})=0$ lie on the same side of each other).

Next, we show that touching hypersurfaces share a common tangent hyperplane at
their point of contact. This result is instrumental in exploiting the closest
counterfactuals in a model extraction attack (proof in Appendix A.1).

######  Lemma 2.6.

Let $\mathcal{S}(\boldsymbol{x})=0$ and $\mathcal{T}(\boldsymbol{x})=0$ denote
two differentiable hypersurfaces in $\mathbb{R}^{d}$, touching each other at
point $\boldsymbol{w}$. Then, $\mathcal{S}(\boldsymbol{x})=0$ and
$\mathcal{T}(\boldsymbol{x})=0$ have a common tangent hyperplane at
$\boldsymbol{w}$.

Lipschitz Continuity: Lipschitz continuity, a property that is often
encountered in related works (Bartlett, Foster, and Telgarsky 2017; Gouk et
al. 2021; Pauli et al. 2021; Hamman et al. 2023; Liu et al. 2020; Marques-
Silva et al. 2021), can be exploited in perfecting model extraction attacks.

######  Definition 2.7 (Lipschitz Continuity).

A model $m$ is said to be Lipschitz continuous with a constant $\gamma$ if

$|m(\boldsymbol{x}_{1})-m(\boldsymbol{x}_{2})|\leq\gamma||\boldsymbol{x}_{1}-\boldsymbol{x}_{2}||_{2}$
(2)

for all $\boldsymbol{x}_{1},\boldsymbol{x}_{2}\in[0,1]^{d}$, with
$\gamma\in{\mathbb{R}}_{0}^{+}$.

##  3 Main Results

###  3.1 Fundamental guarantees on model extraction using closest
counterfactuals

We provide a theoretical guarantee on model extraction using the closest
counterfactuals in Theorem 3.2. We first start out with demonstrating how the
closest counterfactuals provide a linear approximation of _any_ decision
boundary. Prior work (Yadav, Moshkovitz, and Chaudhuri 2023) shows that for
linear models, the line joining a query instance $\boldsymbol{x}$ and the
closest counterfactual $\boldsymbol{w}(=g_{m}(\boldsymbol{x}))$ is
perpendicular to the linear decision boundary. We generalize this observation
to any differentiable decision boundary, not necessarily linear, as follows:

######  Lemma 3.1.

Let $\mathcal{S}$ denote the decision boundary of a classifier and
$\boldsymbol{x}\in[0,1]^{d}$ be any point that is not on $\mathcal{S}$. Then,
the line joining $\boldsymbol{x}$ and its closest counterfactual
$\boldsymbol{w}$ is perpendicular to $\mathcal{S}$ at $\boldsymbol{w}$.

Figure 3: Polytope approximation of a convex decision boundary.

The proof follows by showing that the $d$-dimensional ball with radius
$||\boldsymbol{x}-\boldsymbol{w}||_{2}$ touches (as in Definition 2.5)
$\mathcal{S}$ at $\boldsymbol{w}$, and invoking Lemma 2.6. For details see
Appendix A.1.

As a direct consequence of Lemma 3.1, an adversary may query the system and
calculate tangent hyperplanes of the decision boundary drawn at the
counterfactual instances. This leads to a linear approximation of the decision
boundary (see Fig. 3).

If the decision boundary is convex from the unfavorable side, i.e., the region
where $\left\lfloor{m(\boldsymbol{x})}\right\rceil=0$, such an approximation
will provide a set of supporting hyperplanes. _The intersection of these
supporting hyperplanes will provide a circumscribing polytope approximation of
the decision boundary._ We show that the fidelity of such an approximation,
evaluated over uniformly distributed input instances, tends to 1 when the
number of counterfactuals is large.

######  Theorem 3.2.

Let $m$ be the target binary classifier whose decision boundary is convex
(i.e., the set
$\\{\boldsymbol{x}\in[0,1]^{d}:\left\lfloor{m(\boldsymbol{x})}\right\rceil=1\\}$
is convex) and has a continuous second derivative. Denote by $\tilde{M}_{n}$,
the polytope approximation of $m$ constructed with $n$ supporting hyperplanes
obtained through i.i.d. queries. Assume that the fidelity is evaluated with
respect to ${\mathbb{D}}_{\text{ref}}$ which is uniformly distributed over
$[0,1]^{d}$. Then, when $n\rightarrow\infty$ the expected fidelity of
$\tilde{M}_{n}$ with respect to $m$ is given by

$\mathbb{E}\left[{{\rm
Fid}_{m,{\mathbb{D}}_{\text{ref}}}(\tilde{M}_{n})}\right]=1-\epsilon$ (3)

where $\epsilon\sim\mathcal{O}\left(n^{-\frac{2}{d-1}}\right)$ and the
expectation is over both $\tilde{M}_{n}$ and ${\mathbb{D}}_{\text{ref}}$.

The proof utilizes a result from polytope theory (Böröczky Jr and Reitzner
2004) which provides a complexity bound on volume-approximating smooth convex
sets by random polytopes. The proof involves observing that the volume of the
overlapping decision regions of $m$ and $\tilde{M}_{n}$ (for example, regions
A and C in Fig. 3) translates to the expected fidelity when evaluated under a
uniformly distributed ${\mathbb{D}}_{\text{ref}}$. Appendix A.2 provides the
detailed steps.

Figure 4: Approximating concave regions need denser queries than convex
regions.

######  Remark 3.3 (Relaxing the Convexity Assumption).

Even though Theorem 3.2 assumes convexity of the decision boundary for
analytical tractability, the attack can also be extended to a concave decision
boundary. This is because the closest counterfactual will always lead to a
tangent hyperplane irrespective of convexity and now the rejected region can
be seen as the intersection of these half-spaces (Lemma 3.1 does not assume
convexity). However, it is worth noting that approximating a concave decision
boundary is, in general, more difficult than approximating a convex region. To
obtain equally-spaced out tangent hyperplanes on the decision boundary, a
concave region will require a much denser set of query points (see Fig. 4) due
to the inverse effect of length contraction discussed in Aleksandrov (1967,
Chapter III Lemma 2). Furthermore, approximating a decision boundary which is
neither convex nor concave is much more challenging as the decision regions
can no longer be approximated as intersections of half-spaces.

We note that the aforementioned attack relies on the closest counterfactual
which is often challenging to generate. Practical counterfactual generation
mechanisms often provide counterfactuals that are reasonably close but may not
be exactly the closest. This motivates us to propose a more general strategy –
that we call Counterfactual Clamping Attack (CCA) – that only leverages the
fact that the counterfactuals lie closer to the decision boundary but need not
be the closest. Experiments indicate that the query complexity of CCA is
upper-bounded by the fundamental complexity bound in Theorem 3.2 (see Fig. 14
in Appendix B.2).

###  3.2 An attack based on the proximity of counterfactuals to the target
decision boundary

Before introducing our proposed attack CCA, we first discuss our rationale
behind devising this attack. Let us consider the difference of the model
output probabilities (before thresholding) as a measure of similarity between
the target and surrogate models because it would force the decision boundaries
to overlap. Our proposed attack CCA is motivated from the following
observation: the difference of two models’ output probabilities corresponding
to a given input instance $\boldsymbol{x}$ can be bounded by having another
point with matching outputs in the affinity of the instance $\boldsymbol{x}$.

######  Theorem 3.4.

Suppose the target $m(\boldsymbol{x})$ and the surrogate
$\tilde{m}(\boldsymbol{x})$ are Lipschitz continuous with constants
$\gamma_{1}$ and $\gamma_{2}$, respectively. Assume
$m(\boldsymbol{w})=\tilde{m}(\boldsymbol{w})$ for some
$\boldsymbol{w}\in[0,1]^{d}$. Then, for any $\boldsymbol{x}\in[0,1]^{d}$, the
difference between the outputs of the two models is bounded from above as
follows:
$|\tilde{m}(\boldsymbol{x})-m(\boldsymbol{x})|\leq(\gamma_{1}+\gamma_{2})||\boldsymbol{x}-\boldsymbol{w}||_{2}.$

The proof is presented in Appendix A.3. Usually, a smaller Lipschitz constant
is indicative of a higher generalizability of a model (Gouk et al. 2021; Pauli
et al. 2021).

######  Remark 3.5 (Local Lipschitz Continuity).

Global Lipschitz continuity is not always necessary. If a well-spread set of
points ${\mathbb{W}}=\\{\boldsymbol{w}_{i},i=1,\dots,N\\}$ satisfying
$m(\boldsymbol{w}_{i})=\tilde{m}(\boldsymbol{w}_{i})$ for $i=1,\dots,N$ is
available over some region ${\mathbb{A}}\subseteq[0,1]^{d}$, a more relaxed
condition of local Lipschitz continuity of $m$ and $\tilde{m}$ in the locality
of $\boldsymbol{w}_{i}$’s is sufficient to ensure the conditions of Theorem
3.4 for all $\boldsymbol{x}\in{\mathbb{A}}$ .

Proposed Counterfactual Clamping Attack: Theorem 3.4 provides the motivation
for a novel model extraction strategy. Let $\boldsymbol{w}$ be a
counterfactual. Recall that $\partial{\mathbb{M}}$ denotes the decision
boundary of $m$. As implied by the theorem, for any
$\boldsymbol{x}\in\partial{\mathbb{M}}$, the deviation of the surrogate model
output from the target model output can be bounded above by
$(\gamma_{1}+\gamma_{2})||\boldsymbol{x}-\boldsymbol{w}||_{2}$ given that all
the counterfactuals satisfy $m(\boldsymbol{w})=\tilde{m}(\boldsymbol{w})$.
Knowing that $m(\boldsymbol{w})=0.5$, we may design a loss function which
clamps $\tilde{m}(\boldsymbol{w})$ to be 0.5. _Consequently, with a sufficient
number of well-spaced counterfactuals to cover $\partial{\mathbb{M}}$, we may
achieve arbitrarily small $|\tilde{m}(\boldsymbol{x})-m(\boldsymbol{x})|$ at
the decision boundary of $m$ (Fig. 5)._

Figure 5: Rationale for Counterfactual Clamping Attack.

However, we note that simply forcing $\tilde{m}(\boldsymbol{w})$ to be exactly
equal to 0.5 is quite unstable since in practice the target model’s output
$m(\boldsymbol{w})$ is known to be close to 0.5, while being greater but may
not be exactly equal. Thus, we propose a unique loss function for training the
surrogate neural networks that does not penalize the counterfactuals that are
already inside the decision boundary of the surrogate model.

For $0<k\leq 1$, we define the loss function as

$\displaystyle L_{k}$
$\displaystyle(\tilde{m},y)=\frac{1}{\left|{\mathbb{D}}\right|}\sum_{\boldsymbol{x}\in{\mathbb{D}}}\Bigg{(}\mathds{1}\left[y(\boldsymbol{x})=0.5,\tilde{m}(\boldsymbol{x})\leq
k\right]$
$\displaystyle\times\Bigg{\\{}k\log\left(\frac{k}{\tilde{m}(\boldsymbol{x})}\right)+(1-k)\log\left(\frac{1-k}{1-\tilde{m}(\boldsymbol{x})}\right)\Bigg{\\}}$
$\displaystyle\hskip 85.35826pt+\mathds{1}\left[y(\boldsymbol{x})\neq
0.5\right]L(\tilde{m},y)\Bigg{)}.$ (4)

Here, $y(\boldsymbol{x})$ denotes the label assigned to the input instance
$\boldsymbol{x}$ by the target model, received from the API and
$L(\tilde{m},y)$ is the binary cross-entropy loss. We assume that the
counterfactuals are distinguishable from the ordinary instances, and assign
them a label of $y(\boldsymbol{w})=0.5$. Here, ${\mathbb{D}}$ denotes the set
of all query instances and the counterfactuals. The first term accounts for
the counterfactuals, where they are assigned a non-zero loss if the surrogate
model’s prediction is below $k$. This term ensures
$\tilde{m}(\boldsymbol{w})\approx k$ for the counterfactuals $\boldsymbol{w}$
but allows for counterfactuals that lie farther inside the favorable region,
which are the result of imperfections in the generating mechanisms. The second
term is the ordinary binary cross-entropy loss, which becomes non-zero only
for ordinary query instances. Note that substituting $k=1$ in
$L_{k}(\tilde{m},y)$ yields the ordinary binary cross entropy loss. Algorithm
1 summarizes the attack proposed above.

Algorithm 1 Proposed Counterfactual Clamping Attack

0: Attack dataset ${\mathbb{D}}_{\text{attack}}$, $k$ ($k\in(0,1]$, usually
0.5), API for querying

0: Trained surrogate model $\tilde{m}$

1: Initialize ${\mathbb{A}}=\\{\\}$

2: for $\boldsymbol{x}\in{\mathbb{D}}_{\text{attack}}$ do

3: Query API with $\boldsymbol{x}$ to get $y(\boldsymbol{x})$
{$y(\boldsymbol{x})\in\\{0,1\\}$}

4:
${\mathbb{A}}\leftarrow{\mathbb{A}}\cup\\{(\boldsymbol{x},y(\boldsymbol{x}))\\}$

5: if $y(\boldsymbol{x})=0$ then

6: Query API for counterfactual $\boldsymbol{w}$ of $\boldsymbol{x}$

7: ${\mathbb{A}}\leftarrow{\mathbb{A}}\cup\\{(\boldsymbol{w},0.5)\\}$ {Assign
$\boldsymbol{w}$ a label of 0.5}

8: end if

9: end for

10: Train $\tilde{m}$ on ${\mathbb{A}}$ with $L_{k}(\tilde{m},y)$ as the loss

11: return $\tilde{m}$

######  Remark 3.6 (Extensions to Other Contours).

This strategy can be extended to approximate any given contour
$\partial{\mathbb{M}}_{k}=\\{\boldsymbol{x}\in[0,1]^{d}:m(\boldsymbol{x})=k\\}$.
It can be helpful in cases where the counterfactual generating algorithm
provides counterfactuals that lie on $\partial{\mathbb{M}}_{k}$ for some
$k>0.5$, e.g., due to constraints imposed by robustness (Upadhyay, Joshi, and
Lakkaraju 2021; Hamman et al. 2023; Black, Wang, and Fredrikson 2022), given
that the attacker knows the value of $k$. When available, the probability
predictions received through the API (Tramèr et al. 2016) can be used to fine-
tune $k$.

It is noteworthy that this approach is different from the broad area of soft-
label learning (Nguyen, Valizadegan, and Hauskrecht 2011; Nguyen et al. 2011)
in two major aspects: (i) the labels in our problem do not smoothly span the
interval [0,1] – instead they are either 0, 1 or 0.5; (ii) labels of
counterfactuals do not indicate a class probability; even though a label of
0.5 is assigned, there can be counterfactuals that are well within the
surrogate decision boundary which should not be penalized. Nonetheless, we
also perform ablation studies where we compare the performance of our proposed
loss function with another potential loss which simply forces
$\tilde{m}(\boldsymbol{w})$ to be exactly $0.5$, inspired from soft-label
learning (see Appendix B.2 for results).

CCA overcomes two challenges beset in existing works; (i) the problem of
decision boundary shift (particularly with one-sided counterfactuals) present
in the method suggested by Aïvodji, Bolot, and Gambs (2020) and (ii) the need
for counterfactuals from both sides of the decision boundary in the methods of
Aïvodji, Bolot, and Gambs (2020) and Wang, Qian, and Miao (2022).

Figure 6: A 2-dimensional demonstration of the proposed attack. Orange and blue shades denote the favorable and unfavorable decision regions of each model. Circles denote the target model’s training data. Table 1: Fidelity achieved with 400 queries on the real-world datasets. Values presented are the averages $\pm$ standard deviations (as percentages) over an ensemble of size 100. Target model has hidden layers with neurons (20,10). Model 0 is similar to the target model in architecture. Model 1 has hidden layers with neurons (20, 10, 5). | Architecture known (model 0) | Architecture unknown (model 1)
---|---|---
Dataset | ${\mathbb{D}}_{\text{test}}$ | ${\mathbb{D}}_{\text{uni}}$ | ${\mathbb{D}}_{\text{test}}$ | ${\mathbb{D}}_{\text{uni}}$
| Base. | CCA | Base. | CCA | Base. | CCA | Base. | CCA
Adult In. | 91$\pm$3.2 | 94$\pm$3.2 | 84$\pm$3.2 | 91$\pm$3.2 | 91$\pm$4.5 | 94$\pm$3.2 | 84$\pm$3.2 | 90$\pm$3.2
COMPAS | 92$\pm$3.2 | 96$\pm$2.0 | 94$\pm$1.7 | 96$\pm$2.0 | 91$\pm$8.9 | 96$\pm$3.2 | 94$\pm$2.0 | 94$\pm$8.9
DCCC | 89$\pm$8.9 | 99$\pm$0.9 | 95$\pm$2.2 | 96$\pm$1.4 | 90$\pm$7.7 | 97$\pm$4.5 | 95$\pm$2.2 | 95$\pm$11.8
HELOC | 91$\pm$4.7 | 96$\pm$2.2 | 92$\pm$2.8 | 94$\pm$2.4 | 90$\pm$7.4 | 95$\pm$5.5 | 91$\pm$3.3 | 93$\pm$3.2
Figure 7: Dependence of fidelity on the target model’s Lipschitz constant. The
approximations of the Lipschitz constants are shown in the legend with
standard deviations within brackets. Lipschitz constants are approximated as
the product of the spectral norm of weight matrices in each model. With a
higher Lipschitz constant, the fidelity achieved by a given number of queries
tend to degrade.

##  4 Experiments

We carry out a number of experiments to study the performance of our proposed
strategy CCA. We include some results here and provide further details in
Appendix B.

All the classifiers are neural networks unless specified otherwise and their
decision boundaries are not necessarily convex. We compare the performance of
our proposed attack CCA with the existing attack presented in (Aïvodji, Bolot,
and Gambs 2020) that we refer to as “Baseline” for the case of one-sided
counterfactuals. As the initial counterfactual generating method, we use an
implementation of the Minimum Cost Counterfactuals (MCCF) by Wachter,
Mittelstadt, and Russell (2017).

Performance metrics: Fidelity is used for evaluating the agreement between the
target and surrogate models. It is evaluated over both uniformly generated
instances (denoted by ${\mathbb{D}}_{\text{uni}}$) and test data instances
from the data manifold (denoted by ${\mathbb{D}}_{\text{test}}$) as the
reference dataset ${\mathbb{D}}_{\text{ref}}$.

Results: A summary of the main experiments is provided below. Additional
experiments are detailed in Appendix B.

(i) Visualizing the attack using synthetic data: First, the effect of the
proposed loss function in mitigating the decision boundary shift is observed
over a 2-D synthetic dataset. Fig. 6 presents the results. In the figure, it
is clearly visible that the Baseline model is affected by a decision boundary
shift. In contrast, the CCA model’s decision boundary closely approximates the
target decision boundary. See Appendix B.2 for more details.

(ii) Comparing performance over four real-world dataset: We use four publicly
available real-world datasets namely, Adult Income, COMPAS, DCCC, and HELOC
(see Appendix B.1) for our experiments. Table 1 provides some of the results
over four real-world datasets. We refer to Appendix B.2 (specifically Fig. 11)
for additional results. In all cases, we observe that CCA has either better or
similar fidelity as compared to Baseline.

(iii) Studying effects of Lipschitz constants: We study the connection between
the target model’s Lipschitz constant and the attack performance. Target
model’s Lipschitz constant is controlled by changing the
$L_{2}-$regularization coefficient, while keeping the surrogate models fixed.
Results are presented in Fig. 7. Target models with a smaller Lipschitz
constant are easier to extract. More details are provided in Appendix B.2.

(iv) Studying different model architectures: We also consider different
surrogate model architectures spanning models that are more complex than the
target model to much simpler ones. Results show that when sufficiently close
to the target model in complexity, the surrogate architecture plays a little
role on the performance. Otherwise, the performance degrades. See Fig. 15 and
Appendix B.2 for details. Furthermore, two situations are considered where the
target model is not a neural network (Fig. 19 and Appendix B.2). In both
scenarios, CCA surpasses the baseline.

(v) Studying other counterfactual generating methods: Effects of
counterfactuals being sparse, actionable, and realistic are observed. Sparse
counterfactuals are generated by using $L_{1}-$norm as the cost function.
Actionable counterfactuals are generated using DiCE (Mothilal, Sharma, and Tan
2020) by defining a set of immutable features. Realistic counterfactuals are
generated by retrieving the 1-Nearest-Neighbor for a given query from the
dataset. The results are given in Table 5 with additional details in Appendix
B.2.

(vi) Studying alternate loss functions: We explore using binary cross-entropy
loss function directly with labels 0, 1 and 0.5, in place of the proposed
loss. However, experiments indicate that this scheme performs poorly when
compared with the CCA loss (see Fig. 20 and Appendix B.2).

(vii) Validating Theorem 3.2: Empirical verification of the theorem is done
through synthetic experiments, where the model has a spherical decision
boundary since they are known to be more difficult for polytope approximation
(Arya, Da Fonseca, and Mount 2012). Fig. 8 presents a log-log plot comparing
the theoretical and empirical query complexities for several dimensionality
values $d$. The empirical approximation error decays faster than
$n^{-2/(d-1)}$ as predicted by the theorem (see Appendix B.3).

Figure 8: Verifying Theorem 3.2: Dotted and solid lines indicate the
theoretical and empirical rates of convergence.

##  5 Conclusion

Our work provides novel insights that bridge explainability and privacy. We
introduce novel model extraction strategies aided by counterfactuals, along
with the analyses of the corresponding query complexities. The two attacks
exploit (i) properties of closest counterfactuals; and (ii) the proximity of
the counterfactuals to the target model’s decision boundary, respectively. Our
work addresses an important knowledge gap in the existing literature by
providing theoretical guarantees using random polytope theory. Furthermore,
our attacks address the issue of decision boundary shift amidst a system
providing one-sided counterfactuals. Experiments demonstrate a significant
improvement in fidelity compared to the baseline method proposed in Aïvodji,
Bolot, and Gambs (2020) for the case of one-sided counterfactuals. Results
show that the attack performs well across different model types and
counterfactual generating methods. Our findings also highlight an interesting
connection between Lipschitz constant and vulnerability to model extraction.

Limitations and future work: Utilizing techniques in active learning in
conjunction with counterfactuals is another problem of interest. Extending the
results of this work for multi-class classification scenarios can also be
explored. The relationship between Lipschitz constant and vulnerability to
model extraction may have implications for future work on generalization,
adversarial robustness, etc.

One limitation of our theoretical results is the assumption of a convex
decision boundary. While this assumption may be satisfied in some settings
(Amos, Xu, and Kolter 2017), it is not always the case. In addition, the
derivations require the counterfactual generating mechanisms to provide the
closest counterfactuals. Any relaxation to these assumptions are paths for
exploration. We note that the attack proposed in Section 3.2 remains valid as
long as the majority of counterfactuals lie closer to the decision boundary;
they need not be the closest ones to the corresponding original instances.

##  6 Broader Impact

We demonstrate that one-sided counterfactuals can be used for perfecting model
extraction attacks, exposing a potential vulnerability in MLaaS platforms.
Given the importance of counterfactuals in explaining model predictions, we
hope our work will inspire countermeasures and defense strategies, paving the
way toward secure and trustworthy machine learning systems.

## References

  * Aïvodji, Bolot, and Gambs (2020) Aïvodji, U.; Bolot, A.; and Gambs, S. 2020.  Model extraction from counterfactual explanations.  _arXiv preprint arXiv:2009.01884_.
  * Aleksandrov (1967) Aleksandrov, A. D. 1967.  _A. D. Alexandrov: Selected Works Part II: Intrinsic Geometry of Convex Surfaces_.  American Mathematical Society.
  * Amos, Xu, and Kolter (2017) Amos, B.; Xu, L.; and Kolter, J. Z. 2017.  Input Convex Neural Networks.  In _Proceedings of the 34th International Conference on Machine Learning_ , 146–155. PMLR.  ISSN: 2640-3498.
  * Angwin et al. (2016) Angwin, J.; Larson, J.; Mattu, S.; and Kirchner, L. 2016.  Machine Bias.  ProPublica.
  * Arya, Da Fonseca, and Mount (2012) Arya, S.; Da Fonseca, G. D.; and Mount, D. M. 2012.  Polytope Approximation and the Mahler Volume.  In _Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms_ , 29–42. Society for Industrial and Applied Mathematics.
  * Barocas, Selbst, and Raghavan (2020) Barocas, S.; Selbst, A. D.; and Raghavan, M. 2020.  The hidden assumptions behind counterfactual explanations and principal reasons.  In _Proceedings of the 2020 Conference on Fairness, Accountability, and Transparency_ , 80–89.
  * Bartlett, Foster, and Telgarsky (2017) Bartlett, P. L.; Foster, D. J.; and Telgarsky, M. J. 2017.  Spectrally-normalized margin bounds for neural networks.  In _Advances in Neural Information Processing Systems_ , volume 30.
  * Becker and Kohavi (1996) Becker, B.; and Kohavi, R. 1996.  Adult.  UCI Machine Learning Repository.  DOI: https://doi.org/10.24432/C5XW20.
  * Black, Wang, and Fredrikson (2022) Black, E.; Wang, Z.; and Fredrikson, M. 2022.  Consistent Counterfactuals for Deep Models.  In _International Conference on Learning Representations_.
  * Böröczky Jr and Reitzner (2004) Böröczky Jr, K.; and Reitzner, M. 2004.  Approximation of smooth convex bodies by random circumscribed polytopes.  _The Annals of Applied Probability_ , 14(1): 239–273.
  * Deutch and Frost (2019) Deutch, D.; and Frost, N. 2019.  Constraints-based explanations of classifications.  In _IEEE 35th International Conference on Data Engineering_ , 530–541.
  * Dhurandhar et al. (2018) Dhurandhar, A.; Chen, P.-Y.; Luss, R.; Tu, C.-C.; Ting, P.; Shanmugam, K.; and Das, P. 2018.  Explanations based on the missing: Towards contrastive explanations with pertinent negatives.  In _Advances in Neural Information Processing Systems_ , volume 31.
  * FICO (2018) FICO. 2018.  Explainable Machine Learning Challenge.
  * Goethals, Sörensen, and Martens (2023) Goethals, S.; Sörensen, K.; and Martens, D. 2023.  The privacy issue of counterfactual explanations: Explanation linkage attacks.  _ACM Transactions on Intelligent Systems and Technology_ , 14(5): 1–24.
  * Gong et al. (2021) Gong, X.; Chen, Y.; Yang, W.; Mei, G.; and Wang, Q. 2021.  InverseNet: Augmenting Model Extraction Attacks with Training Data Inversion.  In _Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence_ , 2439–2447.
  * Gong et al. (2020) Gong, X.; Wang, Q.; Chen, Y.; Yang, W.; and Jiang, X. 2020.  Model extraction attacks and defenses on cloud-based machine learning models.  _IEEE Communications Magazine_ , 58(12): 83–89.
  * Gouk et al. (2021) Gouk, H.; Frank, E.; Pfahringer, B.; and Cree, M. J. 2021.  Regularisation of neural networks by enforcing lipschitz continuity.  _Machine Learning_ , 110: 393–416.
  * Guidotti (2022) Guidotti, R. 2022.  Counterfactual explanations and how to find them: Literature review and benchmarking.  _Data Mining and Knowledge Discovery_ , 1–55.
  * Hamman et al. (2023) Hamman, F.; Noorani, E.; Mishra, S.; Magazzeni, D.; and Dutta, S. 2023.  Robust Counterfactual Explanations for Neural Networks With Probabilistic Guarantees.  In _40th International Conference on Machine Learning_.
  * Jagielski et al. (2020) Jagielski, M.; Carlini, N.; Berthelot, D.; Kurakin, A.; and Papernot, N. 2020.  High accuracy and high fidelity extraction of neural networks.  In _Proceedings of the 29th USENIX Conference on Security Symposium_ , 1345–1362.
  * Juuti et al. (2019) Juuti, M.; Szyller, S.; Marchal, S.; and Asokan, N. 2019.  PRADA: Protecting against DNN model stealing attacks.  In _2019 IEEE European Symposium on Security and Privacy_ , 512–527.
  * Karimi et al. (2020) Karimi, A.-H.; Barthe, G.; Balle, B.; and Valera, I. 2020.  Model-agnostic counterfactual explanations for consequential decisions.  In _International Conference on Artificial Intelligence and Statistics_ , 895–905.
  * Karimi et al. (2022) Karimi, A.-H.; Barthe, G.; Schölkopf, B.; and Valera, I. 2022.  A survey of algorithmic recourse: Contrastive explanations and consequential recommendations.  _ACM Computing Surveys_ , 55(5): 1–29.
  * Laugel et al. (2017) Laugel, T.; Lesot, M.-J.; Marsala, C.; Renard, X.; and Detyniecki, M. 2017.  Inverse classification for comparison-based interpretability in machine learning.  _arXiv preprint arXiv:1712.08443_.
  * Lee (2009) Lee, J. M. 2009.  _Manifolds and Differential Geometry_.  Graduate Studies in Mathematics. American Mathematical Society.
  * Liu et al. (2020) Liu, X.; Han, X.; Zhang, N.; and Liu, Q. 2020.  Certified Monotonic Neural Networks.  In _Advances in Neural Information Processing Systems_ , volume 33, 15427–15438.
  * Marques-Silva et al. (2021) Marques-Silva, J.; Gerspacher, T.; Cooper, M. C.; Ignatiev, A.; and Narodytska, N. 2021.  Explanations for Monotonic Classifiers.  In _38th International Conference on Machine Learning_.
  * Milli et al. (2019) Milli, S.; Schmidt, L.; Dragan, A. D.; and Hardt, M. 2019.  Model reconstruction from model explanations.  In _Proceedings of the Conference on Fairness, Accountability, and Transparency_ , 1–9.
  * Mishra et al. (2021) Mishra, S.; Dutta, S.; Long, J.; and Magazzeni, D. 2021.  A Survey on the Robustness of Feature Importance and Counterfactual Explanations.  _arXiv e-prints_ , arXiv:2111.00358.
  * Mothilal, Sharma, and Tan (2020) Mothilal, R. K.; Sharma, A.; and Tan, C. 2020.  Explaining Machine Learning Classifiers through Diverse Counterfactual Explanations.  In _Proceedings of the 2020 Conference on Fairness, Accountability, and Transparency_.
  * Nguyen, Valizadegan, and Hauskrecht (2011) Nguyen, Q.; Valizadegan, H.; and Hauskrecht, M. 2011.  Learning classification with auxiliary probabilistic information.  _IEEE International Conference on Data Mining_ , 2011: 477–486.
  * Nguyen et al. (2011) Nguyen, Q.; Valizadegan, H.; Seybert, A.; and Hauskrecht, M. 2011.  Sample-efficient learning with auxiliary class-label information.  _AMIA Annual Symposium Proceedings_ , 2011: 1004–1012.
  * Oliynyk, Mayer, and Rauber (2023) Oliynyk, D.; Mayer, R.; and Rauber, A. 2023.  I Know What You Trained Last Summer: A Survey on Stealing Machine Learning Models and Defences.  _ACM Computing Surveys_ , 55(14s).
  * Pal et al. (2020) Pal, S.; Gupta, Y.; Shukla, A.; Kanade, A.; Shevade, S.; and Ganapathy, V. 2020\.  Activethief: Model extraction using active learning and unannotated public data.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 34, 865–872.
  * Papernot et al. (2017) Papernot, N.; McDaniel, P.; Goodfellow, I.; Jha, S.; Celik, Z. B.; and Swami, A. 2017.  Practical black-box attacks against machine learning.  In _Proceedings of the 2017 ACM on Asia Conference on Computer and Communications Security_ , 506–519.
  * Pauli et al. (2021) Pauli, P.; Koch, A.; Berberich, J.; Kohler, P.; and Allgöwer, F. 2021.  Training robust neural networks using Lipschitz bounds.  _IEEE Control Systems Letters_ , 6: 121–126.
  * Pawelczyk, Lakkaraju, and Neel (2023) Pawelczyk, M.; Lakkaraju, H.; and Neel, S. 2023.  On the Privacy Risks of Algorithmic Recourse.  In _Proceedings of the 26th International Conference on Artificial Intelligence and Statistics_ , volume 206, 9680–9696.
  * Shokri, Strobel, and Zick (2021) Shokri, R.; Strobel, M.; and Zick, Y. 2021.  On the privacy risks of model explanations.  In _Proceedings of the 2021 AAAI/ACM Conference on AI, Ethics, and Society_ , 231–241.
  * Tramèr et al. (2016) Tramèr, F.; Zhang, F.; Juels, A.; Reiter, M. K.; and Ristenpart, T. 2016.  Stealing machine learning models via prediction APIs.  In _25th USENIX Security Symposium_ , 601–618.
  * Upadhyay, Joshi, and Lakkaraju (2021) Upadhyay, S.; Joshi, S.; and Lakkaraju, H. 2021.  Towards robust and reliable algorithmic recourse.  _Advances in Neural Information Processing Systems_ , 34: 16926–16937.
  * Verma et al. (2022) Verma, S.; Boonsanong, V.; Hoang, M.; Hines, K. E.; Dickerson, J. P.; and Shah, C. 2022.  Counterfactual Explanations and Algorithmic Recourses for Machine Learning: A Review.  _arXiv preprint arXiv:2010.10596_.
  * Wachter, Mittelstadt, and Russell (2017) Wachter, S.; Mittelstadt, B.; and Russell, C. 2017.  Counterfactual Explanations without Opening the Black Box: Automated Decisions and the GDPR.  _Harvard Journal of Law and Technology_ , 31: 841.
  * Wang, Qian, and Miao (2022) Wang, Y.; Qian, H.; and Miao, C. 2022.  DualCF: Efficient Model Extraction Attack from Counterfactual Explanations.  In _2022 ACM Conference on Fairness, Accountability, and Transparency_ , 1318–1329.
  * Yadav, Moshkovitz, and Chaudhuri (2023) Yadav, C.; Moshkovitz, M.; and Chaudhuri, K. 2023.  XAudit : A Theoretical Look at Auditing with Explanations.  _arXiv:2206.04740_.
  * Yeh (2016) Yeh, I.-C. 2016.  Default of Credit Card Clients.  UCI Machine Learning Repository.  DOI: https://doi.org/10.24432/C55S3H.

##  Appendix A Proofs

###  A.1 Proof of Lemma 2.6 and Lemma 3.1

See 2.6

###### Proof.

From Definition 2.5, there exists a non-empty neighborhood
$\mathcal{B}_{\boldsymbol{w}}$ around $\boldsymbol{w}$, such that
$\forall\boldsymbol{x}\in\mathcal{B}_{\boldsymbol{w}}$ with
$\mathcal{S}(\boldsymbol{x})=0$ and $\boldsymbol{x}\neq\boldsymbol{w}$, only
one of $\mathcal{T}(\boldsymbol{x})>0$ or $\mathcal{T}(\boldsymbol{x})<0$
holds. Let $\boldsymbol{x}=(x_{1},x_{2},\dots,x_{d})$ and
$\boldsymbol{x}_{[p]}$ denote $\boldsymbol{x}$ without $x_{p}$ for $1\leq
p\leq d$. Then, within the neighborhood $\mathcal{B}_{\boldsymbol{w}}$, we may
re-parameterize $\mathcal{S}(\boldsymbol{x})=0$ as
$x_{p}=S(\boldsymbol{x}_{[p]})$. Note that a similar re-parameterization
denoted by $x_{p}=T(\boldsymbol{x}_{[p]})$ can be applied to
$\mathcal{T}(\boldsymbol{x})=0$ as well. Let
$\mathcal{A}_{\boldsymbol{w}}=\left\\{\boldsymbol{x}_{[p]}:\boldsymbol{x}\in\mathcal{B}_{\boldsymbol{w}}\setminus\\{\boldsymbol{w}\\}\right\\}$.
From Definition 2.5, all
$\boldsymbol{x}\in\mathcal{B}_{\boldsymbol{w}}\setminus\\{\boldsymbol{w}\\}$
satisfy only one of $\mathcal{T}(\boldsymbol{x})<0$ or
$\mathcal{T}(\boldsymbol{x})>0$, and hence without loss of generality the re-
parameterization of $\mathcal{T}(\boldsymbol{x})=0$ can be such that
$S(\boldsymbol{x}_{[p]})<T(\boldsymbol{x}_{[p]})$ holds for all
$\boldsymbol{x}_{[p]}\in\mathcal{A}_{\boldsymbol{w}}$. Now, define
$F(\boldsymbol{x}_{[p]})\equiv
T(\boldsymbol{x}_{[p]})-S(\boldsymbol{x}_{[p]})$. Observe that
$F(\boldsymbol{x}_{[p]})$ has a minimum at $\boldsymbol{w}$ and hence,
$\nabla_{\boldsymbol{x}_{[p]}}F(\boldsymbol{w}_{[p]})=0$. Consequently,
$\nabla_{\boldsymbol{x}_{[p]}}T(\boldsymbol{w}_{[p]})=\nabla_{\boldsymbol{x}_{[p]}}S(\boldsymbol{w}_{[p]})$,
which implies that the tangent hyperplanes to both hypersurfaces have the same
gradient at $\boldsymbol{w}$. Proof concludes by observing that since both
tangent hyperplanes go through $\boldsymbol{w}$, the two hypersurfaces should
share a common tangent hyperplane at $\boldsymbol{w}$. ∎

See 3.1

###### Proof.

The proof utilizes the following lemma.

######  Lemma A.1.

Consider the $d$-dimensional ball $\mathcal{C}_{\boldsymbol{x}}$ centered at
$\boldsymbol{x}$, with $\boldsymbol{w}$ lying on its boundary (hence
$\mathcal{C}_{\boldsymbol{x}}$ intersects $\mathcal{S}$ at $\boldsymbol{w}$).
Then, $\mathcal{S}$ lies completely outside $\mathcal{C}_{\boldsymbol{x}}$.

The proof of Lemma A.1 follows from the following contradiction. Assume a part
of $\mathcal{S}$ lies within $\mathcal{C}_{\boldsymbol{x}}$. Then, points on
the intersection of $\mathcal{S}$ and the interior of
$\mathcal{C}_{\boldsymbol{x}}$ are closer to $\boldsymbol{x}$ than
$\boldsymbol{w}$. Hence, $\boldsymbol{w}$ can no longer be the closest point
to $\boldsymbol{x}$, on $\mathcal{S}$.

From Lemma A.1, $\mathcal{C}_{\boldsymbol{x}}$ is touching the curve
$\mathcal{S}$ at $\boldsymbol{w}$, and hence, they share the same tangent
hyperplane at $\boldsymbol{w}$ by Lemma 2.6. Now, observing that the line
joining $\boldsymbol{w}$ and $\boldsymbol{x}$, being a radius of
$\mathcal{C}_{\boldsymbol{x}}$, is the normal to the ball at $\boldsymbol{w}$
concludes the proof (see Fig. 9). ∎

Figure 9: Line joining the query and its closest counterfactual is
perpendicular to the decision boundary at the counterfactual. See Lemma 3.1
for details.

We present the following corollary as an additional observation resulting from
Lemma A.1.

######  Corollary A.2.

Following Lemma A.1, it can be seen that all the points in the $d$-dimensional
ball with $\boldsymbol{x}$ as the center and $\boldsymbol{w}$ on boundary lies
on the same side of $\mathcal{S}$ as $\boldsymbol{x}$.

###  A.2 Proof of Theorem 3.2

See 3.2

###### Proof.

We first have a look at Böröczky Jr and Reitzner (2004, Theorem 1 (restated as
Theorem A.3 below)) from the polytope theory. Let ${\mathbb{M}}$ be a compact
convex set with a second-order differentiable boundary denoted by
$\partial{\mathbb{M}}$. Let $\boldsymbol{a}_{1},\dots,\boldsymbol{a}_{n}$ be
$n$ randomly chosen points on $\partial{\mathbb{M}}$, distributed
independently and identically according to a given density
$d_{\partial{\mathbb{M}}}$. Denote by $H_{+}(\boldsymbol{a}_{i})$ the
supporting hyperplane of $\partial{\mathbb{M}}$ at $\boldsymbol{a}_{i}$.
Assume $C$ to be a large enough hypercube which contains ${\mathbb{M}}$ in its
interior.

Now, define

$\tilde{{\mathbb{M}}}_{n}=\bigcap_{i=1}^{n}H_{+}(\boldsymbol{a}_{i})\cap C$
(5)

which is the polytope created by the intersection of all the supporting
hyperplanes. The theorem characterizes the expected difference of the volumes
of ${\mathbb{M}}$ and $\tilde{{\mathbb{M}}}_{n}$.

######  Theorem A.3 (Random Polytope Approximation, (Böröczky Jr and Reitzner
2004)).

For a convex compact set ${\mathbb{M}}$ with second-order differentiable
$\partial{\mathbb{M}}$ and non-zero continuous density
$d_{\partial{\mathbb{M}}}$,

$\mathbb{E}\left[{V(\tilde{{\mathbb{M}}}_{n})-V({\mathbb{M}})}\right]=\tau\left(\partial{\mathbb{M}},d\right)n^{-\frac{2}{d-1}}+o\left(n^{-\frac{2}{d-1}}\right)$
(6)

as $n\rightarrow\infty$, where $V(\cdot)$ denotes the volume (i.e., the
Lebesgue measure), and $\tau(\partial{\mathbb{M}},d)$ is a constant that
depends only on the boundary $\partial{\mathbb{M}}$ and the dimensionality $d$
of the space.

Let $\textbf{x}_{i},i=1,\dots,n$ be $n$ i.i.d queries from the
$\left\lfloor{m(\textbf{x})}\right\rceil=0$ region of the target model. Then,
their corresponding counterfactuals $g_{m}(\textbf{x}_{i})$ are also i.i.d.
Furthermore, they lie on the decision boundary of $m$. Hence, we may arrive at
the following result.

######  Corollary A.4.

Let
${\mathbb{M}}=\\{\boldsymbol{x}\in[0,1]^{d}:\left\lfloor{m(\boldsymbol{x})}\right\rceil=1\\}$
and
$\tilde{{\mathbb{M}}}_{n}=\\{\boldsymbol{x}\in[0,1]^{d}:\left\lfloor{\tilde{M}_{n}(\boldsymbol{x})}\right\rceil=1\\}$.
Then, by Theorem A.3,

$\mathbb{E}\left[{V(\tilde{{\mathbb{M}}}_{n})-V({\mathbb{M}})}\right]\sim\mathcal{O}\left(n^{-\frac{2}{d-1}}\right)$
(7)

when $n\rightarrow\infty$. Note that
${\mathbb{M}}\subseteq\tilde{{\mathbb{M}}}_{n}$ and hence, the left-hand side
is always non-negative.

From Definition 2.3, we may write

$\displaystyle\mathbb{E}\left[{{\rm
Fid}_{m,{\mathbb{D}}_{\text{ref}}}(\tilde{M}_{n})}\right]$
$\displaystyle=\mathbb{E}\left[{\frac{1}{\left|{\mathbb{D}}_{\text{ref}}\right|}\sum_{\textbf{x}\in{\mathbb{D}}_{\text{ref}}}\mathbb{E}\left[{\mathds{1}\left[\left\lfloor{m(\textbf{x})}\right\rceil=\left\lfloor{\tilde{M}_{n}(\textbf{x})}\right\rceil\right]\Big{|}{\mathbb{D}}_{\text{ref}}}\right]}\right]$
(8)
$\displaystyle=\frac{1}{\left|{\mathbb{D}}_{\text{ref}}\right|}\mathbb{E}\left[{\sum_{\textbf{x}\in{\mathbb{D}}_{\text{ref}}}{\mathbb{P}}\left[\left\lfloor{m(\textbf{x})}\right\rceil=\left\lfloor{\tilde{M}_{n}(\textbf{x})}\right\rceil\Big{|}\textbf{x}\right]}\right]\quad(\because\text{query
size is fixed})$ (9)
$\displaystyle={\mathbb{P}}\left[\left\lfloor{m(\textbf{x})}\right\rceil=\left\lfloor{\tilde{M}_{n}(\textbf{x})}\right\rceil\right]\quad(\because\textbf{x}\text{'s
are i.i.d.})$ (10)
$\displaystyle=\int_{\mathcal{M}_{n}}{\mathbb{P}}\left[\left\lfloor{m(\textbf{x})}\right\rceil=\left\lfloor{\tilde{M}_{n}(\textbf{x})}\right\rceil\Big{|}\tilde{M}_{n}(\textbf{x})=\tilde{m}_{n}(\textbf{x})\right]{\mathbb{P}}\left[\tilde{M}_{n}(\textbf{x})=\tilde{m}_{n}(\textbf{x})\right]\text{d}\tilde{m}_{n}$
(11)

where $\mathcal{M}_{n}$ is the set of all possible $\tilde{m}_{n}$’s.

Now, by noting that

${\mathbb{P}}\left[\left\lfloor{m(\textbf{x})}\right\rceil=\left\lfloor{\tilde{M}_{n}(\textbf{x})}\right\rceil\Big{|}\tilde{M}_{n}(\textbf{x})=\tilde{m}_{n}(\textbf{x})\right]=1-{\mathbb{P}}\left[\left\lfloor{m(\textbf{x})}\right\rceil\neq\left\lfloor{\tilde{M}_{n}(\textbf{x})}\right\rceil\Big{|}\tilde{M}_{n}(\textbf{x})=\tilde{m}_{n}(\textbf{x})\right],$
(12)

we may obtain

$\displaystyle\mathbb{E}\left[{{\rm
Fid}_{m,{\mathbb{D}}_{\text{ref}}}(\tilde{M}_{n})}\right]$
$\displaystyle=1-\int_{\mathcal{M}_{n}}{\mathbb{P}}\left[\left\lfloor{m(\textbf{x})}\right\rceil\neq\left\lfloor{\tilde{M}_{n}(\textbf{x})}\right\rceil\Big{|}\tilde{M}_{n}(\textbf{x})=\tilde{m}_{n}(\textbf{x})\right]$
$\displaystyle\hskip
170.71652pt\times{\mathbb{P}}\left[\tilde{M}_{n}(\textbf{x})=\tilde{m}_{n}(\textbf{x})\right]\text{d}\tilde{m}_{n}$
(13)
$\displaystyle=1-\int_{\mathcal{M}_{n}}\frac{V(\tilde{{\mathbb{M}}}_{n})-V({\mathbb{M}})}{\underbrace{\text{Total
volume}}_{=1\text{ for unit
hypercube}}}{\mathbb{P}}\left[\tilde{M}_{n}(\textbf{x})=\tilde{m}_{n}(\textbf{x})\right]\text{d}\tilde{m}_{n}$
$\displaystyle\hskip 159.3356pt(\because\textbf{x}\text{'s are uniformly
distributed})$ (14)
$\displaystyle=1-\mathbb{E}\left[{V(\tilde{{\mathbb{M}}}_{n})-V({\mathbb{M}})}\right].$
(15)

The above result, in conjunction with Corollary A.4, concludes the proof. ∎

###  A.3 Proof of Theorem 3.4

See 3.4

###### Proof.

$\displaystyle|\tilde{m}(\boldsymbol{x})-m(\boldsymbol{x})|$
$\displaystyle=|\tilde{m}(\boldsymbol{x})-\tilde{m}(\boldsymbol{w})-\left(m(\boldsymbol{x})-\tilde{m}(\boldsymbol{w})\right)|$
(16)
$\displaystyle=|\tilde{m}(\boldsymbol{x})-\tilde{m}(\boldsymbol{w})-\left(m(\boldsymbol{x})-m(\boldsymbol{w})\right)|$
(17)
$\displaystyle\leq\underbrace{|\tilde{m}(\boldsymbol{x})-\tilde{m}(\boldsymbol{w})|}_{\leq\gamma_{1}||\boldsymbol{x}-\boldsymbol{w}||_{2}}+\underbrace{|m(\boldsymbol{x})-m(\boldsymbol{w})|}_{\leq\gamma_{2}||\boldsymbol{x}-\boldsymbol{w}||_{2}}$
(18)
$\displaystyle\leq(\gamma_{1}+\gamma_{2})||\boldsymbol{x}-\boldsymbol{w}||_{2}$
(19)

where the first inequality is a result of applying the triangle inequality and
the second follows from the definition of Lipschitz continuity (Definition
2.7). ∎

##  Appendix B Experimental Details and Additional Results

###  B.1 Details of Real-World Datasets

We use four publicly available real-world tabular datasets (namely, Adult
Income, COMPAS, DCCC, and HELOC) to evaluate the performance of the attack
proposed in Section 3.2. The details of these datasets are as follows:

  * •

Adult Income: The dataset is a 1994 census database with information such as
educational level, marital status, age and annual income of individuals
(Becker and Kohavi 1996). The target is to predict “income”, which indicates
whether the annual income of a given person exceeds $50000 or not (i.e.,
$y=\mathds{1}[\text{income}\geq 0.5]$). It contains 32561 instances in total
(the training set), comprising of 24720 from $y=0$ and 7841 from $y=1$. To
make the dataset class-wise balanced we randomly sample 7841 instances from
class $y=0$, giving a total effective size of 15682 instances. Each instance
has 6 numerical features and 8 categorical features. During pre-processing,
categorical features are encoded as integers. All the features are then
normalized to the range $[0,1]$.

  * •

Home Equity Line of Credit (HELOC): This dataset contains information about
customers who have requested a credit line as a percentage of home equity
(FICO 2018). It contains 10459 instances with 23 numerical features each.
Prediction target is “is_at_risk” which indicates whether a given customer
would pay the loan in the future. Dataset is slightly unbalanced with class
sizes of 5000 and 5459 for $y=0$ and $y=1$, respectively. Instead of using all
23 features, we use the following subset of 10 for our experiments;
“estimate_of_risk”, “net_fraction_of_revolving_burden”,
“percentage_of_legal_trades”, “months_since_last_inquiry_not_recent”,
“months_since_last_trade”, “percentage_trades_with_balance”,
“number_of_satisfactory_trades”, “average_duration_of_resolution”,
“nr_total_trades”, “nr_banks_with_high_ratio”. ALl the features are normalized
to lie in the range $[0,1]$.

  * •

Correctional Offender Management Profiling for Alternative Sanctions (COMPAS):
This dataset has been used for investigating racial biases in a commercial
algorithm used for evaluating reoffending risks of criminal defendants (Angwin
et al. 2016). It includes 6172 instances and 20 numerical features. The target
variable is “is_recid”. Class-wise counts are 3182 and 2990 for $y=0$ and
$y=1$, respectively. All the features are normalized to the interval $[0,1]$
during pre-processing.

  * •

Default of Credit Card Clients (DCCC): The dataset includes information about
credit card clients in Taiwan (Yeh 2016). The target is to predict whether a
client will default on the credit or not, indicated by
“default.payment.next.month”. The dataset contains 30000 instances with 24
attributes each. Class-wise counts are 23364 from $y=0$ and 6636 from $y=1$.
To alleviate the imbalance, we randomly select 6636 instances from $y=0$
class, instead of using all the instances. All the attributes are numerical,
and normalized to $[0,1]$ during pre-processing.

###  B.2 Experiments on the attack proposed in Section 3.2

In this section, we provide details about our experimental setup with
additional results. For convenience, we present the neural network model
architectures by specifying the number of neurons in each hidden layer as a
tuple, where the leftmost element corresponds to the layer next to the input;
e.g.: a model specified as (20,30,10) has the following architecture:

Input $\rightarrow$ Dense(20, ReLU) $\rightarrow$ Dense(30, ReLU)
$\rightarrow$ Dense(10, ReLU) $\rightarrow$ Output(Sigmoid)

Other specifications of the models, as detailed below, are similar across most
of the experiments. Changes are specified specifically. The hidden layer
activations are ReLU and the layer weights are $L_{2}-$regularized. The
regularization coefficient is 0.001. Each model is trained for 200 epochs,
with a batch size of 32.

Fidelity is evaluated over a uniformly sampled set of input instances (uniform
data) as well as a held-out portion of the original data (test data). The
experiments were carried out as follows:

  1. 1.

Initialize the target model. Train using ${\mathbb{D}}_{\text{train}}$.

  2. 2.

For $t=1,2,\dots,T:$

    1. (a)

Sample $N\times t$ data points from the dataset to create
${\mathbb{D}}_{\text{attack}}$.

    2. (b)

Carry-out the attack given in Algorithm 1 with ${\mathbb{D}}_{\text{attack}}$.
Use $k=1$ for “Baseline” models and $k=0.5$ for “Proposed” models.

    3. (c)

Record the fidelity over ${\mathbb{D}}_{\text{ref}}$ along with $t$.

  3. 3.

Repeat steps 1 and 2 for $S$ number of times and calculate average fidelities
for each $t$, across repetitions.

Based on the experiments of Aïvodji, Bolot, and Gambs (2020) and Wang, Qian,
and Miao (2022), we select $T,N=20$ and $S=100$, unless specified otherwise.

#### Visualizing the attack using synthetic data

This experiment is conducted on a synthetic dataset which consists of $1000$
samples generated using the make_moons function from the sklearn package.
Features are normalized to the range $[0,1]$ before feeding to the classifier.
The target model has 4 hidden layers with the architecture (10, 20, 20, 10).
The surrogate model is 3-layered with the architecture (10, 20, 20). Each
model is trained for 100 epochs. Since the intention of this experiment is to
demonstrate the functionality of the modified loss function given in (3.2), a
large query of size 200 is used, instead of performing multiple small queries.
Fig. 6 shows how the original model extraction attack proposed by (Aïvodji,
Bolot, and Gambs 2020) suffers from the boundary shift issue, while the model
with the proposed loss function overcomes this problem. Fig. 10 illustrates
the instances misclassified by the two surrogate models.

Figure 10: Misclassifications w.r.t. to the target model, over
${\mathbb{D}}_{\text{uni}}$ and ${\mathbb{D}}_{\text{test}}$ as the reference
datasets for the 2-dimensional demonstration in Fig. 6. “Baseline” model
causes a large number of misclassifications w.r.t. the “CCA” model.

#### Comparing performance over four real-world dataset

We use a target model having 2 hidden layers with the architecture (20,10).
Two surrogate model architectures, one exactly similar to the target
architecture (model 0 - known architecture) and the other slightly different
(model 1 - unknown architecture), are tested. Model 1 has 3 hidden layers with
the architecture (20,10,5).

Fig. 11 illustrates the fidelities achieved by the two model architectures
described above. Fig. 12 shows the corresponding variances of the fidelity
values over 100 realizations. It can be observed that the variances diminish
as the query size grows, indicating more stable model extractions. Fig. 13
demonstrates the effect of the proposed loss function in mitigating the
decision boundary shift issue.

Figure 11: Fidelity for real-world datasets. Solid lines indicate “CCA”
models. Dashed lines indicate “Baseline” models. Colors correspond to the
model architecture, i.e., red: model 0, blue: model 1. Figure 12: Variance of
fidelity for real-world datasets. Solid lines indicate “CCA” models. Dashed
lines indicate “Baseline” models. Colors correspond to the model architecture,
i.e., red: model 0, blue: model 1. Figure 13: Histograms of probabilities
predicted by “Baseline” and “CCA” models under the “Unknown Architecture”
scenario (model 1) for the HELOC dataset. Note how the “Baseline” model
provides predictions higher than 0.5 for a comparatively larger number of
instances with $\left\lfloor{m(\boldsymbol{x})}\right\rceil=0$ due to the
boundary shift issue. The clamping effect of the novel loss function is
evident in the “CCA” model’s histogram, where the decision boundary being held
closer to the counterfactuals is causing the two prominent modes in the
favorable region. The mode closer to 0.5 is due to counterfactuals and the
mode closer to 1.0 is due to instances with
$\left\lfloor{m(\boldsymbol{x})}\right\rceil=1$.

#### Empirical and theoretical rates of convergence

Fig. 14 compares the rate of convergence of the empirical approximation error
i.e., $1-\mathbb{E}\left[{{\rm
Fid}_{m,{\mathbb{D}}_{\text{ref}}}(\tilde{M}_{n})}\right]$ for two of the
above experiments with the rate predicted by Theorem A.3. Notice how the
empirical error decays faster than $n^{-2/(d-1)}$.

Figure 14: A comparison of the query complexity derived in Theorem 3.2 with
the empirical query complexities obtained on the Adult Income and HELOC
datasets. The graphs are on a log-log scale. We observe that the analytical
query complexity is an upper bound for the empirical query complexities. All
the graphs are recentered with an additive constant for presentational
convenience. However, this does not affect the slope of the graph, which
corresponds to the complexity.

#### Studying effects of Lipschitz constants

For this experiment, we use a target model having 3 hidden layers with the
architecture (20, 10, 5) and a surrogate model having 2 hidden layers with the
architecture (20, 10). The surrogate model layers are $L_{2}$-regularized with
a fixed regularization coefficient of 0.001. We achieve different Lipschitz
constants for the target models by controlling their $L_{2}$-regularization
coefficients during the target model training step. Following (Gouk et al.
2021), we approximate the Lipschitz constant of target models by the product
of the spectral norms of the weight matrices.

Fig. 7 illustrates the dependence of the attack performance on the Lipschitz
constant of the target model. The results lead to the conclusion that target
models with larger Lipschitz constants are more difficult to extract. This
follows the insight provided by Theorem 3.4.

#### Studying different model architectures

We use the HELOC dataset for this experiment. The target model has a fixed
architecture of (20, 30, 10). Surrogate model architectures are given in Table
2, ranging from very complex to much simpler than the target model. The
ensemble size $S$ is selected to be 50.

Table 2: Surrogate model architectures Model | Hidden layers
---|---
Model 0 | (30, 20, 20, 10)
Model 1 | (20, 30, 10)
Model 2 | (20, 10)
Model 3 | (5, 5)

Results (see Fig. 15) indicate that the performance is weakly dependent on the
model architecture as long as the surrogate models are closer to the target
model in complexity, which is an observation made also by Aïvodji, Bolot, and
Gambs (2020). Results of additional experiments with varying target and
surrogate model architectures are presented in Table 3 and 4.

Figure 15: Effect of the surrogate model architecture on the attack
performance. Dashed lines correspond to “Baseline” models and solid lines
represent the “CCA” models. See Table 2 for the model specifications. The
attack performance is weakly dependent on the surrogate model architecture as
long as it is closer to the complexity of the target model. Table 3: Fidelity
over ${\mathbb{D}}_{\text{test}}$ and ${\mathbb{D}}_{\text{uni}}$ for datasets
DCCC and HELOC Dataset: DCCC - Fidelity over ${\mathbb{D}}_{\text{test}}$
---
Target archi. $\rightarrow$ | (20,10) | (20,10,5) | (20,20,10,5)
100 queries | 200 queries | 100 queries | 200 queries | 100 queries | 200 queries
Surrogate archi. $\downarrow$ | Base. | CCA | Base. | CCA | Base. | CCA | Base. | CCA | Base. | CCA | Base. | CCA
(20,10) | 0.96 | 0.98 | 0.97 | 0.99 | 0.96 | 0.99 | 0.97 | 0.99 | 0.91 | 0.97 | 0.92 | 0.98
(20,10,5) | 0.96 | 0.98 | 0.97 | 0.99 | 0.94 | 0.97 | 0.96 | 0.98 | 0.91 | 0.97 | 0.92 | 0.97
(20,20,10,5) | 0.93 | 0.97 | 0.94 | 0.98 | 0.92 | 0.97 | 0.93 | 0.97 | 0.88 | 0.94 | 0.92 | 0.96
Dataset: DCCC - Fidelity over ${\mathbb{D}}_{\text{uni}}$
Target archi. $\rightarrow$ | (20,10) | (20,10,5) | (20,20,10,5)
100 queries | 200 queries | 100 queries | 200 queries | 100 queries | 200 queries
Surrogate archi. $\downarrow$ | Base. | CCA | Base. | CCA | Base. | CCA | Base. | CCA | Base. | CCA | Base. | CCA
(20,10) | 0.95 | 0.96 | 0.96 | 0.97 | 0.97 | 0.97 | 0.97 | 0.98 | 0.98 | 0.98 | 0.98 | 0.98
(20,10,5) | 0.94 | 0.96 | 0.95 | 0.96 | 0.95 | 0.94 | 0.94 | 0.96 | 0.97 | 0.98 | 0.98 | 0.98
(20,20,10,5) | 0.92 | 0.93 | 0.95 | 0.94 | 0.96 | 0.94 | 0.95 | 0.96 | 0.94 | 0.92 | 0.96 | 0.94
Dataset: HELOC - Fidelity over ${\mathbb{D}}_{\text{test}}$
Target archi. $\rightarrow$ | (20,10) | (20,10,5) | (20,20,10,5)
100 queries | 200 queries | 100 queries | 200 queries | 100 queries | 200 queries
Surrogate archi. $\downarrow$ | Base. | CCA | Base. | CCA | Base. | CCA | Base. | CCA | Base. | CCA | Base. | CCA
(20,10) | 0.90 | 0.94 | 0.91 | 0.95 | 0.90 | 0.94 | 0.92 | 0.95 | 0.98 | 0.99 | 0.98 | 0.99
(20,10,5) | 0.88 | 0.92 | 0.92 | 0.95 | 0.89 | 0.92 | 0.92 | 0.95 | 0.98 | 0.98 | 0.98 | 0.99
(20,20,10,5) | 0.87 | 0.93 | 0.91 | 0.93 | 0.87 | 0.89 | 0.91 | 0.94 | 0.98 | 0.98 | 0.98 | 0.98
Dataset: HELOC - Fidelity over ${\mathbb{D}}_{\text{uni}}$
Target archi. $\rightarrow$ | (20,10) | (20,10,5) | (20,20,10,5)
100 queries | 200 queries | 100 queries | 200 queries | 100 queries | 200 queries
Surrogate archi. $\downarrow$ | Base. | CCA | Base. | CCA | Base. | CCA | Base. | CCA | Base. | CCA | Base. | CCA
(20,10) | 0.92 | 0.92 | 0.94 | 0.95 | 0.91 | 0.91 | 0.94 | 0.95 | 0.98 | 0.98 | 0.99 | 0.99
(20,10,5) | 0.91 | 0.90 | 0.94 | 0.93 | 0.91 | 0.89 | 0.93 | 0.94 | 0.97 | 0.97 | 0.98 | 0.99
(20,20,10,5) | 0.91 | 0.91 | 0.93 | 0.94 | 0.91 | 0.87 | 0.93 | 0.92 | 0.97 | 0.97 | 0.98 | 0.98
Table 4: Fidelity over ${\mathbb{D}}_{\text{test}}$ and
${\mathbb{D}}_{\text{uni}}$ for datasets Adult Income and COMPAS Dataset:
Adult Income - Fidelity over ${\mathbb{D}}_{\text{test}}$
---
Target archi. $\rightarrow$ | (20,10) | (20,10,5) | (20,20,10,5)
100 queries | 200 queries | 100 queries | 200 queries | 100 queries | 200 queries
Surrogate archi. $\downarrow$ | Base. | CCA | Base. | CCA | Base. | CCA | Base. | CCA | Base. | CCA | Base. | CCA
(20,10) | 0.88 | 0.89 | 0.92 | 0.93 | 0.82 | 0.84 | 0.91 | 0.93 | 0.94 | 0.95 | 0.95 | 0.96
(20,10,5) | 0.87 | 0.88 | 0.91 | 0.93 | 0.79 | 0.82 | 0.90 | 0.92 | 0.93 | 0.94 | 0.95 | 0.96
(20,20,10,5) | 0.85 | 0.86 | 0.91 | 0.91 | 0.79 | 0.81 | 0.89 | 0.92 | 0.93 | 0.92 | 0.95 | 0.95
Dataset: Adult Income - Fidelity over ${\mathbb{D}}_{\text{uni}}$
Target archi. $\rightarrow$ | (20,10) | (20,10,5) | (20,20,10,5)
100 queries | 200 queries | 100 queries | 200 queries | 100 queries | 200 queries
Surrogate archi. $\downarrow$ | Base. | CCA | Base. | CCA | Base. | CCA | Base. | CCA | Base. | CCA | Base. | CCA
(20,10) | 0.71 | 0.81 | 0.75 | 0.87 | 0.78 | 0.84 | 0.79 | 0.87 | 0.84 | 0.88 | 0.85 | 0.91
(20,10,5) | 0.71 | 0.78 | 0.74 | 0.83 | 0.77 | 0.82 | 0.78 | 0.85 | 0.82 | 0.88 | 0.84 | 0.90
(20,20,10,5) | 0.71 | 0.75 | 0.74 | 0.81 | 0.77 | 0.81 | 0.78 | 0.84 | 0.82 | 0.86 | 0.84 | 0.90
Dataset: COMPAS - Fidelity over ${\mathbb{D}}_{\text{test}}$
Target archi. $\rightarrow$ | (20,10) | (20,10,5) | (20,20,10,5)
100 queries | 200 queries | 100 queries | 200 queries | 100 queries | 200 queries
Surrogate archi. $\downarrow$ | Base. | CCA | Base. | CCA | Base. | CCA | Base. | CCA | Base. | CCA | Base. | CCA
(20,10) | 0.93 | 0.96 | 0.94 | 0.97 | 0.92 | 0.94 | 0.94 | 0.96 | 0.94 | 0.96 | 0.95 | 0.97
(20,10,5) | 0.92 | 0.95 | 0.94 | 0.97 | 0.92 | 0.93 | 0.95 | 0.95 | 0.94 | 0.96 | 0.95 | 0.97
(20,20,10,5) | 0.92 | 0.95 | 0.92 | 0.97 | 0.84 | 0.91 | 0.89 | 0.94 | 0.92 | 0.94 | 0.94 | 0.96
Dataset: COMPAS - Fidelity over ${\mathbb{D}}_{\text{uni}}$
Target archi. $\rightarrow$ | (20,10) | (20,10,5) | (20,20,10,5)
100 queries | 200 queries | 100 queries | 200 queries | 100 queries | 200 queries
Surrogate archi. $\downarrow$ | Base. | CCA | Base. | CCA | Base. | CCA | Base. | CCA | Base. | CCA | Base. | CCA
(20,10) | 0.94 | 0.95 | 0.94 | 0.96 | 0.95 | 0.95 | 0.95 | 0.96 | 0.96 | 0.95 | 0.96 | 0.96
(20,10,5) | 0.93 | 0.95 | 0.94 | 0.95 | 0.94 | 0.92 | 0.95 | 0.92 | 0.95 | 0.96 | 0.96 | 0.96
(20,20,10,5) | 0.93 | 0.94 | 0.94 | 0.95 | 0.94 | 0.85 | 0.94 | 0.90 | 0.95 | 0.92 | 0.95 | 0.94

#### Studying alternate counterfactual generating method

Counterfactuals can be generated such that they satisfy additional desirable
properties such as actionability, sparsity and closeness to the data manifold,
other than the proximity to the original instance. In this experiment, we
observe how counterfactuals with above properties affect the attack
performance. DCCC is used as the dataset. Target model has the architecture
(20, 30, 10) and the architecture of the surrogate model is (10, 20).

To generate actionable counterfactuals, we use Diverse Counterfactual
Explanations (DiCE)by Mothilal, Sharma, and Tan (2020) with features “SEX”,
“MARRIAGE”, and “AGE” kept unchanged. The diversity factor of DiCE generator
is set to 1 in order to obtain only a single counterfactual for each query.
Sparse counterfactuals are obtained by the same MCCC generator used in other
experiments, but now with $L_{1}$ norm as the cost function
$c(\boldsymbol{x},\boldsymbol{w})$. Counterfactuals from the data manifold
(i.e., realistic counterfactuals, denoted by 1-NN) are generated using a
1-Nearest-Neighbour algorithm. Table 5 summarizes the performance of the
attack.

When the counterfactuals lie further away from the decision boundary, the
advantage of the proposed attack w.r.t. the baseline diminishes. In order to
observe this effect, we carry-out the attacks using counterfactuals with two
different levels of sparsity. It can be observed that when the sparsity
increases, the counterfactuals tend to lie further away from the decision
boundary (see Fig. 16). Accordingly, the performance gap between the CCA and
the baseline attacks diminishes, as seen in Fig. 17.

Figure 16: Histogram of target model predictions $m(\boldsymbol{x})$ for instances with $\lfloor m(\boldsymbol{x})\rceil=0,1$ and counterfactuals, when different levels of sparsity is used with DiCE. Higher the parameter ’posthoc_sparsity_param’, more sparse the counterfactuals are. Note how the predictions on counterfactuals are concentrated away from the decision boundary when the sparsity is high. Dataset used is DCCC. Figure 17: Attack performance on DCCC dataset when different levels of sparsity in DiCE is used. Higher the parameter ’posthoc_sparsity_param’, more sparse the counterfactuals are. Table 5: Fidelity achieved with different counterfactual generating methods on DCCC dataset. Target model has hidden layers with neurons (20, 30, 10). Surrogate model architecture is (10, 20). | Fidelity over ${\mathbb{D}}_{\text{test}}$ | Fidelity over ${\mathbb{D}}_{\text{uni}}$
---|---|---
CF method | 100 queries | 200 queries | 100 queries | 200 queries
| Base. | CCA | Base. | CCA | Base. | CCA | Base. | CCA
MCCF L2-norm | 0.98 | 0.99 | 0.98 | 0.99 | 0.95 | 0.96 | 0.95 | 0.97
MCCF L1-norm | 0.79 | 0.95 | 0.85 | 0.97 | 0.89 | 0.92 | 0.93 | 0.94
DiCE Actionable | 0.98 | 0.98 | 0.98 | 0.98 | 0.92 | 0.94 | 0.91 | 0.94
1-NN | 0.98 | 0.99 | 0.99 | 0.99 | 0.94 | 0.95 | 0.95 | 0.96

#### Studying effect of unbalanced ${\mathbb{D}}_{\text{attack}}$

In all the other experiments, the attack dataset
${\mathbb{D}}_{\text{attack}}$ used by the adversary is sampled from a class-
wise balanced dataset. In this experiment we explore the effect of querying
using an unbalanced ${\mathbb{D}}_{\text{attack}}$. Model architectures used
are (20, 10) for the target model and surrogate model 0, and (20, 10, 5) for
surrogate model 1.

Two versions of the Adult Income dataset were used in the experiment. The
first version, used in Fig. 18(a) contains 24720 and 7841 examples from
classes $y=0$ and $y=1$, respectively. The second version corresponding to
Fig. 18(b) contains 2472 and 7841 examples from classes $y=0$ and $y=1$,
respectively. The proposed attack surpasses the baseline attack in both
scenarios.

(a)

(b)

Figure 18: Results corresponding to the Adult Income dataset with queries
sampled from biased versions of the dataset (i.e., a biased
${\mathbb{D}}_{\text{attack}})$. The version used in Fig. 18(a) contains 24720
and 7841 examples from classes $y=0$ and $y=1$, respectively. The version
corresponding to Fig. 18(b) contains 2472 and 7841 examples from classes $y=0$
and $y=1$, respectively.

#### Studying other machine learning models

We explore the effectiveness of the proposed attack when the target model is
no longer a neural network classifier. The surrogate models are still neural
networks with the architectures (20, 10) for model 0 and (20, 10, 5) for model
1. A random forest classifier with 100 estimators and a linear regression
classifier, trained on Adult Income dataset are used as the targets. Ensemble
size $S$ used is 20. Results are shown in Fig. 19, where the proposed attack
performs better or similar to the baseline attack.

Figure 19: Performance of the attack when the target model is not a neural
network. Surrogates M0 and M1 are neural networks with the architectures
(20,10) and (20,10,5) respectively. Baseline T is a surrogate model from the
same class as the target model.

#### Studying alternate loss functions

We explore using binary cross-entropy loss function directly with labels 0, 1
and 0.5 in place of the proposed loss. Precisely, the surrogate loss is now
defined as

$L(\tilde{m},y)=-y(\boldsymbol{x})\log\left(\tilde{m}(\boldsymbol{x})\right)-(1-y(\boldsymbol{x}))\log\left(1-\tilde{m}(\boldsymbol{x})\right)$
(20)

which is symmetric around 0.5 for $y(\boldsymbol{x})=0.5$. Two surrogate
models are observed, with architectures (20, 10) for model 0 and (20, 10, 5)
for model 1. The target model’s architecture is similar to that of model 0.
The ensemble size is $S=20$.

The results (in Fig. 20) indicate that the binary cross-entropy loss performs
worse than the proposed loss. The reason might be the following: As the binary
cross-entropy loss is symmetric around 0.5 for counterfactuals, it penalizes
the counterfactuals that are farther inside the favorable region. This in turn
pulls the surrogate decision boundary towards the favorable region more than
necessary, causing a decision boundary shift.

Figure 20: Performance of binary cross-entropy loss with labels 0, 0.5 and 1.
Dashed lines corresponding to binary cross entropy (BCE) loss and solid lines
depict the performance of the CCA loss.

###  B.3 Experiments for verifying Theorem 3.2

This experiment includes approximating a spherical decision boundary in the
first quadrant of a $d-$dimensional space. The decision boundary is a portion
of a sphere with radius 1 and the origin at $(1,1,\dots,1)$. The input space
is assumed to be normalized, and hence, restricted to the unit hypercube. See
Section 3.1 for a description of the attack strategy. Fig. 21 presents a
visualization of the experiment in the case where the dimensionality $d=2$.
Fig. 8 presents a comparison of theoretical and empirical query complexities
for higher dimensions. Experiments agree with the theoretical upper-bound.

Figure 21: Synthetic attack for verifying Theorem 3.2 in the 2-dimensional
case. Red dots represent queries and blue dots are the corresponding closest
counterfactuals. Dashed lines indicate the boundary of the polytope
approximation.