acceptodds
Under review as a conference paper at ICLR 2027

Skeleton Keys: Estimating Randomized Model Selection Distributions With Limited Queries

Abstract

Advances in adversarial machine learning have demonstrated that randomly selecting between defenses at inference time can further boost robustness to evasion attacks, in the white-box setting. However, it is an open question as to how an attacker could learn the model selection probability distribution in this setting. In this paper, we propose a new methodology, skeleton keys, for estimating model selection probability distributions. Skeleton keys are special inputs that leak probability distribution information to the attacker. Our contributions are as follows: First, we develop the first ever skeleton key generation algorithm and define the security properties necessary for an input to serve as a skeleton key. Second, based on skeleton key queries, we derive a likelihood estimator applicable to any defense distribution. We calculate the confidence bounds on this estimator in terms of the number of queries. Third and lastly, we empirically show the validity of our approach using state-of-the-art randomized defense ensembles. Our experiments are conducted using TRADES adversarially trained models, FAT adversarially trained models, MAMBA models and Spiking Neural Networks on CIFAR-10. Code for all our experiments is available anonymously https://anonymous.4open.science/r/proj-skeleton-key-06CE.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
security, statistics, estimation

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 4 reviews, above 27% of the others.
Reviewer_P4sWOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This work examines the problem of developing a method to improve white-box attack success rate against defenders who use an array of defenses which are randomly selected when presented with an example. The central idea is to use white box model access to develop "skeleton key" inputs, which are inputs where the target model will produce a specific class label and all other models will produce a class that differs from the specific class output by the target model. Skeleton keys can be generated by a PGD-like algorithm where an input is perturbed in a way that encourages correct classification for the target model and incorrect classification for non-target models. By generating many skeleton keys for each target model, one can directly estimate the probability distribution with which the defender selects a given defense model by querying the defense with skeleton keys and identifying which model is used each time.

Critical strengths
  • The overall method is sound: a PGD-like approach is used to stabilize the class of the target model and perturb the class of non-target models, which enables a simple and effective way for the attacker to leak information about the defense distribution.
  • The results in Table 4 show that taking the skeleton key distribution into account can increase the effectiveness of adversarial attacks against randomized defenses using an ensemble of models.
Critical weaknesses
  • The paper as written leaves me with some questions about exactly how the randomized defense is evaluated. I am assuming that 1000 APGD steps are use to create an adversary, and that the defense is shown this final adversary a single time to determine whether the input is classified correctly or incorrectly. This should be clarified directly in the main text. The exact evaluation strategy relates to the Single Query Use assumption: if the defense can be queried repeatedly, Skeleton Keys should not be necessary and it should be possible to continue to show the defender adversaries crafted with each individual model, which will cause robustness to collapse to at most the level of the weakest defense in the ensemble. The importance of the SQU assumption is not clearly outlined in the text but it matters for understanding the evaluation. The natural accuracy and robustness for this kind of random defense is stochastic and it seems better to include some kind of uncertainty measurements when presenting these metrics, or to present expected natural accuracy/robustness. Overall, there are some key areas relating to the randomness of this defense that are not laid out clearly in the text.
  • The experimental scope of the method is relatively limited. The method only studies the case where the randomness comes from model selection, and only studies CIFAR-10. It would strengthen the paper to also investigate the possibility of using Skeleton Keys for random transformations such as BaRT, and to extend the results to other datasets.
  • The results in Table 12 seem to cast doubt upon the claims that follow from Table 4. The benefit of the skeleton-key informed method is much less significant in Table 12 (except for Two defenses) than Table 4. This should be clarified: are skeleton keys more effective for certain defender configurations, and only provide a minor benefit for other configurations?
Questions for authors
  • Can you provide a more detailed explanation of the evaluation protocol, how it relates to the SQU assumption, and how uncertainty across model selection impacts the metrics reported in Table 4?
  • Can the method be extended beyond the scope of model ensembles to incorporate random transformations? Does it work on datasets beyond CIFAR-10?
  • Can you provide more context about the less significant results in Table 12 vs. Table 4?
  • The LLM statement required by ICLR 2027 looks like it is missing. Did you use LLMs when writing the paper, and if so how?
5 comments

We thank the reviewer for the careful and constructive feedback. We have addressed all the questions which improved the overall contributions of this work.

W1, Q1: “explanation of the evaluation protocol”, “how it relates to the SQU assumption”

= We thank the reviewer for this insightful comment. The reviewer is correct that the final adversarial example is shown a single time and our robustness is average over 1000 different APGD samples. The one caveat here is the defense can be queried multiple times, but our assumption is this occurs only with DIFFERENT samples. The same sample cannot be repeatedly used to query the defense. This also motivates our use of multiple skeleton keys (instead of a single skeleton key). The original assumption of SQU is to defeat memory based defense systems. E.g. if a defender keeps track of the inputs submitted by each user, it would be easy to identify malicious users as they would be repeating the same exact input every time in a sequence. This phenomena and corresponding defense was well documented in the literature:

