Certified Robustness to Data Poisoning in Gradient-Based Training

Authors: Philip Sosnin, Mark Niklas Mueller, Maximilian Baader, Calvin Tsay, Matthew Robert Wicker
Primary area: optimization
Keywords: Data Poisoning, Certified Robustness, Neural Networks

Abstract:
Modern machine learning pipelines leverage large amounts of public data, making it infeasible to guarantee data quality and leaving models open to poisoning and backdoor attacks. Provably bounding model behavior under such attacks remains an open problem. In this work, we address this challenge by developing the first framework providing provable guarantees on the behavior of models trained with potentially manipulated data without modifying the model or learning algorithm. In particular, our framework certifies robustness against untargeted and targeted poisoning, as well as backdoor attacks, for bounded and unbounded manipulations of the training inputs and labels. Our method leverages convex relaxations to over-approximate the set of all possible parameter updates for a given poisoning threat model, allowing us to bound the set of all reachable parameters for any gradient-based learning algorithm. Given this set of parameters, we provide bounds on worst-case behavior, including model performance and backdoor success rate. We demonstrate our approach on multiple real-world datasets from applications including energy consumption, medical imaging, and autonomous driving.

Decision: reject
Reviewer scores: 5, 8, 5

Reviews and discussion:
<thread>
creation date:
1730080006230

thread_type:
official_review

<thread_object>
creator: reviewer_yeud

<content>
summary:
This paper proposes to certify the robustness of a model trained on possibly poisoned dataset through the robustness of its parameters. Specifically, the model performance is bounded by the worst-case performance over all possible parameters that can be trained over all possible poisoned datasets under a capability constraint on the attacker. The authors therefore propose to certify a parameter-space bounds, and provide a practical algorithm when the model is a fully-connected neural network. The authors demonstrate their certified accuracy through the proposed method on various datasets.

strengths:
1. The paper is well-organized and easy to follow.
2. This paper provides an alternative perspective to certify the model performance through the robustness of model parameters.
3. The topic of AI security and robustness regarding malicious model attacks attracts a signficant amount of attention in recent years.

weaknesses:
**Major Concerns:**

1. While it is intuitive that the variation of model parameters can serve as a tool to evaluate its robustness, the guarantee it could provide is extremely loose, at least as presented in this work. In particular, the authors consider the worst-case parameter interval against all possible poisoning dataset as in Eq. (6), and relax it further to Eqs. (8) and (9). It is questionable how useful such a valid but loose bound will be. This concern is to some extent confirmed by the experimental results. Examples include (i) in Fig 1, either a small perturbation level or a small number of poisoning data points is considered to avoid meaningless result. In Fig 1(c), flipping only 4 labels causes an almost void certified bound. (ii) in Appendix H, the authors acknowledge that their bound is extremely loose compared to real-world attacks and corresponding model performance. 

2. The practical evaluation of Eq. (6). As acknowledged by the authors in Section 3, obtaining an parameter interval by Algorithm 1 is intractable in general. The authors provide an approach to solve Eq. (10) for fully-connected neural networks only.  It seems too ambitious to derive the reachable parameter interval against all potential attacks. Even if we can somehow approximate it, as mentioned in the first point, this interval may turn out to be vacuous. 

3. Attack goals formulated in Section 2.2. While authors claim the goal of the attacker is to maximize the training loss such as Eqs. (3), (4) and (5), it makes more sense to consider controlling the generalization error or the test loss, because people are generally more interested in the test performance. To this end, the experiments should also report the certified and true performance on test datasets. Moreover, Eq. (5) is more similar to adversarial attacks instead of backdoor poisoning. A backdoor poisoning attack has dual goals of preserving the performance of clean data and ensuring the accuracy of the backdoored data in terms of the target label.

**Minor Concerns:**
1. It is unclear to me what is the close-form solution to Eq. (10) for neural networks in terms of $\epsilon, \nu, n, m$. An algorithm explaining these details will help readers better understand it.

2. Some results are neither proved or properly referred, such as Theorem 3.3 and B.1, and Proposition 1 and 2.

questions:
Please see the Weakness section above.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730390372914

thread_type:
official_review

<thread_object>
creator: reviewer_vg7q

