Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: 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. 
main_review: This paper is neatly written, the intuition and heuristic method is easy to follow, and experiments are convincing.
However, 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. 
Also, 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.
In the following I list some of the detailed comments.

1. 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.
2. Line after equation (1): "ball around input x", here $x$ should be $x_0$, denoting the benign input point. 
3. When you mention "projected gradient descent" you should mention (PGD) as its abbreviation, since you used PGD heavily in the later context. 
4. You should specify that N is the number ReLU neurons here. 
5. Second paragraph, page 2: You should specify that $N$ is the number ReLU neurons here. 
6. Second line on page 3: "adversarial adversarial attack" is wrong.
7. All Eq. \ref{...} should be Eq. \eqref{...}
8. For Eq. (2), you should mention for i=1, ..., L. Also, I think you should also impose $\hat{z}^{(i)}(x) \geq 0$. 
9. Page 3: "can be provable obtained" should be "... provably ..."
10. The end of page 3: "... is well explored recently ..." here a reference would be appreciated.
11. "Adversarial common pattern" on page 6 should be highlighted in italic.
12. Second paragraph of page 7: "T percent of" doesn't make sense, it should be "100*T percent".
13. In Fig. 6, for the experiments in (c), I cannot see the obvious improvement for attack margin. 
14. Detailed information of those data-sets should be mentioned. 
15. In Experiment section, it's better to mention Fig. 6 somewhere in this section, while giving a more detailed explanation. 
16. Experiments can be carried out and presented in a more detailed fashion. 
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.
review_title: null

final_score: rating: 8: accept, good paper
review_content: 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.
main_review: Strengths:
- The paper has good novelty, combining techniques from several other papers into an interesting new technique
- The proposed method is shown to provide a significant speed improvement over a vanilla MIP approach on the given tasks

Weaknesses:
- 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).

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.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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
examples using a bottom-up large neighborhood search. Experimental results show that BaB-Attack outperforms the existing attacks in both attack success rates and efficiency.
main_review: Strengths:
- This paper utilizes several technologies to accelerate the branch-and-bound procedure on finding adversarial examples for deep neural networks.
- Compared to the baseline attack method (MIP attack), the proposed BaB attack achieves higher attack success rates within much less time. 

Weaknesses:
- 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.
- 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.
- 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.
- The written is unclear and difficult to understand.
summary_of_the_review: Overall, I think this paper is marginally below the acceptance threshold.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.  
main_review: **Strengths:**
1) New interesting way to approach adversarial attacks from a mixed integer programming perspective (although not fully clear why).
2) Presented several heuristics that improves practicality and speed of the adversarial attack search.

**Weaknesses:**
1) Very difficult to understand the problem that the paper is trying to solve, the main idea, why the results are meaningful. 
Why integer programming and such an esoteric formulation for adversarial attack search? 
What are the benefits of this formulation and method compared to the standard gradient based approach?
I suggest rewriting the paper, especially the background part, to make it more understandable and accessible.
2) Minor grammatical and punctual errors - “**an binary** encoding”, “locate adversarial examples **if exist**”, “**a**dversarial candidates pool dynamically filled...”, etc.

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.
review_title: null

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