[1] https://arxiv.org/abs/1907.05587 (Stateful Detection of Black-Box Adversarial Attacks)
[2] https://arxiv.org/abs/2006.14042 (Defense for Neural Networks against Query-Based Black-Box Attacks)

We will update the paper’s writing according to the reviewer’s feedback to make the relationship between the evaluation protocol and SQU assumption more clear.

Q2: “incorporate random transformations”

= BaRT is a different estimation problem which is expectation over transformation for a series of image processing techniques. Furthermore, BaRT is an older defense that has been shown as vulnerable to different techniques that use advanced estimation techniques. Papers that have already advanced attacks on BaRT to reduce robustness are listed here:

[1] https://arxiv.org/abs/2207.03574 (Demystifying the Adversarial Robustness of Random Transformation Defenses) [2]https://ieeexplore.ieee.org/document/11155075 (Momentum Iterative Method over Expectation)

Q2: “datasets beyond CIFAR-10” = We have evaluated our method on the Tiny-ImageNet dataset, which also shows promising results in terms of skeleton key yield rate and estimation problem. During the rebuttal period, for the Tiny-ImageNet experiments, we used three adversarially trained defense models (WRN-28-10, CaiT-XXS, and MambaVision-T). In the following table, we have outlined the clean accuracy and the robust accuracy of the three models: Table: Clean and robust accuracy of each of the three models on Tiny-ImageNet. Robust accuracy is evaluated under a maximum l∞l_\infty perturbation of ϵmax⁡=0.031\epsilon_{\max}=0.031.

ModelClean AccuracyRobust Accuracy
WRN65.19%31.30%
CAIT52.82%30.47%
MAMBA71.05%40.14%
The comparison between the ordinary-input and skeleton key algorithm generated keys is outlined in the following table:
Table: Skeleton key generation algorithm evaluation for each of the three models on Tiny-ImageNet. All skeleton keys use 100 iterations and a maximum l∞l_\infty perturbation of ϵmax⁡=0.031\epsilon_{\max}=0.031.
ModelValidNon-Valid
:--:--::--:
WRN-28-106059395
CaiT-XXS3979603
MambaVision-T14778523

On Tiny-ImageNet, our algorithm generates a large number of valid skeleton keys for every target model, from 397 for CaiT-XXS up to 1477 for MambaVision-T, with yield rates of 3.97% to 14.77%. In each case, the generated keys far exceed the clean samples that already satisfy the skeleton key condition (2.0x to 4.5x), confirming that our method scales effectively to a larger and more complex dataset. The following table reports the estimated defense distributions and the resulting robust accuracies on Tiny-ImageNet.

Table: Estimate of PD\mathbf{P}_{\mathrm{D}} and robust accuracy of randomized model ensemble under different attack settings on Tiny-ImageNet. JSD denotes Jensen–Shannon divergence computed using base-2 logarithms. R_U denotes robust accuracy when the attacker assumes a uniform probability distribution. R_S denotes the robust accuracy when the attacker uses the skeleton key estimated distribution P^D\hat{\mathbf{P}}_{\mathrm{D}}. Δ=RU−RS\Delta = R_U - R_S.

ModelsPD\mathbf{P}_{\mathrm{D}}P^D\hat{\mathbf{P}}_{\mathrm{D}}JSDRU\mathbf{R}_URS\mathbf{R}_SΔ\boldsymbol{\Delta}
WRN, CaiT, Mamba[0.10, 0.00, 0.90][0.0812, 0.0001, 0.9187]8.24×10−48.24 \times 10^{-4}48.20%35.90%12.30%
WRN, CaiT, Mamba[0.33, 0.33, 0.34][0.3342, 0.3143, 0.3515]2.16×10−42.16 \times 10^{-4}42.80%42.80%0.00%
WRN, CaiT, Mamba[0.00, 0.00, 1.00][0.0000, 0.0001, 0.9999]5.00×10−55.00 \times 10^{-5}48.40%33.10%15.30%
WRN, CaiT, Mamba[0.24, 0.24, 0.52][0.2477, 0.2303, 0.5220]1.17×10−41.17 \times 10^{-4}44.00%42.30%1.70%

