It’s Simplex! Disaggregating Measures to Improve Certified Robustness ^††thanks: Identify applicable funding agency here. If none, delete this.

Despite their excellent benchmark performance, the black-box nature of deep neural networks makes them prone to unexpected behaviours and instability. Of particular interest are adversarial examples, in which model outputs are changed by way of human imperceptible input perturbations [2, 26, 10, 6]. The spectre of such attacks poses risks to deployed models, in a fashion that can materially impact both the model deployer and their users.

While numerous defences against the mechanisms that produce these examples exist, they typically only tackle a single vulnerability and be circumvented by considering alternate attack mechanisms. This intrinsic limitation motivated the development of certifiably robust models, which provide a pointwise guarantee of resistance to attacks up to a fixed, calculable size. These certifications are typically constructed by exploiting either convex relaxation or randomised smoothing [15], and measure how close the nearest-possible adversarial example could be, independent of the technique employed to identify said attack.

Whenever a new certification mechanism is proposed, its utility is demonstrated by considering its average performance over a large number of samples. However, these aggregate measures do not align with the motivations of potential attackers, who may seek to attack individual samples. As such, aggregate measures of certification may disguise how the risk profile of individual samples may change, and more broadly removes the ability to interrogate the factors that drive differential performance of different certification schemes.

In contrast to these aggregated measures of performance, this work takes the contrary, disaggregated perspective, and considers how the performance of different certification schemes depends upon where an individual sample exists within the simplex of permissible output scores. This is made possible by way of some simple-yet-powerful observations relating to the analytic nature of certification mechanisms, which allow for analytic, dataset independent comparisons to be performed. These techniques are then merged with a dataset-dependent, sample-wise analysis, which considers a dataset’s distribution in the context of the output simplex.

In taking this approach, we are able to both better understand the relative performance of certification schemes, and the nature of adversarial risk in certified systems more broadly. This is of critical importance for deployed systems, in which samples will likely be considered to hold differing levels of adversarial risk. Moreover, it may well be that the distribution properties of standard tested datasets may not reflect those observed within vulnerable deployed systems. If this was true, then being able to assess certification performance in a fashion that is aware but not beholden to the output distribution has significant ramifications for understanding the generalisation of certification techniques.

This disaggregated perspective reveals the potential for two additions to the certification oeuvre, which we document within this work. The first of which involves a revised mechanism for constructing certifications by way of differential privacy, which for a subset of samples can produce a more than two-fold increase in the achievable certification for what we will categorise as multinomial style certifications, and a more than five-fold increase for softmax certifications. Our second contribution involves treating certifications not as the product of any one mechanism, but rather as the best calculated value across a set of different approaches, an approach that is only made possible by considering certification performance through a disaggregated lens.

These improvements in both how we consider certifications, and how we construct certifications are supported by Sections 2 and 3, which introduce the current range of extant certification approaches, and how their analytic nature can be used to construct dataset-independent comparisons. From this, Section 4 then considers how these measures can be used to help reveal the potential for our two new certification approaches, both of which have the potential to help improve the sample-wise performance of certifications through consideration of the simplex of permissible output scores. Section 6 then demonstrates how our new approaches uniformly outperforms prior techniques when considering expectations over models that output softmax probability distributions, while providing significant advantages in a subset of the certification domain for multinomial classifiers.

Certification mechanisms use a mixture of computational and analytical techniques to provide guarantees of a models resistance to all adversarial attack. While this approach can be applied to training-time processes [17], within this work we are specifically interested in guarding against $\ell_{2}$-norm perturbations to images at evaluation-time. A learned classifier $f_{\boldsymbol{\theta}}\in\mathbb{R}^{K}$ acting upon an input sample $\mathbf{x}\in\mathbb{R}^{d}$ is considered to be robust to attacks $\boldsymbol{\gamma}\in\mathbb{R}^{d}$ of bounded size $\|\boldsymbol{\gamma}\|_{p}\leq L$—henceforth referred to as $B_{P}(L)$—if

