In many applications, Machine Learning (ML) systems rely on data collected from untrusted data sources, such as humans, machines, sensors, or IoT devices that can be compromised and manipulated. Malicious data from these compromised sources can then be used to poison the learning algorithms themselves. In other applications, the labelling of the training datasets is done manually and crowdsourcing techniques are used to aggregate the labelling information from a set of human annotators. In these cases, crowdturfing attacks are possible where malicious annotators collude to deceive the crowdsourcing algorithm by manipulating some of the labels of the annotated examples [41]. All these scenarios expose ML algorithms to poisoning attacks, where adversaries manipulate a fraction of the training data to subvert the learning process, either to decrease its overall performance or to produce a particular kind of error in the system [2, 16, 25]. Poisoning attacks can also facilitate subsequent evasion attacks or produce backdoor (or Trojan) attacks [15, 21].

Several systematic poisoning attacks have already been proposed to analyse different families of ML algorithms under worst-case scenarios, including Support Vector Machines (SVMs) [4], other linear classifiers [38, 23, 19], and neural networks [18, 24]. These attack strategies are formulated as a bilevel optimisation problem, i.e. an optimisation problem that depends on another optimisation problem. In these cases, the attacker typically aims to maximise some arbitrary malicious objective (e.g. to maximise the error for a set of target points) by manipulating a fraction of the training data. At the same time, the defender aims to optimise a different objective function to learn the model’s parameters, typically by minimising some loss function evaluated on the poisoned training set.

Some of the previous attacks target algorithms that have hyperparameters, but consider them constant regardless of the fraction of poisoning points injected in the training dataset. This can provide a misleading analysis of the robustness of the algorithms against such attacks, as the value of the hyperparameters can change depending on the type and strength of the attack. For example, Xiao et al. [38] presented a poisoning attack against embedded feature selection methods, including , and elastic-net regularisation. Their experimental results show that the attacker can completely control the selection of the features to significantly increase the overall test error of linear classifiers. However, they assume a constant regularisation hyperparameter regardless of the attack scenario considered. As shown in this paper, this approach can provide overly pessimistic results on the ML algorithms’ robustness to poisoning attacks, as the value of the regularisation hyperparameters significantly changes (if they are optimised) when malicious points are injected in the training set.

In this paper we propose a novel and more general poisoning attack formulation to test worst-case scenarios against ML algorithms that contain hyperparameters. For this, we model the attack as a multiobjective bilevel optimisation problem, where the outer objective includes both the learning of the poisoning points and the hyperparameters of the model, whereas the inner problem involves the learning of the model’s parameters. In a worst-case scenario, where the attacker is aware of the dataset used to learn the model’s hyperparameters and aims to maximise the overall error, the outer objective can be modelled as a minimax problem. We applied our proposed attack formulation to test the robustness of ML classifiers that use regularisation. We used hypergradient (i.e. the gradient in the outer problem [22, 10, 11]) descent/ascent to solve the proposed multiobjective bilevel optimisation problem. As the computation of the exact hypergradients can be very expensive, especially for neural networks, we used Reverse-Mode Differentiation (RMD) [8, 22, 24, 11] to approximate the aforementioned hypergradients. Our experimental evaluation shows that, contrary to the results reported in [38], regularisation helps as a mechanism to partially mitigate the effect of poisoning attacks. This is not surprising, as regularisation is known to increase the stability of the learning algorithm, and thus, can hinder the ability of the attacker to poison the target algorithm. We show that the value of the regularisation hyperparameter increases with the strength of the attack. In other words, the algorithm automatically tries to compensate the negative effect of the poisoning points by increasing the strength of the regularisation term. Our proposed attack formulation allows us to appropriately evaluate the robustness of regularisation in worst-case scenarios.

The first poisoning attacks reported in the literature targeted specific applications, such as spam filtering [27, 2] or anomaly detection [3, 17]. A more systematic approach was introduced in [4] to poison SVMs, modelling the attack as a bilevel optimisation problem. Subsequent works extended this approach to other families of ML algorithms, including linear and other convex classifiers [23] or embedded feature selection methods [38]. A more general approach was introduced in [24] formulating different optimal attack strategies for targeting multiclass classifiers. The authors also proposed an algorithm to estimate the hypergradients in the corresponding bilevel optimisation problem through RMD, which significantly improves the scalability of optimal attacks, allowing to poison a broader range of learning algorithms, including neural networks. The authors in [19] proposed an algorithm for solving bilevel optimisation problems with detectability constraints, allowing to craft poisoning points that can bypass outlier detectors. However, the algorithm is computationally demanding, which limits its applicability in many practical scenarios.

Other approaches have also been proposed for crafting poisoning attacks: Koh et al. [18] created adversarial training examples by exploiting influence functions. This approach allows to craft successful targeted attacks by injecting small perturbations to genuine data points in the training set. Shafahi et al. [34] proposed a targeted attack for situations where the adversary does not control the labels for the poisoning points. A Generative Adversarial Net-based model to craft poisoning attacks at scale against deep networks was proposed in [26]. This approach allows to model naturally detectability constraints for the attacker, enabling attacks with different levels of aggressiveness.

On the defender’s side, it is possible to mitigate poisoning attacks by analysing the samples that can have a negative impact on the target algorithms [27]. However, this approach can be impractical in many applications, as it offers a poor scalability. Similarly, in [18], the use of influence functions is proposed as a mechanism to detect poisoning points. Different outlier detection schemes have proved to be effective to mitigate poisoning attacks in cases where the attacker does not model appropriate detectability constraints [36, 28]. Label sanitisation has also been proposed as a mechanism to identify and relabel suspicious training points [29, 42]. However, this strategy can fail in attacks where the poisoning points collude [26]. Finally, Diakonikolas et al. [7] proposed a robust meta-algorithm, based on Singular Value Decomposition, capable of mitigating some poisoning attacks.

