# Exploring Connections Between Active Learning and Model Extraction
∗1
Varun Chandrasekaran, Kamalika Chaudhuri³, Irene Giacomelli²,
Somesh Jha¹, and Songbai Yan³
1 University of Wisconsin-Madison
2 Protocol Labs
3 University of California San Diego
1
University of Wisconsin-Madison
2
Protocol Labs
3
University of California San Diego
November 21, 2019
## Abstract
Machine learning is being increasingly used by individuals, research
institutions, and corporations. This has resulted in the surge of Machine
Learning-as-a-Service (MLaaS) - cloud services that provide (a) tools and
resources to learn the model, and (b) a user-friendly query interface to
access the model. However, such MLaaS systems raise privacy concerns
such as *model extraction*. In model extraction attacks, adversaries maliciously exploit the query interface to *steal* the model. More precisely, in
a model extraction attack, a good approximation of a sensitive or proprietary model held by the server is extracted (*i.e.* learned) by a dishonest
user who interacts with the server only via the query interface. This
attack was introduced by Tramer *et al.* at the 2016 USENIX Security
Symposium, where practical attacks for various models were shown. We
believe that better understanding the ecacy of model extraction attacks
is paramount to designing secure MLaaS systems. To that end, we take
the rst step by (a) formalizing model extraction and discussing possible
defense strategies, and (b) drawing parallels between model extraction
arXiv:1811.02054v6 [cs.LG] 20 Nov 2019and established area of *active learning*. In particular, we show that recent
advancements in the active learning domain can be used to implement
powerful model extraction attacks and investigate possible defense strategies.
## 1Introduction
Advancements in various facets of machine learning has made it an integral
part of our daily life. However, most real-world machine learning tasks are resource intensive. To that end, several cloud providers, such as Amazon, Google,
∗Corresponding author: chandrasekaran@cs.wisc.edu
---
Microsoft, and BigML oset the storage and computational requirements by
providing *Machine Learning-as-a-Service (MLaaS)*. A MLaaS server oers support for both the training phase, and a query interface for accessing the trained
model. The trained model is then queried by other users on chosen instances
(refer Fig.1). Often, this is implemented in a pay-per-query regime *i.e.* the
server, or the model owner via the server, charges the the users for the queries
to the model. Pricing for popular MLaaS APIs is given in Table1.
Current research is focused at improving the performance of training algorithms and of the query interface, while little emphasis is placed on the related
security aspects. For example, in many real-world applications, the trained
models are privacy-sensitive - a model can (a) leak sensitive information about
training data [5] during/after training, and (b) can itself have commercial value
or can be used in security applications that assume its secrecy (*e.g.*, spam lters,
fraud detection etc. [36,47,64]). To keep the models private, there has been
a surge in the practice of *oracle access*, or black-box access. Here, the trained
model is made available for prediction but is kept secret. MLaaS systems use
oracle access to balance the trade-o between privacy and usability.
| Models | Google | Amazon | Microsoft |
| --- | --- | --- | --- |
| DNNs | Confidence Score | X | Confidence Score |
| Regression | Confidence Score | Confidence Score | Confidence Score |
| Decision trees | Leaf Node | X | Leaf Node |
| Random forests | Leaf Node | X | Leaf Node |
| Binary & n-ary classification | Confidence Score | Confidence Score | Confidence Score |
| Batch | $0.093^{*}$ | $0.1 | $0.5 |
| Online | $0.056^{*}$ | $0.0001 | $0.0005 |
Table 1: Pricing, and auxiliary information shared. Googles pricing model is per node per
hour. Leaf node denotes the exact leaf (and not an internal node) where the computation
halts, and 7indicates the absence of support for the associated model.
Despite providing oracle access, a broad suite of attacks continue to target existing MLaaS systems [14]. For example, membership inference attacks
attempt to determine if a given data-point is included in the model’s training
dataset only by interacting with the MLaaS interface (*e.g.* [63]). In this work, we
focus on *model extraction attacks*, where an adversary makes use of the MLaaS
query interface in order to *steal* the proprietary model (*i.e.* learn the model or a
good approximation of it). In an interesting paper, Tramer *et al.* [67], show that
many commonly used MLaaS interfaces can be exploited using only few queries
to recover a model’s secret parameters. Even though model extraction attacks are empirically proven to be feasible, their work consider interfaces that reveal
auxiliary information, such as condence values together with the prediction
output. Additionally, their work does not formalize model extraction. We believe that such formalization is paramount for designing secure MLaaS that are
resilient to aforementioned threats. In this paper, we take the rst step in this
direction. The main contributions of the paper appear in boldfaced captions.
Model Extraction Active Learning. The key observation guiding our
formalization is that the process of model extraction is very similar to *active*
*learning* [61], a special case of semi-supervised machine learning. An active
learner learns an approximation of a labeling function *f* through repetitive
interaction with an oracle, who is assumed to know *f*. These interactions
typically involve the learner sending an instance *x* to the oracle, and the oracle
returning the label *y* = *f* (*x*) to the learner. Since the learner can choose the
instances to be labeled, the number of data-points needed to learn the labeling
function is often much lower than in the normal supervised case. Similarly, in
model extraction, the adversary uses a strategy to query a MLaaS server with
the following goals: (a) to successfully steal (*i.e.* learn) the model (*i.e.* labeling
function) known by the server (*i.e.* oracle), in such a way as to (b) minimize the
number of queries made to the MLaaS server, as each query costs the adversary
a xed dollar value.
$$
y=f^{*}(x)
$$
While the overall process of active learning mirrors the general description of
model extraction, the entire spectrum of active learning can not be used to study
model extraction. Indeed, some scenarios (eg, PAC active learning) assume that
the query instances are sampled from the actual input distribution. However,
an attacker is not restricted to such a condition and can query any instance. For
this reason, we believe that the query synthesis framework of active learning,
where the learner has the power to generate arbitrary query instances best
replicates the capabilities of the adversary in the model extraction framework.
Additionally, the query synthesis scenario ensures that we make no assumptions
about the adversary’s prior knowledge.
Powerful attacks with no auxiliary information. By casting model extraction as query synthesis active learning, we are able to draw concrete similarities
between the two. Consequently, we are able to use algorithms and techniques
from the active learning community to perform powerful model extraction attacks, and investigate possible defense strategies. In particular, we show that:
query synthesis active learning algorithms can be used to perform model extraction on both linear and non-linear classiers with *no auxiliary information*.
Moreover, our evaluation shows that our attacks are better than the classic
attacks, such as by Lowd and Meek [47], which have been widely used in the
security community. Our approach based on active selection also improves upon
existing approaches to extract kernel SVMs (see Section6).
No \free lunch" for defense. Simple defense strategies such as changing
the prediction output with constant and small probability are not eective.
However, defense strategies that change the prediction output depending on the
instances that are being queried, such as the work of Alabdulmohsin *et al.* [2], are
more robust to extraction attacks implemented using existing query synthesis
---
Figure 1: Model extraction can be envisioned as active learning. A data owner, with the
help of a MLaaS server, trains a model *f* on its data. The proprietary model is stored by
the server, which also answers to queries from users (*i.e.*, *y*i= *f* (*x*i)). In a model extraction
attack, a dishonest user tries to exploit this interface to \steal" *f* in the same way as a learner
uses answer from a machine-learning oracle in order to learn *f*.
$$
f^{*}
$$
$$
(i.e.,\,y_{i}=f^{*}(x_{i}))
$$
$$
f^{*}
$$
$$
f^{*}
$$
active learning algorithms. However, in Algorithm1of Section6, we show that
this defense is not secure against traditional passive learning algorithms. This
suggests that there is \no free lunch" { accuracy might have to be sacriced
to prevent model extraction. An in-depth investigation of such a result will be
interesting avenue for future work.
*Paper structure.* We begin with a brief comparison between passive machine
learning and active learning in Section2. This allows us to introduce the notation used in this paper, and review the state-of-the-art for active learning.
Section3focuses on the formalization of model extraction attacks, casting it
into the query synthesis active learning framework. Section4discusses our algorithms used to extract non-linear classiers (*i.e.* kernel SVMs, decision trees,
and random forests). Section5discusses possible defenses strategies. Section6.1
reports our experimental ndings and demonstrates that query synthesis active
learning can be used to successfully perform model extraction, and evaluates
dierent defense strategies. Specically, we observe that $0.09 worth Amazon
queries are needed to extract most halfspaces when the MLaaS server does not
deploy any defense, and $3.65 worth of queries are required to learn a halfspace
when it uses data-independent randomization. Furthermore, our experiments
in Section6.2show modifying adaptive retraining proposed by Tramer *et al.* results in ecienct extraction attacks for non-linear models; we obtain 5-224
improvement for kernel SVMs, and comparable extraction eciency for discrete
models such as decision trees with *no auxiliary information*. Finally, we discuss
some open issues in Section7, which provides avenue for future work. Related
work is discussed in Section8, and we end the paper with some concluding
remarks.
## 2Machine Learning
In this section, we give a brief overview of machine learning, and terminology
we use throughout the paper. In particular, we summarize the passive learning
framework in subsection2.1, and focus on active learning algorithms in subsection2.2. A review of the state-of-the-art of active learning algorithms is
needed to explicitly link model extraction to active learning and is presented in
Section3.
---
## 2.1Passive learning
In the standard, passive machine learning setting, the learner has access to a
large labeled dataset and uses it in its entirety to learn a predictive model from
a given class. Let X be an instance space, and Y be a set of labels. For example,
in object recognition, X can be the space of all images, and Y can be a set of
objects that we wish to detect in these images. We refer to a pair (*x;y*) *2* X Y
as a *data-point or labeled instance* (*x* is the instance, *y* is the label). Finally,
there is a class of functions *F* from X to Y called the *hypothesis space* that is
known in advance. The learner’s goal is to nd a function *f*^*2F* that is a good
predictor for the label *y* given the instance *x*, with (*x;y*) *2* X Y. To measure
how well *f*^ predicts the labels, a loss function *‘* is used. Given a data-point
*z* = (*x;y*) *2* X Y, *‘*(*f;z* ^) measures the \dierence" between *f*^(*x*) and the true
label *y*. When the label domain Y is nite (classication problem), the 0-1 loss
function is frequently used:
(
$$
(x,y)\in\mathbf{X}\times\mathbf{Y}
$$
$$
{\hat{f}}\in{\mathcal{F}}
$$
$$
\hat{f}
$$
$$
(x,y)\in\mathbf{X}\times\mathbf{Y}
$$
$$
\ =(left\boldsymbol{x},\boldsymbol{y})\in\mathbb{X}\times\mathbb{Y},\ell(\dot{f},\boldsymbol{z})
$$
$$
\ell({\hat{f}},z)=\begin{cases}{0,}&{{\mathrm{~i f~}}{\hat{f}}(x)=y}\\ {1,}&{{\mathrm{~o t h e r w i s e~}}}\end{cases}
$$
If the label domain Y is continuous, one can use the square loss: *‘*(*f;z* ^) =
^( 2
(*f x*) *y*).
$$
\ell(\hat{f},z)=,\,
$$
$$
(\hat{f}(x)-y)^{2}
$$
In the passive setting, the PAC (*probably approximately correct*) learning [68]
framework is predominantly used. Here, we assume that there is an underlying
distribution *D* on X Y that describes the data; the learner has no direct
knowledge of *D* but has access to a set of training data *D* drawn from it. The
main goal in passive PAC learning is to use the labeled instances from *D* to
produce a hypothesis *f*^ such that its expected loss with respect to the probability
distribution *D* is low. This is often measured through the *generalization error*
of the hypothesis *f*^, dened by
$$
\hat{f}_{\rangle}
$$
$$
\mathrm{E r r}_{\mathcal{D}}(\hat{f})=\mathbb{E}_{z\sim\mathcal{D}}[\ell(\hat{f},z)]
$$
(1)
More precisely, we have the following denition.
Denition 1 (PAC passive learning [68]). An algorithm *A* is a PAC passive
learning algorithm for the hypothesis class *F* if the following holds for any *D* on
X Y and any *"; 2* (0*;*1): If *A* is given *s*A(*";*) i.i.d. data-points generated
by *D*, then *A* outputs *f*^ *2 F* such that Err (*f*^) min Err (*f*) + *"* with
D f 2F D
probability at least 1. We refer to *s*A(*";*) as the *sample complexity* of
algorithm *A*.
$$
\mathbf{X}\times\mathbf{Y}
$$
$$
\varepsilon,\delta\in(0,1)
$$
$$
s_{A}(\varepsilon,\delta)
$$
$$
\ \hat{f}\in\ \mathcal{F}
$$
$$
\textstyle\ (\hat{f})\leq\operatorname*{m i n}_{f\in\mathcal{F}}\operatorname{E r r}_{\mathcal{D}}(f)+\varepsilon
$$
$$
1-\delta
$$
$$
s_{A}(\varepsilon,\delta)
$$
*Remark* 1 (Realizability assumption)*.* In the general case, the labels are given
together with the instances, and the factor minf 2FErrD(*f*) depends on the hypothesis class. Machine learning literature refers to this as *agnostic learning*
or the non-separable case of PAC learning. However, in some applications, the
labels themselves can be described using a labeling function *f 2 F*. In this
case (known as *realizable learning*), minf 2FErrD(*f*) = 0 and the distribution *D*
$$
\ {}_{f\in\mathcal{F}}\operatorname{E r r}_{\mathcal{D}}(f)
$$
$$
f^{*}\in\mathcal{F}
$$
$$
{_{{f\in\mathcal{F}}}}\operatorname{E r r}_{\mathcal{D}}(f)=0
$$ can be described by its marginal over X. A PAC passive learning algorithm *A*
in the realizable case takes *s*A(*";*) i.i.d. instances generated by *D* and the corresponding labels generated using *f*, and outputs *f*^*2F* such that Err (*f*^) *"*
D
with probability at least 1.
$$
s_{A}(\varepsilon,\delta)
$$
$$
f^{*}
$$
$$
{\hat{f}}\in{\mathcal{F}}
$$
$$
\operatorname{E r r}_{\mathcal{D}}(\hat{f})\leq\varepsilon
$$
## 2.2Active learning
In the passive setting, learning an accurate model (*i.e.* learning *f*^ with low generalization error) requires a large number of data-points. Thus, the labeling
eort required to produce an accurate predictive model may be prohibitive. In
other words, the sample complexity of many learning algorithms grows rapidly
as *" !* 0 (refer Example1). This has spurred interest in learning algorithms
that can operate on a smaller set of labeled instances, leading to the emergence
of *active learning*. In active learning, the learning algorithm is allowed to select
a subset of unlabeled instances, query their corresponding labels from an annotator (a.k.a oracle) and then use it to construct or update a model. How the
algorithm chooses the instances varies widely. However, the common underlying
idea is that by actively choosing the data-points used for training, the learning
algorithm can drastically reduce sample complexity.
$$
\hat{f}
$$
$$
\varepsilon\rightarrow0
$$
Formally, an active learning algorithm is an interactive process between two
parties - the oracle *O* and the learner *L*. The only interaction allowed is through
*queries*-*L* chooses *x 2* X and sends it to *O*, who responds with *y 2* Y (*i.e.*, the
oracle returns the label for the chosen unlabeled instance). This value of (*x;y*)
is then used by *L* to infer some information about the labeling procedure, and
to choose the next instance to query. Over many such interactions, *L* outputs
*f*^ as a predictor for labels. We can use the generalization error (1) to evaluate
the accuracy of the output *f*^. However, depending on the query strategy chosen
by *L*, other types of error can be used.
$$
\mathcal{L},
$$
$$
\mathcal{L}
$$
$$
y\in\mathbf{Y}\;(i.e.)
$$
$$
x\in\mathbb{X}
$$
$$
{\mathcal O},
$$
$$
(x,y)
$$
$$
\mathcal{L}
$$
$$
\mathcal{L}
$$
$$
\hat{f}
$$
$$
\hat{f}
$$
$$
{\mathcal{L}},
$$
There are two distinct scenarios for active learning: *PAC active learning*
and *Query Synthesis (QS) active learning*. In literature, QS active learning
is also known as *Membership Query Learning*, and we will use the two terms
synonymously.
## 2.2.1PAC active learning
This scenario was introduced by Dasgupta in 2005 [22] in the realizable context
and then subsequently developed in following works (*e.g.*, [4,21,33]). In this
scenario, the instances are sampled according to the marginal of *D* over X, and
the learner, after seeing them, decides whether to query for their labels or not.
Since the data-points seen by *L* come from the actual underlying distribution
*D*, the accuracy of the output hypothesis *f*^ is measured using the generalization
error (1), as in the classic (*i.e.*, passive) PAC learning.
$$
\hat{f}
$$
There are two options to consider for sampling data-points. In *stream-based*
*sampling* (also called *selective sampling*) , the instances are sampled one at
a time, and the learner decides whether to query for the label or not on a
per-instance basis. *Pool-based sampling* assumes that all of the instances are
collected in a static pool *S* X and then the learner chooses specic instances
in *S* and queries for their labels. Typically, instances are chosen by *L* in a
$$
S\subseteq\mathbf{X}
$$ greedy fashion using a metric to evaluate all instances in the pool. This is not
possible in stream-based sampling, where *L* goes through the data sequentially,
and has to therefore make decisions to query individually. Pool-based sampling
is extensively studied since it has applications in many real-world problems, such
as text classication, information extraction, image classication and retrieval,
etc. [48]. Stream-based sampling represents scenarios where obtaining unlabeled
data-points is easy and cheap, but obtaining their labels is expensive (*e.g.*,
stream of data is collected by a sensor, but the labeling needs to be performed
by an expert).
Before describing query synthesis active learning, we wish to highlight the
advantage of PAC active learning over passive PAC learning (*i.e.* the reduced
sample complexity) for some hypothesis class through Example1. Recall that
this advantage comes from the fact that an active learner is allowed to adaptively
choose the data from which it learns, while a passive learning algorithm learns
from a static set of data-points.
*Example* 1 (PAC learning for halfspaces)*.* Let *F*d;HSbe the hypothesis class
of *d-dimensional halfspaces*, used for binary classication. A function in *f*w*2*
d
*F*d;HSis described by a normal vector *w 2* R (*i.e.*, *jjwjj₂* = 1) and is dened
by
*d*
f (x) = sign(hw;xi) for any x 2 R
$$
\mathcal{F}_{d,H S}
$$
$$
f{_{w}}\in
$$
$$
\mathcal{F}_{d,H S}
$$
$$
\dot{w\in\mathbb{R}^{d}};\;(i.e.,\;||w||_{2}=1)
$$
$$
f_{w}(x)=\ \mathrm{s i g n}(\langle w,x\rangle)\ \mathrm{f o r~a n y}\ x\ in\ \mathbb{R}^{d}
$$
d
where given two vectors *a;b 2* R, then their product is dened as *ha;bi* =
Pd
i=1*a*i*b*i. Moreover, if *x 2* R, then sign(*x*) = 1 if *x* 0 and sign(*x*) = 1
d 1
otherwise. A classic result in passive PAC learning states that *O*( log() +
" "
1 1
log()) data-points are needed to learn *f*w[68]. On the other hand, several
"
1
works propose active learning algorithms for *F*d;HSwith sample complexity
~(1
*O* dlog()) (under certain distributional assumptions). For example, if the
"
underlying distribution is log-concave, there exists an active learning algorithm
~(1
with sample complexity *O d*log()) [9,10,76]. This general reduction in the
"
sample complexity for *F*d;HSis easy to infer when *d* = 1. In this case, the datapoints lie on the real line and their labels are a sequence of 1’s followed by a
sequence of +1’s. The goal is to discover a point *w* where the change from 1 to
~(1 2
+1 happens. PAC learning theory states that this can be achieve*d* with *O*)
"
points i.i.d. sampled from *D*. On the other hand, an active learning algorithm
1
that uses a simple binary search can achieve the same task with *O*(log())
"
queries [22] (refer Figure2).
$$
a,b\in\mathbb{R}^{d}
$$
$$
\langle a,b\rangle\,=
$$
$$
\textstyle\sum_{i=1}^{d}a_{i}b_{i}
$$
$$
x\,0\,\geq0,
$$
$$
\operatorname{i g n}(x)\,=\,1
$$
$$
x\,\in\,{\mathbb R R}
$$
$$
\mathrm{s i g n}(x)\,=\,-1
$$
$$
O\bigl(\textstyle{\frac{d}{\varepsilon}}\log\bigl(\textstyle{\frac{1}{\varepsilon}}\bigr)\,+
$$
$$
\frac {1}{\varepsilon} \log \left(\frac {1}{\delta}\right)
$$
$$
f_{w}\ [68]
$$
$$
\mathrm{t y}^{1}
$$
$$
\mathcal{F}_{d,H S}
$$
$$
\tilde{O}(d\log\Big(\frac{1}{\varepsilon}\Big))
$$
$$
\tilde{O}(\dot{d}\log(\frac{1}{\varepsilon}))
$$
$$
\mathcal{F}_{d,H S}
$$
$$
d=1
$$
$$
\tilde{O}(\ {textstyle\frac{1}{\}}_{\varepsilon})^{2}}
$$
$$
O(\log{\textstyle{\bigl(}{\frac{1}{\varepsilon}}{\bigr)}})
$$
## 2.2.2Query Synthesis (QS) active learning
In this scenario, the learner can request labels for any instance in the input
space X, including points that the learner generates *de novo*, independent of the
distribution *D* (*e.g.*, *L* can ask for labels for those *x* that have zero-probability
of being sampled according to *D*). Query synthesis is reasonable for many
problems, but labeling such arbitrary instances can be awkward if the oracle is
a human annotator. Thus, this scenario better represents real-world applications
1The *O*~ notation ignores logarithmic factors and terms dependent on.
2 ~(d
More generally, *O*) points.
"
$$
\delta.
$$
$$
\tilde{O}(\frac{d}{\varepsilon})
$$
---
$$
f_{w}(x)=\begin{cases}{-1{\mathrm{~i f~}}\langle w,x\rangle<-1}\\ {+1{\mathrm{~o t h e r w i s e~}}}\end{cases}
$$
Figure 2: Halfspace classication in dimension 1.
where the oracle is automated (*e.g.*, results from synthetic experiments [39]).
Since the data-points are independent of the distribution, generalization error is
not an appropriate measure of accuracy of the hypothesis *f*^, and other types of
error are typically used. These new error formulations depend on the concrete
hypothesis class *F* considered. For example, if *F* is the class of boolean functions
n
from *f*0*;* 1*g* to *f*0*;* 1*g*, then the *uniform error* is used. Assume that the oracle
*O* knows *f 2 F* and uses it as labeling function (realizable case), then the
uniform error of the hypothesis *f*^ is dened as
$$
(e.g.
$$
$$
\hat{f},
$$
$$
\mathcal{F}
$$
$$
\{0,1\}^{n}
$$
$$
\{0,1\}
$$
$$
f^{*}\,\in\,\ \mathcal{F}
$$
$$
\hat{f}
$$
$$
\operatorname{E r r}_{u}(\hat{f})=\operatorname*{P r}_{x\sim\{0,1\}^{n}}[\hat{f}(x)\neq f^{*}(x)]
$$
n
where *x* is sampled uniformly at random from the instance space *f*0*;* 1*g*. Recent
work [3,17], for the class of halfspaces *F*d;HS(refer to Example1) use *geometric*
*error*. Assume that the true labeling function used by the oracle is *f*w, then
the geometric error of the hypothesis *f*w*2F*d;HSis dened as
$$
\{0,1\}^{n}
$$
$$
\mathcal{F}_{d,H S}
$$
$$
f_{w^{*}}
$$
$$
f_{w}\in\mathcal{F}_{d,H S}
$$
$$
\operatorname {E r r} _ {2} \left(f _ {w}\right) = \left| \left| w ^ {*} - w \right| \right| _ {2}
$$
where *jjjj₂* is the 2-norm.
$$
||\cdot||_{2}
$$
In both active learning scenarios (PAC and QS), the learner needs to evaluate
the \usefulness" of an unlabeled instance *x*, which can either be generated de
novo or sampled from the given distribution, in order to decide whether to
query the oracle for the corresponding label. In the state of the art, we can
nd many ways of formulating such *query strategies*. Most of existing literature
presents strategies where ecient search through the hypothesis space is the
goal (refer the survey by Settles [61]). Another point of consideration for an
active learner *L* is to decide when to stop. This is essential as active learning is
geared at improving accuracy while being sensitive to new data acquisition cost
(*i.e.*, reducing the query complexity). While one school of thought relies on the
*stopping criteria* based on the intrinsic measure of stability or self-condence
within the learner, another believes that it is based on economic or other external
factors (refer [61, Section 6.7]).
Given this large variety within active learning, we enhance the standard
denition of a learning algorithm and propose the denition of an active learning
system, which is geared towards model extraction. Our denition is informed
by the MLaaS APIs that we investigated (more details are present in Table1).
---
Denition 2 (Active learning system). Let *F* be a hypothesis class with instance space X and label space Y. An active learning system for *F* is given
by two entities, the learner *L* and the oracle *O*, interacting via membership
queries: *L* sends to *O* an instance *x 2* X; *O* answers with a label *y 2* Y. We
indicate via the notation *O*fthe realizable case where *O* uses a specic labeling
function *f 2F*, *i.e. y* = *f* (*x*). The behavior of *L* is described by the following
parameters:
$$
\mathcal{F}
$$
$$
\mathcal{F}
$$
$$
\mathcal\{O{}cdot
$$
$$
x\in\mathbf{X};\mathcal{O}
$$
$$
y\in\mathrm{Y}
$$
$$
{\mathcal{O}}_{f},
$$
$$
f^{*}\in\mathcal{F},\,i.e.\,y=\dot{f^{*}}(x)
$$
1. *Scenario*: this is the rule that describes the generation of the input for
the querying process (*i.e.* which instances *x 2* X can be queried). In the
PAC scenario, the instances are sampled from the underlying distribution
*D*. In the query synthesis (QS) scenario, the instances are generated by
the learner *L*;
$$
x\in\mathbb{X}
$$
$$
\mathcal {L};
$$
2. *Query strategy*: given a specic scenario, the query strategy is the algorithm that adaptively decides if the label for a given instance *x*iis queried
for, given that the queries *x₁;:::;x*i 1have been answered already. In the
query synthesis scenario, the query strategy also describes the procedure
for instance generation.
$$
x_{i}
$$
$$
x_{1},\ldots,x_{i-1}
$$
3. *Stopping criteria*: this is a set of considerations used by *L* to decide when
it must stop asking queries.
Any system (*L; O*) described as above is an active learning system for *F* if one
of the following holds:
$$
\mathcal{F}
$$
-*(PAC scenario)* For any *D* on X Y and any *"; 2* (0*;*1), if *L* is allowed
to interact with *O* using *q* (*";*) queries, then *L* outputs *f*^*2F* such that
L
Err (*f*^) min Err (*f*) + *"* with probability at least 1.
D f 2F D
$$
(P A C
$$
$$
\mathbf{X}\times\mathbf{Y}
$$
$$
\varepsilon,\delta\in(0,1)
$$
$$
q_{\mathcal{L}}(\varepsilon,\delta)
$$
$$
{\hat{f}}\in{\mathcal{F}}
$$
$$
\operatorname{E r r}_{\mathcal{D}}(\textstyle{\hat{f}})\leq\operatorname*{m i n}_{f\in\mathcal{F}}\operatorname{E r r}_{\mathcal{D}}(f)+\varepsilon
$$
$$
1-\delta
$$
-*(QS scenario)* Fix an error measure Err for the functions in *F*. For any
*f 2F*, if *L* is allowed to interact with *O*fusing *q*L(*";*) queries, then *L*
outputs *f*^*2F* such that Err(*f*^) *"* with probability at least 1.
$$
(Q S
$$
$$
\mathcal{F}.
$$
$$
f^{*}\in\mathcal{F}
$$
$$
{\mathcal{O}}_{f^{*}}
$$
$$
q_{\mathcal{L}}(\varepsilon,\delta)
$$
$$
\mathcal{L}
$$
$$
\hat{f}\in\mathcal{F}
$$
$$
\operatorname{E r r}({\hat{f}})\leq\varepsilon
$$
$$
1-\delta
$$
We refer to *q*L(*";*) as the *query complexity* of *L*.
$$
q_{\mathcal{L}}(\varepsilon,\delta)
$$
$$
\mathcal{L}
$$
As we will show in the following section (in particular, refer subsection3.2),
the query synthesis scenario is more appropriate in casting model extraction
attack as active learningwhen we make no assumptions about the adversary’s
prior knowledge.
Note that, other types queries have been studied in literature. This includes
the *equivalence query* [4]. Here the learner can verify if a hypothesis is correct
or not. We do not consider equivalence queries in our denition because we did
not see any of the MLaaS APIs support them.
## 3Model Extraction
In subsection3.1, we begin by formalizing the process of model extraction. We
then draw parallels between model extraction and active learning in subsection3.2. We proceed to provide insight about extracting non-linear models in
Section7(b).
---
## 3.1Model Extraction Denition
We begin by describing the operational ecosystem of model extraction attacks in
the context of MLaaS systems. An entity learns a private model *f* from a public
class *F*, and provides it to the MLaaS server. The server provides a client-facing
query interface for accessing the model for prediction. For example, in the case of
logistic regression, the MLaaS server knows a model represented by parameters
d
*a₀;a₁;;a*d. The client issues queries of the form *x* = (*x*[1]*;;x*[*d*]) *2* R,
a(x) 1
and the MLaaS server responds with 0 if (1 + *e*) 0*:* 5 and 1 otherwise,
Pd
with *a*(*x*) = *a₀* +i=1*a*i*x*[*i*].
$$
f^{*}
$$
$$
a_{0},a_{1},\cdots,a_{d}
$$
$$
\ =\big(x[1],\cdots,x[d]\big)\in\mathbb{R}^{d}
$$
$$
(1+e^{-a(x)})^{-1}\leq0.5
$$
$$
a(x)=a_{0}+\sum_{i=1}^{d}a_{i}x[i]
$$
Model extraction is the process where an adversary exploits this interface to
learn more about the proprietary model *f*. The adversary can be interested in
defrauding the description of the model *f* itself (*i.e.*, stealing the parameters
*a*ias in a reverse engineering attack), or in obtaining an approximation of the
model, say *f*^*2F*, that he can then use for free for the same task as the original
*f* was intended for. To capture the dierent goals of an adversary, we say that
the attack is successful if the extracted model is \close enough" to *f* according
to an *error function* on *F* that is context dependent. Since many existing
MLaaS providers operate in a pay-per-query regime, we use query complexity
as a measure of eciency of such model extraction attacks.
$$
a_{i}
$$
$$
\ hat\ f in mathcal F
$$
$$
f^{*}
$$
$$
\mathcal{F}
$$
$$
f^{*}
$$
Formally, consider the following experiment: an adversary *A*, who knows
the hypothesis class *F*, has oracle access to a proprietary model *f* from *F*.
This can be thought of as *A* interacting with a server *S* that safely stores *f*.
The interaction has several rounds. In each round, *A* chooses an instance *x*
and sends it to *S*. The latter responds with *f* (*x*). After a few rounds, *A*
outputs a function *f*^ that is the adversary’s candidate approximation of *f*; the
experiment considers *f*^ a good approximation if its error with respect to the
true function *f* held by the server is less then a xed threshold *"*. The error
function Err is dened a priori and xed for the extraction experiment on the
hypothesis class *F*.
$$
{\mathcal A},
$$
$$
f^{*}
$$
$$
{\mathcal{F}},
$$
$$
\mathcal{F}.
$$
$$
f^{*}
$$
$$
\mathcal{A}
$$
$$
f^{*}(x)
$$
$$
\hat{f}
$$
$$
f^{*};
$$
$$
\hat{f}
$$
$$
f^{*}
$$
$$
\varepsilon.
$$
Experiment 1 (Extraction experiment). Given a hypothesis class *F* = *ff* :
X*!* Y*g*, x an error function Err : *F!* R. Let *S* be a MLaaS server with the
knowledge of a specic *f 2F*, denoted by *S*(*f*). Let *A* be an adversary interacting with *S* with a maximum budget of *q* queries. The extraction experiment
"
ExpF(*S*(*f*)*; A;q*) proceeds as follows
$$
\mathbf{X}\to\mathbf{Y}\}
$$
$$
\mathcal{F}=\{f
$$
$$
\ cdot mathcal F rightarrow mathbb R,,
$$
$$
f^{*}\in\mathcal{F}.
$$
$$
S(f^{*})
$$
$$
{mathtt{E x p}}_{\mathcal{F}}^{\varepsilon}(S(f^{*}),\mathcal{A},q)
$$
1. *A* is given a description of *F* and oracle access to *f* through the query
interface of *S*. That is, if *A* sends *x 2* X to *S*, it gets back *y* = *f* (*x*).
After at most *q* queries, *A* eventually outputs *f*^;
$$
\mathcal{F}
$$
$$
f^{*}
$$
$$
x\in\mathrm{X}
$$
$$
S,
$$
$$
y=f^{*}(x)
$$
$$
\hat{f}
$$
2.The output of the experiment is 1 if Err(*f*^) *"*. Otherwise the output is
0.
$$
\operatorname{E r r}({\hat{f}})\leq\varepsilon
$$
Informally, an adversary *A* is successful if with high probability the output of
the extraction experiment is 1 for a small value of *"* and a xed query budget
*q*. This means that *A* likely learns a good approximation of *f* by only asking
*q* queries to the server. More precisely, we have the following denition.
$$
q
$$
---
Denition 3 (Extraction attack). Let *F* be a public hypothesis class and *S* an
MLaaS server as explained before. We say that an adversary *A*, which interacts
with *S*, implements an *"-extraction attack* of complexity *q* and condence
against the class *F* if
$$
\mathcal{F}
$$
$$
{\mathcal A},
$$
$$
\mathcal{F}
$$
$$
\operatorname*{P r}[{mathtt\ p E x p}_{\mathcal{F}}^{\varepsilon}(S(f^{*}),\mathcal{A},q)=1]\geq\gamma
$$
for any *f 2F*. The probability is over the randomness of *A*.
$$
f^{*}\in\mathcal{F}.
$$
In other words, in Denition3the success probability of an adversary constrained by a xed budget for queries is explicitly lower bounded by the quantity
.
Before discussing the connection between model extraction and active learning, we provide an example of a hypothesis class that is easy to extract.
*Example* 2 (Equation-solving attack for linear regression)*.* Let *F*d;Rbe the hyd
pothesis class of regression models from R to R. A function *f*ain this class
is described by *d* + 1 parameters *a₀;a₁;:::;a*dfrom R and dened by: for any
d
*x 2* R,
Xd
$$
\mathcal{F}_{d,R}
$$
$$
\mathbb{R}^{d}
$$
$$
\mathbb{R}
$$
$$
f_{a}
$$
$$
d+1
$$
$$
a_{0},a_{1},\ldots,a_{d}
$$
$$
x\in\mathbb{R}^{d}
$$
$$
f_{a}(x)=a_{0}+\sum_{i=1}^{d}a_{i}x_{i}\,.
$$
d+1 d
Consider the adversary *A*ESthat queries *x¹;:::;x* (*d*+ 1 instances from R)
i
chosen in such a way that the set of vectors *f*(1*;x*)*g*i=1;:::;d+1is linearly inded+1
pendent in R. *A*ESreceives the corresponding *d*+ 1 labels, *y₁;:::;y*d+1, and
i
can therefore solve the linear system given by the equations *f*a(*x*) = *y*i. Assume
i
that *f*ais the function known by the MLaaS server (*i.e.*, *y*i= *f*a(*x*)). It is easy
to see that if we x Err(*f*a) = *jja ajj₁*, then Pr[Exp⁰F(*S*(*f*a)*; A*ES*;d* + 1) =
d;R
1] = 1. That is, *A*ESimplements 0-extraction of complexity *d* + 1 and condence 1.
$$
\mathbb{R}^{d}\,
$$
$$
\mathcal{A}_{E S}
$$
$$
x^{1},\ldots,x^{d+1}
$$
$$
\{(1,x^{i})\}_{i=1,\ldots,d+1}
$$
$$
\mathbb{R}^{d+1}
$$
$$
\mathcal{A}_{E S}
$$
$$
d{+}1
$$
$$
y_{1},\ldots,y_{d+1}
$$
$$
f_{a}(x^{i})=y_{i}
$$
$$
f_{a}
$$
$$
(i(..e.,y_{i}=f_{a^{*}}(x^{i}))
$$
$$
\operatorname*{P r}[\mathtt{E x p}_{\mathcal{F}_{d.R}}^{0}(\mathtt{S}(f_{a^{*}}),\mathring{\mathcal{A}_{E S}},d{+}1)=
$$
$$
1|=1
$$
$$
\mathcal{A}_{E S}
$$
$$
d+1
$$
While our model operates in the black-box setting, we discuss other attack
models in more detail in Remark2
## 3.2Active Learning and Extraction
From the description presented in the Section2, it is clear that model extraction
in the MLaaS system context closely resembles active learning. The survey of
active learning in subsection2.2contains a variety of algorithms and scenarios which can be used to implement model extraction attacks (or to study its
impossibility).
However, dierent scenarios of active learning impose dierent assumptions
on the adversary’s prior knowledge. Here, we focus on the general case of model
extraction with an adversary *A* that has no knowledge of the data distribution
*D*. In particular, such an adversary is not restricted to only considering instances
*x D* to query.For this reason, we believe that query synthesis (QS) is the right
active learning scenario to investigate in order to draw a meaningful parallelism
with model extraction. Recall that the query synthesis is the only framework
where the query inputs can be generated de novo (*i.e.*, they do not conform to
a distribution).
$$
x\sim{\mathcal{D}}
$$
---
Observation 1: Given a hypothesis class *F* and an error function Err, let
(*L; O*) be an active learning system for *F* in the QS scenario (Denition2). If
the query complexity of *L* is *q*L(*";*), then there exists and adversary *A* that
implements *"*-extraction with complexity *q*L(*";*) and condence 1 against
the class *F*.
$$
(\mathcal{L},\mathcal{O})
$$
$$
q_{\mathcal{L}}(\varepsilon,\delta)
$$
$$
1-\delta
$$
$$
q_{\mathcal{L}}(\varepsilon,\delta)
$$
The reasoning for this observation is as follows: Consider the adversary *A*
that is the learner *L* (*i.e.*, *A* deploys the query strategy procedure and the
stopping criteria that describe *L*). This is possible because (*L; O*) is in the QS
scenario and *L* is independent of any underlying (unknown) distribution. Let
*q* = *q*L(*";*) and observe that
$$
\mathcal{L}\ (i.e.,\ mathcal{A}
$$
$$
(\mathcal{L},\mathcal{O})
$$
$$
q=q_{\mathcal{L}}(\varepsilon,\delta)
$$
$$
\begin{array}{r l}&{\operatorname*{P r}[\operatorname{E x p}_{\mathcal{F}}^{\varepsilon}(S(f^{*}),\mathcal{A},q)=1]=}\\ &{\operatorname*{P r}[\mathcal{A}\mathrm{~o u t p u t s~}\hat{f}\mathrm{~a n d~}\operatorname{E r r}(\hat{f})\leq\varepsilon]=}\\ &{\operatorname*{P r}[\mathcal{L}\mathrm{~o u t p u t s~}\hat{f}\mathrm{~a n d~}\operatorname{E r r}(\hat{f})\leq\varepsilon]\geq1-\delta}\end{array}
$$
Our observation states that any active learning algorithm in the QS scenario
can be used to implement a model extraction attack. Therefore, in order to
study the security of a given hypothesis class in the MLaaS framework, we
can use known techniques and results from the active learning literature. Two
examples of this follow.
*Example* 3 (Decision tree extraction via QS active learning)*.* Let *F*n;BFdenote
n
the set of boolean functions with domain *f*0*;* 1*g* and range *f*1*;* 1*g*. The reader
can think of 1 as 0 and +1 as 1. Using the range of *f*1*;*+1*g* is very common
in the literature on learning boolean functions. An interesting subset of *F*n;BF
is given by the functions that can be represented as a boolean decision tree. A
*boolean decision tree T* is a labeled binary tree, where each node *v* of the tree is
labeled by *L*v*f*1*;;ng* and has two outgoing edges. Every leaf in this tree
is labeled either +1 or 1. Given an *n*-bit string *x* = (*b₁;;b*n)*;b*i*2f*0*;* 1*g*
as input, the decision tree denes the following computation: the computation
starts at the root of the tree *T*. When the computation arrives at an internal
P
node *v* we calculate the parity ofi2L*b*iand go left if the parity is 0 and go
v
right otherwise. The value of the leaf that the computation ends up in is the
m
value of the function. We denote by *F*n;BTthe class of boolean decision trees
with *n*-bit input and *m* nodes. Kushilevitz and Mansour [44] present an active
learning algorithm for the class *F*n;BFthat works in the QS scenario. This
algorithm utilizes the uniform error to determine the stopping condition (refer
subsection2.2). The authors claim that this algorithm has practical eciency
m
when restricted to the classes *F*n;BT*F*n;BFfor any *m*. In particular, if the
m
active learner *L* of [44] interacts with the oracle *O*Twhere *T 2F*n;BT, then
*L* learns *g 2F*n;BFsuch that Prxf0;1gn [*g*(*x*) 6= *T* (*x*)] *"* with probability at
1 1
least 1 using a number of queries polynomial in *n*, *m*, and log(). Based
"
on Observation 1, this directly translates to the existence of an adversary that
1
implements *"*-extraction with complexity polynomial in *n*, *m*, and condence
"
m
1 against the class *F*n;BT.
$$
\mathcal{F}_{n,B F}
$$
$$
\overline{{\{0,1\}^{n}}}
$$
$$
\{-1,1\}
$$
$$
\{-1,+1\}
$$
$$
\mathcal{F}_{n,B F}
$$
$$
L_{v}\subseteq\{1,\cdots,n\}
$$
$$
+1{\mathrm{~o r~}}-1
$$
$$
x = \left(b _ {1}, \dots , b _ {n}\right), b _ {i} \in \{0, 1 \}
$$
$$
T
$$
$$
\textstyle\sum_{i\in L_{}}b_{i}
$$
$$
\mathcal{F}_{n,B T}^{m}
$$
$$
\mathcal{F}_{n,B F}
$$
$$
\mathcal{F}_{n,B T}^{m}\subset\mathcal{F}_{n,B F}
$$
$$
m
$$
$$
[44]
$$
$$
T^{*}\in\mathcal{F}_{n,B T}^{m}
$$
$$
\mathcal{O}_{T^{*}}
$$
$$
g\in\mathcal{F}_{n,B F}
$$
$$
\operatorname*{P r}_{x\sim\{0,1\}^{n}}[g(x)\neq T^{*}(x)]\leq\varepsilon
$$
$$
\log{\left({frac11}{\\delta\ }\right)}
$$
$$
1-\delta
$$
$$
\ {n,\,m,\,\ }\frac{1}{\varepsilon}
$$
$$
n,\,m,\,{\frac{1}{\varepsilon}}
$$
$$
\mathcal{F}_{n,B T}^{m}
$$
Moreover, the algorithm of [44] can be extended to (a) boolean functions
n
of the form *f* : *f*0*;* 1*;:::;k* 1*g! f* 1*;*+1*g* that can be computed by a
$$
f\ :\ \{0,1,\ldots,k\ -\ 1\}^{n}\ \to\ \{-1,+1\}
$$ polynomial-size *k*-ary decision tree³, and (b) regression trees (*i.e.*, the output is
a real value from [0*;M*]). In the second case, the running time of the learning
algorithm is polynomial in *M* (refer Section 6 of [44]). Note that the attack
model considered here is a stronger model than that considered by [67] because
the attacker/learner does not get any information about the internal path of
the decision tree (refer Remark2).
*Example* 4 (Halfspace extraction via QS active learning)*.* Let *F*d;HSbe the hypotheses class of *d*-dimensional halfspaces dened in Example1. Alabdulmohsin
*et al.* [3] present a spectral algorithm to learn a halfspace in the QS scenario
that, in practice, outperformed earlier active learning strategies in the PAC
scenario. They demonstrate, through several experiments that their algorithm
1
learns *f*w*2F*d;HSsuch that *kw w k₂ "* with approximately 2*d*log() queries,
"
where *f*w*2F*d;HSis the labeling function used by *O*. It follows from Observation 1 that an adversary utilizing this algorithm implements *"*-extraction against
1
the class *F*d;HSwith complexity *O*(*d*log()) and condence 1. We validate the
"
practical ecacy of this attack in Section6.
$$
\mathcal{F}_{d,H S}
$$
$$
f_{w}\in\mathcal{F}_{d,H S}
$$
$$
\|{w}{-}{w^{*}}\|_{2}\leq\varepsilon
$$
$$
2d\log{\bigl(}{\frac{1}{\varepsilon}}{\bigr)}
$$
$$
f_{w^{*}}\in\mathcal{F}_{d,H S}
$$
$$
\mathcal{F}_{d,H S}
$$
$$
\mathcal{O}(d\log(\frac{1}{\varepsilon}))
$$
*Remark* 2 (Extraction with auxiliary information)*.* Observe that we dene model
extraction for only those MLaaS servers that return *only the label value y* for
a *well-formed query x* (*i.e.* in the oracle access setting). A weaker model (*i.e.*,
one where attacks are easier) considers the case of MLaaS servers responding to
a user’s query *x* even when *x* is incomplete (*i.e.* with missing features), and returning the label *y* along with some auxiliary information. The work of Tramer
*et al.* [67] proves that model extraction attacks in the presence of such \leaky
servers" are feasible and ecient (*i.e.* low query complexity) for many hypothesis classes (*e.g.*, logistic regression, multilayer perceptron, and decision trees).
In particular, they propose an *equation solving attack* [67, Section 4.1] that uses
the condence values returned by the MLaaS server together with the labels
to steal the model parameters. For example, in the case of logistic regression,
the MLaaS server knows the parameters *a₀;a₁;:::;a*dand responds to a query
a(*x*)
x with the label *y* (*y* = 0 if (1 + *e*) 0*:* 5 and *y* = 1 otherwise) *and the*
*value a*(*x*) as condence value for *y*. Clearly, the knowledge of the condence
values allows an adversary to implement the same attack we describe in Example2for linear regression models. In [67, Section 4.2], the authors describes a
*path-nding attack* that use the leaf/node identier returned by the server, even
for incomplete queries, to steal a decision tree. These attacks are very ecient
(*i.e.*, *d*+1 queries are needed to steal a *d*-dimensional logistic regression model);
however, their eciency heavily relies on the presence of the various forms of
auxiliary information provided by the MLaaS server. While the work in [67]
performs preliminary exploration of attacks in the black-box setting [18,47], it
does not consider more recent, and ecient algorithms in the QS scenario. Our
work explores this direction through a formalization of the model extraction
framework that enables understanding the possibility of extending/improving
the active learning attacks presented in [67]. Furthermore, having a better
understanding of model extraction attack and its unavoidable connection with
$$
a_{0},a_{1},\ldots,a_{d}
$$
$$
\left(1+e^{-a\ x}\right)\leq0.5
$$
$$
y=1
$$
$$
a(x)
$$
3A *k*-ary decision tree is a tree in which each inner node *v* has *k* outgoing edges.
---
active learning is paramount for designing MLaaS systems that are resilient to
model extraction.
## 4Non-linear Classiers
This section focuses on model extraction for two important non-linear classiers:
kernel SVMs and discrete models (*i.e.* decision trees and random forests). For
kernel SVMs our method is a combination of the adaptive-retraining algorithm
introduced by Tramer *et al.* and the active selection strategy from classic literature on active learning of kernel SVMs [13]. For discrete models our algorithm is
based on the importance weighted active learning (IWAL) as described in [11].
Note that decision trees for general labels (*i.e.* non-binary case) and random
forests was not discussed in [11].
## 4.1Kernel SVMs
In kernel SVMs (kSVMs), there is a kernel *K* : X X*!* R associated with the
SVM. Some of the common kernels are polynomials and radial-basis functions
(RBFs). If the kernel function *K*(*:;:*) has some special properties (required by
T
classic theorem of Mercer [49]), then *K*(*:;:*) can be replaced with (*:*) (*:*) for
a projection/feature function . In the feature space (the domain of ) the
optimization problem is as follows⁴:
P
$$
K:\mathbf{X}\times\mathbf{X}\to\mathbb{R}
$$
$$
K(.,,)\,
$$
$$
K(.,,)
$$
$$
\dot{\Phi}(.)^{\bar{T}}\Phi(.)
$$
$$
\begin{array}{c}{\operatorname*{m i n}_{w,b}\lVert w\rVert^{2}+C\sum_{i=1}^{n}\eta_{i}}\\ {\operatorname{s u c h}\operatorname{t h a t}\operatorname{f o r}\ 1\leq i\leq n}\\ {y_{i}\hat{y}(x_{i})\ \geq\ 1-\eta_{i}}\\ {\eta_{i}\ \geq0}\\ \end{array}
$$
T
In the formulation given above, *y*^(*x*) is equal to *w* (*x*) + *b*. Recall that prediction of the kSVM is the sign of *y*^(*x*), so *y*^(*x*) is the \pre sign" value of the
prediction. Note that for some kernels (*e.g.* RBF) is innite dimensional, so
one generally uses the \kernel trick"*i.e.* one solves the dual of the above problem
and obtains a *kernel expansion*, so that
$$
{\hat{y}}(x)
$$
$$
wboldsymbol^{T}\boldsymbol\Phi(\boldsymbol x)+\boldsymbol b
$$
$$
{\hat{y}}(x)
$$
$$
\ {\hat{y}}(x)
$$
$$
\begin{array}{l c l}{{hat y x x}}&{{=}}&{{\displaystyle\sum_{i=1}^{n}\alpha_{i}K(x,x_{i})\;+\;b}}\\ \end{array}
$$
The vectors *x₁;;x*nare called support vectors. We assume that hyperparameters of the kernel (*C;*) are known; one can extract the hyper-parameters
for the RBF kernel using the extract-and-test approach as Tramer *et al.* Note
that if is nite dimensional, we can use an algorithm (including active learning strategies) for linear classier by simply working in the feature space (*i.e.*
extracting the domain of ( )). However, there is a subtle issue here, which was
not addressed by Tramer *et al.* We need to make sure that if a query *y* is made
in the feature space, it is \realizable" (*i.e.* there exists a *x* such that (*x*) = *y*).
Otherwise the learning algorithm is not sound.
$$
x_{1},\cdots,x_{n}
$$
$$
(C,\eta)
$$
$$
\Phi(\cdot))
$$
$$
\Phi(x)=y)
$$
Next we describe our model-extraction algorithm for kSVMs with kernels
whose feature space is innite dimension (*e.g.* RBF or Laplace kernels). Our
4we are using the formulation for soft-margin kSVMs algorithm is a modication of the adaptive training approach from Tramer *et*
*al.* Our discussion is specialized to kSVMs with RBFs, but our ideas are general
and are applicable in other contexts.
Extended Adaptive Training (EAT): EAT proceeds in multiple rounds. In
each round we construct *h* labeled instances. In the initial stage (*t* = 0) we
draw *r* instances *x₁;;x*rfrom the uniform distribution, query their labels,
and create an initial model *M₀*. Assume that we are at round *t*, where *t >* 0,
and let *M*t 1be model at time *t* 1. Round *t* works as follows: create *h*
T
labeled instances using a strategy *St* (*M*t 1*;h*) (note that the strategy *St* is
oracle access to the teacher, and takes as parameters model from the previous
round and number of labeled instances to be generated). Now we train *M*t 1
T
on the instances generated by *St* (*M*t 1*;h*) and obtain the updated model *M*t.
T
We keep iterating using the strategy *St* (*;*) until the query budget is satised.
T
Ideally, *St* (*M*t 1*;h*) should be instances that the model *M*t 1is *least condent*
about or closest to the decision boundary.
$$
(t=0)
$$
$$
x_{1},\cdots,x_{r}
$$
$$
M_{0}.
$$
$$
t>0
$$
$$
t,1
$$
$$
M_{t-1}
$$
$$
S t^{\mathcal{T}}(M_{t-1},h)
$$
$$
M_{t-1}
$$
$$
S t^{\mathcal{T}}(M_{t-1},h)
$$
$$
M_{t}.
$$
$$
S t^{\mathcal{T}}(\cdot,\cdot)
$$
$$
\mathrm{}{S t}^{\mathcal{T}}(M_{t-1},h)
$$
$$
M_{t-1}
$$
T
Tramer *et al.* use line search as their strategy *St* (*M*t 1*;h*), which can lead to
several queries (each step in the binary search leads to a query). We generate the
initial model *M₀* as in Tramer *et al.* and then our strategy diers. Our strategy
T
*St* (*M*t 1*;*1) (note that we only add one labeled sample at each iteration) works
as follows: we generate *k* random points *x₁;;x*kand then compute *y*^i(*x*i)
for each *x*i(recall that *y*^i(*x*i) is the \pre sign" prediction of *x*ion the SVM
*M*t 1. We then pick *x*iwith minimum *j y*^i(*x*i) *j* and query for its label and
retrain the model *M*t 1and obtain *M*t. This strategy is called *active selection*
and has been used for active learning of SVMs [13]. The argument for why this
strategy nds the point closest to the boundary is given in [13, §4]. There are
other strategies described in [13], but we found active selection to perform the
best.
$$
S t^{\mathcal{T}}(M_{t-1},h)
$$
$$
M_{0}
$$
$$
S t{t}^{\mathcal{T}}(M_{t-1},1)
$$
$$
x_{1},\cdots,x_{k}
$$
$$
\hat{y}{_i}(x_{i})
$$
$$
x_{i}
$$
$$
\hat{y_{i}}(x_{i})
$$
$$
x_{i}
$$
$$
M_{t-1}
$$
$$
x_{i}
$$
$$
\hat{y_{i}}(x_{i})
$$
$$
M_{t-1}
$$
$$
M_{t}
$$
## 4.2Decision Trees and Random Forests
Next we will describe the idea of *importance weighted active learning (IWAL)* [11].
Our discussion will be specialized to decision trees and random forests, but the
ideas that are described are general.
$$
\left(I W A L\right)\ [11]
$$
Let *H* be the hypothesis class (*i.e.* space of decision trees or random forests),
X is the space of data, and Y is the space of labels. The active learner has a
pool of unlabeled data *x₁;x₂;*. For *i >* 1, we denote by *X*1: i 1the sequence
*x₁;;x*i 1. After having processed the sequence *X*1: i 1, a coin is ipped with
probability *p*i*2* [0*;*1] and if it comes up heads, the label of *x*iis queried. We
also dene a set *S*i(*S₀* =*;*) recursively as follows: If the label for *x*iis not
queried, then *S*i= *S*i 1; otherwise *S*i= *S*i 1*[* (*x*i*;y*i*;p*i). Essentially the set
*S*ikeeps the information (*i.e.* data, label, and probability of querying) for all
the datapoints whose label was queried. Given a hypothesis *h 2H*, we dene
*err*(*h;S*n) as follows:
$$
i>1
$$
$$
x_{1},x_{2},\cdots
$$
$$
X_{1:i-1}
$$
$$
x_{1},\cdots,x_{i-1}
$$
$$
X_{1:i-1}
$$
$$
p_{i}\in[0,1]
$$
$$
x_{i}
$$
$$
S_{i}\,\left(S_{0}\,=\,\emptyset\right)
$$
$$
x_{i}
$$
$$
S_{i}\;=\;S_{i-1};
$$
$$
S_{i}\,=\,S_{i-1}\cup\bigl(x_{i},y_{i},p_{i}\bigr)
$$
$$
S_{i}
$$
$$
h\in\mathcal H
$$
$$
e r r(h,S_{n})
$$
$$
\begin{array}{r c l}{e r r(h,S_{n})}&{=}&{\displaystyle\frac{1}{n}\sum_{(x,y,p)\in S_{n}}\frac{1}{p}1_{h(x)\neq y}}\\ \end{array}
$$
(2)
---
$$
n\geq1)
$$
Next we dene the following quantities (we assume *n* 1):
$$
\begin{array}{r c l}{h_{n}}&{=}&{\operatorname{a r g m i n}\{e r r(h,S_{n-1})\ :\ h\in\mathcal{H}\}}\\ {h_{n}^{\prime}}&{=}&{\operatorname{a r g m i n}\{e r r(h,S_{n-1})\ :\ h\in\mathcal{H}\wedge h(X_{n})\neq h_{n}(X_{n})\}}\\ {G_{n}}&{=}&{e r r(h_{n}^{\prime},S_{n-1})-e r r(h_{n},S_{n-1})}\\ \end{array}
$$
Recall that *p*nis the probability of querying for the label for *X*n, which is dened
as follows:
1 if *G*n(*n*)
$$
p_{n}
$$
$$
X_{n}.
$$
$$
p_{n}={\left\{\begin{array}{l l}{1}&{{\mathrm{i f~}}G_{n}\leq\mu(n)}\\ {s(n)}&{{\mathrm{o t h e r w i s e}}}\end{array}\right.}
$$
q
c0 log n c0 log n
Where (*n*) = +, and *s*(*n*) *2* (0*;*1) is the positive solution to
n 1 n 1
the following equation:
$$
\mu(n)=\sqrt{\frac{c_{0}\log n}{n-1}}+\frac{c_{0}\log n}{n-1}
$$
$$
s(n)\in(0,1)
$$
$$
G_{n}~\ =~~\left(\frac{c_{1}}{\sqrt{s}-c_{1}+1}\right)\cdot\sqrt{\frac{c_{0}\operatorname{l o g}n}{n-1}}+\left(\frac{c_{2}}{\sqrt{s}-c_{2}+1}\right)\cdot\frac{c_{0}\operatorname{l o g}n}{n-1}
$$
Note the dependence on constants/hyperparameters *c₀*, *c₁* and *c₂*, which are
tuned for a specic problem (*e.g.* in their experiments for decision trees [11, §6]
the authors set *c₀* = 8 and *c₁* = *c₂* = 1).
$$
C_{0},\ C_{1}
$$
$$
c_{2}
$$
$$
(e,g.
$$
$$
c_{1}=c_{2}=1)
$$
$$
c_{0}=8
$$
Decision Trees: Let *DT* be any algorithm to create a decision tree. We start
with an initial tree *h₀* (this can constructed using a small, uniformly sampled
dataset whose labels are queried). Let *h*nbe the tree at step *n* 1. The question
0n th
is: how to construct *h*? Let *x*nbe the *n* datapoint and Y = *fl₁;;l*r*g* be
the set of labels. Let *h*n(*x*n) = *l*j. Let *h*n(*l*) be the modication of tree *h*nsuch
0n
that *h*n(*l*) produces label *l 6*= *h*n(*x*n) on datapoint *x*n. Let *h* be the tree in the
set *fh*n(*l*) *j l 2* Y*fl*j*gg* that has minimum *err*(*;S*n 1). Now we can compute
*G*nand the algorithm can proceed as described before.
$$
h_{n}
$$
$$
h_{n}^{\prime}?
$$
$$
x_{n}
$$
$$
n^{t h}
$$
$$
\mathbf{Y}=\{l_{1},\cdots,l_{r}\}
$$
$$
h_{n}(x_{n})=l_{j}
$$
$$
h_{n}(l)
$$
$$
h_{n}(l)
$$
$$
h_{n}
$$
$$
l\neq h_{n}(x_{n})
$$
$$
x_{n}
$$
$$
h_{n}^{\prime}
$$
$$
\left\{h _ {n} (l) \mid l \in \mathbf {Y} - \left\{l _ {j} \right\} \right\}
$$
$$
e r r(\cdot,S_{n-1})
$$
$$
G_{n}
$$
Random Forests: In this case we will restrict ourselves to binary classication,
but the algorithm can readily extended to the case of multiple labels. As before
*RF₀* is the random forest trained on a small initial dataset. Since we are in the
binary classication domain, the label set Y = *f*1*;* 1*g*. Assume that we have
a random forest *RF* = *fRF*[1]*;;RF*[*o*]*g* of trees *RF*[*i*] and on a datapoint *x*
the label of the random forest *RF*(*x*) is the majority of the label of the trees
*RF*[1](*x*)*;;RF*[*o*](*x*). Let *RF*nbe the random forest at time step *n* 1. The
0
question again is: how to construct *RF*n? Without loss of generality, let us say
on *x*n*RF*n(*x*n) = +1 (the case when the label is 1 is symmetric) and there
+1
are *r* trees in *RF*n(denoted by *RF*n(*x*n)) such that their labels on *x*nare +1.
o o
Note that *r > b₂c* because the majority label was +1. Dene *j* = *r b₂c* + 1.
+1
Note that if *j* trees in *RF*n(*x*n) will \ip" their decision to 1 on *x*n, then the
decision on *x*nwill be ipped to 1. This is the intuition we use to compute
0 r
*RF*n. There are choices of trees and we pick the one with minimum error on
j
0 r j
*S*n 1, and that gives us *RF*n. Recall that is approximately *r*, but we can
j
+1
be approximate by randomly picking *j* trees out of *RF*n(*x*n), and choosing the
0
random draw with the minimum error to approximate *RF*n.
$$
R F_{0}
$$
$$
\mathbf{Y}=\{1,-1\}
$$
$$
R F=\{R F[1],\cdots,R F[o]\}
$$
$$
x
$$
$$
R F[i]
$$
$$
R F(x)
$$
$$
R F[1](x),\cdots,R F[o](x)
$$
$$
n-1
$$
$$
R F_{n}
$$
$$
x_{n}\ R F_{n}(x_{n})=+1
$$
$$
R F_{n}^{\prime}?
$$
$$
R F_{n}^{+1}(x_{n})_{,}^{\dagger}
$$
$$
R F_{n}
$$
$$
x_{n}
$$
$$
r>\left\lfloor{\frac{o}{2}}\right\rfloor
$$
$$
j=r-\lfloor{\frac{o}{2}}\rfloor+1
$$
$$
R F_{n}^{+1}(x_{n})
$$
$$
\mathrm{i f}\,j
$$
$$
"flip"
$$
$$
x_{n}
$$
$$
x_{n}
$$
$$
R F_{n}^{\prime}
$$
$$
r^{j}
$$
$$
S_{n-1}
$$
$$
R F_{n}^{\prime}
$$
$$
\binom{r}{j}
$$
$$
R F_{n}^{+1}(x_{n})
$$
$$
j
$$
$$
R F_{n}^{\prime}
$$
---
## 5Defense Strategies
Our main observation is that model extraction in the context of MLaaS systems
described at the beginning of Section3(*i.e.*, oracle access) is equivalent to QS
active learning. Therefore, any advancement in the area of QS active learning
directly translates to a new threat for MLaaS systems. In this section, we
discuss strategies that could be used to make the process of extraction more
dicult.We investigate the link between machine-learning in the noisy setting
and model extraction. The design of a good defense strategy is an open problem;
we believe this is an interesting direction for future work where the machine
learning and the security communities can fruitfully collaborate.
In this section, we assume that the MLaaS server *S* with the knowledge of
*f*, *S*(*f*), has the freedom to modify the prediction before forwarding it to
the client. More precisely, we assume that there exists a (possibly) randomized
procedure *D* that the server uses to compute the answer *y*~ to a query *x*, and
returns that instead of *f* (*x*). We use the notation *S*D(*f*) to indicate that the
server *S* implements *D* to protect *f*. Clearly, the learner that interacts with
*S*D(*f*) can still try to learn a function *f* from the noisy answers from the server.
However, the added noise requires the process to make more queries, or could
produce a less accurate model than *f*.
$$
f^{*},\;S(f^{*})
$$
$$
\tilde{y}
$$
$$
f^{*}(x)
$$
$$
x,
$$
$$
S_{D}(f^{*})
$$
$$
f^{*}
$$
$$
S_{D}(f^{*})
$$
## 5.1Classication case
$$
f,
$$
We focus on the binary classication problem where *F* is an hypothesis class
of functions of the form *f* : X*!* Y and Y is binary, but our argument can be
easily generalized to the multi-class setting.
$$
\mathcal{F}
$$
$$
f:\mathbf{X}\to\mathbf{Y}
$$
First, in the following two remarks we recall two known results from the literature [34] that establish information theoretic bounds (i.e., the computational
cost is ignored) for the number of queries required to extract the model when
any defense is implemented. Let be the generalization error of the model *f*
known by the server *S*Dand be the generalization error of the model *f* learned
by an adversary interacting with *S*D(*f*). Assume that the hypothesis class *F*
has VC dimension equal to *d*. Recall that the VC dimension of a hypothesis
class *F* is the largest number *d* such that there exists a subset *X* X of size
*d* which can be shattered by *F*. A set *X* = *fx₁;:::;x*d*g* X is said to be
d
shattered by *F* if *jf*(*f* (*x₁*)*;f*(*x₂*)*;:::;f*(*x*d)) : *f 2Fgj* = 2.
$$
\nu
$$
$$
f^{*}
$$
$$
S_{D}
$$
$$
\mu
$$
$$
\mathcal{F}
$$
$$
S_{D}(f^{*})
$$
$$
d,
$$
$$
X\subset\mathbb{X}
$$
$$
\mathcal{F}
$$
$$
X\,=\,\{x_{1},\ldots,x_{d}\}\,\subset\,\mathbf{X}
$$
$$
\mathcal{F}{\mathrm{}{\ {i}}~}\vert|\{(f(x_{1}),f(x_{2}),\ldots,f(x_{d})):f\in\mathcal{F}\}|=2^{\hat{d}}.
$$
*Remark* 3 (Passive learning)*.* Assume that the adversary uses a passive learning algorithm to compute *f*, such as the Empirical Risk Minimization (ERM)
algorithm, where given a labeled training set *f*(*X₁;Y₁*)*;:::*(*X*n*;Y*n)*g*, the ERM
Pn
^ = arg min1
algorithm outputs *f*f 2F i=11[*f* (*X*i) 6= *Y*i]. Then, the adversary
n
^ with excess error ~(+*"*
can learn *f* " (*i.e.*, + *"*) with *O*2*d*) examples. For
"
any algorithm, there is a distribution such that the algorithm needs at least
~+"
(2*d*) samples to achieve an excess error of *"*.
"
$$
f_{i}
$$
$$
\{(X_{1},Y_{1}),\ldots(X_{n},Y_{n})\}
$$
$$
\hat{f}=\operatorname{a r g}\operatorname*{m i n}_{f\in\mathcal{F}}\textstyle\frac{1}{n}\sum_{i=1}^{n}\mathtt{I1}\left[f(X_{i})\ \ \neq\ Y_{i}\right]
$$
$$
\hat{f}
$$
$$
\varepsilon (i. e., \mu \leq \nu + \varepsilon)
$$
$$
\tilde{O}\big({textstyle\ \frac{\nu+\varepsilon}{\varepsilon^{2}}}d\big)
$$
$$
\tilde{\Omega}\bigl(\frac{\nu+\varepsilon}{\varepsilon^{2}}d\bigr)
$$
$$
\varepsilon
$$
*Remark* 4 (Active learning)*.* Assume that the adversary uses an active learning
algorithm to compute *f*, such as the disagreement-based active learning algo-
2
rithm [34]. Then, the adversary achieves excess error *"* with *O*~( *d*) queries
"2
(where is the disagreement coecient [34]). For any active learning algorithm,
$$
f{,}
$$
$$
\tilde{O}\bigl({\textstyle\frac{\nu^{2}}{\varepsilon^{2}}}d\theta\bigr)
$$
---
2
there is a distribution such that it takes at least (~ *d*) queries to achieve an
"2
excess error of *"*.
$$
\tilde{\Omega}(\frac{\nu^{2}}{\varepsilon^{2}}d)
$$
Observe that any defense strategy *D* used by a server *S* to prevent the
extraction of a model *f* can be seen as a randomized procedure that outputs
*y*~ instead of *f* (*x*) with a given probability over the random coins of *D*. In the
discrete case, we represent this with the notation
$$
S
$$
$$
f^{*}
$$
$$
D
$$
$$
\tilde{y}
$$
$$
f^{*}(x)
$$
$$
\rho_{D}\bigl(f^{*},x\bigr)=\operatorname*{P r}\bigl[Y_{x}\neq f^{*}(x)\bigr],
$$
(3)
where *Y*xis the random variable that represents the answer of the server *S*D(*f*)
to the query *x* (*e.g.*, ~*y Y*x). When the function *f* is xed, we can consider
the supremum of the functionD(*f;x*), which represents the upper bound for
the probability that an answer from *S*D(*f*) is wrong:
$$
Y_{x}
$$
$$
S_{D}(f^{*})
$$
$$
x\,(e.g.,\,\tilde{y}\gets Y_{x})
$$
$$
f^{*}
$$
$$
\rho_{D}(f^{*},x)
$$
$$
S_{D}(f^{*})
$$
$$
\rho_{D}(f^{*})=\operatorname*{s u p}_{x\in\mathbf{X}}\rho_{D}(f^{*},x).
$$
Before discussing potential defense approaches, we rst present a general negative result. The following proposition states that that any candidate defense
*D* that correctly responds to a query with probability greater than or equal to
1
+ *c* for some constant *c >* 0 for all instances can be easily broken. Indeed,
2
an adversary that repetitively queries the same instance *x* can gure out the
correct label *f* (*x*) by simply looking at the most frequent label that is returned
from *S*D(*f*). We prove that with this extraction strategy, the number of queries
required increases by only a logarithmic multiplicative factor.
$$
D
$$
$$
\frac{1}{2}+c
$$
$$
c>0
$$
$$
x
$$
$$
f^{*}(x)
$$
$$
S_{D}(f^{*})
$$
Proposition 1. *Let F be an hypothesis class used for classication and* (*L; O*)
*be an active learning system for F in the QS scenario with query complexity*
*q*(*";*)*. For any D, randomized procedure for returning labels, such that there*
1
exists f 2 F withD(f) <, there exists an adversary that, interacting
2
*with S*D(*f*)*, can implement an "-extraction attack with condence* 1 2 *and*
8 q(";)
*complexity q* =2*q*(*";*) ln*.*
(1 2D(f))
$$
(\mathcal{L},\mathcal{O})
$$
$$
q(\varepsilon,\delta)
$$
$$
f^{*}\;\in\;\mathcal{F}
$$
$$
\rho_{D}(f^{*})\;<\;\frac{1}{2}
$$
$$
S_{D}(f^{*})
$$
$$
1-2\delta
$$
$$
q=\frac{8}{(1-2\rho_{D}(f^{*}))^{2}}q(\varepsilon,\delta)
$$
$$
\frac{q(\varepsilon,\delta)}{\delta}
$$
The proof of Proposition1can be found in AppendixA.1.1.
Proposition1can be used to discuss the following two dierent defense strategies:
*1. Data-independent randomization.* Let *F* denote a hypothesis class that is
subject to an extraction attack using QS active learning. An intuitive defense for
*F* involves adding noise to the query output *f* (*x*) independent of the labeling
function *f* and the input query *x*. In other words,D(*f;x*) = for any *x 2* X,
*f 2F*, and is a constant value in the interval (0*;*1). It is easy to see that this
1
simple strategy cannot work. It follows from Proposition1that if <, then
2
1
*D* is not secure. On the other hand, if, then the server is useless since it
2
1
outputs an incorrect label with probability at least.
2
$$
\mathcal{F}
$$
$$
\mathcal{F}
$$
$$
f^{*}(x)
$$
$$
x\in\mathbb{X}
$$
$$
\rho_{D}(f,x)=\rho
$$
$$
f^{*}
$$
$$
x\cdot
$$
$$
f\in{\mathcal{F}}
$$
$$
\rho
$$
$$
\rho \geq \frac {1}{2}
$$
$$
\rho<\frac{1}{2}
$$
$$
D
$$
$$
\frac {1}{2}
$$
*Example* 5 (Halfspace extraction under noise)*.* For example, we know that *"*-
extraction with any level of condence can be implemented with complexity
1
*q* = *O*(*d*log()) using QS active learning for the class *F*d;HS*i.e.* for binary clas-
"
sication via halfspaces (refer Example4). It follows from the earlier discussion
$$
\varepsilon-
$$
$$
\ {q\textstyle={\cal O}(d\log\!\!(frac{1}{\varepsilon})\!\!)!}
$$
$$
\mathcal{F}_{d,H S}
$$ that any defense that ips labels with a constant ipping probability does not
work. This defense approach is similar to the case of \noisy oracles" studied
extensively in the active learning literature [37,38,54]. For example, from the
machine-learning literature we know that if the ipping probability is exactly
1
(), the AVERAGE algorithm (similar to our Algorithm1, dened in
2
2
~(d 1
Section6) *"*-extracts *f* with *O*2log) labels [40]. Under bounded noise
(1 2) "
1
where each label is ipped with probability at most (<), the AVERAGE
2
algorithm does not work anymore, but a modied Perceptron algorithm can
~(d 1
learn with *O*2log) labels [74] in a stream-based active learning setting,
(1 2) "
and a QS active learning algorithm proposed by Chen *et al.* [17] can also learn
with the same number of labels. An adversary implementing the Chen *et al.*
algorithm [17] is even more ecient than the adversary *A*~ dened in the proof
of Proposition1(*i.e.*, the total number of queries only increases by a constant
multiplicative factor instead of ln*q*(*;*)). We validate the practical eciency of
this attack in Section6.
$$
\rho\ (\rho\leq\,\frac{1}{2})
$$
$$
f^{*}
$$
$$
\tilde{O}(\textstyle\frac{d^{2}}{(1-2\rho)^{2}}\operatorname{l o g}\textstyle\frac{1}{\varepsilon})
$$
$$
\rho\ \ (\rho<\textstyle\frac{1}{2})
$$
$$
\tilde{O}\bigl(\textstyle\frac{d}{(1-2\rho)^{2}}\operatorname{l o g}\frac{1}{\varepsilon}\bigr)
$$
*2. Data-dependent randomization.* Based on the outcome of the earlier discussion, we believe that a defense that aims to protect a hypothesis class against
model extraction via QS active learning should implement data-dependent perturbation of the returned labels. That is, we are interested in a defense *D*
such that the probabilityD(*f;x*) depends on the query input *x* and the labeling function *f*. For example, given a class *F* that can be extracted using
an active learner *L* (in the QS scenario), if we consider a defense *D* such that
1
D(*f;x*) for some instances, then the proof of Proposition1does not work
2
1
(the argument only works if there is a constant *c >* 0 such thatD(*f;x*) *c*
2
for all *x*) and the eectiveness of the adversary *A*~ is not guaranteed anymore⁵.
$$
\rho_{D}(f^{*},x)
$$
$$
f^{*}
$$
$$
\mathcal{F}
$$
$$
\rho_{D}(f^{*},x)\geq\textstyle\frac{1}{2}
$$
$$
c>0
$$
$$
\rho_{D}\ f^{*}(f^{*},x)\leq{\textstyle{\frac{1}{2}}}\!
$$
$$
\tilde{A}
$$
*Example* 6 (Halfspace extraction under noise)*.* For the case of binary classication via halfspaces, Alabdulmohsin *et al.* [2] design a system that follows this
strategy. They consider the class *F*d;HSand design a learning rule that uses
training data to infer a distribution of models, as opposed to learning a single
model. To elaborate, the algorithm learns the mean and the covariance
for a multivariate Gaussian distribution *N* (*;*) on *F*d;HSsuch that any model
drawn from *N* (*;*) provides an accurate prediction. The problem of learning
such a distribution of classiers is formulated as a convex-optimization problem,
which can be solved quite eciently using existing solvers. During prediction,
when the label for a instance *x* is queried, a *new w* is drawn at random from
the learned distribution *N* (*;*) and the label is computed as *y* = sign(*hw;xi*).
The authors show that this randomization method can mitigate the risk of reverse engineering without incurring any notable loss in predictive accuracy. In
particular, they use PAC active learning algorithms [9,18] (assuming that the
$$
\mathcal{F}_{d,H S}
$$
$$
\mu
$$
$$
\mathcal{N}(\mu,\Sigma)
$$
$$
\mathcal{F}_{d,H S}
$$
$$
\mathcal{N}(\mu,\Sigma)
$$
$$
\mathcal{N}(\mu,\Sigma)
$$
$$
y=\mathrm{s i g n}(\langle w,x\rangle)
$$
5 1~
Intuitively, in the binary case ifD(*f;x*i) then the denition of *y*iperformed by *A*
2
in step 2 (majority vote) is likely to be wrong. However, notice that this is not always the
case in the multiclass setting: For example, consider the case when the answer to query *x*iis
1
dened to be wrong with probability and, when wrong, is sampled uniformly at random
2
among the *k* 1 classes that are dierent to the true class *f* (*x*), then if *k* is large enough, *y*i
dened via the majority vote is likely to be still correct.
$$
\rho_{D}(f^{*},x_{i})\geq\textstyle\frac{1}{2}
$$
$$
y_{i}
$$
$$
\tilde{A}
$$
$$
x_{i}
$$
$$
\geq\frac{1}{2}
$$
$$
f^{*}(x)
$$ underlying distribution *D* is Gaussian) to learn an approximation *w*^ from queries
answered in three dierent ways: (a) with their strategy, *i.e.* using a new model
for each query, (b) using a xed model to compute all labels, and (c) using a
xed model and adding independent noise to each label, *i.e. y* = sign(*hw;xi*+)
and [ 1*;*+1]. They show that the geometric error of *w*^ with respect to
the true model is higher in the former setting (*i.e.* in (a)) than in the others.
On 15 dierent datasets from the UC Irvine repository [1], their strategy gives
typically an order of magnitude larger error. We empirically evaluate this defense in the context of model extraction using QS active learning algorithms in
Section6.
$$
y = \operatorname {s i g n} (\langle w, x \rangle + \eta)
$$
$$
\eta\leftarrow[-1,+1]
$$
Continuous case: Generalizing Proposition1to the continuous case does not
seem straightforward, *i.e.* when the target model held by the MLaaS server is
a real-valued function *f* : X*!* R; A detailed discussion about the continuous
case appears in AppendixA.2.
## 6Implementation and Evaluation
For all experiments described below, we use an Ubuntu 16.04 server with 32 GB
RAM, and an Intel i5-6600 CPU clocking 3.30GHz. We use a combination of
datasets obtained from the scikit-learn library and the UCI machine learning
repository [1], as used by Tramer *et al.*.
## 6.1Linear Models
We carried out experiments to validate our claims that query synthesis active
learning can be used to successfully perform model extraction for linear models.
Our experiments are designed to answer the following three questions: (1) Is
active learning practically useful in settings without any auxiliary information,
such as condence values *i.e.* in an oracle access setting?, (2) Is active learning useful in scenarios where the oracle is able to perturb the output *i.e.* in a
data-independent randomization setting?, and (3) Is active learning useful in
scenarios where the oracle is able to perform more subtle perturbations *i.e.* in
a data-dependent randomization setting?
To answer these questions, we focused on learning the hypothesis class of *d*-
dimensional half spaces. To perform model extraction, we implemented two QS
algorithms [3,17] to learn an approximation *w*, and terminate execution when
*jjw wjj₂ "*. The metric we use to capture eciency is query complexity. To
provide a monetary estimate of an attack, we borrow pricing information from
the online pricing scheme of Amazon *i.e.* $0.0001 per query (more details are
present in Table1). We considered alternative stopping criteria, such as measuring the learned model’s stability over the *N* last iterations. Such a method
resulted in comparable error and query complexity (refer AppendixA.3.1for
detailed results). For our experiments, the halfspace held by the server/oracle
(*i.e.*, the optimal hypothesis *w*) was learned using Python’s scikit-learn
library. Our experiments suggest that:
$$
\left| \left| w ^ {*} - w \right| \right| _ {2} \leq \varepsilon
$$
1.QS active learning algorithms are ecient for model extraction, with low
query complexity and run-time. For the digits dataset (*d* = 64), the
---
Figure 3: Number of queries needed for halfspace extraction using the version space approxi-
1
mation algorithm. Note that the asymptotic query complexity for this algorithm is *O*(*d*log).
"
This explains the increase in query complexity as a function of *d*.
$$
O(\dot{d}\operatorname{l o g}\ \textstyle{frac{1}{\varepsilon}})
$$
dataset with the largest value of *d* which we evaluated on, the active
learning algorithm implemented required 900 queries to extract the half-
4
space with geometric error *"* 10. This amounts to $0*:* 09 worth of
queries.
$$
\varepsilon\leq10^{-4}
$$
2.QS active learning algorithms are also ecient when the oracle ips the
labels independently with constant probability. This only moderately increases the query complexity (for low values of). For the digits dataset of
input dimensionality *d* = 64, and a noise threshold = 0*:* 4, our algorithm
required 36546 queries (or $3*:* 65) to extract the halfspace with geometric
4
error *"* 10.
$$
\rho\cdot
$$
$$
\rho)
$$
$$
d=64
$$
$$
\rho=0.4
$$
$$
\varepsilon\leq10^{-4}
$$
3.State-of-the-art QS algorithms fail to recover the model when the oracle
responds to queries using tailored model randomization techniques (refer
subsection5, specically the algorithm by Alabdulmohsin *et al.* [2]). However, passive learning algorithms (refer Algorithm1) are eective in this
setting.
In each gure, we plot the price (*i.e.* $0*:* 0001 per query) for the most expensive attack we launch to serve as a baseline. We conclude by comparing our
approach with the algorithm proposed by Lowd and Meek [47].
Q1. Usefulness in an oracle access setting: We implemented Version
Space Approximation proposed by Alabdulmohsin *et al.* [3] in approximately 50
lines of MATLAB. This algorithm operates iteratively, based on the principles
of version space learning. A version space [51] is a hierarchical representation
of knowledge. It can also be thought of as the subset of hypotheses consistent
with the training examples. In each iteration, the algorithm rst approximates a
version space, and then synthesizes an instance that reduces this approximated
1
version space quickly. The nal query complexity for this algorithm is *O*(*d*log).
"
---
Figure3plots the number of queries needed to extract a halfspace as a
function of termination criterion *i.e.* geometric error *"*. As discussed earlier,
the query complexity is dependent on the dimensionality of the halfspace to be
extracted. Across all values of dimensionality *d*, observe that with the exponential decrease in error *"*, the increase in query complexity is linear - often by a
small factor (1*:* 3 1*:* 5). The implemented query synthesis algorithm involves
solving a convex optimization problem to approximate the version space, an operation that is potentially time consuming. However, based on several runs of
our experiment, we noticed that the algorithm always converges in < 2 minutes.
$$
d,
$$
$$
\varepsilon,
$$
$$
(1.3\,\times\,-1.5\times)
$$
While the equation solving attack proposed by Tramer *et al.* [67] requires
fewer queries, it also requires the actual value of the prediction output *i.e.*
*hw ;xi* as auxiliary information. On the other hand, extraction using query
synthesis does not rely on any auxiliary information returned by the MLaaS
server to increase its eciency *i.e.* the only input needed for query synthesisbased extraction attacks is sign(*hw ;xi*).
$$
\langle w^{*},x\rangle
$$
$$
(\langle w^{*},x\rangle)
$$
Q2. Resilience to data-independent noise: An intuitive defense against
model extraction might be to ip the sign of the prediction output with independent probability i.e. if the output y 2f1; 1g, then Pr[y 6= signhw ;xi] = <
1
(refer subsection5). This setting (*i.e.*, noisy oracles) is extensively studied in
2
the machine learning community. Trivial solutions including repeated sampling
to obtain a batch where majority voting (determines the right label) can be employed; if the probability that the outcome of the vote is correct is represented
log1
as 1, then the batch size needed for the voting procedure is *k* = *O*(2)
j 0: 5j
*i.e.* there is an increase in query complexity by a (multiplicative) factor *k*, an
expensive proposition. While other solutions exist [53,73], we implemented the
dimension coupling (*DC²*) framework proposed by Chen *et al.* [17] in approximately 150 lines of MATLAB. The dimension coupling framework reduces a
*d* dimensional learning problem to *d* 1 lower-dimensional sub-problems. It
then appropriately aggregates the results to produce a halfspace. This approach
is resilient to noise *i.e.* the oracle can ip the label with constant probability
1
(known a priori) <, and the algorithm will converge with probability 1.
2
~(1 1
The query complexity for this algorithm is *O d* (log + log)).
"
$$
\rho\ i,e
$$
$$
y\in\{1,-1\}
$$
$$
P r\big[y\neq\mathrm{s i g n}\big\langle w^{*},x\big\rangle\big]=\rho<
$$
$$
\frac{1}{2}
$$
$$
(i.e..
$$
$$
1-\alpha.
$$
$$
k=O(\frac{\log\frac{1}{\alpha}}{|\rho-0.5|^{2}})
$$
$$
k,
$$
$$
i.e.
$$
$$
(D C^{2})
$$
$$
d-1
$$
$$
i.e.
$$
$$
\rho<\frac{1}{2}
$$
$$
1-\delta.
$$
$$
\tilde{O}\big(d\;(\log\frac{1}{\varepsilon}+\log\frac{1}{\delta})\big)
$$
The results of our experiment are presented in Figure4. The algorithm is
successful in extracting the halfspace for a variety of values. The exact bound
1 1
is *C*()(*d* (log + log), where *C*() is a function of that is approximately
"
log³(1=)
*O*(2). Thus, there is a multiplicative increase in the number of queries
log 2(1)
with increase in. This introduces a modest increase in complexity in comparison to the noise-free setting. While the increase in pricing is 40, this results
in a worst case expenditure of $3*:* 6 (see Figure4(c)). The time (and number of queries) taken for convergence is proportional to, ranging from 1 20
minutes for successful completion.
$$
\rho
$$
$$
C(\rho)(d\ (\log\textstyle\ \frac{1}{\varepsilon}+\log\textstyle\frac{1}{\delta}
$$
$$
C(\rho)
$$
$$
\rho
$$
$$
O \left(\frac {\rho \log^ {3} (1 / \rho)}{\log^ {2} 2 (1 - \rho)}\right)
$$
$$
\rho
$$
$$
\approx40\times
$$
$$
\approx\oint3.6
$$
$$
4(\mathrm{c}))
$$
$$
\rho,
$$
Q3. Resilience to data-dependent noise: As alluded to in subsection5,
another defense against extraction involves learning a family of functions very
similar to *w* such that they all provide accurate predictions with high prob-
$$
^{5,}
$$
$$
w^{*}
$$
---
(a) Adult Income
(b) Breast Cancer
(c) Digits
(d) Wine
Figure 4: Number of queries needed for halfspace extraction using the dimension coupling
~(1 1
algorithm. Note that the asymptotic query complexity for this algorithm is *O d*(log +log)).
"
This explains the increase in query complexity as a function of *d*.
$$
\tilde {O} \left(d \left(\log \frac {1}{\varepsilon} + \log \frac {1}{\delta}\right)\right)
$$
$$
d.
$$
ability. Proposed by Alabdulmohsin *et al.* [2], data-dependent randomization
enables the MLaaS server to sample a random function for each query *i.e.* for
each instance *x*i, the MLaaS server obtains a new *w*is *N* (*;*) and responds
with *y*i= sign(*hw*i*;xi*i). Thus, this approach can be thought of as ipping the
sign of the prediction output with probabilityD(*w ;x*i) (see subsection5).
$$
i.e.
$$
$$
x_{i}.
$$
$$
\mathrm{M L a a}S\,{}
$$
$$
w_{i}\sim\mathcal{N}(\mu,\sigma)
$$
$$
y_{i}=\operatorname{s i g n}(\langle w_{i},x_{i}\rangle)
$$
$$
\rho_{D}(w^{*},x_{i})
$$
In this algorithm, a separation parameter *C* determines how close the samples from *N* (*;*) are; larger the value of *C*, closer each sample is (refer Section
4 in [2] for more details). We measure the value ofD(*w ;x*i) as a function of *C*
for those *x*ivalues generated by the dimension coupling algorithm.D(*w ;x*i)
is estimated by (a) obtaining *w₁;;w*ns *N* (*;*), for *n* = 1000, and using
them to classify *x*ito obtain *y₁* = sign(*hw₁;xi*i)*;;y*n, and (b) obtaining the
percentage of the prediction outputs that is not equal to sign(*hw ;xi*i). Our
1
hope was that if the value of max8xi D(w ;xi) <, then an adversary similar
2
to *A*~ dened in Proposition1could be used to perform extraction.
$$
\mathcal{N}(\mu,\sigma)
$$
$$
C,
$$
$$
C
$$
$$
\rho_{D}(w^{*},x_{i})
$$
$$
x_{i}
$$
$$
\rho_{D}(w^{*},x_{i})
$$
$$
w_{1},\cdots,w_{n}\sim\mathcal{N}(\mu,\sigma)
$$
$$
n=1000
$$
$$
x_{i}
$$
$$
y _ {1} = \operatorname {s i g n} \left(\langle w _ {1}, x _ {i} \rangle\right), \dots , y _ {n}
$$
$$
\left\langle w^{*},x_{i}\right\rangle^{\prime}
$$
$$
\cdot_{\forall x_{i}}\ \rho_{D}(w^{*},x_{i})<\textstyle\ {\frac{1}{2}}
$$
$$
\tilde{A}
$$
1
Figure5suggests otherwise; the average value ofD(*w ;x*i) for
2
some small *>* 0. Since any adversary will be unable to determine a priori
the inputs for which this value is greater than half, neither majority voting, nor
the vanilla dimension coupling framework will help extract the halfspace. We
believe this is the case for current state-of-the-art algorithms as the instances
they synthesize are "close" to the optimal halfspace. To validate this claim,
we measured this distance for both the algorithms [3,17]. We observed that a
$$
\rho_ {D} \left(w ^ {*}, x _ {i}\right) \approx \frac {1}{2} \pm \gamma
$$
$$
\gamma>0
$$
---
1
Figure 5: averageD(*w;x*i); *x*isynthesized by the dimension coupling algorithm.
2
majority of the points are very close to the halfspace in both cases (see Figure
7in AppendixA.3.2for more details).
$$
\mathsf{e e}\rho_{D}\big(w^{*},x_{i}\big)\approx\textstyle\ \frac{1}{2}\pm\gamma;\,x_{i}
$$
$$
7
$$
Algorithm 1 Passive Learning Algorithm that breaks [2]
p1
1: Input: variance upper bound ^, target error *"*
d
2
(15) 2 2d
2: *m*2*d*max(1*;d*^) log, *l*
" 121d^
d 1
3: Draw *x₁;x₂;:::;x*m*2* S uniformly at random, and query their labels
*y₁;y₂;:::;y*m
Pm
4: *v*i=1*y*i*x*i
5: if *kvk l* then
v
6: Return *w* =
kvk
7: else
8: Return fail
9: end if
$$
\hat{\sigma}\geq\frac{1}{\sqrt{d}}
$$
$$
\varepsilon
$$
$$
\leftarrow \frac {(1 5 \pi) ^ {2}}{\varepsilon^ {2}} d \max (1, d \hat {\sigma} ^ {2})
$$
$$
\textstyle{\frac{2d}{\delta},,l l\leftarrow{frac1{2d d\hat{\sigma}}}}
$$
$$
\mathring{x_{1}},x_{2},\dots,x_{m}\,\\ \in\,\mathring{\mathbb{S}^{d-1}}
$$
$$
y_{1},y_{2},\ldots,y_{m}
$$
$$
\textstyle{v\leftarrow\sum_{i=1}^{m}y_{i}x_{i}}
$$
$$
\|v\|\geq l
$$
$$
w boldsymbol{}}=\frac{\boldsymbol{v}}{\|\boldsymbol{v}\|
$$
Such forms of data-dependent randomization, however, are not secure against
traditional passive learning algorithms. Such an algorithm takes as input an es-
~(d 2
timated upper bound ^ for. The algorithm rst draws *O*2max(1*;d*^))
"
d 1
instances from the *d* dimensional unit sphere S uniformly at random, and
proceeds to have them labeled - by the oracle dened in [2] in this case. It then
Pm
v
computes the average *v* =i=1*y*i*x*i. *w* =, the direction of *v*, is the algokvk
rithm’s estimate of the classier *w*, and the length of *v* is used as an indicator
of whether the algorithm succeeds: if this estimated upper bound is correct (i.e.
^), then with high probability, *kw w k "*; otherwise it outputs fail,
indicating the variance bound ^ is incorrect. In such situations, we can reduce
^ and try again. A detailed proof of the algorithm’s guarantees is available in
AppendixA.1.2.
$$
\hat{\sigma}
$$
$$
\tilde {O} \left(\frac {d}{\varepsilon^ {2}} \max \left(1, d \hat {\sigma} ^ {2}\right)\right)
$$
$$
\mathbb{S}^{d-1}
$$
$$
v=\sum_{i=1}^{m}y_{i}x_{i}.\;w=\frac{v}{\|v\|}
$$
$$
v
$$
$$
w^{*}
$$
$$
v
$$
$$
\sigma\leq\hat{\sigma})
$$
$$
\left\|w-w^{*}\right\|\leq\,\varepsilon;
$$
$$
\hat{\sigma}
$$
$$
\hat{\sigma}
$$
While the asymptotic bounds for Algorithm1are larger than the active
---
Figure 6: log(Number of queries) needed for halfspace extraction (protected by the defense
strategy proposed in [2]) using Algorithm1. Note that the asymptotic query complexity for
1 2 2d
this algorithm is *O*(2*d*max(1;d^) log). This explains the increase in query complexity as
"
Cd
a function of *d* and *"*. The large value of2dominates the query complexity in this algorithm.
"
The price is plotted for the attack on the breast cancer dataset.
$$
[\!2])
$$
$$
O(\frac{1}{\varepsilon^{2}}
$$
$$
(1,d\hat{\sigma}^{2},
$$
$$
\frac{2d}{\delta})
$$
$$
\ \frac{C d}{\varepsilon^{2}}
$$
2
learning algorithms discussed thus far, the constant *C* = (15) can be reduced
C
by a multiplicative factor to reduce the total number of queries used *i.e.*
100
C
or etc. In Figure6, we observe that extracting halfspaces with geometric
1000
1 4 3 7
error *"* 10 requires 10 queries. While achieving *"* 10 requires 10
queries, the algorithm can be executed in parallel enabling faster run-times.
$$
\mathcal{C}=(15\pi)^{2}
$$
$$
i.e.\ \frac{\mathcal{C}}{1\ \cap\Omega}
$$
$$
\frac {\mathcal {C}}{1 0 0 0}
$$
$$
\varepsilon\approx10^{-1}
$$
$$
\leq10^{4}
$$
$$
\varepsilon\approx10^{-3}
$$
$$
10^{7}
$$
Lowd and Meek Baseline: The algorithm proposed by Lowd and Meek [47]
can also be used to extract a halfspace. However, note that this algorithm can
only operate in a noise-free setting. This is a severe limitation if a setting where
the MLaaS employs defense strategies. From Table2, one can observe that
the number of queries required to extract the halfspace is more than the query
synthesis algorithms we implemented. For example, consider the breast cancer
dataset. The version space algorithm is able to extract a halfspace at a distance
4
of *"* 10 with 400 queries (or $0*:* 04). However, the algorithm proposed by
Lowd and Meek takes 970 queries for extraction. Additionally, the geometric
error of the extracted halfspaces are also higher than those extracted in the
query synthesis case. The query complexity of the Lowd and Meek algorithm
1 jwij
is *O*(*d*log()), where *a* = mini=1;;d kw(*w*iis the *i*-th coordinate of the
a" k
1
groundtruth classier *w*). This is worse than the *O*(*d*log()) query complexity
"
of classical active learning algorithms. While this algorithm is not tailored to
minimize the geometric error, we believe that these results further validate our
claim that query synthesis active learning is a promising direction to explore.
$$
\varepsilon\leq10^{-4}
$$
$$
\mathit{a}=\operatorname{m i n}_{i=1,\cdots,d}\frac{|w|_{i}^{*}|}{\|w^{*}\|}
$$
$$
O(d\log(\frac{1}{a\varepsilon}))
$$
$$
(w_{i}^{*}
$$
$$
w^{*}]
$$
$$
O(d\log\big(\frac{1}{\varepsilon}\big),
$$
## 6.2Non-Linear Models
In this section, we report experimental results for extraction ecacy for nonlinear decision boundaries, specically for kernel SVMs and decision trees. Our
---
| Dataset | Queries | $\varepsilon$ | Slowdown |
| --- | --- | --- | --- |
| Wine | 189 | 0.071 | 1.67× |
| Breast Cancer | 940 | 0.162 | 3.19× |
| Digits | 1879 | 0.665 | 2.62× |
Table 2: Number of queries and geometric error observed after extracting halfspaces using
the line search procedure proposed by Lowd and Meek. Observe that the geometric error in
some cases is large. Slowdown indicates the ratio between number of queries taken for the
Lowd and Meek procedure and those taken by the DC2algorithm [17] for *"* = 0*:* 01, and = 0.
experiments are designed to answer the following two questions: (1) Is QS active
learning practically useful to extract non-linear models (*i.e.*, kernel SVMs) in
an oracle access setting?, and (2) Is active learning useful to extract non-linear
models (*i.e.*, decision trees) in scenarios where the ML server does not reveal
any auxiliary information? As before, we use the same datasets as in Tramer
et al. [67]. The continuous variables are made discrete by binning (*i.e.* dividing
into groups), and are then one-hot-encoded. Our experiments suggest that:
1.Utilizing the extended adaptive training (EAT) approach (refer subsection4.1) is ecient for extracting kernel SVMs. Our approach improves
query complexity by 5-224.
2.Utilizing the IWAL algorithm (refer subsection4.2) enables extracting a
decision tree in the absence of *any* auxiliary information, with a nominal
increase in query complexity (14).
Q1. Kernel SVM: As discussed in subsection4.1, Tramer et al. use *adaptive*
*retraining*- a procedure to locate points close to the decision boundary - to
obtain points used to seed their attack. Using these (labeled) points, they
are able obtain the parameters which were used to instantiate the oracle using
an extract-and-test approach (more specically grid search). While techniques
in active learning can not be used to expedite the grid search procedure, our
experiments suggest that they are able to select more *informative* points i.e.
points of greater uncertainty, with far fewer queries. With insight from the work
of Bordes et al. [13], we propose the *extended adaptive retraining approach* (refer
subsection4.1) to obtain uncertain points. Additionally, we measure uncertainty
with respect to a model that we train locally⁶, eliminating redundant queries
to the oracle. To compare the eciency of our algorithm, we re-execute the
adaptive retraining procedure, and present our results in Table3.
It is clear that our approach is more query ecient in comparison to Tramer
*et al.* (between 5-224), with comparable test accuracy. These advantages
stem from (a) using a more informative metric of uncertainty than the distance
from the decision boundary, and (b) querying labels of only those points which
the local model is uncertain about.
Q2. Decision Trees: Tramer et al. propose a path nding algorithm to
determine the structure of the server-hosted decision tree. They rely on the
6such a local model is seeded with uniformly random points labeled by the oracle
---
| Dataset | Adaptive Retraining | | EAT | |
| --- | --- | --- | --- | --- |
| Dataset | Queries | Accuracy | Queries | Accuracy |
| Mushroom | 11301 | 98.5 | 1001 | 94.5 |
| Breast Cancer | 1101 | 99.3 | 119 | 96.4 |
| Adult | 10901 | 96.98 | 48 | 98.2 |
| Diabetes | 901 | 98.5 | 166 | 94.8 |
Table 3: Extraction of a kernel SVM model. Comparison of the query complexity and test
accuracy (in %) obtained running Tramer *et al.* adaptive retraining vs. extended adaptive
retraining.
| Dataset | Oracle | Path Finding | IWAL | |
| --- | --- | --- | --- | --- |
| Dataset | Accuracy | Queries | Queries | Accuracy |
| Adult | 81.2 | 18323 | 244188 | 80.2 |
| Steak | 52.1 | 5205 | 1334 | 73.1 |
| Iris | 86.8 | 246 | 361 | 89.4 |
| GSShappiness | 79 | 18907 | 254892 | 79.3 |
Table 4: Extraction of a decision tree model. Comparison of the query complexity and test
accuracy (in %) obtained by running path nding (Tramer *et al.*) vs. IWAL algorithm. The
test accuracy (in %) of the server-hosted oracle is presented as a baseline.
server’s response to incomplete queries, and the addition of node identiers to
the generated outputs to recreate the tree. From our analysis presented in
Table1such exibility is not readily available in most MLaaS providers. As
discussed earlier (refer subsection4.2), we utilize the IWAL algorithm proposed
by Beygelzimer et al. [11] that iteratively renes a learned hypothesis. It is
important to note that the IWAL algorithm is more general, and does not rely
on the information needed by the path nding algorithm. We present the results
of extraction using the IWAL algorithm below in Table4.
In each iteration, the algorithm learns a new hypothesis, but the eciency
of the approach relies on the hypothesis used preceding the rst iteration. To
this end, we generate inputs uniformly at random. Note that in such the *uni-*
*form* scenario, we rely on zero auxiliary information. We can see that while the
number of queries required to launch such extraction attacks is greater than
in the approach proposed by Tramer et al., such an approach obtains comparable test error to the oracle. While the authors rely on certain distributional
assumptions to prove a label complexity result, we empirically observe success
using the uniform strategy. Such an approach is truly powerful; it makes limited
assumptions about the MLaaS provider and any prior knowledge.
## 7Discussion
We begin our discussion by highlighting algorithms an adversary could use if
the assumptions made about the operational ecosystem are relaxed. Then, we
discuss strategies that can potentially be used to make the process of extraction
more dicult, and shortcomings in our approach.
---
## 7.1Varying The Adversary’s Capabilities
The operational ecosystem in this work is one where the adversary is able to
synthesize data-points de novo to extract a model through oracle access. In
this section, we discuss other algorithms an adversary could use if this assumption is relaxed. We begin by discussing other models an adversary can learn
in the query synthesis regime, and move on to discussing algorithms in other
approaches.
*Equivalence queries.* In her seminal work, Angluin [4] proposes a learning algorithm, *L*, to correctly learn a regular set from any minimally adequate teacher,
in polynomial time. For this to work, however, *equivalence queries* are also
needed along with membership queries. Should MLaaS servers provide responses
to such equivalence queries, dierent extraction attacks could be devised. To
learn linear decision boundaries, Wang *et al.* [71] rst synthesize an instance
close to the decision boundary using labeled data, and then select the real instance closest to the synthesized one as a query. Similarly, Awasthi *et al.* [7]
study learning algorithms that make queries that are close to examples generated from the data distribution. These attacks require the adversary to have
access to some subset of the original training data. In other domains, program
synthesis using input-output example pairs [25,32,58,70] also follows a similar
principle.
If the adversary had access to a subset of the training data, or had prior
knowledge of the distribution from which this data was drawn from, it could
launch a dierent set of attacks based on the algorithms discussed below.
*Stream-based selective sampling.* Atlas *et al.* [6] propose selective sampling as
a form of directed search (similar to Mitchell [50]) that can greatly increase
the ability of a connectionist network (*i.e.* power system security analysis in
their paper) to generalize accurately. Dagan *et al.* [20] propose a method for
training probabilistic classiers by choosing those examples from a stream that
are *more informative*. Lindenbaum *et al.* [45] present a lookahead algorithm for
selective sampling of examples for nearest neighbor classiers. The algorithm
looks for the example with the highest utility, taking its eect on the resulting
classier into account. Another important application of selective learning was
for feature selection [46], an important preprocessing step. Other applications of
stream-based selective sampling include sensor scheduling [41], learning ranking
functions for information retrieval [75], and in word sense disambiguation [31].
*Pool-based sampling.* Dasgupta [23] surveys active learning in the non-separable
case, with a special focus on statistical learning theory. He claims that in this
setting, AL algorithms usually follow one of the following two strategies - (i)
Ecient search in the hypothesis spaces (as in the algorithm proposed by Chen
*et al.* [17], or by Cohn *et al.* [18]), or (ii) Exploiting clusters in the data (as
in the algorithm proposed by Dasgupta *et al.* [24]). The latter option can be
used to learn more complex models, such as decision trees. As the ideal halving
algorithm is dicult to implement in practice, pool-based approximations are
used instead such as uncertainty sampling and the query-by-committee (QBC)
algorithm [15,30,65]. Unfortunately, such approximation methods are only guaranteed to work well if the number of unlabeled examples (i.e. pool size)
grows exponentially fast with each iteration. Otherwise, such heuristics become
crude approximations and they can perform quite poorly.
## 7.2Complex Models
PAC active learning strategies have proven eective in learning DNNs. The
work of Sener *et al.* [60] selects the most representative points from a sample of
the training distribution to learn the DNN. Papernot *et al.* [55] employ substitute model training - a procedure where a small training subset is strategically
augmented and used to train a shadow model that resembles the model being
attacked. Note that the prior approaches rely on some additional information,
such as a subset of the training data.
Active learning algorithms considered in this paper work in an iterative
fashion. Let *H* be the entire hypothesis class. At time time *t* 0 let the set
of possible hypothesis be *H*t*H*. Usually an active-learning algorithm issues
a query at time *t* and updates the possible set of hypothesis to *H*t+1, which is
a subset of *H*t. Once the size of *H*tis \small" the algorithm stops. Analyzing
the eect of a query on possible set of hypothesis is very complicated in the
context of complex models, such as DNNs. We believe this is a very important
and interesting direction for future work.
$$
t\geq0
$$
$$
\mathcal{H}_{t}\subseteq\mathcal{H}
$$
$$
\mathcal{H}_{t+1}
$$
$$
\ {mathcal H}_{t}.
$$
$$
\mathcal{H}_{t}
$$
## 7.3Model Transferability
Most work in active learning has assumed that the correct hypothesis space
for the task is already known *i.e.* if the model being learned is for logistic
regression, or is a neural network and so on. In such situations, observe that the
labeled data being used is biased, in that it is implicitly tied to the underlying
hypothesis. Thus, it can become problematic if one wishes to re-use the labeled
data chosen to learn *another, dierent* hypothesis space. This leads us to *model*
*transferability⁷*, a less studied form of defense where the oracle responds to any
query with the prediction output from an entirely dierent hypothesis class. For
example, imagine if a learner tries to learn a halfspace, but the teacher performs
prediction using a boolean decision tree. Initial work in this space includes that
of Shi *et al.* [62], where an adversary can steal a linear separator by learning
input-output relations using a deep neural network. However, the performance
of query synthesis active learning in such ecosystems is unclear.
## 7.4Limitations
We stress that these limitations are not a function of our specic approach,
and stem from the theory of active learning. Specically: (1) As noted by
Dasgupta [22], the label complexity of PAC active learning depends heavily on
1 1
the specic target hypothesis, and can range from *O*(log) to (). Similar
" "
results have been obtained by others [35,52]. This suggests that for some
hypotheses classes, the query complexity of active learning algorithms is as high
as that in the passive setting. (2) Some query synthesis algorithms assume that
there is some labeled data to bootstrap the system. However, this may not
$$
\Omega(\frac{1}{\varepsilon})
$$
7A special case of agnostic active learning [8].
---
always be true, and randomly generating these labeled points *may* adversely
impact the performance of the algorithm. (3) For our particular implementation,
the algorithms proposed rely on the *geometric error* between the optimal and
learned halfspaces. Oftentimes, however, there is no direct correlation between
this geometric error and the generalization error used to measure the model’s
*goodness*.
## 8Related Work
Machine learning algorithms and systems are optimized for performance. Little attention is paid to the security and privacy risks of these systems and
algorithms. Our work is motivated by the following attacks against machine
learning.
*1. Causative Attacks:* These attacks are primarily geared at *poisoning* the training data used for learning, such that the classier produced performs erroneously
during test time. These include: (a) mislabeling the training data, (b) changing
rewards in the case of reinforcement learning, or (c) modifying the sampling
mechanism (to add some bias) such that it does not reect the true underlying
distribution in the case of unsupervised learning [57]. The work of Papernot
*et al.* [56] modify input features resulting in misclassication by Deep Neural
Networks.
*2. Evasion Attacks:* Once the algorithm has trained successfully, these forms
of attacks provide *tailored* inputs such that the output is erroneous. These
*noisy inputs* often preserves the semantics of the original inputs, are human
imperceptible, or are physically realizable. The well studied area of *adversarial*
*examples* is an instantiation of such an attack. Moreover, evasion attacks can
also be even black-box *i.e.* the attacker needn’t know the model. This is because
an adversarial example optimized for one model is highly likely to be eective for
other models. This concept, known as *transferability*, was introduced by Carlini
*et al.* [16]. Notable works in this space include [12,26,28,42,43,55,66,72]
*3. Exploratory Attacks:* These forms of attacks are the primary focus of this
work, and are geared at learning intrinsics about the algorithm used for training.
These intrinsics can include learning model parameters, hyperparameters, or
training data. Typically, these forms of attacks fall in two categories -*model*
*inversion*, or *model extraction*. In the rst class, Fredrikson *et al.* [29] show
that an attacker can learn sensitive information about the dataset used to train
a model, given access to side-channel information about the dataset. In the
second class, the work of Tramer *et al.* [67] provides attacks to learn parameters
of a model hosted on the cloud, through a query interface. Termed *membership*
*inference*, Shokri *et al.* [63] learn the training data used for machine learning by
training their own inference models. Wang *et al.* [69] propose attacks to learn
a model’s hyperparameters.
## 9Conclusions
In this paper, we formalize model extraction in the context of Machine-Learningas-a-Service (MLaaS) servers that return only prediction values (*i.e.*, oracle ac- cess setting), and we study its relation with *query synthesis* active learning
(Observation 1). Thus, we are able to implement ecient attacks to the class
of halfspace models used for binary classication (Section6). While our experiments focus on the class of halfspace models, we believe that extraction via
active learning can be extended to multiclass and non-linear models such as deep
neural networks, random forests etc. We also begin exploring possible defense
approaches (subsection5). To the best of our knowledge, this is the rst work to
formalize security in the context of MLaaS systems. We believe this is a fundamental rst step in designing more secure MLaaS systems. Finally, we suggest
that data-dependent randomization (*e.g.*, model randomization as in [2]) is the
most promising direction to follow in order to design eective defenses.
## 10Acknowledgements
This material is partially supported by Air Force Grant FA9550-18-1-0166,
the National Science Foundation (NSF) Grants CCF-FMitF-1836978, SaTC-
Frontiers-1804648 and CCF-1652140 and ARO grant number W911NF-17-1-
0405. Kamalika Chaudhuri and Songbai Yan thank NSF under 1719133 and
1804829 for research support.
## References
[2]Ibrahim M. Alabdulmohsin, Xin Gao, and Xiangliang Zhang. Adding robustness to support vector machines against adversarial reverse engineering. In *Proceedings of the 23rd ACM International Conference on Confer-*
*ence on Information and Knowledge Management, CIKM 2014, Shanghai,*
*China, November 3-7, 2014*, pages 231{240, 2014.
[3]Ibrahim M Alabdulmohsin, Xin Gao, and Xiangliang Zhang. Ecient active learning of halfspaces via query synthesis. In *AAAI*, pages 2483{2489,
2015.
[4]Dana Angluin. Learning regular sets from queries and counterexamples.
*Information and computation*, 75(2):87{106, 1987.
[5]Giuseppe Ateniese, Luigi V. Mancini, Angelo Spognardi, Antonio Villani, Domenico Vitali, and Giovanni Felici. Hacking smart machines with
smarter ones: How to extract meaningful data from machine learning classiers. *IJSN*, 10(3):137{150, 2015.
[6]Les E Atlas, David A Cohn, and Richard E Ladner. Training connectionist networks with queries and selective sampling. In *Advances in neural*
*information processing systems*, pages 566{573, 1990.
[7]Pranjal Awasthi, Vitaly Feldman, and Varun Kanade. Learning using local
membership queries. In *Conference on Learning Theory*, pages 398{431,
2013.
[8]Maria-Florina Balcan, Alina Beygelzimer, and John Langford. Agnostic
active learning. *Journal of Computer and System Sciences*, 75(1):78{89,
2009.
[9]Maria-Florina Balcan, Andrei Z. Broder, and Tong Zhang. Margin based
[1] https://archive.ics.uci.edu/ml/datasets.html, 2018.
---
active learning. In *Learning Theory, 20th Annual Conference on Learning*
*Theory, COLT 2007, San Diego, CA, USA, June 13-15, 2007, Proceedings*,
pages 35{50, 2007.
[10]Maria-Florina Balcan and Philip M. Long. Active and passive learning of
linear separators under log-concave distributions. In *COLT 2013 - The*
*26th Annual Conference on Learning Theory, June 12-14, 2013, Princeton*
*University, NJ, USA*, pages 288{316, 2013.
[11]Alina Beygelzimer, Daniel Hsu, John Langford, and Tong Zhang. Agnostic
active learning without constraints. In *23rd International Conference on*
*Neural Information Processing Systems (NIPS)*, 2010.
[12]Arjun Nitin Bhagoji, Warren He, Bo Li, and Dawn Song. Black-box attacks
on deep neural networks via gradient estimation. 2018.
[13]Antoine Bordes, Seyda Ertekin, Jason Weston, and Leon Bottou. Fast kernel classiers with online and active learning. *Journal of Machine Learning*
*Research (JMLR)*, September 2005.
[14]Wieland Brendel, Jonas Rauber, and Matthias Bethge. Decision-based
adversarial attacks: Reliable attacks against black-box machine learning
models. *arXiv preprint arXiv:1712.04248*, 2017.
[15]Klaus Brinker. Incorporating diversity in active learning with support vector machines. In *Proceedings of the 20th International Conference on Ma-*
*chine Learning (ICML-03)*, pages 59{66, 2003.
[16]Nicholas Carlini and David Wagner. Towards evaluating the robustness of
neural networks. In *Security and Privacy (SP), 2017 IEEE Symposium on*,
pages 39{57. IEEE, 2017.
[17]Lin Chen, Seyed Hamed Hassani, and Amin Karbasi. Near-optimal active
learning of halfspaces via query synthesis in the noisy setting. In *AAAI*,
pages 1798{1804, 2017.
[18]David Cohn, Les Atlas, and Richard Ladner. Improving generalization with
active learning. *Machine learning*, 15(2):201{221, 1994.
[19]Hsu D. and Sabato S. Heavy-tailed regression with a generalized medianof-means. In *International Conference on Machine Learning (ICML)*, 2014.
[20]Ido Dagan and Sean P Engelson. Committee-based sampling for training
probabilistic classiers. In *Proceedings of the Twelfth International Confer-*
*ence on Machine Learning*, pages 150{157. The Morgan Kaufmann series
in machine learning,(San Francisco, CA, USA), 1995.
[21]S. Dasgupta, D. Hsu, and C. Monteleoni. A general agnostic active learning
algorithm. In *NIPS*, 2007.
[22]Sanjoy Dasgupta. Coarse sample complexity bounds for active learning.
In *Advances in Neural Information Processing Systems 18 [Neural Infor-*
*mation Processing Systems, NIPS 2005, December 5-8, 2005, Vancouver,*
*British Columbia, Canada]*, pages 235{242, 2005.
[23]Sanjoy Dasgupta. Two faces of active learning. *Theoretical computer sci-*
*ence*, 412(19):1767{1781, 2011.
[24]Sanjoy Dasgupta, Daniel J Hsu, and Claire Monteleoni. A general agnostic
active learning algorithm. In *Advances in neural information processing*
*systems*, pages 353{360, 2008.
---
[25]Dana Drachsler-Cohen, Sharon Shoham, and Eran Yahav. Synthesis with
abstract examples. In *International Conference on Computer Aided Veri-*
*cation*, pages 254{278. Springer, 2017.
[26]Gamaleldin F Elsayed, Shreya Shankar, Brian Cheung, Nicolas Papernot, Alex Kurakin, Ian Goodfellow, and Jascha Sohl-Dickstein. Adversarial examples that fool both human and computer vision. *arXiv preprint*
*arXiv:1802.08195*, 2018.
[27]Chaudhuri K. et al. Convergence rates of active learning for maximum likelihood estimation. In *Advances in Neural Information Processing Systems*,
2015.
[28]Ivan Evtimov, Kevin Eykholt, Earlence Fernandes, Tadayoshi Kohno,
Bo Li, Atul Prakash, Amir Rahmati, and Dawn Song. Robust physicalworld attacks on deep learning models. *arXiv preprint arXiv:1707.08945*,
1, 2017.
[29]Matthew Fredrikson, Eric Lantz, Somesh Jha, Simon Lin, David Page,
and Thomas Ristenpart. Privacy in pharmacogenetics: An end-to-end case
study of personalized warfarin dosing. In *USENIX Security Symposium*,
pages 17{32, 2014.
[30]Yoav Freund, H Sebastian Seung, Eli Shamir, and Naftali Tishby. Selective sampling using the query by committee algorithm. *Machine learning*,
28(2):133{168, 1997.
[31]Atsushi Fujii, Takenobu Tokunaga, Kentaro Inui, and Hozumi Tanaka. Selective sampling for example-based word sense disambiguation. *Computa-*
*tional Linguistics*, 24(4):573{597, 1998.
[32]Sumit Gulwani. Synthesis from examples: Interaction models and algorithms. In *Symbolic and Numeric Algorithms for Scientic Computing*
*(SYNASC), 2012 14th International Symposium on*, pages 8{14. IEEE,
2012.
[33]S. Hanneke. A bound on the label complexity of agnostic active learning.
In *ICML*, 2007.
[34]Steve Hanneke. Theory of disagreement-based active learning. *Foundations*
*and Trends in Machine Learning*, 7(2-3):131{309, 2014.
[35]Tibor Heged}us. Generalized teaching dimensions and the query complexity
of learning. In *Proceedings of the eighth annual conference on Computa-*
*tional learning theory*, pages 108{117. ACM, 1995.
[36]Ling Huang, Anthony D. Joseph, Blaine Nelson, Benjamin I. P. Rubinstein,
and J. D. Tygar. Adversarial machine learning. In *Proceedings of the*
*4th ACM Workshop on Security and Articial Intelligence, AISec 2011,*
*Chicago, IL, USA, October 21, 2011*, pages 43{58, 2011.
[37]Matti Kaariainen. Active learning in the non-realizable case. In *Algorithmic*
*Learning Theory, 17th International Conference, ALT 2006, Barcelona,*
*Spain, October 7-10, 2006, Proceedings*, pages 63{77, 2006.
[38]Richard M. Karp and Robert Kleinberg. Noisy binary search and its applications. In *Proceedings of the Eighteenth Annual ACM-SIAM Symposium*
*on Discrete Algorithms, SODA 2007, New Orleans, Louisiana, USA, Jan-*
*uary 7-9, 2007*, pages 881{890, 2007.
---
[39]Ross D King, Jem Rowland, Stephen G Oliver, Michael Young, Wayne
Aubrey, Emma Byrne, Maria Liakata, Magdalena Markham, Pinar Pir,
Larisa N Soldatova, et al. The automation of science. *Science*,
324(5923):85{89, 2009.
[40]Adam R. Klivans and Pravesh Kothari. Embedding hard learning problems
into gaussian space. In *Approximation, Randomization, and Combinato-*
*rial Optimization. Algorithms and Techniques, APPROX/RANDOM 2014,*
*September 4-6, 2014, Barcelona, Spain*, pages 793{809, 2014.
[41]Vikram Krishnamurthy. Algorithms for optimal scheduling and management of hidden markov model sensors. *IEEE Transactions on Signal Pro-*
*cessing*, 50(6):1382{1397, 2002.
[42]Alex Kurakin, Dan Boneh, Florian Tramer, Ian Goodfellow, Nicolas Papernot, and Patrick McDaniel. Ensemble adversarial training: Attacks and
defenses. 2018.
[43]Alexey Kurakin, Ian Goodfellow, and Samy Bengio. Adversarial machine
learning at scale. *arXiv preprint arXiv:1611.01236*, 2016.
[44]Eyal Kushilevitz and Yishay Mansour. Learning decision trees using the
fourier spectrum. *SIAM J. Comput.*, 22(6):1331{1348, 1993.
[45]Michael Lindenbaum, Shaul Markovitch, and Dmitry Rusakov. Selective
sampling for nearest neighbor classiers. In *AAAI/IAAI*, pages 366{371.
Citeseer, 1999.
[46]Huan Liu, Hiroshi Motoda, and Lei Yu. A selective sampling approach to
active feature selection. *Articial Intelligence*, 159(1-2):49{74, 2004.
[47]Daniel Lowd and Christopher Meek. Adversarial learning. In *Proceedings*
*of the Eleventh ACM SIGKDD International Conference on Knowledge*
*Discovery and Data Mining, Chicago, Illinois, USA, August 21-24, 2005*,
pages 641{647, 2005.
[48]Andrew McCallum and Kamal Nigam. Employing EM and pool-based
active learning for text classication. In *Proceedings of the Fifteenth In-*
*ternational Conference on Machine Learning, Madison, Wisconsin, USA,*
*July 24-27, 1998*, pages 350{358, 1998.
[49]Ha Quang Minh, Partha Niyogi, and Yuan Yao. Mercers theorem, feature maps, and smoothing. In *International Conference on Computational*
*Learning Theory*, pages 154{168. Springer, 2006.
[50]Tom M Mitchell. Generalization as search. *Articial intelligence*, 18(2):203{
226, 1982.
[51]Tom Michael Mitchell. Version spaces: an approach to concept learning.
Technical report, STANFORD UNIV CALIF DEPT OF COMPUTER SCI-
ENCE, 1978.
[52]Mohammad Naghshvar, Tara Javidi, and Kamalika Chaudhuri. Noisy
bayesian active learning. In *Communication, Control, and Computing*
*(Allerton), 2012 50th Annual Allerton Conference on*, pages 1626{1633.
IEEE, 2012.
[53]Robert Nowak. Noisy generalized binary search. In *Advances in neural*
*information processing systems*, pages 1366{1374, 2009.
[54]Robert D. Nowak. The geometry of generalized binary search. *IEEE Trans.*
---
*Information Theory*, 57(12):7893{7906, 2011.
[55]Nicolas Papernot, Patrick McDaniel, Ian Goodfellow, Somesh Jha,
Z Berkay Celik, and Ananthram Swami. Practical black-box attacks against
machine learning. In *Proceedings of the 2017 ACM on Asia Conference on*
*Computer and Communications Security*, pages 506{519. ACM, 2017.
[56]Nicolas Papernot, Patrick McDaniel, Somesh Jha, Matt Fredrikson,
Z Berkay Celik, and Ananthram Swami. The limitations of deep learning
in adversarial settings. In *Security and Privacy (EuroS&P), 2016 IEEE*
*European Symposium on*, pages 372{387. IEEE, 2016.
[57]Nicolas Papernot, Patrick McDaniel, Arunesh Sinha, and Michael Wellman.
Towards the science of security and privacy in machine learning. *arXiv*
*preprint arXiv:1611.03814*, 2016.
[58]Hila Peleg, Shachar Itzhaky, and Sharon Shoham. Abstraction-based interaction model for synthesis. In *International Conference on Verica-*
*tion, Model Checking, and Abstract Interpretation*, pages 382{405. Springer,
2018.
[59]Sabato S. and Munos R. Active regression by stratication. In *Advances*
*in Neural Information Processing Systems (NIPS)*, 2014.
[60]Ozan Sener and Silvio Savarese. Active learning for convolutional neural
networks: A core-set approach. 2018.
[61]B Settles. Active learning literature survey univ. wisconsin-madison, madison, wi, 2009. Technical report, CS Tech. Rep. 1648.
[62]Yi Shi, Yalin Sagduyu, and Alexander Grushin. How to steal a machine
learning classier with deep learning. In *Technologies for Homeland Se-*
*curity (HST), 2017 IEEE International Symposium on*, pages 1{5. IEEE,
2017.
[63]Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly Shmatikov.
Membership inference attacks against machine learning models. In *Se-*
*curity and Privacy (SP), 2017 IEEE Symposium on*, pages 3{18. IEEE,
2017.
[64]Nedim Srndic and Pavel Laskov. Practical evasion of a learning-based
classier: A case study. In *2014 IEEE Symposium on Security and Privacy,*
*SP 2014, Berkeley, CA, USA, May 18-21, 2014*, pages 197{211, 2014.
[65]Simon Tong and Daphne Koller. Support vector machine active learning
with applications to text classication. *Journal of machine learning re-*
*search*, 2(Nov):45{66, 2001.
[66]Florian Tramer, Nicolas Papernot, Ian Goodfellow, Dan Boneh, and Patrick
McDaniel. The space of transferable adversarial examples. *arXiv preprint*
*arXiv:1704.03453*, 2017.
[67]Florian Tramer, Fan Zhang, Ari Juels, Michael K. Reiter, and Thomas
Ristenpart. Stealing machine learning models via prediction apis. In *25th*
*USENIX Security Symposium, USENIX Security 16, Austin, TX, USA,*
*August 10-12, 2016.*, pages 601{618, 2016.
[68]Leslie G Valiant. A theory of the learnable. *Communications of the ACM*,
27(11):1134{1142, 1984.
[69]Binghui Wang and Neil Zhenqiang Gong. Stealing hyperparameters in machine learning. *arXiv preprint arXiv:1802.05351*, 2018.
[70]Chenglong Wang, Alvin Cheung, and Rastislav Bodik. Interactive query
synthesis from input-output examples. In *Proceedings of the 2017 ACM*
*International Conference on Management of Data*, pages 1631{1634. ACM,
2017.
[71]Liantao Wang, Xuelei Hu, Bo Yuan, and Jianfeng Lu. Active learning via
query synthesis and nearest neighbour search. *Neurocomputing*, 147:426{
434, 2015.
[72]David Warde-Farley and Ian Goodfellow. 11 adversarial perturbations of
deep neural networks. *Perturbations, Optimization, and Statistics*, page
311, 2016.
[73]Songbai Yan, Kamalika Chaudhuri, and Tara Javidi. Active learning from
imperfect labelers. In *Advances in Neural Information Processing Systems*,
pages 2128{2136, 2016.
[74]Songbai Yan and Chicheng Zhang. Revisiting perceptron: Ecient and
label-optimal learning of halfspaces. In *Advances in Neural Information*
*Processing Systems 30: Annual Conference on Neural Information Pro-*
*cessing Systems 2017, 4-9 December 2017, Long Beach, CA, USA*, pages
1056{1066, 2017.
[75]Hwanjo Yu. Svm selective sampling for ranking with application to data
retrieval. In *Proceedings of the eleventh ACM SIGKDD international con-*
*ference on Knowledge discovery in data mining*, pages 354{363. ACM, 2005.
[76]Chicheng Zhang and Kamalika Chaudhuri. Beyond disagreement-based
agnostic active learning. In *Advances in Neural Information Processing*
*Systems*, pages 442{450, 2014.
## AAppendix
## A.1Proofs
## A.1.1Proof of Proposition1
*Proof.* Let *A*~ be the adversary that does the following:
$$
\tilde{A}
$$
for *i* = 1*;:::;q*(*";*)
$$
i=1,\ldots,q(\varepsilon,\delta)
$$
1. *A*~ uses the query strategy of *L* to generate the instance *x*;
i
$$
\tilde{A}
$$
$$
x_{i;}
$$
$$
x_{i}
$$
2. *A*~ queries *x* to *S* (*f*) for *r* times and denes *y* the most frequent labels
i D i
among the *r* answers (we assume *r* is an even integer).
$$
S_{D}(f^{*})
$$
$$
y_{i}
$$
At the end, *A*~ (as the learner *L*) learns *f*^ using the points *f*(*x;y*)*g*.
i i i=1;;q(";)
Let *q* = *r q*(*";*), then it holds by the union bound that
$$
\{\big(x_{i},y_{i}\big)\}_{i=1,\cdots,q(\varepsilon,\delta)}.
$$
$$
\tilde{A}
$$
$$
\hat{f}
$$
$$
q=r\cdot q(\varepsilon,\delta)
$$
$$
\begin{aligned}{}&{{}\operatorname*{P r}[\operatorname{E x p}_{\mathcal{F}}^{\varepsilon}(S_{D}(f^{*}),\tilde{A},q)=1]\geq}\\ {}&{{}1-\delta-\left(1-\operatorname*{P r}[\cap_{i=1}^{q(\varepsilon,\delta)}\{y_{i}=f^{*}(x_{i})\}]\right).}\\ \end{aligned}
$$
Dene *X*ijas the binary random variable that is 1 if and only if the answer
$$
X_{i}^{j}
$$
---
Pr
to the *j*-th query of *x*iis correct and *X*i=j=1*X*ij, then
$$
X_{i}=\sum_{j=1}^{r}X_{i}^{j}
$$
$$
x_{i}
$$
$$
\begin{aligned}{\operatorname*{P r}[\cap_{i=1}^{q(\varepsilon,\delta)}\{y_{i}=f^{*}(x_{i})\}]}&{{}\geq\operatorname*{P r}[\cap_{i=1}^{q(\varepsilon,\delta)}\{X_{i}>r/2\}]}\\ {}&{{}\geq1-\sum_{i=1}^{q(\varepsilon,\delta)}\operatorname*{P r}[\{X_{i}\leq r/2\}]}\\ \end{aligned}
$$
where the last step follows from the union bound. Now, observe that E[*X*i] =
*r*(1D(*f;x*i)) *> r=*2 and the Cherno bound can be applied on each term in
1 2
( D (*f*) 2)
r2
the right-hand side. In particular, we have that Pr[*fX*i*r=*2*g*] *e*
and it follows that
$$
\mathbb{E}[X_{i}]=
$$
$$
r\big(1-\rho_{D}\big(f^{*},x_{i}\big)\big)>r/2
$$
$$
\operatorname*{P r}[\{X_{i}\leq r/2\}]\leq e^{-r\frac{\left(\rho_{D}(f^{*})-\frac{1}{2}\right)^{2}}{2}}
$$
$$
\operatorname*{P r}[\mathtt{E x p}_{\mathcal{F}}^{\varepsilon}(S_{D}(f^{*}),\tilde{A},q)=1]\geq1-\delta-q(\varepsilon,\delta)\,e^{-r\frac{(\rho_{D}(f^{*})-\frac{1}{2})^{2}}{2}}\,.
$$
8 q(";) "~
By setting *r* =2ln we have Pr[ExpF(*S*D(*f*)*; A;q*) = 1]
(1 2D(f))
1 2 . That is, the adversary *A*~ implements an *"*-extraction with Condence
8 q(";)
Score 1 2 and complexity *q* =2q(*";*) ln.
(1 2D(f))
$$
\begin{array}{l}{r\;=\;\frac{8}{(1-2\rho_{D}(f^{*}))^{2}}\operatorname{l n}\frac{q(\varepsilon,\delta)}{\delta}}\\ {end{;}}\end{array}
$$
$$
\operatorname*{P r}[{mathtt E x x}_{\mathcal{F}}^{\varepsilon}(S_{D}(f^{*}),{tilde{A}},q)\,=\,1]\,\geq
$$
$$
1-2\delta
$$
$$
\begin{array}{l}{q\stackrel\cdot=\frac{\tilde{8}}{(1-2\rho_{D}(f^{*}))^{2}}q(\varepsilon,\delta)\operatorname{l n}\frac{q(\varepsilon,\delta)}{\delta}}\\ \end{array}
$$
## A.1.2Proof of Algorithm1
Here, we discuss the analysis and proofs associated with Algorithm1.
d d
Assume unit vector *2* R is the ground truth. For each query *x 2* R, a
2
vector *w* is drawn from *N* (*; I*), and the label *y* = sign(*hw;xi*) is returned.
The goal of the learner (attacker) is to return *w*^ such that *k w*^*k* is small.
$$
\boldsymbol{\mu}\in\mathbb{R}^{d}
$$
$$
x\in\mathbb{R}^{d}
$$
$$
N\big(\mu,\sigma^{2}I\big)
$$
$$
y=\operatorname{s i g n}(\langle w,x\rangle)
$$
$$
\left\|\mu-\hat{w}\right\|
$$
We have following theoretical guarantees for Algorithm1.
Proposition 1. *If* ^*, then kw*^ *k " with probability at least* 1*.*
$$
I f\,\sigma\leq\hat{\sigma}
$$
$$
1-\delta
$$
$$
\|\hat{w}-\mu\|\leq\varepsilon
$$
p1 1
Proposition 2. *If* ^ *and* ^*, then kvk with probability at least*
d 12d^
1*.*
$$
I f\,\sigma\leq\hat{\sigma}
$$
$$
\textstyle\hat{\sigma}\geq\frac{1}{\sqrt{d}}
$$
$$
\|\boldsymbol{v}\|\geq\frac{1}{12d\hat{\sigma}}
$$
$$
1-\delta
$$
p1 p 1
Proposition 3. *If* 20^*, then kvk with probability at least*
d 148d^
1*.*
$$
\sigma\geq20\hat{\sigma}\geq\frac{1}{\sqrt{d}}
$$
$$
\left\|v\right\|\leq\frac{1}{\sqrt{148}d\hat{\sigma}}
$$
$$
1-\delta
$$
Propositions1and2guarantees that if the estimated upper bound is correct
( ^), then the algorithm outputs an accurate estimation of; Proposition3
guarantees the algorithm declares failure if the estimated upper bound is too
1
small (^).
20
$$
\left(\sigma\leq\hat{\sigma}\right)
$$
$$
\mu,
$$
$$
\textstyle\left(\hat{\sigma}\leq\frac{1}{20}\sigma\right)
$$
Intuitively, the average of *y*i*x*i(*i* = 1*;:::;m*) points to a direction similar to
because of the symmetry of distributions of both *x* and noise: the projection
of *yx* onto all directions perpendicular to is distributed symmetrically around
0 and thus has mean 0. The projection of *yx* onto has non-negative mean
> 1
since the label *y* is correct (i.e., *yv x* 0) with probability at least, and the
2
projection is larger if the noise of *y* is smaller. Consequently, the scale of the
average can be used as an indicator of the noise level. The Propositions can be
formally proved by applying concentration inequalities on each direction.
$$
y_{i}x_{i}\;(i=1,\ldots,m)
$$
$$
\mu
$$
$$
\mu
$$
$$
y x
$$
$$
\mu
$$
$$
y
$$
$$
(\mathrm{i.e.,}\,y v^{\top}x\geq0)
$$
$$
\frac{1}{2}
$$
$$
y
$$ d 1 d >
Notation. *Denote by* S *the unit sphere fx 2* R : *x x* = 1*g. For any*
d (i)
*vector X 2* R*, denote by X the i-th coordinate of X. Dene Z*i= *Y*i*X*i*for*
*i* = 1*;* 2*;:::;m.*
$$
\mathbb{S}^{d-1}
$$
$$
\{x\,\in\,\mathbb{R}^{d}\,:\,x^{\top}x\,=\,1\}
$$
$$
X\in\mathbb{R}^{d}
$$
$$
X^{(i)}
$$
$$
Z_{i}=Y_{i}X_{i}\;\ \!{\ r}
$$
$$
i=1,2,\ldots,m
$$
We need following facts.
?>
> w x 1
Fact 1. Pr(*w x* 0) = PrN(0;1)(). *Moreover, for z* 0*,*
kxk 2
p z z 1 1 z
PrN(0;1)() max(*;*)*.*
2 6 2 3
$$
\operatorname*{P r}(w^{\top}x\geq0)=\operatorname*{P r}_{\xi\sim N(0,1)}(\xi\geq\,-\frac{w^{\star\top}x}{\sigma\|x\|})
$$
$$
\scriptstyle{\it{f o r}}z,\ \geq\ 0,\ {\textstyle{\frac{1}{2}}}\ -
$$
$$
\frac{z}{\sqrt{2\pi}\sigma}\leq\operatorname*{P r}_{\xi\sim N(0,1)}\big(\xi\geq\frac{z}{\sigma}\big)\leq\operatorname*{m a x}\big(\frac{1}{6},\frac{1}{2}-\frac{z}{3\sigma}\big)
$$
R₁
x 1 y 1 p 2
Fact 2. *Let B*(*x;y*) = (1 *t*) *t dt be the Beta function. Then*
0 d 1
1 d ~~p~~
*B*(;).
2 2 d
$$
B (x, y) = \int_ {0} ^ {1} (1 - t) ^ {x - 1} t ^ {y - 1} d t
$$
$$
\frac{2}{\sqrt{d-1}}\leq
$$
$$
B(\frac{1}{2},\frac{d}{2})\leq\frac{\pi}{\sqrt{d}}.
$$
1d1
Fact 3. *If d* 2*, then* (1)2*.*
d 2
$$
\textstyle\mathit{I f}d\geq2,\:\mathit{t h e n}\:\big(1-\frac{1}{d}\big)^{\frac{d}{2}}\geq\frac{1}{2}.
$$
Fact 4. *(Bernstein inequality) If i.i.d. random variables X₁;:::;X*m*satisfy*
2
*jX*i*j b,* E[*X*i] = q, and E[*X*i] *r², then with probability at least* 1*,*
Pm 2
1 2r 2 b 2
*j*i=1*X*i*j* log + log*.*
m m 32m
$$
X_{1},\ldots,X_{m}
$$
$$
|X_{i}|\,\leq\,b,\;\mathbb{E}[X_{i}]\,=\,\mu
$$
$$
\mathbb{E}[X_{i}^{2}]\;\leq\;r^{2}
$$
$$
1-\delta.
$$
$$
\textstyle|\frac{1}{m}\sum_{i=1}^{m}X_{i}-\mu|\leq\sqrt{\frac{2r^{2}}{m}\operatorname{l o g}\frac{2}{\delta}}+\frac{2b}{3m}\operatorname{l o g}\frac{2}{\delta}
$$
Fact 5. *Suppose* (*x₁;:::;x*d) *is drawn from the uniform distribution over the*
d
(1 z²) 2 3
*unit sphere, then x₁ has a density function of p*(*z*) =d 1 1*.*
B(2;2)
$$
(x_{1},\ldots,x_{d})
$$
$$
x_{1}
$$
$$
p(z)=\frac{(1-z^{2})^{\frac{d-3}{2}}}{B(\frac{d-1}{2},\frac{1}{2})}
$$
Without loss of generality, assume = (1*;* 0*;* 0*;:::;* 0).
$$
\ \mu=(1,0,0,\dots,0)
$$
Following three lemmas give concentration of *v*.
$$
\ \upsilon,
$$
(k)
Lemma 1. *For any k* = 2*;* 3*;:::;d, with probability at least* 1*, jv j*
q
2 2
2 log*.*
md
$$
k = 2, 3, \dots , d,
$$
$$
1-\delta,\ v v^{(k)}|\,\leq
$$
$$
2textstyle{\sqrt{\frac{2}{m d}}\log\frac{2}{\delta}}
$$
(k) (k) (k)
*Proof.* For *k* = 2*;* 3*;:::;d*, *Z₁;Z₂;:::;Z*mare i.i.d. random variables bounded
R 2 d 3
(k) (k) 2 (i) 2 1 2 (1 z) 2
by 1. By symmetry, E[*Z₁*] = 0. E[(*Z₁*)] = E[(*X*)] = 2 *z*d 1 1*dz* =
0 B(;)
2 2
R₁1 d d 1 3
1 B(2;2) 1
d 1*t²* (1 *t*)2 3*dt* =d=. By the Bernstein inequality, with
B(;1) 0 B(;1) d
2 2 2 1 2q q
P(k)
1 2 2 2 2 2
probability at least 1, *j Z*i*j* log + log 2 log.
m md 32m md
q
$$
k=2,3,\ldots,d,Z_{1}^{(k)},Z_{2}^{(k)},\ldots,Z_{m}^{(k)}
$$
$$
\textstyle\mathbb{E}[Z_{1}^{(k)}]=0.\ \mathbb{E}[(Z_{1}^{(k)})^{2}]=\mathbb{E}[(X^{(i)})^{2}]=2\int_{0}^{1}z^{2}\frac{(1-z^{2})^{\frac{d-3}{2}}}{B(\frac{d-1}{2},\frac{1}{3})}d z=
$$
$$
\begin{array}{l}{\frac{1}{B(\frac{d-1}{2},\frac{1}{2})}\int_{0}^{1}t^{\frac{1}{2}}(1-t)^{\frac{d-3}{2}}d t=\frac{B(\frac{d-1}{2},\frac{3}{2})}{B(\frac{d-1}{2},\frac{1}{2})}=\frac{1}{d}}\\ \end{array}
$$
$$
1\!-\!\delta,\,|\frac{1}{m}\sum Z_{i}^{(k)}|\leq\sqrt{\frac{2}{m d}\log\frac{2}{\delta}}+\frac{2}{3m}\log\frac{2}{\delta}\leq2\sqrt{\frac{2}{m d}\log\frac{2}{\delta}}.\quad\square
$$
(1) 1pd p1 1
Lemma 2. *With probability at least* 1*, v* min(1*;*) log*.*
3 d 21m
$$
1 - \delta , v ^ {(1)} \geq \frac {1}{3 \pi \sqrt {d}} \min \left(1, \frac {1}{\sigma \sqrt {d}}\right) - \sqrt {\frac {1}{2 m} \log \frac {1}{\delta}}
$$
$$
Z_{1}^{(1)},Z_{2}^{(1)},\ldots,Z_{m}^{(1)}
$$
(1) (1) (1)
*Proof. Z₁;Z₂;:::;Zm*are i.i.d. random variables bounded by 1. Their mean
can be lower-bounded as follows.
(1)
For for any 0 *a* 1, due to the noise setting, E[*Y j X* = *a*] 0 and
(1) (1) (1) (1) (1)
E[*Y j X* = *a*] 0, so E[*YX j X* = *a*] + E[*YX j X* = *a*] 0.
Consequently we have
$$
0\,\leq\,a\,\leq\,1
$$
$$
\mathbb{E}[Y\mid|\ X^{(1)}=a|\geq0
$$
$$
\mathbb {E} [ Y \mid X ^ {(1)} = - a ] \leq 0, \text {s o} \mathbb {E} [ Y X ^ {(1)} \mid X ^ {(1)} = a ] + \mathbb {E} [ Y X ^ {(1)} \mid X ^ {(1)} = - a ] \geq 0.
$$
---
$$
\begin{aligned}{\mathbb{E}[Y X^{(1)}]}&{{}\geq\mathbb{E}[Y X^{(1)}\mathbb{1}[|X^{(1)}|\geq\frac{1}{\sqrt{d}}]]}\\ {}&{{}=\mathbb{E}[\mathbb{E}[Y\mid X^{(1)}]\^{}}\\ {}&{{}\ -mathbb E Y(mid X^{(1)}\ 1mathbb\vert langle X^{(1)}|\geq\frac{1}{\sqrt{d}}]]}\\ {}&{{}=\mathbb{E}[(1-2\operatorname*{P r}[\ Y=-1\mid X^{(1)}])X^{(1)}\mathbb{1}[X^{(1)}\geq\frac{1}{\sqrt{d}}]]}\\ {}&{{}\geq(1-2\operatorname*{P r}_{\xi\sim N(0,1)}(\xi\geq\frac{1}{\sigma\sqrt{d}}))\mathbb{E}[X^{(1)}\mathbb{1}[X^{(1)}\geq\frac{1}{\sqrt{d}}]]}\\ \end{aligned}
$$
p1 1 1 1pd (1) (1)
Now, PrN(0;1)() max(*;*). Besides, E[*X* 1[*X*
d 6 2 3
d 3 d 1
12 2 (11) 2
1 z(1 z)d 1 1
*p*]] = R 1 d*dz* =dpwhere the rst
d*pd*B(;1) (d 1)B(;1) 2(d 1) pd2 d
2 1 2 2 1 2 1
(1) 1p p1
inequality follows by Fact2and3. Thus, E[*YX*] min(1*;*).
3 d d
P
$$
\operatorname*{P r}_{\xi\sim N(0,1)}(\xi{\,\geq\,}\frac{1}{\sigma\sqrt{d}}){\,\leq\,}\operatorname*{m a x}(\frac{1}{6},\frac{1}{2}-\frac{1}{3\sigma\sqrt{d}})
$$
$$
\mathbb{E}[X^{(1)}\mathbb{I}[X^{(1)}\geq
$$
$$
\begin{array}{l}{\frac{1}{\sqrt{d}}]]=\int_{\frac{1}{\sqrt{d}}}^{1}\frac{z(1-z^{2})^{\frac{d-3}{2}}}{B(\frac{d-1}{2},\frac{1}{2})}d z=\frac{(1-\frac{1}{d})^{\frac{d-1}{2}}}{(d-1)B(\frac{d-1}{2},\frac{1}{2})}\geq\frac{1}{2(d-1)\frac{w}{\sqrt{d-1}}}\geq\frac{1}{2\pi\sqrt{d}}}\\ \end{array}
$$
$$
\ \ \cdot[Y X^{(1)}]\geq\frac{1}{3\pi\sqrt{d}}\operatorname*{m i n}\bigl(1,\frac{1}{\sigma\sqrt{d}}\bigr)
$$
(1) 1 (1)
By the Cherno bound, with probability at least 1, *v* = *Z*i
qm
1*p* p1 1 1
min(1*;*) log.
3 d d 2m
$$
1-\delta,\,v^{(1)}=\frac{1}{m}\sum Z_{i}^{(1)}\geq
$$
$$
\textstyle\frac{1}{3\pi\sqrt{d}}\operatorname*{m i n}(1,\frac{1}{\sigma\sqrt{d}})-\sqrt{\frac{1}{2m}\operatorname{l o g}\frac{1}{\delta}}
$$
q
(1) p 1
Lemma 3. *With probability at least* 1*, v* + log*.*
22d 21m
$$
\begin{array}{l}{1-\delta,\:v^{(1)}\leq\frac{2}{\sqrt{2\pi}d\sigma}+\sqrt{\frac{1}{2m}\log\frac{1}{\delta}}}\\ \end{array}
$$
R₁ 2 d
(1) (1 z) 2 3
*Proof.* We rst give an upper bound of E[*YX*] = 2 *z*d 1 1(1 2 PrN(0;1)(
0 B(;)
2 2
z z p2z
))*dz*. By Fact1, 1 2 PrN(0;1)(), so we have
2
$$
\mathfrak{L}[Y X^{(1)}]=2\int_{0}^{1}z\frac{(1-z^{2})^{\frac{d-3}{2}}}{B(\frac{d-1}{2},\frac{1}{2})}(1\ -22\operatorname*{P r}_{\xi\sim N(0,1)}(\xi\geq
$$
$$
\textstyle\ {frac z sigma\}))d z}
$$
$$
\textstyle{1-2\operatorname*{P r}_{\xi\sim N(0,1)}\ \bigl(\xi\geq\frac{z}{\sigma}\bigr)\leq\frac{2z}{\sqrt{2\pi}\sigma}}
$$
$$
\begin{aligned}{\mathbb{E}[Y X^{(1)}]}&{{}\leq2\int_{0}^{1}z\frac{(1-z^{2})^{\frac{d-3}{2}}}{B(\frac{d-1}{2},\frac{1}{2})}\frac{2z}{\sqrt{2\pi}\sigma}d z}\\ {}&{{}=\frac{4}{\sqrt{2\pi}}\sigma B(\frac{d-1}{2},\frac{1}{2})\int_{0}^{1}z^{2}(1-z^{2})^{\frac{d-3}{2}}d z}\\ {}&{{}=\frac{2B(\frac{d-1}{2},\frac{3}{2})}{\sqrt{2\pi}\sigma B(\frac{d-1}{2},\frac{1}{2})}}\\ {}&{{}=\frac{1}{\sqrt{2\pi}d\sigma}}\\ \end{aligned}
$$
The conclusion follows by the Cherno bound.
Now we present the proofs for the propositions.
2 2 2 > >
*Proof.* (of Proposition1) Since *kw*^ *k* = *kw*^*k* +*k k* 2 *w*^ = 2(1 *w*^) =
(1) (1) 2
vkvk vkvk "
2(1), to prove *kw*^ *k "*, it suces to show 1. Note that
2
(1) 2 4 2
*vkvk* 2 1 " 2 2 " "
1 () =(1))2, and 1 (1) = "2, so it
(*v* 2 4 2 1+12
1+P*d* (k))2 "
k=2(1) (*v*
2
(v) 2
suces to show Pd 2with probability at least 1.
(v(*k*))2*"*
k=2
$$
\|\hat{w}-\mu\|^{2}=\|\hat{w}\|^{2}+\|\mu\|^{2}-2\mu^{\top}\hat{w}=2\,(1-\mu^{\top}\hat{w})=
$$
$$
\textstyle{2(1-\frac{v^{(1)}}{\|v\|})}
$$
$$
\|\hat{w}-\mu\|\leq\varepsilon
$$
$$
\textstyle\frac{v^{(1)}}{\|v\|}\geq1-\frac{\varepsilon^{2}}{2}
$$
$$
1 - \left(\frac {v ^ {(1)}}{\| v \|}\right) ^ {2} = \frac {1}{1 + \frac {\left(v ^ {(1)}\right) ^ {2}}{\sum_ {k = 2} ^ {d} \left(v ^ {(k)}\right) ^ {2}}}
$$
$$
1-\big(1-\frac{\varepsilon^{2}}{2}\big)^{2}=\varepsilon^{2}-\frac{\varepsilon^{4}}{4}\geq\frac{\varepsilon^{2}}{2}\geq\frac{1}{1+\frac{2}{\varepsilon^{2}}}
$$
$$
\frac{(v^{(1)})^{2}}{\sum_{k=2}^{d}(v^{(k)})^{2}}\geq\frac{2}{\varepsilon^{2}}
$$
$$
1-\delta
$$
---
Now, by Lemma1and2and a union bound, with probability at least 1,
q
$$
1-\delta,
$$
$$
\frac{(v^{(1)})^{2}}{\sum_{k=2}^{d}(v^{(k)})^{2}}\geq\frac{(\frac{1}{3\pi\sqrt{d}}\operatorname*{m i n}(1,\frac{1}{\sigma\sqrt{d}})-\sqrt{\frac{1}{2m}\operatorname{l o g}\frac{d}{\delta}})^{2}}{4(d-1)\frac{2}{m d}\operatorname{l o g}\frac{2d}{\delta}},
$$
2
2 (15) 2 2d
which is at least2for our setting of *m* =2*d*max(1*;d*^) log.
" "
$$
\frac{2}{\varepsilon^{2}}
$$
$$
m=\frac{(15\pi)^{2}}{\varepsilon^{2}}d\operatorname*{m a x}\bigl(1,d\hat{\sigma}^{2}\bigr)\log\frac{2d}{\delta}
$$
(1)
*Proof.* (of Proposition2) By Lemma2, with probability at least 1, *v* =
q
P(1)
1 1p p1 1 1 1p p1
*Z*imin(1*;*) log min(1*;*), which implies
m 3 d d 2m 12 d ^ d
(1) 1p p1
*kvk v* min(1*;*).
12 d ^ d
$$
1-\delta,\,v^{(1)}=
$$
$$
\textstyle\frac{1}{m}\sum Z_{i}^{(1)}\geq\frac{1}{3\pi\sqrt{d}}\operatorname*{m i n}(1,\frac{1}{\sigma\sqrt{d}})-\sqrt{\frac{1}{2m}\operatorname{l o g}\frac{1}{\delta}}\geq\frac{1}{12\sqrt{d}}\operatorname*{m i n}(1,\frac{1}{\bar{\sigma}\sqrt{d}})
$$
$$
\textstyle{\big\|v\big\|\geq v^{(1)}\geq\frac{1}{12\sqrt{d}}\operatorname*{m i n}(1,\frac{1}{\hat{\sigma}\sqrt{d}})}
$$
*Proof.* (of Proposition3) By Lemma1and3and a union bound, with probability at least 1,
$$
1-\delta.
$$
$$
\begin{aligned}{\left\|v\right\|^{2}}&{{}=\sum_{k=1}^{d}(v^{(k)})^{2}}\\ {}&{{}\leq4(d-1)\frac{2}{m d}\operatorname{l o g}\frac{2d}{\delta}+(\frac{2}{\sqrt{2\pi}d\sigma}+\sqrt{\frac{1}{2m}\operatorname{l o g}\frac{1}{\delta}})^{2}}\\ {}&{{}\leq\frac{1}{148d^{2}\hat{\sigma}^{2}}.}\\ \end{aligned}
$$
## A.2Noisy Labels for the Continuous Case
In the continuous, the model extraction problem becomes a regression problem.
In [19] the authors consider passive linear regression with squared loss and pro-
>
vide an algorithm that achieves nearly optimal convergence rate E[*X w*^ *Y*]
>?~C
E[*X w Y*] = *O* where the constant *C* depends on the covariance matrix
n
?
of *X* and the error of the optimal linear model *w*. In [59] the authors point out
1
that unlike in the classication case, the *O*() cannot be improved by active
n
learning, but it provides an algorithm under a stream-based querying model
(in fact, they assume the algorithm can draw *X* from any distribution, which
can be implemented by rejection sampling with stream-based querying model)
that achieves a learning rate with a better constant factor *C*. Authors in [27]
consider active learning for maximum likelihood estimation (MLE) under the
assumption that the model is well-specied (*P* (*Y jX*) is given by a model in the
model class) and that the Fisher information matrix does not depend on label
*y* (this assumption holds for linear regression and generalized linear models). It
shows that a two-stage algorithm achieves a nearly optimal convergence rate.
$$
\mathbb{E}[X^{\top}\hat{w}-Y]-
$$
$$
\mathbb{E}[X^{\top}\vec{w^{\star}-Y}]=\tilde{O}\left(\frac{C}{n}\right)
$$
$$
w^{\star}
$$
$$
O({\frac{1}{n}})
$$
$$
(P|Y|X)
$$
The main diculties of computationally ecient active learning for classication arise because of two factors: (1) how to eciently nd a classier with
the minimum classication error rate; (2) how to select examples for labeling.
For (1), it has been shown that optimizing the classication error rate (0-1 loss)
---
with noise is hard in general, and computational ecient solutions with theoretical guarantees are only known under some assumptions of the hypothesis space
and noise conditions (for example [17,40,74]). For (2), most existing active
learning algorithms maintain a candidate set of classiers either explicitly [33]
or implicitly [17,21,74], and the noise tolerance is achieved by repetitive querying as in Proposition1or a carefully designed sampling schedule to guarantee
that the candidate set is \correctly shrunk" with high probability [21,33,74].
For regression, most loss functions (for example the squared error, negative
log likelihood) are convex, and thus can be optimized eciently. The labeling
strategies in regression are also dierent: instead of maintaining candidate sets,
active regression algorithms [27,59] often rst nd a good sampling distribution
that optimize some statistics of the covariance matrix and then draw labeled
samples from this distribution. Such strategies tolerates noise naturally and
de-noising strategies like repetitive querying are not necessary.
## A.3Additional Results
## A.3.1Alternate Stopping Criterion
We investigated if measuring the model’s stability over *N* iterations results in
acceptable extraction attacks. Here, we dene model stability as the oscillation
between the approximation learned at iteration *i* and at iteration *i*+1. Formally,
stability can be dened as *S*i= *jjw*i*w*i+1*jj₂*. Our approach checks if *S*ifor
*i* = 1*;;N* and terminates execution if the condition is satised. We observe
that this approach fails for the algorithm proposed by Chen *et al.* [17], as the
approximation produced at each iteration diers greatly from the approximation
produced in the preceding iteration. The results for the algorithm proposed by
Alabdulmohsin *et al.* [3] can be found Table5.
$$
\mathcal{S}_{i}=||w_{i}-\!w_{i+1}||_{2}
$$
$$
\mathcal{S}_{i}\leq\tau
$$
$$
i=1,\cdots,N
$$
| | N=10Queries | | N=15Queries | | N=20Queries | | Baselineε=0.001 |
| --- | --- | --- | --- | --- | --- | --- | --- |
| Breast Cancer | 241 | 0.0047 | 247 | 0.0034 | 252 | 0.0031 | 300 |
| Adult Income | 117 | 0.0019 | 122 | 0.0015 | 127 | 0.0012 | 135 |
| Digits | 493 | 0.0077 | 498 | 0.0075 | 503 | 0.0073 | 700 |
| Wine | 120 | 0.0016 | 125 | 0.0014 | 130 | 0.0012 | 135 |
$$
\underline{{\mathbf{N}=}}\ 5
$$
$$
\varepsilon=0.001
$$
Table 5: Model stability results in nominal savings at the expense of a small increase in
geometric error (^*"*). The trends are the same for other values of *"*.
## A.3.2A Direction For Defense?
Recall from earlier discussion that QS active learning algorithms are capable of
generating points de novo. It is conceivable that these points are not generated
from the distribution from which the training data is sampled from. To this
end, we veried if these distributions are indeed dierent using the Hotelling’s
*T²* test, specically for the algorithms proposed by Alabdulmohsin *et al.* [3] and
Chen *et al.* [17] under the null hypothesis that the distributions are the same
(refer Table6and Table7). We observe that this QS active learning algorithm
indeed produces points that are not from the underlying natural distribution.
$$
T^{2}
$$
---
| Dataset | t-value | n-1 | p-value | Reject Null? |
| --- | --- | --- | --- | --- |
| Breast Cancer | 319.27 | 322 | 0 | √ |
| Adult Income | 467.43 | 133 | $9.64\times 10^{-216}$ | √ |
| Mushroom | 65.74 | 222 | $1.58\times 10^{-147}$ | √ |
$$
9.64\,\times\,10^{\ -216}
$$
$$
1.58\,\times\,10^{\ -147}
$$
Table 7: Results of the Hotelling *T²* test for multivariate distributions, for n samples. It
is observed that the data-points generated by the DC2algorithm do not lie in the natural
distribution underlined by samples from the training data.
$$
T^{2}
$$
$$
\mathbf{D}\mathbf{C}^{2}
$$
While discarding points that can not be sampled from the training distribution
may seem as a tempting defense strategy, it is conceivable that certain real
world tasks may query MLaaS providers with outlier points. Further analysis
is required to determine how this strategy may eectively be used to defend
against model extraction.
(a) Version Space Approximation
(b) *DC*2
$$
D C^{2}
$$
Figure 7: Distance of the instances synthesized by (a) version space approximation algorithm, and (b) dimension coupling algorithm from optimal halfspace.
| Dataset | t-value | n-1 | p-value | Reject Null? |
| --- | --- | --- | --- | --- |
| Breast Cancer | 14.24 | 198 | $3.70\times 10^{-32}$ | √ |
| Adult Income | 9.71 | 92 | $9.22\times 10^{-16}$ | √ |
| Mushroom | 22.16 | 599 | $5.92\times 10^{-80}$ | √ |
$$
3.70\,\times\,10^{\ -32}
$$
$$
9.22\,\times\,10^{\ -16}
$$
$$
5.92\,\times\,10^{\ -80}
$$
Table 6: Results of the Hotelling *T²* test for multivariate distributions, for n samples. It
is observed that the data-points generated by the version space approximation algorithm
do not lie in the natural distribution underlined by samples from the training data.
$$
T^{2}
$$