(De)Randomized Smoothing for Certifiable Defense against Patch Attacks

Introduction

In recent years, adversarial attacks have become a topic of great interest in machine learning . However, in many instances the threat models considered for these attacks (e.g. small $L_{\infty}$ distortions to every pixel of an image) implicitly require the attacker to be able to directly interfere with the input to a neural network. This limits practicality of such attacks as well as defenses against them. On the other hand, the development of physical adversarial attacks , in which small visible changes are made to real world objects in order to disrupt classification of images of these objects, represents a more concerning security threat. Unlike $L_{p}$ attacks, physical adversarial attacks can be perceptible (e.g. adding an adversarial sticker on a stop sign is a perceptible change). Nevertheless, humans would still correctly classify the attacked image while the classification model would fail to predict the correct label. Therefore, the attacked image is an adversarial example.

Physical adversarial attacks can often be modeled as “patch” adversarial attacks, in which the attacker can make arbitrary changes to pixels within a region of bounded size. Indeed, there is often a direct relationship between the two: for example, the universal patch attack proposed by is an effective physical sticker attack. The attack method proposed in is universal in a sense that pixels of the adversarial patch do not depend on the attacked image. Image-specific patch attacks have also been proposed, such as LaVAN , which reduces ImageNet classification accuracy to 0% using only a $42\times 42$ pixel square patch (on images of size $299\times 299$). In this paper, we consider all attacks (image-specific or universal) on square patches of size $m\times m$.

Practical defenses against patch attacks have been proposed. For the aforementioned $42\times 42$ pixel attacks on ImageNet, claims the current state-of-the-art practical defense. However, has recently broken this defense, reducing the classification accuracy on ImageNet to 14%. In the same work, also proposes the first certified defense against patch adversarial attacks, which uses interval bound propagation . In a certifiably robust classification scheme, in addition to providing a classification for each image, the classifier may also return an assurance that the classification will provably not change under any distortion of a certain magnitude and threat model. One then reports both the clean accuracy (normal accuracy) of the model, as well as the certified accuracy (percent of images which are both correctly classified, and for which it is guaranteed that the classification will not change under a certain attack type). Unlike practical defenses, certified defenses guarantee that no future adversary (under a certain threat model) will break the defense.

The certified defense proposed by , however, does not scale well to practical classification tasks on complex inputs such as CIFAR-10 or ImageNet samples. Specifically, while this certified defense performs well on MNIST, it achieves poor certified accuracy on CIFAR-10 and, to quote from the paper itself, “is unlikely to scale to ImageNet.” In this work, we propose a certified defense against patch attacks which overcomes these issues. In particular, our certifiable defense method leads to the following results:

Notably, our method achieves a more than $27$ percentage point increase in certified robustness on CIFAR-10 compared to . Moreover, our method has top-1 certified accuracy on ImageNet classification which is approximately equal to the 14% empirical accuracy of the state-of-the art practical defense under the attack proposed by (although our clean accuracy is lower, 44% vs. 71%). On MNIST, which is often regarded as a toy dataset in deep learning applications, our method also achieves a relatively high certified robustness (but not as high as the method of ) and clean accuracy (slightly higher than that of ). Further, the certified defense proposed by also has a computationally expensive training algorithm: the training time for the reported best model was 8.4 GPU hours for MNIST, and 15.4 GPU hours for CIFAR-10, using NVIDIA 2080 Ti GPUs. Our models, by contrast, took approximately 1.0 GPU hour to train on MNIST, and 2.5 GPU hours to train on CIFAR-10, on the same model of GPU.

Our certifiably robust classification scheme is based on randomized smoothing, a class of certifiably robust classifiers which have been proposed for various threat models, including $L_{2}$ , $L_{1}$ and $L_{0}$ and Wasserstein metrics. All of these methods rely on a similar mechanism where noisy versions of an input image $\mathbf{x}$ are used in the classification. Such noisy inputs are created either by adding random noise to all pixels or by removing (ablating) some of the pixels . A large number of noisy images are then classified by a base classifier and then the consensus of these classifications is reported as the final classification result. For an adversarial image $\mathbf{x}^{\prime}$ at a bounded distance from $\mathbf{x}$, the probability distributions of possible noisy images which can be produced from $\mathbf{x}$ and $\mathbf{x}^{\prime}$ will substantially overlap. This implies that, if a sufficiently large fraction of noisy images derived from $\mathbf{x}$ are classified to some class $c$, then with high confidence, a plurality of noisy images derived from $\mathbf{x}^{\prime}$ will also be assigned to this class.

