Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper proposes a certified defense against triggerless and backdoor data poisoning attacks. The authors consider a threat model where the attacker can poison training instances (and the test instance for the backdoor attack) by flipping up to s of the features/label per instance. The defense is based on randomized smoothing, where the smoothing operation involves bagging of the training set and random flipping of features/labels. The certificate provides a (probabilistic) guarantee that up to R instances can be poisoned without changing the model’s prediction on a test instance. The derivation and computation of the certificate (i.e. R) is quite involved, and various relaxations are considered to speed up the computation. Experimental results demonstrate improved certified accuracies compared to bagging alone for triggerless attacks, when the fraction of poisoned instances is high and the number of flips is small. Results for backdoor attacks vary depending on the dataset. 
strengths_and_weaknesses: *Originality*

The BagFlip method proposed in this paper seems to be a hybrid of methods by Jia, Cao & Gong (2021) and Wang, Cao, Jia & Gong (2020), in the sense that it combines bagging and feature/label flipping. In this sense, it could be viewed as a more incremental paper. However the authors should be credited for the derivation of the certificate, which was quite complex in the bagging/flipping setting. Another benefit of their method is that it encompasses both triggerless and backdoor threat models.

*Quality*

I was generally impressed by the quality of the paper, although I was not able to check the derivations in Sections 5 and 6 carefully. It was good to see a variety of datasets were tested in the experiments, as the conclusions did vary in some cases.

*Significance*

The proposed method (BagFlip) seems to perform similarly to Bagging (Jia, Cao & Gong, 2021) for triggerless attacks in regimes where the certified accuracy remains reasonably high (e.g. above 70%). Given this observation, it’s not clear whether BagFlip should be preferred over Bagging. For instance, if the smoothing operation and certificate for BagFlip is significantly more computationally demanding, then BagFlip may not be preferred. It would be interesting to investigate this further, e.g. by comparing the computational cost of BagFlip versus baselines. 

*Clarity*

I enjoyed reading the paper. Sections 5 and 6 were somewhat challenging to read, but that is probably unavoidable due to the complexity of the analysis. 
questions: Is there a reason why the flipping approach by Wang, Cao, Jia & Gong (2020) was not considered as a baseline in the experiments?

In Section 7.2, BagFlip is not found to be effective against backdoor attacks for CIFAR10 and EMBER. Are the authors able to speculate why BagFlip doesn’t work for the higher-dimensional datasets?

I noticed the use of a superscript “?” in line 171 and elsewhere. Is that intentional?
limitations: These are discussed adequately in Section 8.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper presents BagFlip, a model-agnostic certified approach that utilizes bagging and randomized smoothing to defend against various types of poisoning and backdoor attacks. This paper formulates the theoretical way to compute the certified radius of BagFlip and ways to speed up the computation. This paper evaluates BagFlip in various settings to show its effectiveness. 
strengths_and_weaknesses: Strengths:

+ Strong attack model. 
+ This paper provides a certified guarantee in defending against backdoor attacks. 
+ The threat model and the goals are formulated clearly. 

Weaknesses:
- Potential runtime problem. Could authors provide empirical evaluations for the running time?

- The explanations of experimental results are unclear. When compared with bagging, the same k is used for both bagging and BagFlip. However, BagFlip adds additional Gaussian noise to the k training examples. Therefore, the noise added by BagFlip is larger than bagging. As a result, the normal accuracy for bagging is higher compared with BagFlip. Could authors use a smaller k for bagging such that bagging and BagFlip have similar normal accuracy? Given the similar normal accuracy, we can compare the robustness of the two methods. This is also applicable in the comparison to FeatFlip and RAB.
questions: See above.
limitations: See above.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The article proposes a model-agnostic certified method to handle data-poisoning attacks that maliciously modify the training dataset. The article addresses trigger-less and backdoor attacks, and solves them with a noising/smoothing approach on training datasets. The proposed method was evaluated on image and malicious portable executable datasets including MNIST, CIFAR10, and EMBER, and showed robust accuracy in trigger-less and backdoor attacks, respectively.
strengths_and_weaknesses: (strength)
The article is well-structured, easy-to-follow. The proposed method (BagFlip) is technically sound.
(weakness)
The proposed method was compared only for a limited control group (FeatFlip[35] and RAB[39]). Considering that FeatFlip[35] proposed a randomized smoothing strategy, the technical novelty of the proposed method is weak.

questions: 1. Section 7.2 describes the differences in the proposed method compared to FeatFlip. However, considering that FeatFlip proposed a randomized smoothing strategy, utilizing additional noise to cope with trigger-less attack seems like a minor modification of FeatFlip. Compared to FeatFlip, what is the technical novelty of the proposed method?
2. While it is true that inductive learning approaches (including machine learning and deep learning) are being explored, many malware detection software is still based on traditional search/traverse algorithms based on signatures. In terms of malware detection, are data poisoning attacks observed in the real world?

limitations: The proposed method uniformly flips features and labels regardless of data distribution.
review_title: null

Meta-review: metareview: The paper proposes a new method for certified defense against data poisoning, in both trigger-less and backdoor scenarios. The method augments previous work (Bagging) with random flipping of labels. The latter enables computation of probabilistic certificates, although this results in a huge computational overhead. Various relaxation techniques are proposed to improve the computational burden, bringing the cost to just one order of magnitude "above" the baseline. Experiments show reasonable improvement of defense strength compared to the baselines, although the computational cost remains an issue. Apart from its incremental character and the computational complexity, the method is well executed and theoretically sound.  
confidence: Less certain
Decision: Accept