In data poisoning attacks the attacker can tamper with a fraction of the training data points to manipulate the behaviour of the learning algorithm [3, 2]. We assume that the attacker can manipulate all the features and the label of the injected poisoning points, provided that the resulting points are within a feasible domain of valid data points. We consider white-box attacks with perfect knowledge, i.e. the attacker knows everything about the target system, including the training data, the feature representation, the loss function, the ML model, and the defence (if applicable) used by the victim. Although unrealistic in most cases, these assumptions for the adversary allow us to analyse the robustness of the ML algorithms in worst-case scenarios for attacks with different strength.

3.1 Problem Formulation

In line with most literature on poisoning attacks we consider ML classifiers. Then, in a classification task, given the input space and the label space, Y, the learner aims to estimate the mapping . Given a training set with IID samples drawn from the underlying probability distribution p(X, Y), we can estimate f with a model M trained by minimising an objective function w.r.t. its parameters1, w , given a set of hyperparameters

We assume that the defender has access to a small validation dataset with trusted data points. In practical settings it is not uncommon to have access to a limited clean dataset, e.g. because the integrity of a small set of data sources can be ascertained or because the system is re-calibrated at specific points in time. This small clean dataset is held out for hyperparameter optimisation. Then, as proposed in [9], the model’s hyperparameters can be learned by solving the following bilevel optimisation problem:

where represent the feasible domain set for the hyperparameters . On the other side, in a poisoning attack, the adversary aims to inject a set of malicious data points, in the training dataset to maximise some arbitrary objective, A, evaluated on a set of target data points . As described in [24] different attack scenarios can be considered depending on both the set of target data points and the attacker’s objective, including indiscriminate and targeted attacks. In these settings, we propose to formulate the problem for the attacker as the multiobjective bilevel optimisation problem:

Previous work in the research literature have neglected the effect of the hyperparameters in the problem for the attacker, e.g. the regularisation hyperparameter for the cost function for SVMs [4] or for embedded feature selection methods [38]. From the general formulation we propose in (2) it

Figure 1: Effect of regularisation on a synthetic example. The blue and green points represent the training data points for each class, and the red point is the poisoning point (labelled as green). The dashed-dotted grey box represent the attacker’s constraints. Dashed-white lines and solid-red lines depict the decision boundaries for LR classifiers trained on clean and poisoned datasets respectively. (Left) Standard LR with no regularisation. (Centre) LR with regularisation. The colour-maps in the two plots represent the validation error as a function of the poisoning point. (Right) Value of learned by solving (1) as a function of the injected poisoning point.

is clear that the poisoning points in have an effect not only on the parameters of the classifier, but also on its hyperparameters. Then, testing the robustness of the learning algorithms with attacks that ignore this effect can produce misleading results, as we show, for example, in the synthetic experiment in Fig. 1 for the case of regularisation. By ignoring the effect on the hyperparameters, these attacks overestimate the adversary’s capabilities to influence the learning algorithm.

Our novel attack formulation in (2) allows to model a wide variety of attack scenarios, depending on the attacker’s objective and the combinations between the target, validation and training data points. In the remainder of the paper we will focus on analysing worst-case scenarios for indiscriminate poisoning attacks, i.e. those where the attacker—which has perfect knowledge—aims to increase the overall classification error in the target system. To achieve such a goal, the attacker aims to maximise the loss evaluated on the defender’s validation set, i.e. . Then, the problem for the attacker can also be formulated as a bilevel optimisation problem where the outer objective is a minimax problem:

None of previous approaches described in the research literature have modelled attacks as multiobjec- tive bilevel optimisation problems as in (2) and (3). Beyond the scope of our paper, our approach can also be useful to test the robustness of defensive algorithms to data poisoning in worst-case scenarios when those algorithms contain hyperparameters.

3.2 Solving General Optimal Poisoning Attacks

Solving the multiobjective bilevel optimisation problems in (2) and (3) is strongly NP-Hard [1] and, even if the inner problem is convex, the bilevel problem is, in general, non-convex. However, it is possible to use gradient-based approaches to get (possibly) suboptimal solutions, i.e. finding local optima for the problem in (2) and saddle points for the minimax problem in (3). For the sake of clarity, in the remainder we will focus on the solution for the problem (3), as we shall use it in our experiments to show the robustness of regularisation to indiscriminate poisoning attacks. The solution of (2) follows a similar procedure.

To compute the hypergradients for the outer objective, we assume that the loss function, L, is convex and its first and second derivatives are Lipschitz-continuous functions. Similar to [4, 23, 38, 24] we assume that the label of the poisoning points is set a priori, so the attacker just needs to learn the features for the poisoning points, . For the sake of clarity, in the following description we shall use A to denote the loss function evaluated on in the outer objective, i.e. L to refer to the loss function evaluated on in the inner objective, i.e. ; both are evaluated on the optimal solution wof the inner problem. We can compute the hypergradients in the outer problem by leveraging the conditions for stationarity in the inner problem, i.e. applying the implicit function theorem [23]. Then, the hypergradients can be computed as:

where we assume that the Hessian is not singular. Brute-force computation of (4) requires inverting the Hessian, which scales in time as and in space as —where d is the dimensionality of the parameters. However, as in [9], we can rearrange the terms in the second part of (4) and solve first the linear system:, and compute linear system can be efficiently solved by using conjugate gradient descent. Moreover, Hessian-vector products can be computed exactly and efficiently with the technique proposed in [30], avoiding the computation and storage of the Hessian (for further details, see Appendix A).

However, the previous approach requires training the whole learning algorithm to compute the hypergradient. This can be intractable for some learning algorithms such as deep networks, where the number of parameters is huge. To sidestep this problem, different techniques have been proposed to estimate the value of the hypergradients [8, 22, 31, 10, 24, 11]. These techniques do not require to re-train the learning algorithm every time the hypergradient is computed. Instead, they estimate the hypergradient by truncating the learning in the inner problem to a reduced number of epochs.