Patch adversarial attacks can be considered a special case of $L_{0}$ (sparse) adversarial attacks: in an $L_{0}$ attack, the adversary can choose a limited number of pixels and apply unbounded distortions to them. A patch adversarial attack is therefore a sparse adversarial attack where the attacker is additionally constrained to selecting only a block of adjacent pixels to attack, rather than any arbitrary pixels. The current state-of-the-art certified defense against sparse adversarial attacks is a randomized smoothing method proposed by . In this method, a base classifier, $f(\mathbf{x})$, is trained to make classifications based on only a small number of independently randomly-selected pixels: the rest of the image is ablated, meaning that it is encoded as a null value. At test time, the final classification $g(\mathbf{x})$ is taken as the class most likely to be returned by $f$ on a randomly ablated version of the image.

In practice, we find that applying the defense method developed in for sparse attacks directly to patch attacks yields poor results (see Figure 1). This is because the defense proposed in does not incorporate the additional structure of the attack. For patch attacks, we can use the fact that the attacked pixels form a contiguous square to develop a more effective defense. In this paper, we propose a structured ablation scheme, where instead of independently selecting pixels to use for classification, we select pixels in a correlated way in order to reduce the probability that the adversarial patch is sampled. Empirically, structured ablation certificates yields much improved certified accuracy to patch attacks, compared to the naive $L_{0}$ certificate.

By reducing the total number of possible ablations of an image, structured ablation allows us to de-randomize our algorithm, yielding improved, deterministic certificates. For $L_{0}$ robustness, achieves the largest median certificates on MNIST by using a base classifier $f$ which classifies using only $45$ out of $784$ pixels. There are $\binom{784}{45}\approx 4\times 10^{73}$ ways to make this selection. It is therefore not feasible to evaluate precisely the probability that $f(\mathbf{x})$ returns any particular class $c$: one must estimate this based on random samples. Using our proposed methods, the number of possible ablations is small enough so that it is tractable to classify using all possible ablations: we can exactly evaluate the probability that $f(\mathbf{x})$ returns each class. Our certificate is therefore exact, rather than probabilistic, so our classifications are provably robust in an absolute sense.

Determinism provides another benefit: the absence of estimation error increases the certified accuracies that can be reported. Additionally, because estimation error is no longer a concern, derandomization allows us to use more rich information from the base classifier without incurring an additional cost in increased estimation error. We take advantage of this to allow the base classifier to abstain in cases where it cannot make a high-confidence prediction towards any class. This leads to substantially increased certificates on MNIST, although the effects on CIFAR-10 are not significant.

After the initial distribution of this work, improved upon it by proposing a tighter certificate. In a concurrent work to ours, also proposes a method similar to “block smoothing” proposed below.

Certifiable Defenses against Patch Attacks

As mentioned in the introduction, patch attacks can be regarded as a restricted case of $L_{0}$ attacks. In particular, let $\rho$ be the magnitude of an $L_{0}$ adversarial attack: the attacker modifies $\rho$ pixels and leaves the rest unchanged. A patch attack, with an $m\times m$ adversarial patch, is also an $L_{0}$ attack, with $\rho=m^{2}$. We can then attempt to apply existing certifiably robust classification schemes for the $L_{0}$ threat model to the patch attack threat model: we simply need to certify to an $L_{0}$ radius of $\rho=m^{2}$. Consider specifically the $L_{0}$ smoothing-based certifiably robust classifier introduced by . In this classification scheme, given an input image $\mathbf{x}$, the base classifier $f$ classifies a large number of distinct randomly-ablated versions of $\mathbf{x}$, in each of which only $k$ pixels of the original image are randomly and independently selected to be retained and used by the base classifier $f$. Therefore, for any choice of $\rho$ pixels that the attacker could choose to attack, the probability that any of these $\rho$ pixels is also one of the $k$ pixels used in $f$’s classification is:

where $\rho$ is the number of attacked pixels, $k$ is the number of retained pixels used by the base classifier, and the overall dimensions of the input image $\mathbf{x}$ are $h\times w$. To understand this, note that the classifier has $k$ opportunities to choose an attacked pixel, and $\rho$ out of $hw$ pixels are attacked. Clearly, if $f$ does not use any of the attacked pixels, then its output will not be corrupted by the attacker. Therefore, the attacker can change the output of $f(\mathbf{x})$ with probability at most $\Delta$. Let $c$ be the majority classification at $\mathbf{x}$ (i.,e., $g(\mathbf{x})=c$). If $f(\mathbf{x})=c$ with probability greater than $0.5+\Delta$, then for any distorted image $\mathbf{x}^{\prime}$, one can conclude that $f(\mathbf{x}^{\prime})=c$ with probability greater than $0.5$, and therefore that $g(\mathbf{x}^{\prime})=c$. As discussed in the introduction, while this technique produces state-of-the-art guarantees against general $L_{0}$ attacks, it yields rather poor certified accuracies when applied to patch attacks, because it does not take advantage of the structure of the attack (See Figure 1; data for MNIST are provided in supplementary material.).

