PaperlayerView exact revision on arXiv

Source-linked AI summary

Exploring Connections Between Active Learning and Model Extraction

Varun Chandrasekaran, Kamalika Chaudhuri, Irene Giacomelli, Somesh Jha, Songbai Yan

arXiv:1811.02054v6cs.LGcs.CRstat.ML

TL;DR

MLaaS protects proprietary models through black-box query access, but users may still extract them. This paper formalizes extraction through its connection to query-synthesis active learning and evaluates resulting attacks and defenses. The study reports substantial query-complexity improvements for kernel SVM extraction, decision-tree extraction without auxiliary information, and failures of query-synthesis attacks against tailored randomization.

  • Problem

    MLaaS systems expose privacy-sensitive or commercially valuable models through query interfaces, while model extraction lacks formalization needed to design secure systems.

  • Method

    The paper formalizes black-box model extraction as a bounded-query experiment and maps query-synthesis active-learning algorithms onto extraction attacks.

  • Results

    EAT improves kernel-SVM query complexity by 5×-224×, IWAL extracts decision trees with a 14× query-complexity increase, and query-synthesis attacks fail against tailored randomization while passive learning remains effective.

  • Takeaways & Limitations

    Active-learning results can be used to study MLaaS extraction security, including both efficient attacks and defenses that change which learning strategies succeed.

  • Takeaways & Limitations

    The analysis is constrained by active-learning limitations, including difficulty analyzing complex hypothesis spaces such as deep neural networks and dependence on target hypotheses or bootstrap data.

Abstract

from arXiv · show

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 efficacy of model extraction attacks is paramount to designing secure MLaaS systems. To that end, we take the first step by (a) formalizing model extraction and discussing possible defense strategies, and (b) drawing parallels between model extraction and 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.

1 Introduction

MLaaS reduces the storage and computation burden of machine learning while exposing trained models through query interfaces, creating privacy and security risks. The paper formalizes model extraction, connects it to active learning, and investigates attacks and defenses.

  • 1 Introduction: MLaaS providers support model training and expose trained models through user query interfaces, often using pay-per-query pricing.The server or model owner can charge users for model queries.
  • 1 Introduction: Black-box oracle access balances model privacy and usability, but models may leak training information or have commercial and security value.Examples include spam filters and fraud-detection systems.
  • 1 Introduction: Model extraction attacks use the MLaaS interface to learn a proprietary model or a good approximation of it.Prior work demonstrated feasible attacks, particularly against interfaces revealing auxiliary information such as confidence values.
  • 1 Introduction: The paper formalizes model extraction and draws a parallel with active learning, where a learner repeatedly queries an oracle for labels.Because the learner can choose queried instances, active learning may require fewer labeled points than standard supervised learning.
  • 1 Introduction: Query synthesis active learning best matches extraction because an attacker can generate arbitrary query instances rather than sampling from the input distribution.The paper uses this connection to study attacks and possible defenses.

2 Machine Learning

The paper contrasts passive learning from fixed labeled data with interactive active learning, emphasizing that adaptive query selection can reduce labeling requirements. It focuses on query synthesis, where learners generate arbitrary instances and use query strategies to narrow the hypothesis space.

  • 2.1 Passive Learning: Passive PAC learning uses i.i.d. labeled data from an underlying distribution to produce a low-error hypothesis.The framework allows approximation within ε of the best hypothesis in the class with probability at least 1 −δ.
  • 2.2 Active Learning: Adaptive selection can reduce sample complexity because active learners choose informative data instead of learning from a static dataset.The paper motivates active learning by the potentially prohibitive labeling effort of passive learning.
  • 2.2 Active Learning: Active learning is an iterative interaction in which a learner chooses an instance, receives its oracle label, and uses the result to select subsequent queries.The learner eventually outputs a predictor for labels.
  • 2.2 Active Learning: PAC active learning samples instances from the data distribution, whereas query synthesis generates query instances de novo.Query synthesis is also called membership query learning.
  • 2.2 Active Learning: For halfspaces under suitable distributional assumptions, active-learning sample complexity can be lower than passive learning, with a representative bound of ˜O(d log(1/ε)).The comparison concerns binary classification by d-dimensional halfspaces.
  • 2.2 Active Learning: Active-learning systems evaluate query usefulness, update the possible hypothesis set, and stop when the remaining hypotheses are sufficiently constrained.The paper proposes an active-learning-system definition oriented toward model extraction.

