Towards Robustness Certification Against Universal Perturbations
Authors: Yi Zeng
Zhouxing Shi
Ming Jin
Feiyang Kang
Lingjuan Lyu
Cho-Jui Hsieh
Ruoxi Jia
Venue: ICLR 2023 poster (2023)
Keywords: Universal Perturbation
Adversarial Attack
Backdoor Attack
Certified Robustness
Poisoning Attack

Abstract: In this paper, we investigate the problem of certifying neural network robustness against universal perturbations (UPs), which have been widely used in universal adversarial attacks and backdoor attacks. Existing robustness certification methods aim to provide robustness guarantees for each sample with respect to the worst-case perturbations given a neural network. However, those sample-wise bounds will be loose when considering the UP threat model as they overlook the important constraint that the perturbation should be shared across all samples. We propose a method based on a combination of linear relaxation-based perturbation analysis and Mixed Integer Linear Programming to establish the first robust certification method for UP. In addition, we develop a theoretical framework for computing error bounds on the entire population using the certification results from a randomly sampled batch. Aside from an extensive evaluation of the proposed certification, we further show how the certification facilitates efficient comparison of robustness among different models or efficacy among different universal adversarial attack defenses and enables accurate detection of backdoor target classes.

Published as a conference paper at ICLR 2023
TOWARDS ROBUSTNESS CERTIFICATION AGAINST UNIVERSAL PERTURBATIONS
Yi Zeng * Zhouxing Shi *2, Ming Jin', Feiyang Kang', Lingjuan Lyu',
Cho-Jui Hsieh² and Ruoxi Jia'
Virginia Tech, Blacksburg, VA 24061, USA University of California, Los Angeles, CA 90095, USA Sony AI, Tokyo, 108-0075 Japan
ABSTRACT
In this paper, we investigate the problem of certifying neural network robustness against universal perturbations (UPs), which have been widely used in universal adversarial attacks and backdoor attacks. Existing robustness certification meth- ods aim to provide robustness guarantees for each sample with respect to the worst-case perturbations given neural network. However, those sample-wise bounds will be loose when considering the UP threat model as they overlook the important constraint that the perturbation should be shared across all samples. We propose a method based on a combination of linear relaxation- analysis and Mixed Integer Linear Programming establish the first robust certi- fication method for UP. In addition, we develop a theoretical framework for com- puting error bounds on the entire population using the certification results from a randomly sampled batch. Aside from an extensive evaluation of the proposed certification, we further show how the certification facilitates efficient comparison of robustness among different models or efficacy among different universal adver- sarial attack defenses and enables accurate detection of backdoor target classes.
perturbation
INTRODUCTION
As deep neural networks become prevalent in modern performance-critical systems such as self- driving cars and healthcare, it is critical to understand their failure modes and performance guaran- tees. Universal perturbations (UPs) are an important class of vulnerabilities faced by deep neural networks. Such perturbations can fool a classifier into misclassifying any input from given distri- bution with high probability test time. Past literature has studied two lines of techniques to create UPs: universal adversarial attacks (Moosavi-Dezfool
et al., 2017) and backdoor attacks (Gu et al., 2019; Chen et al., 2017). The former crafts a UP based on a trained model and does not rely on access to training data. The latter, by contrast, prespecifies pattern training data so that adding the pattern (often known as the trigger in backdoor attack literature) will change the output of the trained classifier into attacker desired target class.
UP and further alters the
Many defenses have been proposed for both universal adversarial attacks (Akhtar & Mian, 2018; Dezfooi et al., 2017; Shafahi et al., 2020; Benz al., 2021; Liu al., 2021) and backdoor attacks (Wang et al., 2019; Chen et al., 2019; Guo et al., 2019; Borgnia et al., 2020; Qiu et al., 2021). But empirical evaluation with attacks does not provide a formal guaran- tee on the robustness as it is infeasible for an attack algorithm to provably cover all con- cerned perturbations. In contrast, robustness certification aims verify the output bounds of the model given certain class of input perturbations and provably certify the robustness against all the concerned perturbations. Although several recent works (Weber al., 2020; Xie et al., 2021) developed techniques to achieve certified robustness of classifier against backdoor-attack- induced UPs with certain norm bound. However, these techniques apply to specific learn- ing algorithms and require the knowledge of the training data. It remains an open question:
How to certify the robustness of a trained model against class of UPs in way that is agnostic to the underlying training algorithm and data, and is general for different UPs (including both universal adversarial attacks and boundddddded backdoor attacks)?
"Thouxing Shi and Yi Zeng contributed equally. Corresponding Yi Zeng, Lingjuan Lyu Ruoxi Jia. Work partially done during Yi Zeng's 's internship at Sony AI.

---

Published as a conference paper at ICLR 2023
In this paper, we propose framework to certify the worst-case classification accuracy batch of test samples against --n---ooooudeeee UPs. Our approach builds off of past works for certify- ing robustness against sample-wise perturbations that are independently added to each sample. For efficient verification, many recent works linearly relax nonlinear activation functions in neural net- works into linear bounds and then conduct linear bound propagation to obtain the output bounds for the whole model (Wong& & Kolter, 2018; Wang et al., 201 8b; Dvijotham et al., 2018; Zhang et al., 2018; Singh et al., 2019b). This process also referred as linear perturbation analysis (Xu al., 2020a). Since the worst-case model accuracy against sample-wist wise perturbations is lower bound of the worst-case aceuracy against UPs, these certification techniques could be applied to obtain a certificate against UPs. However, direct application would overlook the important constraint that a UP is shared across different inputs, thereby producing overly conservative certification results.
Unlike sample-wise perturbations, UPs require theoretical reasoning to generalize certification re- sults. This is because UPs are applied to any input from the data distribution, and our main interest lies in the expected model accuracy over the entire data distribution against UPs. However, certifi- cation procedures can only accept a batch of samples from the distribution and certify the accuracy over the samples. Therefore, it's crucial to understand the discrepancy between certified robustness computed from samples and the actual population robustness.
We summarize contributions follows:
We formulate the problem of robustness certification against UPs. We then generalize linear relaxation based perturbation analysis (LiRPA) to UPs, and further propose Mixed Integer Linear Programming (MILP) formulation over linear bounds from LiRPA, obtain tighter certification on the worst-case accuracy of given model against UPs within a -norm ball".
We establish a theoretical framework for analyzing the generalizability of the certification results based on random sampled subsets to the entire population.
We conduct extensive experiments to show that our certification method provides certified lower bounds on the worst-case robust accuracy against both universal adversarial attacks and lac bbounded backdoor attacks, which are substantially tighter than results by directly applying existing sample-wise certification.
We also investigate the implications of robustness certification on UPs to facilitate easy comparisons of robustness among different models or the efficacy of empirical defenses, and to achieve reliable identification of backdoor target classes.
2 BACKGROUND AND RELATED WORK
Universal Adversarial Perturbation Neural networks are vulnerable to adversarial exam- ples (Szegedy et al., 2014), which has led to the development of universal adversarial perturba- tions (UAPs), a same noise can consistently deceive a target network on most images (Liu et al., 2019; 2020). Existing defenses against UAPs include fine-tuning on pre-computed UAPs (Moosavi- Dezfooli et al., 2017), post-hoc detection (Akhtar et al., 2018) 8). universal adversarial training with online UAP generation (Mummadi et al., 2019; Shafahi et al., 2020; Benz et al., 2021). However, all existing defenses to UAPs are empirical works without efficacy guarantee to new attacks.
Backdoor Attacks backdoor attacks, attackers plant a predefined UP (a.k.a. the trigger) in the victim model by manipulating the training procedure (Li et al., 2020c). Attacked models can give adversarially-destie
outputs for any input patched with the trigger while still show good perfor- mance on clean inputs. Existing defenses include: poison detection via outlier detection (Gao al., 2019; Chen et al., 2018; Tran et al., 2018; Zeng et al., 2021) which rely on the modeling of clean samples' distribution; poisoned model identification (Xu et al., 2019; Wang al., 2020b); trojan removal via trigger synthesising (Wang et al., 2019; Chen et al., 2019; Guo et al., 2019; Zeng et al., 2022a), or preprocessing and fine-tuning; (Li et al., 2020b; Borgnia et al., 2020); robust training via differential privacy (Du et al., 2019) or redesigning the training pipeline (Levine & Feizi, 2020; Jia et al., 2020; Huang et al., 2022: Li et al., 2021). As all these defenses were empirical, existing literature has revealed those empirical defenses' limitations to zero-day attacks or adaptive attacks (Zeng et al., 2022b).
Robustness Certification of Neural Networks Early robustness certifications (Katz et al., 2017; Ehlers, 2017: Tjeng et al., 2017) largely relied on satisfiability modulo theory (SMT) or integer
httpp::/ thub. com/ wwoo/ruoxi-ii jia
http://oooiil---rroouuuuiieeeeee www.ooguuuuuuuraaaaaarrae Caarruuiiieeer______eeeee Pert_Cert
2

---

