PROSAC: Provably Safe Certification for Machine Learning Models under Adversarial Attacks

We thank the reviewer for the insightful comments. Here are our responses.

Q1: I do not believe it has suitable rigorous experimentation (especially in terms of dataset diversity), or experimentation (does not follow standard expectations regarding the trade off between certification proportion and size that are common in other certification papers). While there is validity in a paper that demonstrates that a new approach has the potential to extend the ability of certifications to new frontiers - however, part of doing this kind of validation would require a comprehensive set of experiments demonstrating scaling and performance, all of which are missing.

R1: We use ImageNet as the dataset as it is one of the default dataset to certify adversarial robustness. There is no explicit trade-off between certification radius and sample sizes in our method, because our method does not need more samples/trials as the radius is increased. If the radius is increased, we run the attack algorithm with that radius and get the empirical risk to compute the p-value. About the scaling and performance, we will consider experiments with a larger sample size in our next version, to illustrate its impact on the certification procedure.

Q2: Also one of the stated contributions of this work is to extend Randomised Smoothing from $l_2$ to $l_p$. However, this is missing a wide range of literature on $l_p$ certifications in randomised smoothing, see Yang et. al "Randomised Smoothing of All Shapes and Sizes", 2020 as an example of this.

R2: Thanks for mentioning this. It is worth noting that Yang et. al also has the drawback of only giving a certification for certain test samples, while the major contribution of our method is to certify a model’s adversarial risk at the population level. We will add the discussion with Yang et. al in the next version.

Q3: I also worry that this paper is attempting to cover quite a few bases - it's trying to both introduce a Bayesian optimisation mechanism and to demonstrate that VIT's are more robust than other architectures.

R3: Our observation about off-the-shelf ViT’s is based on the result of certifying the ViT’s with our method, so we are not claiming in any way this is a substantial contribution. Our main contribution first and foremost involves the proposal of a certification methodology, including the use of off-the-shelf Bayesian optimization methods and associated theoretical guarantees allowing one to certify a machine learning model in practice. We will revise the paper to address this concern.

Q4: Figures 1 & 2 don't even seem to be referenced in text?

R4: They are referenced as Fig. 1 and 2 of page 8.

Q5: What’s the difference between the proposed safety framework relative to something like Differential Privacy (as considered by Lecuyer)?

R5: Lecuyer uses differential privacy techniques to certify defenses against adversarial attacks. Their approach leverages differential privacy bounds to implement certified robustness checks for individual predictions. Our approach in turn offers the means to certify the population-level performance of any machine learning model in the presence of an adversarial attack.

We thank the reviewer for the insightful comments. Here are our responses.

Q1: The work's presentation overall is difficult for me to understand.

R1: We will address this weakness in the next version. Please check other responses below too.

Q2: In certifying the space of attack hyperparameters a model is robust to, it is unclear what hyperparameters are being varied in each attack and what hyperparameter values the work is certifying are safe.

R2: Fig. 1 and 2 use the default hyperparameters of AutoAttack and SquareAttack. Thus, we only change the attack budget in these two attacks and if the resulting p-value is smaller than 0.05, we reject the null hypothesis, hence we declare the model is safe. Table 1 of page 4 summarizes the hyperparameters we changed in our experiment.

Q3: The experimental results in section 5 seem to suggest the certification is unreliable.

R3: The randomness comes from the attack. We are running additional experiments where the attack is run multiple times so that we can report more stable p-values

Q4: Theorem 4 seems to say that multiple rounds of approximation are needed to certify a machine learning model, but it does not quantify or attempt to make a statement about that number of rounds of approximation.

R4: The supplementary material shows how the number of rounds T needs to scale to retain the ($\alpha$,$\zeta$) model safety guarantee. We agree with the reviewer it is important to state these in the main paper, so we will revise the new version accordingly.

Q5: What is the relation between this work and PAC (Probably Approximately Correct) learning / adversarial PAC learning? It seems the guarantees are very similar to those proposed in this work.

R5: (Adversarial) PAC learning estimates the generalization error of a learning algorithm in the presence of an adversary, while our work certifies the adversarial population risk of a pre-trained classifier. Therefore, both approach consider slightly different problems / challenges.

Q6: Why is this not the case and why is there so much variability in p-values?

R6: The randomness comes from the attacker, e.g., random sampling squares in SquareAttack. It is possible to reduce the variability by running the attack over additional trials. We will run more trials and report the mean and variance in the next version.

Q7: Section 2 states "... RS (randomized smoothing) is limited to certifying empirical risk of a machine learning model on pre-defined test datasets under &l_2&-norm bounded adversarial perturbations." What is meant by a pre-defined test dataset and how is randomized smoothing restricted to it? How is PROSAC not restricted to it?

R7: A pre-defined test set means the RS algorithm only certifies samples in the given test set. Our method in turn offers population risk guarantees.