3 Model Extraction

The paper defines extraction as learning a proprietary model through bounded black-box queries and shows that query-synthesis active-learning algorithms directly yield extraction attacks. Examples cover linear, tree, and nonlinear models, while experiments also identify defense limitations.

  • 3.1 Model Extraction Definition: Model extraction lets an adversary use a query interface to recover model parameters or obtain an approximation usable for the original task.The adversary knows the public hypothesis class but not the proprietary model’s internal representation.
  • 3.1 Model Extraction Definition: An extraction experiment gives an adversary at most q queries and declares success when its output has error at most ε against the server’s model.An extraction attack additionally specifies a confidence γ for this success.
  • 3.1 Model Extraction Definition: A linear-regression equation-solving attack uses d+1 linearly independent queries to recover the model exactly, achieving 0-extraction with complexity d+1 and confidence 1.The queried labels form a solvable linear system for the model parameters.
  • 3.2 Active Learning and Extraction: Any query-synthesis active-learning algorithm with query complexity qL(ε, δ) yields an ε-extraction attack with the same complexity and confidence 1 −δ.The adversary runs the learner’s query strategy and stopping rule against the proprietary model.
  • 3.2 Active Learning and Extraction: Query-synthesis methods provide polynomial-query extraction results for halfspaces and decision trees, including settings without auxiliary information.The paper frames these results as direct uses of active-learning techniques against MLaaS models.

4 Non-linear Classifiers

The paper adapts active-learning strategies to extract non-linear classifiers through oracle queries. It develops extended adaptive training for kernel SVMs and importance-weighted active learning for decision trees and random forests.

  • Kernel SVMs: Kernel SVM extraction combines Tramèr et al.’s adaptive retraining with active selection strategies for kernel SVMs.The approach targets non-linear kernels, including RBF and Laplace kernels.
  • Decision Trees and Random Forests: For decision trees and random forests, the extraction algorithm is based on importance-weighted active learning.The method constructs alternative hypotheses that disagree with the current prediction and selects updates using accumulated error.
  • Kernel SVMs: Extended Adaptive Training iteratively generates labeled instances using the current model and retrains until the query budget is exhausted.Ideally, generated instances are those where the current model is least confident or nearest the decision boundary.
  • Kernel SVMs: Each EAT iteration adds one labeled sample by ranking random points according to their SVM pre-sign predictions.This strategy differs from Tramèr et al.’s line search, which may require several queries per binary-search step.
  • Decision Trees and Random Forests: For random forests, the method approximates a forest whose prediction is flipped by selecting trees whose changes minimize error on previously queried data.The approximation randomly samples candidate subsets of trees and retains the lowest-error choice.

5 Defense Strategies

The paper models defenses as randomized perturbations of oracle answers and proves that uniformly reliable noise does not prevent extraction. It therefore motivates data-dependent perturbation, while noting important scope limitations.

  • Defense framework: Model extraction through oracle access is equivalent to query-synthesis active learning, so advances in that field create corresponding MLaaS threats.The defense analysis treats server responses as randomized answers to adversarial queries.
  • Classification case: If a defense answers correctly with probability at least 1/2 + c for every instance, repeated queries and majority voting can recover labels with only logarithmic query overhead.Proposition 1 gives complexity q = 8(1−2ρ_D(f*) )^-2 q(ε, δ) ln q(ε, δ) for confidence 1−2δ.
  • Data-independent randomization: Data-independent randomization cannot secure an extractable hypothesis class: noise below 1/2 remains breakable, whereas noise at least 1/2 makes the server useless.The conclusion follows from Proposition 1 and the resulting incorrect-label probability.
  • Related active-learning bounds: For halfspaces, query-synthesis active learning supports ε-extraction with complexity O(d log(1/ε)), while noisy active-learning results provide related label-complexity guarantees.The paper cites AVERAGE, modified Perceptron, and Chen et al.’s query-synthesis algorithm under different noise models.
  • Data-dependent randomization: Data-dependent perturbation is proposed because its error probability can vary with both the queried instance and the target labeling function.When some instances have error probability at least 1/2, the uniform-noise majority-vote argument no longer applies.
  • Scope limitation: The continuous case is not straightforward because Proposition 1 does not directly generalize when the target model is real-valued.The paper refers to a separate appendix discussion for continuous-valued functions.