2 Proposed Method: Structured Ablation

To exploit the restricted nature of patch attacks, we propose two structured ablation methods, which select correlated groups of pixels to reduce the probability $\Delta$ that the adversarial patch is sampled:

Block Smoothing: In this method, we select a single $s\times s$ square block of pixels, and ablate the rest of the image. The number of retained pixels is then $k=s^{2}$. Note that for an $m\times m$ adversarial patch, out of the $h\times w$ possible selections for blocks to use for classification, $(m+s-1)^{2}$ of them will intersect the patch. Thus, we have:

As illustrated in Figure 2, this implies a substantially decreased probability of intersecting the adversarial patch, compared to sampling $k$ pixels independently.

Band Smoothing: In this method, we select a single band (a column or a row) of pixels of width $s$, and ablate the rest of the image. In the case of a column, the number of retained pixels is then $k=sh$. For an $m\times m$ adversarial patch, out of the $w$ possible selections for bands to use for classification, $m+s-1$ of them will intersect the patch. Then we have:

For both of these methods, it is tractable to use the base classifier to classify all possible ablated versions of an image (i.e. $hw$ and $w$ possible ablations for block and column smoothing, respectively). This allows us to exactly compute the smoothed classifier, $g(\mathbf{x})$, yielding deterministic certificates.

Our experiments show that structured ablation produces higher certified accuracy than $L_{0}$ randomized ablation. This is because, for similar values of $\Delta$, structured ablation methods yield much higher base classifier accuracies (Figure 3). Empirically, we find that the band method (and specifically, column smoothing) produces the most certifiably robust classifiers (Figure 5). In supplementary materials, we explore structured ablation using multiple blocks or bands of pixels.

The final smoothed classification is simply the plurality class returned: $g(\mathbf{x}):=\arg\max_{c}n_{c}(\mathbf{x}).$ In the case of ties, we deterministically return the smaller-indexed class. Because the adversarial patch only intersects $(m+s-1)^{2}$ blocks, the adversary can only alter the output of $(m+s-1)^{2}$ of the evaluations of the base classifier. This yields the following guarantee:

For any image $\mathbf{x}$, base classifier $f$, smoothing block size $s$, and patch size $m$, if:

then for any image $\mathbf{x}^{\prime}$ which differs from $\mathbf{x}$ only in an $(m\times m)$ patch, $g(\mathbf{x}^{\prime})=c$.

In Theorem 1, the indicator function term (${\bm{1}}_{c>c^{\prime}}$) is present because we break ties deterministically by label index during the final classification. Proofs are provided in supplementary materials.

Note that the classifier counts $n_{c}(\mathbf{x})$ can be though of as exact estimates for the probability that the base classifier returns the class $c$, simply scaled up by a factor of $hw$. For the column smoothing case (or row smoothing, by simple transpose), we can compute a similar certificate. In this case, the base classifier is $f_{c}(\mathbf{x},s,x)$, where $s$ is now the width of the retained column of pixels, and $x$ is the position of the leftmost edge of this column. We then only need to sum over one dimension:

Again, we classify using $g(\mathbf{x}):=\arg\max_{c}n_{c}(\mathbf{x}).$ To derive the final guarantee, we now use that the adversarial patch will overlap with only $(m+s-1)$ columns:

For any image $\mathbf{x}$, base classifier $f$, smoothing column size $s$, and patch size $m$, if:

then for any image $\mathbf{x}^{\prime}$ which differs from $\mathbf{x}$ only in an $(m\times m)$ patch, $g(\mathbf{x}^{\prime})=c$.

In practice, we use a deep network as our base classifier, and set $f_{c}(\mathbf{x},s,x,y)=1$ if the logit corresponding to class $c$ is greater than a threshold hyperparameter $\theta$. This allows the base classifier to abstain from classifying in the case that there is no usable information in the retained block, as well as to “vote” for multiple classes, which may be beneficial if the base classifier top-1 accuracy is low.

The input of to the neural network used as the base classifier is a copy of the image $\mathbf{x}$, with all pixels except for those in the retained block or band replaced with a specially-encoded ‘NULL’ value. We encode the additional ‘NULL’ value in the input in the same manner described for randomized ablation by for each dataset tested: this involves adding additional color channels, so that the NULL value is distinct from all real pixel colors. During training, as in prior smoothing works, we train $f$ on ablated samples, using a single randomly-determined ablation pattern (selection of block or column to retain) on all samples in each batch.

