On the Adversarial Robustness of Benjamini Hochberg

Summary

Benjamini-Hochberg provides a means for controlling the false detection rate (FDR) in multiple hypothesis testing. This paper explores how the FDR region can be perturbed by an adversary. Specifically, the author(s) propose two adversarial attacks *Increase-C* and *MOVE-1* to efficiently perturb *c* scores and 1 score, respectively. The author(s) prove analytical bounds on their attacks' guarantees. The author(s) also provide simulated experiments demonstrating their attacks effectiveness on synthetic z-scores.

Strengths

I was not familiar with Benjamini-Hochberg before reading this paper (I did not bid on the paper). However, with significant effort and outside reading, the paper was still attainable. That is a strength of the work in general. The *Balls in Bins* warm-up was definitely helpful to a reader. I provide comments on how this warm-up could be improved below. ### Novel Area and Good Execution To the extent of my knowledge, no existing work has studied the adversarial robustness of methods to control FDR. I discuss why I believe that is below in the limitations section. Nonetheless, the authors provide reasonable first-pass attack methods that are intuitive and performant. They even provide an optimal method in the case of singleton perturbations. The authors also provide thorough theoretical analysis.

Weaknesses

### Very Little Analysis of Section 5's Empirical Results Sections 5.1 and 5.2 are essentially just an overview of the two experimental setups. There is no real analysis or discussion of what the experimental results show or why it's important. While Section 5.3 has some basic analysis, it is again quite minimal. I understand that the page limit forces difficult decisions over content but so little in the way of commentary on the results is a disservice to the reader and overall a poor choice. I would have preferred empirical results on real datasets as opposed to the toy datasets in the paper, but I understand the author(s)'s choices here, especially given related work. ### Move-1 Relegated to the Appendix Beyond a very definition in Section 1.5, all discussion of MOVE-1 including how the method works and why its optimal are relegated to the appendix. There should at least a basic overview of the key ideas of MOVE-1 including some basic intuitions how it differs from INCREASE-c in the main paper. ### Making the Work More Intuitive Section 2 in my view is a warmup for readers to help build intuitions and understanding of BH, even if they are not familiar with the related background. Section 2 could be significantly improved if figures were used to better illustrate the key ideas. These figures need not be large and any additional camera ready page could be used to visualize the ideas. Even if the authors chose not to include such figures in the main paper, they could be in the appendix. ### Limited Potential Impact There is undeniable merit and utility in studying the robustness of a method that provide tools to control FDR, such as Benjamini-Hochberg. Nonetheless, this work falls essentially is a niche (BH) within a niche (adversarial analysis). Hence, I view it as unlikely that this work will have a significant impact.

Questions

None.

Rating

6

Confidence

3

Soundness

3

Presentation

2

Contribution

2

Limitations

This paper describes two adversarial attacks and identifies the brittleness of Benjamini-Hochberg. While such work inherently creates a non-zero risk, there are no serious negative societal impact.

Summary

This paper studies the adversarial robustness of the Benjamini-Hochberg (BH) procedure, introducing simple adversarial test-perturbation algorithms. The experiments show that BH's control can be significantly compromised with minimal perturbations. The analysis uses a combinatorial perspective and generalized ballot problems to derive non-asymptotic lower bounds.

Strengths

This paper addresses a novel and significant aspect of the BH procedure—its adversarial robustness. This research probelm is relatively unexplored, providing new insights into the vulnerabilities of widely used statistical methods.

Weaknesses

This paper would benefit from a discussion of potential mitigation strategies that could enhance the robustness of the Benjamini Hochberg procedure against attacks such as INCREASE-c.

Questions

Please refer to the weaknesses.

Rating

5

Confidence

1

Soundness

3

Presentation

2

Contribution

3

Limitations

The authors' justification is "Yes, we discuss to what extent our analysis could be extended and further generalized, but were not done due to space constraints.". However, even in Appendix, there is not any analysis of limitations.

Summary

