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

¹ University of Wisconsin-Madison ² Protocol Labs ³ 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.

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 min_{f 2F}Err_D(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), min_{f 2F}Err_D(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_w2 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 = P_{d i=1}a_ib_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 ~(₁ 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 dlog()) [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 achieved 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.

² ~(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 f0*;* 1g to f0*;* 1g, 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 f0*;* 1g. Receⁿt 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_w2F_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 1}have 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 ⁽¹ + e⁾ 0*:* 5 ^and 1 otherwise, Pd with a(x) = a₀ +_i=1a_ix[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ⁱas 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*!* Yg, 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 ^" Exp_F(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, X^d

$$ \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ⁱ_=1;:::;d+1is linearly inded+1 pen^dent 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ⁱ. Assume i that f_ais the function known by the MLaaS server (i.e., y_i= f_a(x)). It ⁱs 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 f0*;* 1g aⁿd range f1*;* 1g. The reader can think of 1 as 0 and +1 as 1. Using the range of f1*;+1g* 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_vf1*;;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_i2f0*;* 1g 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 of_i2Lb_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;BTF^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 Pr_xf0;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 : f0*;* 1*;:::;k* 1g! f 1*;+1g* 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^w2F^d;HSsuch that kw w k₂ " with approximately 2dlog() queries, " where f_w2F_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(dlog()) 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) $$

³A 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

⁴we 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 1}be 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 1}is 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 1}and 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 1}the sequence x₁;;x_{i 1}. After having processed the sequence X_{1: i 1}, a coin is ipped with probability p_i2 [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 Gn(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) = +, a_nd 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_rg 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 Yfl_jgg 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 = f1*;* 1g. 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 RF1;;RFo. 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_nRF_n(x_n) = +1 (the case when the label is 1 is symmetric) and there +1 are r trees in RFⁿ(denoted by RFⁿ(xⁿ)) such that their labels on xⁿare +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ⁿwill be ipped to 1. This is the intuition we use to compute ₀ r RF_n. There a_re 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 app_roximately r, but we can j +1 be approximate by randomly picking j trees out of RFⁿ(xⁿ), 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 F1,\cdots,R Fo $$

$$ 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_dg 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ⁿ;Yⁿ)g, the ERM Pn ^ = arg min1 algorithm outputs f_{f 2F i=1}1[f (X_i) 6= Y_i]. Then, the adversary n ^ with excess error ~(+" can learn f " (i.e., + ") with O₂d) examples. For " any algorithm, there is a distribution such that the algorithm needs at least ~_+" (₂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 function_D(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 ¹

• 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 =₂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 ² 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. ₂

$$ \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(dlog()) using QS active learning for the class F^d;HSi.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 ¹ (), the AVERAGE algorithm (similar to our Algorithm1, dened in 2 2 (d 1 Section6) "-extracts f with O2log) 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₂log₎ 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 lnq(;)). 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 probability_D(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 that_D(f;x) c ₂ 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) $$

⁵ 1~ Intuitively, in the binary case if^D(f;xⁱ) then the denition of yⁱperformed 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ⁱis 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(dlog). _" 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(dlog). _"

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] = < ¹ (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(₂) _{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(₂). 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;xii). Thus, this approach can be thought of as ipping the sign of the prediction output with probability_D(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 of_D(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₁;xii);;y_n, and (b) obtaining the percentage of the prediction outputs that is not equal to sign(hw ;xii). 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 of^D(w ;xⁱ) for ² 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: average_D(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 boun_d ^, target error " d 2 (15) 2 2d ^2: m²dmax(1*;d*^) log, l " ^{121d^} d 1 3: Draw x₁;x₂;:::;x_m2 S uniformly at random, and query their labels y₁;y₂;:::;ym P_m ^4: v_i=1yⁱxⁱ 5: if kvk l then v 6: Return w = _k^vk 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₂max(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=1y_ix_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(²dmax(¹;^d^) log). This explains the increase in query complexity as " Cd a function of d and ". The large value of₂dominates 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 " ₁0 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 ⁴00 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(dlog()), where a = min_{i=1;;d kw}(wⁱis the i-th coordinate of the a" k 1 groundtruth classier w). This is worse than the O(dlog()) 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

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 DC²algorithm [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

⁶such a local model is seeded with uniformly random points labeled by the oracle

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.

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_tH. 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}) $$

⁷A 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~ quer_ies 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} $$

P_r to the j-th query of x_iis correct and X_i=_j=1X_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(1_D(f;x_i)) *> r=*2 and the Cherno bound can be applied on each term in 1 2 ( D (f) ₂) r² the right-hand side. In particular, we have that Pr[fX_ir=2g] 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 =²ln we have Pr[Exp_F(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 (^). ²⁰

$$ \left(\sigma\leq\hat{\sigma}\right) $$

$$ \mu, $$

$$ \textstyle\left(\hat{\sigma}\leq\frac{1}{20}\sigma\right) $$

Intuitively, the average of y_ix_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 = 1g. For any d (i) vector X 2 R*, denote by X the i-th coordinate of X. Dene Z*_i= Y_iX_ifor 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) = Pr_N(0;1)(). Moreover, for z 0*,* kxk ₂ 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) = (¹ t) t dt be the Beta function. Then 0 d 1 1 d p B(;). ² 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* (¹)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_msatisfy 2 jX_ij b, E[X_i] = q, and E[Xⁱ] r², then with probability at least 1*,* P_m 2 1 2r 2 b 2 j_i=1X_ij log + log*.* _m m 3₂m

$$ 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 ₁. _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₎] = ₂ z_{d 1 1}dz = 0 B(;) 2 2 R₁₁ d d 1 3 1 B(2;2) 1 d 1t² (1 t_{)2 3}dt =_d=. _By the Bernstein inequality, with B(;1) 0 B(;1) d 2 2 2 _{1 2}q q P₍k) _{1 2} 2 2 2 2 probability at least ₁, j Z_ij log + log ₂ log. m _md 3₂m 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(¹;) log*.* 3 d 2¹m

$$ 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₂;:::;Zmare 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, Pr_N(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 ¹ p]] = R ^{1 d}dz =^dpwhere the rst dpdB(;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(¹;). 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 = Zi qm ₁p p1 1 ¹ min(¹;) 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*.* ₂₂d 2¹m

$$ \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 Pr_N⁽0_;1)( 0 B(;) 2 2 z z p2_z ))dz. By Fact1, 1 2 Pr_N(0;1)(), so we have ²

$$ \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 ² 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+Pd (k))2 " k=2(1) (v 2 (v) 2 suces to show P_{d 2}with 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 least²for our setting of m =₂dmax(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 1p p1 1 1 1p _p1 Z_imin(₁;) log _min(₁;), which implies m 3 d d 2m 12 d ^ d (1) 1p p1 kvk v min(¹;). 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() caⁿnot 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_iw_i+1jj₂. 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 $$

$$ \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} $$

$$ 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 DC²algorithm 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²

$$ D C^{2} $$

Figure 7: Distance of the instances synthesized by (a) version space approximation algorithm, and (b) dimension coupling algorithm from optimal halfspace.

$$ 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} $$