Constructing Adversarial Examples for Vertical Federated Learning: Optimal Client Corruption through Multi-Armed Bandit
Authors: Duanyi YAO
Songze Li
Ye XUE
Jin Liu
Venue: ICLR 2024 poster (2024)
Keywords: Vertical Federated Learning
Adversarial Examples
Adaptive Client Corruption
Multi-armed Bandit
Primary area: societal considerations including fairness, safety, privacy
TL;DR: We propose a novel adversarial attack on inference of vertical federated learning, which selects the optimal client corruption pattern through solving a multi-armed bandit problem.

Abstract: Vertical federated learning (VFL), where each participating client holds a subset of data features, has found numerous applications in finance, healthcare, and IoT systems. However, adversarial attacks, particularly through the injection of adversarial examples (AEs), pose serious challenges to the security of VFL models. In this paper, we investigate such vulnerabilities through developing a novel attack to disrupt the VFL inference process, under a practical scenario where the adversary is able to *adaptively corrupt a subset of clients*. We formulate the problem of finding optimal attack strategies as an online optimization problem, which is decomposed into an inner problem of adversarial example generation (AEG) and an outer problem of corruption pattern selection (CPS). Specifically, we establish the equivalence between the formulated CPS problem and a multi-armed bandit (MAB) problem, and propose the Thompson sampling with Empirical maximum reward (E-TS) algorithm for the adversary to efficiently identify the optimal subset of clients for corruption. The key idea of E-TS is to introduce an estimation of the expected maximum reward for each arm, which helps to specify a small set of *competitive arms*, on which the exploration for the optimal arm is performed. This significantly reduces the exploration space, which otherwise can quickly become prohibitively large as the number of clients increases. We analytically characterize the regret bound of E-TS, and empirically demonstrate its capability of efficiently revealing the optimal corruption pattern with the highest attack success rate, under various datasets of popular VFL tasks.

Published as a conference paper at ICLR 2024
CONSTRUCTING ADVERSARIAL EXAMPLES FOR VER- TICAL FEDERATED LEARNING: OPTIMAL CLIENT COR- RUPTION THROUGH MULTI-ARMED BANDIT
Duanyi, Yao
Songze, Southeast University songzelilses edu.cn
HKUST
dyao8connect. ust..........
Ye, Xue
Jin, Liu HKUST(GZ))
Shenzhen Research Institute of Big Data, CUHK(SZ) xueye@cuhk, www.wuuwwwwkccc...ooooooooeeeaae en
jliu577econnect www.oonnnec..uustteeeoe edw.ttt-gzedd.c..
ABSTRACT
Vertical federated learning (VFL), where each participating client holds a subset of data features, has found numerous applications in finance, healthcare, and IoT systems. However, adversarial attacks, particularly through the injection of adversarial examples (AEs), pose serious challenges to the security of VFL models. In this paper, we investigate such vulnerabilities through developing a novel attack disrupt the VFL inference process, under practical scenario where the adversary is able to adaptively corrupt a subset of clients. We formulate the problem of finding optimal attack strategies as an online optimization problem, which is decomposed into an inner problem of adversarial example generation (AEG) and an outer problem of corruption pattern selection (CPS). Specifically, we establish the equivalence between the formulated CPS problem and multi- armed bandit (MAB) problem, and propose the Thompson sampling with Empirical maximum reward (E-TS) algorithm for the adversary to efficiently identify the optimal subset of clients for corruption. The key idea of E-TS is to introduce an estimation of the expected maximum reward for each arm, which helps specify a small set of competitive arms, on which the exploration for the optimal arm is performed. This significantly reduces the exploration space, which otherwise can quickly become prohibitively large as the number of clients increases. We analytically characterize the regret bound of E-TS, and empirically demonstrate its capability of efficiently revealing the optimal corruption pattern with the highest attack success rate, under various datasets of popular VFL tasks.
INTRODUCTION
Federated learning (FL) Li al. (2020) is distributed learning paradigm that enables multiple clients to collaboratively train and utilize a machine learning model without sharing their data. Conventionally, most FL research considers the Horizontal FL (HFL) setting, where clients hold different data samples with the same feature space. In contrast, vertical FL (VFL) tackles the secnarios where clients have identical samples but disjoint feature spaces. A typical VFL model comprises a top model maintained by server and multiple bottom models, one at each participating client. During the inference process, each client computes the local embedding of data features using bottom model and uploads it to the server through communication channel for further prediction. Due to its advantage of incorporating attributes from diverse information sources, VFL has found promising applications in healthcare systems Poirot et al. (2019), e-commerce platforms Mammen (2021), and financial systems Liu et al. (2022). ) VFL inference has also been applied to the Internet of Things (IoT) scenarios (also known as collaborative inference Liu et al. Ko et al. (2018)), where sensor data with distinct features are aggregated by a fusion center for further processing. A recent example is to utilize multi-modal image data from sensors for remote sensing image classification Shi et al. (2022).

---