Q8: Section 2 states "randomized smoothing (RS) represents a versatile certification methodology free from model architectural constraints or model parameters access" but then later states "Our certification framework shares RS’s versatility but a) it also exhibits the ability to accommodate a diverse range of lp norm-based adversarial perturbations; b) it is not restricted to particular model architectures...". These statements seem to first state that RS is free from model architectural constraints but then states it is restricted to particular model architectures. Do I misunderstand what is being said?

R8: This is a typo, we will revise this.

Q9: In Table 1, why is the hyperparameter field "N.A." for AutoAttack? There are several hyperparameters that can be set (e.g., number of gradient steps, number of expecation over transformation estimates, the type of attack to execute, etc.).

R9: We use the standard version of AutoAttack as most adversarial defense/attack papers do.

Q10: Equation 10 is difficult for me to understand. What is $h_1$? Could a narrative be given for what this equation is saying?

R10: $h_1$ is defined within the statement of the Theorem. This equation defines how to calculate a super uniform p-value associated with our hypothesis testing problem, allowing us to accept or reject the null, depending on how the p-value compares to $\zeta$.

Q11: In section 4.1, a footnote says that the attack budget and norm are not considered hyper-parameters because it would not be possible to control the risk if the adversary can choose any attack budget. This justification does not explain why the norm is not considered a hyper-parameter. Is there a reason the norm is not considered a hyperparameter?

R11: In the research community of adversarial machine learning, the norm is often an adversarial attack setting as different norms measure different distances and are not directly comparable. We do not consider the attack budget to be a hyper-parameter because it is expected the attacker will limit the attack budget due to a variety of practical constraints (including limiting the ability of the attack to be detected)

Q12: In equation 7, shouldn't the risk no longer have a $\lambda$ subscript?

R12: Yes, we will fix it in the next version.

Q13: In the paragraph below equation 5, I don't understand what is meant by "We will be assuming in the sequel, where appropriate,..." and later "We will be representing in the sequel..." What is the meaning of the word sequel here?...

R13: “In the sequel” means “from now on” in English.

Q14: Is $\mu$ and $\sigma$ the mean and variance of $\lambda$?

R14: They are mean and variance of GP prediction.

We thank the reviewer for the insightful comments. Here are our responses.

Q1: There are lots of existing works on machine learning's robustness certification. Those works have been mentioned in Section 2, but that is probably too late.

R1: We will re-write the title, abstract and introduction to highlight the difference between our work and existing certification methods.

Q2: Compared to the existing machine learning certification algorithms that are independent from attack algorithms, the one proposed in this paper requires a specific attack algorithm.

R2: We believe that certifying the population-level dependence on attacks is practical, as users are inclined to seek safety guarantees tailored to their risk exposure for both black-box and white-box attack settings individually. To approximate attack-independent certification, we certify the model – using identical tools – against a wide range of attacks.

Q3: It is unclear what the computational cost is, and how the number of data samples may affect the results.

R3: The computational cost derives mainly from the p-value computation in equation 10 , since it involves the computation of the model empirical risk in the presence of the adversarial attack (which also involves optimization of the adversarial perturbation). Note that this computation also involves a maximization over the set of adversarial hyper-parameters over a chosen grid.. With more calibration samples, the variance of the empirical risk appearing in equation would be reduced and the p-value too.

We thank the reviewer for the insightful comments. Here are our responses.

Q1: Theorem 4 only states that "we can do sth by relying on Alg 1". But how is the Algorithm 1's result used to derive the final guarantee in Eqn. (12)? As a certification approach

R1: Theorem 4 uses a regret bound for the GP-UCB algorithm to give a guarantee for the GP-UCB algorithm’s p-value approximation. The reviewer is correct that Theorem 4 uses some assumptions that have been made clear in Appendix D. In particular, we assume that p-value lies in an RKHS with some known kernel k and the observation noise is R-sub-Gaussian. We will make this explicit in the new version in the main Theorem.

Q2: The experimental evaluation is not quite clear and may lack some baselines. What are $\alpha$ and $\zeta$?

R2: $\alpha$ represents an (upper bound) to the max adversarial risk, whereas the parameter zeta represents the confidence level (the type-I error probability associated with the underlying hypothesis testing problem). Thus, we reject the null (ie we declare the model is safe) provided that p-value<&\zeta&. Our figures (Fig. 1 and 2) allow us to establish immediately whether reject the null, hence whether the model is safe.

Q3: The existing literature can guarantee the risk for any attack within the perturbation budget.

R3: Yes, our certification is attack-dependent but gives a population-level certification. We will make it clear in the next version. However, we believe that certifying the population-level dependence on attacks is practical, as users are inclined to seek safety guarantees tailored to their risk exposure for both black-box and white-box attack settings individually. To approximate attack-independent certification, we certify the model – using identical tools – against a wide range of attacks.

Q4: Minor typos.

R4: Thanks for the comment, we will fix it in our next version.