Binarized Neural Networks (BNNs) have recently attracted significant interest due to their computational efficiency. Concurrently, it has been shown that neural networks may be overly sensitive to ``attacks" -- tiny adversarial changes in the input -- which may be detrimental to their use in safety-critical domains. Designing attack algorithms that effectively fool trained models is a key step towards learning robust neural networks.
 The discrete, non-differentiable nature of BNNs, which distinguishes them from their full-precision counterparts, poses a challenge to gradient-based attacks. In this work, we study the problem of attacking a BNN through the lens of combinatorial and integer optimization. We propose a Mixed Integer Linear Programming (MILP) formulation of the problem. While exact and flexible, the MILP quickly becomes intractable as the network and perturbation space grow. To address this issue, we propose IProp, a decomposition-based algorithm that solves a sequence of much smaller MILP problems. Experimentally, we evaluate both proposed methods against the standard gradient-based attack (PGD) on MNIST and Fashion-MNIST, and show that IProp performs favorably compared to PGD, while scaling beyond the limits of the MILP. The success of neural networks in vision, text and speech tasks has led to their widespread deployment in commercial systems and devices. However, these models can often be fooled by minimal perturbations to their inputs, posing serious security and safety threats BID13 . A great deal of current research addresses the "robustification" of neural networks using adversarially generated examples BID19 BID22 , a variant of standard gradient-based training that uses adversarial training examples to defend against possible attacks. Recent work has also formulated the problem of "adversarial learning" as a robust optimization problem BID22 BID17 BID29 , where one seeks the best model parameters with respect to the loss function as measured on the worst-case adversarial perturbation of each point in the training dataset. Attack algorithms may thus be used to augment the training dataset with adversarial examples during training, resulting in more robust models BID19 . These new advances further motivate the need to develop effective methods for generating adversarial examples for neural networks.In this work, we focus on designing effective attacks against Binarized Neural Networks (BNNs) BID8 . BNNs are neural networks with weights in {−1, +1} and the sign function non-linearity, and are especially pertinent in low-power or hardware-constrained settings, where they have the potential to be used at an unprecedented scale if deployed to smartphones and other edge devices. This makes attacking, and consequently robustifying BNNs, a task of major importance. However, the discrete, non-differentiable structure of a BNN renders less effective the typical attack algorithms that rely on gradient information. As strong attacks are crucial to effective adversarial training, we are motivated to address this problem in the hope of generating better attacks.The goal of adversarial attacks is to modify an input slightly, so that the neural network predicts a different class than what it would have predicted for the original input. More formally, the task of generating an optimal adversarial example is the following: Given:-A (clean) data point x ∈ R n ;-A trained BNN model with parameters w, that outputs a value f c (x; w) for a class c ∈ C; -prediction, the class predicted for data point x, arg max c∈C f c (x; w); -target, the class we would like to predict for a slightly perturbed version of x; -, the maximum amount of perturbation allowed in any of the n dimensions of the input x. We developed combinatorial search methods for generating adversarial examples that fool trained Binarized Neural Networks, based on a Mixed Integer Linear Programming (MILP) model and a target propagation-driven iterative algorithm IProp. To our knowledge, this is the first such integer optimization-based attack for BNNs, a type of neural networks that is inherently discrete. Our MILP model results show that standard (PGD) attack methods often are suboptimal in generating good adversarial examples when the perturbation budget is limited. The ultimate goal is to "attack to protect", i.e. to generate perturbations that can be used during adversarial training, resulting in BNNs that are robust to a class of perturbation. Unfortunately, our MILP model cannot be solved quickly enough to be incorporated into adversarial training. On the other hand, through extensive experiments we have shown that our iterative algorithm IProp is able to scale-up this solving process while maintaining good performance compared to the PGD attack. With these contributions, we believe we have laid the foundations for improved attacks and potentially robust training of BNNs. This work is a good example of successful cross fertilization of ideas and methods from discrete optimization and machine learning, a growing synergistic area of research, both in terms of using discrete optimization for ML as was done here BID11 BID2 , as well as using ML in discrete optimization tasks BID14 BID28 BID16 BID18 BID9 . We believe that target propagation ideas such as in IProp can be potentially extended for the problem of training BNNs, a challenging task to this day. The same can be said about hard-threshold networks, as hinted to by BID11 . We implemented the method of "simultaneous perturbation stochastic approximation" (SPSA) BID30 , which was recently used in BID33 as an example of a gradient-free attack. Our implementation of SPSA follows BID33 and uses the Adam optimization method with learning rate 0.01, a stochastic sample of perturbations (referred to as "batch size" in BID33 ) of size 100, and an iteration limit of 100. As with PGD, SPSA is run with random restarts every 100 iterations until the time limit of 180 seconds is reached. FIG10 shows the flip prediction rates for IProp (same as in FIG3 in the main text) and SPSA. Generally, SPSA performs worse than IProp and PGD.
Gradient-based attacks on binarized neural networks are not effective due to the non-differentiability of such networks; Our IPROP algorithm solves this problem using integer optimization Proposes a new target propagation style algorithm to generate strong adversarial attacks on binarized neural networks. This paper proposed a new attack algorithm based on MILP on binary neural networks. This paper presents an algorithm to find adversarial attacks to binary neural networks which iteratively finds desired representations layer by layer from the top to the input and is more efficient than solving the full mixed integer linear programming (MILP) solver.