The simplicity of this statement stands in stark contrast to the difficulty of proving it, as exploring the entire feasible space of $\boldsymbol{\gamma}$ is computationally intractable, especially as $d$ increases. As such, in order to establish the robustness of a model, certifications mechanisms instead construct provable lower bounds on the distance to the nearest adversarial example, making such certifications inherently conservative.

In attempting to certify against $\ell_{2}$-norm bounded perturbations, two primary frameworks have been considered, which can be broadly categorised as statistical certifications, and those that exploit knowledge of the model’s architecture. Of these, the latter involves constructing bounds on the output of a model by inspecting and tracing bifurcations under norm-bounded perturbations [19, 27, 33, 33, 24]. Framed in general as convex relaxation, these techniques opt to use linear relaxation to construct bounding polytopes of a model’s outputs over bounded perturbations [23]. These approaches have been extended by adopting augmented loss functions to promote tight output bounds [28]. However, these approaches require significant amounts of computational resources to construct their certifications, which typically leads to these approaches failing to scale beyond datasets of the size of CIFAR-$10$.

In contrast statistical methods typically leverage a process known as randomised smoothing, in which repeated model draws under noise are employed to produce what is known as a smoothed classifier, the properties of which can be exploited to construct guarantees of model robustness. This is made possible by attempting to parameterise worst-case behaviours under attack. While the addition of this noise is not cost-free, it is an embarrassingly parallel process that requires significantly fewer resources to scale to large models and complex datasets than are required with convex relaxation. Moreover, randomised smoothing does not require any modifications to the core model architecture, nor to the training and testing loops, which significantly reduces the level of engineering required to support the deployment of certified guarantees. It is due to these factors that for the remainder of this work we will only consider such statistical certification techniques.

Each of the aforementioned certification mechanisms has demonstrated its utility by showing improvements over the previously established state of the art. In each of these works, the core metric has been the certified accuracy, which corresponds to the proportion of samples that are correctly predicted with a radius greater than $r$, equivalent to

where $l(\mathbf{x})$ is the correct class label for the sample $\mathbf{x}$, and $L(\cdot)$ is the certification stemming from the smoothed classifier $g$.

While such a measure allows for comparisons between techniques to be easily parsed, it also presents a picture that suggests that improvements in certification performance between approaches are uniform across all samples. In doing so, the drivers of certification performance in different techniques are distorted, and more difficult to interrogate. This is intrinsically problematic, as it both limits our ability to understand how a technique may generalise to new, semantically different datasets; and the capacity to assess certification performance for datasets where samples have differing adversarial risks.

In order to resolve these limitations in how we assess certifications schemes, we introduce a simple but powerful observation: certification mechanisms often decompose such that the only determinant of certification performance are the model output expectations. This would appear to be immediately contradicted by Equations 5,  8, and  9, however each of these exhibits linear, multiplicative proportionality to $\sigma$, and as such, the only determinant of performance is the expectation set. While this is an obvious statement, it is also not a consideration that any prior work has considered, and allows for a dataset, learner, and model agnostic mechanism for comparing certification approaches, while also providing a framework for disaggregated analysis of the performance of any specific combination of dataset, learner, and model.

We introduce Definition 3.1 to formalise this statement, and to emphasise that certification mechanisms strictly depend upon the projection of the output $C_{K}$ space onto the $C_{3}$-simplex. Thus any comparison between technique performance can also be considered in terms of this permissible space, yielding what we term as a dataset independent comparison. In doing so, the performance of the certifications can be compared in a fashion that is agnostic to the choice of model, dataset, or training infrastructure employed.

To explore this concept, Figure 2 considers the relative certification performance between the Cohen et al. and Li et al. approaches, by considering the permissible space of expectations across the $C_{3}$ simplex as inputs, rather than the output of any specific model. While prior works have considered the Cohen et al. approach to uniformly produce the largest achievable radii of certification, in practice the commonly employed form of Cohen only out-certifies in the neighbourhood of $E_{0}+E_{1}\approx 1$. Outside of this region—which is likely to be seen in datasets which exhibit significant semantic overlap between classes—Li et al. begins to produce significantly larger certifications.

