Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: Authors extend deepFool by adding extra steps and constraints to find closer points to the source image as the adversarial image. They both project onto the decision boundary. Deepfool does and adhoc clipping to keep the pixel values in (0,1) but the new proposed method respects the constraints during the steps. Also during the steps they combine projection of last step result and original image to keep it closer to the original image. Moreover, at the end of the optimization they perform extra search steps to get closer to the original image. Also they add random restarts. Rather than considering the original image, they randomly choose an image in the half ballpark of the total delta.

According to the results in fig.2 the backward steps has the highest impact in comparison to deepfool. But mixing with original projection always helps a little and random restarts help a little too. Without the backward steps there is almost no gain from mixing the projections.

Considering the full results in the appendix, the results are mixed with no obvious advantage in comparison to PGD specially.
review_title: Official Blind Review #1

final_score: rating: 6: Weak Accept
review_content: The authors propose a new gradient-based method (FAB) for constructing adversarial perturbations for deep neural networks. At a high level, the method repeatedly estimates the decision boundary based on the linearization of the classifier at a given point and projects to the closest "misclassified" example based on that estimation (similar to DeepFool). The authors build on this idea, proposing several improvements and evaluate their attack empirically against a variety of models.

I found the proposed method quite interesting and intuitive. All the improvements made to the core method are well-motivated and clearly explained, while the ablation experiments are relatively thorough.

However, I did find the presentation of experimental evidence quite misleading. 

Specifically, reporting mean accuracy over models, datasets, and epsilon constraints in Table 2 does not give the full picture. Going through the appendix tables, we can see the following:
-- The step size used for PGD is quite large---eps/4 for the L2 case---which is quite uncommon when using 150 iterations. Based on prior work and my own personal experience, a step size of 2 * eps / #steps (i.e., eps / 75) would seem more suitable. I wonder if this is the reason for PGD performing worse than FAB for large epsilon values on CIFAR10. The authors mention that they chose this parameter using grid search but do not provide concrete details.
-- The adversarially trained MNIST model of Madry et al. 2018 learns to use thresholding filters as the first layer (observed in the original paper). This causes issues for most gradient-based methods (e.g., PGD performs worse than the decision-based attack of Brendel et al. 2018, also observed in other prior work). While it is encouraging that FAB is robust to such gradient obfuscation, this is arguably not the ideal setting to compare gradient based methods (especially when averaging performance over models). 
-- For MNIST and Restricted IN, PGD performs comparably or even better than FAB (modulo larger epsilon values for which the large step size used could be an issue for PGD and the Linf-trained model with the thresholding filters).
-- For the L1-norm setting, EAD performs similarly or better compared to FAB (again modulo the Linf-trained model).
Based on these observations, I am not fully convinced that FAB outperforms PGD (for L2 and Linf) and EAD (for L1) by as much as Table 2 suggests.

Moreover, the runtime comparison performed in not exactly fair:
-- It is not clear how many restarts where included in the runtime of PGD. Its runtime should be in the same ballpark as FAB but the time reported is ~20x higher. 
-- PGD is known to produce quite accurate estimates when run with much fewer (say 15) steps. Thus in order to make a fair comparison one would also need to look at the entire #steps vs robust accuracy curve to get a better picture of the efficiency of these two methods. Choosing an arbitrary number of steps for each method is not very enlightening.
-- It is not necessary to run PGD 5 times to evaluate the robust accuracy at 5 thresholds. One can perform binary search for each input in order to find the smallest epsilon for which a misclassification can be found. This will result in at most 3 (sometimes 2) evaluations per point (instead of 5).

Despite these shortcomings of the experimental evaluation, I still believe that the paper has merit. After all, the method is clean and well-motivated,  performs comparably to the best of PGD and EAD in a variety of settings, and is robust to a certain degree of gradient masking. In that sense, it could potentially be a valuable contribution and could be of interest to a subset of the adversarial ML community.

