Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper aims to study the “computational complexity” of attacking versus that of defending machine learning models against adversarial attacks, which are test-time attacks that find so-called adversarial examples.

An adversarial example for an input x is a bounded perturbation of x that is misclassified.

The paper studies the worst-case computational complexity of finding adversarial examples (for a given perturbation threshold) vs. training a robust model. It is shown that in the *worst case* (even for basic ReLU models):
Finding adversarial examples is NP complete, while
Finding robust models is Sigma-2 complete. Sigma-2 is a bigger than (or equal to) complexity class than NP (and is conjectured to be strictly bigger).

The paper then defines a way of perhaps defending adversarial examples by trying to test robustness of the points one by one, and abstaining from answering when there is a non-robustness evidence. In particular, the paper applies a class S of attacks on each point, using a specific perturbation eps. Then, the thesis is that if we don’t find an example with eps perturbations, then perhaps it is relatively safe to assume that there is no such example for smaller eps’ < eps. The paper verifies this experimentally for small models for which the exact robustness can be computed.

Evaluation: I think the formulation of the problem this way has serious limitations that could prevent us from using these results for any real world insights. So I cannot support acceptance. See my comments below.

Considering NP completeness to reflect “easier task” than being Sigma-2 complete is both correct (theoretically) and wrong (practically). Theoretically, Sigma-2 is a “harder class” as it contains NP, but when it comes to running algorithms efficiently, there is no difference between them, as they both contain problems that we don’t know how to solve in polynomial time. So, there is a fundamental difference between the “computational approach” of this paper and that of e.g., Garg et al (cited work) where the distinction there is drawn between poly-time vs. non-poly-time algorithms. This makes the theoretical insight of this paper quite irrelevant to practice.

The paper does not pay attention that their notion of adversarial examples might *not* lead to misclassified inputs. For example, suppose we perturb x into x’ and the model changes the label for x’ while the true label is the changed label. (e.g., changing a cat image to a dog image while the model predicts the dog as dog). This should not constitute an adversarial example. E.g., see the work of “revisiting adversarial examples” by Suggala et al. Without this subtle point being fixed, it is hard to interpret the results of the paper as attacks. This might seem like a minor thing, but it becomes clear that it is a major issue when one notices that hardness of robust or non-robust learning of a task crucially depends on *what class of concept functions* we want to learn. E.g., one can show that simple function classes *can* be learned robustly and the literature is full of such results. This shows another flaw with the formulation of the problem in this paper.

The computational complexity of adversarially robust learning is an *average-case* phenomenon. Namely, we would like to know, what is adversary’s chance of making x misclassified, when we (say i.i.d) sample the training set, then train (perhaps in a randomized way) a model, and then pick x at random, and finally let adversary perturb x. So, even though the perturbation itself is studied in the worst-case, the whole problem is average-case. As an example, breaking crypto-systems is an average case task, even though one can find specific ciphertex whose complexity *in the worst case* is NP complete, yet finding NP complete encryption schemes is a major open question in cryptography.

By now, there is a rich literature on “certifying” robustness of decisions per instance. The paper seems to invent the wheel here and give a *weaker* certification than what those works offer, in terms of its guarantee. While other works on certification are provably right, here we only get a heuristic claim. This looks like a step back.

In addition, there is also a (by now rich) line of work on “abstaining” from answering queries for the sake of robustness. This paper’s approach is different, but still quite relevant, to that line of work. So it is good to do a discussion and compare. (As I understand those works try to abstain from answering the perturbed inputs, while this paper’s approach is to not answer even when x is not perturbed, but is just close to a dangerous perturbation). My understanding is that this approach hurts the correctness/accuracy much more, as it might abstain from answering normal instances as well.

strength_and_weaknesses: Strength: aiming for a computational understanding of the adversarial example phenomenon and explaining why defending is hard.

Mild weakness: the NP completeness results, as formulated, are rather trivial. For example, if we allow the model to compute SAT instances, is is clear that finding a "close point that is misclassified" could be NP complete, because one can choose the model and the input in such a way that doing so is the same as solving an arbitrary SAT instance.

Weakness: there are several severe limitations on how much one can interpret the results of this paper in relation with practice. The experimental part is extensive, but its guarantee is only heuristic while there is a line of work on provably certifying robustness of decisions.


clarity,_quality,_novelty_and_reproducibility: The paper is written quite clearly. The approach is novel, but also flawed in some sense.