Extending the dataset-independent analysis of Figure 2 to incorporate Lecuyer et al. reveals that for multinomial outputs it is uniformly outperformed across the entirety of permissible outputs. However, the very notion that differential performance is possible upon a sample-wise basis suggests that improving upon the bounds delivered by Lecuyer et al. may achieve improvements over a subset of the output space. This is especially true as recent works have shown the differential privacy mechanism that underpins Lecuyer et al. underestimates the level of privacy that can be achieved for a given level of added noise [1, 34]. Within the remainder of this section, we will demonstrate how this improved mechanism can be incorporated into a new certification regime, that both uniformly outperforms Lecuyer et al. across the $C_{3}$ simplex; and yields improvements over Li et al. and Cohen et al. for the majority of the permissible output space.

In aide of this goal, we begin by introducing some core concepts of differential privacy: differential privacy as a stability condition on output distributions and how it translates to the stability of expected outputs (Lemma 4.1); the post-processing inequality (Lemma 4.2) and how it captures the invariance of differential privacy to data-independent compositions; and the improved analysis of the Gaussian mechanism. Of these, Lemma 4.1 and Lemma 4.2 follow Lecuyer [15]; and the improved analysis of the Gaussian mechanism follows [1].

The familiar post-processing inequality of differential privacy [9] is critical for certification in that it permits privacy-preserving randomisation to be applied at early network layers.

The $\epsilon$-DP of a random mechanism $A(\mathbf{x})$ is captured by the privacy loss random variable

where $\mathbf{x}^{\prime}=\mathbf{x}+\boldsymbol{\gamma}$. By then introducing $L_{A,\mathbf{x},\mathbf{x}^{\prime}}=l_{A,\mathbf{x},\mathbf{x}^{\prime}}(Y)$ [1], an equivalent condition for differential privacy is

To elaborate upon these probabilities, consider a mechanism of the form $y\sim h(\mathbf{x})+\mathcal{N}(0,\sigma^{2}\mathbf{I})$, where $h(x)$ is any arbitrary function. Taking such a framing allows the privacy loss random variable to be analytically expressed as

A consequence of the fact that the inner product is equivalent to $\mathcal{N}\left(0,\sigma^{2}\left\lVert h(\mathbf{x})-h(\mathbf{x}^{\prime})\right\rVert_{2}^{2}\right)$ is that

Based upon this framing, the components of Equation (12) can be constructed as

Extending this concept to certified robustness requires the application of the post-processing inequality of 4.2. If we consider a function $h(\cdot)$ such that $h(\mathbf{x})=\mathbf{x}$, then Equations 12 and 4 can be combined to take the form

where $L=\|\mathbf{x}-\mathbf{x}^{\prime}\|$ is the certified radius. If this is true for any function $y\sim h(\mathbf{x})+\mathcal{N}(0,\sigma^{2}\mathbf{I})$, then by virtue of the post-processing inequality the equivalent privacy relationship also holds for any mechanism $f(\cdot)$, which allows us to define our randomised mechanism as

This definition of $A(\mathbf{x})$ then becomes equivalent to the $g(\mathbf{x})$ of Section 2.1, if the expectations were to be taken over a single draw of noise.

In a similar fashion to Equation 5, this differential privacy based certification scheme can be framed as a maximisation problem, especially as Equation 16 does not admit an analytic inverse. However, rather than strictly considering $\epsilon\in(0,1]$ as the optimisation criteria, the above criteria can be recast as a constrained optimisation problem over $\epsilon\geq 0$ and $\delta\in[0,1]$ in order to construct a certification by way of