<content>
summary:
This submission considers the problem of providing provable robustness guarantees to training-time adversarial attacks. Specifically, the considered perturbation models admits changes to a constrained number of $n$ feature vectors and $m$ labels, with optional constraints on their norm. The adversary's objective is to perform a succesful targeted or untargeted poisoning attack, or a backdoor attack.  
Unlike prior work, the authors propose to generalize existing convex relaxation based methods for neural network verification to (1) determine a reachable set of model parameters at training time and (2) at inference time determine a reachable set of model outputs given this parameter sets.  
The reachable set of model parameters is iteratively expanded with each gradient step.
Given the perturbation model and bounds from the previous iteration, lower and upper bounds for the gradients are determined via convex relaxation while (1) considering worst-case choices of inputs and parameteers for $max(m,n)$ inputs and (2) worst-case choices of parameters for the remaining inputs.  
The strength of the resultant bounds for different perturbation model parameters are evaluated by training a model from scratch on a simple regression dataset and dimensionality-reduced MNIST, as well as fine-tuning on two other vision datasets.

strengths:
* This submission proposes a novel solution to an extensively studied problem (susceptibility to training-time attack), which has received renewed attention due to the current excitement around language models.
* The problem is well-motivated via references to prior work on poisoning attacks.
* The method is clearly distinguished from prior aggregation-based approaches.
* The idea of applying iterative reachability analysis to SGD is very natural. It is somewhat surprising that no one has tried this ansatz before, i.e., the work closes a very obvious gap in existing literature.
* Rather than proposing a completely new relaxation approach, the work expands the well-established CROWN method (soundness appears to be good).
* The method is applicable to a very general perturbation model.
* The in-depth discussion of the method and its limitations in Section 3.4 is commendable.
* The work opens various obvious avenues for future work that could be of interest for the wider robust ML community (refining single- and multi-neuron bounds, generalizing beyond feed-forward networks, enforcing consistency of perturbations between gradient steps etc.)
* The manuscript is well-structured, beginning with a high-level approach (Paramaeter-space certification) and a specific instantiation of this approach (Abstract gradient training), before discussing the technical details of its individual components.

weaknesses:
* I agree with the authors' argument that the approach taken by this method is orthogonal to prior work. Nevertheless, the experiments would be significantly more informative if one were to use prior work as baselines. Instead of demonstrating "the method for verifying robustness does in fact verify robustness for sufficiently small perturbations", one could demonstrate "the verification method fills a useful niche in the certified-accuracy/runtime space for certain dataset / model sizes".
* The authors claim that their procedure was applicable to any first-order optimizer like Adam (see ll.198-199). This claim appears to be incorrect, since it would require a reachability analysis of the optimizer's internal state (moments etc.). Instead, the method appears to be limited to vanilla SGD.
* The submission does not include an implementation. Since the proposed method is rather involved, and implementing verifiers requires significant care, this significantly hinders reproducibility. I would strongly encourage the authors to provide code.
* Even if one were to try and reimplement the method, the description of hyperparameters and other aspects of the experimental setup is hardly sufficient to reproduce any of the results (see Appendix J). I would strongly encourage the authors to upload experiment configurations with their code.
* The discussion of related work is mostly relegated to Appendix A. This is an integral part of the paper and should (maybe with slightly more concise writing) be moved to the main text.

**Minor weaknesses**:
* While the authors provide asymptotic bounds on runtime complexity, they do not specify the wall-clock time needed for veryifing the different models in the experiment section. This would make it easier to gauge the practical feasibility of the proposed method.
* Based on the asymptotic runtime complexity, the use of small-scale models, and fine-tuning instead of training from scratch, the method appears to be hardly scalable to real-world settings -- except for some  special cases. I do, however, not consider this a major weakness, as this work represents a first step in a novel research direction.
* The definition of targeted attacks (Eq. 4) assumes the existence of a single, data-independent set of safe outputs $S$. However, what constitutes a safe output may often be data-dependent (e.g., whether steering left/right is safe depends on whether the ground truth direction is left/right in the PilotNet dataset from Fig. 5). It should be easy to generalize the proposed method to this use case, since one just has to evaluate the model output bounds differently.
* The definition of backdoor attacks (Eq. 5) does not enforce that the model should have high accuracy on unperturbed samples. As such, the guarenteees are likely to be very loose upper bounds on unnoticable backdoor attacks. It would probably be better to solve a constrained optimization problem over the set of reachable model parameters.
* Prior work on parameter-level verification for Bayesian NNs is mentioned, but it is not explained why these methods are not applicable to the considered problem. For instance, Wicker et al. (2020) [1] appear to determine a "safe" set of weights such that only some desired set of outputs is reachable, which is essentially inverse to Theorem 3.1.

---

[1] Wicker et al. Probabilistic Safety for Bayesian Neural Networks. UAI 2020.

---