3 Comparison to Conventional Randomized Smoothing

In conventional randomized smoothing, rather than computing the probability that $f$ returns each class directly, one must instead lower-bound, with high confidence, the probability $p_{c}$ that $f$ returns the plurality class $c$ and upper-bound the probabilities $p_{c^{\prime}}$ that $f$ returns all other classes, based on samples. This leads to decreased certified accuracy due to estimation error. Additionally, all of these bounds must hold simultaneously: in order to ensure that the gap between $p_{c}$ and $p_{c^{\prime}}$ is sufficiently large for each $c^{\prime}$ to prove robustness, one must bound the population probabilities for every class. Some works do this directly using a union bound, leading to increased error as the number of classes increases. Others, following , instead only use samples to lower-bound the probability $p_{c}$ that the base classifier returns the top class. One can then upper bound all other class probabilities by observing that $\forall c^{\prime},\,\,p_{c^{\prime}}\leq 1-p_{c}$. In other words, rather than determining whether $c$ will stay the plurality class at an adversarial point, one instead determines whether $c$ will stay the majority class. This is also the estimation method used by for $L_{0}$ certificates: this is why, when describing that method in Section 2.1, we gave the condition for certification as $p_{c}>0.5+\Delta$. In our deterministic method, we can use a less strict condition, that $\forall c^{\prime},\,\,p_{c}-p_{c^{\prime}}>2\Delta$, where $p_{c}=n_{c}/hw$ for block smoothing, and $p_{c}=n_{c}/w$ for column smoothing. (As described above, we can sometimes even certify in the equality case, when it is assured that $c$ will be selected if there is a tie between the class probabilities at the distorted point.)

In this work, we sidestep the estimation problem entirely by computing the population probabilities exactly. This substantially reduces evaluation time: for example, column smoothing on CIFAR-10 requires 32 forward passes, compared to $10^{4}-10^{5}$ for randomized ablation . (We provide measured evaluation times in supplementary material.) However, by avoiding the assumption of , that all probability not assigned to $c$ is instead assigned to a single adversarial class, we can make an additional optimization: we can add an ‘abstain’ option. If there is no compelling evidence for any particular class in an ablated image (i.e., if all logits are below a threshold value $\theta$), our classifier abstains. This prevents blocks which contain no information from being assigned to an arbitrary, likely incorrect class. Figure 5-a shows that this significantly increases the certified accuracy on MNIST, although it has little effect on CIFAR-10. Our threshold system also allows the base classifier to select multiple classes, if there is strong evidence for each of them. This is intended to increase certified accuracy in the case of a large number of classes, where the top-1 accuracy of the base classifier might be low: if the correct class consistently occurs within the top several classes, it may still be possible to certify robustness.

In a concurrent work, also proposes a derandomization of a randomized smoothing technique. However, the threat model considered is quite different: develops a defense against label-flipping poisoning attacks, where the adversary changes the labels of training samples. Notably, ‘s result only applies directly to linear base classifiers. By making this restriction, is able to analytically determine the probabilities of $f(\mathbf{x})$ returning each class. By contrast, our de-randomized technique for patch attacks does not restrict the architecture of the base classifier $f$, in practice a deep network.

Results

Certified robustness against patch attacks is presented for $5\times 5$ patches on MNIST and CIFAR-10 in Figure 5, using both block and column smoothing (On MNIST, we also tested smoothing with rows rather than columns, with slightly worse results: see supplementary materials.) Results in the figures are using a validation set of 5,000 images; the final results reported in Table 1 are on a separate test set of 5,000 images. On both datasets, we have found that column smoothing produces better certified accuracies than block smoothing. However, the performance gap is larger on MNIST than on CIFAR-10. We have also tested with the base classifier returning only the top-one class, rather than thresholding the logits to abstain on low confidence predictions. We find that thresholding produces a large improvement on MNIST, but has had little effect on CIFAR-10. This is possibly because MNIST images, when ablated, will often have zero information (i.e., be entirely black), while in natural images, the retained region will always have some information. In both datasets, we found that the column smoothing certificates are not highly sensitive to the threshold hyperparameter $\theta$.

Experiments using multiple blocks and columns, rather than just a single block or column for each base classification, are presented in supplementary materials.