Attack Analysis on Tiny-ImageNet: The above table shows that using the skeleton key estimated defense distribution also improves attack effectiveness over the uniform baseline on Tiny-ImageNet. For the two skewed defense configurations, robust accuracy drops from 48.20% to 35.90% and from 48.40% to 33.10%, reductions of 12.30 and 15.30 percentage points, respectively. When the defense distribution is close to uniform, the gain is small or vanishes (1.70 and 0.00 percentage points), because the uniform assumption already closely matches the true distribution. These results show that the estimated defense distribution gives the attacker the most useful information when the defender’s model selection is non-uniform, yielding up to a 15.30 percentage-point gain in attack success. These results demonstrate that our method generalizes beyond CIFAR-10 to a larger and more complex dataset. We will include the Tiny-ImageNet results in the revised manuscript.

[1] https://arxiv.org/abs/2207.03574 (Adversarial Robustness of Random Transformation Defenses) [2] https://arxiv.org/abs/2211.14669 (GaME paper)

W3, Q3: “context about the less significant results in Table 12 vs. Table 4”

= We have added the results for all the rows to make Table 4 and Table 12 consistent. Both the tables now have an equal number of rows. The numbers of Table 12 have now changed. Here are the updated numbers for our Table 12.

Table: Estimate of PD\mathbf{P}_{\mathrm{D}} and robust accuracy of randomized model ensemble under different attack settings on CIFAR-10. R_U denotes robust accuracy when the attacker assumes a uniform probability distribution. R_S denotes the robust accuracy when the attacker uses the skeleton key estimated distribution P^D\hat{\mathbf{P}}_{\mathrm{D}}. Δ=RU−RS\Delta = R_U - R_S. Model abbreviations are: W = WRN-28-10, C = CaiT-XXS, V = ViT-L/16, M = MambaVision-T, D = DM-R18, and F = FAT-R18.

ModelsPD\mathbf{P}_{\mathrm{D}}P^D\hat{\mathbf{P}}_{\mathrm{D}}RU\mathbf{R}_URS\mathbf{R}_SΔ\boldsymbol{\Delta}
W,C,V,M,D,F[1, 0, 0, 0, 0, 0][0.9995, 0.0001, 0.0001, 0.0001, 0.0001, 0.0001]80.30%70.40%9.90%
W,C,V,M,D,F[0.5, 0, 0.25, 0.25, 0, 0][0.5049, 0.0001, 0.2349, 0.2599, 0.0001, 0.0001]78.50%71.60%6.90%
W,C,V,M,D,F[0.26, 0.07, 0.26, 0.17, 0.17, 0.07][0.2699, 0.0777, 0.2521, 0.1344, 0.1934, 0.0725]70.20%69.60%0.60%
W,C,V,M,D,F[0.167, 0.167, 0.167, 0.167, 0.166, 0.166][0.1877, 0.1555, 0.1630, 0.1555, 0.1729, 0.1654]66.60%67.20%−0.60%
C,V,M,D,F[0, 0.4813, 0.5187, 0, 0][0.0001, 0.4824, 0.5173, 0.0001, 0.0001]75.90%65.90%10.00%
Here, for the CIFAR-10 results, in three of the five settings, skeleton keys reduce robust accuracy by 6.90–10.00 points. Only the two near-uniform settings show small gains, as expected.
For the Tiny-ImageNet results, in two of the four settings, skeleton keys reduce robust accuracy by 12.30–15.30 points. The moderately non-uniform setting gives a smaller gain of 1.70 points, and the uniform setting gives none, as expected.
We will clarify this in the revised manuscript.

Q4: “Did you use LLMs when writing the paper, and if so how?” = We used LLM only to polish the writing, such as correcting grammar and spelling. We will update this in the revised manuscript.

We will make sure to address all the responses in the updated version. We thank the reviewer for their diligence and humbly ask them to reconsider their score for the paper accordingly.

Reviewer_kNqcOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies an attacker who knows the candidate defense models but does not know their fixed randomized selection probabilities. It constructs skeleton-key inputs on which one target model predicts a label that none of the other models produces, turning an output label into a Bernoulli observation of model selection. A constrained maximum-likelihood estimator recovers the selection distribution, with a convex negative log-likelihood and an asymptotic variance analysis. CIFAR-10 experiments use six adversarially trained models across several architectures and report low distribution-estimation error at 400 observations per model. The paper also reports improved evasion attacks using the estimated probabilities, but the single-use query protocol and conflicting attack results require clarification.

Critical strengths
  1. The paper separates knowledge of candidate models from knowledge of their random selection probabilities and shows why this distinction can matter for an attacker.

  2. Classwise uniqueness creates an observable Bernoulli event, and the simplex-constrained likelihood enforces a valid probability distribution.

  3. The experiments include convolutional, transformer, state-space, and spiking models and disclose the low key-generation yields rather than reporting estimation accuracy alone.

Critical weaknesses