In this paper, the authors have tested the Benjamini-Hochberg (BH) 's adversarial robustness, as this procedure is deployed in critical applications such as drug discovery, forensics, and anomaly detection. Specifically, the authors develop a class of simple and easily implementable adversarial test-perturbation algorithms to analyze under what conditions BH does and does not exhibit adversarial robustness. Next, to support their findings, the authors provide non-asymptotic guarantees on the expected adjustments to the FDR due to these adversarial attacks. Their technical analysis involves a combinatorial reframing of the BH procedure as a "balls into bins" process. It connects this to generalized ballot problems to utilize information-theoretic approaches for deriving non-asymptotic lower bounds. Finally, the authors also conducted experiments to support their findings.

Strengths

- In this paper, the authors provided a detailed theoretical analysis of the BH procedure's robustness against adversarial attacks. They also introduced the INCREASE-c algorithm, which gives methodical mathematical bounds and probabilities for different cases (large and small alternative means). - I liked how advanced probabilistic and statistical tools, such as KL divergence and Pinsker's inequality, are used to provide a solid mathematical foundation for the analysis. The proofs and the lemmas were thoroughly justified. - Finally, the paper presentation is well-structured. The paper's organization is clear and logical. In each section, a comprehensive analysis is done and well-presented.

Weaknesses

- In practical scenarios, an adversary manipulates the input directly, not the z-scores; thus, the insight into how perturbations applied to z-scores translate back to the original data samples or vice-versa is missing in the paper. - My other concern is that since z-scores are computed only utilizing the means and the standard deviation of the sample, the manipulation at the data level can get lost at the z-scores level.

Questions

- In practical scenarios, an adversary manipulates the input directly, not the z-scores; thus, could the authors provide more insight into how perturbations applied to z-scores translate back to the original data samples or vice-versa? Or, when the inputs are perturbed, what will impact the proposed analysis of the BH algorithm (given the z-scores computed from the input samples)? - A statement on Page 4: "A benefit of this approach is that perturbation at the level of z-scores places the corruption more directly at the point of data collection than does perturbation of the p-values." Could the authors answer: Won't the perturbation at the data collection directly place the corruption at the data level? Also, why was it not assumed to be corruption at the data level, then the computation of either the z-scores or the p-values? How this mapping between the data and the z-scores is computed? - The evaluation results are a bit difficult to navigate in the paper. For example, Figure 1 and Figure 4 are not understandable. Could the authors make the evaluation section comprehensible? - Could the authors add more evaluations to test how the proposed method performs with real-world data? Post-rebuttal: I have changed my rating from borderline reject to borderline accept, confidence from 3 to 4, and soundness of the paper from 2 to 3.

Rating

5

Confidence

4

Soundness

3

Presentation

4

Contribution

3

Limitations

Same as Weaknesses.

Summary

The paper explores the adversarial robustness of the Benjamini-Hochberg procedure. In particular, the authors theoretically show that it is possible to perturb test scores to cause the BH procedure to not be robust to adversarial attacks. BH is reframed as a "balls into bins" problem, and the authors propose an algorithm (INCREASE-c) to increase the rejection count. The authors also provide experiments to support their theoretical findings.

Strengths

- The technical contribution seems solid and sound. - There is a clear novelty aspect, as the adversarial robustness of BH has not been considered before. - The authors show an interesting gap between distributional robustness (which was shown to hold (ref [29] in the paper)) and adversarial robustness for BH procedure. - The (synthetic) statistical experiment supports the theoretical claims.

Weaknesses

- In the introduction, the paper (correctly) highlights the importance of hypothesis testing to various safety applications such as OOD detection. However, the experimental section does not, in any capacity, consider an end-to-end application such as OOD detection. In fact, it reads purely as a statistical simulation (which is fine as a synthetic experiment). But a minimal experiment with a MNIST/FashionMNIST OOD-classifier, to show that indeed the Z-scores can be affected by INCREASE-c could make the paper much stronger. - The attack is dependent on the algorithm (BH) used for FDR -- stronger results in adversarial robustness are often model/algorithm-independent. - There seems to be a certain lack of justification for choices in the problem setup (addressed in questions below).