Published as a conference paper at ICLR 2023
linear programming (ILP) solvers are were limited to very small networks. For more efficient ver- ification, bound propagation with convex relaxations has been proposed (Wong & Kolter, 2018; Wang et al., 2018b; Zhang al., 2018; Weng et al., 2018; Singh et al., 2019b; Salman et al., 2019), which over-approximates nonlinear activations with convex relaxation and propagates the bounds layer by layer to finally bound the entire model. Xu al. (2020a) proposed bound propagation framework for general computational graphs and referred to the related methods as linear relaxation based perturbation analysis (LiRPA), as activations are relaxed by linear bounds. Bound propagation methods have also been further enhanced with techniques such as saanch-nnd-bourd (Bunel et al., 2018: 2020; Wang et al., 201 8a;b; Xu et al., 2020b; Wang et al., 2021), multi-neuron relaxation and cutting planes (Singh et al., 2019a; Ferrari et al., 2021; Zhang et al., 2022a) for tighter results at a cost of efficiency. However, these works are developed for sample-wise perturbations, and they cannot directly produce tight certification against universal perturbations. Besides, there are several randomized smoothing (Cohen et al., 2019) based methods for certified robustness against backdoor attacks (Weber et al., 2020; Wang et al., 2020a; Xie et al., 2021; Zhang et al., 2022b). These are stochastic methods and are usually considered orthogonal to deterministic certification. Moreover, they require access training data, only applicable some specific learning algorithms (e.g.. binary models or federated learning) and not general for other UPs, such as UAPs.
METHODOLOGY
3.1 PROBLEM FORMULATION
On a set of n independent samples {2(1) ..... 2(0) from the data distribution Q where 2(0) = (x:; y1) is the i-th example, x; (x, E R4) is the input and y/ is the ground-truth label, we aim to certify the robustness of a K-way neural network classifier J Bd + R against potential universal perturbation with lo norm constrained as || I c. In particular, we aim to certify and lower bound the worst-case accuracy of the neural network on (2() (z.,)..., 2())] for any universal perturbation d (1lo) S E) applied to all the examples:
Ei min |6
1 min dein(mm..de (mg.s(x; + +0) > 0). 3F
(1)
1=1
where [ + +6) = - (x; + 6) [z(x, 0) is the margin between the ground-truth class y and incorrect class j + yi. and the indicator checks whether the margin is positive for any 1 y: when a perturbation 5 is added. It is NP-hard to exactly verify Eq. (1) even for n = 1 and a small ReLU network (Katz et al., 2017). Thus recent neural network verifiers usually compute lower bound for the margin as my.. (x: 5) S m + 6), and then we can replace m in Eq. (1) with m to lower bound Eq. (1) and this bound also serves as a lower bound for the robustness.
(x;
3.2 LINEAR PERTURBATION ANALYSIS W.R.T. A UNIVERSAL PERTURBATION
We adopt linear relaxation based perturbation analysis (LiRPA) from previous works which focused on sample-wise perturbations, "auto LiRPA" (Xu et al., 2020a) specifically, to obtain lower bounds on ( + 5) represented as linear functions w.r.t. the universal perturbation 5. but it is also feasible to use other verification frameworks such as Singh et al. (2019b); Wang et al. (2018b). auto LiRPA can bound the output of a computational graph when its input nodes are perturbed, and it can produce linear functions w.r.t. the perturbed inputs nodes as linear bounds. Note that margin functions can be appended to the original neural classifier as the output of the computational graph, and thereby the margins can be bounded. When sample-wise perturbations are considered in previous works, the linear bounds can usually be written as
(x,
(8) (x: + +) +5, (1) a
Vi E [n], Vj 4 Mi V|] S E, myn (x; + 8)
(2)
(4) where a.) and by are coefficients and biases in the linear bounds. This is achieved by relaxing
nonlinear functions such as activation functions in the network with linear bounds and propagating
linear coefficients through the computational graph. The hight-hand-side (RHS) of Eq. (2) is linear
function w.r.t. (x,+ +)). To obtain a final bound represented as a concrete number without relying on
the 5 variable, a concretization step can be applied on the RHS given the constraint on ||0|| which
(i) eliminates the 5 variable and lower bounds the RHS as A (6) (xx+0)+ 2 -ella
(2) || + x,
(6)
(6)
3

---

Published as a conference paper at ICLR 2023
However, the aforementioned concretization step considers the worst-case ő for each sample in- dependently but a universal perturbation should be shared across all the examples. Thereby will produce relatively loose and over-conservative results under the universal perturbation setting, as the perturbations are much stronger when each example can take an independent perturbation respectively compared single and universal perturbation for all the examples.
In contrast, we propose to obtain tighter certification for universal perturbation. Unlike Eq. (2), we use auto LiRPA to compute the linear lower bound with respect to instead of (x; + +6) by treating ō as a perturbed input node and x; as fixed input node in the computational graph:
(6) Vi E [n]. Vj + V/a V/l S my (x, + 6) 2 aj 8+b
(3)
new coefficients and biases in the linear bound, and x; does not appear the RHS as it is fixed. In the next section, we will lower bound the worst-case accuracy Eq. (1) by solving MILP problem based Eq. (3).
( where a and b
3.3 AN MILP FORMULATION TO LOWER BOUND THE WORST-CASE ACCURACY
In this section, we use linear bounds in Eq. (3) to compute a lower bound for the worst-case accuracy in Eq. (1). Specifically, by replacing each my..j in Eq. (1) with its lower bound from Eq. (3), we lower bound Eq. (1) by solving the following problem:
n
minimize
min j#
8 +++b a
(0 }0)
s.t. 1 S.
(4)
Now, we show that Eq. (4) can be rewritten into an MILP formulation:
Theorem 1. Problem Eq. (4) equivalent to the following MILP problem:
minimize 0
n1
8.1.
0
(5)
i=1
We [m]. 1 E (0,1), -7(1 01 $ Σ
a 8 b 1)0)) (0)
(0)
S (
(6)
j7%
Wi [m]. Vj + ya $j E 1), Σ 1
(7)
Ei [n], Vi + yı, Vj2 # Ui, (a)
(1) 1j
-
7(1
(1) < (a))
(9)
(8)
|101l0= Sc,
(0) 8 b0 is a sufficient large constant. where 7 2 maxig[m) Ej a
In Theorem 1, given a universal perturbation 6, for the i-th example, integer variable g()) E {0, 1} denotes whether the the model is certifiably correct this example based on linear bounds from Eq. (3), and the certified accuracy on the whole batch can be computed as Eq. (5). The model is (8)
certifiably correct the i-th example when ( 5) 2 aj + b > 0 holds for all j * yi- [0. to denote whether class j is the hardest among all j # y/ 5 holds, which is enforced by Eq. (8). We require each example to have exactly one hardest class j with s
(8)
We use integer variable $)
a) (8) under the ceritification, i.e., Vj * yı.
S L 5 (0)
(see Eq. (7)); in case that there are multiple classes with an equal lower bound on the margin function, it is valid to treat any of (i)
them as the hardest. Then only need to check whether a) 5 b
(t) 0 holds for the hardest class ( > 0. In Eq. (6), as is sufficiently large, only (0)
j with (1) 1, equivalently Σj (a) 8 +b,)) ())))s() Ejtu. required when (6) O. Note that if exactly Ejjn, (a) 8 + b )s}
(a) ( 8 ( )s (1) 0 effectively required when (i) 1, and Ejvu. (a ( 5 b ())))
(i) (t) 0 happens, (6) will
be taken by MILP due the minimization objective, and thus is still compatible with our goal
4

---