summary_of_the_review: Interesting direction for studying the complexity of adversarial examples vs defending against test time evasion attacks. The weakness is that the formulation of the problem does not give an actual insight on how much is the running time of those tasks in practice, as the formulation is in the worst case and there is no major difference between NP completeness and sigma-2 completeness in practice; they are both not feasible. See more details in the detailed review.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proves that attacking a polynomial-time classifier is NP-complete, and training a polynomial-time model that is robust on a
single input is Σ_2^P-complete. The authors proposed a method that evaluates on the fly if a model is robust on a specific point by running
an adversarial attack on the input. Based on this, the authors proposed a dataset of provably optimal adversarial examples found on
images of MNIST and CIFAR10 for 6 small-scale Neural Networks.
strength_and_weaknesses: Strength:
The authors provided a thorough theoretical analysis of the complexity of neural network adversarial robustness. The proposed counter-attack method is very simple but is able to take advantage of existing defenses and provide robustness guarantees. The authors also showed detailed information about their experiments.
Weakness:
1. In the main text, it would be great if the authors can present a table for comparison between CA and existing defense methods on their certified robustness accuracy, as well as adversarial accuracy under different attacks. 
2. Please refrain from only using color to distinguish curves in Figure 2, as it may not be friendly to readers with color blindness.
clarity,_quality,_novelty_and_reproducibility: In general, I think this paper is well-written and organized. The motivation and rationale of the proposed method are introduced clearly.
summary_of_the_review: In general, I think the proposed method is well-motivated and the studies are solid. So I recommend a weak accept.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: To improve the attack-defense gap for robust classifiers, the paper suggests using a sample-specific attack-based flag, Counter-Attack(CA),  that tells the user if there are adversarial samples within a $\epsilon$-ball of the given sample. In the case of a perfect attack, the authors show that Counter-Attack also provides a computational robustness guarantee that it is hard to find unflagged adversarial examples beyond the threat models $\epsilon$ radius. 

However, the paper also formally proves that, under broad assumptions, attacking a polynomial-time classifier is $NP$-complete, while training a polynomial-time model that is robust on even a single input is $\Sigma^P_2$-complete. They also extend these results to the case of general non-polynomial time classifiers.

The authors suggest using a heuristic attack to flag examples for practical purposes. To improve the validity of this approach, the authors recommend using a higher radius for the heuristic attacks to make up for their relative weakness to a perfect attack. To this end, the authors study the consistency between the average distance of an adversarial example found by the heuristic attacks vs. the perfect attack or MNISt and CIFAR10 datasets. The empirical results show that for a well-chosen suit of attacks, the gap is pretty consistent in the evaluated examples.
strength_and_weaknesses: Strengths
- The complexity results for attacking polynomial models and training robust polynomial models provide a reasonable explanation for the hardness of doing these tasks on practical datasets.
- The empirical results showing that the attack radius achieved by a suit of weaker attack strongly correlates with the actual radius of the decision boundary around an example is very interesting and provides a good justification for the CA approach.

Weakness
- The underlying ideas presented in the paper are not very novel. Similar hardness results for ReLU networks do exist in previous papers. The flagging of specific examples provides a heuristic guarantee in contrast to the solid theoretical guarantees provided by other certification methods. The use case of Counter-Attack is not very clear to me.
-  Due to the computational limitations of the MIP solvers, the empirical justification for the method is only shown on small neural networks. It is not clear whether these results extend to general neural networks with more complicated architectures.
clarity,_quality,_novelty_and_reproducibility: The paper provides an interesting approach to bridging the attack-defense gap for robust classifiers. Some of the ideas and empirical results in the paper are new and interesting. The paper is also very clearly written and provides detailed proof of the theorems listed. The authors also provide all relevant details to reproduce the results. They also created a dataset UG100, recording some of the results for optimal bounds provided in the paper.
summary_of_the_review: The idea of using the success of a suit of heuristic attacks to flag vulnerable examples is interesting, but it is not clear if there is a specific use case where it would help. Although the paper establishes some interesting theoretical results for the power of this method when used with a perfect attack, none of the guarantees extend to the setting of heuristic attacks. The empirical evidence provided to show the effectiveness is only limited to a very small set of architectures for shallow neural networks. It is not clear if these observations hold in general. As for the setting of shallow neural networks, some of the formal verification methods already provide good bounds. 

I feel the paper provides some interesting results that might serve as an interesting starting point for further investigation. However, it does not provide enough justification to use the proposed Counter-Attack method.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper proves that attacking a polynomial-time classifier is NP-complete, and training a polynomial-time model that is robust on a single input is Σ_2^P-complete. The theory seems solid. But the reviewers find that the theory can not provide the insight on the running time in practice. The related work also shows the similar hardness results for ReLU networks. The experiments are also not extensive.
Decision: Reject