Depending on the order in which the operations are computed, we differentiate two approaches to estimate the hypergradients: Reverse-Mode (RMD) and Forward-Mode Differentiation (FMD) [14, 10]. In the first case, RMD requires to first train the learning algorithm for T epochs. Then, the hypergradients estimate is computed by reversing the steps followed by the learning algorithm. In some cases, RMD requires to store all the information collected in the trajectory of the parameters. This can be prohibitive for deep networks where the number of parameters is huge. However, other RMD methods proposed do not require to store this information [22, 24]. In contrast, FMD computes the hypergradients estimate as the algorithm is trained. However, the scalability of FMD depends heavily on the number of hyperparameters compared to RMD. So, for problems where the number of hyperparameters is large, as is the case for the poisoning attacks we introduced in (2) and (3), RMD is computationally more efficient. Hence, we used RMD in our experiments. Moreover, compared to grid search, these gradient-based techniques allow reducing the computational cost, as the algorithm does not need to be trained completely and evaluated for each combination of hyperparameters.

Finally, once we have computed the hypergradients, at each hyperiteration we can use projected hypergradient descent/ascent to update the value of the poisoning points and the model’s hyperparameters:

where are respectively the learning rates and are the projection operators for the features of the poisoning points, , and the hyperparameters, , so that their updated values are within the corresponding feasible domains, and . In our case we used standard gradient ascent/descent to solve (3). The analysis of other alternatives to solve minimax games, such as optimistic gradient descent/ascent [6] is left for future work.

Poisoning attacks are intrinsically related to the stability of ML algorithms. Attackers aim to produce large changes in the target algorithm by influencing a reduced set of training points. Xu et al. [40] introduced the following definition of stability: “an ML algorithm is stable if its output is nearly identical on two datasets, differing on only one sample." This concept of stability has also been studied in the field of robust statistics, in which robustness formally denotes this notion of stability [32]. It is not our intention here to provide a formal analysis on the stability of the ML algorithms, but to show that stability is an important property for the design of ML algorithms robust to data poisoning. For instance, in [26] it was shown empirically that for the same fraction of attack points, the effect of a poisoning attack reduces when the number of training points increases, as the stability of the algorithm increases. Thus, data augmentation can help to limit the attacker’s ability to degrade the overall system’s performance, leading to significant improvements in generalisation [35]. However data augmentation may not be as effective to defend against more targeted attacks or backdoors.

(or Tikhonov) regularisation is a well-known mechanism to increase the stability of ML algorithms [40]. In regularisation we add a penalty term to the original loss function which shrinks the norm of the model’s parameters, so that where is the hyperparameter that controls the strength of the regularisation term. The exponential form is used to ensure a positive contribution of the regularisation term for the loss function and to help learning , for example by using (1), as this hyperparameter is usually searched over a log-spaced grid [31]. Different regularisation schemes can be considered: e.g., in neural networks, we could have one regularisation term for the parameters at each layer or even a different term for each parameter [9].

Xiao et al. [38] analysed the robustness of embedded feature selection, including regularisation, for linear classifiers against optimal poisoning attacks. Although their experimental results showed that was slightly more robust compared to regularisation and elastic-net, all the classifiers tested where significantly vulnerable to indiscriminate optimal poisoning attacks. However, these results relied on the assumption that the regularisation hyperparameter was constant regardless of the fraction of poisoning data. This approach can produce misleading results, as the poisoning points can have a significant effect on the value of the hyperparameter learned, for example by using (1).

In Fig. 1 we show a synthetic example with a binary classifier to illustrate the limitations of the approach considered in [38]. Here, 32 points for the two classes (16 per class) were drawn from two different bivariate Gaussian distributions and we trained a Logistic Regression (LR) classifier. Fig. 1(left) shows the effect of injecting a single poisoning point (red point, labelled as green) that aims to maximise the error (measured on a separate validation set with 64 data points) against an LR classifier with no regularisation.3 The dashed-white line represents the decision boundary learned when training on the clean dataset, whereas the red line depicts the decision boundary of the LR trained on the poisoned dataset. We can observe that a single poisoning point can significantly alter the decision boundary. Fig. 1(centre), shows a similar scenario, but training an LR classifier with regularisation, setting . Here, we can observe that the effect of the poisoning point on the classifier is much reduced and the decision boundary shifts only slightly. In the background of these two figures we represent the error evaluated on the validation set for the LR trained on a poisoned dataset as a function of the location of the poisoning point. We can observe that, when there is no regularisation (left) the error can significantly increase when we inject the poisoning point in certain regions. On the contrary, when regularisation is applied (centre), the colour-map is more uniform, i.e. the algorithm is quite stable regardless of the position of the poisoning point and the increase in the validation error after the attack is very small.

Fig. 1(right) shows how the value of the regularisation hyperparameter, , changes as a function of the poisoning point. The colour-map in the background represents the value of learned by solving (1), i.e. the that minimises the error on the validation set. We can observe that can change significantly depending on the position of the poisoning point. Thus, is much bigger for the regions where the poisoning point can influence more the classifier (Fig. 1(left)). Then, when the poisoning attack can have a very negative impact on the classifier’s performance, the importance of the regularisation term, controlled by , increases. It is clear that selecting the value of appropriately can have a significant impact on the classifier’s robustness. Furthermore, when testing the robustness of -regularised classifiers we must consider the interplay between the attack strength and the value of

In this section, we evaluate the effectiveness of the attack strategy in (3) against LR and feed-forward Deep Neural Networks (DNNs). For LR, we use three different binary classification problems: MNIST (‘0’ vs ‘8’) [20], Fashion-MNIST (FMNIST) (T-shirt vs pullover) [39], and ImageNet (dog vs fish) [33] preprocessed as in [18], where the first two datasets have 784 features, and the latter has 2, 048 features. For the DNN, we focus on ImageNet. All datasets are balanced, and for all of them

Figure 2: Results for the optimal attack against LR: The first row represents the average test error on (a) MNIST, (b) FMNIST, and (c) ImageNet. The second row contains the plots for the average for (d) MNIST, (e) FMNIST, and (f) ImageNet.