Published as a conference paper at ICLR 2023
for checking aj 8 bb, > O. Overall the MILP formulation minimizes the certified accuracy over
all possible universal perturbation 8 (1 S e), finally produce lower bound for Eq. (I). We formally prove this theorem in Appendix A.I, and we use Gurobi (Bixby, 2007) to solve the MILP.
Although it is possible solve the whole certification algorithm through MILP (Tjeng al., 2017), it will be computationally prohibitive. Even for very small networks with thousands of neurons, the number of integer variables in their MILP formulation will be proportional the number of neurons. In contrast, by computing linear bounds first before solving MILP, the number of integer variables in our formulation is only proportional to the number of samples in batch and the number of classes, and it does not depend on the size of the network, which makes it feasible in practice.
4 GENERALIZATION OF UNIVERSAL PERTURBATION
In the previous section, we proposed our robustness certification method against UPs. Note that the certification results are only guaranteed for the given batch of samples till now. In this section, study how the certified accuracy computed on a batch approximates the certified accuracy computed on the entire data distribution.
Let (+) be a random sample drawn from probability space F,),, which is endowed with a a-- algebra F and a probability measure P.. A dataset D, & {2(1), ..... (n))) consists of n observations random point in
drawn independently from 52 according to IP; equivalently can be considered (Ω" F², ),",, which is the n-fold Cartesian product of S2 equipped with the product o-algebra F and the product pm P.....X
Let A denote the Loc ball that contains all allowable perturbations
times
A {ò |00 I e} with radius e. And let B Ω R(++1jK be a linear bound generation procedure, and for each = (x, y), it returns parameters (ay, by of the linear lower bounds on the margins. i.c., my.j (x + 8) 2 a (x 8) + by. In the proposed framework, B is instantiated to be auto LiRPA (Xu et al., 2020a). Let A,, RR (d+1))Kn + A denote the MILP in Eq. (4), which return a perturbation d given the linear bounds on the margins. The overall certification procedure is the composition of An and B, denoted by G = An B An 8
For every data sample =(x,v) E E we define the set
1 = 8 A
min (2, (,
as the set of perturbations such that the margin between the ground-truth class and any other class is certifiably positive according to the linear bounds provided by B, i.e., the model is certifiably robust to any perturbation in this set, but it is still possible for the model to be robust to a perturbation d & A. Note that the dependence of the on B has been made explicit because ay by depend on B. Similarly, we define the set
m m ( +6) > >0)
min jFy
as the set of all perturbations that are incapable of fooling the given model f. i.c., the data æ is actually robust to any perturbation this set. Note that Å is a superset of A and unlike A does not depend on the linear bound generation procedure. We make the following definitions:
Definition 1. The certified robust probability (CRP) of a given perturbation d A based on linear bound generation procedure B is defined as
VB( A Pl 8 A The actual robust probability (ARP) of a given perturbation E is defined as
(10)
( 2 P(z E Q: : 8 Σz).
(11)
The certified robust rate (CRR) of a perturbation E A on an evaluation dataset D,, based on linear bound generation procedure B is
2 1 Σ 1(8 AP).
(B: D.)
(12)
n
5

---

Published as a conference paper at ICLR 2023
Equivalently, we write the objective of Eq. (4) as minses (6: D,). A can be equivalently defined by the existence of a binary variable as in the MILP formulation in Theorem and is thus
nonconvex in general. In the following, we use (B (0) for (5; D,)) if the evaluation dataset is Dr for notational simplicity. Note that (5) S (() for any ó A and the equality is attained when the equality in (3) is attained, i.e., the lower bound generated by B exactly matches the actual margin any 8. Now we present the following theorem that estimates the value of ARP based on the CRR computed from a batch of random samples.
Theorem ((1 - ))-probable certification for ARP). Given G = An o B. and O < < 1, for any any 5, it holds that
pm ((()) min U.()"))((()))) - -V8 (100 )
2 21-6.
(13)
BEA
where (S, n)) is the root of the equation (1 + In(1 + 46) 4t 1 In((E/E) and to (E, n) is a monotonically decreasing function in n and 8 = arg ming (6). Moreover, have that
pd
U(6)
min SEA
BB
(E.
2 1 11-6.
(14)
The proof can be found in Appendix A.2. Both bounds interesting to interpret. The bound Eq. (13) shows that the discrepancy between the ARP of any perturbation and the
1.0
E 0.01
0.8
8 0.05
2.66
{
CRR (i.e., the certified accuracy on a random batch) de- pends on (66)) V (8+) and t (E, Given the trained model and the underlying data distribution, 8* is fixed; hence, the term U(8*)= VBB depends on the tightness of linear bounds produced by B3 The tighter bounds B can provide, the smaller difference there will be between (6*) and (8*). This bound suggests that plugging tighter linear bound generation techniques into certification framework can potentially give rise to better approximation error. It is also interesting to note that the approximation error of the proposed certification framework g AA, B exclu- sively depends on B, not An. This is because An always returns the optimal solution to the MILP, thereby not introducing any additional error. The second term 1" (", n) depends samples for certification and it vanishes as the n grows (illustrated in Figure 1). The second bound (Eq. (14)) utilizes the fact that U(6))= - (88) Z O, and is more relaxed but more convenient than the first bound (Eq. (13)) because the lower bound of the ARP can be calculated given the certification results on a batch, the number of samples in the batch, and the confidence level 5.
0.0
5
10
25
50
100
200
500
1000
Figure 1: tt t", m) vs. n.
the number of
In the Section 5.2, we will showcase the estimation of the ARP using this bound.
EXPERIMENT
5.1 EXPERIMENTAL SETUP
For evaluating the certification, we consider two benchmark datasets, MNIST (LeCun et al., 1998) and CIFAR-10 (Krizhevsky et al., 2009), widely adopted in existing works. We adopt model structures from existing works (Singh et al., 2019a; Tjandraatmadja et al., 2020; Wang et al., 2021; Müller et al., 2022; Zhang et al., 2022a): Conv-small, Conv-4-layer, Conv-big on MNIST, and ResNet-2B, ResNet-4B on CIFAR-1O, with details in Appendix B. We use the CRR and attack- ACC (accuracy under an attack) as the metrics. All the results are averaged over three runs with different random seeds on 100 random samples for each dataset. Further experimental details can be found in Appendix B.
5.2 EVALUATION
Comparing to existing robustness certification We first focus on evaluating our certification re- sults compared to existing robustness certification for sample- wise perturbation. There several competitive frameworks such as Singh et al. (2019b); Bunel et al. (2020); Henriksen & Lomus- cio (2021), and we compare with auto LiRPA (Xu et al., 2020a) specifically for its state-of-the-a

---

Published as a conference paper at ICLR 2023
Table 1: Certification results naturally trained MNIST models (CRR %).
4-layer
Coav-big
Samplc-Wise
Ours
Gample-Wise
Ours
Sample- Wise
Ours
4/255
94,00
3.74
25.00.12.94
93.331287
35.3311.25
41.6713.44
65.3316660
6/255
80.67
6818
86.33 14.50
69.00
78.6743.68 52.016.68
6.67-42.9 0.0010.00
8.67133.09
8/255
6.23
63.3345.25
40.67.6.13
0.0010.00
Table 2: Certification results on PGD-32 adversarially trained MNIST models (CRR %).
Conv-small
Comy-4-layed
Cony-big
Sample- 94.67=1.25
Ours
Sample- Wise
Ours
Sample. Wise
Ours
16/255 32/255
15.33111.70 44.3349.39
96.67-1.447 $4.33:10447
97.0010:00 67.022.16
69.6711.70 0=00
70.67:1.70
34.67=5.31
0=:
Table 3: Certification results on PGD-8 adversarially trained CIFAR- 10 models (CRR %).
ResNet-2B
ResNett-B
Sample-Wiss
Sampls-Wisc
Ours
1/255
43.33#2.62
06.33:0.94 33.0011441
51.00+3.77
54.67=4.03 0.0010.000
3/255
28.67.12.05
0.00.10.00
performance (Bak et al., 2021). We consider models from both natural training and adversarial training. For MNIST, we evaluate the two certification methods on models naturally trained, and PGD-32 (PGD with &o norm 253 the results on naturally trained MNIST models. Our method provides much tighter bounds than sample-wise certification results across all the settings. Table 2 illustrates results on PGD-32 trained MNIST models. With adversarial training, we observe the certified robustness of the models against UPs also largely increased compared naturally trained models in Table 1. Our certification results are still much tighter than sample-wis results especially under settings with larger perturbations. On CIFAR-10, and ResNet-4B) as the naturally trained model is severely susceptible to perturbations on CIFAR-10 (see Figure 5) even with 255 To sum up, our method can provide tighter robustness certification than existing sample-wise methods.
32 adversarially trained models (Madry et al., 201 8). Table details
only evaluate the results adversarially trained models (PGD-8 for ResNet-2B
Estimation of the lower bound of ARP Figure 2 illustrate the application of Theorem 2 with CRR. We use the naturally trained
1.0
Bchust Rate
0.8
Conv-4-layer on MNIST as an example and we set e 255 We demonstrate the estimation of 0.9-probable certification for the lower bound of ARP, or ARP, by setting & = 0.1. From Figure 2, we can learn that the empirical results, CRR, can be tighter when more samples are considered in certification. Incorporating more samples also makes the estimated ARP much closer to the CRR (as t5, n) is smaller). Such an observation shows that when incorporating more samples in certification, the empirical results would better reflect the actual robustness of the whole population. In particular, when using 1000 samples, the result can be interpreted the ARP is larger than 84.73% with at least 90% probability.
0.6)
0.2
Estimattc Al2 Chn
0.0
50 500 1960
Figure 2: Different numbers of samples vs. the lower bound of ARP, i.e., ARP, (Conv-4-layer, 6
MNIST, at c 255 & = 0.1).
Validating with UAP attacks We then val- idate the robustness certification results with
CRR
Adv-UAP
CoS-UAP
DF-UAP
100
100
100
UAP attacks as CRR should lower bound the
ACC (90)
80
8D
80
60
60
60
ACCsck-ACCs. We consider three SOTA UAP attacks: Adv-UAP (Li et al.. 2022), Cos- UAP (Zhang et al., 2021a), and DF-UAP (Zhang et al., 2020), detailed in Appendix B. Figure 3 compares CRR and atCack-ACCs on PGD-32 trained MNIST models. As shown in Figure 3, CRRs are indeed lower than all the attack-ACCs as expected.
40
40
40
0
60 90
0
30 60
0
30 60
Value of x 255
Value of x 255
Value of x 255
Conv-small
Conv-4-layer
Conv-big
(PGD-32)
(PGD-32)
(PGD-32)
Figure 3: CRRs vs. UAP-attacked ACCs (MNIST, PGD-32 trained models).
Validating with backdoor attacks We also validate whether CRR still lower bounds the attack- ACCs in backdoor attacks. We consider two backdoor triggers namely a blended trigger (Chen et al., 2017) with small -nom [| 255.
5 referred the stealthy trigger), and the BadNets (Gu
7

---

Published as a conference paper at ICLR 2023
Cleen
Trojened
Attack's
Clean
Tunnd-Tre/an
Scratch-Trajan
Steathyy Trigger
(%6)
100
Stamtard Frigger Value of x 255
CRR (%)
80
88888
60
Poisoned Sample
Trigger
01234567
Pobsoned Sample
Trigger 255/255
5255 (519)
Value of E 255
Figure 4: Visual examples of the backdoor poisoned samples, the triggers, and certified UP-ACCs (Conv-small, MNIST). We magnified the stealthy trigger 51 for visualization.
et al., 2019) (10] = 255
755 ). All the attacks utilize the same poison ratio, 20% following existing works (Zeng et al., 2021). The visual example of the poisoned sample, the triggers, and the certifi- cation results are listed in Figure 4. Under the setting of the stealthy blended backdoor, we find that the CRR drops dramatically before reaching the trigger's norm (fjöl 255) compared to the same model trained on clean MNIST. This observation verifies the correctness of CRR and its potential to reveal stealthy lox -buunded backdoor attacks in the current trend of backdoor development with smaller 4x -norm constraints, e.g., Zeng et al. (2022b); Zhao et al. (2020). However, assuming an &p norm bound of the backdoor triggers is not widely accepted in traditional backdoor settings. Thus, 255 in Figure 4. We consider the backdoor also present the results of BadNets (with ||ō||c 255
model trained from scratch or fine-tuned from the clean model. The CRR is still nower-bounding the attack's deployed foc bound of the trigger. However, as the trigger has large foo norm, the CRRs of poisoned models are of no difference to the clean model and thus not that useful. Nevertheless, in Section 5.3, we show simple twist of the certification framework to help reveal backdoors' existence.
5.3 IMPLICATIONS OF ROBUSTNESS CERTIFICATION AGAINST UPs
Now we explore the potential implications of our robustness certification against UPs. We focus on 3 case studies model structure comparison, UAP defenses comparison, and backdoor detection.
Comparing model structures One impli-
cation of robustness certification regarding UPs is to compare different model structures and training strategies regarding the certified robustness against UPs. Figure 5 depicts the certification results of all the considered model structures with different training set- tings on MNIST and CIFAR- 100 We con- sider both naturally trained and PGD trained models with different to perturbation norm. In Figure 5 (a) MNIST, find that the largest model, Conv-big, shows the worst certified robustness against UPs. But the smallest Conv-small's CRR is higher than that of Conv-4-layer under naturally trained setting, PGD-8, and PGD-16, but not PGD- 32. The only difference between Conv- small and Conv-4-layer is that Conv-4-layer uses larger padding step which resulting a slightly larger hidden layer (see Appendix B). Based on the observation, there is an interesting trade-off between model size and certified robustness against UPs: A slightly larger structure can help the model obtain better certified robustness when adopting adversarial training, potentially due to increased model capacity. Such an observation can be further illustrated in Figure 5 (b). Specifically, ResNet-2B's CRR would drop to random guessing when using PGD-16, while ResNet-4B can still maintain a certain scale of CRR. But even larger models Figure& (a) have worse certified robustness, potentially due to looser certified bounds.
Comy
Coes-kaaeer
+ Cony- big
CHR PS)
100
100
100
100
50
80
80
MNIST Volue C 255
Value
255
Value of 255
Value 6 255
Normal Training
PGD-8
PGD-16
PGD-32
@3CIFRR- 10
Rectee
Recket
CAR qu
80
-0
20
20
20
Value # 755
Value 755
Value 755
Walue
Figure 5: CRR comparison with different training set- tings and structures on (a) MNIST and (b) CIFAR-10. PGD-8, PGD-16, and PGD-32 stand for PGD training with Ego norm 255
16 32 respectively.
253 255
Implication to UAP defenses Another implication of the CRR is to compare existing UAP defenses regarding their efficacy. We consider three types of defenses and five different defenses in total: FGSM and PGD sample-wise adversarial training (Goodfellow al., 2014; Madry al., 2017;
8

---

Published as a conference paper at ICLR 2023
Table UAP defenses at [8|
(ResNet-4B. CIFAR-10).
255
Normal
FGSM
PGD
UAT-FGSM
UAT-PGD
IBP
Ori-ACC
99.03
98.97
98.88
98,99
98,99
98.66
CRR
0.3340.47
27.33=5.91
30.67+6.34
24.00+0.82
28.99+2.99
95 66+2.55
DE-UAP
98, 98.94:0.04
98.91=0.01
98 08.4400.02
98.82+0.08
9% 94.9400004
9% 62
Cos-UAP
98.62=0.15
98.87=0.06
98.82+0.02
98. 08.88400008
98.89+0.02
98.59+0.03
Ady-UAP
98.96:0.04
98. 98.94
98. 08.8660.02
98.89+0.02
98. 96+000000
98. 68.6840000
Worst
10.4120.15
-0.1020.06
-0.0640.02
-0.1740.08
-0.1020.02
+.05500.03
Wong et al., 2019); universal adversarial training (UAT) with FGSM or PGD synthesizing UPs (Shafahi et al., 2020); sample-wise certified defense with Interval Bound Propagation (IBP) training (Gowal et al., 2018; Mirman et al., 2018). The defended models are further evaluated with UAP attacks and certification. The results with small perturbation radius |0|30 255
shown in Table 50 are in Table 7, Appendix C. We 4. Additional results with a larger perturbation radius (o0 255
16
use the row titled "Worst" to record the maximum accuracy drop using UAP attacks compared to clean accuracy, Surprisingly, in Table 4, we find the CRR of models trained with UAT is worse than their sample-wist adversarial training counterparts (i.e., UAT-PGD results are worse than PGD). However, in the case of larger perturbation radius (Table Appendix O), the UAT-trained models can achieve higher CRR than the sample-wise counterparts. Such an observation indicates an under- explored trade-off between perturbation radius and UAP defense method on CRR. The CRR result from the IBP-trained model is much tighter than others, IBP directly optimizes for certified robustness and tightens the certified bounds for all the neurons. Moreover, CRR is also aligned with the worst attacked accuracy drop and can be an indicator for comparing different settings of UAP defenses.
objective
Implication to backdoor defenses We evaluated the effectiveness of the CRR in revealing potential backdoors in the above
CAR 1%
300
100
100
100
80
80
80
80
60
60
60
60
40
40
40
section, but the effectiveness is yet only limited to triggers with small perturbations. This section presents a simple twist on the certification framework by teaming up with adversarial training (PGD-16). We depict the average class-wise certification results on 10 ResNet-4B models trained with dif- ferent random seeds over different BadNets poison ratios in Figure 4. Based on the re- sults, we find the certification can reliably reveal the targeted label and justify how mighty the backdoor attack is (i.e., the CRR is aligned with the poison ratio used). Additional results on the Smooth attack (Zeng et al., 2021) and &2 invisible attack (Li et al., 2020a) are listed in Appendix C, which share similar observations. The reason of the successful identification that, naturally, the adversarial training would force the model to learn more from the reliable features and thus make standard backdoors stand out from benign features of the data (i.e., easier to be learned by the model), as also discussed in Weng et al. (2020). Thus after training a model with adversarial training with large perturbation radius, the model would likely engrave the trigger and thus have a high CRR only on the target label. CRR by our proposed method provides an intriguing point of view to determine the attack's strength (i.e., poison ratio).
20
20
20
20
01234567
01234567
02234567
01234567
Value e 255
Value of x
Value 255
Value of X 255
Poi-Ratio:0%
1%
5%
20%
Figure 6: CRRs on adversarial-trained models over CIFAR-10 10 datasets that contains a different ratio of poi- sons (BadNets, target label is 0). Different class in- dexes depicted with different colors listed the top.
CONCLUSION
In this work, we present the first focused study on certifying neural networks' robustness against UPs. In contrast to previous robustness certification works that focused on sample-wise perturba- tions, we formulate the certification problem against UPs by emphasizing sharing a universal per- turbation between different samples. We propose combination of linear relaxation-based bounds and MILP to solve the problem. We also present a theoretical analysis framework to estimate the certification result for the entire population based on results from a batch of random samples. Ex- tensive experiments reveal that our certification imposes tighter results than directly applying exist- ing sample-wist wise robustness certifications. In addition, certification against UPs could facilitate comparing certified robustness between different model structures and defense methods and provide reliable backdoor detection.
discuss and demonstrate how robustness

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGEMENT
This work is partially funded by Sony AI. This work is also supported in part by NSF under IIS- 2008173, IIS-2048280, and by Army Research Laboratory under W91 19F-200--2-01 RJ and the ReDS lab appreciate the support of The Amazon Virginia Tech Initiative for Efficient and Robust Machine Learning and the Cisco Award. YZ and ZS are both supported by the Amazon Fellowship.
REFERENCES
Naveed Akhtar and Ajmal Mian. Threat of adversarial attacks on deep learning in computer vision: A survey. leee Access, 6:14410-14430, 2018.
Naveed Akhtar, Jian Liu, and Ajmal Mian. Defense against universal adversarial perturbations. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 3389- 3398, 2018
Stanley Bak, Changliu Liu, and Taylor Johnson. The second international verification of neural networks competition (ynn-comp 2021): Summary and results. arXiv preprint urXiv:2109.00499 2021.
George Bennett. Probability inequalities for the sum of independent random variables. Journal of the American Statistical Association, 57(297):33 45, 1962.
Philipp Benz, Chaoning Zhang, Adil Karjauv, and In So Kweon. Universal adversarial training with class-wise perturbations. In 2021 IEEE International Conference on Multimedia and Expo (ICME), pp. 1-6. IEEE, 2021.
Bob Bixby. The gurobi optimizer. Transp. Re-search Part B, 41(2)1159-178, 2007.
Eitan Borgnia, Valeriia Cherepanova, Liam Fowl, Amin Ghiasi, Jonas Geiping, Micah Goldblum, Tom Goldstein, and Arjun Gupta. Strong data augmentation sanitizes poisoning and backdoor attacks without an accuracy tradeoff, 2020.
Tom B Brown, Dandelion Mané, Aurko Roy, Martín Abadi, and Justin Gilmer. Adversarial patch. arXiv preprint 1 2017.
Rudy Bunel, llker Turkaslan, Philip H. S. Torr, Pushmeet Kohli, and Pawan Kumar Mudigonda. A unified view of piecewise linear neural network verification. In Advances in Neural Information Processing Systems, pp. 4795-4804, 2018.
Rudy Bunel, P Mudigonda, llker Turkaslan, P Torr, Jingyue Lu, and Pushmeet Kohli. Branch and bound for piecewise linear neural network verification. Journal of Muchine Learning Research, 21(2020). 2020.
Nicholas Carlini and David Wagner. Towards evaluating the robustness of neural networks. In 2017 ieee symposium on security and privacy (sp), pp. 39-57. IEBE, 2017.
Bryant Chen, Wilka Carvalho, Nathalic Baracaldo, Heiko Ludwig. Benjamin Edwards, Tacsung Lee, Ian Molloy, and Biplav Srivastava. Detecting backdoor attacks on deep neural networks by activation clustering. arXiv preprint 181 1.03728, 2018
Huili Chen, Cheng Fu, Jishen Zhao, and Farinaz Koushanfar. Deepinspect: black-box trojan detection and mitigation framework for deep neural networks. In IJCAI. volume 2, pp. 8, 2019.
Xinyun Chen, Chang Liu, Bo Li, Kimberly Lu, and Dawn Song. Targeted backdoor attacks on deep learning systems using data poisoning, 2017.
Jeremy M. Cohen, Elan Rosenfeld, and J. Zico Kolter. Certified adversarial robustness via random- ized smoothing. In International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 1310-1320, 2019.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Fei-Fei Li. Imagenet: A large-scall scale hi- crarchical image database. In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR). pp. 248-255, 2009. doi: 10. 10.11090VPR22200022656
10

---

Published as a conference paper at ICLR 2023
Min Du, Ruoxi Jia, and Dawn Song. Robust anomaly detection and backdoor attack detection via differential privacy. arXiv preprint arXiv:1911.0711, 2019.
Krishnamurthy Dvijotham, Robert Stanforth, Sven Gowal, Timothy A. Mann, and Pushmeet Kohli. A dual approach to scalable verification of deep networks. In Proceedings of the Thirty-Fourdh Conference on Uncertainty in Artificial Intelligence, UAI 2018, Monterey, California, USA, Au- gust 6-10, 2018, pp- 550-559, 2018
Ruediger Ehlers. Formal verification of piece-wise linear feed-forward neural networks. In Interna- tional Symposium on Automated Technology for Verification and Analysis, pp. 269-286, 2017.
Claudio Ferrari, Mark Niklas Mueller, Nikola Jovanović, and Martin Vechev. Complete verification via multi-neuron relaxation guided branch-and -nd--ndd--- In International Conference on Learning Representations, 2021.
Yansong Gao, Change Xu, Derui Wang, Shiping Chen, Damith C. Ranasinghe, and Surya Nepal. Strip: defence against trojan attacks on deep neural networks. In ACSAC '19, pp. 113-125. Association for Computing Machinery, 2019. ISBN 9781450376280. doi: 10.1 10.1145/3359789. 3359790.
Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. arXiv preprint arXiv:1412.6572, 2014.
Sven Gowal, Krishnamurthy Dvijotham, Robert Stanforth, Rudy Bunel, Chongli Qin, Jonathan Ue- sato, Relja Arandjelovic, Timothy Mann, and Pushmeet Kohli. On the effectiveness of interval bound propagation for training verifiably robust models. arXiv preprint
2018.
Tianyu Gu, Kang Liu, Brendan Dolan -avitt,, and Siddharth Garg. Badnets: Evaluating backdooring attacks on deep neural networks. IEEE Access, 7:47230-4720 47244, 2019.
Wenbo Guo, Lun Wang, Xinyu Xing, Min Du, and Dawn Song. Tabor: A highly accurate approach to inspecting and restoring trojan backdoors in ai systems. arXiv preprint arXiv:1908.01770 2019.
Patrick Henriksen and Alessio Lomuscio. Deepsplit: An efficient splitting method for neural net- work verification via indirect effect analysis. In IJCAI, pp. 2549-2555, 2021.
Kunzhe Huang, Yiming Li, Baoyuan Wu, Zhan Qin, and Kui Ren. Backdoor defense via decoupling the training process. In ICLR, 2022.
Jinyuan Jia, Xiaoyu Cao, and Neil Zhenqiang Gong, Intrinsic certified robustness of bagging against data poisoning attacks, 2020.
Guy Katz, Clark Barrett, David L Dill, Kyle Julian, and Mykel Kochenderfer. Reluplex: An efficient smt solver for verifying deep neural networks. In International conference on computer aided verification, pp. 97-117. Springer, 2017.
Soheil Kolouri, Aniruddha Saha, Hamed Pirsiavash, and Heiko Hoffmann. Universal litmus patterns: Revealing backdoor attacks cnns. Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 301-310, 2020.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, (11):2278-232) 1998.
Alexander Levine and Soheil Feizi. Deep partition aggregation: Provable defense against general poisoning attacks, 2020.
Maosen Li, Yanhua Yang, Kun Wei, Xu Yang, and Heng Huang. Learning universal adversarial perturbation by adversarial example. 2022.
11

---

Published as a conference paper at ICLR 2023
Shaofeng Li, Minhui Xue, Benjamin Zhao, Haojin Zhu, and Xinpeng Zhang. Invisible backdoor attacks on deep neural networks via steganography and regularization. IEEE Transactions on Dependable and Secure Computing, 2020a.
Yige Li, Xixiang Lyu, Nodens Koren, Lingjuan Lyu, Bo Li, and Xingjun Ma. Neural attention distillation: Erasing backdoor triggers from deep neural networks. In International Conference on Learning Representations, 2020b.
Yige Li, Xixiang Lyu, Nodens Koren, Lingjuan Lyu, Bo Li, and Xingjun Ma. Anti-backdoor learn- ing: Training clean models on poisoned data. NeurIPS, 34, 2021.
Yiming Li, Baoyuan Wu, Yong Jiang, Zhifeng Li, and Shu-Tao Xia. Backdoor learning: A survey. arXiv preprint arXiv:2007.0877 2020c.
Aishan Liu, Xianglong Liu, Jiaxin Fan, Yuqing Ma, Anlan Zhang, Huiyuan Xie, and Dacheng Tao. Perceptual-sensitiee gan for generating adversarial patches. In Proceedings of the AAAI confer- ence on artificial intelligence, volume 33, pp. 1028-1035, 2019.
Aishan Liu, Jiakai Wang, Xianglong Liu, Bowen Cao, Chongzhi Zhang, and Hang Yu. Bias-based universal adversarial patch attack for automatic check-out. In European Conference Computer Vision, 2020.
Aishan Liu, Xianglong Liu, Hang Yu, Chongzhi Zhang, Qiang Liu, and Dacheng Tao. Training robust deep neural networks via adversarial noise propagation. IEEE Transactions on Image Processing, 2021.
Alcksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. arXiv preprint arXiv:1706.0660 2017.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In International Conference on Learning Representations, 2018.
Matthew Mirman, Timon Gehr, and Martin Vechev. Differentiable abstract interpretation for prov- ably robust neural networks. In International Conference Machine Learning, pp. PMLR, 2018.
Seyed-Mohsen Moosavi-Dezfone Dezzool,,,,,, Alhussein Fawzi, Omar Fawzi, and Pascal Frossard. Universal adversarial perturbations. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 1765-1775 2017.
Mark Niklas Müller, Gleb Makarchuk, Gagandeep Singh, Markus Püschel, and Martin Vechev. Prima: general and precise neural network certification via scalable convex hull approximations. Proc. ACM Program. Lang., 6(POPL):1-33 2022.
Chaithanya Kumar Mummadi, Thomas Brox, and Jan Hendrik Metzen. Defending against universal perturbations with shared adversarial training. In Proceedings of the IEEE/CVF International Conference Computer Vision, pp. 4928 4937, 2019.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high- performance deep learning library. NeurIPS, 32:8026 (01668807,20000 2019.
Han Qiu, Yi Zeng, Shangwei Guo, Tianwei Zhang, Meikang Qiu, and Bhavani Thuraisingham. Deepsweep: An evaluation framework for mitigating dnn backdoor attacks using data augmen- tation. In Proceedings of the 2021 ACM Asia Conference Computer and Communications Security, pp. 363-377, 2021.
Hadi Salman, Greg Yang. Huan Zhang, Cho-Jui Hsieh, and Pengchuan Zhang. A convex relaxation barrier to tight robustness verification of neural networks. Advances in Neural Information Processing Systems, pp. 9832-993222 2019.
12

---

Published as a conference paper at ICLR 2023
Ali Shafahi, Mahyar Najibi, Zheng Xu, John Dickerson, Larry S Davis, and Tom Goldstein. Uni- versal adversarial training. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 5636-5643, 2020.
Zhouxing Shi. Yihan Wang, Huan Zhang, Jinfeng Yi, and Cho-Jui Hsieh. Fast certified robust training with short warmup. Advances in Neural Information Processing Systems, 34:18335- 18349, 2021.
Gagandeep Singh, Rupanshu Ganvir, Markus Püschel, and Martin Vechev. Beyond the single neu- convex barrier for neural network certification. Advances in Neural Information Processing Systems, 32, 2019a.
Gagandeep Singh, Timon Gehr, Markus Püschel, and Martin Vechev. An abstract domain for cer- tifying neural networks. Proceedings of the ACM on Programming Languages, 3(POPL):41, 2019b.
Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. In ICLR, 2014.
Christian Tjandraatmadja, Ross Anderson, Joey Huchette, Will Ma, Krunal Kishor Patel, and Juan Pablo Vielma. The convex relaxation barrier, revisited: Tightened single-neuron relaxations for neural network verification. Advances in Neural Information Processing Systems, 33:21675- 21686, 2020.
Vincent Tjeng, Kai Xiao, and Russ Tedrake. Evaluating robustness of neural networks with mixed integer programming. arXiv preprint arXiv:1711.07356, 2017.
Brandon Jerry Li, and Aleksander Madry. Spectral signatures in backdoor attacks. In Advances in Neural Information Processing Systems, pp. 8000-8010, 2018.
Binghui Wang, Xiaoyu Cao, Neil Zhenqiang Gong, et al. On certifying robustness against backdoor attacks via randomized smoothing. arXiv preprint arXiv:2002. 17550, 2020a.
Bolun Wang, Yuanshun Yao, Shawn Shan, Huiying Li, Bimal Viswanath, Haitao Zheng, and Ben Y Zhao. Neural cleanse: Identifying and mitigating backdoor attacks in neural networks. In 2019 IEEE S&P, pp. 707-723, IEEE, 2019.
Ren Wang, Gaoyuan Zhang, Sijia Liu, Pin- Yu Chen, Jinjun Xiong, and Meng Wang. Practical detection of trojan neural networks: Data-limited and data-free cases. In Computer Vision ECCV 2020: 16th European Conference, Glasgow, UK, August 23-28, 2020, Proceedings, Part XXIII 16, pp. 222-238. Springer, 2020b.
Shiqi Wang, Kexin Pei, Justin Whitehouse, Junfeng Yang, and Suman Jana. Efficient formal safety analysis of neural networks. In Advances in Neural Information Processing Systems, pp. 6369- 6379, 2018a.
Shiqi Wang, Kexin Pei, Justin Whitehouse, Junfeng Yang, and Suman Jana. Formal security analysis of neural networks using symbolic intervals. In 27th {USENIX) Security Symposium ( ((USENIX) Security 18), pp. 1599-1614, 2018b.
Shiqi Wang, Huan Zhang, Kaidi Xu, Xue Lin, Suman Jana, Cho-Jui Hsieh, and Zico Kolter. Beta-crown: Efficient bound propagation with per-neuron split constraints for neural network robustness verification. Advances in Neural Information Processing Systems, 34:29909-29921, 2021.
Maurice Weber, Xiaojun Xu, Bojan Karlaš, Ce Zhang, and Bo Li. Rab: Provable robustness against backdoor attacks. arXiv preprint wrXiv:2003.08904 2020.
Cheng-Hsin Weng, Yan- Yan-Ting Lee, and Shan- Hung Brandon Wu. On the trade-off between adver- sarial and backdoor robustness. Advances in Neural Information Processing Systems, 33:1 1973- 11983, 2020.
13

---

Published as a conference paper at ICLR 2023
Tsui- Wei Weng, Huan Zhang, Hongge Chen, Zhao Song. Cho-Jui Hsich, Luca Daniel, Duane S. Boning, and Inderjit Dhillon. Towards fast computation of certified robustness for relu net- works. In International Conference Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 5273-5282, 2.18.
Eric Wong and J. Zico Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. In International Conference on Machine Learning, volume 80 of Proceed- ings of Machine Learning Research, pp. 5283-5292, 2018
Eric Wong, Leslie Rice, and Zico Kolter. Fast is better than free: Revisiting adversarial training. In International Conference on Learning Representations, 2019.
Chulin Xie, Minghao Chen, Pin-Yu Chen, and Bo Li. Crfl: Certifiably robust federated learning
against backdoor attacks. In International Conference on Machine Learning, pp. 11372-11382. PMLR. 2021.
Kaidi Xu, Zhouxing Shi, Huan Zhang, Yihan Wang, Kai-Wei Chang, Minlie Huang, Bhavya Kailkhura, Xue Lin, and Cho-Jui Hsieh. Automatic perturbation analysis for scalable certified robustness and beyond. Advances in Neural Information Prucessing Systems, 33:1 129-1141,, 2020a.
Kaidi Xu, Huan Zhang. Shiqi Wang, Yihan Wang, Suman Jana, Xue Lin, and Cho-Jui Hsieh. Fast and complete: Enabling complete neural network verification with rapid and massively parallel incomplete verifiers. arXiv preprint arXiv:2011.13894 2020b.
Xiaojun Xu, Qi Wang, Huichen Li, Nikita Borisov, Carl A Gunter, and Bo Li. Detecting trojans using meta neural analysis. arXiv preprint arXiv:1910.03133 2019.
Matthew D Zeiler. Adadelta: an adaptive learning rate method. arXiv preprint arXiv:1212.5700 2012.
Yi Zeng, Won Park, Z Morley Mao, and Ruoxi Jia. Rethinking the backdoor attacks' triggers: A frequency perspective. In ICCV, 2021.
Yi Zeng, Si Chen, Won Park, Zhuoqing Mao, Ming Jin, and Ruoxi Jia. Adversarial unlearning of backdoors via implicit hypergradient. ICLR, 2022a.
Yi Zeng, Minzhou Pan, Hoang Anh Just, Lingjuan Lyu, Meikang Qiu, and Ruoxi Jia. Narcissus: A practical clean-label backdoor attack with limited information. arXiv preprint arXiv:2204.05255, 2022b.
Chaoning Zhang, Philipp Benz, Tooba Imtiaz, and In So Kweon. Understanding adversarial exam- ples from the mutual influence of images and perturbations. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 14521-14530, 2020.
Chaoning Zhang, Philipp Benz, Adil Karjauv, and In So Kweon. Data-free universal adversarial perturbation and black-box attack. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 7868-7877, 2021a.
Huan Zhang, Tsui-Wei Weng, Pin- Yu Chen, Cho-Jui Hsieh, and Luca Daniel. Efficient neural net- work robustness certification with general activation functions. In Advances in Neural Information Processing Systems, 4954-4953, 2018.
Huan Zhang, Shiqi Wang, Kaidi Xu, Linyi Li, Bo Li, Suman Jana, Cho-Jui Hsieh, and J Zico Kolter. General cutting planes for bound woandd-poaggtton-aaae neural network verification. arXiv preprint arXiv:2208.057400 2022a.
Quan Zhang, Yifeng Ding. Yongqiang Tian, Jianmin Guo, Min Yuan, and Yu Jiang. Advdoor: adversarial backdoor attack of deep learning system. In Proceedings of the 30th ACM SIGSOFT International Symposium on Software Testing and Analysis, pp. 127-138, 2021b.
Yuhao Zhang, Aws Albarghouthi, and Loris D' Antoni. Bagflip: A certified defense against data poisoning. arXiv preprint arXiv:2205. 13634, 2022b.
14

---

Published as a conference paper at ICLR 2023
Shihao Zhao, Xingjun Ma, Xiang Zheng, James Bailey, Jingjing Chen, and Yu- Yu-Gang Jiang. Clean- label backdoor attacks on video recognition models. 2020 CVPR, pp. 14431-14440. IEEE Computer Society, 2020.
Table 5: Table of Notations.
Notation
Definition
Notation
Definition
dimensionality of the impult number ouiput classes ncural network classifier clean data sample with index sample 2ffiss inpert feature sample sff''s label, yu e (L...., X} cemificationn procedure, returns worst-case
space of possable data,
universal perurbation,
space satisties the norm-coestriins f norm of the universal perturbation, 2:
J:R - R
249 (8
Norm- constraint on the universal perturbation. i.c. |dlp I e bound of the margin from di to bias term of the linear lower bound of margin from şi to set perturbations incagable fooling the classifter sample
X, RR
19
cnefficients the linear
19 R
yi E
A0: A
A PROOFS
A.1 1 PROOF OF THEOREM 1
Let i be the solution of the MILP problem in the theorem, and i be the solution to Eq. (4).
Theorem states that 1 = J. We formally prove the equivalence below.
Proof. We first show that 1 < Ô. In Eq. (4), there exists some å such that
8 arg min
(in
min シサツ
(3)
(
>0).
2=1
Then, for every E [n]. take the following values for variables in the MILP formulation:
gi)
min {a.) (2)8+b,0}>>)) }0)
j73
0 = 1 Σ (0)
(0) jj)='',, where j' = arg min argmin a (88 +b), Vj + yi, 8)
jæy.
and it is easy to see that the values for these variables satisfy all the constraints in the MILP problem. Thus the result of the minimization in the MILP should be no smaller than á, i.e., 0 <
We now show that 1 < 3. We use 8. $ to denote the values of q, s variable in the solution of MILP. For every E [n]. Eq. (7) ensures that there exists exactly one 3 ( * ys) with s(9) 1, and
(i)
(3) holds. Thus
Eq. (8) ensures that for all j * yi. a
S
a
Σ
(a 1 86b )000
min jzy.
1 8 bb,
According to Eq. (6), if (0) = 1, Σ ビッ (a)
00 8 by 1
> 0 holds. In case that Ejøn. (a) (28 +
b )(()))))))) = 0, Eq. (6) also holds with ((0)= = 0. and due to the minimization objective of MIIP,
git) = 0 instead of ((+) = 1 will be taken. Thus Σj (a + by ) > 0 strictly holds when
g(o) = 1. And if g(t) = 0, Σ johnn
) (1) < 0 holds. Thus
min (a (2) 1 > 0). J7
909 Σ
a
+
17
Thereby
1
(1) 8 + b b,9) > 00)
3
q
min a
11
T=1
and then the result of Eq. (4) is no smaller than ô, i.e., ē < 3.
Hence à 1 is proved.
15