1.The single-use query budget is not demonstrated. Section 2 prohibits reusing a key, but Table 2 produces only 15–103 valid keys per model while Section 4.2 uses 400 observations per model. The manuscript does not specify how additional distinct keys are obtained, whether keys are reused, or whether the observations are sampled synthetically from the assumed distribution. Without this connection, the empirical estimator evaluation does not establish feasibility under the stated threat model, and the six-model online budget is 2,400 calls rather than 400.

2.The incremental value of skeleton keys is not established. A white-box observer can use known label partitions of ordinary inputs to infer model probabilities even when a query is not exclusive to one model. The paper does not compare such ordinary-input likelihood estimation at the same total query budget, and the evasion baseline uniformly samples attack-source models instead of testing a stronger ensemble-aware attack. Consequently, the experiments do not isolate the benefit of adversarial key generation or probability estimation itself

3.The confidence analysis does not provide the claimed general query guarantee. Equations 16–22 use asymptotic normality under regularity assumptions, whereas several evaluated distributions have exact zero or one probabilities on the simplex boundary. A normal-approximation width calculation is not a finite-sample coverage guarantee, and no repeated-trial coverage evaluation or boundary treatment is reported. The confidence/query statements therefore require a narrower interpretation or additional justification

Questions for authors

1.Were the 400 observations per model obtained from 400 distinct deployed-defense queries, reused valid keys, or synthetic Bernoulli draws? Please provide distinct-key counts, total generation attempts and online calls, and the implemented cross-query similarity criterion.

2 comments

We thank the reviewer for the careful and constructive feedback. We have addressed all the questions given by the reviewer. This has led to a significant improvement in the overall contributions of this work.

W1, Q1: “Please provide distinct-key counts, total generation attempts and online calls, and the implemented cross-query similarity criterion. ” W2: “ordinary-input likelihood estimation”

=We thank the reviewer for raising this point. In Table 3 we simulate the use of 400 keys through a repeated sampling process. We will make this clear in the updated writing of the paper.

We have conducted experiments on CIFAR-10 to compare ordinary-input and skeleton key algorithm generated keys and outlined in the following table:

Target ModelClean KeysGenerated Keys (Ours)Improvement
CaiT-XXS263.0×
DM-R186122.0×
FAT-R1812211.8×
MambaVision-T4102.5×
ViT-L/1613302.3×
WRN-28-108212.6×
Total451002.2×
The table shows that our method is effective in generating new keys, which is required for estimation analysis.

Additionally, we have evaluated our method on the Tiny-ImageNet dataset, which also shows promising results in terms of skeleton key yield rate and estimation problem. During the rebuttal period, for the Tiny-ImageNet experiments, we used three adversarially trained defense models (WRN-28-10, CaiT-XXS, and MambaVision-T). In the following table, we have outlined the clean accuracy and the robust accuracy of the three models:

Table: Clean and robust accuracy of each of the three models on Tiny-ImageNet. Robust accuracy is evaluated under a maximum l∞l_\infty perturbation of ϵmax⁡=0.031\epsilon_{\max}=0.031.

ModelClean AccuracyRobust Accuracy
WRN65.19%31.30%
CAIT52.82%30.47%
MAMBA71.05%40.14%
The comparison between the ordinary-input and skeleton key algorithm generated keys is outlined in the following table:
Table: Skeleton key generation algorithm evaluation for each of the three models on Tiny-ImageNet. All skeleton keys use 100 iterations and a maximum l∞l_\infty perturbation of ϵmax⁡=0.031\epsilon_{\max}=0.031.
ModelValidNon-Valid
:--:--::--:
WRN-28-106059395
CaiT-XXS3979603
MambaVision-T14778523

On Tiny-ImageNet, our algorithm generates a large number of valid skeleton keys for every target model, from 397 for CaiT-XXS up to 1477 for MambaVision-T, with yield rates of 3.97% to 14.77%. In each case, the generated keys far exceed the clean samples that already satisfy the skeleton key condition (2.0x to 4.5x), confirming that our method scales effectively to a larger and more complex dataset. The following table reports the estimated defense distributions and the resulting robust accuracies on Tiny-ImageNet.

Table: Estimate of PD\mathbf{P}_{\mathrm{D}} and robust accuracy of randomized model ensemble under different attack settings on Tiny-ImageNet. JSD denotes Jensen–Shannon divergence computed using base-2 logarithms. R_U denotes robust accuracy when the attacker assumes a uniform probability distribution. R_S denotes the robust accuracy when the attacker uses the skeleton key estimated distribution P^D\hat{\mathbf{P}}_{\mathrm{D}}. Δ=RU−RS\Delta = R_U - R_S.