In Figure 6, we show how our certificates scale to different patch sizes, beyond the standard $5\times 5$. On CIFAR-10, we maintain high certified accuracy even at a patch size of $9\times 9$. Notably, the optimal column width $s$ seems not to depend on the patch size, suggesting that a single trained model can defend against a broad class of patch attacks.

On ImageNet-1000 (ILSVRC2012), we have tested certified robustness to $42\times 42$ patch attacks with column smoothing alone, using column width $s=25$, and over the $\theta$ hyperparameter range $\theta=\{0.1,0.2,0.3,0.4\}$. We have used 1,000 images for validation, and 1,000 for test, using the optimal $\theta=0.2$; test set results are presented in Table 1. Full validation results for all datasets are presented as tables in supplementary materials.

We also compare column smoothing certificates for MNIST and CIFAR-10 to randomized column smoothing smoothing certificates on both datasets: see Table 2. We find that the “derandomization” improves the certificates independently of the effect of thresholding (for example, it increases the certified accuracy on CIFAR-10 by nearly 7 percentage points.)

We evaluated the empirical robustness of our method, specifically column smoothing, on CIFAR-10, using a modified version of the IFGSM patch attack from . In particular, because the zero-one base-classifications $f_{c}$ are non-differentiable, we cannot attack $n_{c}(\textbf{x})$ directly. Instead, in order to generate the attacks, we use a surrogate model in which $f_{c}$ returns SoftMax scores. Note that this is similar to ’s attack on Gaussian-smoothed classifiers, but there is no need to consider random sampling in this case. Further details on the attack are provided in supplementary materials. Results are presented in Figure 7-a. We note that, as expected, our certified lower bounds hold, and furthermore that our model is significantly more robust to patch adversarial attacks compared with an undefended baseline model. We also evaluated the robustness of our attack to a non-patch adversarial attack, specifically an $L_{\infty}$-bounded IFGSM attack. Because all base classifiers are attacked simultaneously in this model, our method provides no robustness guarantee, and one might worry that the model could be particularly vulnerable to the attack. However, while the accuracy under this attack was reduced compared to an undefended baseline model, this was not a dramatic effect: see Figure 7-b.

Conclusion

Patch adversarial attacks are important threat models because they formalize physical adversarial attacks. In this work, we propose Structured Ablation, a provably robust defense against patch attacks. Our method, an adaptation of randomized smoothing, significantly outperforms the state-of-the-art certified defense for patch attacks on CIFAR-10, and, unlike previous methods, scales to ImageNet.

Broader Impact

Adversarial patch attacks are extremely relevant to security threats posed by adversarial machine learning. In particular, patch attacks model physical adversarial attacks, in which real-world objects are manipulated in order to disrupt computer vision systems. Malicious use of such attacks could therefore be catastrophically damaging in highly critical applications of computer vision, such as self-driving cars. For example, consider an adversary that puts adversarial stickers on stop signs to cause significant errors in classification of those images by deep models deployed in autonomous vehicles. Such an attack could cause significant damage. Moreover, the existence of such vulnerabilities in deep models can harm the confidence of users of systems that employ such models, which could slow adoption of these systems. Our proposed techniques in this paper provide new provable and guaranteed defenses against these attacks, advancing the effort to mitigate these issues.

We note that the algorithms described in this paper are purely defensive. That is, this work does not reveal (in any way obvious to the authors) any unknown vulnerabilities in existing computer vision systems. While we do develop an adversarial attack against our classifier, this attack is a straightforward extension of existing work on adversarial attacks to smoothed classifiers : implementing this attack represents necessary due diligence to evaluate the robustness of our defense.

One possible negative outcome of provable robustness guarantees is that they may cause users to be overconfident in the reliability of machine learning systems in general. As we have demonstrated in Section 3.1, our techniques do not provide robustness to general adversarial attacks other than patch attacks. Further, a guarantee of robustness is not a guarantee of correctness: in fact, the accuracy of our classifiers is reduced compared to undefended models. Users should be aware of these issues before applying these techniques in critical applications.

Additionally, we acknowledge that, as for any computer vision advance, malicious actors could also use the techniques demonstrated here. For example, the application of these techniques could make it more difficult to thwart excessive and unwanted surveillance, posing a potential privacy concern. However, given the important safety applications described above, we believe that making this work available will have an overall positive impact.

Acknowledgements

This project was supported in part by NSF CAREER AWARD 1942230, grants from NIST 60NANB20D134, HR001119S0026, HR00111990077, HR00112090132 and Simons Fellowship on “Foundations of Deep Learning.”

References

Appendix A Proofs

We first prove the block smoothing algorithm. Recall the definitions and statement of Theorem 1. In particular, recall the base classification counts $n_{c}(\mathbf{x})$:

