Deep Learning Algorithm Poisoning Attacks Based on Reverse Gradient Optimization

1. 01What problem does this paper attempt to solve?

   How to extend poisoning attacks from a few binary classification algorithms to multiclass problems and to be able to attack gradient-trained models such as neural networks.

   Core question: how to carry out effective training data poisoning attacks against multiclass learning algorithms (especially neural networks and deep learning architectures).

   • Problem setting: The authors point out that many online services rely on machine learning to process data collected in the wild (e.g., PDFRate allows users to give feedback on classification results), and attackers can inject malicious data to gradually corrupt the learning process; poisoning is regarded as one of the main emerging threats facing data-driven techniques.
   • Shortcomings of existing methods: The authors state that existing poisoning attacks (implicit differentiation based on KKT stationarity conditions) can only be used for a limited set of binary classification algorithms; computing and inverting the Hessian matrix has time complexity O(p³) and memory O(p²), and requires the inner learning problem to be solved exactly, which is infeasible for neural networks and deep learning architectures.
   • Core observation: back-gradient optimization (originally used for hyperparameter optimization) can compute the outer gradient by back-propagating through the sequence of parameter updates of the learning algorithm, without storing the entire training trajectory and without requiring the inner optimization to converge to a stationary point.
   • Paper contributions: The authors extend the poisoning threat model to multiclass settings (introducing the concept of error specificity), propose a poisoning algorithm based on back-gradient optimization, conduct experiments on spam filtering, malware detection and handwritten digit recognition, and also examine the transferability of poisoning samples across different learning algorithms.
   • Threat model:
     • Goal: availability corruption (increasing overall classification error) or integrity corruption; in the multiclass setting, divided into error-generic (arbitrary misclassification) and error-specific (misclassification into a specified class).
     • Knowledge: Perfect-Knowledge (PK) attackers know the training data, feature set, learning algorithm and parameters; Limited-Knowledge with Surrogate Learners (LK-SL) attackers know the training data but not the learning algorithm, and use a surrogate model to generate attacks.
     • Capability: causative influence, i.e., the ability to manipulate training data; the attacker is given an initial set of attack samples and modifies them within a constraint space Φ; labels are usually not controlled by the attacker, and constraints are needed to ensure that poisoning points are labeled with the desired label.
     • Victim systems: classifiers trained with gradient-descent-type methods, including MLP, LR, ADA and CNN in the experiments.

   Collapse this answer

2. 02What related research exists?

   Related work includes theoretical analyses of poisoning attacks, KKT-based gradient poisoning attacks, back-gradient optimization techniques, and studies of adversarial example transferability.

   Theory and early work on poisoning attacks

   • Bshouty et al. (1999), Kearns and Li (1993)—analyze the feasibility of supervised learning when an omniscient attacker corrupts the training data; the authors state that their results are overly pessimistic.
   • Kloft and Laskov (2012), Nelson et al. (2008)—the first practical poisoning attacks against spam filtering and anomaly detection; the authors state that these attacks do not easily generalize to other learning algorithms.

   Gradient poisoning attacks based on KKT conditions

   • Biggio et al. (2012)—first demonstrated the vulnerability of SVMs to poisoning attacks.
   • Xiao et al. (2015)—poison LASSO, ridge regression and elastic net.
   • Mei and Zhu (2015)—use a machine teaching unified framework to poison convex learning algorithms with Tikhonov regularization. The authors state that such methods require full retraining at each iteration to satisfy the KKT conditions, are computationally expensive, and are not applicable to deep networks trained by gradient descent.
   • Koh and Liang (2017)—use influence functions to train a surrogate LR model on deep features to generate adversarial training examples; the authors point out that this is a binary classification task and does not attack deep networks end-to-end.

   Back-gradient optimization

   • Domke (2012), Maclaurin et al. (2015), Pedregosa (2016), Bengio (2000)—reverse-gradient techniques proposed for hyperparameter optimization and energy models, which compute the outer gradient by reversing the learning process; this paper introduces them into poisoning attacks.

   Adversarial examples and transferability

   • Biggio et al. (2013), Šrndic and Laskov (2014), Papernot et al. (2017)—demonstrate the transferability of evasion attacks (adversarial test samples) across SVMs, neural networks and deep networks; the authors state that the transferability of poisoning attacks had not been studied before.

   Baselines and comparison setup: In the experiments, the authors compare error-generic attacks with random label-flip attacks (taking points from the validation set and randomly flipping their labels); in the transferability experiments, MLP, LR and ADA are used as surrogate models for one another.

   The authors' positioning: this paper is what the authors call the first attack that can poison deep neural networks end-to-end (without using a surrogate model), and the first work to systematically demonstrate the transferability of poisoning samples across algorithms.

   Collapse this answer

