Intrinsic Explanation of Random Subspace Method for Enhanced Security Applications

We thank the reviewer for the constructive comments.

Weakness 1. Adaptive attack discussion: Discussion and experiments on adaptive attacks could further strengthen the paper. If attackers know the defense strategy, what happens? For instance, they could adjust the attack target so that triggers do not fall within the top 10% or 20% of important features but rather within the top 30% or 40% to circumvent defenses.

Thank you for the constructive suggestion. We think that designing adaptive attacks capable of simultaneously bypassing both the defense mechanism (the random subspace method) and staying undetected by our method is an intriguing and meaningful direction for future research.

Question 1. The two works compared by the authors are not defense-oriented, so is this comparison fair? Should comparisons also include existing defenses against backdoor and adversarial attacks for large language models (LLMs) to better evaluate the proposed method’s effectiveness?

We emphasize that our method is not primarily defense-oriented. Instead, we first establish that it provides a faithful explanation by proving its order consistency with the Shapley value. Faithfulness, in this context, implies that a feature with greater influence on the model's prediction is assigned a higher importance score. Consequently, the certified detection guarantee can be seen as a byproduct of this faithfulness. Moreover, as demonstrated in Table 1 of the experimental section, our method outperforms baseline approaches even when no attacks are present.

While the random subspace method can be employed to defend against backdoor and adversarial attacks on LLMs, existing research has only focused on its use for jailbreaking attacks (which can be considered a more powerful form of adversarial attack without constraints on the perturbation boundary). We believe that exploring the application of the random subspace method for defending against backdoor and adversarial attacks on LLMs presents an intriguing direction for future research.

Question 2. Without prior knowledge, if the proposed method is used to defend and 10% or 20% of the important words are deleted, can the LLM still make accurate responses? The experimental results do not indicate whether the defense proposed in this paper affects the model's responses to normal text.

Our method serves as a post-hoc explanation tool for existing defense mechanisms that uses the random subspace method. It does not alter the decisions made by these defense mechanisms but instead identifies the most important features influencing those decisions.

Question 3. Regarding the faithfulness comparison in Table 1: Faithfulness is defined as the percentage of label flips when the top e features with the highest importance scores are deleted. My understanding is that this metric should be as high as possible under attack, as the deleted important features likely contain adversarial elements. In the absence of an attack, if deleting these features leads to a high label flip rate, it indicates that removing important features significantly impacts model performance. How should one decide whether or not to delete these features?

Thank you for the question. In this paper, faithfulness is employed as a metric to evaluate the performance of the explanation. It’s important to note that our method does not actually delete features in practice. Instead, it provides an explanation for the outcome of a defense mechanism (one using the random subspace method). For instance, when combined with RA-LLM in the context of jailbreaking attacks against LLMs, our method serves as a post-attack analysis tool. RA-LLM determines whether an attack has occurred, and our method is subsequently used to identify which parts of the input leads to that decision.

Question 4. It is recommended that the authors add a discussion on adaptive attacks to enhance the practical value of the proposed method.

Thank you for the valuable suggestion. We believe that developing adaptive attack strategies that can effectively bypass both the defense and the explanatory mechanisms presents an exciting and important avenue for future research.

We thank the reviewer for the valuable feedback. We address the questions below:

Weakness 1. In section 4, the importance scores for each feature within a given feature group are equal. This approach is overly simplistic and fails to reasonably capture the differences in importance among the various features.

We note that these feature groups are randomly sampled and can be vary. In Section 5.3, we demonstrate that our method satisfies the essential properties of effective feature attribution and is order-consistent with the Shapley value. For more details, please refer to Weakness 4.

Weakness 2. In section 4, the author highlights an issue where variations in appearance frequency can lead to an unfair assessment of feature importance when the sample size N is small. However, there is no mathematical analysis of Eq. (9) to demonstrate how the designed importance score addresses this issue.

Thank you for pointing that out. We conduct an empirical comparison between two approaches: (1) directly applying Monte Carlo sampling, and (2) Monte Carlo sampling with normalization based on appearance frequency (Eqn. 9). Our experiments focus on adversarial attacks, with $N$ set to 200. The results demonstrate that normalizing the importance scores by appearance frequency improves the performance.

Weakness 3. In section 5.1, why not limit k < |S| instead of considering the special case that |S| < k. In Section 5.1, we follow the standard definition of the Shapley value, which is calculated as the average of marginal contributions across all feature subsets, ranging in size from $0$ to $d-1$. This implies that for any given feature subset $S$, regardless of its size, the ensemble model should always be able to make predictions.