And recall the definition of the smoothed classifier:

where in the case of ties, we choose the smaller-indexed class as the argmax solution.

For any image $\mathbf{x}$, base classifier $f$, smoothing block size $s$, and patch size $m$, if:

then for any image $\mathbf{x}^{\prime}$ which differs from $\mathbf{x}$ only in an $(m\times m)$ patch, $g(\mathbf{x}^{\prime})=c$.

Let $(i,j)$ represent the upper-right corner of the $m\times m$ patch in which $\mathbf{x}$ and $\mathbf{x}^{\prime}$ differ. Note that, for all $c$, the output of $f_{c}(\mathbf{x},s,x,y)$ will be equal to the output of $f_{c}(\mathbf{x}^{\prime},s,x,y)$, unless the $s\times s$ block retained (starting at $(x,y)$) intersects with the $m\times m$ adversarial patch (starting at $(i,j)$). This condition occurs only when both $x$ is in the range between $i-s+1$ and $i+m-1$, inclusive, and $y$ is in the range between $j-s+1$ and $j+m-1$, inclusive. Note that there are $(m+s-1)$ values each for $x$ and $y$ which meet this condition, and therefore $(m+s-1)^{2}$ such pairs $(x,y)$. Therefore $f_{c}(\mathbf{x},s,x,y)=f_{c}(\mathbf{x}^{\prime},s,x,y)$ in all but $(m+s-1)^{2}$ cases.

Note that if $i-s+1<0$, then the intersecting values for $x$, taking into account the wrapping behavior of $f$, will be $h-(i-s+1)$ through $h$, and $0$ through $i+m-1$ (see Figure 4 in the main text): there are still $(m+s-1)$ such values, and a similar argument applies to $j$.

Therefore, because $f_{c}(\cdot)\in\{0,1\}$,

Now, consider any $c^{\prime}\neq c$, such that $n_{c}(\mathbf{x})\geq\left[n_{c^{\prime}}(\mathbf{x})+{\bm{1}}_{c>c^{\prime}}\right]+2(m+s-1)^{2}$. There are two cases:

$c>c^{\prime}$: In this case, in the event that $n_{c}({\mathbf{x}}^{\prime})=n_{c}^{\prime}({\mathbf{x}}^{\prime})$, we have that $g({\mathbf{x}}^{\prime})=c^{\prime}$. Therefore, a sufficient condition for $g({\mathbf{x}}^{\prime})\neq c^{\prime}$ is that $n_{c}({\mathbf{x}}^{\prime})>n_{c}^{\prime}({\mathbf{x}}^{\prime})$. By Equation 10 and triangle inequality, this must be true if $n_{c}(\mathbf{x})>\left[n_{c^{\prime}}(\mathbf{x})\right]+2(m+s-1)^{2}$, or equivalently, if $n_{c}(\mathbf{x})\geq\left[n_{c^{\prime}}(\mathbf{x})+{\bm{1}}_{c>c^{\prime}}\right]+2(m+s-1)^{2}$.

$c^{\prime}>c$: In this case, in the event that $n_{c}({\mathbf{x}}^{\prime})=n_{c}^{\prime}({\mathbf{x}}^{\prime})$, we have that $g({\mathbf{x}}^{\prime})=c^{\prime}$. Therefore, a sufficient condition for $g({\mathbf{x}}^{\prime})\neq c^{\prime}$ is that $n_{c}({\mathbf{x}}^{\prime})\geq n_{c}^{\prime}({\mathbf{x}}^{\prime})$. By Equation 10 and triangle inequality, this must be true if $n_{c}(\mathbf{x})\geq\left[n_{c^{\prime}}(\mathbf{x})+{\bm{1}}_{c>c^{\prime}}\right]+2(m+s-1)^{2}$.

Therefore, if $n_{c}(\mathbf{x})\geq\max_{c^{\prime}\neq c}\left[n_{c^{\prime}}(\mathbf{x})+{\bm{1}}_{c>c^{\prime}}\right]+2(m+s-1)^{2}$, then no class other than $c$ can be output by $g(\mathbf{x}^{\prime})$. ∎

The column smoothing method can be proved similarly. For completeness, we state and prove Theorem 2 here as well. Recall

For any image $\mathbf{x}$, base classifier $f$, smoothing band size $s$, and patch size $m$, if:

then for any image $\mathbf{x}^{\prime}$ which differs from $\mathbf{x}$ only in an $(m\times m)$ patch, $g(\mathbf{x}^{\prime})=c$.