ModelsPD\mathbf{P}_{\mathrm{D}}P^D\hat{\mathbf{P}}_{\mathrm{D}}JSDRU\mathbf{R}_URS\mathbf{R}_SΔ\boldsymbol{\Delta}
WRN, CaiT, Mamba[0.10, 0.00, 0.90][0.0812, 0.0001, 0.9187]8.24×10−48.24 \times 10^{-4}48.20%35.90%12.30%
WRN, CaiT, Mamba[0.33, 0.33, 0.34][0.3342, 0.3143, 0.3515]2.16×10−42.16 \times 10^{-4}42.80%42.80%0.00%
WRN, CaiT, Mamba[0.00, 0.00, 1.00][0.0000, 0.0001, 0.9999]5.00×10−55.00 \times 10^{-5}48.40%33.10%15.30%
WRN, CaiT, Mamba[0.24, 0.24, 0.52][0.2477, 0.2303, 0.5220]1.17×10−41.17 \times 10^{-4}44.00%42.30%1.70%

Attack Analysis on Tiny-ImageNet: The above table shows that using the skeleton key estimated defense distribution also improves attack effectiveness over the uniform baseline on Tiny-ImageNet. For the two skewed defense configurations, robust accuracy drops from 48.20% to 35.90% and from 48.40% to 33.10%, reductions of 12.30 and 15.30 percentage points, respectively. When the defense distribution is close to uniform, the gain is small or vanishes (1.70 and 0.00 percentage points), because the uniform assumption already closely matches the true distribution. These results show that the estimated defense distribution gives the attacker the most useful information when the defender’s model selection is non-uniform, yielding up to a 15.30 percentage-point gain in attack success. These results demonstrate that our method generalizes beyond CIFAR-10 to a larger and more complex dataset. We will include the Tiny-ImageNet results in the revised manuscript.

W3: “confidence analysis”, “asymptotic normality under regularity assumptions”

=We agree with the reviewer that the normal approximation used in Equations 16–22 is justified asymptotically for probability vectors in the interior of the simplex, but does not directly extend to probabilities exactly on the boundary (i.e., when probabilities are zero or one). We will clarify this distinction in the revised manuscript.

Our objective was to determine a sufficiently large, uniform number of skeleton-key queries to estimate the probability of each defense appearing in the ensemble with a desired precision. Our analysis uses the asymptotic variance to determine the maximum confidence-interval width over the space of possible probability distributions. This provides a conservative query-budget calculation without requiring prior knowledge of the individual defense probabilities.

For a desired margin of error of 0.05 at the 95% confidence level, this analysis suggests approximately using 264 queries obtained from the upper bound of the asymptotic variance from the limiting maximum variance calculation. We further increased this budget to 400 queries in our experiments to provide an additional margin of conservatism.

We would like to clarify that the intention of this analysis was to establish a reasonable and conservative query budget based on estimation precision, rather than to claim or establish a finite-sample coverage guarantee for the resulting confidence intervals. We did not intend to suggest that the asymptotic normal approximation provides guaranteed finite-sample coverage, nor did we consider empirical repeated-trial coverage evaluation a requirement of this analysis.

Nevertheless, we agree that probabilities exactly on the simplex boundary warrant separate consideration. In such cases, exact finite-sample binomial confidence intervals can be used instead of the normal approximation. For example, when zero successes are observed in 400 independent queries, the two-sided 95% Clopper–Pearson exact confidence interval is approximately [0,0.0092]. Thus, the margin of error under the boundary truth is substantially smaller than our target margin of error of 0.05. This provides an additional justification that our selected budget of 400 queries achieves the desired estimation precision even in the boundary case. We will include this exact finite-sample treatment to complement the asymptotic analysis and clarify the interpretation of the query budget being our objective.

Finally, our use of the maximum variance across possible probability distributions is deliberate. It allows us to use the same query budget across all defenses without relying on intermediate estimates of their individual probabilities.

We will make sure to address all the responses in the updated version. We thank the reviewer for their diligence and humbly ask them to reconsider their score for the paper accordingly.

Reviewer_gGbeOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper estimates hidden selection probabilities in randomized model ensembles using “skeleton keys”: inputs whose output uniquely identifies selection of a particular model. It derives a constrained likelihood estimator and evaluates estimation accuracy and downstream attack benefits on CIFAR-10.

Critical strengths
  • The threat model usefully separates knowledge of candidate models from knowledge of their selection probabilities.
  • Exclusive outputs provide a clear Bernoulli observation model, and the likelihood’s convexity argument is sound.
  • Experiments cover diverse architectures and disclose low key-generation yields.