where $i$ corresponds to the predicted class, and $E[A_{i}(\mathbf{x})]$ and $E[A_{j}(\mathbf{x})]$ are respectively upper and lower bounded as per Section 2.1. While the form of the above equation is complex and nonlinear, the constraint functions exhibit near-monotonic behaviour in $(\epsilon,\delta,L)$, and as such can be quickly solved with any conventional constrained numerical optimisation tools. That this approach is only conditional upon $A(\mathbf{x})\in[0,1]$, it can be applied to both softmax and multinomial distributions, or indeed any $A(\mathbf{x})\in[0,c]$, as the latter case is simply a uniform scaling of $[0,1]$. The provably true nature of these guarantees is a direct consequence of Lecuyer et al. [15], as our approach tightens their bounds.

Beyond its ability to incorporate the improved privacy mechanism, framing the certification process as an optimisation process presents an additional advantage over the differentially privacy certifications of Lecuyer et al.: we remove the need to arbitrarily set the $(\epsilon,\delta)$-privacy level prior to certification. This is meaningful as most of the contexts for which certification is useful do not care for a specific, fixed privacy level across all samples, rather they value producing the largest achievable certification, in order to more accurately gauge adversarial risks.

In the context of the dataset-agnostic comparisons across the $C_{3}$ simplex, Figure 3 reveals that for a softmax output distribution, our approach uniformly outperforms Lecuyer et al. across the entire simplex, exhibiting a maximal relative $5$-fold improvement in the calculated certification.

For a multinomial output distribution, our new technique yields improved certifications against both Cohen et al. and Li et al. over the majority of the output space. When incorporating our technique into the comparison, across the $C_{3}$ simplex Cohen et al. produces strong certifications only in the neighbourhood of $E_{1}=1-E_{0}$; while Li et al. [16] produces the strongest certification near $(E_{0},E_{1})\to(1,0)$. However, as $E_{0}$ and $E_{1}$ both decrease—as seen in semantically complex samples—our comparisons demonstrate that it is possible to inrease the certification more than two-fold.

To demonstrate how the aforementioned processes can be implemented, Algorithms 1 and 2 cover certifications across all of the techniques for all of the multinomial and softmax approaches. For a given test sample $x$, the functions Multinomial-Certify and Softmax-Certify return the predicted class and certifications, with both tasks performed through randomised smoothing. Within this algorithm, the function Confint refers to the Beta function approach with Bonferroni correction, as is described within Section 2.1.

Every effort was made to accurately recreate the implementations of Li et al. and Lecuyer et al., in order to perform a fair comparison. However, as was alluded to in Section 2, the approach of Cohen et al. has the potential to incorrectly classify samples, and in doing so fail to certify. This stems from Algorithm 3’s sampling approach, in which classification is based on a small number of samples—as few as $n_{0}=100$ in Cohen et al., before a second sampling draw over $n$ samples estimates the expectation based solely upon the count of times the classifier’s class is selected.

While selecting a large enough $n$ produces tight bounds on the uncertainties for the expectation, the uncertainties for the $100$ samples are often large enough to not be able to accurately classify the output solution. Moreover, the very nature of the binomial sampling of Cohen—in which the expectation of the classifier’s output is compared to the likelihood of the intersection of all other classes—means that if the incorrect class is chosen, the mistake cannot be rectified without completely re-sampling. As such, we instead selected the expectation for Cohen based not upon the binomial sampling process, but the same multinomial sampling process employed by both us and Li et al..

To validate the applicability of our improved Gaussian mechanism and ensembling approach, experiments were performed for $\ell_{2}$-norm-bounded certifications utilising both CIFAR-$10$ [14], and the latest face-blurred variant of ImageNet [29], which respectively exist under a MIT and a BSD $3-$Clause license. While this blurring has been shown to introduce a slight degradation of predictive performance, the privacy-preserving protections that are introduced are important for the integrity of vision research. Our results highlight ImageNet, due to presence of human indistinguishable adversarial examples within trained models [26].