Questions

- Problem setup questions: - What is the rationale for the attacker having access to z-scores at that stage of the pipeline? Usual studies consider attackers having access to data, and it may take quite a lot of changes in data points to change a z-score. - Why is the attacker's knowledge of $q$ realistic? I assume that in some models, the deployment will come with a (public) guarantee for $q$ -- but this should be at least mentioned. - It would be good to have a comment justifying the choice of perturbation ( $||\cdot||_0$ ), which I suppose is because BH is an algorithm for order statistics. What happens when considering a different type of budget (e.g., arbitrary $||\cdot||_p$ norms)? - l.128-132: When are these assumptions met in practice? - What is the impact of attacking BH procedure on the whole OOD system? Can you break OOD detection in a meaningful way? **** Post-rebuttal: I have increased my confidence score from 2 to 3 following the authors' response and other reviews.

Rating

6

Confidence

3

Soundness

3

Presentation

4

Contribution

2

Limitations

I think some of the problem setup questions above would address some limitations of the work.

Rebuttal Response

Dear authors, Thank you for the detailed rebuttal and the clarifications. Regarding the OOD application, my comment was more in line with reviewer L7r5, in that an experiment on real-world data (rather than a synthetic one) would significantly strengthen the paper. Regarding the algorithmic-dependent results, a remark in the spirit of the last sentence of your response to this weakness (*Further, BH belongs to the family of step-up procedures, which means the rejection region is decided via a stopping time (see our analysis), which since our paper shows can be manipulated, it means other ``step-up" procedures" are similarly prone.*) would be worth including in a future version, perhaps along with more general theorem statements/corollaries. My last remaining question for the author is whether they would be willing/able to add justifications/explanations in the paper in line with my and other reviewer's comments and questions on z-scores perturbation, choice of norm, adversary's power, etc. (which would make the paper clearer, a bit more solid and easier to approach for people who are not as familiar with the literature), and whether they have or will perform an experiment on real-world data as suggested by L7r5 and myself.

On a Real-World data experiment (Credit Card Fraud Detection)

Thanks for letting us address the comments on real-world data. We have since conducted an experiment on the ``Credit Card" dataset, the same one used in the real-world data experiments in Bates, Candes, et al 2023. While we appreciate the suggestion to consider MNIST/FasionMNIST, we chose this experiment on this dataset, as it relates to fraud detection, which we feel may better align with the Safety in Machine Learning theme. We proceed to describe this experiment. The ``Credit Card" dataset contains 284,807 transactions transactions made by credit cards in September 2013 by European cardholders over the course of two days - 492 of which were frauds. With the exception of 'Time' and 'Amount', it contains numerical input variables that are the result of a PCA transformation. The 'Class' label takes value 1 in case of fraud and 0 otherwise. We trained an isolation forest (just as Bates et al 2023 did) on 141,758 randomly selected genuine transactions (that is, about 1/2 of the total) using the R library isotree. Then for each of $10^2$ simulations, we drew 141,657 genuine instances uniformly at random from the remaining 142,557 genuine transactions to form a calibration set, with the remaining 900 genuine transactions combined with a randomly drawn set of 100 forged instances drawn from the 492 forged collection to form a test set of 1000 credit card transactions. Running the score function on the test set members produced a collection of test set anomaly scores, which with the use of the calibration set, conformal p-values were generated. Hence, in each of the simulations that saw the random generation of calibration and test sets, a list of conformal p-values is generated, one for each corresponding test set credit card transaction. Next, we executed our adversarial INCREASE-c algorithm to generate an altered list $p$ of p-values, for varying $c$; in other words, $c$- many of the credit card transactions from the test set were altered to generate a slightly modified list $p_{+c}$. Then, we performed $BH_{0.1}$ twice, once on $p$, and once on $p_{+c}$. We report the average (over all simulations) false detection proportion (FDP) by $BH_{0.1}$ when there is no adversarial intervention, $E[FDP[BH_{.1}; p]]$, the average FDP incurred by $BH_{0.1}$ when the adversary implements INCREASE-c (for $c = 1, 5, 10, 20$), $E[FDP[BH_{.1}; p_{+c}]]$ , as well as the average rejection count $E[\tilde{k}]$ and the adversarially-adjusted rejection count $E[\tilde{k}_{+c}]$. See the summary table below. | $c$ |$E[FDP[BH_{.1}; p]]$ | $E[FDP[BH_{.1}; p_{+c}]]$ |$E[\tilde{k}]$ |$E[\tilde{k}_{+c}]$ | |-------|------------------------|----------------------------|-----------------|----------------------| | 1 | 0.09 | 0.11 | 62.6 | 64.27 | | 5 | 0.09 | 0.17 | 48.69 | 57.12 | | 10 | 0.09 | 0.23 | 56.39 | 72.85 | | 20 | 0.09 | 0.31 | 58.12 | 89.06 | The false detection proportion is the proportion of the total number claimed to be fraudulent that were in fact genuine. As we can see, although $BH_{0.10}$ can control the FDR below the explicit $0.10$ level, INCREASE-c's tampering can push the FDR above this control level. We are happy to conduct more real-world data experiments and add to the appendix, if given the opportunity to do so. We would be glad to share the relevant R code as well.

