EnsembleSHAP: Faithful and Certifiably Robust Attribution for Random Subspace Method

1. Problem Statement

The Random Subspace Method (RSM) is a widely used ensemble learning technique in security applications, such as providing certified defenses against adversarial attacks, backdoor attacks, and jailbreaking attacks on Large Language Models (LLMs). While RSM offers robustness guarantees, understanding why it makes specific predictions (feature attribution) remains a significant challenge.

Existing state-of-the-art feature attribution methods (e.g., Shapley values, LIME) face two critical limitations when applied to RSM:

1. Computational Inefficiency: Standard methods require perturbing the input $M$ times. For RSM, each perturbed input requires $N$ sub-sampled evaluations to generate an ensemble prediction. This results in a prohibitive computational cost of $M \times N$ queries (often exceeding $1,000 \times 1,000$), making them impractical for real-time or large-scale use.
2. Lack of Security Guarantees: Existing methods lack theoretical robustness against explanation-preserving attacks. In such attacks, an adversary perturbs the input to cause misclassification while manipulating the features so that the attribution method still highlights the original (benign) features, effectively hiding the attack.

2. Methodology: EnsembleSHAP

The authors propose EnsembleSHAP, a feature attribution method specifically designed for the Random Subspace Method that reuses computational byproducts from the ensemble prediction process.

Core Algorithm

Instead of generating new perturbations, EnsembleSHAP calculates importance scores based on the feature groups already sampled during the RSM prediction process.

• Definition: For a predicted label $\hat{y}$, the importance score $\alpha_i^{\hat{y}}$ of the $i$-th feature is defined as the probability that a randomly sampled feature group contains $x_i$ and predicts $\hat{y}$.
• Formula:
  $$\alpha_i^{\hat{y}}(x, h, k) = \frac{1}{k} \mathbb{E}_{z \sim U(x,k)} [I(x_i \in z) \cdot I(h(z) = \hat{y})]$$
  Where $z$ is a random subset of size $k$, and $h$ is the base model.
• Efficient Approximation: To avoid bias from uneven feature appearance frequencies in finite sampling, the authors introduce a normalization term. The score is approximated as:
  $$\alpha_i^{\hat{y}} \approx \frac{1}{d \cdot \sum I(x_i \in z_j)} \sum_{j=1}^N I(x_i \in z_j) \cdot I(h(z_j) = \hat{y})$$
  This reuses the $N$ predictions already computed for the ensemble decision, adding negligible overhead (~0.03s).

Theoretical Properties

EnsembleSHAP is proven to satisfy key properties of effective attribution:

1. Local Accuracy: The sum of all feature importance scores equals the ensemble's predicted probability for the label.
2. Symmetry: Features contributing equally to all subsets receive equal scores.
3. Order Consistency: The ranking of features by EnsembleSHAP is consistent with the ranking by the theoretical Shapley value for RSM. (Note: It relaxes the "dummy" and "linearity" properties of Shapley values to achieve computational feasibility, but maintains order consistency which is crucial for ranking).

Certified Robustness

The paper provides the first provable robustness against explanation-preserving attacks.

• Theorem: The authors derive a Certified Detection Size ($D(x, T)$). This is a lower bound on the number of adversarial features (modified by an attacker changing $T$ features) that must appear in the top-$e$ most important features reported by EnsembleSHAP.
• Mechanism: If an attacker changes the model's prediction, they must alter the predictions of enough feature groups. This inevitably increases the importance scores of the modified features, making them detectable. The authors provide an optimization problem to calculate the minimum overlap between modified features and reported important features.

3. Key Contributions

1. Novel Attribution Method: Introduction of EnsembleSHAP, the first feature attribution method tailored for Random Subspace Methods that is both computationally efficient and theoretically grounded.
2. Provable Robustness: Establishment of the first theoretical guarantee against explanation-preserving attacks, quantifying the minimum number of adversarial features that must be detected.
3. Computational Efficiency: The method adds negligible computational cost (reusing existing RSM byproducts) compared to the massive overhead of applying Shapley/LIME directly to ensembles.
4. Comprehensive Evaluation: Extensive empirical validation across text classification (SST-2, IMDB, AGNews) and LLM jailbreaking scenarios.

4. Experimental Results

The authors evaluated EnsembleSHAP against baselines (Shapley values, LIME, ICL) under various attack scenarios:

• Faithfulness (Clean & Attacked Data):

  • In Backdoor and Adversarial attacks, EnsembleSHAP significantly outperformed baselines. For example, on the IMDB dataset under adversarial attacks, removing the top 10% of features identified by EnsembleSHAP caused a label flip in 98% of cases, compared to 84% for Shapley values and 16% for LIME.
  • In Jailbreaking defense, it successfully identified the harmful queries embedded in prompts with higher precision and recall than baselines.

• Key Word Prediction:

  • EnsembleSHAP achieved superior Precision and Recall in identifying ground-truth trigger words (backdoors) or adversarial words. For backdoor attacks on IMDB, it achieved a recall of 0.892 (vs. 0.491 for Shapley).

• Certified Detection:

  • The method successfully certified the detection of adversarial features. As the number of reported important features ($e$) increased, the certified detection rate improved.
  • The detection rate remained robust even as the number of modified features ($T$) increased, though it naturally decreased with higher $T$.

• Efficiency:

  • Feature attribution took ~0.03 seconds per sample.
  • Certified detection took ~0.2–0.4 seconds per sample.
  • This is orders of magnitude faster than applying Shapley/LIME to the ensemble (which would require thousands of base model calls).

5. Significance

• Bridging the Gap: This work bridges the gap between robust machine learning (RSM) and explainable AI (XAI). It allows users to trust why a robust model made a decision without sacrificing the model's security guarantees.
• Security Implications: By providing certifiable detection of adversarial features, EnsembleSHAP enables security systems to not only reject malicious inputs but also audit them to identify exactly which parts of the input caused the failure. This is crucial for debugging defenses and understanding jailbreak mechanisms.
• Scalability: The method's efficiency makes it viable for deployment in real-world security systems where latency and computational resources are constrained.
• Theoretical Advancement: It establishes a new benchmark for robustness in XAI, moving beyond "prediction-preserving" attacks to "explanation-preserving" attacks, a critical frontier in adversarial machine learning.

In summary, EnsembleSHAP offers a faithful, efficient, and mathematically provable solution for explaining Random Subspace Methods, ensuring that security-critical models remain transparent and auditable even under sophisticated adversarial conditions.