To support this, training was performed upon NVIDIA P$100$ GPUs using in PyTorch [20] and a cross-entropy loss, with a fixed random seed employed to ensure reproducibility. Certification employed $n=100,000$ samples for estimating expectations. Confidence intervals were set at $\alpha=0.001$ for a $0.1\%$ chance of any produced certification over-estimating the radius of certification. These parameters mirror those of Cohen et al. [5]. In the case of CIFAR-$10$, two GPUs and a $110$-layer residual network were trained for $90$ epochs under added noise $\sigma\in\{0.12,0.25,0.5,1.0\}$, with certification then being applied using the appropriate matched $\sigma$. This training process used stochastic gradient descent subject to an initial learning rate of $0.1$, momentum of $0.9$ and weight decay of $10^{-4}$, and batch size set at $400$. The learning rate was refined in a step-wise fashion where $L_{r}=0.1\times 0.1^{\lfloor\frac{e}{30}\rfloor}$, where $e$ is the current epoch.

For ImageNet, training was performed using a mixed precision [18] ResNet-$50$ model using a ten-node system, where each node also had access to two GPUs. In order to understand the influence of noise on the more-complex model, training and certification were performed at levels $\sigma\in\{0.25,0.5,1,2,3,4,5\}$. Due to the increased complexity of ResNet-$50$, training was modified to match best practices under available system resources. Both GPU cores on every node were trained with a batch size of $200$, and in the fashion of [12] the learning rate is set at $L_{r}=0.1563$, to be equivalent to a learning rate of $0.1$ for a single node training with a batch size of $256$. To improve convergence, the first three epochs were performed under $L_{r}=0.01563$, before reverting to the original rate. This was then scaled by $0.1$ at the $30$, $60$ and $80$-th epochs.

By considering certification performance through a disaggregated lens, this work demonstrates that it is possible to better understand the drivers of certification performance, from both a dataset and mechanistic perspective. This form of analysis demonstrated the utility of our multiple improvements to to the current oeuvre of certification techniques, including an improved differential privacy based Gaussian mechanism that for some samples can produce a more than two-fold increase in the achievable multinomial certification, or up to five-fold in the case of softmax certifications. These improvements are particularly evident in the case where the largest class expectation is diminished.

Beyond this, our work also demonstrates that a simple ensemble-of-certifications can reuse the costly components of certifications, in order to improve upon performance relative to any one single technique. This technique, which introduces almost no additional computational burden, is able to certify $98\%$ of samples above $r=0.05$ at $\sigma=1$ for ImageNet, relative to the $89\%$ achieved by the prior state-of-the-art in Cohen et al. [5]. Our technique’s advantage over other certification mechanisms grows with both the semantic complexity of the dataset and $\sigma$.

Through this works mechanisms, we have demonstrated how minor changes to certification systems can be used to construct larger certifications, which in turn would allow for a greater degree of confidence in the adversarial resistance of systems deployed in contexts where they may be implemented. Moreover, our approach of assessing certification performance within the context of the simplex of output scores has the potential to allow for a more nuanced view of adversarial risk. Operationalising this perspective, in the context of our improvements to the achievable radii of certification, has the potential to reduce reduce the need for domain experts to manually verify inputs that have the potential to be adversarially influenced, or to guide a greater understanding of adversarial risk in deployed systems.

This research was undertaken using the LIEF HPC-GPGPU Facility hosted at the University of Melbourne. This Facility was established with the assistance of LIEF Grant LE170100200. This work was also supported in part by the Australian Department of Defence Next Generation Technologies Fund, as part of the CSIRO/Data61 CRP AMLC project. Sarah Erfani is in part supported by Australian Research Council (ARC) Discovery Early Career Researcher Award (DECRA) DE220100680.

The full suite of code required to replicate the experiments contained within this work can be found at https://github.com/andrew-cullen/ensemble-simplex-certifications

The techniques and processes described within this paper have the potential to decrease the vulnerability of deployed machine learning systems to adversarial example. However, in doing so there is also the potential to also counter beneficial applications of attacks, such as stylometric privacy. However, we believe that the value in minimising risks to deployed systems significantly outweighs these concerns.