Clarification on Credit Card Experiment and the role of the adversary for L7r5

*Question: Could the authors explain this? If the authors are again computing a perturbed set of p-values from the input samples, which are already manipulated by an adversary, then the feasibility of the proposed approach in real scenarios is lost.* **Response: The input samples are not "*already manipulated by an adversary*." If we are understanding correctly, you are under the impression that fraudulent credit card transactions are created by the adversary we are studying, which is not the case. Both genuine and fraudulent credit card transactions are phenomena that arise/occur independent of the adversary we are studying, albeit fraudulent ones are considered "anomalies" that we certainly wish to detect. And the adversary we are studying is acting to complicate this task of distinguishing the genuine from the fraudulent. More precisely, an anomaly detection system's task in this context is to help credit card companies distinguish fraudulent credit card transactions from genuine credit card transactions. Bates et al 2023 and other recent works would suggest developing an anomaly detection system that leverages BH's false discovery rate control so as to not make too many false positives which in this context translates to not mistakenly identify too many genuine transactions as fraudulent.** **In particular, Bates et al 2023 used exactly this same dataset to illustrate their methodology. They first trained an isolation forest on genuine transactions. Then they drew a random test set composed of both genuine and fraudulent transactions (the identity of which is effectively unknown to the decision-maker/AI system) in order to evaluate the capacity of their methodology to detect fraudulent transactions. Using the trained isolation forest along with a calibration set, they transformed the test set transactions into a corresponding collection of (conformal) p-values, for which they used BH to ultimately label each test set transaction as either genuine or fraudulent. While BH provides the guarantee that the expected false positive rate (or FDR) of this methodology can be kept below a user-defined threshold, we show that if an adversary were to step in and make (minimal) alterations to the test set of transactions, the methodology's FDR control could be broken. For details on this statement, we kindly refer you to the fact that our simulations indicated $E[FDP[BH_{0.1}; p]] \leq 0.10$, in line with the theory of BH; however, upon adversarial intervention on the test set, i.e., execution of INCREASE-c, we obtained instead $E[FDP[BH_{0.1}; p_{+c}]]$ that (significantly) exceeded 0.10. In other words, the adversary's corruption of $c-$ many test transactions could confuse the BH-based methodology into a greater FDR than it would claim, equiv., the average ratio of (the number of transactions falsely labeled as fraudulent) : (number of all transactions labeled as fraudulent) is higher than what would be guaranteed.** *Question: The authors should have first computed p-values and the z-scores from the input samples and then implemented the INCREASE-c algorithm to calculate its efficacy.* **Response: If we're understanding you correctly, this is in fact precisely what we did. It appears as though there has been a misunderstanding of what the Credit Card Data experiment is about. We sincerely hope our response in the preceding lines above have helped to clarify.**