we use 512 training and 171 validation points, drawn at random from the original pool of training points. For testing, we use 1, 954 points for MNIST, 2, 000 for FMNIST, and 600 for ImageNet.4 All the results in our experiments are the average of 10 repetitions with different random data splits for training and validation, whereas the test set is fixed. For all the attacks we measure the average test error for different attack strengths, where the number of poisoning points ranges from 0 to 85.

5.1 Logistic Regression

For LR we test the general poisoning attack strategy in (3) using the following settings for the computation of the hypergradients with RMD. For MNIST we set T, the number of epochs for the inner problem, to 150. For FMNIST and ImageNet we use T = 200. For comparison purposes, we craft optimal poisoning attacks, setting the value of to different constant values: a very small regularisation term (), a very large one (for MNIST, for FMNIST, and for ImageNet), and the value of optimised with 5-fold cross-validation, training the model on the clean dataset (). With the small and large constant values for we aim to show the trade-off between accuracy and robustness to different attack strengths. The case of is similar to the settings used in [38].

The results are shown in Fig. 2(a)-(c). We can observe that for the small the attacks are very effective and the test error increases significantly when compared to the algorithm’s performance on the clean dataset. In contrast, for the biggest the test error increases only slightly with the increasing fraction of poisoning points, showing a stable performance regardless of the attack strength. However, in the absence of an attack, the algorithm clearly underfits and the error is significantly higher compared to the other models. When the value of is learned (), i.e. solving the problem in (3), the increase on the test error is quite moderate and, when the ratio of poisoning points is large, presents a similar performance as in the case where the value of is large. In this sense, the error does not increase further by injecting more poisoning points. In the absence of attack, we can observe that the performance for is as good as in the case of

The results in Fig. 2(a)-(c) show that the attack and the methodology presented in [38] provide an overly pessimistic view on the robustness of regularisation to data poisoning attacks and that, by appropriately selecting the value of , we can effectively reduce the impact of such attacks. Furthermore, we can also observe that there exists a trade-off between accuracy and robustness:

Figure 3: Results for the optimal attack against the DNN on ImageNet. (a) Average test error. represents the one learned with RMD. (b) Average learned with RMD. (c) Average where represents the number of parameters of the corresponding layer. This normalisation allows comparing for each layer regardless of the number of the parameters.

over-regularising (i.e. setting a very large value for ) makes the algorithm more robust to the attack, but the performance is degraded when there is no attack.

In Fig. 2(d)-(f) we show the value of learned and the norm of the model’s parameters, function of the fraction of poisoning points injected for the solution of problem (3) with RMD. We can observe that in all cases, the regularisation hyperparameter increases as we increase the fraction of poisoning points, which means that the regularisation term tries to compensate the effect of the malicious samples on the model’s parameters. Thus, as expected, provides a natural mechanism to stabilise the model in the presence of attacks. For ImageNet, the order of magnitude of is higher, as there are more features in the model. In Fig. 2(d)-(f) we can also observe that, as expected from the properties of regularisation, when increases, the norm of the parameters decreases.

5.2 Deep Neural Networks

For DNNs, we consider a vector of regularisation hyperparameters , with one hyperparameter for each layer. Intuitively, the amount of scaling needed by each layer’s parameters to compensate for a change in the output is not the same, given the nonlinear activation functions. This can also give us an intuition about which layer is more vulnerable to the poisoning attack. We also propose an additional modification to the RMD algorithm: we apply different initial random parameters wfor every update of the poisoning points. This can be interpreted as assembling different randomly initialised DNNs to improve the generalisation of the poisoning points across different parameter initialisations. In this case we set T = 600. This scenario is much more challenging for the multiobjective bilevel problem we aim to solve, as the model has two hidden layers () with Leaky ReLU activation functions, which sums up to a total of 266, 433 parameters.

As in the previous experiment, we performed attacks with different strengths for the DNN trained with small () and large () values for the regularisation hyperparameter, constant for all the layers. In this case, we omitted the case where is set with 5-fold cross-validation on the clean dataset as the search space is large, which makes it computationally very expensive. As before, we denote with the case where the regularisation hyperparameter is learned (3). The results in Fig. 3(a) are consistent with those obtained for the case of LR. For the algorithm is very vulnerable to the poisoning attack and its test error significantly increases up to 12% when the training dataset is poisoned with 16.6% malicious points. On the contrary, for the algorithm’s performance remains quite stable for increasing fractions of poisoning points. For the test error increases moderately and stabilises when the fraction of poisoning points is 10%. Finally, from Fig. 3(a) we can see that when there is no attack, the test error for is smaller than the other two cases. As discussed before, although over-regularising may be appealing to make the algorithm more robust to poisoning attacks, the performance in the absence of attack may be significantly worse.

In Fig. 3(b) we can observe that the learned for the second and output layers increase faster than the one for the first layer. This result suggests that the latter layers are more vulnerable to the poisoning attack. In other words, the poisoning attack tries to produce more changes in the parameters of the network in those layers and, at the same time, the network tries to resist to those changes by increasing the value of the corresponding regularisation hyperparameters. Finally, in Fig. 3(c) we show the norm of the parameters for each layer divided by the number of parameters in each case. The results are consistent with those in Fig. 3(b): The norm of the parameters in the last two layers significantly decrease when we increase the fraction of poisoning points. On the other side, regardless of the attack strength, the norm of the parameters is significantly bigger for the output layer.

In this paper we introduce a novel poisoning attack strategy for evaluating the robustness of ML classifiers that contain hyperparameters in worst-case scenarios. The attack can be formulated as a multiobjective bilevel optimisation problem that can be solved with gradient-based techniques. We show the limitations of previous approaches, such as [4, 38], where the model’s hyperparameters are considered constant regardless of the type and strength of the attack. As shown in our experiments, this approach can provide a misleading (and, often, pessimistic) view of the algorithms’ robustness. We show that these poisoning attacks can have a strong influence on the hyperparameters learned, and thus, their influence must be considered when assessing the robustness of the algorithms.