In the sense, while my initial stance is to recommend (weak) rejection, I would be open to increasing my score and recommending (weak) acceptance should my concerns be addressed.

UPDATE: I appreciate the response and the additional experiments performed by the authors. The authors have addressed my concerns in their response. I am increasing my score to a weak accept.

One thing that would be nice to add in the next version of the manuscript is a note inviting the reader to consider the appendix tables since average robust accuracy can be inconclusive.
review_title: Official Blind Review #2

final_score: rating: 6: Weak Accept
review_content: The paper studies the problem of the white-box attack of neural network-based classifiers, with an emphasis on the "minimal distortion solution": The new input that changes the labeling output of the network with the minimal distance (l1, l2, l_inf) with respect to a given input. 

The main intuition of the algorithm is to do a local linear approximation of the network at the current point (which is the Taylor expansion up to the gradient term). After that, the algorithm identifies a class (output coordinate) with the minimal "margin to gradient norm ratio", i.e. the total movement in gradient direction to change the labeling function in that coordinate, within this linear approximation. The algorithm solves the subproblem of minimizing a linear function inside lp ball as the critical routine.

Overall, the notion of finding the minimal distortion attacker as opposed to finding the best attacker inside a fixed distortion ball is quite interesting to me. The main concern for me about this paper is the comparison to other methods such as PGD. As far as I know, these attackers DO NOT explicitly minimize the distortion, thus it is quite believable that these models do not identify the minimal distortion solution (rather it will more likely to find a solution that lies in the boundary since it would be the easiest way to attack). However, for the proposed algorithm in this paper, the algorithm is explicitly minimizing the distance to the given input (x_orig in their language). 


I would like to see more implementation details of the other algorithms, for example, what is the performance if we add an additional regularizer as the distance of the current attacker to the given input to PGD. So far, the paper lacks solid proof of the usefulness of this particular algorithm. (In particular the justification for solving the local linear system instead of doing a gradient descent step).

After Rebuttal: I have read the authors' responses and acknowledge the sensibility of the statement. I apologize for the earlier misunderstanding and higher the score accordingly.

review_title: Official Blind Review #3

Meta-review: This work presents a method for generating an (approximately) minimal adversarial perturbation for neural networks. During the discussion period, the AC raised additional concerns that were not originally addressed by the reviewers. The method is an iterative first order method for solving constrained optimization problems, however when considered as a new first order optimization method the contribution seems minimal. Most of the additions are rather straightforward---e.g. using a line search at each step to determine the optimal step size---and the reported gains over PGD are unconvincing. PGD can be considered as a "universal" first order optimizer [1], as such we should be careful that the reported gains are substantial and not just a question of tuning. Given that using a line search at each step increases the computational cost by a multiplicative factor, the comparison with PGD should take this into account.

The AC notes several plots in the Appendix show PGD having better performance (particularly on restricted Imagenet), and for others there remain questions on how PGD is tuned (for example the CIFAR-10 plots in Figure 5). One of two things explains the discrepancies in Figure 5: either PGD is finding a worse local optimum than FAB, or PGD has not converged to a local optimum. There needs to be provided experiments to rule out the second possibility, as this is evidence that PGD is not being tuned properly. Some standard things to check are the step size and number of steps. Additionally, enforcing a constant step size after projection is an easy way to improve the performance of PGD. For example, if the gradient of the loss is approximately equal to the normal vector of the constraint, then proj(x_i+ lambda * g) ~ x_i will result in an effective step size that is too low to make progress.

Finally, it is unclear what practical use there is for a method that finds an approximately minimum norm perturbation. There are no provable guarantees so this cannot be used for certification. Additionally, in order to properly assess the security and reliability of ML systems, it is necessary to consider larger visual distortions, occlusions, and corruptions (such as the ones in [2]) as these will actually be encountered in practice. 

1. https://arxiv.org/pdf/1706.06083.pdf
2. https://arxiv.org/abs/1807.01697
Decision: Reject