Critical weaknesses
  1. Feasibility under the single-use constraint is not demonstrated. Table 2 reports only 15–103 valid keys per model, whereas Section 4.2 requires 400 observations per model. The paper does not explain whether additional distinct keys were generated, keys were reused, or observations were simulated. It also leaves the similarity detector unspecified. These details are essential to substantiate the claimed query efficiency.

  2. The incremental benefit of skeleton keys remains unclear. Known models’ predictions on ordinary inputs can also provide information about selection probabilities, without requiring an exclusive label. A matched-budget comparison is missing. The downstream evaluation likewise compares against uniform attack-source sampling, leaving the benefit over stronger ensemble-aware baselines unresolved.

  3. The empirical results contain consequential inconsistencies. For the single-defense setting, Tables 4 and 12 report skeleton-key-informed robust accuracies of 65.80% and 75.70%, respectively. This changes the headline improvement from 10.70 to 0.80 points and requires explanation.

Additional issue: Table 10 assigns all defender probability to WRN and reports a game value of 93.80%. However, Table 7 reports WRN accuracy of 85.60% against its own APGD attack, which is included in the game’s attack set. Under the stated worst-case payoff definition, that pure strategy’s value cannot exceed 85.60%. The payoff construction or reported metric therefore needs correction or clarification.

The confidence claims exceed the analysis. Equations (16)–(22) provide an interior asymptotic approximation, not a finite-sample query guarantee. Several evaluated distributions contain exact zeros or ones, where the regularity assumptions fail. Repeated-trial coverage and appropriate boundary treatment are needed.

Questions for authors
  1. How were 400 distinct observations per model obtained while enforcing single-use and similarity constraints?

  2. Can the conflicting attack results and the game-value inconsistency be reconciled?

  3. How does estimation compare with ordinary-input queries at the same total budget?

2 comments

We thank the reviewer for the careful and constructive feedback. We have addressed all the questions given by the reviewer. This has led to a significant improvement in the overall contributions of this work.

Q1: “How were 400 distinct observations per model obtained while enforcing single-use and similarity constraints? ”

=We thank the reviewer for raising this point. In Table 3 we simulate the use of 400 keys through a repeated sampling process. We will make this clear in the updated writing of the paper. Furthermore, if we were to use our own proposed skeleton key algorithm to generate the sufficient number of skeleton keys, this is merely a scaling issue. In terms of scaling, 400 distinct keys per model would require approximately 26,700 candidate images for ViT, 38,100 each for WRN and FAT-R18, 66,700 for DM-R18, 80,000 for MambaVision-T, and 133,300 for CaiT-XXS. These numbers are calculated based on our updated experiments on the CIFAR-10 dataset. For the original CIFAR-10 training some of these numbers go beyond the original dataset size, however, there exists many other CIFAR-10 augmentation techniques that can create more starting clean examples so this is not a true limitation. For example see the following paper where CIFAR-10 augmentation has been done:

[1]https://arxiv.org/abs/2302.04638

Q3: “How does estimation compare with ordinary-input queries at the same total budget?”

=We would like to thank the reviewer for this question. We have added an additional column outlining the clean samples that satisfy the skeleton key conditions on CIFAR-10 dataset.

Target ModelClean KeysGenerated Keys (Ours)Improvement
CaiT-XXS263.0×
DM-R186122.0×
FAT-R1812211.8×
MambaVision-T4102.5×
ViT-L/1613302.3×
WRN-28-108212.6×
Total451002.2×

We have conducted the above experiment to alleviate this reviewer’s concern. Our results show clean images rarely satisfy this condition. Across the six target models, only 45 of 12,000 image–model pairs (0.38%) qualify as skeleton keys: 2 for CaiT, 6 for DM-R18, 12 for FAT-R18, 4 for MambaVision, 13 for ViT, and 8 for WRN. From the same candidate images, our implementation of the corrected skeleton key algorithm produces 100 valid keys (0.83%), more than twice as many (2.2×). It improves the count for every target model, with gains from 1.8× (FAT-R18: 12 → 21) up to a tripling for CaiT (2 → 6). The largest gains are on the models with the fewest clean keys, CaiT, where the number of keys triples, and MambaVision (4 → 10). Overall this shows the versatility and importance of our skeleton key generation algorithm which gives results not achievable using clean data alone.

W3: “consequential inconsistencies ”

=We sincerely thank the reviewer for pointing this issue out. We have cross-checked the value and want to declare two typos. In table 12, the skeleton key informed robust accuracy for the Single Defense Probability is 65.8%. In table 10. WRN's accuracy against APGD-CE(WRN) is 92.2%. We have checked all other values for correctness and verified our results. We will update the paper with these corrections accordingly.

Additional Reviewer Comment: “The confidence claims exceed the analysis.”