We also show that, contrary to the results reported in [38], regularisation can help to to mitigate the effect of poisoning attacks, increasing the stability of the learning algorithms. When the attacker increases the strength of the attack, the regularisation hyperparameter also increases to compensate the instability that the attacker tries to produce in the algorithm. Our experimental evaluation shows the benefits of using regularisation as a good practice to reduce the impact of poisoning attacks. We also illustrate the trade-off between robustness and accuracy as a function of the regularisation hyperparameter. Our results highlight the importance of stability as a desired property for the design of more robust algorithms to data poisoning. Further research work will include the analysis of attacks in multiclass settings, other forms of regularisation, such as and elastic-net, and the analysis of the robustness to data poisoning for other learning algorithms that contains hyperparameters.

[1] J. F. Bard. Practical Bilevel Optimization: Algorithms and Applications, volume 30. Springer Science & Business Media, 2013.

[2] M. Barreno, B. Nelson, A. D. Joseph, and J. D. Tygar. The security of machine learning. Machine Learning, 81(2):121–148, 2010.

[3] M. Barreno, B. Nelson, R. Sears, A. D. Joseph, and J. D. Tygar. Can Machine Learning Be Secure? In Proceedings of the 2006 ACM Symposium on Information, Computer and Communications Security, pages 16–25. ACM, 2006.

[4] B. Biggio, B. Nelson, and P. Laskov. Poisoning Attacks against Support Vector Machines. In International Conference on Machine Learning, pages 1807–1814, 2012.

[5] C. M. Bishop. Pattern Recognition and Machine Learning. Springer, 2006.

[6] C. Daskalakis and I. Panageas. The Limit Points of (Optimistic) Gradient Descent in Min-Max Optimization. In Advances in Neural Information Processing Systems, pages 9236–9246, 2018.

[7] I. Diakonikolas, G. Kamath, D. Kane, J. Li, J. Steinhardt, and A. Stewart. Sever: A Robust Meta-Algorithm for Stochastic Optimization. In International Conference on Machine Learning, pages 1596–1606, 2019.

[8] J. Domke. Generic Methods for Optimization-Based Modeling. In Artificial Intelligence and Statistics, pages 318–326, 2012.

[9] C.-S. Foo, C. B. Do, and A. Y. Ng. Efficient multiple hyperparameter learning for log-linear models. In Advances in Neural Information Processing Systems, pages 377–384, 2008.

[10] L. Franceschi, M. Donini, P. Frasconi, and M. Pontil. Forward and Reverse Gradient-Based Hyperparameter Optimization. In International Conference on Machine Learning, pages 1165–1173, 2017.

[11] L. Franceschi, P. Frasconi, S. Salzo, R. Grazzi, and M. Pontil. Bilevel Programming for Hyperparameter Optimization and Meta-Learning. In International Conference on Machine Learning, pages 1568–1577, 2018.

[12] X. Glorot and Y. Bengio. Understanding the difficulty of training deep feedforward neural networks. In Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, pages 249–256, 2010.

[13] I. Goodfellow, Y. Bengio, and A. Courville. Deep Learning. MIT Press, 2016.

[14] A. Griewank and A. Walther. Evaluating Derivatives: Principles and Techniques of Algorithmic Differentiation, volume 105. SIAM, 2008.

[15] T. Gu, K. Liu, B. Dolan-Gavitt, and S. Garg. BadNets: Evaluating Backdooring Attacks on Deep Neural Networks. IEEE Access, 7:47230–47244, 2019.

[16] L. Huang, A. D. Joseph, B. Nelson, B. I. P. Rubinstein, and J. D. Tygar. Adversarial Machine Learning. In Proceedings of the 4th ACM Workshop on Security and Artificial Intelligence, pages 43–58. ACM, 2011.

[17] M. Kloft and P. Laskov. Security Analysis of Online Centroid Anomaly Detection. Journal of Machine Learning Research, 13(Dec):3681–3724, 2012.

[18] P. W. Koh and P. Liang. Understanding Black-box Predictions via Influence Functions. In International Conference on Machine Learning, pages 1885–1894, 2017.

[19] P. W. Koh, J. Steinhardt, and P. Liang. Stronger Data Poisoning Attacks Break Data Sanitization Defenses. arXiv preprint arXiv:1811.00741, 2018.

[20] Y. LeCun, L. Bottou, Y. Bengio, P. Haffner, et al. Gradient-Based Learning Applied to Document Recognition. Proceedings of the IEEE, 86(11):2278–2324, 1998.

[21] Y. Liu, S. Ma, Y. Aafer, W.-C. Lee, J. Zhai, W. Wang, and X. Zhang. Trojaning Attack on Neural Networks. In Department of Computer Science Technical Reports, Purdue University, 2017.

[22] D. Maclaurin, D. Duvenaud, and R. Adams. Gradient-based Hyperparameter Optimization through Reversible Learning. In International Conference on Machine Learning, pages 2113– 2122, 2015.

[23] S. Mei and X. Zhu. Using Machine Teaching to Identify Optimal Training-Set Attacks on Machine Learners. In Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, pages 2871–2877, 2015.

[24] L. Muñoz-González, B. Biggio, A. Demontis, A. Paudice, V. Wongrassamee, E. C. Lupu, and F. Roli. Towards Poisoning of Deep Learning Algorithms with Back-gradient Optimization. In Proceedings of the 10th ACM Workshop on Artificial Intelligence and Security, pages 27–38. ACM, 2017.

[25] L. Muñoz-González and E. C. Lupu. The Security of Machine Learning Systems. In AI in Cybersecurity, pages 47–79. Springer, 2019.

[26] L. Muñoz-González, B. Pfitzner, M. Russo, J. Carnerero-Cano, and E. C. Lupu. Poisoning Attacks with Generative Adversarial Nets. arXiv preprint arXiv:1906.07773, 2019.

[27] B. Nelson, M. Barreno, F. J. Chi, A. D. Joseph, B. I. P. Rubinstein, U. Saini, C. A. Sutton, J. D. Tygar, and K. Xia. Exploiting Machine Learning to Subvert Your Spam Filter. LEET, 8:1–9, 2008.