Published as a conference paper at ICLR 2024
Despite its widespread applications, ML models have been shown vulnerable to adversarial examples (AEs) Goodfellow et al. (2014). which are modified inputs designed to cause model misclassification during the inference. Constructing AEs in the VFL setting presents unique challenges compared to the conventional MI. setting. Specifically, we consider a third-party adversary who can access, replay, and manipulate messages on the communication channel between client and the server. (For simplicity, we use client x to denote the communication channel between client z and the server throughout the paper). However, it can only corrupt subset of clients due to resource constraints, like computational and network bandwidth| Lesi et al. (2020); [Li and Tang (2018) 8); Wu et al. 2018). Also, the server's 's top model and the other uncorrupted clients' embeddings and models are unknown to the adversary. Under this setting, the adversary aims to generate AEs by adding manipulated perturbations to embeddings in the corrupted clients, such that the attack success rate (ASR) over a sequence of test samples is maximized. Prior works have proposed methods to generate AEs for VFL inference, for a fixed corruption pattern (i.c., the set of corrupted clients remains fixed throughout the attack). In Pang al. (2022), finite difference method proposed to generate adversarial dominating inputs, by perturbing the features of a fixed corrupted client, to control the inference result, regardless of the feature values of other clients; another work Qiu al. (2022) employed zeroth-order optimization (ZOO) to find the optimal perturbation on the uploaded embedding of a malicious client. Meanwhile, these attacks also make assumptions on certain prior knowledge the adversary, e.g., the adversary can obtain subset of complete test samples in advance.
In this paper, we consider an adversary who lacks prior knowledge on test data or VFL models, but can adaptively adjust its corruption pattern based on the effectiveness of the previous attacks, subject to a maximum number of clients that can be corrupted. For a VFL inference process of T rounds, we formulate the attack as an online optimization problem, over T corruption patterns, one for each inference round, and the embedding perturbations for the test samples in each round. To solve the problem, we first decompose it into two gub-problems: the inner adversarial examples generation (AEG) problem and the outer corruption pattern selection (CPS) problem. For the AEG problem with fixed corruption pattern, apply the natural evolution strategy (NES) to estimate the gradient for perturbation optimization. For the outer CPS problem, we establish its equivalence with arm selection in multi-armed bandit (MAB) problem, with the reward being the optimal ASR obtained from the AEG problem. Given the unique challenge that the total number of arms scale combinatorially with the number of clients, we propose a novel method named Thompson sampling with empirical maximum reward (E-TS), enabling the adversary to efficiently identify the optimal corruption pattern. The key idea is to limit the exploration within the competitive set, which is defined using the expected maximum reward of each arm. Compared with plain Thompson sampling (TS) for the MAB problem [Agrawal and Goyal (2112). E-TS additionally maintains the empirical maximum reward for each arm, which are utilized to estimate the underlying competitive arms, within which TS is executed to select the corruption pattern.
We theoretically characterize a regret bound of (N - D)0(1) (D-))0(1) + DO(log(T)) for the proposed E-TS algorithm, where N is the number of arms and D is the number of competitive arms. This demonstrates the advantage of E-TS over the plain TS, especially for a small number of competitive arms. We also empirically evaluate the performance the proposed attack on datasets with four major types of VFL tasks. In all experiments, the proposed attack uniformly dominates all baselines with fastest convergence to the optimal corruption pattern with the highest ASR. For the proposed attack, we further conduct extensive experiments evaluate its effectiveness under various combinations of system parameters and the design parameter, and common defense strategies against AEs.
PRELIMINARIES
VFL inference. A VFL system consists of a central server and M clients. Each client mn E possesses a subset of disjoint features Im and corresponding bottom model fms where M denotes the set (1..... M.. The central server maintains top model fo. Given test sample
[
X | [ x Mr) VFL inference is carried out in two stages. First, each client m computes a local embedding him = fm (xm) using its bottom model, and uploads it to the server through a communication channel for querying a label. In the second stage, the server aggregates the embeddings from all clients and computes the predicted result p = fo((h,....
har)) E R which
is a probability vector over e classes. The server broadcasts p to all the clients, who then obtain the predicted label ū(P), where (-)) returns the class with the highest probability. To enhance robustness
2

---

Published as a conference paper at ICLR 2024
against system impairments, such dropouts in embedding transmission, the system permits repeated queries for the same test sample, with a maximum limit of Q times. The inference process operates in an online mode, such that test samples are received continuously in streaming fashion.
Multi-armed bandit. A multi-armed bandit (MAB) problem consists of N arms. Each arm k E [N] corresponds random reward following an unknown distribution with mean j4k- The bandit is played for 7 rounds. In each round & E [T]. one of the N arms, denoted by k(tt, is pulled. The pulled arm yields random reward r'kce) (t) supported in the range [O, 1], which is i.i.d. from repeated plays of the same arm and observed by the player. The player must decide which arm to pull at each round t, i.e., k(t), based on the rewards in previous rounds, maximize the expected cumulative reward at round T, expressed as E|Ei=> (R(t)]. where (x(()) = Eg (race) (t)). Assuming there exists an optimal arm with the highest mean reward μ the problem is equivalent to minimizing the expected regret E[R(T)), which is defined as follows:
T
N the
E[R(T)] = E
Σ (
mK(1)) = E
(
LA
where (T) denotes the number of times pulling arm & in T rounds, and D =²" pi denotes the mean reward gap between the optimal arm and arm k.
3 THREAT MODEL
Goal of the adversary. We consider two types of attacks: targeted attack and untargeted attack. For the targeted attack with some target label you the adversary aims corrupt the samples whose original prediction is not you making the top model output 9 = Yvu For instance in lending application, the adversary might set yo to "lending" secure loan to unqualified customer. For the untargeted attack with some label yuu the adversary would like to corrupt the samples whose original prediction Yus making the top model output # Yu- Note that the conventional untargeted attack MMamoood let al.] (2021) is special case of the one considered here, when setting yu as the true label of the attacked samples.
The attack's effectiveness is measured by attack success rate (ASR), which is defined as ASR; Ei= (((p:))=y)) and ASR; Eis ((((p.))tu)) for targeted and untargeted attack, respectively, where is the number of samples to be attacked, p; is the probability vector of test sample i, and 1()) is the indicator function.
Metric.
Capability of the adversary. We consider an adversary as a third party in VFL inference, who can access, replay, and manipulate messages on the communication channel between two endpoints. This scenario stems from a con-in-thhe-middee (MITM) attack [onti et al. (2016); Wang et al. 2020). e.g.. Mallory can open letters sent from Bob to Alice and change or resend their contents before handing over the letter to Alice. In VFL inference, a communication channel is established between each client and the server, through which embeddings and predictions are exchanged. The adversary can choose to corrupt any specific channel, e.g., client (for simplicity, we use client to denote the communication channel between client r and the server). However, due to resource constraints like computational power and network bandwidth (see, Lesi et al. (2020); Wang et al. (2016); Wu et al. (2018), the adversary can corrupt at most C < M clients. Formally, for a test sample i, the adversary can perturb the embeddings of up to C clients, denoted h with |hr,al S C, to obtain h4,a such that ||h,, lo < (ub; - lb,), where ub, and 1b; represent the maximum and minimum values of the elements in h, respectively, and 3 E [0, 1] is the perturbation budget of some simple magnitude-based anomaly detector.
A Adaptive corruption. In the context of online inference, we focus on class of powerful adversaries capable of adaptively adjusting their corruption patterns. In each attack round, the adversary perturbs the embeddings in the corrupted clients for a batch of test samples. In subsequent attack rounds, the sets of corrupted clients can be adjusted subject to the constraint C, exploiting feedbacks on attack performance from previous rounds.
4 PROBLEM DEFINITION
The attack proceeds in T rounds. In each attack round E [T], the adversary seeks to perturb a batch of B' test samples following cornuption pattern C {a1, -
ac)) ac), where aj, j E [C]. denotes the
3

---

Published as a conference paper at ICLR 2024
index of the corrupted client. More precisely, given the embeddings of a test sample i [B*], denoted where h m E [M], represents the embedding vector of client m, we partition h into the adversarial part h = !ai............................. h , and the benign part h according to C The adversary crafts perturbation nf [n " ai with || S B(bb; (b2). and adds it to f to obtain an adversarial embedding h h + n; before submitting it to the server. Upon receiving hi, and h the server returns the prediction fo to all clients. After collecting all predictions of Ba adversarial embeddings. the adversary computes the ASR, ie., A((n C"; B²) Σ 2 (t) A( C² B+) Σn' 165(Fo(h (h for the untargeted attack with label yu--
as h = i......... M.Ml
for the targeted attack with target label Vo.
Ba
The adversary aims find the optimal set of corruption patterns [C=))=1> and the optimal set of perturbations {n]]= 17, for each sample E [B*] in attack round E [7]. thus maximizing the expected cumulative ASR over I attack rounds. We formulate this attack as online optimization problem in (2). Note that the expectation E, is taken over the randomness with the t-th attack round and the expectation E is taking over the randomness of all T rounds.
E2 max
A((7))E1 C B*)
2==1
{C' Ham
Σ1 B
(2)
s.t. |C'| = C, llmillo S B(ub - lbi), AA [T].
METHODOLOGY
To solve Problem 2
we decompose the above problem into an inner problem of adversarial example generation (AEG) and an outer problem of corruption pultern selection (CPS). We first specify the inner problem of AEG. At each round f, E [T]. with a fixed corruption pattern C', for each test sample i [B*], the adversary intends to find the optimal perturbation ny that minimizes some loss function, shown in 3 We consider the loss function L(n;; C*) I(fo(h",ai ht,)) Mo) for the targeted attack with target label ye. and L(n!: C*) = -I(fohhi, h(,)):
Vu) for the untargeted attack with label Ya. where 1(.) denotes the loss metric, such as cross-entropy margin loss.
Inner problem (AEG): min mink(
s.t. || I B(ub, - 1b.), Vi e [B*].
Then, we obtain the ASR of B² test samples, i..., =((( B"), obtained using optimal perturbations n [B*], from solving the problem AEG. As such, the outer problem of CPS can be cast into
E
ΣV
(a
Er (A* B)]
Outer problem (CPS):
min Ttm!
Σ B
(4)
s.t. =, Vt [T].
where a" is any positive constant. The inherent randomness of (C B¹) for a fixed C' arises from the random test samples and the random noises in the AE generation process.
5.1 AE GENERATION BY SOLVING THE AEG PROBLEM
To address the box-constraint inner AEG problem one might initially consider employing the projected gradient descent (PGD) method Madr et al. (2017) 77). However, our setting, the adversary can only access the value of the loss function and cannot directly obtain the gradient, thus necessitating the use of ZOO methods. The ZOO method iteratively seeks for the optimal variable, Each iteration typically commences with estimation of the current variable's gradient, followed by a gradient descent- based variable update. NES Ilyas et al. (2018). a type of ZOO method, not only estimates the gradient but also requires fewer queries than conventional finiteddifference methods. NES is thus
4

---

Published as a conference paper at ICLR 2024
Algorithm 1 E-TS for CPS
Initialization: vk E [N], fix = 0, 8x = 1, n 0,r%
0, 5/
2: for 1, do
3: if to then
4: Select fully explored arms to construct the set S = {k E [NV] ne 2 11-1)
5: Select the empirical best arm (t) m fig.
6:
Initialize Ex 9, add arms & E [N] which satisfy Gp 2 (2) to E
7: else
8:
Initialize set Ed [N].
9:
end if
10:
vk E E": Sample 02 ~ N (( Ōk).
Choose the arm k(t) = arg max, 02 and decide the compution pattern Ct k(t).
12:
Sample batch data [B'), play the arm k(t) as the corruption pattern in Algorithm 2 and
observe the reward Tk(() (t) from the attack result for the corrupted embedding h [h.......,,
Vi v 1.
[B".
Update TQ(()) = T((()) + 1, (R((1) Pe - Ōx(()
13:
maa
m A(E) (1((e) (t)}. (k(()) = (Mx(0)) PAAC))
PACO
R(())
Pk(())
14: end for
15: Output k(())....,,(7))
especially well-suited for addressing the AEG problem (3) in the VFL setting, where query times are inherently limited. In the process of AE generation using NES, the adversary samples Gaussian noises ô5 (0, J [m]. and adds them to the current variable n/ with some scaling parameter O. Then, the gradient estimation is given by
Lmni C*)
on Σ
8 (n) Cod;
After obtaining the gradient estimates, the adversary update 77 in PGD manner. The details of the AE generation process are provided in Algorithm 2 in Appendix A Note that the number of queries each test sample is limited to Q, therefore, the adversary can update the drafted perturbation most times for each sample.
5.2 THOMPSON SAMPLING WITH THE EMPIRICAL MAXIMUM REWARD FOR SOLVING THE CPS PROBLEM
To solve the CPS problem, we make a key observation that the outer problem in ( can be cast as an MAB problem. Specifically, picking C out of total M clients to corrupt results in N = =(r) possible corruption patterns, which are defined as N arms in the MAB problem. That is to say, there is bijection between the set of N arms and the optimization space of C' Therefore, we can transform
optimization variables {C*) in (4) into the selected arms round, i.e., (k(t) 1- At round
t, pulling an arm k(t) returns the reward (a(e)) (t) as the ASR, i.e., (t) = AC, B') E [o. 1].
We define the mean of the reward for arm k((() as E. (x(rr(o) = (4(()) (C'; BO]. Without
loss of generality, we assign the best arm the arm I with fixed positive mean μ41 > 0, which can be
considered as the positive value a* in (4). Finally, the CPS problem in is transformed into an
MAB problem, i.e., mi()(()))))), (M -Mcc))
E-TS algorithm. In our context, the adversary could face significant challenge as the exploration space N can become prohibitively large when engaging with hundreds of clients, which could result steep accumulation regret. To mitigate the issue from extensive exploration, we first introduce the following definition of the competitive arm.
Definition 1 (Competitive arm). An arm l is described as competitive arm when the expected
maximum reward larger than the best arm's mean, i.e., Å = Σr Ele max (t) 44 2 0, where rk max (t) max,etg (re(7)) Otherwise, it is non-competitive arm.
5

---

Published as a conference paper at ICLR 2024
Based the above definition, we propose Thompson sampling with Empirical maximum reward (E- TS) algorithm. The basic idea of E-TS is to restrict the exploration space within the set of competitive arms reduce accumulated regret. However, the ground-trun truth competitive arms cannot be accessed priori. Therefore, we propose to construct an empirical competitive set E' with estimated competitive at each round and restrict exploration within it. Estimating the competitive arms requires calculating the empirical best arm and empirical maximum reward defined as follows.
Definition (Empirical best arm and empirical maximum reward). An arm k is selected as the empirical best arm p (t) at round t, when & = arg maXkes" P (f), where (tx(t) is the estimated mean of arm k's reward at round I, St {k E [N] : mx(1)) 2 (x2 3. and ny (t) denotes the number of times pulling arm & in rounds. An arm k's empirical maximum reward (x((t (t) is computed by: ( (t) == 5x ri max (k))))))=)
Based Definitions 1 [nd we now able to present the key components of the E-TS algorithm. E-TS consists of two steps: first, for constructing an empirical competitive set Ex at round Ł, E-TS
estimates μl and Σr E(rr (t) using the mean of empirical best arm (t) (t) and the empirical T maximum reward (t), and obtains E { E [N] (x(() - (exmm (t) 2 0}. Second, while
performing TS to explore each arm, E-TS adopts a Gaussian prior (t) PeED to approximate
the distribution of the reward, where (1) is defined as (L) == E (A)T))))) In addition (x(()
to the above two steps, E-TS also involves to warm-up rounds, in which it simply executes TS across all arms. These warm-up rounds are designed facilitate a more accurate estimation each arm's reward mean and expected maximum reward. The complete algorithm is presented in Algorithm [ Remark 1. Previous work Gupta et al. (2021) leverages the upper bound (r,((r) of arm k's reward conditioned on obtaining reward r from pulling arm 7 (i.e., E(rr(t)// = -r] S (r)) to reduce the exploration space, where (r, is known constant. In contrast, the proposed E-TS algorithm does not require any prior information about reward upper bound, making it more practical.
6 REGRET ANALYSIS
In this section, we analyze the regret bound for the proposed E-TS algorithm. Prior to proof, we assume that each is pulled at least twice during the initial warm-up rounds. This assumption aligns with our analysis on the optimal choice of warm-up rounds detailed in Appendix CC6) Achieving this assumption is highly probable the number of warm-up rounds increases asymptotically (Agraaal and Goyal (2017). Additionally, an adversary can traverse all arms before implementing E-TS to ensure this prerequisite is met. To facilitate discussion, we first introduce two key lemmas. Then, we present the expected regret bound of E-TS algorithm in Theorem [ We defer all proof details of the lemmas and the theorem in Appendix
Lemma (Expected pulling times of a non-competitive arm). Under the above assumption, for non-competifive arm kes with Âgne_ J < O, the expected number of pulling times in T rounds, i,e., E[ (T)), is bounded by B(ux==(()) S O()..
Lemma 2 (Expected pulling times of a competitive but sub-optimal arm). Under the above assumption, the expected number of times pulling a competitive but sub-optimal arm kaau with
A ApauD1 2 in rounds is bounded as follows,
El (T)) = Pr(k(() = R. s.b (t) 2 N (log(T)))
Theorem 1 (Upper bound on expected regret of E-TS). Let D < N denote the number of competitive arms. Under the above assumption, the expected regret of the E-TS algorithm is upper bounded by DO(log(T)) + (N (1)
Proof sketch. We first demonstrate that the probability that pulling the optimal arm infrequent (i.e.. (t) < (t-1)] is bounded. Next, we categorize the sub-optimal arms into non-competitive arms and competitive but sub-optimal arms, and analyse their regret bound respectively. For compeetiti arm ke the probability of kt)) = = is bounded by the probability of selecting as the competitive arm, i.e., Pr(kee E.), which is further bounded in Lemma 1 On the other hand, for competitive

---

Published as a conference paper at ICLR 2024
but sub-optimal arm kad,, we further divide the analysis in two cases based on whether or not the optimal arm is included in Et. By combining the probability upper bounds in these two cases, we arrive at upper bound on the probability of k(t) k-suh in Lemma 2
Remark 2. In comparison with plain TS, our proposed E-TS holds a significant advantage in terms of limiting the expected number of times pulling a non-competitive arm, which reduced from (log(TT) to ((1).
7
EXPERIMENTAL EVALUATIONS
7.1 SETUP
The proposed attack is implemented using the PyTorch framework Paszke et al. (2017), and all experiments are executed a single machine equipped with four NVIDIA RTX 3090 GPUs. Each experiment is repeated for 10 trials, and the average values and their standard deviations are reported.
Datasets. We perform experiments on six datasets of distinct VFL tasks. 1) Tabular dataset: Credit Ych and Lien (2009) and Real-Sim Chang and Lin (201T), where data features are equally par- titioned across and 10 clients, respectively; 2) Computer vision (CV) dataset: FashionMNIST Xiao et al. (017) and CIFAR- R-0RR11 Krizhevsky et al. (2009), with features equally distributed across 7 and 8 clients, respectively; 3) Multi-view dataset: Caltech-7 Li et al. (2022), which consists of 6 views, each held by separate client; 4) Natural language dataset: IMDB Maas et al. (201I), where each complete movie review is partitioned among clients, each possessing a subset of sentences. More details about the datasets and model structures are provided in Appendix C.1
Baselines. We consider three baseline strategies for corruption pattern selection: 1) Fixed corruption pattern, where the adversary comupts fixed set of clients during the inference. For comparison, consider two fixed corruption patterns where one is the underlying optimal pattern with the highest ASR, and another is randomly selected at the beginning of the attack; 2) Random corruption (RC), where the adversary selects uniformly at random set of C' clients to corrupt in each attack round; and 3) Plain Thompson sampling (TS), where the adversary executes the plain TS to improve the corruption pattern selection.
Experimental parameters setting. The adversary can query the server for up to Q 2000 times per test sample. The number of warm-up rounds in E-TS to is set to 80 for FaShionMNIST, CIFAR-10. 10, and Caltech-7, 50 for Credit and Real-Sim, and 40 for IMDB. For the targeted attack, we set the target label to 7 for MNSS and CIFAR-10. 10, and 3 for Caltech-7. We measure the ASR over 30 test epochs, each comprising multiple attack rounds. our ablation study, we adjust one parameter at time, keeping the rest constant, with default settings of C 2, to 80, Q 2000, and B = 0.3.
7.2 RESULTS
We plot the ASR of targeted and untargeted attacks for different datasets in Figure I Note that the targeted and untargeted attacks are equivalent for Credit, Real-Sim, and IMDB with binary labels. We observe that uniformly across all datasets, the proposed E-TS method effectively attacks VFL models with an ASR of 38% 99% for targeted attack and 41% ~ 99% for untargeted attack. For each attack, we observe significant gap in ASR between the best and sub-optimal corruption patterns, demonstrating the significance of corruption pattern selection. The RC baseline exhibits a stable, yet sub-optimal ASR performance, it does not leverage any information from historical ASRs. In sharp contrast, the performance of both TS and E-TS converge to that of the best corruption pattern. Notably, thanks to the estimation of empirical maximum reward, the E-TS algorithm efficiently narrows down the exploration space, achieving much faster and more stable convergence than TS.
Ablation study. We evaluate the effects of system parameters, including corruption constraint C, query budget Q, and perturbation budget 8, and the design parameter, the number of warm-up up rounds to, on the performance of the proposed attack. Besides, we test the attack performance under a larger search space. As shown in Figure (a)) ASR increases more clients are corrupted, and E-TS consistently outperforms random corruption. is illustrated in Figure 3)b) that is critical to select the appropriate number of warm-up rounds to at the beginning of E-TS. When to is too small, i.e., to = 20, it leads to an inaccurate estimate of the empirical competitive set which may exclude the best arm, causing E-TS to converge to = 200 or 1000, the advantage over plain TS diminishes. That is, one needs to optimize to to find the optimal arm with the fastest speed. Figure 3) and (d) show that ASR generally increases with
sub-optimal arm. However, if to is too large, i.e.,
7

---

Published as a conference paper at ICLR 2024
FasHionMNIST
CIFAR-10 artack roundshee spoch)
roundshest spoch)
28
4 30-
Cl
Test sparep
Test apoth
Text
(6) Targeted (3 0.15)
(b) Unlargeted (13 0.1)
(c) Targeted @ 0.08)
(d) Untargeted (8 0.08)
Credit
Real-Sim
Caltech
(30 sttack roundshhest spoch)
277 allack roundhhest spoch)
10
A38070
Clend
30
15
20
25
30
(e) B
0.3
(1 / 0.3
(g) Targeted (8 = 0.3)
(bi Untargeted (B = 0.3)
IMDB spuch)
Defense
strategies)
80
Ro defertn
Diapnul
Rundemiedd smootleg
70-
20
Nomber cormupted clientsiC)
Number corrupted dientsic)
① B = 0.05
Targeted 0.3)
Untargeted
Figure 1: Attack performance on six datasets of distinct VFL tasks.
Figure 2: Attack performance on FashionMNIST under different defense strategies.
55-
45
53
40-
66-
13
02 0.5 0. Perturbatton basgettj))
Number corrupted clientsiC)
Tast sooch
Query budgett0)
(a) Cormpttio constraint (C) (b) Number of warm up rounds (tg)
(c) Query budget (Q)
(d) Petturbation budget (3)
Figure 3: Targeted attack performance FashionMNIST using different parameters.
larger Q and B. Nevertheless, after reaching 0.3, increasing perturbation budget has negligible effect on improving ASR. F that E-TS consistently outperforms baselines in larger exploration
space, i.e., when there are (29) 120, (10) 560, (29) 378, and (29) 3276 choices. Notably, this performance gap between E-TS and TS becomes even more pronounced when the exploration space is expanded, demonstrating its effectiveness in handling larger exploration spaces. More experimental results of corrupting different numbers of clients on other datasets are provided in Appendix We also investigated the dynamics of arm selection and empirical competitive set in TS and E-TS (in Appendix C.3) minimum query budget and corruption channels to achieve 50% ASR (in Appendix C.4.. the E TS performance in large exploration spaces (in Appendix C.5) and
the optimal choice the warm-up round (ni Appendix C.6).
Defenses.
We further evaluate the effectiveness the proposed attack under the following common defense strategies. Randomized smoothing (Cohen et al. (2019)): The main idea is to smooth out the decision boundary of a classifier, such that it's less sensitive to small perturbations in the input data. To construct smooth VFL classifier, Gaussian noises added to clients' embeddings, which are then processed by the top model to make a prediction. The final prediction obtained by majority voting over 100 such trials; Dropout (Quu al. (2022)): A dropout layer is added after
8

---

Published as a conference paper at ICLR 2024
60-
40
20.
19
19
50
25
13
Coruut Zout of 16 clients
(b) Corrupt 3 out of 16 clients
(c) Corrupt 2 out of 28 clients
(d) Corrupt out of clients
Figure 4: Targeted attack performance on FashionMNIST with larger search space
each activation layer in the server's top model improve the robustness. Here, we set the dropout rate to 0.3; Manifold projection (Meng and Chen (017); Lindgvist et al. (208)); An autoencoder incorporated into the model as a pre-procese preccessssing step before the top model. During training, the autoencoder is trained using clean embeddings and designed to reconstruct the original embeddings. During inference, the clients' embeddings are first processed using the autoencoder before being passed to the top model for prediction.
As shown in Figure 2 for a targeted attack with 3 = 0.3, the ASR of the proposed attack reduces under all considered defenses; for untargeted attack when 8 = 0.1, the ASRs experience marginal reductions under the randomized smoothing and dropout defenses, but significant drops of 35% ~ 72% in the ASR under manifold projection. The advantage of manifold projection can be attributed to the learning of the manifold structure and the transformation of adversarial embeddings into clean embeddings. Overall, while manifold projection exhibits the strongest capability in defending the proposed attack, it fails to completely eliminate all AEs.
RELATED WORK
AE generation for MI. models. AE generation methods be generally classified into two categories: white-box and black-box settings. While the former assumes the adversary knows full knowledge of model parameters and architectures, the latter assumes no prior knowledge of either the models or training data. Our work is concerned with a black-box setting, which is typically addressed query-based solutions. trassfer-based methods Papernot al. (2016); Liu et al. (2016) generate AEs using a substitute model, which is trained either by querying the model's s output or using subset of training data. Query-based methods Bhhaooj et al. (2018); Chen et al. (2017) optimize AEs utilizing gradient information, which is estimated through the queried outputs. One classical example is the ZOO attack Chen et al. (201)). which employs zeroth-order stochastic coordinate descent for gradient estimation.
using either transfer-basee
MAB algorithms. Multiple classical algorithms, such as e-greedy Sutton and Barto 2018). Upper Confidence Bounds (UCB) Lai et al. (1955); Garivier and Cappé (201)), and Thompson sampling Agrawal and Goyal (0122), are proposed to solve the MAB problem. Recent advancements have proposed variants of MAB under different settings, leveraging additional information to minimize the exploration. These include correlated arm bandit Gupta et al. (202T). contextual bandit Singh et al. (2020); Chu et al. (201 and combinatorial handit al. (2013). However, their application in the context of adversarial attacks, particularly in VFL, remains largely unexplored.
CONCLUSION
We propose novel attack, for adversary who adaptively corrupt certain number of com- munication channels between a client and the server, to generate AEs for inference of VFL models. Specifically, we formulate the problem of adaptive AE generation as online optimization problem, and decompose it into an adversarial example generation (AEG) problem and corruption pattern selection (CPS) problem. We transform the CPS problem into an MAB problem, and propose novel Thompson Sampling with Empirical maximum reward (E-TS) algorithm to find the optimal corruption pattern. We theoretically characterize the expected regret bound E-TS, and perform extensive experiments on various VFL tasks to substantiate the effectiveness of our proposed attack.
ACKNOWLEDGMENT
This work in part supported by the National Nature Science Foundation of China (NSFC) Grant 621 62106057.

---

Published as a conference paper at ICLR 2024
REFERENCES
Tian Li, Anit Kumar Sahu, Ameet Talwalkar, and Virginia Smith. Federated learning: Challenges, methods, and future directions. IEEE signal processing magazine, 3703):50-60, 2020.
Maarten Poirot, Praneeth Vepakomma, Ken Chang, Jayashree Kalpathy-Cramer, Rajiv Gupta, and Ramesh Raskar. Split learning for collaborative deep learning in healthcare. arXiv preprint arXiv:1912.12115, 2019.
Priyanka Mary Mammen. Federated learning: opportunities and challenges. arXiv preprint arXiv:2101.05528, 2021.
Yang Liu, Yan Kang, Tianyuan Zou, Yanhong Pu, Yuanqin He, Xiaozhou Ye, Ye Ouyang, Ya- Ya-Qin Zhang, and Qiang Yang. Vertical federated learning. arXiv preprini arXiv:2211 (tt.::2211.228111 2022.
Jing Liu, Chulin Xie, Oluwasanmi O Koyejo, and Bo Li. Copur: Certifiably robust collaborative inference via feature purification. In Advances in Neural Information Processing Systems.
Jong Hwan Ko, Taesik Na, Mohammad Faisal Amir, and Saibal Mukhopadhyay. Edge-host partition- ing of deep neural networks with feature space encoding for resource- consreeconttr internet-of-thingg platforms. In 2018 15th IEEE International Conference on Advanced Video and Signal Based Surveillance (AVSS), pages 1-6. IEEE, 2018
Cheng Shi, Yenan Dang, Li Fang, Minghua Zhao, Zhiyong Lv, Qiguang Miao, and Chi-Man Pun. Multifeature collaborative adversarial attack in multimodal remote sensing image classification. IEEE Transactions on Geoscience and Remote Sensing, 60:1-15, 2022.
Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. arXiv preprint 1XI::1412.6672. 2014.
Vuk Lesi, Ilija Jovanov, and Miroslav Pajic. Integrating security in resource-constrained cyber- physical systems. ACM Transactions Cyber-Physical Systems, 4(3):1-27, 2020.
Fangfei Li and Yang Tang. False data injection attack for constraint. IEEE transactions on cybernetics, 50(2):729-738, 2018.
systems with resource
Guangyu Wu, Jian Sun, and Jie Chen. Optimal data injection attacks in cyber-physical systems. IEEE transactions on cybernetics, 48( (2):11):322222 -31322 2018.
Qi Pang, Yuanyuan Yuan, and Shuai Wang. Attacking vertical collaborative learning system using adversarial dominating inputs. arXiv preprint S.XXv:22011.22775 2022.
Pengyu Qiu, Xuhong Zhang, Shouling Ji, Changjiang Li, Yuwen Pu, Xing Yang, and Ting Wang. Hijack vertical federated learning models with adversarial embedding. arXiv preprint arXiv:2212.00322, 2022.
Shipra Agrawal and Navin Goyal. Analysis of thompson sampling for the multi-armed bandit problem. In Conference on learning theory, pages 39-1. JMLR Workshop and Conference Proceedings, 2012.
Kaleel Mahmood, Rigel Mahmood, Ethan Rathbun, and Marten van Dijk. Back in black: A comparative evaluation of recent state-of-the-art black-bor attacks. IEEE Access, 1019, 2021.
Mauro Conti, Nicola Dragoni, and Viktor Lesyk. A survey of man in the middle attacks. IEEE communications surveys & tutorials, 1803):207-2251, 2016.
Derui Wang, Chaoran Li, Sheng Wen, Surya Nepal, and Yang Xiang. Man-in-the-middle attacks against machine learning classifiers via malicious generative models. IEEE Transactions on Dependable and Secure Computing, 18(5):2074-0077, 2020.
Dong Wang, Zidong Wang, Bo Shen, Fuad E Alsaadi, and Tasawar Hayat. Recent advances filtering and control for cyber-physical systems under security and resource constraints. Journal of the Franklin Institute, 353(1 -222411-2466, 2016.
10

---

Published as a conference paper at ICLR 2024
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. arXiv preprint arXiv: 707.00000,, 2017.
Andrew Ilyas, Logan Engstrom, Anish Athalye, and Jessy Lin. Black-box adversarial attacks with limited queries and information. In International Conference Machine Learning, pages 2137-2146. PMLR, 2018.
Samarth Gupta, Shreyas Chaudhari, Gauri Joshi, and Osman Yagan. Multi arme bandits with correlated arms. IEEE Transactions on Information Theory, 67(10):6711-773 2021.
Shipra Agrawal and Navin Goyal. Near-optimal regret bounds for thompson sampling. Journal of the ACM (JACM), 64(5):1-24, 2017.
Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in pytorch. 2017.
I-Cheng Yeh and Che-hui Lien. The comparisons of data mining techniques for the predictive accuracy of probability of default of credit card clients. Expert systems with applications, 36(2): 2473-2480, 2009.
Chih-Chung Chang and Chih-Jen Lin. Libsvm: library for support vector machines. ACM transactions on intelligent systems and technology (TIST), 2(3): 2011.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: novel image dataset for benchmarking machine learning algorithms. arXiv preprint arXiv:1708.07747, 2017.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Fei-Fei Li, Marco Andreeto, Mare' Aurelio Ranzato, and Pietro Perona. Caltech 101, April 2022.
Andrew L. Maas, Raymond Daly, Peter Pham, Dan Huang, Andrew Y. Ng, and Christopher Potts. Learning word vectors for sentiment analysis. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies, pages 142-150, Portland, Oregon, USA, June 2011. Association for Computational Linguistics. URL http:
//www. www.accwwb..rgg////o wwwp:a/w.eebboorr//atttoooo///--
Jeremy Cohen, Flan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. international conference on machine learning, pages 1310-1320. PMLR, 2019.
Dongyu Meng and Hao Chen. Magnet: a two-pronged defense against adversarial examples. In Proceedings of the 2017 ACM SIGSAC conference on computer and communications security. pages 135-147, 2017.
Blerta Lindqyist, Shridatt Sugrim, and Rauf Izmailov. Autogan: Robust classifier against adversarial attacks. arXiv preprint /rXiv:/8/2.033: 18/2003405 2018.
Nicolas Papernot, Patrick McDaniel, and Ian Goodfellow. Transferability in machine learning: from phenomena to black-box attacks using adversarial samples. arXiv preprint arXiv:1605.00 1605.07277, 2016.
Yanpei Liu, Xinyun Chen, Chang Liu, and Dawn Song. Delving into transferable adversarial examples and black-box attacks. arXiv preprint arXiv:1611.027700 2016.
Arjun Nitin Bhagoji, Warren He, Bo Li, and Dawn Song. Practical black-box attacks on deep neural networks using efficient query mechanisms. In Proceedings of the European Conference on Computer Vision (ECCV), pages 164- 2018
Pin- Yu Chen, Huan Zhang, Yash Sharma, Jinfeng Yi, and Cho-Jui Hsieh. Zoo: Zeroth order optimization based black-box attacks to deep neural networks without training substitute models. In Proceedings of the 10th ACM workshop on artificial intelligence and security, pages 15-26, 2017.
11

---

Published as a conference paper at ICLR 2024
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Tze Leung Lai, Herbert Robbins, et al. Asymptotically efficient adaptive allocation rules. Advances in applied mathematics, 6 6(1):4-22, 1985.
Aurélien Garivier and Olivier Cappé. The kl-ucb algorithm for bounded stochastic bandits and beyond. In Proceedings of the 24th annual conference on learning theory, pages 359-376. JMLR Workshop and Conference Proceedings, 2011.
Rahul Singh, Fang Liu, Xin Liu, and Ness Shroff. Contextual bandits with side-observations. arXiv preprint (xXiv:2006.03955 2020.
Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandits with linear payoff functions. In Proceedings of the Fourteenth International Conference Artificial Intelligence and Statistics, pages
JMLR Workshop and Conference Proceedings, 2011.
Wei Chen, Yajun Wang, and Yang Yuan. Combinatorial multi multi-armed bandit: General framework and applications. International conference on machine learning. pages 151-159 PMLR, 2013.
12

---

Published as a conference paper at ICLR 2024
APPENDIX
A AE GENERATION ALGORITHM
The function (6) is used estimate the gradient from the Natural evolution strategy (NES) Ilyas et al. (2018). The detailed method for zeroth-order AE generation in VFL is presented in Algorithm 2 In step 6, we use antithetic sampling to generate noise for efficiency.
C+)
on Σ L (n: + tō,
(6)
Algorithm/ 2 Zeroth-order AE generation in VFL
1: Input: Batch [B'). adversarial embedding a benign embedding hi [B'). corruption
pattern C², learning rate ir, the sample size of the Gaussion noise n, the perturbation budget 3 query budget Q. and the embedding range [lb;, ubi]. [B*]
2: Initialization: m/. = 0, m E [M] nn [ Mhaol counter
3: for i E {B'c) do
4: for E [ do
5: Clamp the perturbation to ||v] ll x0 S 3(bb; - 1b:).
6: Make query to the server with adversarial embedding hi, h - n! if the attack
7:
successful then
8:
Initiate noise vectors d, N(O, E {I, } another zhB noise vectors are
8, = 6, E .u.......
9:
Clamp the perturbation ||n) + 8, I B(ub, 16.). where j E [n]. Make queries to the server and estimate the gradient G through function 6 Update the perturbation n) =n Ir G.
10:
11:
else
13:
Break the loop, store v/ and
1.
14:
end if
15:
end for
16:
end for
17:
Clamp |/ B(ub; 1b.), i [B*), return nf and the attack success rate Br.
B PROOFS IN SECTION REGRET ANALYSIS
In this section, we provide detailed proofs of lemmas and the theorem in Section Regret Analysis of our paper. We initiate the proof procedure by establishing the definitions for two key events and three supporting facts, intended to streamline the proof process.
Fact 1 (Hoeffding's inequality). Let X1, X1...., X, be independent i..dd random variables bounded in Ja, bl, then for any 5 > 0, we have
Σ X;
22n82
Pr
E(Xi) 20 2
(b-a)²
Fact 2 (Abramowitz And Stegun 1964). For a Gaussian distributed random variable Z with mean m and variance o², for any 2,
7-3 < Pr(l ml > 20) - 2/22
Fact 3 (Concentration Bounds). Let Xy...., Xn be 0-I-valued random variables. Suppose that there are 0 & 6, & 1, for & i & such that, for every set S S [n], Pr [Nes =1] & II 8, Let 8 (1/n) En 8, Then, for any 7 such that â & y 1, have Pr 12 X; 7m| < ( where D(al(b) is the cross entropy of and b.
13

---

Published as a conference paper at ICLR 2024
Definition 3 (Events E (t) and Ez(t)). Ei( is the event that the optimal arm 1 satisfies (t) N
(t-1), Vt E [T - to]- (t) the event that the optimal arm not identified in the empirical
competitive set Ex at round t, > to.
Based on the above facts and the definition, we then provide the following lemmas.
Lemma 3. Let
N-1 N, and 5 (N 1)( exp(-A /16) + 2exp(-Aminl
eexpp-5A 55 min/ /16) + exp
(40 )لتد + +exp(-AAmil The probability of event Et(t) is upper
bounded by Pr(n (t) < xx)
S exp ( (-1D(7116))
Proof. Let X, = denote the optimal arm is pulled at r round, and X, = denotes that the best arm is not pulled. Considering the probability (t(n((t)= < - t > to). we assume that each arm is pulled at least two times after the warm-up up round tg. Therefore, we can transform the probability (t( < & > to) into Pr( X, > (N- (N-1), + 2 < Pr > (N ()) t).
N
In our algorithm, for every set S S [t- tol. Pr (AresX, = 1) = IIes Pr (X, 1[Fr), where Fr the history of pulling the optimal arm 1 until round We first analyze the upper bound of the probability Pr (X, = Fr),,, when 7 E [ - lo].
From our algorithm, we can derive that Pr (X, 1 S EEENTY Pr Pr (0)(F) < (e(+)
+ [N Pr (T) < (ee(T), ne(t)= 2 (T-1)) where l is a sub-optimal arm. We then analyze
the bound of probablity Pr (X, = 1) as follows:
(T
Σ (r((((T) <0,(T)]F+)+
Σ Pr (I(T) < <(((t)
N
RE(N]V
RE(N]
Σ Pr
((016) <1
A
(c(T) > 11
-1-21 -
-1
2
EENNI
Σ Pr ((1(0) <M1
Amin
)U (e(()) > 11
Amin
.me(t)z
(T (T-1))
2
2
A
Σ Pr
(1((T)
<1
+
Σ Pr (c(T)
> Me +
2
2
REIN
BE(N](1
ΣT E
Elr (t)]
A min
Σ Pr (I(T)
T
2
EE[MI
Amin
(T - 1)
Σ Pr
(ee(T)
> pe
ne(T)
2
N
MM
(b)
(N 1)(( 1
exp(e main/ /16) 2 exxepp A
2 2uin/4) /4)
exp(( 2 exp (_11o (lo - 1) min
+ eep(--A
2
2N
where we have (a) from the union bound. For inequality (b), our objective is to delineate the
upper bounds of to derive the upper bound of Pr (0I(T) < f1 2 ) and Pr (0c(7) > pe + A )
To achieve this, we invert our approach to discuss the lower bounds of Pr (01 2 /1 -ar) and
Pr (Be(T) S pe 4) We first focus the probability Pr (0) 2 p 4
14

---

Published as a conference paper at ICLR 2024
4 2
A
4
Pr (1(T) 2 p1
2 Pr
(1(() 2 (1(
2 n
4
2
A/) ) Pr (b2(T)
De
De
= Pr
(1(() 2 A1())
2 μ1
4
2
80 1 exp( (0(0mn) (+)44/322) e1-exp( -n (8))
1
(oxpp(nn1(0
1
1 exp( 1 (T) - exp( + (xp(-5n1(T)A23
(8)
where the inequality (c) is from Fact 1 and 2
Similarly, we can derive
A 2 2 1- 1
Pr (c(T)) S me
exp( ( /22).
Then we can derive (b) using Fact and the warm-up round fo-
and we have ensured each arm is pulled at least times during
For every S - [t - tol. we have an upper bound value 6max for Pr (X, = =1 Smax (N exp(- / 116 + +2 min 4) 1 exp(-55A2 / 116 + exp
2N
exp(-A2 (mn) )) Let d- t-to Et dmax = δmax and 7 [N-1)
we can derive the following N
bound from Fact 3
t 1-1 1
- 1) N
Pr(mi(t) <
Pr
X
S exp (xp((t1()1)))
(9)
N
T=0
Lemma 4. After the warm-up round to for any sub-optimal arm k # 1, Dr = un - Mk 2 0, the following inequality holds,
(1 1)
4N
Σ +1
Pr k= komp n1))
<
A
Proof.
We bound the probability by:
T
k = hemp (t), n2 (t) 2 (1 - 1)
Σ
Pr
N
1=
(1 - 1)
.n((t)) 2 (1-1) 1)
Pr
1= kt) 2
N
N
1=
T
(t - 1)
(t (t-1) 1)
Σ Pr
(nx(1) 2 (1))
,n](1)
2
N
N
(=l++1
Σ
T
Pr
(Pi(() Sm
U m1 - - .na(t) 2
(t 1t-
.1(() 2
(t 1)
2
N
N
(=o+1
T
(Bi(0) Sm AG
U((a(t)) me + - mx(())
(1-1)
,nt(t) 2 (1-1)
Σ Pr
N
N
t=
T
A
ml(()= 2 (1-1))
T
(1) - 1 2 A
(1 - 1)
Pr
(1) - -14 S
+ Σ
Pr
(1)(() 2
2
N
2
N
+1
t
(t--
(g)
4N
Σ
2exp
2N
A
(=f++1
(10)
15

---

Published as a conference paper at ICLR 2024
Here, (d) holds because of the truth that the empirical best arm is ke (t) selected from the set
S. = (k E [M] : ny (8) 2 D. J. Inequality (e) follows the union bound. We have (f) from the
truth that pa = Ei (T Vk E [N] and Fact ! The last inequality (g) uses the fact
(e
that and the geometric series.
Proof of Lemma 1. Now, we prove Lemma 1 in the main paper.
Proof. During to warm-up rounds, the maximum pulling times of a non-competitive arm kr are bound in fo. We then analyze the expected number of times pulling Aac after round to-
Pr(l(t)= = km)))
11
Σ
Pr(k(t)= = ke (t) -
Σ Pr(k(t)= = knc ,n))n
(t (1-1)
t1
t
(0)
T
(t 6-11 1)
Pr(k(() = k,c kace = cmm (1), 721 (1) 2
N
t1
k(1)= knc kne Se \. k.mp (1), (1) 2 (t (8-11 1)
T
(t- 1)
Σ
Pr
Σ Pr(n)(1)
N
1=
(=fo+1
T
(t (t-1))
4N
T
Σ
Pr
(t((t)= S
= kmc (t) 2
+
exp xxt(((())1)))
11
N
A
kine
t=
T
(B,(0) SM + 1 U ((pancott) 14 + AgmeL)
(t (t-1)
1)
Σ t=to+1
Pr
.k(t)) ksc (t((t) 2
N
4N
Σ exp
(-tD(>)16)) +
A kne
1=t++1
T
A 1 m1(1) 2
(1 - 1)
Pr
(t) S11 +
N
1=
E|
(1)
Âgne,1 ,k(t)= k.ne
4N
Σ Pr
Ga (t) 2
1=
kac
exp (-tD(>>10))
T
A A
11
t=
(k)
T
-11-)) k
T Σ
Et=1
maz kue
A Ann,1
Σ
exp
+
Pr
PAnc (Tx)
2N
T
2
1=
j=1
4N
Σ
exp
+ (-ID(+110))
2
1=t++1
knc
1=
Σ
T
1
exp
(t
2N
1)
k
j=1
exp
J
kno,1
2
+
t=
Σ
exp
+ exp(ttD(>11))
A
4N
gne
(m)
2N
2
4N
+
+
((),
A
2
D
A kmc
Ane,1
kne.1
(11)
Here, both (h) and (j) are derived using the union bound. We have (i) from the Lemma 4 and Lemma 3 The inequality (k) is obtained from Fact wherein j (k) explicitly denotes the round
index when arm boub is pulled. Inequality (l) stems from Trom
Fact We have (m) because of the truth
33 _2m0,1
2 0, Agne,1 2 0, and D(>11)) 2 0. We also use geometric series in (m).
that
2N
16

---

Published as a conference paper at ICLR 2024
We provide another Lemma to facilitate the proof of Lemma 2 in the main paper. Lemma 5. The following inequality holds,
(-
(t 1)4 min
(N -W-1) 1)
Pr (E2(t)) & A(N - exx
+
2NV
D(rll0)
where Amin ming 4
Proof.
(2) S
(1-1)
N (nt(t) 2 (1-1)
Pr (E2((t))
E Pr ((())))(()))m())))))))))))))))))
N
BE(N](1
(1(1) < (c(1) < (t-1)
_n((t) 2 (t-1) 1)
+ Σ Pr
N
N
KENN
(t (t-1)
- (t
+ Σ Pr
(1(t) <(e(t),
.ne(t) 2
N
N
EENN
Amin Ukie(t) > p1
Aminy
S Σ Pr(
(f1(t) </1
2
KEINTL
ni (f) 2 (1-1)
(1 (1-1)
.n((t) 2
N
N
+ Σ Pr(
(P1(t) < <11
Amin U(pe(t) P1
A Amin
2
KENNN/
ni (f) 2 (1 1-11 1)
(1 (1-1) 1)
(1 - 1)
.ne(t) 2
+
Σ
Pr m1(1) <
N
N
N
RE|N]I
D
B(rrnax
A Amnn _n(()) 2
(t - 1)
Σ Pr BE[NJ
(+1(1) <
21=
T
2
N
+ Σ Pr
(0z(1) < 141
A min
m1(1) 2
(t 1)
2
N
KENNN
A Amin
(1
11)
+
Σ Pr (e((t) > Me +
ne(t) 2
(N (x
N
RE[NT11
(p)
(t (_
1) min
S 4(N - 1) exp
+ +N - 1) exp exp (-tD(rl10))
2N
(12)
Inequality (n), using union bound, arises from the observation that when arm is absent from the empirical competitive set 5º at round it is either not selected the empirical best arm kemp(t) (t) its (1) is less than the estimated mean of the empirical best arm ( (4). The validity of inequality
(n)) relies the fact that Ei B[r (t) > fn and Lemma We establish the final inequality (p) by leveraging Fact]]
T
Proof of Lemma 2. Now, we present proof details of Lemma 2 in the main paper.
Proof. We split the analysis of Et Pr(k(t) = )m=b)) into three parts: the pulls in the warm round; the pulls when the event (t) happens after the warm round; the pulls when the complementary of
17

---

Published as a conference paper at ICLR 2024
(t) happens. We summarize it as follows:
40
(k(t) = kou0)
(k(t) = kou0) +
Σ
Pr (k(tt)
= aen E2()))
t
Σ
Pr (k(t)) = k.sub F Et)
(13)
t=o+1
T
T
Pr (k(t) = k.ub)
+
Σ t
(F(F2(1)
When event Et( does not happen, the analysis of the upper bound of pulling the competitive but sub-optimal arm aligns to plain TS. We apply the result from Agrawal and Goyal (2012). which bounds the number of times a sub-optimal arm k * pulled within (log(())) In Lemma when (t) happens, we derive the following bound:
T
([N--)eep) exp (1 1)4 mán
Pr((2(())
Σ
4(N -
+ (N
exp (xxp(((())))))
2N
#1
11+
8N(N - 1)
A min
D(y(18)
(1).
(14)
The proof is completed.
Proof the Theorem 1.
Proof. We revisit the definition of expected regret, given by:
T
N nr (T)
E [(T)
E
(11 (o(c))
= E
A==1
Considering D competitive arms and (N D) non-competitive arms, the regret of E-TS in T rounds is bounded by:
((T))
E El (T) Agne +
E Eliigena (T))
k
(15)
A A 0(1)+ +
Rnaa (log(T))
k= D]
Reub E|D
< SN - (1) + (log(T)))
where the inequality (1) is from Lemma P Lemma
Thus the proof is finalized.
C SUPPLEMENTARY EXPERIMENTS AND EXPERIMENTAL DETAILS
C. DATASET AND MODEL STRUCTURE
Table provides essential information about each dataset used in study. We will introduce more details regarding the dataset characteristics and the corresponding model structures.
The Credit dataset consists of information regarding default payments, demographic characteristics, credit data, payment history, and credit card bill statements from clients in Taiwan. The dataset is partitioned evenly across six clients, each managing bottom model with Banear--ttchhomm.. ReLU structure. The server hosts the top model, comprising of two Linear-Red followed by WeightNorr--Linaare -iner-SSggoi layer.
layers
18

---

Published as a conference paper at ICLR 2024
The Real-sim dataset is from LIBSVM, which is library for support vector machines (SVMs). 10 clients equally hold the data features and compute embeddings through a bottom model with Linear-Ree -ea-a--ee----Boooomt layers. The server controls the top model with Linar-ReLL layers.
The FNSh dataset consists of 28 x 28 grayscale images of clothing items. The dataset is equitably distributed across 7 clients, with each holding data portion of 28 x 4 dimensions. On the client side, it holds a Norra-aatttta-eReeeleee model comprises eight groups of Hann-BatchNorm-RRee structures, two MaxPool layers, two Linear-Dropout
bottom model. On the server side, the top
layers, and a final Linear output layer.
The CIFAR-10 dataset contains 60,000 color images of size 32 32, representing vehicles and animals. We divide each image into 4 x 32 sub-images and distribute them among 8 clients. Each client's bottom model consists of 2 convolutional layers and max-pooling layer. The server's top model is built with 6 convolutional layers and 3 linear layers.
The C dataset, subset of seven classes from the Caltech- 101 object recognition collection, is distributed across six clients. Each client is assigned one unique feature view, encompassing the Gabor feature, Wavelet moments (WM), CENTRIST feature, Histogram of Oriented Gradients (HOG) feature, GIST feature, and Local Binary Patterns (LBP) feature, respectively. Every client structure. At the server level, the top
maintains a bottom model utilizing Birecrr-BachNNoom-Ree model comprises eight Linear-Rell layers, two Dropout layers, and final Linear output layer.
The IMDB dataset comprises 50,000 highly polarized movie reviews, each categorized as either positive or negative. For distributed processing across 6 clients, each review is divided into several sentences, and an equal number of these sentences are allocated to each client. Each client utilizes a Bert model without fine-tuning-- These embeddings are then input to the server's top model, which consists of two Linear-Rel.J layers followed by final Linear output layer.
the bottom level to obtain an embedding with 512 dimensions.
Table 1: VFL dataset and parameters descriptions.
Task
Tabular
CV
Multi-view
NLP
Datasct name
Credit
Real-sim
PashionMNIST
CIFARTO
Caltech-7
IMDB
Number of samples
30,000
72,309
70,000
60,000
1474
50,000
Feature size
23
20,958
784
1024
3766
Number classes
10
Number of clients
8
Batchsize B²
32
512
128
32
16
64
Warm-up rounds to
50
50
80
80
80
40
C.2 EXPERIMENTAL RESULT IN ABLATION STUDY
Additional experiments have been conducted across a variety of datasets under diverse corruption constraints, as illustrated in Figure 5
C.3 DYNAMICS OF ARM SELECTION AND EMPIRICAL COMPETITIVE SET IN TS AND E-TS
We investigated the arm selection behavior of TS and E-TS during a targeted attack on FashionM- NIST, as shown in Figure 6) This study also tracked the variation in the size of E-TS's empirical competitive set, depicted in Figure The parameters for this analysis were consistent with those in the FashionMNIST targeted attack scenario (Figure TD: to = 80, 2, 3 = 0.15, Q = 2000 and the number of arms N
= 21. We list all arms as follow:
[0: (client 1, client 2), 1: (client 1, client 3), 2: (client 1, client 4), 3: (client 1, client 5), 4:(client 1,
client 6), 5: (client 1, client 7), 6: (client 2, client 3). 7: (client 2, client 4), 8: (client 2, client 5), 9: (client client 6), 10: (client 2, client 7), 11: (client 3, client 4), 12: (client 3, client 5), 13: (client 3,
client 6). 14: (client 3, client 7). 15: (client 4, client 5), 16: (client 4, client 6). 17: (client 4, client 7),
18: (client 5, client 6), 19: (client 5, client 7), 20: (client 6, client 7)].
Analysis of Figure reveals that initially, E-TS selected a suboptimal arm. However, after 140 rounds, it consistently chose arm 5 (representing the pair of client I and client 7), indicating stable
19

---

Published as a conference paper at ICLR 2024
FasHionMNIST
Caltech-7
Number of mopteed dlentrr()
Wenter of compone dermo))
Kumber comrupte chnre
Samzer of compeet d wredd
(a) Targeted (8 0.3)
(b) Unlargeted 0.1)
(c) Targeted (3 0.3)
(d) Unlargeted (B 0.3)
Credit
IMDB
100
A390900
-6
Sumber of comppptdd chentel))
Number corrupted dlenkat))
(e) 9 0.3
(0) 0 = 0.05
Figure 5: ASR using different number of corrupted clients.
selection. In contrast, TS continued explore different arms during this period. Figure 6(b) shows that the empirical competitive set in E-TS reduced to a single arm within the first 40 rounds. Initially, the competitive arm selected by E-TS was not optimal. Nevertheless, E-TS effectively narrowed down its focus to this suboptimal arm, eventually dismissing it as non-competitive and identifying the best arm for selection.
The choice of arm vs attack rounds
The size of competitive set attack round of E:TS
20
E-TS
E-TS
18
TS
18-
16
16-
14
14-
12
Ams5
12
100
M 10-
100 150
200
250
300
100
150
200
250
Attack round (t)
Attack round (t)
(a) The choice of arm in E-TS and TS.
(b)
The change of the empirical competitive set's size.
Figure 6: Dynamics of arm selection and competitive set in E-TS and TS.
C.4 MINIMUM QUERY BUDGET AND CORRUPTION CHANNELS TO ACHIEVE 50% ASR
To explore how the necessary number of queries and corrupted channels vary across different models, datasets, and systems, we conducted experiments using Credit and Real-sim datasets. We specifically analyzed the average number of queries required to attain a 50% ASR under various levels of client corruption (corruption constraint C). For this analysis, we applied the proposed attack on both the Credit and Real-sim datasets in 7-client setting. We varied C' from to 7 and recorded the average queries q needed for attacking over 50% of the samples successfully. In addition to assessing the impact of different datasets, we investigated the influence of model complexity by attacking two deeper Real-sim models contrasting it with the standard 3-layer server model. Specifically, the standard 3-layer model Real-sim (stadaaddrrd) has Dropout layer after the first layer of the server model and achieves 96.1% 1% test accuracy. One deeper server model (eaees) added an extra three layers to the Real-sim(standart after the Dropout layer of the server model. Another model
20

---

Published as a conference paper at ICLR 2024
Real-sim seal--ii(dropout)) structure is the same Real-sim(deep) except that it added another Dropout layer before the penultimate layer of the server model. Both <ddee)) and Real-sim((ropooe have 97% test accuracy. Furthermore, to analyze the system's effect q and C, we conducted experiments on Real-sim in 10-client scenario, varying C from to 10 and recording q- Throughout these experiments, we maintained 0.8 and In 2N, where N denotes the number of arms. The results are presented in Figure
Average number of queries in different C
Average number of queries in different
(o)
700
sealttimmstan
Average number of querles (a)
6.00
Real-sim
Credit
Real sim[deep]
500
mimdrrout)))))
400-
200
200
100
2
3
6
2
3
4
5
10
Number of corrupted cilents
Number of corrupted ciients
(a) 7 clients.
(b) 10 clients.
Figure Average number of queries in different corruption constraint achieve 50% ASR.
we observe that the required average number of queries decreases with a looser (or higher) corruption constraint C. The comparison of Real-sim and Credit (Figure ((a) reveals that simpler datasets in the same task category (both being tabular datasets) necessitate fewer queries.
From Figure 7
Contrary to our initial assumption, a deeper model does not necessarily require more queries. The results for (istadiimstanddrd) Real-s) and Real-sim attacking Real-sim(deep) requires fewer queries. deeper model with an extra Dropout layer can make the model more robust and needs more quires to achieve 50% ASR. The reason for that is the deeper model will learn a different hidden feature of the sample, thus making the model have different robustness compared to the shallow one. Dropout can enhance robustness by preventing the model from becoming overly reliant on any single feature or input node, encouraging the model to learn more robust and redundant representations.
from Figure (() suggest that
Comparing Figure (a) and (b), we deduce that systems with more clients demand greater number of queries to achieve the same ASR a given C, due to each client possessing fewer features.
In conclusion, to attain a target ASR with the same C, simpler datasets within the same task require fewer queries. Systems with higher number of clients necessitate more queries. However, the influence of the model's complexity does not simply depend on the scales of model parameters but is affected more by the Dropout layer.
C.5 DISCUSSION ON THE LARGE EXPLORATION SPACES
We extend the experiments in Figure 4 to larger exploration spaces, i.c. set the corruption constraint = and C = 8, which results in (19) 11, 440, (19) 12, 870 arms, respectively. However, constrained by the computation power and limited time in the rebuttal period, we compare E-TS and plain TS in large exploration spaces through numerical simulation where ASR is substituted with sample in Gaussian distribution. For the simulation, we created a list of means starting from 0 up to 0.99, in increments of 0.01. each with a variance of 0.1. This list was extended until comprised 11, 1,4 by mean of and a variance of 0. This list represents the underlying mean and variance of the arms. Upon playing an arm, reward is determined by randomly sampling a value, constrained to the range 1]. With knowledge of the underlying mean, we plotted the cumulative regret over rounds,
and 12, 870 elements, to which we added the best arm, characterized
= -(t)=I=r (w) - ) ). where μ4 is the best arm's mean, and k(r) is the arm selected in round These results presented in Figure
21

---

Published as a conference paper at ICLR 2024
Regret 11,440)
Regret 12,870)
35000
25000
25,000
20000
20000
Regret
15000
Regret
10000
5000
0
2000n
40000
60000
100000
0
20000
43000
60000
80000
Icocon
Round (t)
Round (t)
N 11, 440.
(b) N 12, 870.
Figure 8: Regret in large exploration spaces.
The results from Figure Saaneereveer reveal that in large exploration spaces, TS struggles to locate the best arm within a limited number of rounds. In contrast, E-TS demonstrates rapid convergence, further confirming the benefits of utilizing an empirical competitive set in large exploration spaces.
C.6 THE STUDY OF OPTIMAL CHOICE ON THE WARM-UP UP ROUND to
To ascertain the ideal number of warm-up rounds to for different arm settings, we conducted numerical experiments with N 100 and N 500. For N 100, experimented with to 150 (less than 2N), to = 200, 300, 500 (within [2N,, 5N)), and to = 800 (greater than 5N). Similarly, for N 500, the settings were 750 (less than 2N), to 1000, 2000, 2500 (within (2),, and to 4000 (greater than 5.N).
In these experiments, ASR arms with means from 0 to 0.99 (in 0.01 increments) and variances of 0.1. The reward for playing sampled from its Gaussian distribution. The cumulative regret R(T) was computed as R(T) (P1 ()(()), where μn = 0.99 and k(t) the arm selected at round t, as illustrated in Figure
replaced with Gaussian distribution samples. We initialized 100
Round vs Regret (N 500)
Round Regret (N 100)
15-150
1200
(D-230
200
I0-320
1000
B--500
12m0200
150
Regret
Regrat
400
50
200
2000
4000
6000
10000
250 500
750 1000 1250 1500 1750 2000 Round
Round
(a) N = 100.
(b) N 500.
Figure 9: E-TS performance using different warm-up rounds.
Figure (a) shows that E-TS converges faster with a smaller fo. but with to 150, it converges to sub-optimal arm. Figure 9b) indicates faster convergence with smaller lg. Both figures suggest that to = 2N achieves the most stable and rapid convergence, while t, > 5.N results in the slowest convergence rate. Analyzing the pull frequencies of each arm during tu, find that with to 2N, most arms are pulled only once, and some are never explored. Conversely, with tn 5N], most arms pulled at least twice, yielding
reliable estimation of their prior distributions.
22

---

Published as a conference paper at ICLR 2024
Thus, recommend setting to to at least N, with the optimal range being [2N, 5. in practical scenarios. This range ensures that each arm is sampled at least twice using TS, enabling a more accurate initial ussessment of each arm's 's prior distribution. Such preliminary knowledge is vital for E-TS to effectively form an empirical competitive set of arms. If to is too small, there's s an increased suboptimal arm due inadequate initial data, possibly
risk of E-TS prematurely converging overlooking the best arm in the empirical competitive set.
23


Reviews:
[{"review_id": "YBnvUkjwqZ", "reviewer": "Reviewer_GNem", "summary": "The paper studies the adversarial attack in vertical federated learning inference phase. The adversary is the man-in-the-middle that can only perturbs the intermediate embeddings of the test samples sent by the clients. The authors propose an attack utilizing multi-armed bandit to dynamically choose the best subset of the clients to perturb. The goal of the adversary can be targeted (i.e., the prediction of the test sample is a specific label) and untargeted (i.e., the prediction of the test sample can be any label except a specific one). An ablation experimental study is provided to study how the different parameters (e.g., the number of corrupted channels, perturbation budget) impact the attack.", "questions": "Questions:\n1) For the VFL inference setting, one point is not clear for me: the server broadcasts the probabilities vector back to all the clients for the inference. However, it would be more cost-saving to broadcast only the label. In this scenario, it would be harder to design attacks. Is there any reason that the client must receive the probability vector for the inference? \n\n2) I would like to see the discussion on how easy/difficult this attack can be noticed by the server. For me, it seems that targeted attack could be easily identified by the server. If the server observes that for test sample queries, the probability vector evolution converges to the same label, i.e., there might be an attack. Then one naïve way to mitigate this attack is that the server sends back always the probability vector obtained by using the first embedding query to avoid the training of $\\eta_i^t$. Actually, I do not see the interest for the server to answer $n$ queries of the same test sample (line 10 in Algo 2) which helps the attacker to find the best perturbation.   \n\n3) From my intuition, untargeted attack should be easier than the targeted one. If one can succeed the targeted attack with ASR $r$ on label $x$, then one would expect the untargeted one should be at least $r$ on label $y != x$. More precisely, let $r(x)$ be the targeted ASR on label $x$, the untargeted one on label $y$ should be better than $max$ {$r(x)|\\forall x!=y$}. In the experiment, the results on FashionMNIST confirms this intuition, whileas the results on CIFAR-10 gives opposite observation. Could authors provide more explanation for this observation? Besides, what are the untargeted labels used in the experiments? \n\n4) In Figure 3c, when the query budget decreases to 500 for FashionMNIST, the targeted attack accuracy reaches almost 10%, which is equivalent to the ASR of no-attack case if the sample is randomly split in the batch.  The same observation can be found in Figure 5c when there is only one corrupted channel. Does it mean that when the query budget is limited or the number of corrupted channels is limited, applying the proposed method has smaller or even no advantage than doing nothing for targeted attack? What impacts the minimum necessary query budget and the minimum required number of corrupted channels? The complexity of the dataset, model or the scale of the system? I would like to have more insight on this problem.       \n\nMinors:\n\n1) The settings for each Figure are not well-indicated, especially for the ablation study. For example, in Figure 3, when we vary one parameter, what are the default values for the other parameters.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "The paper is well-written, not hard to follow. The algorithm is clearly presented. The theoretical part seems solid with classical analysis.", "weaknesses": "However, I have some concerns on the attack design and the feasibility of the proposed method (detailed in the questions). I might misunderstand some part, but if the authors can answer my concerns, I would like to adjust my score.   For the correct stage, I would not go for the acceptance.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "8hgdRXTQez", "reviewer": "Reviewer_HdL1", "summary": "This paper delves into the vulnerabilities of Vertical Federated Learning (VFL)  through developing a novel attack to disrupt the VFL inference process, under a practical scenario where the adversary can adaptively corrupting a subset of clients. This paper frames this problem as an online optimization problem consisting of adversarial example generation (AEG) and corruption pattern selection (CPS). The paper equates CPS to a multi-armed bandit problem, proposing the Thompson sampling with Empirical maximum reward (E-TS) algorithm, which efficiently identifies the best clients to corrupt, backed by analytical regret bounds and empirical results showcasing its effectiveness.", "questions": "1. See in Weakness 1. Can authors explain the choice of the probabilities and the bounds?\n\n2. The performance of the proposed algorithm is related to the choice of $t_0$. The requirement of the prior information of $t_0$ violates the black-box setting. Can authors provide any insight into the proper choice of $t_0$ in the black-box setting?\n\n3. In my opinion, the corruption pattern selection (CPS) problem is more like the setting of combinatorial multi-armed bandits (CMAB) with bandit feedback than MAB. Why did the author choose the model of MAB? Are there some benefits of MAB?", "limitations": "", "rating": 5, "confidence": 3, "soundness": 1, "presentation": 3, "contribution": 2, "strengths": "Originality: The paper introduces a novel attack to disrupt the VFL inference process, under a practical scenario where the adversary can adaptively corrupting a subset of clients. This paper frames the attack problem as an online optimization problem consisting of adversarial example generation (AEG) and corruption pattern selection (CPS). CPS is solved by an bandit algorithm which is quite interesting and novel. \n\nQuality: The paper provides a rigorous analysis of the regret bound of the proposed E-TS algorithm. The paper also presents an attack algorithm for attackable instances. The paper also empirically evaluate the performance of the proposed attack on datasets with four major types of VFL tasks.\n\nClarity: The paper is well-written and  presents the concepts, definitions, and analyses with clarity and precision. The detailed presentation of the experimental setup and outcomes ensures comprehensibility and ease of replication for readers.\n\nSignificance: The paper characterize the regret bound of the proposed E-TS algorithm, and empirically demonstrate its capability of efficiently revealing the optimal corruption pattern with the highest attack success rate. The idea of using bandit algorithm to perform optimal attacks may have practical implications for designing efficient attack strategies.", "weaknesses": "Overall, I like the formulation of the attack problem and the idea of utilizing bandit algorithm to reveal the optimal corruption pattern. However, I have the following concerns:\n\n1. The regret bound is a probability bound which only holds with some probabilities. However, the probabilities are not in the form like $1-p$. The probabilities depend on N and are less than $\\frac{1}{2}$ for any N. If N is smaller than 10, the probabilities are further smaller than 0.07. I doubt whether this regret bound really provide enough information about the effectiveness of the proposed algorithm.\n\n2. In Lemma 2 and Theorem 1, the regret guarantee requires that the selected warm-up rounds $t_0$ satisfies $\\sqrt{\\frac{t_0}{8N log(t_0)}} \\ge \\frac{1}{\\Delta}$. As the adversary is a black-box adversary, $\\Delta$ is unknown to the adversary, and there is no prior information about the choice of the $t_0$. The proper choice of $t_0$ is still a problem.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "3mi8g1bfg7", "reviewer": "Reviewer_XBEx", "summary": "The paper considers adversarial attacks on Vertical Federated Learning via selection of a set of clients to corrupt, and choice of perturbations of their representations in VFL. The perturbations are subject to a bound, as also the cardinality of the selected client set.  The client subset selection problem (choosing C out of M clients to corrupt) is recast as a MAB problem, and a modified Thompson sampling approach is proposed to deal with the computational complexity (#arms Some theoretical results are presented, bounding the regret under the modified sampling method. ). Performance results are presented for several datasets.", "questions": "Please see comments under Weaknesses\n\n--- Added after rebuttal/discussion phase -\n\nThe authors have addressed all my major concerns; they have added substantially to the Supplementary Material, and made changes as needed, including strengthening of one of the Lemmas. Based on this I have changed my score to Accept.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "VFL is an emerging area, and there has not been much work studying adversarial attacks in this setting.", "weaknesses": "The VFL setting as explained at the top of Section 2 is puzzling. This implies that a prediction query arrives simultaneously at all M clients.  But even in the given setting, why does the server need to broadcast the full probability vector, rather than the class with the maximal value? Is there a notion of a primary query client? Or is it more realistic that the query comes to the central server which then asks clients for their representations? \n\nWhat was the loss function L (in eqn (3), etc.) adopted in the experimental settings? \n\nWhy is the constant \\alpha^* needed in (4)? The later discussion in Sec 5.2 that the mean reward corresponding to the best arm (client subset) can be taken to be \\alpha^* is also confusing. The adversary does not know \\alpha^*, so how can it proceed to solve (4)? \n\nAlgorithm 1:\n- Please identify the inputs: t_o, {B_t, t=1,..,T} and the corresponding embeddings ….. \n- After line 11, shouldn’t there be a call to Alg 2 to compute the corrupted embeddings? \n- Line 6 should be in plural \n- Line 13: are the rewards assumed to be positive? \n- The role of \\phi is not clear. Let n(t) be the number of times a given arm is played, and let r(j) denote the corresponding rewards. Then \\phi = \\frac{1}{n(t)} \\sum_{j=1}^{n(t)} \\max(r_i, i=1,…j). Why is this an useful quantity to compute\n-  What is the reward? Is it merely the ASR over the batch? With reference to Remark 1 and the discussion of [Gupta et al., 2021], is the reward in this setting simply 0 or 1 (so max=1)? \n \nExperiments\nGiven that the value of N is small in all the settings (M takes values of 6, 7, 8 and 10, and C = 2,3,4), it would have been insightful to show how the best arm selection changes over t \\in [1, T]. It would also have been insightful to show how the size of the restricted set decrease with t. \n\nThe choice of datasets is poorly motivated for the VFL problem. The credit score and Caltech datasets are reasonable, but segmenting a CIFAR or MNIST image into segments, or an IMDB review at different clients is not reasonable. \n\nA value of Q=1000 is outrageously large. Servers with any reasonable security settings would turn off queries if they are repeated more than 3 or 5 times. A large Q is simply a mechanism for an adversary to learn (more samples). Q = 1000 is not a reasonable number. \nWhat were the default values of \\beta, B^t, T and C?\n\nThe “Ablation study” is not particularly helpful. That the adversary’s success rate would increase with \\beta, T, or C is obvious. This does not add any insights. Further discussion on choosing t_o would be useful. \n\nIn Figure 1 what do the curves ‘Client 4 5’ etc. mean? Why are different client pairs shown in different plots? What is a test epoch and what does 25 attack rounds/test epoch mean? Does this mean that B^t is fixed at 25? And that T  was 30 (judging from the figures)?\nThere is little difference between TS and E-TS after about 5 epochs. What is the corresponding complexity comparison? The log(T) to O(1) improvement does not seem to show up here. \n\nFigure 2: Fashion MNIST has 7 clients; so even with all 7 clients corrupted, manifold defense does pretty well. This is a surprising and unexpected result. \n\nFigures 2, 3 (and parts of 1): Figures showing performance results on Credit Score or the Caltech dataset would have been more meaningful. More specifically, recognition of MNSIT / Fashion MNIST / CIFAR does not require all pieces of the full image; neither does sentiment analysis of a review; further, as noted earlier, such segmentation is unrealistic in any case. \n\nFigure 4: What is the setting with 16 and 28 clients? How were the images segmented? Is it meaningful to have a 28-pixel image segment at each of 28 clients? \n\nTheoretical results\nLemma 1, Lemma 2, and Theorem 1 appear to have an implicit large N assumption.  The lower bound on the probability is negative for N < 55, and exceeds 0.5 at about N=150. \n\nHow does the proposed E-TS algorithm work compared to sequential arm elimination proposed in \nS. Shahrampour, M. Noshad and V. Tarokh. On Sequential Elimination Algorithms for Best-Arm Identification in Multi-Armed Bandits. IEEE Transactions on Signal Processing, vol. 65, no. 16, pp. 4281-4292, 15 Aug.15, 2017 \n\nIs a factor 2 missing in the equation for Fact 1?\n\nIn the proof of Lemma 4, shouldn’t the = sign be <= on line 5. The transition from line 6 to line 7 (“g”) is not clear. \n\nProof of Lemma 5: The fact that … towards the end of the proof is not obvious; it holds asymptotically; why does it hold for all T?\n\nProof of Theorem 1: Please add proof details. The terse statements are insufficient. \n\nPuzzling statement in Section 3: “β ∈ [0, 1] is the perturbation budget of some simple magnitude-based anomaly detector.” Whose anomaly detector, and why is it assumed to be simple?\n\n\n\nBefore (2): “taking over” should be “taken over”. \n\nP6, line 7: “obtain” should be “obtains”. \n\nThe sentence about the large exploration space (below Fig 1 and Fig 2) is confusing. How are these numbers obtained?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "nK2sYJLYNv", "reviewer": "Reviewer_qKnn", "summary": "To me it seems the main contribution of this paper is the formulation of the adversarial attacks in the VFL setting as a MAB problem and the development of the E-TS algorithm, whose usage in practice seems unrealistic to me, considering the combinatorial structure of the problem and availability of combinatorial MAB algorithms.", "questions": "no questions for now", "limitations": "", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper is nicely written and executed. \nTheir contributions are clear and the experimental results are fairly diverse.\nThe formulations of the problem in (3) and (4) as a MAB problem is interesting, and to my knowledge and as per authors' claim, novel as well.\nThe E-TS algorithm is an interesting approach to circumvent the combinatorial structure of the problem and the authors provide regret bounds and experimental evidence as to the expected performance improvement gained from E-TS. However, I am not fully convinced to its practical utility.", "weaknesses": "The E-TS algorithm is supposed to outperform the TS algorithm via the machinery of \"competitive arm set\" constructed at each round. \n\nA critical point that leaves me in doubt about E-TS is the number of required warm-up rounds t_0 being too large to the point it renders E-TS useless, even with fairly small scale problems. This is suggested both by intuition and Lemma 2, i.e., it grows proportional to the inverse square of the minimum sub-optimality gap and to the number of total arms, which grows exponentially in number of individuals arms to be selected, therefore rendering E-TS' practical utility very limited in my opinion. For instance, I would like to see what happens when the number of clients to be selected is increased from 2 or 3 to, say, 7-8 in Figure 4. There is a vast literature on \"combinatorial\" MABs which could offer better solutions to this problem with lesser assumptions, e.g., by imposing and exploiting some sort of structure between the arms.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)