=We agree with the reviewer that the normal approximation used in Equations 16–22 is justified asymptotically for probability vectors in the interior of the simplex, but does not directly extend to probabilities exactly on the boundary (i.e., when probabilities are zero or one). We will clarify this distinction in the revised manuscript. Our objective was to determine a sufficiently large, uniform number of skeleton-key queries to estimate the probability of each defense appearing in the ensemble with a desired precision. Our analysis uses the asymptotic variance to determine the maximum confidence-interval width over the space of possible probability distributions. This provides a conservative query-budget calculation without requiring prior knowledge of the individual defense probabilities. For a desired margin of error of 0.05 at the 95% confidence level, this analysis suggests approximately using 264 queries obtained from the upper bound of the asymptotic variance from the limiting maximum variance calculation. We further increased this budget to 400 queries in our experiments to provide an additional margin of conservatism. We will update the paper with this analysis, accordingly to address the reviewer’s concern. We would like to clarify that the intention of this analysis was to establish a reasonable and conservative query budget based on estimation precision, rather than to claim or establish a finite-sample coverage guarantee for the resulting confidence intervals. We did not intend to suggest that the asymptotic normal approximation provides guaranteed finite-sample coverage, nor did we consider empirical repeated-trial coverage evaluation a requirement of this analysis.

Nevertheless, we agree that probabilities exactly on the simplex boundary warrant separate consideration. In such cases, exact finite-sample binomial confidence intervals can be used instead of the normal approximation. For example, when zero successes are observed in 400 independent queries, the two-sided 95% Clopper–Pearson exact confidence interval is approximately [0,0.0092]. Thus, the margin of error under the boundary truth is substantially smaller than our target margin of error of 0.05. This provides an additional justification that our selected budget of 400 queries achieves the desired estimation precision even in the boundary case. We will include this exact finite-sample treatment to complement the asymptotic analysis and clarify the interpretation of the query budget being our objective.

Finally, our use of the maximum variance across possible probability distributions is deliberate. It allows us to use the same query budget across all defenses without relying on intermediate estimates of their individual probabilities. To reiterate, we will add these clarifications and additional statistical analyses into the main paper or appendix.

Reviewer_ukhiOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies how an attacker can estimate the probabilities with which a defense selects among several models. It proposes “skeleton keys”: perturbed inputs for which one known model gives a unique class label. The attacker uses the observed labels to estimate the selection distribution, then uses that estimate to choose which model to attack. The paper gives a likelihood estimator and evaluates it on CIFAR-10 models.

Critical strengths
  • The question is interesting. A randomized defense may hide its selection probabilities even when the attacker knows the component models.
  • The idea of using model-specific predictions as measurements is clear, and the paper connects the estimated distribution to an attack experiment.
Critical weaknesses
  1. I am not sure how the estimation experiment gets enough keys. Table 2 finds only 15-103 valid keys per model from 2,000 images, but Table 3 uses 400 keys per model. The paper should explain how many images were needed to reach that number and what the total cost was.

  2. The paper does not show how many usable skeleton keys already occur among clean images. Since the attacker knows the models, they can find clean images where one model gives a unique label and query those directly. Comparing this simple approach with generated keys would show whether the perturbation algorithm adds much.

  3. The method is only evaluated on small CIFAR-10 dataset. This couldn't demonstrate the effectiveness of the method.

  4. The assumption is strong where attackers has access to set of models D. I wonder how effective the attack is in a less strong assumption (grey box/ blackbox settings)

Questions for authors
  1. How did you obtain 400 valid keys per model for Table 3, given the much smaller numbers in Table 2? How many candidate images did this require?

  2. How many valid skeleton keys can be found among unmodified clean images, and how does estimating the distribution with those keys compare with your generated keys at the same defense-query budget?

  3. Can the method generalize to different datasets, for example, ImageNet?

  4. How effective is the method if the attackers has less information about the set of models D?

2 comments

We thank the reviewer for the careful and constructive feedback. We have addressed all the questions which improved the overall contributions of this work.

While preparing this rebuttal we re-audited our pipeline and have updated the experimental numbers accordingly, hence some numbers may be different than what was originally reported in the paper.

W1,Q1: “I am not sure how the estimation experiment gets enough keys.” =We thank the reviewer for raising this point. In Table 3 we simulate the use of 400 keys through a repeated sampling process. We will make this clear in the updated writing of the paper. Furthermore, if we were to use our own proposed skeleton key algorithm to generate the sufficient number of skeleton keys, this is merely a scaling issue. In terms of scaling, 400 distinct keys per model would require approximately 26,700 candidate images for ViT, 38,100 each for WRN and FAT-R18, 66,700 for DM-R18, 80,000 for MambaVision-T, and 133,300 for CaiT-XXS. These numbers are calculated based on our updated experiments on CIFAR-10 dataset. For the original CIFAR-10 training some of these numbers go beyond the original dataset size, however, there exists many other CIFAR-10 augmentation techniques that can create more starting clean examples so this is not a true limitation. For example see the following paper where CIFAR-10 augmentation has been done: [1]https://arxiv.org/abs/2302.04638