---

Published as a conference paper at ICLR 2023
A.2 PROOF OF THEOREM 2
Let 8 = arg minses U()) be the optimal universal perturbation that minimizes the ARP, let on be the value returned by x)Dx), and let å = arg minses V that minimizes the CRP. We introduce the following lemma:
Lemma 1. Given An, it holds that
P" P" -8 > (E, S
(15)
where t' (c, is the root of the equation (1 46) In(1 4t) 4t In(1/E).
Proof. Let ql =666= E AB 200) which can also be interpreted ming { faf08 8 + +b,b D,0 >
0). Then, (78(8*) - (6) and (8 1 [8]] B[q Let 0² denote the variance of ( Since gl is a binary random variable, we have that o² z 1/4. Let h(w) = (1 u) In(1 u) For any > 0, we have that
) E[g (0)
> t) S exp
-nooh 02
(16)
1=1
12 (- h(44))
I exp
(17)
where the first inequality a direct application the Bennett's inequality (Bennett, 1962), and the second inequality is due to the fact that no /3 is monotonically decreasing function of 0² Let t(e,n) denote the root of exp ( h4t)) Then, follows that IP (P E g() E[g (), E.
Then we prove Theorem 2 to certify the robustness of a classifier against the worst-case attack 5*.
Proof. We use the following relations: for any & A,
U()) 2 min (8)
U()*)
U(8*) - VV + (78))-8((888) + (88(88))
( (3,)) + + (18))
(18)
(4))
(1) + (ii) V (8.),,
where (ii) can be bounded by applying the concentration inequality in Lemma 1; (1ii) due the optimality of 8, arg minsea B (8)) Combining these bounds yields Theorem 2.
B FURTHER DETAILS ON EXPERIMENTAL. SETTINGS
We one server equipped with total of 8 RTX A6000 GPUs as the hardware platform. PyTorch (Paszke et al., 2019) is adopted as the implementation framework. We detail the model structures used in our experiment Table All of the model structures used in this work were also considered in other existing robustness certification works as the standard set-ups: Conv-small, Conv-4-layer, Conv-big on the MNIST (Singh et al., 2019a; Tjandraatmadja et al., 2020; Wang et al., 2021: Müller et al., 2022), and ResNet-2B, ResNet-4B on the CIFAR-10 10 (Zhang et al., 2022a). We use Adadelta (Zeiler, 2012) as the optimizer with a learning rate set to 0.1 for all the model training process (including the adversarial training for the model updating step as well). For MNIST models, we train each model with 60 epochs. For CIFAR-10 1-0 models, we train each model with 500 epochs to ensure full convergence. For adversarial training adopted in the main text, the number of steps in PGD attacks 7; step-size for PGD is set as 4. For IBP training, we use the implementation in Shi al. (2021).
16