3. 03How does the paper address this problem?

   Model poisoning as bilevel optimization, and use back-gradient optimization to back-track the gradient descent updates to compute the outer gradient, replacing the KKT conditions.

   Overall approach: formulate the multiclass poisoning attack as a bilevel optimization problem, and replace the traditional KKT implicit differentiation with back-gradient optimization, so that the outer gradient can be computed efficiently by back-replaying the truncated learning process, thereby enabling attacks on neural networks.

   Threat model formalization

   • The attacker's goal is characterized by a triple: security violation (integrity / availability / privacy), attack specificity (targeted / indiscriminate), error specificity (specific / generic, newly added for the multiclass setting).
   • The optimal attack strategy is written as D_c^⋆ ∈ argmax_{Dc′ ∈ Φ(Dc)} A(D_c′, θ), i.e., maximizing the attack objective function A within the modification constraint space Φ.
   • Error-generic attack: A is defined as the loss L(D̂val, ŵ) on a surrogate validation set, and the inner problem is training the model on D̂tr ∪ Dc′. Error-specific attack: A = −L(D̂val′, ŵ), where the validation set labels are changed to the misclassification labels desired by the attacker.

   Simplifying assumptions

   • Consistent with prior work: only one poisoning point xc is optimized at a time; its label yc is pre-selected by the attacker and fixed during optimization.
   • The simplified problem is: max L(D̂val, ŵ), s.t. ŵ ∈ arg min L(xc′, w′).

   Traditional gradient methods and their bottleneck

   • Prior work computes ∇xc A by the chain rule, where ∂ŵ/∂xc is obtained implicitly through the KKT stationarity condition, requiring computing and inverting the Hessian ∇w²L.
   • This computation has time complexity O(p³) and memory O(p²) (p is the number of parameters), and requires the inner problem to be solved exactly; it is infeasible for deep networks.

   Back-gradient optimization

   • Core idea: replace the inner optimization with the T gradient descent iterations actually performed by the learning algorithm (Algorithm 2), compute the outer gradient by reverse-mode differentiation, and simultaneously reverse the parameter updates step by step during backpropagation (Algorithm 3), without storing the entire parameter trajectory w1,…,wT.
   • Applicability condition: the learning algorithm updates parameters in a smooth manner (e.g., fixed-step gradient descent, stochastic gradient descent with momentum).
   • The terms involving ∇xc∇wL and ∇w∇wL in the reverse update can be computed efficiently with Hessian-vector products.
   • The time complexity is O(T); the authors state that the outer gradient can be estimated accurately using an incomplete inner optimization truncated to T iterations.

   Attack algorithm procedure

   • Algorithm 1: iteratively execute—train the learning algorithm (in this paper, truncated to T iterations) → update the poisoning point along the direction of ∇xc A and map it back to the feasible set with the projection operator ΠΦ → until the change in the objective function is less than ε.
   • In the error-specific attack the outer objective is minimization, so only the update direction needs to be reversed.
   • Multiple poisoning points are handled by making multiple passes over the poisoning point set and optimizing one point at a time; line search can be used to reduce the number of training updates.

   Collapse this answer