W2, Q2: “The paper does not show how many usable skeleton keys already occur among clean images.” =We have conducted an experiment to alleviate this reviewer’s concern. Our results show clean images rarely satisfy this condition. Across the six target models, only 45 of 12,000 image–model pairs (0.38%) qualify as skeleton keys: 2 for CaiT, 6 for DM-R18, 12 for FAT-R18, 4 for MambaVision, 13 for ViT, and 8 for WRN. From the same candidate images, our implementation of the corrected skeleton key algorithm produces 100 valid keys (0.83%), more than twice as many (2.2×). It improves the count for every target model, with gains from 1.8× (FAT-R18: 12 → 21) up to a tripling for CaiT (2 → 6). The largest gains are on the models with the fewest clean keys, CaiT, where the number of keys triples, and MambaVision (4 → 10). Overall this shows the versatility and importance of our skeleton key generation algorithm which gives results not achievable using clean data alone.

W3, Q3: “The method is only evaluated on small CIFAR-10 dataset.” =We additionally evaluated our method on Tiny-ImageNet, using a three-model ensemble of WRN, CaiT, and MambaVision. Given more time, we will continue to generate more results on more datasets, but this is the experiment we could perform during the limited rebuttal period.

Our Tiny-ImageNet results confirm that both stages of our method, skeleton key generation and distribution estimation, transfer effectively to this larger setting. The following table outlines the valid keys and the yield rate.

Table: Skeleton key generation algorithm evaluation for each of the three models on Tiny-ImageNet. All skeleton keys use 100 iterations and a maximum l∞l_\infty perturbation of ϵmax⁡=0.031\epsilon_{\max}=0.031.

ModelValidNon-ValidYield RateClean Samples
WRN-28-1060593956.05%248
CaiT-XXS39796033.97%89
MambaVision-T1477852314.77%731

Attack Analysis on Tiny-ImageNet. The table below shows that using the skeleton key estimated defense distribution also improves attack effectiveness over the uniform baseline on Tiny-ImageNet. For the two skewed defense configurations, robust accuracy drops from 48.20% to 35.90% and from 48.40% to 33.10%, reductions of 12.30 and 15.30 percentage points, respectively. When the defense distribution is close to uniform, the gain is small or vanishes (1.70 and 0.00 percentage points), because the uniform assumption already closely matches the true distribution. These results show that the estimated defense distribution gives the attacker the most useful information when the defender’s model selection is non-uniform, yielding up to a 15.30 percentage-point gain in attack success.

Table: Estimate of and robust accuracy of randomized model ensemble under different attack settings on Tiny-ImageNet.

ModelsPD\mathbf{P}_{\mathrm{D}}P^D\hat{\mathbf{P}}_{\mathrm{D}}JSDRU\mathbf{R}_URS\mathbf{R}_SΔ\boldsymbol{\Delta}
WRN, CaiT, Mamba[0.10, 0.00, 0.90][0.0812, 0.0001, 0.9187]8.24×10−48.24 \times 10^{-4}48.20%35.90%12.30%
WRN, CaiT, Mamba[0.33, 0.33, 0.34][0.3342, 0.3143, 0.3515]2.16×10−42.16 \times 10^{-4}42.80%42.80%0.00%
WRN, CaiT, Mamba[0.00, 0.00, 1.00][0.0000, 0.0001, 0.9999]5.00×10−55.00 \times 10^{-5}48.40%33.10%15.30%
WRN, CaiT, Mamba[0.24, 0.24, 0.52][0.2477, 0.2303, 0.5220]1.17×10−41.17 \times 10^{-4}44.00%42.30%1.70%

These results demonstrate that our method generalizes beyond CIFAR-10 to a larger and more complex dataset. We will include the Tiny-ImageNet results in the revised manuscript.

W4, Q4: “I wonder how effective the attack is in a less strong assumption” =Our threat model is consistent with the literature, which commonly assumes attacker knowledge of the defense models [1, 2, 3]. The white-box setting is also reasonable in realistic cases for example in the voting domain for ballot classification and in the medical domain. For example, a medical diagnosis system may deploy well-known, publicly available models, so an attacker can reasonably know the candidate set. Extending our attack to grey-box and black-box settings is an exciting direction for future work, but it is beyond the scope of this paper.

[1] https://arxiv.org/pdf/2003.01690 (white-box realism in election systems)

[2] https://www.sciencedirect.com/science/article/pii/S0925231225021782?via%3Dihub (white-box realism in energy efficient machine learning)

[3] https://arxiv.org/abs/2506.14582 (white-box auto-attack, the defacto standard for measuring robustness)

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.