---

Published as a conference paper at ICLR 2023
Table 6: Model structures in our experiments. Conv [1, 16, 4) stands for conventional layer with input channel, output channels, and a kemel size of 4 x 4. (innea((1668, 100) stands for fully connected layer with 1568 input features and 100 output features. ResBlockk16,, 32) stands for a residual block with 16 input channels and 32 output channels. ReLU activation function is adopted between any two consecutive layers.
Model
Model structure
Conv-small (MNIST)
Couv(1, 16, 4) Conv(16, 32, 4) Linear 100) Linear( 10)
Conv-4-layer (MNIST)
Conv(1. 16, 4) - Conv(16, 32, 4) Linear(1566) 100) L.near(1000 10)
Conv-big (MNIST)
Conv(1, 32,3)
Conv(32, 32, 4) Conv (32, 64.3) Conv(64, 64,4) 4) Lincur(3136, 512)
Linear(512. 512) Limear(512, 10)
RosNet-2B (CIFAR- 10) ResNet-4B (CIFAR-IK 10)
Conv [3, 8, 3) ResBlock(S, (8, 16) ResBlock 16, 16)) Linear( 1021, 100) Linear 100, 10)
Conv(3, 16.3)
(csBlock(16.32 ResBlock(32, 32)) Linear (512, 100) Linear (100. 10)
Now, we details the UAP attacks considered in the experiment for validating the certification results, namely the Adv-UAP (Li et al., 2022). Cos-UAP (Zhang et al., 20)1a), and DF-UAP (Zhang et al., 2020). The design of each UAP attack's synthesis procedure distinguishes these attacks. Specifi- cally, Adv-UAP synthesizes and generates adversarial examples for each input before synthesizing the UAP, which has shown to be more effective finding stronger UAPs. Cos-UAL produces UAP by reducing the Cosine similarity between the original output logits and the disturbed logits; DF- UAP employs a similar loss as listed the C& W attack (Carlini & Wagner, 2017), which aims to reduce the distance between the ground-truth label's logits and the maximum logits of the rest.
Now we provide the detailed settings of the backdoor target-class identification in Section 5.3. For the threat model, we consider the scenario where the defender aims to determine if backdoor attack resides in a given dataset, identify the target class, and justify how potent the attack is there is identified attack. We assumes the defender has access to the training set be inspected, with no additional clean validation data required. To conduct the instantiated case shown in Section 5.3, the defender adversarially trains (with PGD-16) 10 different models on the inspecting training dataset and obtaining the averaging CRR results in a class-wise manner. Especially as we assume no additional clean validation data is required, we pass through 100 random noise into the certifying models to obtain the results in Figure 6, 7, 8.
C ADDITIONAL RESULTS
C.I ADDITIONAL RESULTS ON UAP DEFENSES COMPARISON
Table 7 details the results of UAP defenses comparison under the large-norm setting 255 ing all the defenses adopted are also incorporated with the same expense. For large-norm settings, we find that only the robusteess training ends up with a CRR larger than 0. Apart from its actual effectiveness, as mentioned in the main text, the IBP-trained model also ends up with much tighter intermediate linear bounds (i.e., a and b are tighter). Even though our work can only return a positive CRR on the IBP-trained model, the certification results are still aligned with the actual attack results, as the IBP-trained model would have stronger robustness than the other models in terms of the least change in the ACC drop.
80 Not-
Table 7: UAP defenses at 18 (ResNet-4B, CIFAR-10)
Normal
FGSM
PGD
CAT-GGMM
CAT-PG
IBP
OFi-ACC
99.03
98.94
98.75
99.20
99.02
96.04
CRR
0
40.67+4.11
DE-UAP
26.46:9.27
98. 1020.02
97.4020.05
98. 5620.07
08.45+0.02
94,8950.05
Cos-LAP
41.8=11.27
19.22=1.41
95.13=0.37
96.68+0.12
97.50=0.11
95.18=0.07
Ady-UAP
37.6947.51
97.93=0.10
97.36+0.03
98. 98.40=0.05
98.54+0.02
94,8320.05
Worst
-72.5749.27
-19,72=1.41
-3.62+0.37
-2.52+0.12
-1.52+0.11
-1.21
C.2 ADDITIONAL RESULTS ON BACKDOOR TARGET-CLASS IDENTIFICATION
We now provide additional results on implementing the certification framework to identify the ex- istence of backdoor attacks. In this section, the results provided are evaluated against the Smooth attack (Zeng et al., 2021) and the ig-invisible attack (Li et al., 2020a). Figure 7,8 illustrate the results on the Smooth attack and ly-invisble attack respecively. Based on the results, find the certifica- tion can also reliably reveal the targeted label and justify how powerful the backdoor attack is for Smooth attack and the ln-invisible attack.
17