4. 04What experiments did the paper conduct?

   Evaluates PK and LK-SL attacks, transferability, and end-to-end poisoning of a CNN on Spambase, Ransomware and MNIST.

   Experimental Setup

   • Models evaluated: MLP (one 10-neuron hidden layer, tanh activation, softmax output), LR (log-loss), ADA (mean squared error); deep network experiments use the MNIST CNN proposed by LeCun et al. (1998), requiring optimization of over 450,000 parameters.
   • Datasets: Spambase (4,601 emails, 1,813 spam emails, 54 binary features); Ransomware (530 ransomware samples, 549 benign applications, 400 binary features); MNIST (28×28=784 pixels, 10 classes).
   • Data splits: Spambase/Ransomware use 100 samples for training, 400 for validation, the rest for testing per split, averaged over 10 independent random splits; MNIST error-generic uses 1000 training, 1000 validation, 8000 test; error-specific uses 1000 training, 4000 validation, 5000 test; CNN experiments use 1000 training, 2000 validation, 2000 test, 5 splits.
   • Attack parameters: Spambase/Ransomware inject at most 20 poisoning points, T set to 200 (MLP), 100 (LR), 80 (ADA) respectively; MNIST error-generic at most 60 points, T=60; error-specific at most 40 points, T=60; CNN experiments inject 10 points, do 2 passes and use line search.
   • Baseline: random label-flip attack (take points from the validation set and randomly flip labels).
   • Metrics: test classification error rate, per-class error rate, difference in confusion matrices before and after poisoning; results are averages over multiple random splits, the paper does not report statistical significance tests.

   Main Results

   PK attack results (Figure 2, test error rate varying with the proportion of poisoning points):

   Dataset	Model	Error rate at 15% poisoning points
   Spambase	ADA	about 30%
   Spambase	LR	about 30%
   Spambase	MLP	about 25%
   Ransomware	MLP / LR / ADA	the three are similar (the paper does not give a single value)

   • The authors state that the PK attack can break all evaluated classifiers; on Spambase, MLP is more resistant to poisoning than linear classifiers, and on Ransomware, MLP is as vulnerable as ADA and LR.
   • Transferability (LK-SL, Figure 3): poisoning points generated with a linear model (ADA or LR) as the substitute model have a similar effect on another linear classifier, and a smaller but still clear effect on MLP; when MLP is the substitute model, the effect on other algorithms is much smaller. The authors state that poisoning points can transfer effectively between linear algorithms, and transfer from nonlinear to linear models is worse.

   MNIST Multi-class Attack

   • Error-generic: fewer than 6% poisoning points nearly double the LR classification error rate, and are much more effective than random label-flip; errors grow similarly across classes, but the authors point out that the digit 5 is more easily poisoned (Figure 4 top row).
   • Error-specific (goal: misclassify 8 as 3): after adding fewer than 4% poisoning points, the error rate of digit 8 rises from about 20% to about 50%; the error rate of digit 3 also rises slightly, which the authors state is not a large magnitude (Figure 4 bottom row).

   End-to-end Poisoning of Deep Networks

   • For the CNN (considering only the three classes of digits 1, 5, 6), inject 10 poisoning points (less than 1%): the authors find that the poisoning points only slightly and not significantly raise classification error, and random label-flip has essentially no effect.
   • Attacking LR under the same setting: error rate rises from 2% to 4.3% (random label-flip only rises to 2.1%). The authors state that at least in this simple scenario, deep networks appear more robust to a very small proportion of poisoning points.
   • Visualization of poisoning samples (Figures 5, 6): poisoning samples targeting the CNN are visually indistinguishable from the original images, while those targeting LR are not; the authors believe this may be related to the shape of the deep network's decision function, but do not analyze it in depth.
   • Transfer experiments: poisoning points for LR attacking the CNN are completely ineffective; poisoning points for the CNN attacking LR have an effect similar to random label-flip.

   Other Ablations and Analyses

   • Demonstration on three-class synthetic data (Figure 1): shows the decision region changes of error-generic and error-specific attacks, the validation loss surface and back-gradient direction, and verifies the effect of the logistic loss approximation with zero-one loss.

   Collapse this answer