Let $(i,j)$ represent the upper-right corner of the $m\times m$ patch in which $\mathbf{x}$ and $\mathbf{x}^{\prime}$ differ. Note that, for all $c$, the output of $f_{c}(\mathbf{x},s,x)$ will be equal to the output of $f_{c}(\mathbf{x}^{\prime},s,x)$, unless the band (of width $s$) retained, starting at column $x$, intersects with the $m\times m$ adversarial patch (starting at $(i,j)$). This condition occurs only when $x$ is in the range between $i-s+1$ and $i+m-1$, inclusive. Note that there are $(m+s-1)$ values for $x$ which meet this condition. Therefore $f_{c}(\mathbf{x},s,x,y)=f_{c}(\mathbf{x}^{\prime},s,x,y)$ in all but $(m+s-1)$ cases.

Again, if $i-s+1<0$, then the intersecting values for $x$, taking into account the wrapping behavior of $f$ will be $h-(i-s+1)$ through $h$, and $0$ through $i+m-1$: there are still $(m+s-1)$ such values. Therefore, because $f_{c}(\cdot)\in\{0,1\}$,

The rest of the proof proceeds exactly as in the block smoothing case, with $(m+s-1)$ substituted for $(m+s-1)^{2}$. ∎

Appendix B Full Validation Result Tables for Column and Block Smoothing

Tables 3 and 5 present the full validation set clean and certified accuracies for $5\times 5$ patches on MNIST and CIFAR-10, respectively, for all tested values of parameters $s$ and $\theta$, and for both block and column smoothing. Note that this is presented in Figure 5 in the main text. Table 4 presents the validation set clean and certified accuracies for $42\times 42$ patches on ImageNet using column smoothing, for all four tested values of the hyperparameter $\theta$.

Appendix C Results for Row Smoothing

We also tested smoothing with rows, rather than columns, on MNIST. This resulted in slightly lower certified accuracy under $5\times 5$ patch attacks (45.32% validation set certified accuracy, versus 53.22% using column smoothing). Full results are presented in Table 6.

Appendix D Multi-column and Multi-block Derandomized Smoothing

In the main text, we argued for having the base classifier use a single contiguous group of pixels on the grounds that, compared to selecting individual pixels, it provides for a smaller risk of intersecting the adversarial patch. However, there may be some benefit to getting information from multiple distinct areas of an image, even if there is some associated increase in $\Delta$. Rather than just looking at the extremes of entirely independent pixels (Table 10) versus a single band or block (Figure 5 in the main text) we also explored, on MNIST, the intermediate case of using a small number of bands or blocks. In Table 7, we show all mathematically possible multiple-column certificates on MNIST, as well as several certificates for multiple-blocks with $s=4$. Interestingly, while the certificates using multiple columns are far below optimal, the certified accuracy for two blocks is only marginally below the best single-block certified accuracy.

For smoothing with multiple blocks or multiple columns, we consider only blocks or columns aligned to a grid starting at the upper-left corner of the image. For example, if using block size $s=4$, we consider only retaining blocks with upper-left corner $(i,j)$, where $i$ and $j$ are both multiples of $4$. This prevents retained blocks from overlapping, and also reduces the (large) number of possible selections of multiple blocks, allowing for derandomized smoothing.

Let the number of retained blocks or bands be $\kappa$, and, as in the paper, let the block or band size be $s$, the image size be $h\times w$, and the adversarial patch size be $m\times m$. For the block case, note that there are $\lceil h/s\rceil\times\lceil w/s\rceil$ such axis-aligned blocks. Of these, the adversarial patch will overlap at most $(\lceil(m-1)/s\rceil+1)^{2}$ blocks. For example, for a $5\times 5$ adversarial patch, using block size $s=4$, the adversarial patch will overlap exactly $4$ blocks, regardless of position: see Figure 8.

When performing derandomized smoothing, we classify all $\binom{\lceil h/s\rceil\times\lceil w/s\rceil}{\kappa}$ possible choices of $\kappa$ blocks. Of these classifications, at least

will use none of the at most $(\lceil(m-1)/s\rceil+1)^{2}$ blocks which may be affected by the adversary. Therefore, the number of classifications which might be affected by the adversary is at most:

We can then use the above quantity in place of the number of classifications $(m+s-1)^{2}$ that might be affected by the adversarial patch in standard block smoothing (Equation 4). This modification, in addition to classifying all $\binom{\lceil h/s\rceil\times\lceil w/s\rceil}{\kappa}$ selections of $\kappa$ axis-aligned blocks, is sufficient to adapt the certification algorithm to a multi-block setting.