Overall, I believe that this submission is a meaningful, well-motivated contribution to the field of robust machine learning. It proposes a very natural approach to robustness certification under training-time attacks that closes an obvious gap in existing literature.  
The submission is primarily held back by poor reproducibility and somewhat uninformative experiments, which do not provide any insights about when parameter-space certification is preferable to existing aggregation-based approaches.  
I thus recommend borderline/weak acceptance. Should the authors address either of these weaknesses (e.g. by sharing a link to anonymized code or comparing to some aggregation / randomized smoothing method on MNIST), I will further increase my score (even if the experimental results are negative).

**EDIT**: Following the rebuttal, which addresses both of my primary concerns, **I have decided to increase my score to 8 (accept)**.

questions:
* Shouldn't we use $\mathrm{SEMin}_{m+n}$ in Theorem 3.3, since the $m$ feature vectors and $n$ labels that are perturbed can belong to disjoint sets of samples (see see ll.117-118)?
* Aside from increased computational cost, are there any reasons why you decided to extend CROWN instead of more recent methods like ($\alpha,\beta$)-CROWN, MN-BAB etc.?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730714920324

thread_type:
official_review

<thread_object>
creator: reviewer_odiz

<content>
summary:
This paper attempts to provide provable guarantees on the behaviour of models trained with potentially manipulated data without modifying the model or learning algorithm. The method uses convex relaxations to over-approximate the set of all possible parameter updates for a given poisoning attack, and provide bounds on worst-case behaviour.

strengths:
The paper proposes a framework, with a (claimed to be novel) bound propagation strategy, for computing bounds on the
influence of a poisoning adversary on any model trained with gradient-based methods,  from the above, a series of proofs are suggested to bound the effect of poisoning attacks, finally, empirical evaluation are proposed to illustrate the approach.

weaknesses:
While I might have missed the rationale for computing the set of all reachable trained models given how loose such (worst-case) bounds can be, the approach seems to claim novelty while overlooking important previous contributions, in particular, the use of influence functions in robust statistics, and their revival in modern machine learning.

Cook, R. D. Detection of influential observation in linear regression. Technometrics, 19:15–18, 1977.

Cook, R. D. Assessment of local influence. Journal of the Royal Statistical Society. Series B (Methodological), pp. 133–169, 1986.

Cook, R. D. and Weisberg, S. Characterizations of an empirical influence function for detecting influential cases in regression. Technometrics, 22:495–508, 1980.

Cook, R. D. and Weisberg, S. Residuals and influence in regression. New York: Chapman and Hall, 1982.

Koh, P.W. and Liang, P., 2017, July. Understanding black-box predictions via influence functions. In International conference on machine learning (pp. 1885-1894). PMLR.

questions:
My main question would be on how this approach compares (in terms of computing the exact influence of a poisoned dataset) to the finer analysis in the references provided above.
</content>
</thread_object>

</thread>
<thread>
creation date:
1731959516906

thread_type:
official_comment

<thread_object>
creator: authors

<content>
comment:
We thank all of the reviewers for the detailed reviews. We believe that the edits in response to these reviews have improved the clarity of our work. We have provided a revised version of the manuscript with the following changes (highlighted in blue):

- Added proofs for Theorem B.1, Theorem 3.3 and Proposition 1.
- Added wall-clock time comparison to Appendix J.
- Added direct comparison with aggregation-based algorithms.
- Collected all proofs into a dedicated appendix (I) for clarity.
- Changed $\max(n, m)$ to $n + m$ in Theorem 3.3, and re-run the affected plot (Figure 1, panel d).
- Added clarification to Section 2.2 regarding test vs training time attack goals and data-dependent safe-sets.
- Corrected the heading of Figure 4.
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper explores the problem of providing provable robustness guarantees to training-time adversarial attacks. The proposed framework certifies robustness against poisoning and backdoor attacks by bounding the set of all reachable parameters, with worst-case guarantees on model performance and attack success rate.

Reviewers were interested in the approach and found the ideas fairly novel. However, there were major concerns that the bounds given by the proposed method were extremely loose and hence may not be meaningful in practice. This point was not resolved through the rebuttals. Also, the experiments were not well grounded in prior research since the authors did not use baseline methods from the literature. While this was partially added during rebuttals, the experiments have yet to be presented with sufficient rigor.

The work is promising, and the authors have worked to improve it during this review process, but the changes required are not quite complete, and are too major to be accepted as is. I am recommending rejection, but want to encourage the authors to resubmit to a comparable conference after taking the reviewer’s feedback into consideration.