6 Implementation and Evaluation

The evaluation shows that query-synthesis active learning can extract linear models with limited query and runtime costs, including under independent label noise, while tailored model randomization defeats these methods but not passive learning. Experiments also extend the approach to kernel SVMs and decision trees, improving query efficiency or maintaining comparable accuracy relative to prior attacks.

  • Linear Models: Query-synthesis active learning efficiently extracts halfspaces with low query complexity and runtime.The largest evaluated dimensionality required 900 queries for geometric error ε ≤10^-4, costing $0.09; the version-space algorithm converged in under two minutes.
  • Linear Models: 36546 queries ($3.65) extracted the d = 64 digits halfspace at ε ≤10^-4 when labels were independently flipped with probability ρ = 0.4.The authors characterize this as a moderate query-complexity increase for low noise values.
  • Linear Models: Tailored model randomization defeats state-of-the-art query-synthesis algorithms, whereas passive learning remains effective in that setting.The defense therefore creates a trade-off in which preventing extraction may require sacrificing accuracy.
  • Linear Models: Query-synthesis extraction uses only sign(⟨w∗, x⟩), unlike equation-solving attacks that require the prediction value ⟨w∗, x⟩.This demonstrates extraction without auxiliary confidence or prediction information from the MLaaS server.
  • Linear Models: The dimension coupling algorithm successfully extracts halfspaces across noise rates, with query complexity increasing multiplicatively as the noise threshold ρ rises.For the reported experiments, the price increase was approximately 40×, but the worst-case expenditure was approximately $3.6 and convergence took 1–20 minutes.
  • Linear Models: The dimension-coupling attack synthesizes points whose average disagreement probability is approximately 1/2 ± γ, limiting majority voting and vanilla dimension coupling against data-dependent noise.The authors attribute this behavior to synthesized instances being close to the optimal halfspace.
  • Linear Models: The Lowd–Meek baseline requires more queries than the implemented query-synthesis algorithms and operates only in a noise-free setting.On the breast-cancer dataset, the version-space method reached ε ≤10^-4 with 400 queries, costing $0.04.
  • Non-Linear Models: For non-linear models, extended adaptive training improves kernel-SVM query complexity by 5×–224×, while IWAL extracts decision trees with a nominal 14× query increase.Kernel-SVM extraction achieved comparable test accuracy, and decision-tree extraction achieved comparable test error to the oracle despite using uniformly random initialization without auxiliary information.

7 Discussion

The discussion broadens the attack setting beyond de novo query synthesis, relates model extraction to active-learning assumptions, and identifies theoretical and practical limitations. It also highlights uncertainty for complex and mismatched hypothesis classes.

  • The operational setting assumes an adversary can synthesize data points de novo and obtain model responses through oracle access.
  • Relaxing this assumption enables alternative attacks based on prior training-data access or knowledge of the data distribution.
  • Complex Models: Query-synthesis active learning is difficult to analyze for complex models because each query changes the learner’s possible hypothesis set.
  • Model Transferability: Model transferability considers an oracle that predicts with a different hypothesis class from the one the adversary attempts to learn.
  • Limitations: For some hypothesis classes, active-learning query complexity can be as high as in passive learning, while some query-synthesis methods require labeled data to bootstrap.
  • Limitations: Randomly generating bootstrap labels may harm performance, and geometric error between halfspaces may not correlate directly with generalization error.

