A Branch and Bound Framework for Stronger Adversarial Attacks of ReLU Networks
Authors: Huan Zhang
Shiqi Wang
Kaidi Xu
Yihan Wang
Suman Jana
Cho-Jui Hsieh
J Zico Kolter
Venue: ICLR 2022 Submitted (2022)
Keywords: adversarial attack
branch and bound
adversarial robustness
deep neural network

Abstract: Strong adversarial attacks are important for evaluating the true robustness of deep neural networks. Most existing attacks find adversarial examples via searching in the input space, e.g., using gradient descent. In this work, we formulate an adversarial attack using a branch-and-bound (BaB) procedure on ReLU neural networks and search adversarial examples in the activation space corresponding to binary variables in a mixed integer programming (MIP) formulation. This attack formulation can be used to tackle hard instances where none of the existing adversarial attacks can succeed. Existing attacks using this formulation rely on generic solvers which cannot exploit the structure of neural networks and also cannot utilize GPU acceleration, so they are mostly limited to small networks and easy problem instances. To improve its scalability and practicability, we propose a top-down beam-search approach to quickly identify the subspace that may contain adversarial examples. The search utilizes the bound propagation based neural network verifiers on GPUs to rapidly evaluate a large number of searching regions, which is not possible in generic MIP solvers. Moreover, we exploit the fact that good candidates of adversarial examples can be easily found via gradient based attacks, and build an adversarial candidates pool to further guide the search in activation space via diving techniques. Additionally, any candidate adversarial examples found during the process are refined using a bottom-up large neighbourhood search (LNS) guided by the candidates pool. Our adversarial attack framework, BaB-Attack, opens up a new opportunity for designing novel adversarial attacks not limited to searching the input space, and enables us to borrow techniques from integer programming theory and neural network verification to build stronger attacks. In experiments, we can successfully generate adversarial examples for hard input instances where existing strong adversarial attacks fail, and outperform off-the-shelf MIP solver based attacks in both success rates and efficiency. Our results further close the gap between the upper bound of robust accuracy obtained by attacks and the lower bound obtained by verification.

Under review as a conference paper at ICLR 2022
A BRANCH AND BOUND FRAMEWORK FOR STRONGER ADVERSARIAL ATTACKS OF RELU NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
Strong adversarial attacks are important for evaluating the true robustness of deep neural networks. Most existing attacks find adversarial examples by searching the input space, e.g., using gradient descent, and may miss adversarial examples due to non-convexity. In this work, we search adversarial examples in the activation space of ReLU networks, which allows a systematic search of adversarial exam- ples and can tackle hard instances where none of the existing adversarial attacks succeed. Unfortunately, searching the activation space typically relies on generic mixed integer programming (MIP) solvers and is limited to small networks and easy problem instances. To improve scalability and practicability, we use branch and bound (BaB) with specialized GPU- bound propagation methods, and propose a top-down beam-search approach to quickly identify the subspace that may contain adversarial examples. Moreover, we build an adversarial candidates pool using cheap attacks to further assist the search in activation space via diving techniques and a bottom-up large neighbourhood search (LNS). Our adversarial attack framework, BaB-Attack, opens up new opportunity for designing novel adversarial attacks not limited to searching the input space, and enables us to bor- row techniques from integer programming theory and neural network verification build stronger attacks. In experiments, we can successfully generate adversar- ial examples for hard input instances where existing strong adversarial attacks fail, and outperform aff-the-shelf MIP solver based attacks in both success rates and efficiency. Our results further close the gap between the upper bound of robust accuracy obtained by attacks and the lower bound obtained by verification.
INTRODUCTION
Adversarial attacks aim to find adversarial examples (Szegedy et al. 2013), which are close to benign inputs in certain distance metrics yet trigger wrong behavior of neural networks (Carlini & Wagner) 2017 Madry et al., 2018 Athalye et al. 2018 Croce & Hein 2020b). Adversarial attacks are
important tools gauge the empirical robustness of deep neural networks. Finding an adversarial
example can be generally formulated as a constrained optimization problem:
Fady
arg min fx:
#EC
where C is often an Eoo or & norm ball around the original input zo, and f(z) is attack success criterion involving a neural network (such as the margin between the groundtruth class and another class): f(x < 0 indicates successful attack. A straightforward way of solving Eq. (1 is via first- order constrained optimization methods, such as projected gradient descent (PGD) Madry et al. Tashiro et al.) 2020 Croce & Hein 2020a;] Xie et al., Additionally, some gradient- frree attacks were pro-
2018) and its variants (Croce & Hein 2020b
2019 Dong et al.] [0188] Zheng al.) 2019
posed (Brendel et al. 2018 Cheng et al. 2018 Alzantot et al. 2019 Andriushchenko et al. 2020).
mostly based on certain heuristic search on the input space x.
Limitations of existing attacks. As f(x usually consists of a highly non-convex neural network, solving Eq. (1) to its global minimum is challenging. This leads to failures in adversarial attacks: an adversarial example may exist but no attacks can find it, giving false sense of security (Athalye al. 2018). Especially, gradient based attacks can be easily trapped into local minimum or misguided by masked gradients (Papernot et al., 2016 Tramer et al. 2017). Even if we give the attacker an infinite amount of time (e.g., run a very large number PGD steps, allowing large number of samples on input space), it is still hard to guarantee to find the adversarial example, since

---

Under review as a conference paper at ICLR 2022
it is extremely difficult to systematically search the high dimensional and continuous input space. Models concluded robust under existing attacks might still have security vulnerability in practice, leading to an urgent request for stronger attacks that can possibly approach ground-truth robustness.
The mixed-integer approach. This paper seeks stronger adversarial attacks from a different an- gle: instead of searching for adversarial examples in the input space, we look for adversarial ex- amples in the activation space. The main intuition that neural networks with piece-wise linear activation functions (e.g.. ReL.U) can be seen as piece-wise linear function and each piece is uniquely defined by a specific setting of activation function status. For ReLU networks, each neu- ron can either be active (its input is positive) or inactive (its input is negative so the output is 0), which can be encoded by discrete 0-1 variables. This leads to a mixed integer programming (MIP) formulation (Ehlers 2017), and Tjeng et al. (2019) conducted attacks using a MIP solver.
Benefits of the MIP formulation. The MIP formulation with the 0-1 encoding of ReLU neurons allows us to systematically search all the linear pieces in the input space, theoretically guarantee to enumerate the entire input space and obtain the global minimum of Eq. ( given sufficient time. Practically, MIP-based attacks can often find adversarial examples that are missed by existing attacks and identify true weaknesses of model. It also helps close the gap between the upper and lower bounds of robust accuracy (i.e., attack accuracy vs. verified accuracy). Existing works aimed to reducing this gap by tightening the lower bound with stronger verifiers (Raghunathan et al. [008bb] Wang et al. 2021). while our work aims to tighten the upper bound by a systematic search of adversarial examples. Closing this gap is difficult even on small models (Dathathri et al.. 2022))
Generic MIP solvers are inefficient for adversarial attacks. Despite its strengths, a MIP-based attack are often a few orders of magnitudes slower than existing attacks due to the high cost of running an off-the-shelf solver such as Gurobi (Tjeng et al. 2019). There are three root causes for its inefficiency. First, an off-the-shelf solver is not aware of the underlying optimization problem corresponds to a neural network, and has to apply generic solving techniques (c.g., using Simplex algorithm with relaxations) which can be expensive or ineffective. Second, it cannot utilize solutions obtained cheaply from gradient based attacks to accelerate its search. Third, generic MIP solvers are mostly restricted to CPUs and can hardly utilize GPU acceleration, which is crucial for efficiency.
Contributions of this paper. We address the above weaknesses in MIP solvers for adversarial attacks, by developing a GPU-accelerated branch and bound procedure to systematically search adversarial examples in the activation space, which is more efficient than generic MIP solvers. We focus on solving hard instances, where none of existing adversarial attacks based on searching the input space are successful but no verifier can prove their robustness. Our contributions includes;
We apply the GPU-accelerated bound propagation based methods (Wang et al., 2021 Xu al. 2020 Zhang et al., 2018 WWong& & Kolter 2018), which were originally developed for neural net- work verification, to the adversarial attack setting. These specialized methods can quickly examine thousands of regions in activation space in parallel and rule out the regions with no adversarial examples, which is difficult in off-the-shelf MIP solvers with generic solving procedure.
We employ a top-down beam-search to explore the activation space. Unlike the best-first search scheme used in many neural network verifiers, we can quickly go deep in the search tree and identify the most promising regions with adversarial examples. A smaller sub-MIP can then be created on- the-fly to search adversarial examples in the reduced regions with much fewer integer variables.
We collect adversarial examples generated by cheap attacks in candidate pool and utilize them in two ways. First, we conduct a bottom-up up search on examples close to decision boundary by applying large neighborhood search (LNS). Second, when conducting the top-down search, by fixing integer variables according to adversarial examples in the pool to reduce the search space.
adopt diving
Our new attack framework, BaB-A -AttAttack, is designed to tackle hard instances where existing strong adversarial attacks (such as AutoAttack) cannot succeed. Despite being more expensive than attacks on the input space, BaB-Attaer is about an order of magnitude faster than using an MIP solver on hard instances, and can find adversarial examples that cannot be discovered by any existing attacks.
2 BACKGROUND
Notations. We define a L layer feed-forward ReLU network as f Re + R and f(x) = (z). where 2 (x) = (() (x) + b(0 with i-th layer weight matrix W( and bias (0), (() = (z)) and input ((0) = x. Layer i has dimension n,, and N is the total (6) For simpler presentation, we
number of neurons. We denote the j-th neuron in layer 2,
2

---

Under review as a conference paper at ICLR 2022
assume fx) is a binary classifier and benign input 2o has f( 0. An attacker seeks to minimize [()) within a &o norm perturbation set C to make f(x) < O. We can attack a multi-class classifier by considering each pair of target and ground-truth label individually where f is defined as the margin between them, similarly to (Gowal et al. 2019b). We use [N] to represent the set (1,..,,]]
The MIP formulation for adversarial attack. Tjeng et al. (2019) formulated the adversarial attack and verification of ReLU network into mixed integer programming (MIP) problem, solved by existing MIP solvers (refer to as the "MIP attack"). It has binary variables s) for each ReLU:
min f(r) s.t. z (z) = w (x) + bbO;
x EEC;
()) 23 (z); (x) u//o/ (c))))
xx) 10--000 10 (1-8)));; o/9); (2)
{) 0; ( e 1152 uf of e iE [4], j e [m.]
where o/ ( indicating the two status of ReLU neuron: (1) inactive: when $ (1) = 0, constraints on
e(() simplifies to 2/6 = 0; or (2) active: when s
(1) 1 we have 2/0) =z .eee 1/)) uy (1)
are pre-
(1) computed intermediate lower and upper bounds on ace-activation oj such that 1(00 S (x) uj
(i)
for any x E C. The complexity of this problem can increase exponentially with the number of ReLU neurons, so it can take hours run even on small network, unless the network is trained with strong regularization such as a certified dense (Wong & Kolter 2018 Xiao et al. 2019).
Searching in the Activation Space via Branch and Bound. Given the formulation in Eq. (2). we can view a neural net- work in the activation space A = 1] where N is the total number of neurons, and each dimension corresponds to the setting of s E 13 variable. To determine 5 corre- sponding to a known adversarial example Talv, we can prop- agate Tady through the network and check the sign of each
10.3
9
5 (4 -
S {Fo 1)
(2)
(4y
8 (4s
03
81 1)
3.8
1.9
(1) 2 0). This uniquely locates the linear piece of fz) where Tadv lies, because Eq. ( becomes set of linear inequalities when all s/") are fixed. Intuitively, can search adversarial examples by fixing all s) to one of the 2 possible combinations in A, and then solve Eq. (2) exactly using linear programming; an adversarial example is found when the solution negative. To avoid clutter, we flat- ten the ordering of 8 subscript $1, ... .S to denote all binary variables.
neuron 2j so 8) = [(z))
(6)
0.01
Adversarial
example
Leaf nodes: al binary variables been fixed
A branch and bound search tree. Each node represents subdomain determined by S, and the numbers are LB(S). No adversarial example exist in the suhdomain LB(S) > (green). A concrete adversarial example is a leaf node Seat where (B(S) < 0.
Figure 1:
(i) for E [L]. E [v.] and use a single
To effectively and systematically search in the activation space, instead of fixing all s; (i E (N)) we can first fix a subset of them and bound the objective f(x) to guide the search, leading to the branch and bound (BaB) method. In BaB, we solve Eq. (2) by cre- ating subproblems constraining some binary variables, for example, $1 or 81 (since we can branch on the neurons in any fixed order, without loss of generality, we branch the neurons chrono-
logically). We define a set S containing all the branching constraints (e.g., = {s] = 0, $2 = 17), which corresponds to a subdomain of the original problem Eq. (2). BaB requires the LB primitive on S, which relaxes the remaining binary variables to obtain a lower bound of Eq. 2
Lower bound in subdomain: LB(S)= S min [xx s.t. 8 E S and all other constraints in Eq.
Here E S means setting binary variables $ according to the constraints in S. Typically, more
constraints in S lead to tighter bounds. LB(S) > O indicates that no adversarial example exist within this subdomain, otherwise adversarial examples may exist in this subdomain.
We illustrate a BaB search tree in Fig. I Initially, Spoet 0. where x E C' without any extra constraints in activation space and a lower bound of Eq. 2 is obtained. When LB(0) < 0, an adversarial example may exist, and we branch Spoot into two subdomains:
S = S Us1 = 0); S1+ = Swa U = Then we bound each subdomain. Since more constraints are added, LB(S,) and LB(S)+) are usually improved. The branching procedure continues recursively, and if any LB(S) > 0, no further
3