[28] A. Paudice, L. Muñoz-González, A. György, and E. C. Lupu. Detection of Adversarial Training Examples in Poisoning Attacks through Anomaly Detection. arXiv preprint arXiv:1802.03041, 2018.

[29] A. Paudice, L. Muñoz-González, and E. C. Lupu. Label Sanitization Against Label Flipping Poisoning Attacks. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 5–15. Springer, 2018.

[30] B. A. Pearlmutter. Fast Exact Multiplication by the Hessian. Neural Computation, 6(1):147–160, 1994.

[31] F. Pedregosa. Hyperparameter optimization with approximate gradient. In International Conference on Machine Learning, pages 737–746, 2016.

[32] B. I. P. Rubinstein, B. Nelson, L. Huang, A. D. Joseph, S.-h. Lau, S. Rao, N. Taft, and J. D. Tygar. ANTIDOTE: Understanding and Defending against Poisoning of Anomaly Detectors. In Proceedings of the 9th ACM SIGCOMM Conference on Internet Measurement, pages 1–14. ACM, 2009.

[33] O. Russakovsky, J. Deng, H. Su, J. Krause, S. Satheesh, S. Ma, Z. Huang, A. Karpathy, A. Khosla, M. Bernstein, et al. ImageNet Large Scale Visual Recognition Challenge. International Journal of Computer Vision, 115(3):211–252, 2015.

[34] A. Shafahi, W. R. Huang, M. Najibi, O. Suciu, C. Studer, T. Dumitras, and T. Goldstein. Poison Frogs! Targeted Clean-Label Poisoning Attacks on Neural Networks. In Advances in Neural Information Processing Systems, pages 6103–6113, 2018.

[35] P. Y Simard, D. Steinkraus, and J. C Platt. Best Practices for Convolutional Neural Networks Applied to Visual Document Analysis. In Proceedings of the Seventh International Conference on Document Analysis and Recognition - Volume 2, pages 958–962, 2003.

[36] J. Steinhardt, P. W. W. Koh, and P. S. Liang. Certified Defenses for Data Poisoning Attacks. In Advances in Neural Information Processing Systems, pages 3517–3529, 2017.

[37] C. Szegedy, V. Vanhoucke, S. Ioffe, J. Shlens, and Z. Wojna. Rethinking the Inception Architecture for Computer Vision. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 2818–2826, 2016.

[38] H. Xiao, B. Biggio, G. Brown, G. Fumera, C. Eckert, and F. Roli. Is Feature Selection Secure against Training Data Poisoning? In International Conference on Machine Learning, pages 1689–1698, 2015.

[39] H. Xiao, K. Rasul, and R. Vollgraf. Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms. arXiv preprint arXiv:1708.07747, 2017.

[40] H. Xu, C. Caramanis, and S. Mannor. Sparse Algorithms Are Not Stable: A No-Free-Lunch Theorem. IEEE Transactions on Pattern Analysis and Machine Intelligence, 34(1):187–193, 2011.

[41] Y. Yao, B. Viswanath, J. Cryan, H. Zheng, and B. Y. Zhao. Automated Crowdturfing Attacks and Defenses in Online Review Systems. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, pages 1143–1158. ACM, 2017.

[42] X. Zhang, X. Zhu, and S. Wright. Training Set Debugging Using Trusted Items. In Thirty-Second AAAI Conference on Artificial Intelligence, 2018.

Let x , y , v , and . If the second partial derivatives of f(x, y) are continuous almost everywhere5 in X and Y (mild condition), the Hessian-vector products can be computed exactly and efficiently by using the following identities [30]:

The left and right expressions scale as O(m) and O(max(m, n)), respectively, both in time and space. Analogous expressions can be obtained when v . An elegant aspect of this technique is that, for machine learning models optimised with gradient-based methods, the equations for exactly evaluating the Hessian-vector products emulate closely those for standard forward and backward propagation. Hence, the application of existing automatic differentiation frameworks to compute this product is typically straightforward [30, 5].

Alg. 1 describes the procedure to solve the multiobjective bilevel problem proposed in Sect. 3. Essentially, this algorithm implements projected hypergradient descent/ascent to optimise, in a coordinate manner, the poisoning points—replaced into the training set—and the set of hyperparameters.