However, by the original definition, the ensemble model cannot subsample $k$ features from the provided $|S|$ features if $|S| < k$. To address this limitation and ensure theoretical rigor, we mention this special case in our analysis.

Weakness 4. The importance score is calculated based on the frequency with which a feature is selected and the predicted label, meaning that two features that are occasionally selected together end up with the same importance score. In contrast, Shapley value calculations based on label probability would differentiate between these features. Consequently, the proposed ENSEMBLESHAP, which relies on this importance score, assigns identical values to these features, potentially overlooking the differences in their individual influences.

Thank you for the question. In fact, two features that are occasionally selected together will not have the same importance score. They will only have identical scores if they are always selected together in every subsampled feature group. However, the probability of this occurring decreases exponentially as the number of subsamples increases.

As we prove in Section 5.3, our method is order-consistent with the Shapley value when a large number of feature groups are subsampled. In other words, if the Shapley value can differentiate between these features, our method can do so as well.

Weakness 5. The authors claim that the proposed method is computationally efficient. However, there is a lack of analysis regarding its complexity and the associated time costs.

Given that the random subspace method is already deployed, our method introduces negligible additional computational time (less than 3 seconds) for the explanation.

Thanks for the feedback!

Weakness 1. Unclear presentation.
The general approach of bagging or subsampling the feature set was, to the best of our knowledge, originally introduced to enhance the performance of decision trees. Therefore we follow the naming. We will provide additional clarification of this terminology in our paper.

Weakness 2. Lack of empirical computational complexity analysis.
We note that our method serves as a post-hoc explanation for the random subspace method. This means the defender first makes predictions using the random subspace method (which involves a large number of base model queries to improve robustness), and then our method provides an explanation for those predictions. Our key claim is that our approach incurs negligible additional computational cost (less than 3 seconds to compute Eqn.9), as it reuses the computational byproducts already generated during the deployment of the random subspace method. In contrast, other feature attribution methods require additional computation time because they are not specifically tailored to the random subspace method.

Weakness 3. No comparison with other efficient Shapley values estimation techniques.
Given that the RSM is already deployed, our method introduces negligible additional computational overhead (less than 3 seconds). FastSHAP can be seen as an extension of LIME, which needs to build up a training dataset for the explainer model. When applied directly to the random subspace method, it needs significant additional computational time.

Weakness 4. The formal algorithm is missing.
Sorry for the confusion. Eqn.9 in Section 4 provides the formal calculation of our method with “Monte Carlo” sampling. We use binary search to solve the presented optimization problem in Section 5.4. We will provide clarification on this in our paper.

Weakness 5. No further discussion of the certified detection rate results. The paper should be more self-contained. Thank you for pointing this out. The explanation for the experimental results on the certified detection rate was short due to space constraints. From our experiments, we observed that the certified detection rate is insensitive to the total number of features (e.g., IMDB has much longer input sequences than AG-News, but both exhibit similar certified detection rates). However, the certified detection rate is strongly influenced by the ratio of subsampled features to the total number of features, as shown in Figure 17 in the Appendix. Specifically, a smaller subsampling ratio (or larger dropping ratio) improves the certified detection rate. This occurs because each adversarial feature influences fewer subsampled groups, making it harder for these features to change the predicted label without being detected.

Regarding the plateau observed after a few "e," we notice a turning point when "e" reaches the number of adversarial features "T." Beyond this point, the number of reported features "e" is no longer the bottleneck. Instead, the certified detection rate depends more on "T." When "T" is large, in the worse case, the attacker can distribute the influence of perturbed features more evenly toward the target label, making each adversarial feature contribute less to the target label. Since there are benign features that may inadvertently contribute to the target label, these perturbed features become hard to detect.

Some experimental details are in the appendix because of space reasons. We will further refine our paper.

Question 1. Why did the authors not provide a comparison with other efficient methods for Shapley values estimation, like FastSHAP [1]?
Please refer to Weakness 3 for details. In summary, our method repurposes the computational byproducts generated during the ensemble model's predictions to provide explanations, with no additional computational cost. Additionally, we theoretically demonstrate that our explanation is order-consistent with the Shapley value for the ensemble model, which is hard to compute.

Question 2. What approach is used for solving the optimization problem stated in Sect. 5.4?