---

Under review as a conference paper at ICLR 2022
branching is needed since no adversarial examples are in that subdomain. Each branching increases the cardinality of S by I, and eventually we reach leaf nodes with |Starl = NN, each leaf locating a linear piece of f [ar). In that case, LB(Star) is an exact solution since no binary variables are left, and if (B < O, concrete adversarial example is the minimizer x² of Eq. ( with & E Steat- Since N can be quite large and adversarial examples lie in the leaf level, we must guide the search to reach there quickly. Although BaB is used in existing neural network verifiers (Bunel et al. 2018 De Palma et al. 2021a), they do not aim to reach the leaf level and typically branch the node with the worst bound first, generally leading to a wide but shallow search tree and unsuitable for detecting
adversarial examples. We will discuss our search algorithm in Sec. 3
Bounding in Branch and Bound of Neural Networks. The LB(S) primitive is crucial in the BaB process: needs to provide a tight lower bound efficiently. A simple way to lower bound the objective of Eq. (2) is via relaxation of integer variables and linear programming (LP) (Bunel jet al. 2018, Lu & Kumar 2020); but an LP solver is needed which restricts its efficiency. Recently, popular choice in neural network verifiers is the specialized bound propagation methods (Zhang ee al. 2018 Wong Kolter 2018) which exploit the structure of the optimization problem (which generie LP/MIP solver cannot) and give (B()) efficiently on GPUs without an LP solver. Essen- tially, they relax each ReLU neuron into convex domains (Salman et al. 2019) and propagate them layer by layer through the network while maintaining sound bounds. A BaB and bound propagation based verifier a.3-CROWN (Zhang et al. 2018 Xu et al., 2021; Wang et al. 202I), achieves the state-of-the-ar verification performance (Bak et 2021)) and we utilize its bounding subprocedure produce LB)). Importantly, will show that how we use LB(S) guide adversarial attacks, while existing works mostly use them for verification.
Top-Down on GPUs
subdomaan
METHOD
r.B-CROWN
Verifier
Iower bounds
Beamn Search
woldoominss
Commroa advenssrial pallems
Overview of BaB attack. To systematically
upper bounds
Promising subdomains
search adversarial examples in activation space, Input:
we must explore the search tree and enumerate, s.t x C
min f(x)
PGD
Adversarial Candidates Pool
as more leaf nodes as possible. Although the
random starts
Diving
worst case search time complexity is exponen-
tial in the numbers of ReLU neurons (visiting ev-
Disiegrond
Promising adversania
Solutios
adversorial
Sub- MIPP
ery leaf node of the tree), practically, if right search procedure is chosen, only a small fraction of nodes need to be visited to find an adversarial example. In this paper, we propose BaB attack, specializing the BaB searching strategy over the activation space for the purpose of adversarial at- tacks. The search is well guided by (1) a top-down beam-search thread accelerated on GPUs which quickly goes deep into the search tree, and (2) a bottom-up search thread on CPUs for large neighborhood search. The top-down and bottom-up searches run in parallel threads and they both benefit from the adversarial candidates pool P. which contains examples P = {Zey. Test where M is the pool capacity. f(ze,) ) is still positive but small; the pool keeps the M best (ranked by f(xx)): ): smaller is better) examples it receives. The activation space representations of these candidates are used as extra information to guide the search towards adversarial examples. We detail each part of BaB attack in next sub-sections.
patterns
candidbles
Local Search
Sub MIPa
Sub MIP
Solver
Balltom-Up thread on CPUS
Output
adversarial example detected: fF <
Figure 2:
Overview of BaB attack.
3.1 TOP-DOWN BEAM SEARCH GUIDED BY NEURAL NETWORK VERIFEERS
Challenges in searching adversarial examples. The activation space can be quite large (e.g., with thousands or more dimensions), and adversarial examples are at the leaf level of the search tree. Searching directly from the root node and traversing the search tree in an exhaustive manner (such as BFS or DFS) can be quite insufficient. To locate adversarial examples faster, we propose to use beam search guided by lower bounds from neural network verifiers, detailed below.
Beam search in activation space. The key insight in our procedure is to accelerate the search by prioritizing suspicious subdomains with small LB(S), quickly excluding the tree branches that are guaranteed with no adversarial examples. At the root node in the search tree, our beam search procedure expands the tree by D levels, yielding 2" subdomains:
S = Spoot U {si = 0, 0..., ,SD = 0},
S₂ = Sport U fs1 = 1, = -.... SD = 0},
Sa Swont U (s) = 0, 81 11...,,9p = 0},
S2o = Scont U U(81 = 1, 11 1...,8p = 1}
4