The column case is similar: there are $\lceil w/s\rceil$ axis-aligned bands (defined as bands which start at a column index which is a multiple of $s$). Of these, the adversarial patch will overlap at most $(\lceil(m-1)/s\rceil+1)$ bands. When performing smoothing, we classify all $\binom{\lceil w/s\rceil}{\kappa}$ possible choices of $\kappa$ bands. Of these classifications, at least

will use none of the at most $(\lceil(m-1)/s\rceil+1)$ bands which may be affected by the adversary. Therefore, the number of classifications which might be affected by the adversary is at most:

Full validation set results for multi-block and multi-band smoothing are shown in Table 7.

Appendix E Comparison with Randomized Structured Ablation

As discussed in the main text, there are two benefits to derandomization: first, we can eliminate estimation error, and second, it allows the classifier to abstain or select multiple classes without complicating estimation. In order to distinguish these effects, we present in Tables 8 and 9 the certificates on MNIST and CIFAR-10 using randomized column smoothing (with the estimation scheme from ), versus deterministic column smoothing. We compare to both the “Top-1 class” method (without abstaining or thesholding) as well as to the thresholding method, with $\theta=0.3$. We find that derandomization alone, without the thresholding method, provides a considerable improvement (around 6 percentage points increase on MNIST, around 7 percentage points on CIFAR-10). On MNIST (although not on CIFAR-10), the thresholding scheme provides a large additional improvement.

Appendix F Sparse Randomized Ablation for Patch adversarial Attacks

In Table 10, we provide the certified accuracies computed from applying sparse Randomized Ablation to patch adversarial attacks, as discussed in Section 2.1 of the main text.

Appendix G Adversarial Attack Details

In order to test adversarial attacks against our structured ablation model (in particular the column smoothing model) we must work around the non-differentiability of the base classifier $f$ with respect to the image. We accomplish this using a method similar to the attack on smooth classifiers proposed by .

In particular, as described in Section 2.2.1 in the main text, the base classifier $f$ in our model is implemented using a neural network: let $F$ represent the (SoftMax-ed) logits of this neural network:

Rather than attacking $n(\mathbf{x})=\sum^{w}_{x=1}f(\mathbf{x},s,x)$, we instead attack a soft smooth classifier, $N(\mathbf{x})$:

The objective of the adversary (as in ) is now applied to this soft classifier:

where $y$ is the true label. The IFGSM patch attack proposed by proceeds by first randomly selecting a patch to attack, and then attacking it with standard IFGSM, without imposing any $L_{\infty}$ magnitude constraint on the attack (other than as required to produce a feasable image). This is repeated many times on many random patches. However, the most successful attack so far is recorded at each step of optimization, and finally returned at the end of the attack. (Note that this is the most successful attack over all steps of all random initializations.) In , this is taken as whichever perturbed version of the image maximizes the objective (Equation 16). Because we ultimately care about the “hard” smoothed classifier $n(\mathbf{x})$, we instead just evaluate the final “hard” classification $n(\mathbf{x})$ at each step. We record an attack to return only if it is actually successful at making the final classification incorrect. Note that this does not impose significant computational costs, because we already have the value of each ‘soft’ base classifier $F_{c}(\mathbf{x})$ at each step.

As mentioned in the main text, for the patch attack, we perform 80 random starts, 150 iterations per random start, and use a step size of 0.05. When attacking patches, we uniformly randomly initialize the pixels in the attacked region. For $L_{\infty}$ IFGSM, we used IFGSM for 50 iterations and a step size of $0.5/255$: for this, we did not randomize the pixel values before optimizing, but rather started at the initial $\mathbf{x}$. Training parameters for baseline models were identical to those for column-smoothed models, except that a regular, full ResNet-18 model was used.

Appendix H Evaluation Times

Data on evaluation times (using the optimal hyperparameters to maximize certified accureacy for each method) are shown in Table 11. We used NVIDIA 2080 Ti GPUs for our experiments.

Appendix I Architecture and Training Details

As discussed in the paper, we used the method introduced by to represent images with pixels ablated: this requires increasing the number of input channels from one to two for greyscale images (MNIST) and from three to six for color images. For MNIST, we used the simple CNN architecture from the released code of , consisting of two convolutional layers and three fully-connected layers. For CIFAR-10 and ImageNet, we used modified versions ResNet-18 and ResNet-50, respectively, with the number of input channels increased to six. Training details are presented in Table 12.

For randomized smoothing experiments, we follow the empirical estimation methods proposed by . We certify to $95\%$ confidence, using 1000 random samples to select the putative top class, and 10000 random samples to lower-bound the probability of this class. For sparse randomized ablation on MNIST, we use released pretrained models from .