We use binary search to solve the optimization problem in Section 5.4. We will provide clarification on this in our paper.

Question 3. What rationale is behind selecting the ICL as a baseline? How is it adapted for feature attribution?

We think it would be interesting to leverage the in-context learning capabilities of large language models (LLMs) to build the explainer, as LLMs are becoming increasingly powerful and widely adopted. For this purpose, we use the GPT-3.5-turbo model. The prompt includes an in-context learning dataset, where the inputs consist of indexes of subsampled features, and the labels correspond to the predictions of the base model based on these subsampled features. The prompt includes an instruction guiding the LLM to output a ranked list of a certain fraction (e.g.,20%) of the most important features.

We thank the reviewer for the constructive comments.

Weakness 1.EnsembleSHAP is designed specifically for random subspace methods, which could limit its generalizability to other ensemble methods or broader feature attribution applications that do not involve subsampling.

Random subspace methods have a wide range of applications. In this paper, we focus on their use for defending against attacks in the input space. Additionally, random subspace methods have been applied to differential privacy (Liu et al., 2020), facilitate machine unlearning (Bourtoule et al., 2021), and build robust models to withstand poisoning attacks (Jia et al., 2021). Exploring the potential of EnsembleSHAP in these and other applications of random subspace methods represents an intriguing direction for future research.

Weakness 2. The efficiency claim is not well studied in the experimental section.

Our method serves as a post-hoc explanation technique for the random subspace method, leveraging computational byproducts while introducing negligible costs (less than 3 seconds). Improving the computational efficiency of the random subspace method itself remains an open challenge (Jia et al., 2021;Zhang et al.,2023; Zeng et al.,2023).

Weakness 3. The certified detection theorem and detection strategy are not clearly explained, making it difficult for readers to fully understand the approach and its guarantees.

Thank you for pointing that out. The explanation of the certified detection theorem is brief due to space constraints. The theorem states that if an attacker modifies $T$ features of the original testing input $x$ to alter the predicted label of the ensemble classifier, our method can guarantee that $D(x, T)$ of these modified features will be detected as the most important features.

To provide some intuition, consider an extreme case where the subsampling size $k$ is 1, meaning each feature gets a single vote. Suppose there are 5 features in total, and all features initially vote for the correct label before the attack. To flip the predicted label, the attacker would need to change the predictions of at least 3 features to the target label. In this scenario, the contributions of these 3 modified features to the target label would surpass those of the unmodified features (which contribute nothing to the target label). Therefore, if we report top-3 most important features for the predicted label (after the attack), these 3 modified features are provably reported.

The guarantee $D(x, T)$ depends on several factors in the general case:

1. Confidence of the ensemble model's prediction before the attack: If the ensemble model is highly confident, the modified features must influence a greater number of subsampled groups to alter the prediction, making them more detectable.

2. Subsampling ratio: A smaller subsampling ratio enhances certified detection performance.

3. $T$: A larger $T$ makes certified detection more challenging.

These factors collectively impact the effectiveness of the certified detection.

Weakness 4. The method’s assumptions about limited modifications to input features may not hold, where an attacker might poison the entire input space or apply more complex poisoning strategies.

Our certified detection guarantee holds for any complex poisoning strategies, provided the number of poisoned features is bounded. However, we acknowledge that certified detection becomes increasingly difficult as the number of perturbed features grows. This is because adversarial features can collectively influence the target label, reducing the individual contribution of each adversarial feature to a level that becomes indistinguishable from benign features (which may also inadvertently contribute to the target label). It is worth noting that this challenge also exists in certified defenses. Indeed, existing certified defenses (Jia et al., 2021; Zhang et al.,2023; Zeng et al.,2023) cannot certify for >10% of adversarial features. In practice, our method is still effective when 20% of the input features are poisoned (in adversarial attacks).

Weakness 5. Some attacks evaluated are somewhat dated, and there are newer, more sophisticated adversarial and backdoor attacks. In fact, one can even design an adaptive attack.

We employ TextFooler for adversarial attacks and BadNets for backdoor attacks because they are representative and can be readily applied to ensemble models. Many advanced white-box adversarial attacks require substantial modifications and high computational costs to adapt to ensemble models. For black-box attacks, the design of state-of-the-art methods fundamentally aligns with TextFooler, as they all rely on a trial-and-error process for black-box optimization. Additionally, our certified detection analysis indicates that the effectiveness of our method depends largely on the total number of modified features, rather than the specific attack strategy employed.