---

Under review as a conference paper at ICLR 2022
For each subdomain, we obtain its lower bound via the primitive LB(S). We use the bound propaga- tion procedure in the a,8-CROWN verifier to efficiently provide LB(S), but other efficient bounding methods can also be used in principle. Then, we sample K subdomains without replacement out of the 2D domains, with the following probability associated with each S₁
exp (-T (-T-L)(S)) (LB((S) < <0) i {1..... 22), i' the temperature. to 0.1
P
E exp cxp (-T LB(S.)) ((L((S.) 0)
Bearn search
A subdomain with more negative lower bound has a higher probability to be selected, since the large negative bounds may indicate a higher chance of the existence of adversarial exam- ples. Subdomains with positíve bounds will never be selected, since they are guaranteed to not contain adversarial examples. The picked out subdomains ,', , become the parent nodes for the next iteration of beam search. In the next itera- tions, we explore K 2 subdomains and increase the depth by D per iteration. Since all the subdomain lower bounds are com- puted in a large batch on GPUs and only take a few seconds, our search procedure quickly explore deep in the search tree. Our specialized top-down beam search procedure with lower bounds computed efficiently by bound propagation methods on GPUs brings us great advantages over existing MIP solvers, which conduct BaB on CPUs using generic procedure such as the Simplex algorithm. In practice, we can visit several or- ders of magnitude more subdomains.
expands to domains {00
10.3
8
D
(40
81
2.1
4.2
Choose most
promneing domains
-28
-2.4
-3.8
0.1
0.02
.0.01
Advensorial
Leaf nodes: all binary variatiles have been fixed
Figure 3: Beam search: we select K subdomains probabilistically accord- ing to LB(S), and expand the search tree by 1) levels using bound propaga- tion on GPU.
Sub-MIP on most promising subdomains. Before the beam search reaches the leaf level, we start searching adversarial examples in the most promising subdomains (e.g.. in some of the selected domains Si,"' Skk). ) by constructing sub-MIP problem of Eq. 2 in the k--th sub-MII, we fix its binary variables $ based on constraints in Sy In this step, although a generic MIP solver is used, it is instructed to search in subdomains guided by beam search to be likely to contain adversarial examples. With a large number of ( fixed during beam search, the MIP solver only needs to work on much smaller problem and can be much more effective than solving Eq. (2 directly.
Completeness. Beam search, if implemented with back-tracking, can achieve completeness (Zhou & Hansen 2005): given sufficient time, it will systematically visit all leaf nodes, and guarantee to either locate adversarial example, or prove the network safe. However, due to the large number of neurons and associated binary variables, achieving completeness often requires an infeasibly large amount of time and space. We thus focus on searching adversarial examples as fast as possible rather than exhaustively visiting every node, although thcoretically our procedure can be made complete.
3.2 DIVING IN BRANCH AND BOUND WITH COMMON ADVERSARIAL PATTERNS
What is diving? "Diving" refers to diving deep in the BaB search tree by heuristically fixing some integer variables without exploring all possible branches. It is a common strategy in generic MIP solvers, able to quickly uncover feasible solutions of MIP problem (Berthold 2006 Nair et al.)
2020 In our case, we want to fix binary variables s in Eq. (2) and feasible solution x with [(x) < 0 is an adversarial example (Figure A generic MIP solver uses diving to hopefully find high quality feasible solutions quickly. however it cannol use the information provided by cheaply generated adversarial examples like PGD attack to guide this heuristic. In this work, we propose a specialized diving scheme in the activation space based on the statistics in the adversarial candidates pool, and construct sub-MIPs with additional diving constraints to reduce the search space.
Diving with common adversarial patterns. Given the candidates pool P = {xey. Nens J. we first extract the corresponding binary variables for each example. by propagating them through the network (see Section 2. The binary variable corresponds to the i-th neuron of the m-th adversarial example is denoted as $i. (0 or 1). A variable is called a common activation when the function c(i) is greater than a threshold:
M
Si,m M/2
c(i)
+05
CE 00.5, 1.0]
M
For example, when C = 0.9, a common activation requires that at least 90% examples in the pool share the same value of s; (0 1). All the common activations and their common values (0 1)
5

---

Under review as a conference paper at ICLR 2022
called common adversarial patterns, indicating that adversarial examples will be very likely to contain these settings of 84. We can thus construct a set of constraints Semmonn setting common activations and their common values:
M c() 2 [NT
common = {s,
S..
2
Then, when constructing the top-down sub-MIPS in Sec. 3.1 we provide additional constraints Swommon. Including these additional constraints further reduces the search space for the MIP solver (the MIP solver solves Eq. (2) with both beam search constraints Sj and diving constraints Scomeea), making it easier to find an solution. The threshold C controls the aggressiveness of diving; too much diving may lead to a too small search space so good adversarial examples cannot be found.
How to fill the ad adversarial candidates pool? To obtain use- ful common adversarial pattern, we maintain an adversarial candidates pool with up to M most promising adversarial can- didates (f(z) is close to 0 but the label is not yet flipped). The pool is initialized with perturbed samples bounded within C found with output diversified PGD (Tashiro et al. 2020), which creates a diverse set of adversarial candidates. Dur- ing our BaB attack process, new adversarial candidates come from three sources: (1) some neural network verifier provides upper bounds for each subdomain during beam search; in 0,8-CROWN these upper bounds are obtained via conduct-
Beam search
0
-10.3
2211
-3.6
-4.2
1.9
S
2.8
244
3.88
0.5
Fix more variables
Fry-1
ing PGD on its dual solutions (Wang et al.) (021)) produced by the solver, and they are added to the pool; (2) the solutions returned by the top-down sub-MIP solved with beam search and diving constraints, and (3) the solutions returned by the bottom-up sub-MIP with large neighborhood search (which will be discussed in the next subsection). When new adver- sarial candidates are inserted, they are compared to existing ones in the pool, and we keep the best M adversarial candi- dates with distinct activation patterns.
Dive Node
-1.8
4n
Adverearial
0.01
0.3
example
Leaf nodes: binary variables have been fixed
Figure 4: We dive the search tree with additional constraints constructed by common adversarial patterns to greatly reduce top-down sub-MIP search space.
Sub-MIP variablea
frop variabia Sy-11
.2.7
3.3 BOTTOM- UP LARGE NEIGHBORHOOD SEARCH (LNS)
What is bottom-up search? The bottom-up search proce- dure starts at the leaf nodes of the BaB search tree (Figure 5 we start from a known adversarial candidate V, that is close to decision boundry (f (f(x)) > 0 but very small), and want to further reduce f(xx)) by searching around z,. A naive way is to conduct PGD attack in the input space with Te as the start- ing point, but we found it not helpful because the adversarial candidates in the pool have already been optimized using PGD or stronger attacks. Thus, we propose to use a large neighbor- hood search in the activation space.
-1.8
-1.9
free var iabbe
Reference
point
0.01
+0.01
Adversarial excample
nodes: binary varables have been fhxod
Figure 5: In bottom-up search, we feee some fixed integer variables at a leaf node (an adversarial candidate) search- ing its neighborhood in activation space.
Bottom-up search via large neighborhood search. Large neighborhood Search (LNS) (Walser) 2003 Schrijver (003) a generic local search heuristie: one defines a neighborhood around a ref- erence point (a reasible solution) and finds the optimum objective in this neighborhood, typically by constructing a sub-MIP problem with neighborhood constraints. In the setting of integer program- ming, the neighborhood can be defined by freeing certain fixed integer variables, allowing them to be optimized while fixing other integer variables. However, traditional local search algorithms in MIP solvers has little guidance regarding promising subdomains in common adversarial examples and can be ineffective due to the high dimensional search space in the adversarial attack problem.
In BaB attack, we extend the general idea of LNS to a specialized local search for adversarial attacks by selecting the most promising adversarial candidates in the pool the reference point and then use the statistics from the pool to free certain binary variables s;. Specifically, among all the binary variables corresponding to ReLU neurons where adversarial candidates in the pool that disagree the most and define the disagreed adversarial patterns. Formally, similar to the setting in Sec. 3.2 a variable s; is called a disagreed activation if:
the selected candidate,
find the ReLU neurons
c(i)= == c(i) C. C E [0.0,

---

Under review as a conference paper at ICLR 2022
minuum ottakk margin
minmum ettazk marain
minuum margin
0.35
1.75
ODS AGD
ODS-PGD
ODS-PGD
0.25
AutoAttack
1.25
0.06
0.20
y-x
y-x
y-x
0.15
2.0.04
0.10
0.50
0.02
0.00 0.05 0.00.115 0.00 2.033 0.40
0.00 0.25 0.200.055.00077. 0.50.755 1500000111011155500000 15
0.00
0.00
0.52
0.34
0.06
0.58
0.10
minmum attack margin
minmum attack margin
minmum attack margin
IMT-PGD, ODS PGD, AutoAttack)
(MT PGD, ODS PGD, AutoRttack)
(MT PGD. ODS-PGD, AutoAtteck)
(a) MNIST CNN-A-Adv
(b) MNIST Small-ACe Adv
(c) CIFAR CNN-B-Ady
minmum attack margin
0.30
0.35
MIT-PG
ODS-PGD
minmum attack margin
0.25
ODS-PGD
MTTPPD
minmum attack margin
3.B
MT-PGD
ODS-PGD
(buts
0.20
0.25
y-x
AutoAttack
0:15
AutoAltack
(Qurs)
2.6
yex
AutoAitack
2.0
0.10
0.05
0.2
9.0
8.00
30.0
0.6 0.6
minmum allack
eilack
minmum ellack margin (MT.PGD, PGD, AutoAttack)
PST, ODS PGD, AutoArackk)
(MT. ODS,PGD, AutoAttock)
(d) CIFAR CNN-A-Mix
(c) CIFAR Marabou
(f) MNIST Conv- SmwlS
Figure 6: For examples that attacks failed, we compare minimum margin between the ground-truth label and all other target labels for the adversarial candidate. A smaller margin is better. Our attack achieves noticeably smaller margins compared to other attacks (margins from other attacks are below the y = x line).
For example, when C 0.3, 8; a disagreed activation when there are at least 30% examples in the pool do not share the same value of 8;. Since these variables are quite different across existing adversarial examples, we remove their corresponding binary variables to allow the MIP solver to search for better setting of these variables. The aggressiveness of freeing variables in LNS is determined by C. The set of disagreed adversarial patterns is set of binary variables:
Sdisagreed {s; E(i) 2 C i [N]]
Formally, to search around an adversarial candidate we first propagate xe through the network and obtain activation values 2;, extract the corresponding binary variables s; for ze. and remove the constraints that are in disaggeed to construct the set of constraints for bottom-up search:
Sbottom-up (8; 1 (z, 2 0), 8; & Saisugreed, E [N]]
We then construct sub-MIIP using Eq. 2 with the additional constraints Spation up and solve it using a MIP solver. The optimal solution to each sub-MIP (if still not an adversarial example) will be added back to adversarial candidates pool again waiting for another round of local search.
4 EXPERIMENTS
Setup. We evaluate our methods on all 10,000 test examples of MNIST (LeCun 1998) and CI- FAR10 (Krizhevsky et al. 2009) dataset, and select 9 models which are mostly benchmarking mod- els used in previous works or competitions (details in Appendix AA.. For each model, we first run three commonly used strong adversarial attacks:
multi-targetee PGD (MT-PGD) attack (Gowal ctt al. 2019a) with 100 Adam steps and 30 random restarts; a multi multi-targeted PGD attack with Out- put Diversified Sampling (ODS-PGI) PGD) (Tashiro et al. 2020) with 100 Adam steps and 30 random restarts, and AutoAttack (Croce & Hein| 2020b) which an ensemble of parameter-free free attacks. The remaining robust images are then tested with o.g-CROWN verifier (Wang et al. 2021: Xu al. 2021 Zhang et al., 2018) to see if they can be verified robust so no further attack needed. Any images that failed with the verifier are then evaluated in an MIP formulation (Tjeng et al. 2019) solved using Gurobi. The MIP solver is used as the last resort because it usually much more ex- pensive than other approaches. We set an one hour timeout for MIP attack and our BaB attack, but our attack usually terminates much faster than generic MIP solver. Any instance that cannot be attacked via a combination of MT-PGD, ODS-PGD and AutoAttack nor verified is referred to a hard instance, and the main evaluation is conducted on these instances. All attacks are loo norm-based with listed in Table 1. The hyperparameters can be found in Appendix A.2
7

---

Under review as a conference paper at ICLR 2022
Results. Table 1 shows breakdown of all 10,000 test exam- ples on the models. Among these models, MNIST Small-Adv, MNIST Conv-Small, CIFAR LPN--NN-A, and LPP-ResNet are relatively easy, and most of datapoints can either attacked or verified by SOTA tools. The I. I.PD-CNN-A and ..PD-ReNNet mod- els were among the largest ones in (Teng et al., 2019), however they have become quite easy due to the recent progress of neu- ral network verifiers only 2 and (out of 10,000) examples are hard instances. On the relatively small MNIST Small-Adv model,
70
13
10
BaB Attack
MIP Attack
Rurning
(a) MNIST Small-Adv
a MIP solver can terminate within reasonable amount of time, and we can attack the same number of images while being faster. On the MNIST CNN-A-Adv model, many instances timeout with the MIP solver and we can attack more images under less time; see Fig. and Fig. 8 (in Appendix) for time vs. number of images attacked. The CIFAR ENN-B-Adv, CNN-A-Mix, and Marabou models are much harder, and we managed to solve 5, 17, and 27 more images compared to MIP attack within much shorter time. BaB attack can solve the same number of images on MNIST Conv-Small and CIFAR CNN-A-AC but is over 10x faster in average. For images that none of the attacks work, we plot the minimum margin between the ground-trun label and other labels in Fig. and compare the margins against ODS-PGI MT- PGD attacks and Auto/ttack. Our method consistently achieves smaller margins on all 6 models.
Ball Attack
numoer of more Soneooa
66
Attack
9
MIP attack
MABST Chikstlder Running time
(b) MNIST CNN-A-ADV
Figure 7: Running time vs. num- ber of attacked images compared to MIP attack.
Comparison to more attacks. We compare our BaB attack to 5 state-of-thed the art attacks on all hard instances in Table 2 Attacks we evaluated include 1) FAB attack (Croce & Hein 2020a): white- box boundary adversarial attack; 2) Square attack (Andriushchenko et al. 2020): a query-efficient black-box adversarial attack using randomized search with localized square-shaped updates; 3) DIFGSM attack (Xie et al.) 2019): a white box attack leveraging input diversity; 4) MIFGSM at- tack (Dong et al.) 2018): a momentum-based iterative white box attack to escape from poor local maxima and 5) Distributional attack (Zheng et al. 2019):: white box attack considering adversarial- data distribution. We increased steps and iterations to make some attacks stronger, hyperparameters are in Appendix A.3 Most attacks are not effective on these hard instances. Square attack is the strongest among them but still finds less adversarial examples than us and is also relatively slow.
Ablation study. To fully understand how each proposed component contributes to the overall performance of BaB attack, we conduct ablation study on MNIST Small-Ady and MNIST CNN-A- Adv models and show the number of successfully attacked instances and average time in Table 3 first show that the beam search guided by verifier a,33 0.3-CROWN significantly helps the performance compared to random top-down search without any guidance. We then show that the top-down diving and bottom-ur up large neighborhood search contribute to different hard instances and the combination of them lead to the best attack performance. Note that the average time here is on successfully attacked samples by each method only, showing the efficiency of each component instead of strength.
We
Dataset
Model
aps
Clean Ace.
Total verifled
Total sttckeed
Hard instances
MIP attick
Aug. time(s)
Ball attack
Avg. time(s)
Amall-Ads
0.3
97.91%
8176
L559
59
439,88
37
16.15
MNIST
CNN-A-Adv
0.3
3356
6757
2239
637
2546. 13
67
111.77
Conv-Small
0.12
98.04%
7628
21599
38
17
3358.49 49
17
8.52
LPd-CNN-A
22255
60.86%
5019
1065
2
13.80
2
9.50
LPA-RES
8/255
27.07%
2243
463
1
0)
CIBAR
CNN-A
2/155
65.63%
4755
1660
148
906,77
57.98
CNN
78.25%
1551
CNN.A-Mi
1062
3467.52
Murshou
63.14%
875
4188
1251
1470.22
(using Gurobi) and our BaB Attack. Both attacks focus on hard instances where a combination of MT-PGD, ODS-PGD and Auto cannot attack and their robustness also cannot be verified using a verifier. We are faster than MIP Attack and also find more adversarial examples in all models. Average time excludes examples where all methods time out.
Table 1:
Comparison between MIP attack (Tjeng et al. 2019)
RELATED WORK
Adversarial examples and attacks. Adversarial examples were first discovered in (Szegeyy et al., 2013 Biggio al. 2013) and they can be easily constructed by sigle-/mulli-ssepp gradient descent to fool regularly trained neural networks (Kurakin et al.) 2016 Goodfellow et al. (215).. However, purely gradient-based methods can fail due to gradient masking and obfuscated gradients (Tramer et al. 2017 Papernot et al. 2016 AAhhlly et al., 2018). Popular attacks like PGD (Madry et al. CW (Carlini & Wagner 2017) can lead to overestimation of robustness (Mosbach al.
2018
8

---

Under review as a conference paper at ICLR 2022
Dassset
Model
Rotal
FAB
Square
DIPGSM
MIFGSM
Distrbutional
BaB anack
socc. Time(()
suze.
Time(s)
suec.
Timets)
succ.
Time())
succ.
Timels)
suuc.
Timee(s)
Small-Ady
59
12.29
12
79.61
0.04
0.02
0
0.03
16.15
MNIST
CNN-A-Ado
637
0
33.96
17
117.51
0.04
0
0.02
0.001
67
111.77
Cam--Small
38
31.90
113.03 14
0.04
0
0.02
0.03
17
8.52
L
2
0
34,61
0
117.33
0.02
0
0.02
01
0.64
9.90
LPA-RES
1
48.98
0
242 52
0.42
0
0.06
01
1,62
CIFAR
CNN-A A-vv
148
33.22
0
116.76
0.39
0.02
0.01
57.98
CNN-
1551
CNi.A-Mix
1062
34.13
0,02
71.65
Marshoo
1251
20:21
111.70
0.04
0.02
0.03
56.82
Table 2: Number of successfully (#f succ.) attacked hard instances (from Table D under five more attacks.
MNIST-Smail-Ad
MNIST-CNN-A-AGY
siccess
# total
Avg. time
success
# total
Avg. time
Mandom top-dows heam search
8
59
19.52
22
6.37
13.46
Verifer guided beam search
36
59
21.58
54
637
203.75
Verilier guided
scarch diiiing
36
59
20.63
57
Verißer guided beam scarch + bottomup search
36
59
22.67
66
637
110.65
Verifier guided beam scarch + diving bottomup search
37
59
16.15
67
637
111.77
Table 3: Ablation study on how each proposed component contributes the overall performance.
Croce et al. (2020) despite their empirically good performance and efficiency. A large body of white-box adversarial attacks have been proposed strengthen adversarial attacks; many of them are variants of PGD based attacks (Zheng et al.] 2019 Tashiro et al., 2020] Gowal et al.) 2019b] Wang et al. 2019). Due non-convexity of the adversarial attack objective, gradient-free methods and black-box attacks are also widely explored but mostly result in similar or worse performance compared to gradient-based ones (Papernot et al. 2017 Chen et al. 2017 Ilyas et al., 2018a b. Xiao et al. 2018 Andriushchenko et al.) 2020). Recently, stronger attacks (Croce & Hein 2020a b) are proposed but they are also restricted to searching in input space. In this paper, we are the first to conduct a systematic and efficient search of adversarial examples in activation space inspired by branch and bound techniques used for integer optimization and neural network verification.
2018
Neural network verification. Early neural network verifiers solve the verification problem with satisfiability modulo thcories (SMT) or MIP solvers and can only scale to very small networks (Katz) al. 2017: Huang et al.) 2017: Ehlers 2017, Dutta et al. 2018 Tjeng et al.. 2019). Efficient
verification methods with various sound relaxations are then proposed for verifying larger networks
but without completeness guarantee (Wong & Kolter 2018 Dvijotham et al. 2018 Raghunathan
jet al. 2018a b) [Singh et al. 2018b a Zhang et a 2018 Tjandrattmadja et al. 2020). Branch and
bound (BaB) based verifters can efficiently branch on ReLO neurons and achieve completeness on
ReLU networks using efficient incomplete verifiers (Bunel et al. 2018 Wang et al. 2018a| Lu & Kumar 2020: Botoeva et al.) 2020). BaB based methods with input domain split and refinements are also investigated but they are limited to low input dimensions (Wang et al. 2018b] Royo et al.)
2019 Anderson et al. 2019). Recent verifiers use GPU accelerated incomplete solvers to further
scale up verification and achieve several orders of magnitude speedup (Bunel et al.) 2020 De Palma et al. 2021bb Anderson et al. 2020 Xu et al.) [021] Müller et al. [021] 2020 Wang et al. 2021)
Our BaB attack relies on the lower bounds of BaB subdomains computed by o, B-COWN (Zhang eet al. 2018, Xu et al., 2021 Wang et al. (021). one of the most efficient GPU-based verifiers that
won the second neural network verification competition (VNN-COMP 2021) (Bak et al. 2021.
6 CONCLUSION
In this paper, we proposed BaB attack, a strong adversarial attack using branch and bound to sys- tematically search adversarial examples in activation space. We propose a top-down beam search utilizing bound propagation methods from neural network verifiers on GPUs to quickly locate po- tential subdomains containing adversarial examples. We further exploit the common activation pat- terns of adversarial candidates obtained by cheap attacks to guide the searching process with diving. Moreover, a bottom-up large neighborhood search procedure explores around promising adversarial candidates to find potential adversarial examples. Experimental results show that our BaB attack can find adversarial examples for hard input instances where SOTA adversarial attacks fail. We achieve higher attack success rates within much less time compared to generie MIP solver based attacks.
Limitations of this study. One limitation of BaB Attack is speed it usually takes a few minutes to explore a branch and bound tree using beam search, while gradient based adversarial attacks are often very fast, in few seconds. Practically, BaB attack is mostly useful for hard instances, and we can use other simpler attacks as a filter to reduce the number of inputs for BaB attack. Additionally, BaB attack currently relies on neural network verifiers to give lower bound for each subdomain to guide the beam search, so its scalability is limited by SOTA verification tools. Yet, we have demonstrated that it is faster and also more effective than attacks using an off-the-sher MIP solver.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Moustafa Alzantot, Yash Sharma, Supriyo Chakraborty, Huan Zhang, Cho-Jui Hsieh, and Mani B Srivastava. Genattack: Practical black-box attacks with gradient-free optimization. In Proceed- ings of the Genetic and Evolutionary Computation Conference, pp. 1111-1119, 2019.
Greg Anderson, Shankara Pailoor, Isil Dillig, and Swarat Chaudhuri. Optimization and abstraction: A synergistic approach for analyzing neural network robustness. In Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), 2019.
Ross Anderson, Joey Huchette, Christian Tjandraatmadja, and Juan Pablo Vielma. Strong convex relaxations and mixed-integer programming formulations for trained neural networks. Mathemat- ical Programming, 2020.
Maksym Andriushchenko, Francesco Croce, Nicolas Flammarion, and Matthias Hein. Square at- tack: a query- query-efficient black-box adversarial attack via random search. In European Conference on Computer Vision, pp. 484-501. Springer, 2020.
Anish Athalye, Nicolas Carlini, and David Wagner. Obfuscated gradients give a false sense of security: Circumventing defenses to adversarial examples. In ICMI, 2018.
Stanley Bak, Changliu Liu, and Taylor Johnson. The second international verification of neural networks competition (ynn-comp 2021): Summary and results. arXiv preprint wrXi::2109.00498, 2021.
Timo Berthold. Primal heuristics for mixed integer programs. 2006.
Battista Biggio, Igino Corona, Davide Maiorca, Blaine Nelson, Nedim Šindić, Pavel Laskov, Gior- gio Giacinto, and Fabio Roli. Evasion attacks against machine learning at test time. In Joint European conference on machine learning and knowledge discovery in databases, 2013.
Elena Botoeva, Panagiotis Kouvaros, Jan Kronqvist, Alessio Lomuscio, and Ruth Misener. Eff- cient verification relu-based neural networks via dependency analysis. In AAAI Conference on Artificial Intelligence (AAAI), 2020.
Wieland Brendel, Jonas Rauber, and Matthias Bethge. Decision- based adversarial attacks: Reliable attacks against black-box machine learning models. In ICLR, 2018
Rudy Bunel, Alessandro De Palma, Alban Desmaison, Krishnamurthy Dvijotham, Pushmeet Kohli, Philip H. S. Torr, and M. Pawan Kumar. Lagrangian decomposition for neural network verifica- tion. Conference on Uncertainty in Artificial Intelligence (UAI), 2020.
Rudy Bunel, llker Turkaslan, Philip Torr, Pushmeet Kohli, and Pawan K Mudigonda. A unified view of piecewise linear neural network verification. In Advances in Neural Information Process- ing Systems (NeurIPS), 2018
Nicholas Carlini and David Wagner. Towards evaluating the robustness of neural networks. In Security and Privacy (SP), 2017 IEEE Symposium on, pp. 39-57. IEEF, 2017.
Pin-Yu Chen, Huan Zhang, Yash Sharma, Jinfeng Yi, and Cho-Jui Hsieh. Zoo: Zeroth order opti- mization based black-box attacks to deep neural networks without training substitute models. In Proceedings of the 10th ACM Workshop on Artificial Intelligence and Security, pp. 15-26. ACM, 2017.
Minhao Cheng, Thong Le, Pin-Yu Chen, Jinfeng Yi, Huan Zhang, and Cho-Jui Hsieh. Query- efficient hard-label black-box attack: An optimization- based approach. arXiv preprint 1SG.:18807.04457. 2018
Francesco Croce and Matthias Hein. Minimally distorted adversarial examples with fast adaptive boundary attack. In International Conference on Machine Learning, pp. 2196-2205. PMLR, 2020a.
Francesco Croce and Matthias Hein. Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-free attacks. In International conference on machine learning, pp. 2206- 2216. PMLR, 2020b.
10

---

Under review as a conference paper at ICLR 2022
Francesco Croce, Jonas Rauber, and Matthias Hein. Scaling up the randomized gradient- free adver- sarial attack reveals overestimation of robustness using established attacks. International Journal of Computer Vision, 2020.
Sumanth Dathathri, Krishnamurthy Dvijotham, Alexey Kurakin, Aditi Raghunathan. Jonathan Ue- sato, Rudy R Bunel, Shreya Shankar, Jacob Steinhardt, Ian Goodfellow, Percy S Liang, et al. Enabling certification of verification-agnosiie networks via memory-efficient semidefinite pro- gramming. Advances in Neural Information Processing Systems (NeurIPS), 2020.
Alessandro De Palma, Harkirat Singh Behl, Rudy Bunel, Philip H. S. Torr, and M. Pawan Kumar. Scaling the convex barrier with active sets. International Conference on Learning Representations (ICLR), 2021a.
Alessandro De Palma, Rudy Bunel, Alban Desmaison, Krishnamurthy Dvijotham, Pushmeet Kohli, Philip HS Torr, and M Pawan Kumar. Improved branch and bound for neural network verification via lagrangian decomposition. arXiv preprint Xrv: 104. .4.066//8 2021b.
Yinpeng Dong, Fangzhou Liao, Tianyu Pang, Hang Su, Jun Zhu, Xiaolin Hu, and Jianguo Li. Boost- ing adversarial attacks with momentum. In Proceedings of the IEFE conference computer vision and pattern recognition, pp. 9185-9193, 2018.
Souradeep Dutta, Susmit Jha, Sriram Sankaranarayanan, and Ashish Tiwari. Output range analysis for deep feedforward neural networks. In NASA Formal Methods Symposium, 2018.
Krishnamurthy Dvijotham, Robert Stanforth, Sven Gowal, Timothy Mann, and Pushmeet Kohli. A dual approach to scalable verification of deep networks. Conference on Uncertainty in Artificial Intelligence (UAI), 2018.
Ruediger Ehlers. Formal verification of piece-wise linear feed-forward neural networks. In Interna- tional Symposium on Automated Technology for Verification and Analysis (ATVA), 2017.
Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. In ICLR, 2015.
Sven Gowal, Krishnamurthy Dvijotham, Robert Stanforth, Rudy Bunel, Chongli Qin, Jonathan Ue- sato, Timothy Mann, and Pushmeet Kohli. On the effectiveness of interval bound propagation for training verifiably robust models. Proceedings of the IEEE International Conference on Computer Vision (ICCV), 2019a.
Sven Gowal, Jonathan Uesato, Chongli Qin, Po-Sen Huang, Timothy Mann, and Pushmeet Kohli. An alternative surrogate loss for pgd-based adversarial testing. arXiv preprint 1rXiv:9910009338, 2019b.
Xiaowei Huang, Marta Kwiatkowska, Sen Wang, and Min Wu. Safety verification of deep neural networks. In International Conference on Computer Aided Verification (CAV), 2017.
Andrew Ilyas, Logan Engstrom, Anish Athalye, and Jessy Lin. Black-box adversaria attacks with limited queries and information. In International Conference on Machine Learning (ICML), 2018a.
Andrew Ilyas, Logan Engstrom, and Aleksander Madry. Prior convictions: Black-box adversarial attacks with bandits and priors. arXiv preprint arXiv:1807.0799 0797,07978 2018b.
Guy Katz, Clark Barrett, David I. Dill, Kyle Julian, and Mykel Kochenderfer. Reluplex: An efficient smt solver for verifying deep neural networks. In International Conference on Computer Aided Verification (CAV), 2017.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. Technical Report TR-2009 2009.
Alexey Kurakin, Ian Goodfellow, and Samy Bengio. Adversarial examples in the physical world. arXiv preprint arXiv: 160..0253, 2016.
Yann LeCun, The mnist database of handwritten digits. http://yann. lecun. com/exdb/nmist//, 1998.
11

---

Under review as a conference paper at ICLR 2022
Jingyue Lu and M Pawan Kumar. Neural network branching for neural network verification. Inter- national Conference on Learning Representation (ICLR), 2020.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In International Conference Learning Representations (ICLR), 2018.
Marius Mosbach, Maksym Andriushchenko, Thomas Trost, Matthias Hein, and Dietrich Klakow. Logit pairing methods can fool gradient-based attacks. arXiv preprint arXiv:1810. 100022220.22 2018.
Christoph Müller, Gagandeep Singh, Markus Püschel, and Martin Vechev. Neural network robust- ness verification on gpus. arXiv preprint arXiv:2007.10866 2020.
Mark Niklas Müller, Gleb Makarchuk, Gagandeep Singh, Markus Püschel, and Martin Vechev. Pre- cise multi-neuron abstractions for neural network certification. arXiv preprint wxXi:22033006338 2021.
Vinod Nair, Sergey Bartunov, Felix Gimeno, Ingrid von Glehn, Pawel Lichocki, Ivan Lobov, Bren- dan O' O'Donoghue, Nicolas Sonnerat, Christian Tjandraatmadja, Pengming Wang, et al. Solving mixed integer programs using neural networks. arXiv preprint arXiv:2012. 13344, 2020.
Nicolas Papernot, Patrick McDanicl, Arunesh Sinha, and Michael Wellman. Towards the science of security and privacy in machine learning. arXiv preprint 16Xiv: 11..014411..3114,, 2016.
Nicolas Papernot, Patrick McDaniel, Ian Goodfellow. Somesh Jha, Z Berkay Celik, and Ananthram Swami. Practical black-box attacks against machine learning. In Proceedings of the 2017 ACM on Asia Conference on Computer and Communications Security, pp. 506-519, ACM, 2017.
Aditi Raghunathan, Jacob Steinhardt, and Percy Liang. Certified defenses against adversarial exam- ples. International Conference on Learning Representations (ICLR), 2018:.
Aditi Raghunathan, Jacob Steinhardt, and Percy Liang. Semidefinite relaxations for certify- ing robustness adversarial examples. In Advances in Neural Information Processing Systems (NeurIPS), 2018b.
Vicenc Rubies Royo, Roberto Calandra, Dusan M Stipanovic, and Claire Tomlin. Fast neural net- work verification via shadow prices. arXiv preprint arXhv:1902.07247, 2019.
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 (NeurIPS), 2019.
Alexander Schrijver. Combinatorial optimization: polyhedra and efficiency, volume 24. Springer
Science & Business Media, 2003.
Gagandeep Singh, Timon Gehr, Matthew Mirman, Markus Püschel, and Martin Vechev. Fast and effective robustness certification. In Advances in Neural Information Processing Systems (NeurIPS), 2018a.
Gagandeep Singh, Timon Gehr, Markus Püschel, and Martin Vechev. Boosting robustness certifica- tion of neural networks. In International Conference on Leurning Reprexentations, 201 8b.
Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. ICLR, 2013.
Yusuke Tashiro, Yang Song, and Stefano Ermon. Diversity can transferred: Output diversification for white-and black-box attacks. Advances in Neural Information Processing Systems (NeurIPS), 2020.
Christian Tjandraatmadja, Ross Anderson, Jocy Huchette, Will Ma, Krunal Patel, and Juan Pablo Vielma. The convex relaxation barrier, revisited: Tightened single-neuron relaxations for neural network verification. Advances in Neural Information Processing Systems (NeurIPS), 2020.
Vincent Tjeng, Kai Xiao, and Russ Tedrake. Evaluating robustness of neural networks with mixed integer programming. International Conference on Learning Representations (ICLR), 2019.
12

---

Under review as a conference paper at ICLR 2022
Florian Tramèr, Alexey Kurakin, Nicolas Papernot, Ian Goodfellow, Dan Boneh, and Patrick Mc- Daniel. Ensemble adversarial training: Attacks and defenses. arXiv preprint (edi:1705..77755 2017.
Joachim P Walser. Integer optimization by local search: A domain-indeeendenn approach. Springer, 2003.
Shiqi Wang, Kexin Pei, Justin Whitchouse, Junfeng Yang, and Suman Jana. Efficient formal safety analysis of neural networks. In Advances in Neural Information Processing Systems (NeurIPS), 2018a.
Shiqi Wang, Kexin Pei, Justin Whitchouse, Junfeng Yang, and Suman Jana. Formal security analysis of neural networks using symbolic intervals. In USENIX Security Symposium, 20188 8b.
Shiqi Wang, Yizheng Chen, Ahmed Abdou, and Suman Jana. Enhancing gradient-based attacks with symbolic intervals. arXiv preprint arXiv: 02282, 2019.
Shiqi Wang. Huan Zhang, Kaidi Xu, Xue Lin, Suman Jana, Cho-Jui Hsich, and Zico Kolter. Beta- crown: Efficient bound propagation with per-neuron split constraints for complete and incomplete neural network verification. arXiv preprint XXix:2003.060 2021.
Eric Wong and Zico Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. In International Conference Machine Learning (ICML), 2018.
Eric Wong, Frank Schmidt, Jan Hendrik Metzen, and J Zico Kolter. Scaling provable adversarial defenses. In Advances in Neural Information Processing Systems (NeurIPS), 2018.
Chaowei Xiao, Bo Li, Jun- Yan Zhu, Warren He, Mingyan Liu, and Dawn Song. Generating adver- sarial examples with adversarial networks. International Joint Conference Artificial Intelli- gence (IJCAI), 2018.
Kai Y Xiao, Vincent Tjeng. Nur Muhammad Shafiullah, and Aleksander Madry. Training for faster adversarial robustness verification via inducing relu stability. In ICLR, 2019.
Cihang Xie, Zhishuai Zhang, Yuyin Zhou, Song Bai, Jianyu Wang. Zhou Ren, and Alan L Yuille.
Improving transferability of adversarial examples with input diversity. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pp. 2730-2739, 2019.
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 Processing Systems (NeurIPS), 2020.
Kaidi Xu, Huan Zhang. Shiqi Wang, Yihan Wang, Suman Jana, Xue Lin, and Cho-Jui Hsich. Fast and complete: Enabling complete neural network verification with rapid and massively parallel incomplete verifiers. International Conference on Learning Representations (ICLR), 2021.
Huan Zhang, Tsui- Wei Weng. Pin-Yo Yu Chen, Cho-Jui Hsieh, and Luca Daniel. Efficient neural net- work robustness certification with general activation functions. Advances in Neural Information Processing Systems (NeurIPS), 2018.
Tianhang Zheng, Changyou Chen, and Kui Ren. Distributionally adversarial attack. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), 2019.
Rong Zhou and Eric A Hansen. Beam-stack search: Integrating backtracking with beam search. In ICAPS, pp. 90-98, 2005.
13

---

Under review as a conference paper at ICLR 2022
A APPENDIX
A.1 DETAILS OF MODELS
MNIST CNN-A-Adv, CIFAR CNN-A-Adv, CIFAR CNN-B-Ady and CIFAR CNN-A-Mix models are provided by (Dathathri et al. 2020) and were trained with adversarial training, except that CI- FAR CNN-A-Mix is trained with mixture of adversarial training loss and certified defense loss. These models were used as a benchmark to evaluate the gap between verified accuracy and attack acucracy in a few papers (Dathathri al. 2020: Wang et al. 2021 Müller et al.] 202T). MNIST Amall-Adv trained using adversarial training with architecture similar to the MNIST model used in (Madry et al. 2018) 8) but scaled down by 4X and maxpool layers removed. MNIST Conv-Small a naturally trained model from the ERAN benchmarks (Singh et al. 2018a) Sa Muller et al. 2021) CIFAR LPd-CNN-A and LPd-RES TTeng et al., (2019) are trained using a dual linear programming based certified defense (Wong et al. 20188, so they are relatively easy to attack and verify. The CI- FAR Marabou model is from the mar marabou- c farl0 benchmark in 2nd International Verification
of Neural Networks Competition (VNN-Comp) 2021 (Bak et al., [221); the model (original name cifarl0-smar onnx) is naturally trained on CIFAR-IO 10 dataset.
A.2 HYPERPARAMETERS FOR OUR BAB ATTACK
We set the common adversarial pattern threshold be 1.0 for both top-down diving and disagreed adversarial pattern threshold C to 0.0 for bottom-up large neighborhood search. We use state- oh-the-art verifier a.B-CROWN to provide verified lower bounds LB(S). prioritizing suspicious subdomains. We use the default learning rates 0.01 and 0.05 for both a-CROWN and 3-CROWN. To tighten the estimation for each subdomain and provide more accurate guidance for suspicious ones, we increase the optimization iterations to 100 for both a-CROWN and 3-CROWN with a learning rate decay of 0.999. We use the maximal batch size B fit into the GPU memory. For each step of our beam search, we set the depth for each iteration of beam search D to be 8 and the number of picked out subdomains K to be B B/2D. One can adjust D control the searching speed.
We run all our experiments on EPYC 7502 CPU with 32 physical cores, and use up to 32 sub-MIP threads for top-down or bottom-up search. We set a timeout threshold for each sub-MIP to be 30 seconds for MNIST-Small
(because it is a relatively small model), 180s for the other MNIST models and 360s for CIFARIO models. We run each attack for up an hour to be consistent with the timeout threshold of baseline MIP attack while our BaB attack usually terminates much faster.
A.3 SETUP FOR COMPARED ATTACKS
We did small scale grid search for the best combination of hyperparameters for each attack. For FAB attack, we select 100-steps attack with 50 restarts and set Omaa = 0.1, B 0.9 and 7) = 1.05; for Square attack, we use 7000 queries. 20 restarts and set 0.6 as the size of squares. Note that FAB and Square attacks are part of the AutoAttack suite, but here we significantly increased their steps and number of iterations compared to the defaults in AutoAttack. For DIFGSM attack, we set a 6/255, decay rate as 0.9, number of iterations as 50 and the probability of applying input diversity as 0.5; for MIFGSM attack, we set = 2/255, decay rate as 0.9 and number of iterations as 20; for Distributional attack, we used 100 attack iterations, step size 0.01, and a balancing parameter of 0.05.
A.4 MORE EXPERIMENTAL RESULTS
We plot running time vs. number of attacked images for five more models in Figure 7 Our BaB at- tack achieves distinetly faster running time and produces more successful attacked images compared sovler.
the MIP attack using an
14

---

Under review as a conference paper at ICLR 2022
1.5
MIP attack
NIP attack
images
BaB attack
images
MIP attack
1000 MNIST-Conw-Small: running time (in 5)
1000
10
100
CIFAR-CNN-A-Adv: running time (in
CIFAR-CNN--BAdd running time (in
No. of imuqes attacked
BaB attack
No. of attocked
40
15
MIP attack
30
10
attack MIP attack
20
10
100
1000
10
300
1000
CIBAR-CNN-AMicc running time (in
CIFAR-Marabou:: running time (in
Figure 8: Running time number of attacked images compared to MIP attack five models.
15


Reviews:
[{"review_id": "dxZkqd9xiDZ", "reviewer": "Reviewer_wXK6", "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": "Strengths:\n- The paper has good novelty, combining techniques from several other papers into an interesting new technique\n- The proposed method is shown to provide a significant speed improvement over a vanilla MIP approach on the given tasks\n\nWeaknesses:\n- The experiments are only run on the adversarial examples which could not be solved by any other method, and only compared to the vanilla MIP approach. I would like to see some numbers comparing the proposed approach to some different methods for time and efficacy (the proposed method is slow so I would not expect to see this tried on a large dataset).\n", "summary_of_the_paper": "This paper introduces an efficient way to apply a branch-and-bound procedure to solve the mixed integer programming formulation of the problem of creating adversarial examples. This method of adversarial example creation is particularly designed to work in difficult cases where other methods fail.", "summary_of_the_review": "Overall the paper is good, demonstrating a novel method to quickly produce adversarial attacks in hard cases. It could be improved with the inclusion of more extensive experiments.", "strength_and_weaknesses": "", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "QZL_1vpyPYa", "reviewer": "Reviewer_G18n", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "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": "This paper is neatly written, the intuition and heuristic method is easy to follow, and experiments are convincing.\nHowever, this paper is purely heuristic-based where some theoretical results would be much appreciated, and experiments are not comprehensive, I feel like by keep working towards either one of these two aspects will highly improve the quality of this paper. \nAlso, while the adversarial attack is a very important problem, I think the basic idea presented in this paper is not fundamentally novel and in that regard, the contribution of this paper seems a bit weak.\nIn the following I list some of the detailed comments.\n\n1. Throughout, \"branch-and-bound\" and \"branch and bound\" are both used. You should be consistent, and the first one is more commonly used. Also, its abbreviation is usually denoted as B&B.\n2. Line after equation (1): \"ball around input x\", here $x$ should be $x_0$, denoting the benign input point. \n3. When you mention \"projected gradient descent\" you should mention (PGD) as its abbreviation, since you used PGD heavily in the later context. \n4. You should specify that N is the number ReLU neurons here. \n5. Second paragraph, page 2: You should specify that $N$ is the number ReLU neurons here. \n6. Second line on page 3: \"adversarial adversarial attack\" is wrong.\n7. All Eq. \\ref{...} should be Eq. \\eqref{...}\n8. For Eq. (2), you should mention for i=1, ..., L. Also, I think you should also impose $\\hat{z}^{(i)}(x) \\geq 0$. \n9. Page 3: \"can be provable obtained\" should be \"... provably ...\"\n10. The end of page 3: \"... is well explored recently ...\" here a reference would be appreciated.\n11. \"Adversarial common pattern\" on page 6 should be highlighted in italic.\n12. Second paragraph of page 7: \"T percent of\" doesn't make sense, it should be \"100*T percent\".\n13. In Fig. 6, for the experiments in (c), I cannot see the obvious improvement for attack margin. \n14. Detailed information of those data-sets should be mentioned. \n15. In Experiment section, it's better to mention Fig. 6 somewhere in this section, while giving a more detailed explanation. \n16. Experiments can be carried out and presented in a more detailed fashion. ", "summary_of_the_paper": "In this paper, the authors propose to solve the adversarial attack problem of ReLU neural network by using a branch-and-bound procedure, and search adversarial examples within the activation space corresponding to binary variables of a mixed-integer programming formulation. The experiments showcase that such adversarial attack framework enables them to find adversarial examples for hard instances where existing adversarial attacks fail. ", "summary_of_the_review": "This paper can be much improved by conducting a more extensive numerical experiments, basic idea is obvious and not fundamentally novel. ", "strength_and_weaknesses": "", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "IDBBEPi4_4J", "reviewer": "Reviewer_LiPk", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "Strengths:\n- This paper utilizes several technologies to accelerate the branch-and-bound procedure on finding adversarial examples for deep neural networks.\n- Compared to the baseline attack method (MIP attack), the proposed BaB attack achieves higher attack success rates within much less time. \n\nWeaknesses:\n- One drawback of the BaB attack is speed. Compared to the gradient-based attacks, which takes only a few seconds to generate adversarial example, the time cost of the BaB attack is not negligible.\n- The BaB attack consists of several parts, including bean search guided by neural network verifiers, diving in branch and bound, and large neighborhood search. However, no ablation experiments were presented to verify the effect of each part.\n- In the design of the BaB attack algorithm, many are heuristic and lack theoretical analysis. For example, the BaB attack utilizes lower bounds given by the bound propagation method $\\alpha, \\beta$-CROWN to guide beam search.\n- The written is unclear and difficult to understand.", "summary_of_the_paper": "This paper proposes a branch-and-bound attack (BaB-Attack) to solve hard instances efficiently, where none of the existing adversarial attacks can succeed. Specifically, the BaB-Attack utilizes the bound propagation-based neural network verifiers on GPUs to rapidly evaluate a large number of searching regions, builds an adversarial candidates pool to guide the search, and refines candidates adversarially\nexamples using a bottom-up large neighborhood search. Experimental results show that BaB-Attack outperforms the existing attacks in both attack success rates and efficiency.", "summary_of_the_review": "Overall, I think this paper is marginally below the acceptance threshold.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "52SRlF0by_", "reviewer": "Reviewer_aJSd", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "**Strengths:**\n1) New interesting way to approach adversarial attacks from a mixed integer programming perspective (although not fully clear why).\n2) Presented several heuristics that improves practicality and speed of the adversarial attack search.\n\n**Weaknesses:**\n1) Very difficult to understand the problem that the paper is trying to solve, the main idea, why the results are meaningful. \nWhy integer programming and such an esoteric formulation for adversarial attack search? \nWhat are the benefits of this formulation and method compared to the standard gradient based approach?\nI suggest rewriting the paper, especially the background part, to make it more understandable and accessible.\n2) Minor grammatical and punctual errors - “**an binary** encoding”, “locate adversarial examples **if exist**”, “**a**dversarial candidates pool dynamically filled...”, etc.\n", "summary_of_the_paper": "Authors proposed a novel branch and bound attack, which searches adversarial examples in the activation space of binary variables in a mixed integer programming formulation. They also present several heuristics such as top-down beam-search, diving, and bottom-up large neighborhood search guided by the adversarial candidates pool to efficiently obtain strong adversarial attacks better than standard MIP solvers and other SOTA methods.  ", "summary_of_the_review": "Since it is hard to capture the main point of the paper and the problem it is trying to solve, I tend to be on the rejection side.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This work proposes a branch and bound framework for adversarial attacks, based on the MIP formulation of attacking against ReLU networks. It adopts several heuristic tricks to accelerate the attack efficiency, and shows better attack performance on hard examples, compared to off-the-shelf MIP solvers. 

The main concerns in the first-round reviews include: 
1. The limited novelty, since the problem and formulation is not novel, and the proposed method is the combination of several heuristic tricks, without theoretical analysis. 
2. The experiments are insufficient, and only MIP solvers are compared, while other attack methods and the ablation study of different tricks are not presented. 
3. The efficiency is higher than off-the-shelf MIP solvers, but significantly lower than other adversarial attack methods.

The authors made great efforts to respond these concerns, such as adding some baseline attack methods and ablation studies. Most reviewers appreciated the authors' efforts and raised their initial score. However, after reading the revised manuscript, reviews and responses, I think many serious issues still exist. 
1. Since the proposed method is only applicable to the MIP formulation of attacking ReLU networks, it could not become a new baseline to attack mainstream deep neural networks, which significantly restrict its practical contribution to the community. And, it didn't provide novel theoretical tools or better theoretical results of analyzing the robustness of ReLU networks. It just reduce the gap to the verified robustness of existing verification methods. Thus, I cannot find significant contributions to the community of adversarial examples, from both practical and theoretical perspectives. 
2. The experiments are still insufficient. There have been massive advanced white-box and black-box attack methods. The added FAB, square (black-box), DIFGSM, MIFGSM (white-box), are popular methods, but not SOTA methods. Besides, only small images of MNIST and CIFAR-10 are tested, while large-scale images like ImageNet are not tested. It has been observed in many works, and according to my own experience, the attack performance on between small images (MNIST and CIFAR-10) and large images (ImageNet) is not always consistent. And, the low efficiency weakness (compared to other attack methods) of the proposed method may be further highlighted. 

It is not easy to decide to reject a submission with average score 7. The authors's efforts during their submission and the responses are greatly appreciated. However, I would like to accept works that can bring in real contributions to the research community. Hope the reviews and meta review could be helpful to further improve this work.
Decision: Reject