5. 05What are some points that can be further explored?

   The authors state that they did not systematically evaluate the poisoning security of deep networks and list several future directions; the experiments cover only three datasets and four models.

   Limitations noted by the authors and future directions

   • The authors explicitly write that the main limitation is that they did not conduct a broad poisoning attack evaluation on deep networks, and thus cannot thoroughly evaluate their safety; preliminary experiments show that deep networks may be more resistant to poisoning, but a more complete and systematic analysis remains to be done (Section 6).
   • The authors plan to study more systematically in the near term the effect of back-gradient poisoning attacks on deep networks (Section 6).
   • Future direction: extend and evaluate the attack to different deep learning architectures and non-parametric models (Section 6).
   • Future direction: study whether poisoning samples against deep networks have universal perturbations that do not depend on the initial attack point (similar to universal adversarial perturbations) (Section 6).
   • Future direction: evaluate defense mechanisms against poisoning attacks through data cleaning and robust learning algorithms (Section 6).
   • The authors leave a more detailed analysis of the phenomenon that CNN poisoning samples are visually indistinguishable to future work (Section 4.2).

   Scope of experimental coverage

   • The models tested are MLP, LR, ADA and one MNIST CNN, 4 in total; the CNN experiments cover only the three classes of digits 1, 5, 6.
   • The datasets are Spambase, Ransomware, MNIST, three in total; Spambase/Ransomware use only 100 training samples per split.
   • Defense evaluation was not conducted; the only comparison attack is random label-flip.
   • The CNN experiments inject only 10 poisoning points (less than 1%), repeated over 5 random splits; the paper does not report statistical significance tests.
   • The paper does not report measured data on attack runtime or computational cost, and only gives an O(T) complexity analysis.

   Collapse this answer

6. 06Summarize the main content of the paper

   Proposes a multiclass poisoning attack based on back-gradient optimization that can attack neural networks, and demonstrates the attack's effectiveness and transferability.

   A paper on training data poisoning attacks, aiming to extend poisoning attacks from a few binary convex algorithms to multiclass problems and neural networks.

   • Problem: Existing poisoning attacks based on KKT conditions require inverting the Hessian (O(p³) time) and require the inner learning problem to converge exactly, so they cannot be used for neural networks; moreover, they only consider binary classification.
   • Method: The authors extend the threat model to multiclass settings (adding the error specificity dimension) and use back-gradient optimization to compute the outer gradient—back-propagating through the sequence of gradient descent updates truncated to T iterations, with complexity O(T), without requiring the inner problem to converge to a stationary point.
   • Result one: On Spambase, a PK attacker controlling 15% of the training data raises the classification error rate of ADA and LR to about 30%, and of MLP to about 25% (Figure 2).
   • Result two: On MNIST, the error-generic attack uses fewer than 6% poisoning points to nearly double the LR error rate; the error-specific attack uses fewer than 4% poisoning points to raise the error rate for digit 8 from about 20% to about 50% (Figure 4).
   • Result three: End-to-end poisoning of CNN (10 points, three-class MNIST) only slightly raises the error rate, and not significantly; under the same setting, the LR error rate rises from 2% to 4.3%; the authors state that deep networks may be more robust to a small proportion of poisoning.
   • Result four: Poisoning samples transfer effectively between linear algorithms, transfer poorly from nonlinear to linear models; bidirectional transfer between LR and CNN is essentially ineffective.
   • Authors' conclusion: The authors state that this is the first attack that can poison deep networks end-to-end, and plan to systematically evaluate the poisoning security of deep networks and study universal perturbations and defense mechanisms in the future.

   Collapse this answer

Related papers