Alg. 1 receives as inputs M (the target model), A and L (outer and inner objective functions), and (validation and training datasets), (number of poisoning points to optimise), (indices of the points—uniformly sampled without duplicates—of to be replaced by and T (number of hyperiterations for the outer problem and number of epochs for the inner problem), and (learning rates for the features of the poisoning points, , for the hyperparameters, , and for the parameters of the inner problem, respectively). In addition, let w and denote the the model’s parameters and the labelled poisoning points, correspondingly. At the end of the algorithm, it outputs the optimised poisoning points and hyperparameters, i.e. . For the sake of clarity, in the algorithms included in this appendix and the following ones we shall make use of the following notation:

where Xval and Xare the features of the validation and poisoned training sets, and yval and yare their respective labels.

To reduce the computational burden, we consider the simultaneous optimisation of a batch of poisoning points, . We generate the initial values of by cloning uniformly sampled without duplicates—of . Their labels are initially flipped and kept fixed during the optimisation. This process is carried out in the function initDp (Line 1). Then, these samples replace the clean samples of whose indices are in the set P (Line 2). On the other hand, the hyperparameters are initialised in initL (Line 3). In the case study of this paper, the hyperparameters correspond to the regularisation ones.

In a bilevel optimisation problem, the outer problem depends on the solution of the inner problem. Hence, in order to solve the bilevel problem, every time (hyperiteration) the variables in the outer problem (i.e. Xp and in this case) are updated, the variables in the inner problem (i.e. the model’s parameters) need to be previously initialised and optimised. Thus, let initW (Line 5) be a particular initialisation for the model’s parameters. hypGradXp (Line 6) and hypGradL (Line 9) refer to the particular optimisation algorithm used to train the model’s parameters and compute the corresponding

11: end for

hypergradients. In this work, this algorithm is Reverse-Mode Differentiation (RMD) (Alg. 2). Then, (Line 7) and (Line 10) are the projection operators for , so that their updated values are within the corresponding feasible domains, . Line 8 updates the features of the poisoning samples in the poisoned training set.

In our experiments, we simulate different ratios of poisoning points in a cumulative manner: Once the optimisation of the current batch of poisoning points and hyperparameters is finished,6 this batch of poisoning points is fixed and the next batch of poisoning points is replaced into the remaining clean training set, to carry out their corresponding optimisation. To accelerate their optimisation, the hypergradients for the poisoning points are normalised with respect to their norm.7 Regarding the hyperparameters, their values are updated continuously for the whole set of batches of poisoning points.

As described in [10], we can think of the training algorithm as a discrete-time dynamical system, described by a set of states , with t = 0, . . . , T, where each state depends on model’s parameters, the accumulated gradients and/or the velocities. Then, from a reduced number of training iterations, T, we can estimate the hypergradients from the values of the parameters collected in the set of states. Depending on the order to compute the operations we can differentiate two approaches to estimate the hypergradients: Reverse-Mode (RMD) and Forward-Mode Differentiation (FMD) [14, 10]. In the first case, RMD requires first to train the learning algorithm for T epochs, and then, to compute . Then, the hypergradients estimate is computed by reversing the steps followed by the learning algorithm from down to . On the other hand, FMD computes the estimate of the hypergradients as the algorithm is trained, i.e. from to (i.e. the estimates can be computed in parallel with the training procedure).

In some cases, as in [8], RMD requires to store all the information collected in the states in the forward pass. This can be prohibitive in some cases as, for example, for deep networks where the number of parameters is huge. However, other RMD methods proposed in the literature do not require to store this information [22, 24]. To estimate the hypergradients, RMD requires to compute a forward and a backward pass through the set of states. In contrast, FMD just needs to do the forward computation. However, the scalability of FMD depends heavily on the number of hyperparameters

compared to RMD. Then, for problems where the number of hyperparameters is large, as it is the case for the poisoning attacks we introduced in Sect. 3, RMD is computationally more efficient to estimate the hypergradients. For this reason, we used RMD in our experiments.

Here we include the Reverse-Mode Differentiation (RMD) algorithm (Alg. 2) [8, 22, 24], which we use to compute the hypergradient estimate at the outer level problem (both for the features of the poisoning points, Xp, and the hyperparameters, ). We make use of a similar notation to the algorithms presented in [22, 24]. The resulting algorithm for the case of is analogous.

In the following specifications, denotes the number of hyperiterations at the outer problem when the poisoning points are learned and when the training set is clean and is learned, and are learned in a coordinate manner. Finally, is the learning rate when testing the attack.

D.1 Architecture of the Models and Initialisation of Their Parameters

The Logistic Regression (LR) classifier’s parameters are always initialised with zeros, for all the datasets.

In contrast, the Deep Neural Network (DNN) model—trained on ImageNet—has two hidden layers () with Leaky ReLU activation functions (with a negative slope of 0.1), which sums up to a total of 266, 433 parameters. These parameters are initially filled with values according to the Xavier Initialisation method [12], using a uniform distribution for all the parameters except the bias terms, which are initialised with a value of

D.2 Synthetic Example

For the synthetic experiment shown in Sect. 4, we sample the attacker’s data from two bivariate Gaussian distributions, and , with mean vectors and covariance matrices for each class, i = 0, 1:

Table 1: Characteristics of the datasets used in the experiments.

Table 2: Experimental settings for the poisoning attack.

Table 3: Experimental settings for training the models.

The attacker uses 32 points (16 per class) for training and 64 (32 per class) for validation, and one poisoning point cloned from the validation set (in the example of Sect. 4, cloned from the set labelled as blue), whose label is flipped. This poisoning point is concatenated into the training set and the features of this point are optimised with RMD. In order to poison the LR classifier, we use a learning rate and a number of hyperiterations for the poisoning point ; the feasible domain ; the learning rate and number of epochs for the inner problem ; and when evaluating the attack, , batch size = 32 (full batch), and number of epochs = 100. When we apply regularisation, we fix

To plot the colour-map that shows the value of the regularisation hyperparameter learned (Fig. 1(right)) as a function of the poisoning point injected in the training set, the values of explored for each possible poisoning point are in the range . Then, the optimal value of is chosen such that it minimises the error of the model, trained on each combination of the poisoning point (concatenated into the training set) and in the grid, and evaluated on the validation set.

D.3 MNIST, FMNIST and ImageNet

In our experiments, all the results for MNIST ‘0’ vs ‘8’ [20], Fashion-MNIST (FMNIST) T-shirt vs pullover [39], and ImageNet dog vs fish [33] (preprocessed as in [18]) are the average of 10 repetitions with different random data splits for training and validation, whereas the test set is fixed. For all the attacks we measure the average test error for different attack strengths, where the number of poisoning points is in the range between 0 and 85. To reduce the computational cost, the size of the batch of poisoning points that are simultaneously optimised (as explained in Appendix B) is 17 for all the datasets. This way, we simulate six different ratios of poisoning ranging from 0% to 16.6%.

The details of each dataset are included in Table 1. All the datasets are balanced. Moreover, both MNIST and FMNIST sets are normalised to be in the range , whereas for the ImageNet sets we use the same Inception-v3 [37] features as in [18], and normalised them with respect to their training mean and standard deviation.

Figure 4: Average test false positive and false negative rate for LR. represents the one learned with RMD. The first row represents the test false positive rate: (a) MNIST, (b) FMNIST, and (c) ImageNet. The second row depicts the test false negative rate: (d) MNIST, (e) FMNIST, and (f) ImageNet.

For all the experiments, we make use of stochastic gradient descent both to update the parameters in the forward pass of RMD8 (full batch training), and to train the model when testing the attack (mini-batch training). The details of the attack settings are shown in Table 2, whereas the ones for training are in Table 3. Additionally, is optimised with 5-fold cross-validation—training the model on the clean dataset, as in [38]. For all the datasets the ranges of values of explored to compute (no better performance was observed for larger values of ). On the other hand, to accelerate the optimisation of , when the training set is clean these hyperparameters are warm-started with a value

D.4 Details of the Hardware Used

All the experiments are run on GB NVIDIA GeForce RGTX 1080 Ti GPUs. The RAM memory is 64 GB (GB) Corsair VENGEANCE DDR4 3000 MHz. The processor (CPU) is Intel Ri7 Quad Core Processor i7-7700k (4.2 GHz) 8 MB Cache.

E.1 Test False Positive and False Negative Rate

E.1.1 Logistic Regression

In Fig. 4 we represent the results for the test false positive and false negative rate for LR on MNIST, FMNIST, and ImageNet. The results are consistent with the test error shown in Fig. 2(upper row): The rates for lower bound the ones where regularisation is not applied (), whose trend

Figure 5: Average test false positive and false negative rate for the DNN on ImageNet. represents the one learned with RMD: (a) Test false positive rate and (b) test false negative rate.

is very similar to the case of . For MNIST, the false positive rate for (Fig. 4(a)) is lower than the one for the large value of of poisoning points; the false negative rate for (Fig. 4(d)) is lower than the one for the large regularisation term until a 2% of poisoning points, and follows a similar trend from that point on. On the other side, for FMNIST, the false positive rate when learning (Fig. 4(b)) is lower than the one for when the fraction of poisoning points is lower than 5%, and it reaches a maximum at around 10%, where it starts to decrease, being again lower at approximately 15% of poisoning points; the false negative rate for (Fig. 4(e)) is lower until a 2.5% of poisoning, and from then on it follows a similar pattern to the one for Finally, for ImageNet, the false positive rate when is learned (Fig. 4(c)) follows a very similar trend to the one for ; in the case of the false negative rate (Fig. 4(f)), it is lower than the one for the large regularisation term until a 3% of poisoning points, and from that point on it presents a similar pattern.

E.1.2 Deep Neural Networks

In Fig. 5 we depict the results for the test false positive and false negative rate for the DNN on ImageNet. The results present a similar trend to the test error (Fig. 3(a)), as again the rates corresponding to are lower bounded by the ones for . The false positive rate for (Fig. 5(a)) appears to be greater than the plot corresponding to , which does not seem affected by the attack. Regarding the false negative rate for (Fig. 5(b)), it is lower than the one for until a 5% of poisoning points, and after a roughly 10% of poisoning points it slightly decreases when the fraction of poisoning points increases, until a 16.6% of poisoning points, where it becomes equal to the one for the strong regularisation term.

E.2 Histograms of the Models’ Parameters

E.2.1 Logistic Regression

In Fig. 6 we represent the histogram of the values of the parameters, w, of the LR classifier on MNIST, FMNIST and ImageNet, when the training sets are clean (blue bars) and when a 16.6% of each training set is replaced by poisoning points (orange bars). To appreciate better the distribution of the parameters, we omit the upper part of some plots. The first row depicts the cases when no regularisation is applied, and the second row shows the case where is learned using RMD. We can clearly appreciate the effect of the regularisation: For all the datasets, the range of values of the parameters (blue bars of the second row) is narrowed down, and when the attacker injects poisoning points, this forces the model to compress more these values (orange bars of the second row) close to 0, as the value of increases. This leads to a more stable model under possible malicious manipulations of the training data.

E.2.2 Deep Neural Networks

In Fig. 7 we represent the histogram of the values of the parameters of the DNN classifier on ImageNet, for the clean dataset (blue bars) and when a 16.6% of the training set is replaced by poisoning points (orange bars). The first, second, and third column show the results for the first hidden, second hidden, and output layer, correspondingly. The first row depicts the cases where no regularisation is applied, and the second row when is learned using RMD. Once again, we can

Figure 6: Histograms (in terms of relative frequency) of the LR’s parameters. For a better visualisation, the upper part of some subfigures has been omitted. The first row represents the case where no regularisation is applied: (a) MNIST, (b) FMNIST, and (c) ImageNet. The second row shows the case where is learned with RMD: (d) MNIST, (e) FMNIST, and (f) ImageNet.

Figure 7: Histograms (in terms of relative frequency) of the DNN’s parameters on ImageNet. The first row represents the case where regularisation is not applied: (a) first hidden layer, (b) second hidden layer, and (c) output layer. The second row shows the corresponding results when is learned with RMD: (a) first hidden layer, (b) second hidden layer, and (c) output layer.

appreciate the effect of the regularisation: For all the layers, the range of values of the parameters (blue bars of the second row) is narrowed down, and when the attacker poisons the training data, this forces the model to bound more these values (orange bars of the second row), as the corresponding values of for each layer increase.

Figure 8: Examples of poisoning points computed with RMD for the LR classifier on MNIST: (a) initial features, (b) features optimised for , and (c) features optimised for

Figure 9: Examples of poisoning points computed with RMD for the LR classifier on FMNIST: (a) initial features, (b) features optimised for , and (c) features optimised for

E.3 Examples of Poisoning Points Computed

Here we depict the image representation of poisoning points randomly sampled across different fractions of poisoning. These points are computed with RMD for the LR classifier on MNIST (Fig. 8) and FMNIST (Fig. 9), respectively. For both datasets we represent the initial values of the features of the poisoning points and their optimised values for the cases where there is no regularisation (), and when is learned (). We do not include examples for ImageNet as we use the same Inception-v3 features as in [18], so that each of the images is represented by a 2, 048-dimensional vector that does not have an obvious representation in the image domain.

For MNIST, we can observe that the optimised points present a similar pattern for the cases where is learned. For FMNIST, they also present a similar representation in most of the cases, although when the attack is strong—i.e. the ratio of poisoning points is large—the solutions obtained when is learned present more saturated features, which could be more detectable for the human perception. In other words, in this case the poisoning attack against the classifier learning the regularisation term requires increasing the level of perturbation in the malicious examples, which can make the attack more detectable.