8 Related Work

The related-work discussion situates model extraction among broader attacks against machine-learning systems, including causative attacks before training and evasion attacks after training.

  • Causative attacks manipulate training data, rewards, or sampling so the learned classifier performs erroneously at test time.
  • Evasion attacks supply tailored inputs after training to induce erroneous outputs while often preserving the original inputs’ semantics.

9 Conclusions

The paper formalizes model extraction for prediction-only MLaaS interfaces and connects it to query-synthesis active learning. It demonstrates efficient halfspace attacks and identifies data-dependent randomization as a promising defense direction.

  • The paper formalizes model extraction when MLaaS servers return only prediction values through an oracle-access interface.
  • It studies the relation between model extraction and query-synthesis active learning.
  • The resulting approach implements efficient attacks against halfspace models for binary classification.
  • The authors suggest extending extraction via active learning to multiclass and nonlinear models, including deep neural networks and random forests.
  • Data-dependent randomization, including model randomization, is identified as the most promising direction for effective defenses.

A.1.1 Proof of Proposition 1

The proof constructs an adversary that generates active-learning queries, repeats each oracle query, uses majority labels, and learns an extracted hypothesis from the resulting labeled points.

  • The adversary uses the learner’s query strategy to generate each instance x_i.
  • It queries each x_i repeatedly and assigns the most frequent returned label as y_i.
  • After collecting q(ε,δ) labeled points, the adversary learns an estimated hypothesis from the pairs {(x_i, y_i)}.
  • The proof models answer correctness with binary variables and applies a Chernoff bound because the expected number of correct answers exceeds r/2.
  • The construction yields score 1−2δ with total query complexity q = 8/(1−2ρ_D(f∗))^2 · q(ε,δ) ln(q(ε,δ)/δ).

A.1.2 Proof of Algorithm 1

Algorithm 1 estimates the ground-truth direction from noisy labeled queries, using concentration bounds to establish accuracy and failure guarantees under noise-bound assumptions.

  • Algorithm setup: The learner queries x ∈ R^d, receives y = sign(⟨w, x⟩) for w drawn from N(µ, σ^2I), and estimates µ with a vector ŵ.The objective is to make ∥µ − ŵ∥ small.
  • Theoretical guarantees: Proposition 1 guarantees ∥ŵ − µ∥ ≤ ε with probability at least 1 − δ when σ ≤ σ̂.The guarantee depends on the estimated noise upper bound being valid.
  • Theoretical guarantees: Proposition 3 guarantees that the algorithm declares failure when the estimated upper bound is too small, specifically when σ̂ ≤ 1/20σ.The average query-label vector also provides an indicator of the noise level.
  • Proof strategy: The proofs analyze coordinate-wise concentration of Zi = YiXi and combine the resulting bounds using union bounds and concentration inequalities.The vector average points toward µ because perpendicular projections are symmetrically distributed around zero.

A.2 Noisy Labels for the Continuous Case

The continuous model-extraction problem is connected to regression and active learning, whose query strategies can be effective but may generate atypical points and resist stability-based defenses.

  • Continuous-case connections: In the continuous setting, model extraction becomes a regression problem, with prior work studying passive linear regression and active-learning convergence rates.The cited work distinguishes convergence-rate improvements from improvements only in constant factors.
  • Active-learning challenges: Computationally efficient noisy active learning must address both classifier optimization and informative example selection.Known guarantees generally require assumptions about the hypothesis space or noise conditions.
  • Defense evaluation: Model-stability monitoring fails against the algorithm proposed by Chen et al. [17].The defense checks whether successive approximations differ by at most a threshold τ, then terminates.
  • Distribution-based defense: Hotelling’s T 2 tests indicate that points generated by version-space approximation and DC2 do not lie in the natural training-data distribution.The table caption explicitly reports this result for DC2.
  • Distribution-based defense: Discarding points outside the training distribution is not established as a reliable defense because real-world users may legitimately query with outliers.The paper calls for further analysis of this strategy.
Loading 1811.02054v6…