---

Published as a conference paper at ICLR 2023
100
100
100
100
80
80
60
60
20
20
012 6
01234567
36
Poi-Ratio: 0%
1%
5%
20%
Figure 7: Certified UP-ACCs adversarial-traing madels over CIFAR-I0 datasets that contains different ratio of poisons (Smooth attack with the target label being set to 0) Different class indexes are depicted with different colors listed the top.
CAR (%)
100
100
40
40
40
20
20
20
20
0
01234567
01234567
01234567
0
Value of 255 Value of x 255
Value of 255 Value of 255
Pot-Ratio: 0%
1%
5%
20%
Figure 8: Certified UP-ACCs on adversarial -rainne models over CIFAR-IO datasets that contains a diffcrent ratio of poisons (l2-inv attack with the target label being set to Differre class indexes are depicted with different colors listed the top.
D BROADEN IMPACT AND LIMITATIONS
D.1 UAP AND BACKDOOR ATTACKS
UAP attacks aim synthesize UP by accessing and analyzing the output of a trained neural net- work. Backdoor attacks aim to insert a predefined trigger into the neural network and ensure an effective attack without accessing and analyzing the output after the model is trained over the poi- soned samples. Many existing works have found these two paralleled lines work have interesting intersections. In particular, the formulation of UAP synthesizing has also inspired or has its interest- ing counterparts in backdoor attacks or defense designs. For example, Li et al. (2020a); Zhang et al. (2021b) designed their backdoor trigger via similar process of synthesizing UAP using trained model. Kolouri et al. (2020); Zeng et al. (2022a) adopted this interesting intersection between UAP and backdoor attacks provide identification of backdoors or conduct online removal of backdoors. Suppose we view these two attack paradigms at the inference time (with a trained model). In that case, mitigation defenses and robustness synthesizing tools for both attacks can be developed for general robustness to UP.
D.2 LIMITATIONS
Unconstrained or Large -norm Attacks: Some of the UAP attacks are generated without spec- ifying constraint (Brown et al., 2017), and in most backdoor attacks, the trigger inserted does not have a constrained foo norm. the attack can have an unconstrained fox or a very large foc. norm, only trivial certification results be obtained from certification. This limitation also com- monly exists in state-of-the-ee art sample-wise certification methods (Wang et al., 2021; Ferrari et al., 2021). In fact, any certification procedure requires some constraints on potential perturbations and does not apply to unbounded perturbations. This open problem calls for answers and the attention for future research.
Computational Cost: Supporting large models and large datasets can be computationally costly for our certification. Existing works for certifying pre-trained models (Wang et al., 2021; Ferrari al., 2021) are also commonly limited to moderate-sized networks, and the cost of our method is lower bounded by existing linear bound propagation frameworks that we use obtain the linear bounds before solving the MILP problem. It remains challenging open-problem for scaling larger-scale networks, such as models for ImageNet (Deng et al., 2009).
18


Reviews:
[{"review_id": "wWeewi6Nff2", "reviewer": "Reviewer_GEmp", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper looks at a critical but rarely studied problem: the certification of robustness to Universal Perturbations (UPs). In particular, UPs (e.g., universal adversarial noise, backdoor, or neural trojan attacks) have become alarming lines of threats that make it hard to use Machine Learning as a service safely and reliably.\n\nThe authors formulated and solved the robustness certification for UPs utilizing a method based on linear relaxation and Mixed Integer Linear Programming. An intriguing discussion on the difference between existing sample-wise certification and the certification against UPs was provided. The authors also theoretically analyzed the relationship between the certification result based on observed samples and the actual robustness of neural networks to UPs w.r.t. the underlying distribution. Multi-perspective evaluations of the tightness (compared with existing certification), soundness of the bound (real UAP and backdoor attacks), and potential implications (to existing attacks and defenses) are offered.", "summary_of_the_review": "In summary, the authors study a promising robustness certification method against UPs, along with theoretical analysis and a thorough discussion of the implications to model structure, UAP attacks, and backdoor attacks. Some minor issues with the clarity of the settings and the discussion of the limitations should be further improved.", "strength_and_weaknesses": "Strength:\n\n1.\tThe paper is generally well-written and easy to follow, with a well-designed structure;\n\n2.\tThe problem of robustness certification to UPs is of great importance, and detailed implications to model/defense comparison and backdoor detection are discussed with empirical results;\n\n3.\tThe proposed method with MILP and linear relaxation accounting for establishing the information sharing between samples is intuitive but compelling; the tightness of the certification results is shown with a comprehensive study with existing certification techniques and actual attacks;\n\n4.\tTo the best of my knowledge, UP’s generalization analysis in this paper is the first of its kind effort, which also leads to an intriguing analysis of the error of certification results using the proposed robustness certification method.\n\nWeakness:\n\n1.\tSome settings of the experiment are unclear. For example, I think the settings for the Implication to backdoor defenses (i.e., the backdoored class identification) can be further improved with more details on the threat model and how to use the proposed tool for detection regarding existing backdoor attacks.\n\n2.\tI can understand the difficulties of the robustness certification to large neural networks or large datasets, especially the problem of certifying against UPs requiring computing w.r.t. multiple samples (it seems it is required to compute a much larger computational graph when the network size and input size grow). I highly recommend the authors add a section discussing these limitations.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "uKiAsZTZyr8", "reviewer": "Reviewer_e7K7", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper focused on exploring and extending linear-relaxation-based sample-wise robustness certification to evaluate the robustness of trained neural networks against Universal Perturbations (UPs). The authors pointed out an interesting intersection between universal adversarial perturbations (UAPs) and backdoor triggers. They showcased how the robustness certification to UPs of neural networks can impact these two lines of effort. The theoretical contribution evaluates the generalizability of the effects of the UPs computed using observed samples to unseen data populations. Detailed empirical evaluation regarding multiple perspectives of the proposed method is presented on two standard computer vision benchmarks (MNIST and CIFAR-10) regarding five different model structures (Conv-small, Conv-4-layer, Conv-big, ResNet-2B, and ResNet-4B)", "summary_of_the_review": "This work resides at the interesting crossroads of UAP and backdoor attacks. The authors presented a novel certification methodology for UP-robustness together with a theoretical study of the result's generalizability. With empirical findings, the implications of this work are discussed in detail. This work has a number of intriguing technical/empirical findings that could lead to future work on backdoor defenses, UAP defenses, and more advanced robustness certification for these threats.", "strength_and_weaknesses": "Strength:\n\n1. This paper focused on a critical problem, certifying the robustness of neural networks to UPs;\n2. The paper is well-written. I enjoyed reading this work;\n3. A clear structure for recognizing the road map of existing work in UAPs, backdoors, and robustness certification, which facilitates readers to position this work in an interesting intersection between UAP attacks and backdoor attacks;\n4. Interesting and solid technical efforts. Given the lack of theoretical analysis in existing UAP and backdoor attacks, the proposed theoretical analyzing framework in this paper gives an interesting first attempt toward a better understanding of neural networks' robustness against these two types of threats;\n5. Interesting experimental design. In particular, the author thoroughly evaluated the proposed UP certification and compared it with existing sample-specific certifications, and validated the results with three actual UAP attacks and two types of backdoor attacks. They also devised the theoretical efforts in practice and studied three implications of UP-robustness certification;\n\nWeaknesses:\n\n1. I find the intersection/similarity/difference between UAP attacks and backdoor triggers extended in this work quite interesting. Apart from the current related work section, I highly recommend the authors add a discussion to talk about the similarity/difference between these two lines of threats. Especially some of the recent work in the backdoor literature utilize this interesting intersection for stronger attack efficacy and better stealthiness [1,2] or effective defenses [3].\n2. I find most of the experimental settings well-detailed, except for the backdoor target-class identification experiment (Section 5.3). Please add more details to the threat model and the availability of the defender's knowledge, e.g., data accessibility.\n3. There is a limitation when using the proposed method to compare different UAP defenses regarding large norms (Table 7, Appendix C.1), i.e., all the results except the result on the IBP-trained model are trivial. I encourage the authors to add discussions on this limitation.\n\nReferences\n\n[1] Zhang, Quan, et al. \"AdvDoor: adversarial backdoor attack of deep learning system.\" Proceedings of the 30th ACM SIGSOFT International Symposium on Software Testing and Analysis. 2021.\n\n[2] Zeng, Yi, et al. \"NARCISSUS: A Practical Clean-Label Backdoor Attack with Limited Information.\" arXiv preprint arXiv:2204.05255 (2022).\n\n[3] Kolouri, Soheil, et al. \"Universal litmus patterns: Revealing backdoor attacks in cnns.\" Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2020.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "ILcr4-NeI3g", "reviewer": "Reviewer_wZWn", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a certification defense against universal adversarial\nexamples and backdoor attacks. The proposed method is based on the combination\nof linear relaxation-based perturbation analysis and Mixed Integer Linear\nProgramming. It also provides a theoretical framework for analyzing the\ngeneralizability of the certification results. Experiments demonstrate that it\nis better than existing sample-wise certification methods when defending\nagainst UAPs.", "summary_of_the_review": "My main concern is the novelty might be limited, and the claim that the\nproposed method can be applied to certify the robustness against backdoor\nattacks might not be well supported.", "strength_and_weaknesses": "Strengths\n\n· Interesting topic and good motivation.\n· The proposed method has better results than sample-Wise certification.\n· The writing is good.\n\nWeaknesses\n\n· The novelty might be limited.\n· It's unclear if the proposed method can be applied to certify the robustness\nagainst backdoor attacks.\n· Comparisons with some related works are missing.\n· Generalization of the proposed method is unclear.\n· Experiments on adversarial patch attacks are missing.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "B3eBmV0t7l", "reviewer": "Reviewer_Kpjw", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper studies the verification of neural networks against universal\nadversarial perturbations, i.e., perturbations that are universally applied on\na set of images. It solves the verification problem by adapting bound\npropagation- and MILP-based verification methods to  universal perturbations.", "summary_of_the_review": "Whilst the paper is the first to study the verification problem for neural\nnetworks and  universal adversarial perturbations, the resulting method is\nhighly incremental to previous work and the soundness of the comparisons with\nrelated work is not convincing.", "strength_and_weaknesses": "+ The paper is the first to the best of my knowledge to discuss the formal\nverification of universal perturbations.\n\n+ The paper includes an analysis of the generalisation of robustness results\nfrom samples to the entire data distribution.\n\n- The verification method is a straightforward adaptation of existing methods. \n\n- Unsound comparison with bound propagation-based methods: whereas the\n  certified robust rate for the bound propagation methods is taken as the rate\n  of images for which a model is robust, said rate for the current method is\n  being minimised in an MILP formulation.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster