On the Adversarial Robustness of Benjamini Hochberg

Authors: louis l chen
roberto  szechtman
matan  seri
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 13:07:42

Abstract: The Benjamini-Hochberg (BH) procedure is widely used to control the false detection rate (FDR) in multiple testing. Applications of this control abound in drug discovery, forensics, anomaly detection, and, in particular, machine learning, ranging from nonparametric outlier detection to out-of-distribution detection and one-class classification methods. Considering this control could be relied upon in critical safety/security contexts, we investigate its adversarial robustness. More precisely, we study under what conditions BH does and does not exhibit adversarial robustness, we present a class of simple and easily implementable adversarial test-perturbation algorithms, and we perform computational experiments. With our algorithms, we demonstrate that there are conditions under which BH's control can be significantly broken with relatively few (even just one) test score perturbation(s), and provide non-asymptotic guarantees on the expected adversarial-adjustment to FDR. Our technical analysis involves a combinatorial reframing of the BH procedure as a ``balls into bins'' process, and drawing a connection to generalized ballot problems to facilitate an information-theoretic approach for deriving non-asymptotic lower bounds.

Main paper: 
 introduction: 
 Multiple testing has broad applications in drug discovery, forensics, candidate screening, anomaly detection, and in particular, machine learning. Indeed, recent works [5, 17, 27, 31] , in nonparametric outlier detection, out-of-distribution detection (OOD), and one-class classification have all adopted multiple testing methodology in developing principled decision rules with statistical guarantees. In fact, the Benjamini-Hochberg (BH) multiple testing procedure, widely used to control the false detection rate (FDR), is either used or modified in all these recent methods. Considering this FDR control could be relied upon in some critical (safety/security) contexts, for which false positives incur costs, we investigate its adversarial robustness.Adversarial corruption presents a challenge to statistical methodology, and is a modern-day concern due to not only the ease with which high volumes of data can now be accessed/processed but also the increasingly widespread use of statistical procedures. This threat poses vulnerabilities to machine learning tasks like OOD, which would aim to fortify security systems like fraud detection [5] .Manipulation of data and experimental results are common means by which incorrect conclusions can be reached. Worse, strategic perturbation can dramatically decrease the fidelity of the models and methods used. A burgeoning field of adversarial corruption has gained traction in recent years to meet this concern, most notably in the area of (deep) machine learning; see, for example, [26, 15, 19] . In this work we address adversarial corruption in hypothesis testing, specifically in the large-scale context in which the primary focus is on the aggregate metric: FDR. BH [6] is one of the most widely used multiple testing procedures, which upon input of a collection of p-values, outputs a rejection region ensuring that the FDR is no greater than a user-defined threshold q ∈ (0, 1). This control of FDR holds under independently generated p-values -as well as some restricted forms of dependency like positive regression dependent on a subset (PRDS) [7] -but it generally holds without strong assumptions on the alternative distributions. This degree of distributional robustness, however, could be said to come at the cost of adversarial robustness, as we show in this work.Although OOD methods [22, 12, 20, 21] are often complex and not always supported by statistical guarantees, conformal inference has made possible the use of one-class classifiers to generate conformal p-values for which OOD can now be conducted via multiple testing. This has led to the adoption of the BH procedure in OOD. Indeed, [5] leverages the FDR control afforded by BH over conformal p-values (shown to be PRDS) to test for outliers. More precisely, given a test set of observations for which we wish to identify as inliers or outliers (out of distribution), a conformal p-value is generated for each observation, which is then processed by BH to decide which are likely outliers. We refer the reader to [17, 27] for other recent works along this vein.In recent years, concerns have risen over the possibility of adversarial manipulation of statistical methodologies. This manipulation commonly occurs at the level of data collection and training, often invalidating the assumptions made regarding how data is drawn, but it can also occur at test time. There is a growing literature on adversarial robustness, which is concerned with securing statistical methods like (deep) machine learning [26, 15, 19] , linear regression [8] , M-estimation [9] , and online learning [25, 16, 1] . As well, a similar concept to the notion of adversarial robustness that we adopt in this paper is one the literature refers to as perturbation resilience. Generally speaking, a problem instance is called αperturbation resilient when despite a degree (parameterized by α) of perturbation to the instance, the optimal solution does not change. First introduced in [10] for combinatorial optimization (in particular, MAX-CUT), the concept has since also inspired research into devising resilient unsupervised learning, particularly in clustering [4, 3, 2] .With respect to the hypothesis testing literature, there are recent adversarial robust studies focused on simple [18] and sequential hypothesis testing [11] from a game theoretic perspective, in which protection of statistical power, risk, or sample size from corruption is of chief concern. Complementing the adversarial robust perspective are several distributionally robust studies, in which the data-generating distribution is known only to lie in a parametric family. Recent works include [11, 23, 14] which focus on test risk in single and sequential hypothesis testing settings employing uncertainty sets of distributions of fixed distance (e.g. Wasserstein, phi-divergence) for the null and alternative hypotheses. In contrast to these works, this paper is focused on FDR, not individual test risk. Furthermore, distributional robustness is not equivalent to the perturbation-robustness that this paper and other adversarial robust studies seek in general. Indeed, [29] shows that the BH procedure's FDR control exhibits a distributional robustness to possible dependence between null and non-null hypotheses. On the other hand, our work would illustrate that, distributional robustness aside, BH can lack adversarial robustness.Let N ∶= {1, . . . , N }, where N ∈ Z + , be a finite set for which each member i ∈ N denotes a binary hypothesis test deciding between a null and alternative hypothesis. Further, there exists a partitioning, N = H 0 ⊍ H 1 , such that the correct decision for test i ∈ N is either null if i ∈ H 0 , or alternative if i ∈ H 1 . Here, H 0 and H 1 are the (unknown) sets of null and alternative test indices, respectively; consequently, for any test i, the correct decision (i.e. set membership) is unknown to the decision maker. In fact, while the number of tests N is known (and large, on the order of thousands), neitherN 0 ∶= |H 0 | nor π 0 ∶= N0N is known to the decision maker, although π 0 ≥ 0.90 "is reasonable in most large-scale testing situations" -( [13] , p. 285).For each test i ∈ N , p-value p i ∈ [0, 1] is randomly generated (independent of all other p j , j ≠ i), which we model as a draw from either U (0, 1) when i ∈ H 0 (p i then referred to as a null p-value) or some alternative distribution P 1 i on [0, 1] when i ∈ H 1 (p i then referred to as an alternative p-value). A multiple-testing algorithm A takes as input a randomly generated collection of p-values p = {p i } i∈N and outputs for each test i a determination A(i) ∈ {0, 1} with A(i) = 1 iff the determination is to reject the null hypothesis (i.e., claim i ∈ H 1 ), or sometimes referred to as "make a discovery" for the i-th test. With a p ∶= ∑ i∈H0 A(i) denoting the number of false discoveries, and R p ∶= |A -1 (1)| denoting the number of rejections/discoveries made, we refer to F DP [A; p] ∶= ap Rp∨1 as the false detection proportion summarizing A's decisions on p-values p, where x∨y is shorthand for max(x, y) for any x, y ∈ R. We refer to its expectation with respect to the random generation of p as the false detection rate,F DR(A) ∶= E p F DP [A; p].In this work, we focus on the Benjamini Hochberg procedure, a widely-used multiple-testing algorithm.Given a collection of p-values p = {p i } i∈N and desired control level q ∈ (0, 1) to bound FDR, the BH procedure BH q operates as follows:1. The p-values are sorted in increasing order, p (1) ≤ p (2) ≤ . . . ≤ p (N ) .We model an (omniscient) adversary with knowledge of H 0 , H 1 , and that knows the decision maker's choice of control level q. The adversary receives the p-values p = (p i ) N i=1 after they are generated but before they are received by the decision maker, or before test time. Given the ability to perturb c ≥ 1 p-values, the adversary solves maxp ′ ∶∥p-p ′ ∥0≤c F DP [BH q ; p ′ ], (c-Perturb)where p ′ denotes the p-values derived from an adjusted collection of p-values p ′ = (p ′ i ) N i=1 . In words, the adversary finds the perturbation of at most c-many p-values before the execution of BH q so as to maximize the adversarially-adjusted false detection proportion F DP [BH q , p ′ ]. Perturbation of p-values is implicitly the result of data perturbation, and we refer to both Remark 4.6 and Section 5.2 for examples and experiments involving direct perturbation of data.While we assume omniscience for the adversary throughout, we will briefly address modifications in analysis for an oblivious adversary that has no knowledge of H 0 , nor H 1 . Indeed, our algorithms to be presented can be modified naturally for implementation by an oblivious adversary (see comments in Section 3); further, there is nearly equivalent performance when π 0 is large, as is typical. Hence, it is for the sake of brevity that we omit explicit analysis of the oblivious adversary.Intuitively, the effect of a small number of p-value perturbations becomes insignificant in settings where a large number of tests are rejected (see Theorem 3.2). This happens, for instance, when either the number of tests N , or the control level q, or the distance (e.g. KL-divergence) between the null and alternative distributions, is large. For this reason, we focus on results that are non-asymptotic in the number of tests N .In Section 3, we present the algorithm INCREASE-c that uses strategic increases to c null p-values to induce expansion of the BH rejection region. We also present an efficient, optimal algorithm MOVE-1 (Appendix Section 7.2) for the adversary's maximization of FDR with at most one (i.e. c = 1) p-value perturbation.In Section 4 we discuss the adversarial robustness of BH through study of the adversarial adjustments to FDR by the INCREASE-c algorithms, revealing where its control is and isn't adversarially robust.In Section 5 we provide accompanying numerical experiments on i.i.d. as well as PRDS p-values. 
the index: 
 i max ∶= max{i ∈ [0, N ] Z ∶ p (i) ≤ i q N } is identified, with p (0) ∶= 0.3. Reject the tests corresponding to the smallest i max p-values: p (1) , p (2) , . . . , p (imax) .BH q provides provable FDR control at the level of q without any assumptions on the alternative distributions {P 1 i } i∈H1 .Lemma 1.1 (Theorem 4.1 from [13] ). If every null p-value is super-uniform, equiv., p i ∼ P 0 i ≽ U (0, 1) for all i ∈ H 0 , and the collection is jointly independent, then regardless of the collection of alternative distributions {P 1 i } i∈H1 , F DR(BH q ) = π 0 q ≤ q, ∀q ∈ (0, 1).(EQUATIONRemark 1.2. In fact, the assumption of joint independence of the null p-values can be relaxed to a form of dependency known as PRDS -see [7] for this generalization of Lemma 1.1.In this section we will establish important notation for the discussions to follow. We reduce the real line to a collection of N + 1 "bins". N 0 and N 1 balls will each be assigned to one of these bins independently of each other, from discrete distributions that are specified in the next subsection. The main motivation for this reduction is to facilitate discussion of effective perturbations in Section 3, and for the technical analysis in Section 4.We partition the segment [0, 1] into N equiprobable segments that will be referred to as bins. We Rejection Count: Borrowing terminology from the classic balls into bins problem of probability theory [28] , this framework facilitates a re-interpretation of the random drawing of p-values as balls being randomly placed into an ordered collection of bins, enumerated 1 up to N + 1. Framed in this way, we see that BH q operates by identifying the rejection countdefine the i-th bin B i ∶= {p ∈ R ∶ (i-1) q N ≤ p < i q N }, for i = 1, . . . , N. What remains forms bin N +1, i.e., B N +1 ∶= {p ∈ R ∶ 1 ≥ p ≥ 1 -q}. For shorthand, we write B 1∶i ∶= ∪ i l=1 B l = {p ∈ R ∶ 0 ≤ p < i q N },EQUATIONwhich corresponds to the largest collection of consecutive bins 1, . . . , i that collectively contain precisely i balls, so that BH q rejects all tests with p-values lying in the first k bins. The case k = 0 corresponds to rejecting no tests. In fact, k is a stopping time under a filtration F that we define next.Filtration F = {F i } N i=0 : Let Ω ∶= [0, 1]N be a sample space with the classical Borel σalgebra B and (with slight abuse of notation) probability measure P ∶= (⊗ i∈H0 U (0, 1)) ⊗ (⊗ i∈H1 P 1 i ). We define a filtration beginning with F N ∶= σ(B N N +1 , B 0 N +1 ), and continuing inductively (N towards 0), let F i be the σ-algebra generated by {B N j } N +1 j=i+1 and {B 0 j } N +1 j=i+1 . In words, this filtration corresponds to what is cumulatively learned about the bin loads (null and total) upon examination of the bins in sequence starting with bin N + 1 and concluding with bin 1, assuming each observed p value comes with correct identification of whether or not i ∈ H 0 .We note the fact that for ℓ > i, it follows that E [B 0 1∶i i ||F ℓ ] = E [ B 0 1∶i i || B 0 1∶ℓ ℓ ] = B 0 1∶ℓ ℓ a.s., so that B 0 1∶N N , B 0 1∶N -1 N -1 , . . . , B 0 1∶11 form a martingale sequence adapted to the filtration. This fact will prove useful when combined with the optional stopping theorem to facilitate several results in this work.Under this lens, the adversary's (algorithmic) task reduces to reshuffling p-values among the bins, and in Section 3 we demonstrate there are indeed simple, tractable ways of performing this to manipulate BH, with potentially great effect on FDR control. The key insight is that there exist alternative stopping times that present alternative rejection counts (/regions) that can break FDR control.It in fact suffices for the c-many p-values to be placed in any bin i ≤ k+c . We remark that since an oblivious adversary cannot discern null-drawn from alternative-drawn in the collection p, INCREASEc as written is unimplementable in such a case. Hence, for the oblivious adversary, we modify INCREASE-c's criterion to B N N +1 ≥ c and have the oblivious adversary now take the c-many p-values uniformly at random from among the p-values in the (N + 1)-th bin. Intuitively, this modification for the oblivious adversary should yield nearly c null p-values being moved (on average) just as in the non-oblivious case, assuming the proportion of nulls among the B N N +1 -many p-values is high, as a typically large π 0 would entail.We conclude this section with a characterization of the average increase in FDR, denoted ∆ c that INCREASE-c induces. Theorem 3.2. Given c ≥ 1, let p +c denote the perturbed form of p that INCREASE-c produces. Then the adversarially-adjusted FDR induced by INCREASE-c isEFDP[BH q ; p +c ] = EFDP[BH q ; p] + ∆ c ,for any collection of alternative distributions {P 1 i } i∈H1 , whereEQUATIONIn Section 4 to follow, we provide analytical lower bounds for ∆ c as part of a discussion on BH's adversarial robustness. Section 5 presents computational experiments (e.g. Table 1 ). We remark that INCREASE-c is not optimal for all instances of c-Perturb; indeed, for c = 1, we present a provably optimal algorithm MOVE-1 in Appendix Section 7.2, which in contrast to INCREASE-1 sometimes induces a reduced rejection count. However, INCREASE-c remains a formidable adversarial procedure, as the results of Section 5 demonstrate on not only i.i.d. p-values but also PRDS conformal p-values.4 Theoretical Analysis: Performance Guarantees and Insights into Adversarial Robustness BH's FDR control -Lemma 1.1 -is (distributionally) robust in the sense that it holds no matter the alternative distributions {P 1 i } i∈H1 . However, as Theorem 3.2 indicates, the degree to which this control can withstand data perturbations at test time, i.e., its adversarial robustness, very much depends on {P 1 i } i∈H1 .Recalling Lemma 1.1, we may assume without loss of generality that no alternative distribution P 1 i stochastically dominates U (0, 1) (equiv., P 1 i ≽ U (0, 1)). That being said, the "degree" to which the alternative distributions {P 1 i } i∈H1 are (stoch.) dominated by the null distribution U (0, 1) (equiv.,EQUATION)) is critical. We briefly preview two regimes of special interest for which each of the next two subsections cover.High sub-uniformity: When the alternatives are sub-uniform P 1 i ≼ U (0, 1) for all i ∈ H 1 , and highly so, such that for all i ∈ H 1 it holds that P 1 i (p i < ϵ) ≈ 1 for some small ϵ > 0, then it follows that k is large and B 1∶ k should contain most alternative p-values. Consequently, in order for INCREAES-c to induce any sizeable increase to the FDR, the adversary will need to expand the BH rejection region significantly so as to introduce a commensurate number of nulls. Table 1 indicates c may need to be quite large to make a dent in FDR control. This message is made more precise in Theorem 4.1.Low sub-uniformity: As we will see, when the alternative p-values are barely dominated by U (0, 1), ∆ c can be rather large. In fact, in the special case that there is no dominance such that P 1 i = U (0, 1) for all i ∈ H 1 , a strikingly vulnerable state occurs with high probability. Indeed, in this case where nulls and alternatives are virtually indistinguishable, BH q (in fact any A) admits an FDR of π 0 whenever any rejections are made (i.e., E[FDP[BH q ; p]|| k ≥ 1] = π 0 ) so that BH q accordingly compensates by making no rejections with high probability (P ( k = 0) = 1 -q), which follows by the distributional robust control (1) from Lemma 1.1. But those times when k = 0 is precisely when INCREASE-c's simultaneous expansion of the rejection region and injection of nulls into this region is most damaging. That this event and other similarly vulnerable events occurs with high probability is the fault of the distributional robustness. This message is made rigorous in the forthcoming Theorem 4.5. 
adversarial algorithm: increase-c: 
 Throughout this section, we don the role of the adversary and study the c-Perturb problem, in which we are given q ∈ (0, 1), a realized collection p = {p i } i∈N (along with the labels of null or alternative for each p i ), and a budget c ≥ 1, and our task is to produce a perturbed collection p ′ . Toward this, we focus on a procedure called INCREASE-c that despite its sub-optimality (see Appendix Section 7.2) is intuitive and simple to execute; further, as theoretical and empirical analysis in sections 4 and 5 respectively show, it has strong performance in expectation.We begin by defining a random variable that is a stopping time adapted to F; given an integer c ≥ 1,EQUATIONand we choose to write k+ in place of k+1 .The interest in k+c is that if we moved any selection of c null p-values from bin N + 1 into bin k+c (in fact any bin i ≤ k+c ), then BH q would output a new, increased rejection count k+c . We formally study this in Section 4. In the meantime, we comment on the increase k+c -k, which is a difference between two stopping times It is easy to see that k+c -k ≥ c whenever B 0 N +1 ≥ c; hence, the increase in the rejection count is at least c, but possibly more. We provide a stronger lower bound on this increase by utilizing the ratio between the number B 0 k+2∶N of nulls not rejected by BH q and the number N -( k + 1) of bins left outside of the BH q rejection region in the case of no corruption. Computational experiments indicate comparable performance of this bound with those of simulations presented in Section 5's Table 1 EQUATIONfor any collection of alternative hypothesis distributions {P 1 i } i∈H1 .1. IF B 0 N +1 ≥ c, then move the largest c (ties broken arbitrarily) in the (N+1)-th bin to bin k+c . 
case of high sub-uniformity in alternatives {p: 
 1 i } i∈H1 If P 1 i ≼ U (0, 1) for all i ∈ H 1 , with P 1 i (p i < ϵ) ≈ 1for some small ϵ > 0, then it is clear that the number of alternatives rejected by BH q should be nearly the maximum number N 1 of correct rejections possible (i.e., B 1 1∶ k ≈ N 1 ) with high probability, limiting any potential impact of INCREASE-c. The following bounds are formulated to elaborate on such dynamics in this case of large separation between alternatives and nulls, for which the event[B 1 1∶c = N 1 ] has probability close to 1. Theorem 4.1. If c ≥ 1, then ∆ c ≤ P(B 1 1∶c = N 1 ) E[ c c + N 1 + B 0 1∶N1+c ∥B 0 N +1 ≥ c] + 1 -P(B 1 1∶c = N 1 )andEQUATIONIn words, for fixed c, as the alternative distributions concentrate more and more on 0, it follows that P(B 1 1∶c = N 1 ) ↑ 1, so that the effect ∆ c of INCREASE-c on BH's FDR is dampened. And this occurs despite the fact that the increase k+c -k in rejection count produced by INCREASE-c consists of mostly the introduction of nulls, and tends to a magnification of (N 1 + c) by at least a factor of the inverse of1 -E[ B 0 1∶N N ∥B 0 1∶N ≤ N 0 -c] ,which is straightforward to compute since B 0 1∶N ∼ Binom(N 0 , q). We refer the reader to Section 5's Table 1 for simulations illustrating the above.1 i } i∈H1In the study of this regime, we aim to demonstrate that the adversarial increase ∆ c can be rather large. We provide a lower bound L c on ∆ c that will be a function of parameters q, N, N 0 , as well as the alternative distributions {P 1 i } i∈H1 .In view of 5, the event [ k+c = c] is clearly of significance in the computation of ∆ c . In words, this event describes the case that the BH q rejection region captures nothing, and yet when the adversary successfully executes INCREASE-c the rejection will now capture only nulls -generating a false detection proportion of 1. Hence, we lower bound the adjustment ∆ c of Theorem 3.2 by lower-bounding the probability of this event.Our strategy: (1) first, characterize this probability under the special case that P1 i = U (0, 1) for all i ∈ H 1 ;(2) second, to handle when P 1 i ≼ U (0, 1) for some i ∈ H 1 , we translate the KL divergence of the resulting discrete, bin-assignment distributions into a bound via Pinsker's Inequality.The key to the first step will be to recognize that when P 1 i = U (0, 1) for all i ∈ H 1 , the vector of total loads (B N 1 , . . . , B N N ) is exchangeable (i.e., its law is invariant under permutations), given B N 1∶N . Indeed, exchangeability, combined with the generalized Ballot Theorem of [30] (∩ n r=1 [∑ r i=1 Bi < r]) = 1 -x n .Armed with Corollary 4.2, we can begin to estimate the probability laws of k and k+c .Corollary 4.3.If P 1 i = U (0, 1) for all i ∈ H 1 , then P( k = ℓ) = ( 1-q 1-q+ (N -ℓ)q N) ⋅ P(B N 1∶ℓ = ℓ) for ℓ = 0, . . . , N, where 0 0 = 1,and P(B N 1∶ℓ = ℓ) = ( N ℓ ) ( qℓ N ) ℓ (1 -qℓ N ) N -ℓ . If B 0 N +1 ≥ c, then P( k+c = c || B 0 N +1 ) = (1 -cq N ) N1 ⋅ (1 -c N ) N0-B 0 N +1 (1 - N0-B 0 N +1 N -c -N1q N -cq ).Next, we carry out the second step of our plan. Towards this, we make the following assumption. Assumption 4.4. Suppose the alternative p-values are independent and identically distributed, with common distribution P 1 , i.e., {p i } i∈H1 iid ∼ P 1 . We write δ ∶= (1 -q) -P 1 (p i ∈ B N +1 ), and δ j ∶= P 1 (p i ∈ B j ) -q N , and we assume that P 1 (p i ∈ B j ) > 0 for all j ∈ [N ], as well as P 1 (p i ∈ B ℓ∶N ) > 0 for arbitrary ℓ < N .This assumption not only reduces the notational burden (otherwise documenting N 1 many alternative distributions) but it also allows the leveraging of KL divergences between the different bin assignment distributions implied by the alternative P 1 versus the null U (0, 1). Theorem 4.5. Suppose Assumption 4.4. Then∆ c ≥ L c (q, N, N 0 , P 1 ) ∶= (1 - cq N -δ 1∶c ) N1 [(1 - c N ) N0 (1 -π c -V c )M c + Z c ]whereπ c (q, N, N 0 , P 1 ) ∶= N0+E[B 1 c+1∶N ||B 1 1∶c =0] N -c , E[B 1 c+1∶N ||B 1 1∶c = 0] = N 1 (N -c)q+N δ c+1∶N N -cq-N δ1∶c , V c (q, N, N 0 , P 1 ) ∶= √ ln2 2 E[B 1 c+1∶N ||B 1 1∶c = 0] D KL (P 1 , c), M c (q, N, N 0 ) ∶= N -cq N -c -E[(1 -c N ) -B 0 N +1 ; B 0 N +1 ≤ c -1],Z c (q, N, N 0 ) ∶= P(B 0N +1 ≥ c) (1 -c N ) N0-E[B 0 N +1 ||B 0 N +1 ≥c] E[B 0 N +1 ||B 0 N +1 ≥c] N -c D KL (P 1 , c) ∶= ∑ j 1 N -1 log ( q+δ-∑ c j=1 (q/N +δj )(N -1)(q/N +δj ) ) Remark 4.6. For a more concrete application/example, consider when the p-values {p i } i∈N are derived from z-scores {z i } i∈N via p i = P(Z > z i ), where Z ∼ N (0, 1), with null z-scores {z i } i∈H0 i.i.d. N (0, 1) and alternative z-scores {z i ∼ N (µ i 1 , 1)} i∈H1 (with all µ i 1 ≥ 0). Indeed, under this framework, we may view the µ i 1 as the distance between P 1 i and U (0, 1). Towards satisfying Assumption 4.4, we can assume throughout that there exists a nonnegative parameter µ 1 such that the alternative parameters (µ i 1 , σ i ) = (µ 1 , 1) for all i ∈ H 1 . Indeed, if every member of the collection {µ i 1 } i∈H1 is in reality only close to zero, then the forthcoming estimates (lower bounds) would provide close, conservative estimates when settingEQUATION) -q N . Intuitively, BH is adversarially robust (∆ c small) when the alternative distributions are "far" (µ 1 >> 0) from the theoretical null, and the opposite holds when they are "close" (µ 1 = 0) -see Figures 2 and 3 . 
simulations and data experiments: 
 In this section, we provide computations (performed in R and Python on a Macbook Air-M2 chip, 8GB memory, with no experiment time exceeding 5 minutes) to demonstrate the performance of the adversarial algorithm INCREASE-c. We demonstrate its performance through simulation on synthetic data to make comparisons to the theoretical estimates provided in Section 4. We then demonstrate its performance on a real-data experiment in outlier detection. (2) F DP [BH q ; p] and F DP [BH q ; p +c ] are calculated. In Figure 1 each of the 10 4 -many (F DP [BH q ; p], F DP [BH q ; p +c ]) pairs are plotted. As can be seen, the vast majority of the pairs satisfy F DP [BH q ; p +c ] > F DP [BH q ; p], and, further, all pairs lie above the horizontal line situated at the level of the BH control level π 0 ⋅ q = .09, i.e, F DP [BH q ; p +c ] > π 0 ⋅ q.In Table 1 , we present the effectiveness of INCREASE-c over ranges of corruption budget c and µ 1 from small to large. As can be seen, when µ 1 = 0, any amount of corruption budget c yields large post-corruption FDR E z F DP [BH q ; z +c ]. When µ 1 > 0 grows, however, the budget c must correspondingly grow in order for there to be nontrivial post-corruption FDR. Finally, we note that for any fixed c, the increase in rejection count k+c -k is on the average larger when µ 1 is larger. For experiments on non-i.i.d., PRDS p-values, we refer the interested reader to Section 5.2 or Appendix Section 7.4.In Figures 2 and 3 we illustrate how well the insights discussed in Section 4.2 capture the sensitivity of BH to adversarial perturbations when µ 1 is near 0. Specifically, for each q in the grid {.01, .02, . . . , .99}, we computed the difference F DP [BH q ; p + ] -F DP [BH q ; p] across 10 3 replications of the setup as in Section 5.1.1, with the average of this difference being an estimate of ∆ 1 . The plot of these ∆ 1 estimates with respect to q is then compared with the plot of our lower bound L 1 as a function of q.Figures 2 and 3 illustrate that the stricter the control, i.e., the smaller q is, the more effective INCREASE-c becomes. In fact, the bound indicates high vulnerability for the typical use case z +c ] and E[ k+c -k] (in parentheses) when all {µ i 1 } i∈H1 commonly equal some µ 1 ∈ {0, 1, 2} and N = 10 3 , q = 0.10, π 0 = 0.90, and all σ i = 1. of q ∈ (0, 0.10). On the other hand, as q increases, INCREASE-c's effect weakens; however, for increased q, the decision maker is accepting a higher FDR already.The Credit Card 2 dataset D ∶= {(X i , Y i )} n i=1 ⊆ R 30 × {0, 1} contains n = 284, 807 credit cardGiven a set of unlabeled transactions {X i } i∈S , where S ⊆ [n], the fraud detection task is to identify which members of S belong to n 1 , i.e., are fraudulent. We experiment with the BH-based, outlier detection method of [5] on this fraud detection task -specifically, we consider the false detection proportion of this method in the absence and presence of an adversary. The details of the experimental setup will now be discussed.We begin by training an unsupervised decision-tree-based algorithm on a training set. From the set n 0 of genuine transactions, we uniformly at random select a subset n train ⊆ n 0 of size 141, 758 to form a training set D train ∶= {X i } i∈ntrain upon which we train an isolation forest [24] ŝ ∶ R 30 → R + using the R library isotree3 , where, in principle, ŝ(X i ) returns an isolation depth that is smaller if Y i = 1 (i.e. is an outlier) and larger if Y i = 0 (i.e. is an inlier)Then for each of 10 2 simulations, we uniformly at random selected a subset ñcal ⊆ n 0 ∖ n train of size 141, 657 to form a calibration set Dcal ∶= {X i } i∈ñ cal of strictly genuine transactions. As well, we uniformly at random selected a subset ñtest,1 ⊆ n 1 of 100 fraudulent transactions to append to the 900 remaining genuine transactions comprising ñtest,0 ∶= n 0 ∖ n train ∖ ñcal to form a test set Dtest ∶= {X i } i∈ñtest , where ñtest ∶= ñtest,0 ∪ ñtest,1 . Finally, we transformed X i ↦ pi ∈ (0, 1)for each i ∈ ñtest via pi = 1+|{j∈ñ cal ∶ŝ(Xj )≤ŝ(Xi)}| |ñ cal |. The resulting collection of conformal p-values p ∶= (p i ) i∈ñtest is PRDS, as proven in [5] , and hence the FDR control of Lemma 1.1 holds (see [7] ). In contrast, upon executing INCREASE-c to generate a corresponding adversarially-perturbed collection p+c ∶= (p +c,i ) i∈ñtest , we obtain a collection for which BH's FDR control no longer holds.We executed BH on both p and p+c , with an execution providing the decision for each i ∈ ñtest whether to report it as genuine (null) or fraudulent (alternative). We report the average (over the 10 2 indicates, although the method of [5]  
conclusions: 
 This is the first work to consider adversarial corruption of the popular Benjamini Hochberg multiple testing procedure to break its FDR control. While BH may exhibit robustness when the alternative distributions are "far" from the null, it exhibits great sensitivity in practical cases when the alternatives are "closer" to the null. In such cases, with the modification of few p-values (as few as one), the attacker can increase the expected FDR well past the guarantee stipulated by the BH procedure. This study suggests some caution may be necessary when using BH, especially in safety-security settings. Numerical experiments support the analytical results. Finally, BH is but one member of the family of step-up multiple testing procedures, which generally entail rejection regions decided via a stopping time, which since our paper shows can be manipulated in the case of BH, it means other step-up procedures can be similarly prone.7 Appendix / supplemental material 7.1 Adversarial Algorithm:INCREASE-c Theorem 3.1. If c ≥ 1, then E[ k+c -k∥B 0 N +1 ≥ c] ≥ c -1 1 -E[ B 0 k+2∶N N -( k+1) || B 0 N +1 ≥ c] + 1 (4)for any collection of alternative hypothesis distributions {P 1 i } i∈H1 .Proof. Since the statement in the case of c = 1 is trivially true, we henceforth assume that c > 1. Recallk+c = max{i ∈ [c, N ] Z ∶ B 1∶i = i -c}. Let us define k0 +c ∶= max{i ∈ [c, N ] Z ∶ B 0 1∶i = i -(B 1 1∶ k + c)}.Then we begin by establishing that k+c ≥ k0 +c > k + 1. To see why this holds, we note thatB 0 1∶ k+1 = k -B 1 1∶ k+1 = k + 1 -(B 1 1∶ k+1 + 1) > k + 1 -(B 1 1∶ k+1 + c), and this implies k + 1 < k0 +c . Further, B 1∶ k0 +c = B 0 1∶ k0 +c + B 1 1∶ k0 +c = k0 +c -(B 1 1∶ k + c) + B 1 1∶ k0 +c = k0 +c -c + (B 1 1∶ k0 +c -B 1 1∶ k) ≥ k0 +c -c, which implies k+c ≥ k0 +c .Next, we justify the relationE ⎡ ⎢ ⎢ ⎢ ⎣ B 0 k+2∶N N -( k + 1) || k, B 1 1∶ k, [B 0 N +1 ≥ c] ⎤ ⎥ ⎥ ⎥ ⎦ = E ⎡ ⎢ ⎢ ⎢ ⎢ ⎣ B 0 k+2∶ k0 +c k0 +c -( k + 1) || k, B 1 1∶ k, [B 0 N +1 ≥ c] ⎤ ⎥ ⎥ ⎥ ⎥ ⎦ .It suffices to establish it for any fixed, joint realization of k, B 1 for such a fixed realization, and writeĒ [⋅] for E[⋅∥ k, B 1 1∶ k, [B 0 N +1 ≥ c]].The plan is to apply the Optional Stopping Theorem on a martingale sequence. To do so, let us form a (backwards-running) filtration: let F N be the sigma-algebra generated by the event [B 0 N +1 ≥ c] as well as the random variable B 0 N +1 , and let F i be the sigma-algebra generated by the event [B 0 N +1 ≥ c] as well as the random variables {B 0 j } N +1 j=i+1 . Then for any integers k, ℓ ∈ {N, N -1, . . . 1} such that ℓ > k,Ē [B 0 k+2∶[k∨( k+2)] || F ℓ ] = Ē [B 0 k+2∶[k∨( k+2)] ||B 0 k+2∶[ℓ∨( k+2)] ] = [k -( k + 1)] ∨ 1 [ℓ -( k + 1)] ∨ 1 B 0 k+2∶[ℓ∨( k+2)] ,whereB 0 k+2∶[ℓ∨( k+2)] ∈ F ℓ since B 0 k+2∶[ℓ∨( k+2)] = N 0 -B 0 N +1 -( k -B 1 1∶ k) -B 0 (ℓ+1)∨( k+3)∶N is ameasurable function of the random variables in F ℓ . In other words, the collection {B 0 k+2∶[k∨( k+2)][k-( k+1)]∨1 } forms a martingale under the filtration. As well, k0 +c is a stopping time. Hence, by the Optional Stopping Theorem,E ⎡ ⎢ ⎢ ⎢ ⎣ B 0 k+2∶N N -( k + 1) || k, B 1 1∶ k, [B 0 N +1 ≥ c] ⎤ ⎥ ⎥ ⎥ ⎦ = Ē ⎡ ⎢ ⎢ ⎢ ⎣ B 0 k+2∶N N -( k + 1) || [B 0 N +1 ≥ c] ⎤ ⎥ ⎥ ⎥ ⎦ = Ē ⎡ ⎢ ⎢ ⎢ ⎢ ⎣ B 0 k+2∶ k0 +c k0 +c -( k + 1) || [B 0 N +1 ≥ c] ⎤ ⎥ ⎥ ⎥ ⎥ ⎦ = E ⎡ ⎢ ⎢ ⎢ ⎢ ⎣ B 0 k+2∶ k0 +c k0 +c -( k + 1) || k, B 1 1∶ k, [B 0 N +1 ≥ c] ⎤ ⎥ ⎥ ⎥ ⎥ ⎦ .We note that the martingale property could be established even without the event [B 0 N +1 ≥ c] in the filtration but for the sake of forthcoming computations we have included it.Next we observe thatB 0 k+2∶ k0 +c + k -B 1 1∶ k = B 0 k+2∶ k0 +c + B 0 1∶ k = B 0 1∶ k0 +c = k0 +c -(B 1 1∶ k + c) ⇒ B 0 k+2∶ k0 +c = k0 +c -( k + c), we derive B 0 k+2∶ k0 +c k0 +c -( k + 1) = k0 +c -( k + c) k0 +c -( k + 1) = k0 +c -( k + 1) -c + 1 k0 +c -( k + 1) = 1 - c -1 k0 +c -( k + 1) ⇒ 0 < E ⎡ ⎢ ⎢ ⎢ ⎣ B 0 k+2∶N N -( k + 1) || k, B 1 1∶ k, [B 0 N +1 ≥ c] ⎤ ⎥ ⎥ ⎥ ⎦ = 1 -(c -1)E [ 1 k0 +c -( k + 1) || k, B 1 1∶ k, [B 0 N +1 ≥ c]] < 1 (*) ⇒ 1 E[ k0 +c -( k + 1) || k, B 1 1∶ k, [B 0 N +1 ≥ c]] ≤ E[ 1 k0 +c -( k + 1) || k, B 1 1∶ k, [B 0 N +1 ≥ c]] = 1 -E[ B 0 k+2∶N N -( k+1) || k, B 1 1∶ k, [B 0 N +1 ≥ c]] c -1 . Hence, c -1 1 -E[ B 0 k+2∶N N -( k+1) || k, B 1 1∶ k, [B 0 N +1 ≥ c]] +1 ≤ E[ k0 +c -k || k, B 1 1∶ k, [B 0 N +1 ≥ c]] ≤ E[ k+c -k || k, B 1 1∶ k, [B 0 N +1 ≥ c]] . It follows that c -1 1 -E[ B 0 k+2∶N N -( k+1) || B 0 N +1 ≥ c] + 1 = c -1 E[1 -E[ B 0 k+2∶N N -( k+1) || k, B 1 1∶ k, [B 0 N +1 ≥ c]] || B 0 N +1 ≥ c] + 1 ≤ E ⎡ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ c -1 1 -E[ B 0 k+2∶N N -( k+1) || k, B 1 1∶ k, [B 0 N +1 ≥ c]] || B 0 N +1 ≥ c ⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ + 1 ≤ E[ k+c -k || B 0 N +1 ≥ c] ,where we have used (conditional) Jensen's Inequality -valid because c > 1 and (*) ensures 1 -E[ B 0 k+2∶N N -( k+1) || k, B 1 1∶ k, [B 0 N +1 ≥ c]] > 0.Theorem 3.2. Given c ≥ 1, let p +c denote the perturbed form of p that INCREASE-c produces. Then the adversarially-adjusted FDR induced by INCREASE-c isEFDP[BH q ; p +c ] = EFDP[BH q ; p] + ∆ c ,for any collection of alternative distributions {P 1 i } i∈H1 , whereEQUATIONProof. We deriveEFDP[BH q ; p + ] = E ⎡ ⎢ ⎢ ⎢ ⎢ ⎣ B 0 1∶ k+c + c k+c ; B 0 N +1 ≥ c ⎤ ⎥ ⎥ ⎥ ⎥ ⎦ + E ⎡ ⎢ ⎢ ⎢ ⎣ B 0 1∶ k∨1 k ∨ 1 ; B 0 N +1 < c ⎤ ⎥ ⎥ ⎥ ⎦ = E ⎡ ⎢ ⎢ ⎢ ⎢ ⎣ B 0 1∶ k+c k+c ; B 0 N +1 ≥ c ⎤ ⎥ ⎥ ⎥ ⎥ ⎦ + E[ c k+c ; B 0 N +1 ≥ c] + E ⎡ ⎢ ⎢ ⎢ ⎣ B 0 1∶ k∨1 k ∨ 1 ; B 0 N +1 < c ⎤ ⎥ ⎥ ⎥ ⎦ = P(B 0 N +1 ≥ c) E[ B 0 1∶N N ||B 0 N +1 ≥ c] + E[ c k+c ; B 0 N +1 ≥ c] + P(B 0 N +1 < c) E[ B 0 1∶N N ||B 0 N +1 < c] = E[ B 0 1∶N N ] + E[ c k+c ; B 0 N +1 ≥ c] ,as desired. 
move-1: 
 MOVE-1 is an efficient, optimal algorithm for an (omniscient) adversary with budget c = 1. We begin with several small insights en route to describing MOVE-1 in full.EQUATIONProof. When B 1 1∶c = N 1 , it easily follows that k+c ≥ c + N 1 + B 0 1∶N1+c . This combined with Theorem 3.2 easily yields the first inequality.As for the second inequality, letk0 +c ∶= max{i ∈ [0, N ] Z ∶ B 0 1∶i = i -(N 1 + c)} ≥ N 1 + c > 0. Then E[ B 0 1∶N N ∥ B 0 N +1 ≥ c] = E ⎡ ⎢ ⎢ ⎢ ⎢ ⎣ B 0 1∶ k0 +c k0 +c ∥ B 0 N +1 ≥ c ⎤ ⎥ ⎥ ⎥ ⎥ ⎦ = E[ k0 +c -(N 1 + c) k0 +c ∥ B 0 N +1 ≥ c] = 1 -(N 1 + c)E [ 1 k0 +c ∥ B 0 N +1 ≥ c] implies that 1 E[ k0 +c ∥ B 0 N +1 ≥ c] ≤ E[ 1 k0 +c ∥ B 0 N +1 ≥ c] = 1 N 1 + c ⋅ (1 -E[ B 0 1∶N N ∥ B 0 N +1 ≥ c]) , so that E[ k+c ∥ B 0 N +1 ≥ c, B 1 1∶c = N 1 ] = E[ k0 +c ∥ B 0 N +1 ≥ c] ≥ N 1 + c 1 -E[ B 0 1∶N N ∥ B 0 N +1 ≥ c] ,since whenever B 1 1∶c = N 1 , it follows that k+c = k0 +c . Consequently, we derive N 1 + c 1 -E[ B 0 1∶N N ∥ B 0 N +1 ≥ c] ≤ E[ k+c ∥ B 0 N +1 ≥ c, B 1 1∶c = N 1 ] = E[ k+c ; B 1 1∶c = N 1 , B 0 N +1 ≥ c] P(B 1 1∶c = N 1 ) P(B 0 N +1 ≥ c) = E[ k+c ; B 0 N +1 ≥ c] -E[ k+c ; B 1 1∶c < N 1 , B 0 N +1 ≥ c] P(B 1 1∶c = N 1 ) P(B 0 N +1 ≥ c) = E[ k+c || B 0 N +1 ≥ c] 1 P(B 1 1∶c = N 1 ) -E[ k+c || B 1 1∶c < N 1 , B 0 N +1 ≥ c] P(B 1 1∶c < N 1 ) P(B 1 1∶c = N 1 ) , yielding P(B 1 1∶c = N 1 )⋅ N 1 + c 1 -E[ B 0 1∶N N ∥ B 0 N +1 ≥ c] +E [ k+c || B 1 1∶c < N 1 , B 0 N +1 ≥ c]⋅P (B 1 1∶c < N 1 ) ≤ E[ k+c || B 0 N +1 ≥ c] .(∩ n r=1 [∑ r i=1 Bi < r]) = 1 -x n .Proof. We will appeal to the following result of [30] :Hence, P( k+c = c || B 0 N +1 ) = P(B N 1∶c = 0 || B 0 N +1 ) P(∩ N j=c+1 [B N c+1∶j < j -1] || B N 1∶c = 0, B 0 N +1 ) = (1 - cq N ) N1 ⋅ (1 - c N ) N0-B 0 N +1 (1 - N 0 -B 0 N +1 N -c - N 1 q N -cq ) .Theorem 4.5. Suppose Assumption 4.4. Then∆ c ≥ L c (q, N, N 0 , P 1 ) ∶= (1 - cq N -δ 1∶c ) N1 [(1 - c N ) N0 (1 -π c -V c )M c + Z c ]where π c (q, N, N 0 , P1 ) ∶= N0+E[B 1 c+1∶N ||B 1 1∶c =0] N -c , E[B 1 c+1∶N ||B 1 1∶c = 0] = N 1 (N -c)q+N δ c+1∶N N -cq-N δ1∶c , V c (q, N, N 0 , P 1 ) ∶= √ ln2 2 E[B 1 c+1∶N ||B 1 1∶c = 0] D KL (P 1 , c), M c (q, N, N 0 ) ∶= N -cq N -c -E[(1 -c N ) -B 0 N +1 ; B 0 N +1 ≤ c -1], Z c (q, N, N 0 ) ∶= P(B 0 N +1 ≥ c) (1 -c N ) N0-E[B 0 N +1 ||B 0 N +1 ≥c] E[B 0 N +1 ||B 0 N +1 ≥c] N -c D KL (P 1 , c) ∶= ∑ j 1 N -1 log ( q+δ-∑ c j=1 (q/N +δj ) (N -1)(q/N +δj ) ) Proof. Observe that ∆ c = E[ c k+c ; B 0 N +1 ≥ c] ≥ P( k+c = c, B 0 N +1 ≥ c) . By Theorem 4.3, P( k+c = c, B 0 N +1 ≥ c) = E[P( k+c = c || B 0 N +1 ) ; B 0 N +1 ≥ c] = E ⎡ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ P(B 1∶c = 0 || B 0 N +1 ) ⋅ P(∩ N j=c+1 [B N c+1∶j < j -c] || [B N 1∶c = 0], B 0 N +1 ) (#) ; B 0 N +1 ≥ c ⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦where we now proceed to lower bound (#). The following discussion outlines how we proceed in the case of c = 1, but this is without loss of generality.Let B 0 N +1 and B 1 2∶N be given, along with the event [B N 1 = 0]. Then there are N 0 -B 0 N +1 many null p-values and B 1 2∶N many alternative p-values each of whose assignment to one of bin number 2, . . . , N remains stochastic. Let there be an arbitrary enumeration of these null p-values, upon which we let the collection of their bin-assignment random variables be denoted (α 0 i )N0-B 0 N +1 i=1. Let there also be an arbitrary enumeration of these alternative p-values, upon which we let the collection of their bin-assignment random variables be denoted (α1 i ) B 1 2∶Ni=1 . More precisely, α 0 i ∼ U nif ({2, . . . , N }), and α 1 i = j with probability q/N +δj q+δ-(q/N +δ1) , for j = 2, . . . , N . Finally, we will write P bins 1 for the joint distribution derived from the independent coupling of all the random variables (α 0 i )N0-B 0 N +1 i=1 and (α 1 i ) B 1 2∶Ni=1 . For contrast, let α1 i ∼ U nif ({2, . . . , N }), which expresses the random bin assignment of any alternative p-value to one of B 2 , . . . , B N given that B N 1 = 0, were P 1 = U (0, 1). Then P bins 0 , the joint derived from the independent coupling of (α 0 i )N0-B 0 N +1 i=1 and (α 1 i ) B 1 2∶Ni=1 , offers a useful counterpoint to P bins 
 
 Appendix: If p ′ = p, i.e., the sample statistics are left unperturbed, we obtain a false detection proportion ofF DP [BH q ; p] = B 0 1∶ k k .If it is possible to improve on this, it can be easily shown that in the case of c = 1 we must induce an altered rejection countEQUATIONhenceforth referred to as the (adversarially) adjusted rejection count resulting from the adversary's choice of p ′ . As it turns out, for the special case of c = 1, k′ ≠ k is necessary if a larger FDP is to be obtained, as the following lemma indicates.Lemma 7.1. If ||p -p ′ || 0 ≤ 1 and F DP [BH q ; p ′ ] ≠ F DP [BH q ; p] , then k′ ≠ k.Proof. We suppose the contrary for the sake of a contradiction, i.e., k′ = k. It follows that|{j ∈ N ∶ 0 ≤ p ′ j < k q N }| = k′ = k = |{j ∈ N ∶ 0 ≤ p j < k q N }|,and then byF DP [BH q ; p ′ ; ] ≠ F DP [BH q ; p] , it follows that |{j ∈ H 0 ∶ 0 ≤ p ′ j < k q N }| ≠ |{j ∈ H 0 ∶ 0 ≤ p j < k q N }|,Since ||p -p ′ || 0 ≤ 1, these two conclusions are at odds, presenting a contradiction.Considering Lemma 7.1, the adversary's p ′ ∈ [0, 1] N decision simplifies to deciding on an adjusted rejection count k′ from among a constrained set of integers consistent with the constraint ∥p ′ -p∥ 0 ≤ 1.An optimal k′ can indeed be larger or smaller than, or even equal to k. Hence, towards understanding this new search space, it suffices to characterize the set of feasible k′ that are larger than k, and smaller.Towards understanding how to increase the rejection count, we first highlight the following fact that follows immediately from (2).Lemma 7.2. If i ∈ { k + 1, . . . , N }, then B N 1∶i ≤ i -1. In particular, B N 1∶ k+1 = i -1. Proof. Suppose there exists i ∈ { k + 1, . . . , N } such that B N 1∶i > i -1. If B N 1∶i = i, then i > kpresents a contradiction of (2). However, proceeding with B N 1∶i ≥ i + 1, we see that there necessarily exists j ∈ {i + 1, . . . , N } for which B N 1∶j = j, for if this were not the case, then B N 1∶j ≥ j + 1 for all j ∈ {i + 1, . . . , N }, meaning B N 1∶N ≥ N + 1, yet another contradiction since there are only N p-values.Consequently, for k′ > k, we require a perturbed collection p ′ for which bin counts increase. This necessitates a decrease of a p-value -see Lemma 7.5 for details. Hence, we defineEQUATIONand note that these are precisely the positions i for which the addition of one (and only one) p-value into B 1∶i through the decrease of a p-value brings i into candidacy for the new rejection count -see equation ( 2).Proposition 7.3. L = { k′ ∶ k′ > k, ∥p -p ′ | 0 ≤ 1} Proof.To prove the first statement, we recall that by Lemma 7.2, if i > k, then B N 1∶i ≤ i -1. So, if i ≥ k + 1 with B N 1∶i < i -1, then no decrease of a single p-value could increase B N 1∶i to i (Lemma 7.5), precluding the possibility of k′ = i. In other words, no i ∉ L is achievable for the new rejection count k′ .On the other hand, say we enumerate L withi L > i L-1 > . . . > i 1 = k + 1.For the case of i L , k′ = i L is achieved if and only if a p-value is decreased from any bin B j with j > i ℓ to a bin B j-s where i L ≥ js ≥ 1. For the case of i ℓ , k′ = i ℓ is achieved if and only if a p-value is decreased from any bin B j with i ℓ+1 ≥ j > i ℓ to a bin B j-s where i ℓ ≥ js ≥ 1. Finally, all these movements of p-value just described are always possible for any given p = {p i } i∈N .Analogously, it follows that the increase of a p-value is necessary for the decrease of the rejection count -see Lemma 7.6, and we defineEQUATIONwhere i * ∶= 0 ∨ max{i ∈ {1, . . . , k -1} ∶ B N 1∶i = i + 1}. We note that R is precisely the set of all the achievable new (decreased) rejection counts k′ < k we could induce with the perturbation of a single p-value.Proposition 7.4. R = { k′ ∶ k > k′ , ∥p -p ′ | 0 ≤ 1}Proof. We begin by proving the first statement that k′ < k implies k′ ∈ R. To do so, we proceed in two steps. First we show that k ≥ i * , so that i * ≤ k′ ≤ k -1. Then we show that if k′ = i for some i ∈ {i * + 1, . . . , k -1} in which B N 1∶i ≠ i, we arrive at a contradiction. To see that k′ ≥ i * , if i * > k′ , then B N 1∶i * = i * + 1 becomes B N 1∶i * ≤ i * -1 by Lemma 7.2; in other words, the change in magnitude of B N 1∶i * is at least 2, which contradicts Lemma 7.6. Next, if i ∈ {i * + 1, . . . , k -1}, then B N 1∶i ≤ i by the definition of i * . This means if B N 1∶i ≠ i, then B N 1∶i < i, so that Lemma 7.6 indicates k′ could not be i.As for the second statement, let R be enumeratedi R > i R-1 > . . . > i 1 = i * .For the case of i R , k′ = i R is achieved if and only if a p-value is moved from bin B j with k ≥ j > i R to a bin B j+s > k. For R -1 ≥ r ≥ 2, by Lemma 7.6 it holds that k′ = i r is achieved if and only if a p-value is moved from a bin B j with i r+1 ≥ j > i r to a bin B j+s with j + s > k. Finally, for the case of i 1 , k′ = i 1 = i * is achieved if and only if a p-value is moved from B j with i * ≥ j to a B j+s with j + s > k. Finally, all these movements of p-values just described are always possible for any given p = {p i } i∈N .It follows that k′ ≠ k if and only if k′ ∈ L ⊍ R, so an efficient, optimal search procedure becomes straightforward. Informally, we iterate over the bins in reverse order, beginning with N + 1 and terminating with i * . At iteration (/bin number) i, if i ∈ L ⊍ R, then the trivial subproblem max p ′ ∶||p-p ′ ||0≤1, k′ =i F DP [BH q ; p ′ ] is solved; otherwise, nothing is done. Upon termination, the best FDP encountered is the answer. This is summarized in Theorem 7.7 Lemma 7.5 (Decreasing a p-value). Let p ′ be such that ||p -p ′ || 0 ≤ 1. If p ′ is the decrease of a single p-value in p from B j to B j-s , where j ∈ {2, . . . , N + 1} and 1 ≤ s ≤ j -1, then• i ∈ {1, . . . , j -s -1} ⇒ B N 1∶i remains constant• i ∈ {j -s, . . . , j -1} ⇒ B N 1∶i increases by 1• i ∈ {j, . . . , N + 1} ⇒ B N 1∶i remains constant. Lemma 7.6 (Increasing a p-value). Let p ′ be such that ||p -p ′ || 0 ≤ 1. If p ′ is the increase of a single p-value in p from B j to B j+s , where j ∈ {1, . . . , N } and 1 ≤ s ≤ N + 1 -j, then• i ∈ {1, . . . , j -1} ⇒ B N 1∶i remains constant • i ∈ {j, . . . , j + s -1} ⇒ B N 1∶idecreases by 1• i ∈ {j + s, . . . , N + 1} ⇒ B N 1∶i remains constant. Theorem 7.7 (MOVE-1). Let q ∈ (0, 1), p-values {p i } i∈N and sets H 0 , H 1 be given. For each i ∈ L ∪ R, letF DP i ∶= max p ′ ∶||p-p ′ ||0≤1, k′ =i F DP [BH q ; p ′ ].Thenmax p ′ ∶||p-p ′ ||0≤1 F DP [BH q ; p ′ ] = ( max i∈L∪R∪{ k} F DP i )This result explains that with one pass of the p-values from the largest to the smallest in the collection, we can ascertain the optimal perturbation p ′ . As the execution based on this result is straightforward, we omit the pseudocode for the sake of brevity.In Table 3 , we compare the average performance of INCREASE-1 against that of the optimal MOVE-1 over 10 4 simulations. The experiments followed the setup described in Remark 4.6, in which N = 10 3 p-values are derived from independently generated z-scores, with N 0 (= 900) null z-scores i.i.d. N (0, 1) and N 1 (= 100) alternative z-scores i.i.d. N (µ 1 , 1), for µ 1 = 1, 2. As Table 3 indicates, INCREASE-1 can provide nearly identical performance in adjustment to FDR; however, the perturbation distance ∥z -z ′ ∥ is on the average much greater than in MOVE-1. INCREASE-1 (in parentheses) when µ 1 = 0, 1, 2 and N = 10 3 , q = 0.10, π 0 = 0.90, and all σ i = 1.E z F DP [BH q ; z ′ ] Average ||z -z ′ || 1 µ 1 = 2 0.. By the chain rule for KL-divergence, we find Let a 0 i (respectively a 1 i ) denote the realization of the i-th null (respectively alternative) p-value's bin assignment. Then if we set E to be the collection of realizations (a 0 i )D KL (P bins 0 ||P bins 1 ) = N0-B 0 N +1 ∑ i=1 D KL (α 0 i ||α 0 i ) + B 1 2∶N ∑ i=1 D KL (α 1 i ||α 1 i ) = B 1 2∶N ∑ j 1 N -1 log ⎛ ⎜ ⎝ 1 N -1 q/N +δj q+δ-(q/N +δ1) ⎞ ⎟ ⎠ =∶D KL (P 1 ,1)N0-B 0 N +1 i=1and (a 1 i )B 1 2∶Ni=1 that are consistent with ∩ N j=2 [B 2∶j < j -1], we find Hence, for the case of general c, EQUATION(#) = E[P(∩ N j=c+1 [B N c+1∶j < j -c] || [B N 1∶c = 0], B 0 N +1 , B 1 c+1∶N ) || [B N 1∶c = 0], B 0 N +1 ] ≥ E ⎡ ⎢ ⎢ ⎢ ⎢ ⎣ (1 - N 0 -B 0 N +1 + B 1 c+1∶N N -c ) - √ ln2 2 B 1 c+1∶N D KL (P 1 , c) || [B N 1∶c = 0], B 0 N +1 ⎤ ⎥ ⎥ ⎥ ⎥ ⎦ (Pinsker's Inequality) ≥ 1 - N 0 -B 0 N +1 + E[B 1 c+1∶N ||B 1 1∶c = 0] N -c - √ ln2 2 E[B 1 c+1∶N ||B 1 1∶c = 0] D KL (P 1 , c).N +1 ≥ 1) (1 -cq N -δ 1∶c ) N1 ≥ E ⎡ ⎢ ⎢ ⎢ ⎢ ⎣ (1 - c N ) N0-B 0 N +1 ⎛ ⎝ 1 - N 0 -B 0 N +1 + E[B 1 c+1∶N ||B 1 1∶c = 0] N -c - √ ln2 2 E[B 1 2∶N ||B 1 1 = 0] D KL (P 1 , c) ⎞ ⎠ ; B 0 N +1 ≥ 1 ⎤ ⎥ ⎥ ⎥ ⎥ ⎦ = (1 - c N ) N0 ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ 1 - N 0 + E[B 1 c+1∶N ||B 1 1∶c = 0] N -c π(c,µ1) - √ ln2 2 E[B 1 c+1∶N ||B 1 1∶c = 0] D KL (P 1 , c) V (c,µ1) ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ E[(1 -c N ) -B 0 N +1 ; B 0 N +1 ≥ c] ( * * ) + E[(1 -c N ) N0-B 0 N +1 B 0 N +1 N -c ; B 0 N +1 ≥ c] ( * * * ), where of EFDP[BH q ; p +c ] on marginal conformal pvalues for outlier detection [5] , in terms of signal strength a and budget c. . This was performed for a ∈ {1, 1.5, 2, 2.5, 3}; a signal strength a = 1 corresponds to identical null and alternative distributions, while larger values of a make it easier to detect outliers. We set the fraction of outliers in each test set to π 1 = .1, so that a fraction π 0 = .90 of the observations are inliers in each data set.( * * ) = E ⎡ ⎢ ⎢ ⎢ ⎣ (1 - c N ) -B 0 N +1 ⎤ ⎥ ⎥ ⎥ ⎦ -E ⎡ ⎢ ⎢ ⎢ ⎣ (1 - c N ) -B 0 N +1 ; B 0 N +1 ≤ c -1 ⎤ ⎥ ⎥ ⎥ ⎦ = N -cq N -c -E ⎡ ⎢ ⎢ ⎢ ⎣ (1 -https://www.kaggle.com/datasets/mlg-ulb/creditcardfraudhttps://cran.r-project.org/web/packages/isotree/vignettes/An_Introduction_to_Isolation_Forests.html 


Decision: The paper investigates the conditions under which the Benjamini-Hochberg procedure is resilient to adversarial attacks.  In addition, the authors reframe the BH procedure as a "balls into bins" process as well as propose an algorithm to increase the rejection count. Finally, the authors also conducted experiments to support their findings.

All the reviewers had positive opinion on the paper, though in some cases this would come with low confidence as BH is not a well-known approach within the machine learning literature.  Nevertheless, good discussion was generated during the rebuttal period and on one hand several clarifications were provided or reviewers' questions were answered by the authors, and on the other hand the authors also agreed to add information on the final version of the paper that would make the final manuscript more accessible to everyone and on-par with other papers that are accepted in NeurIPS. Along these lines, in the final version of the paper clarifications are expected on matters like z-score, perturbation, norm choice, adversary power, etc.  Furthermore, the authors also performed experiments on a real-world dataset during the rebuttal period and these experimental results further elucidate the authors' approach as it was requested by the reviewers. I expect that these results will be included in the final version of the paper in one way or another.  For example, the authors may find it more reasonable to hint about these additional experimental results in the main text of their paper and provide full details in the supplementary material.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: - 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: 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.
limitations: limitations: I think some of the problem setup questions above would address some limitations of the work.
paper_summary: paper_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.
strength_weakness: strength_weakness: - 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: 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.
limitations: limitations: Same as Weaknesses.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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: questions: Please refer to the weaknesses.
limitations: 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.
paper_summary: paper_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.
strength_weakness: strength_weakness: ### 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: questions: None.
limitations: 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.

Comments: title: Clarification on Credit Card Experiment and the role of the adversary for L7r5
Adding Justifications/Explanations and Experiments
On a Real-World data experiment (Credit Card Fraud Detection)
Rebuttal Response
comment: *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.**
Dear Authors, 
Thank you for experimenting with the ``Credit Card" dataset. But I have one concern. If the experiments were conducted on a dataset containing both fraudulent and genuine transactions, what was the need to generate an altered list $p$ of p-values for varying $c$? Doesn't an adversary implicitly make the alterations in the fraudulent samples? Thus, changes in the fraudulent samples must have been mapped to the p-values and the z-scores. 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. 

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.
*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.*

**Response: Understood, thanks for the suggestion. We have now posted a "global" official comment above that discusses a real-world data experiment concerning credit card fraud detection. We are happy to include more real-world data experiments along these lines in the paper, if given the opportunity.**

*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.* 

**Response: Yes, we appreciate this suggestion and agree that this additional discussion surrounding the generality of attacking "step-up" procedures would be worthwile.**

*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.*

**Response: Yes, we are absolutely willing and able to add the justifications/explanations we offered to the review team on matters like z-score perturbation, norm choice, adversary's power, etc. And yes, we have performed one experiment on real-world data and offered it in the "global" official comment above, and we are willing to perform additional experiments on real-world data as suggested by L7r5 and yourself.**
Yes, we would be happy to add experiments with real-world data to the appendix. We have provided an experiment in our "global" official comment above, which serves as an example of things we could provide in the appendix, if given the opportunity to do so.

Thank you for your suggestion!
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.
Dear Authors,

There are still some pending clarification questions from at least two reviewers.  For example, would you commit to add experiments  on real-world data and explanations along the lines of what Reviewers L7r5 and pEvv request?

We need your input.
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.
Dear Authors, 
Thank you for your response. The rebuttal clarified the majority of my questions. 
- However, there remains an open concern (from all the reviewers) about how well the proposed method would perform with real-world data. Given the page limit of 9 pages, could the authors experiment with an MNIST/FashionMNIST OOD-classifier to demonstrate the efficacy of the INCREASE-c algorithm, as suggested by reviewer pEvv, and add it in the appendix? It will help strengthen the paper. 

-  This will also show the practical relevance of the proposed approach, as real-world adversarial attacks are more likely to target the raw input data.