Label Leakage and Protection in Two-party Split Learning

Problem setup. Consider two parties learning a composition model $h\circ f$ jointly for a binary classification problem over the domain $\mathcal{X}\times\left\{0,1\right\}$ (Figure 1). The non-label party owns the representation function $f:\mathcal{X}\to\operatorname{\mathbb{R}}^{d}$ and each example’s raw feature $X\in\mathcal{X}$ while the label party owns the logit function $h:\operatorname{\mathbb{R}}^{d}\to\operatorname{\mathbb{R}}$ and each example’s label $y\in\left\{0,1\right\}$¹¹1 To simplify notation, we assume no additional features in the label party to compute the logit. The data leakage problem still holds true for other more complicated settings (see WDL experiment setting in Section 5). . Let $\ell=h(f(X))$ be the logit of the positive class whose predicted probability is given through the sigmoid function: $\widetilde{p}_{1}=1/(1+\exp(-\ell))$. We measure the loss of such prediction through the cross entropy loss $L=\log(1+\exp(-\ell))+(1-y)\ell$. During model inference, the non-label party computes $f(X)$ and sends it to the label party who will then execute the rest of forward computation in Figure 1.

Model training (Figure 1: backward gradient computation). To train the model using gradient descent, the label party starts by first computing the gradient of the loss $L$ with respect to the logit $\frac{dL}{d\ell}=(\widetilde{p}_{1}-y)$. Using the chain rule, the label party can then compute the gradient of $L$ with respect to its function $h$’s parameters and perform the gradient updates. To also allow the non-label party to learn its function $f$, the label party needs to additionally compute the gradient with respect to cut layer feature $f(X)$ and communicate it to the non-label party. We denote this gradient by $g\coloneqq\nabla_{f(X)}L=(\widetilde{p}_{1}-y)\nabla_{z}h(z)|_{z=f(X)}\in\operatorname{\mathbb{R}}^{d}$ (by chain rule). After receiving $g$, the non-label party continues the backpropagation towards $f$’s parameters and also perform the gradient updates.

Why Not Differential Privacy? Note that for a given iteration, the non-label party randomly chooses $B$ example IDs to form a batch. Therefore, the identity of which examples are used is known to the non-label party by default. In addition, the communicated features $f(X)$ and returned gradients $g$ will both be matrices in $\operatorname{\mathbb{R}}^{B\times d}$ with each row belonging to a specific example in the batch. The different gradients (rows of the matrix) are not with respect to the same model parameters, but are instead with respect to different examples’ cut-layer features; thus, no averaging over or shuffling of the rows of the gradient matrix can be done prior to communication to ensure correct computation of $f$’s parameters on the non-label party side. This example-aware and example-specific nature of the communicated gradient matrix makes differential privacy (which focuses on anonymizing an example’s participation in an aggregate function) inapplicable for this problem (see also Section 2).

Below we specify several key aspects of our threat model, including the adversary’s objective and capabilities, our metric for quantifying privacy loss, and the possible inclusion of side information.

Adversary’s objective. At a given moment in time during training (with $f$ and $h$ fixed), since the communicated cut layer gradient $g$ is a deterministic function of $f(X)$ and $y$ (see Section 3.1), we consider an adversarial non-label party whose objective is to recover the label party’s hidden label $y$ based on the information contained in $g$ for every training example.

Adversary’s capability. We consider an honest-but-curious non-label party which cannot tamper with training by selecting which examples to include in a batch or sending incorrect features $f(X)$; instead, we assume that the adversary follows the agreed-upon split training procedure while trying to guess the label $y$. This can be viewed as a binary classification problem where the (input, output) distribution is the induced distribution of $(g,y)$. We allow the adversary to use any binary classifier $q:\operatorname{\mathbb{R}}^{d}\rightarrow\left\{0,1\right\}$ to guess the labels. This classifier can be represented by a (scoring function $r$, threshold $t$) tuple, where $r:\operatorname{\mathbb{R}}^{d}\rightarrow\operatorname{\mathbb{R}}$ maps an example’s cut layer gradient to a real-valued score and the threshold $t\in\operatorname{\mathbb{R}}$ determines a cut-off so that $q(g)=1$ if $r(g)>t$ and $q(g)=0$ if $r(g)\leq t$. Moving forward, we use this tuple representation to describe adversarial non-label party classifiers.

Privacy loss quantification. As we consider binary classification, a natural metric to quantify the performance of an adverary’s scoring function $r$ is the AUC of its ROC curve. Denote the unperturbed class-conditional distributions of the cut-layer gradients by $P^{(1)}$ and $P^{(0)}$ for the positive and negative class, respectively. The ROC curve of a scoring function $r$ is a parametric curve $t\mapsto(\textrm{FPR}_{r}(t),\textrm{TPR}_{r}(t))\in[0,1]^{2}$ which maps a threshold value $t\in\operatorname{\mathbb{R}}$ to the corresponding (False Positive Rate, True Positive Rate) tuple of the classifier represented by $(r,t)$, with $\textrm{FPR}_{r}(t)\coloneqq P^{(0)}(\left\{g:r(g)>t\right\})$ and $\textrm{TPR}_{r}(t)\coloneqq P^{(1)}(\left\{g:r(g)>t\right\})$. The AUC of the ROC curve of a scoring function $r$ (denote by $\textrm{AUC}(r)$) can be expressed as an integral:

(more details on this expression see Appendix A.1.) We use this value as the privacy loss quantification metric for a specific adversary scoring function $r$ and refer to it as the leak AUC. This metric summarizes the predictive performance of all classifiers that can be constructed through all threshold values $t$ and removes the need to tune this classifier-specific hyperparameter. The leak AUC being close to $1$ implies that the corresponding scoring function $r$ can very accurately recover the private label, whereas a value of around $0.5$ means $r$ is non-informative in predicting the labels. In practice, during batch training, the leak AUC of $r$ can be estimated at every gradient update iteration using the minibatch of cut-layer gradients together with their labels.

Side information. Among all the scoring functions within our threat model, it is conceivable that only some would recover the hidden labels more accurately than others and thus achieve a higher value of leak AUC. Picking these effective scoring functions would require the non-label party to have population-level side information specifically regarding the properties of (and distinction between) the positive and negative class’s cut-layer gradient distributions. Because we allow the adversary to pick any specific (measurable) scoring function $r$, we implicitly allow for such population-level side information for the adversary. However, we assume the non-label party has no example-level side information that is different example by example. Next we provide two scoring function examples which use population-level side-information to effectively recover the label $y$.

Attack 1: Norm-based scoring function. Note that $\|g\|_{2}=\left|\widetilde{p}_{1}-y\right|\cdot\|\nabla_{a}h(a)|_{a=\bm{f}(X)}\|_{2}$. We make the following observations for $\left|\widetilde{p}_{1}-y\right|$ and $\|\nabla_{a}h(a)|_{a=\bm{f}(X)}\|_{2}$, which hold true for a wide range of real-world learning problems.

• •

  Observation 1: Throughout training, the model tends to be less confident about a positive example being positive than a negative example being negative. In other words, the confidence gap of a positive example $1-\widetilde{p}_{1}=\left|\widetilde{p}_{1}-y\right|$ (when $y=1$) is typically larger than the confidence gap of a negative example $1-\widetilde{p}_{0}=\widetilde{p}_{1}=\left|\widetilde{p}_{1}-y\right|$ (when $y=0$) (see Figure 2(a)). This observation is particularly true for problems like advertising conversion prediction and disease prediction, where there is inherently more ambiguity for the positive class than the negative. For example, in advertising, uninterested users of a product will never click on its ad and convert, but those interested, even after clicking, might make the purchase only a fraction of the time depending on time/money constraints. (See a toy example of this ambiguity in the Appendix A.2.)

• •

  Observation 2: Throughout training, the norm of the gradient vector $\|\nabla_{z}h(z)|_{z=\bm{f}(X)}\|_{2}$ is on the same order of magnitude (has similar distribution) for both the positive and negative examples (Figure 2(b)). This is natural because $\nabla_{a}h(a)|_{a=\bm{f}(X)}$ is not a function of $y$.

As a consequence of Observation 1 and 2, the gradient norm $\|g\|_{2}$ of the positive instances are generally larger than that of the negative ones (Figure 2(c)). Thus, the scoring function $r_{n}(g)=\|g\|_{2}$ is a strong predictor of the unseen label $y$. We name the privacy loss (leak AUC) measured against the attack $r_{n}$ the norm leak AUC. In Figure 2(c), the norm leak AUCs are consistently above $0.9$, signaling a high level of label leakage throughout training.

Attack 2: Direction-based scoring function. We now show that the direction of $g$ (in addition to its length) can also leak the label. For a pair of examples, $(X_{a},y_{a}),(X_{b},y_{b})$, let their respective predicted positive class probability be $\widetilde{p}_{1,a}$, $\widetilde{p}_{1,b}$ and their communicated gradients be $g_{a}$, $g_{b}$. Let $\cos:\operatorname{\mathbb{R}}^{d}\times\operatorname{\mathbb{R}}^{d}\to\operatorname{\mathbb{R}}$ denote the cosine similarity function $\cos(g_{a},g_{b})=g_{a}^{T}g_{b}/(\|g_{a}\|_{2}\|g_{b}\|_{2})$. It is easy to see that $\cos(g_{a},g_{b})=\textrm{sgn}(\widetilde{p}_{1,a}-y_{a})\cdot\textrm{sgn}(\widetilde{p}_{1,a}-y_{b})\cdot\cos(\nabla_{z}h(z)|_{z=\bm{f}(X_{a})},\nabla_{z}h(z)|_{z=\bm{f}(X_{b})})$, where sgn(x) is the sign function which returns $1$ if $x\geq 0$, and $-1$ if $x<0$. We highlight two additional observations that can allow us to use cosine similarity to recover the label.

• •

  Observation 3: When the examples $a,b$ are of different classes, the term $\textrm{sgn}(\widetilde{p}_{1,a}-y_{a})\cdot\textrm{sgn}(\widetilde{p}_{1,a}-y_{b})=-1$ is negative. On the other hand, when examples $a$, $b$ are of the same class (both positive/both negative), this product will have a value of $1$ and thus be positive.

• •

  Observation 4: Throughout training, for any two examples $a,b$, their gradients of the function $h$ always form an acute angle, i.e. $\cos(\nabla_{z}h(z)|_{z=\bm{f}(X_{a})},\nabla_{z}h(z)|_{z=\bm{f}(X_{b})})>0$ (Figure 2(d)). For neural networks that use monotonically increasing activation functions (such as ReLU, sigmoid, $\tanh$), this is caused by the fact that the gradients of these activation functions with respect to its inputs are coordinatewise nonnegative and thus always lie in the first closed hyperorthant.

Since $\cos(g_{a},g_{b})$ is the product of the terms from Observation 3 and 4, we see that for a given example, all the examples that are of the same class result in a positive cosine similarity, while all opposite class examples result in a negative cosine similarity. If the problem is class-imbalanced and the non-label party knows there are fewer positive examples than negative ones, it can thus determine the label of each example: the class is negative if more than half of the examples result in positive cosine similarity; otherwise it is positive. For many practical applications, the non-label party may reasonably guess which class has more examples in the dataset a priori without ever seeing any data—for example, in disease prediction, the percentage of the entire population having a certain disease is almost always much lower than 50%; in online advertising conversion prediction, the conversion rate (fraction of positive examples) is rarely higher than 30%. Note that the non-label party doesn’t need knowledge of the exact sample proportion of each class for this method to work.

To simplify this attack for evaluation, we consider an even worse oracle scenario where the non-label party knows the clean gradient of one positive example $g_{+}$. Unlike the aforementioned practical majority counting attack which needs to first figure out the direction of one positive gradient, this oracle scenario assumes the non-label party is directly given this information. Thus, any protection method capable of defending this oracle attack would also protect against the more practical one. With $g_{+}$ given, the direction-based scoring function $r_{d}$ is simply $r_{d}(g)=\cos(g,g_{+})$. We name the privacy loss (leak AUC) against this oracle attack $r_{d}$ the cosine leak AUC. In practice, we randomly choose a positive class clean gradient from each batch as $g_{+}$ for evaluation. For iterations in Figure 2(e), the cosine leak AUC all have the highest value of $1$ (complete label leakage).

Random perturbation and the isotropic Gaussian baseline. To protect against label leakage, the label party should ideally communicate essential information about the gradient without communicating its actual value. Random perturbation methods generally aim to achieve this goal. One obvious consideration for random perturbation is to keep the perturbed gradients unbiased. In other words, suppose $\tilde{g}$ is the perturbed version of an example’s true gradient $g$, then we want $\operatorname{\mathbb{E}}[\tilde{g}\mid g]=g$. By chain rule and linearity of expectation, this ensures the computed gradients of the non-label party’s parameters $f$ will also be unbiased, a desirable property for stochastic optimization. Among unbiased perturbation methods, a simple approach is to add iid isotropic Gaussian noise to every gradient to mix the positive and negative gradient distribution before sending to the non-label party. Although isotropic Gaussian noise is a valid option, it may not be optimal because 1) the gradients are vectors but not scalars, so the structure of the noise covariance matrix matters. Isotropic noise might neglect the direction information; 2) due to the asymmetry of the positive and negative gradient distribution, the label party could add noise with different distributions to each class’s gradients.

Norm-alignment heuristic. We now introduce an improved heuristic approach of adding zero-mean Gaussian noise with non-isotropic and example-dependent covariance. [Magnitude choice] As we have seen that $\|g\|_{2}$ can be different for positive and negative examples and thus leak label information, this heuristic first aims to make the norm of each perturbed gradient indistinguishable from one another. Specifically, we want to match the expected squared $2$-norm of every perturbed gradient in a mini-batch to the largest squared $2$-norm in this batch (denote by $\|g_{\max}\|_{2}^{2}$). [Direction choice] In addition, as we have seen empirically from Figure 2(e), the positive and negative gradients lie close to a one-dimensional line in $\operatorname{\mathbb{R}}^{d}$, with positive examples pointing in one direction and negative examples in the other. Thus we consider only adding noise (roughly speaking) along “this line”. More concretely, for a gradient $g_{j}$ in the batch, we add a zero-mean Gaussian noise vector $\eta_{j}$ supported only on the one-dimensional space along the line of $g_{j}$. In other words, the noise’s covariance is the rank-$1$ matrix $\operatorname{\mathrm{Cov}}[\eta_{j}]=\sigma_{j}^{2}g_{j}g_{j}^{T}$. To calculate $\sigma_{j}$, we aim to match $\operatorname{\mathbb{E}}[\|g_{j}+\eta_{j}\|_{2}^{2}]=\|g_{\max}\|_{2}^{2}$. A simple calculation gives $\sigma_{j}=\sqrt{\|g_{\max}\|_{2}^{2}/\|g_{j}\|_{2}^{2}-1}$. Since we align to the maximum norm, we name this heuristic protection method max_norm. The advantage of max_norm is that it has no parameter to tune. Unfortunately, it does not have a strong theoretical motivation, cannot flexibly trade-off between model utility and privacy, and may be broken by some unknown attacks.

Motivated by the above issues of max_norm, we next study how to achieve a more principled trade-off between model performance (utility) and label protection (privacy). To do so, we directly minimize the worst-case adversarial scoring function’s leak AUC under a utility constraint. We name this protection method Marvell (optiMized perturbAtion to pReVEnt Label Leakage).

Noise perturbation structure. Due to the distribution difference between the positive and negative class’s cut layer gradients, we consider having the label party additively perturb the randomly sampled positive $g^{(1)}$ and negative $g^{(0)}$ gradients with independent zero-mean random noise vectors $\eta^{(1)}$ and $\eta^{(0)}$ with possibly different distributions (denoted by $D^{(1)}$ and $D^{(0)}$). We use $\widetilde{P}^{(1)}$ and $\widetilde{P}^{(0)}$ to denote the induced perturbed positive and negative gradient distributions. Our goal is to find the optimal noise distributions $D^{(1)}$ and $D^{(0)}$ by optimizing our privacy objective described below.

Privacy protection optimization objective. As the adversarial non-label party in our threat model is allowed to use any measurable scoring function $r$ for label recovery, we aim to protect against all such scoring functions by minimizing the privacy loss of the worst case scoring function measured through our leak AUC metric. Formally, our optimization objective is $\min_{D^{(1)},D^{(0)}}\max_{r}\textrm{AUC}(r)$. Here to compute $\textrm{AUC}(r)$, the $\textrm{FPR}_{r}(t)$ and $\textrm{TPR}_{r}(t)$ needs to be computed using the perturbed distributions $\widetilde{P}^{(1)}$ and $\widetilde{P}^{(0)}$ instead of the unperturbed $P^{(1)}$ and $P^{(0)}$ (Section 3.2). Since AUC is difficult to directly optimize, we consider optimizing an upper bound through the following theorem:

From Theorem 1 (proof in Appendix A.3), we see that as long as the sum KL divergence is below $4$, the smaller sumKL is, the smaller $\max_{r}\textrm{AUC}(r)$ is. ($1/2+\sqrt{\epsilon}/2-\epsilon/8$ decreases as $\epsilon$ decreases.) Thus we can instead minimize the sum KL divergence between the perturbed gradient distributions:

Utility constraint. In an extreme case, we could add infinite noise to both the negative and positive gradients. This would minimize (1) optimally to $0$ and make the worst case leak AUC $0.5$, which is equivalent to a random guess. However, stochastic gradient descent cannot converge under infinitely large noise, so it is necessary to control the variance of the added noise. We thus introduce the noise power constraint: $p\cdot\mathrm{tr}(\operatorname{\mathrm{Cov}}[\eta^{(1)}])+(1-p)\cdot\mathrm{tr}(\operatorname{\mathrm{Cov}}[\eta^{(0)}])\leq\;P$, where $p$ is the fraction of positive examples (already known to the label party); $\mathrm{tr}(\operatorname{\mathrm{Cov}}[\eta^{(i)}])$ denotes the trace of the covariance matrix of the random noise $\eta^{(i)}$; and the upper bound $P$ is a tunable hyperparameter to control the level of noise: larger $P$ would achieve a lower sumKL and thus lower worst-case leak AUC and better privacy; however, it would also add more noise to the gradients, leading to slower optimization convergence and possibly worse model utility. We weight each class’s noise level $\mathrm{tr}(\operatorname{\mathrm{Cov}}[\eta^{(i)}])$ by its example proportion ($p$ or $1-p$) since, from an optimization perspective, we want to equally control every training example’s gradient noise. The constrained optimization problem becomes:

Additional details of Marvell. By Theorem 2, our optimization problem over two positive semidefinite matrices is reduced to a much simpler 4-variable optimization problem. We include a detailed description of how the constants in the problem are estimated in practice and what solver we use in a full description of the Marvell algorithm in Appendix LABEL:appsubsec:marvell_details. Beyond optimization details, it is worth noting how to set the power constraint hyperparameter $P$ in Equation 2 in practice. As directly choosing $P$ requires knowledge of the scale of the gradients in the specific application and the scale could also shrink as the optimization converges, we instead express $P=s\left\|\Delta g\right\|_{2}^{2}$, and tune for a fixed hyperparameter $s>0$. This alleviates the need to know the scale of the gradients in advance, and the resulting value of $P$ can also dynamically change throughout training as the distance between the two gradient distributions’ mean $\left\|\Delta g\right\|_{2}$ changes.

After showing Marvell can provide strong privacy protection against our identified attacks, we now see how well it can preserve utility by comparing its privacy-utility tradeoff against other protection baselines: no_noise, isotropic Gaussian (iso), and our proposed heuristic max_norm. Similar to how we allow Marvell to use a power constraint to depend on the current iteration’s gradient distribution through $P=s\|\Delta g\|_{2}^{2}$, we also allow iso to have such type of dependence—specifically, we add $\eta\sim\mathcal{N}(\bm{0},(t/d)\cdot\|g_{\max}\|_{2}^{2}I_{d\times d})$ to every gradient in a batch with $t$ a tunable privacy hyperparameter to be fixed throughout training. To trace out the complete tradeoff curve for Marvell and iso, we conduct more than 20 training runs for each protection method with a different value of privacy hyperparameter ($s$ for Marvell, $t$ for iso) in each run on every dataset. (Note that no_noise and max_norm do not have privacy hyperparameters.)

We present the tradeoffs between privacy (measured through norm and cosine leak AUC at cut layer/first layer) and utility (measured using test loss and test AUC) in Figure 4. To summarize the leak AUC over a given training run, we pick the 95% quantile over the batch-computed leak AUCs throughout all training iterations. This quantile is chosen instead of the mean because we want to measure the most-leaked iteration’s privacy leakage (highest leak AUC across iterations) to ensure the labels are not leaked at any points during training. $95\%$ quantile is chosen instead of the max ($100\%$) as we want this privacy leak estimate to be robust against randomness of the training process.

Privacy-Utility Tradeoff comparison results. In measuring the privacy-utility tradeoff, we aim to find a method that consistently achieves a lower leak AUC (better privacy) for the same utility value.

• •

  [Marvell vs iso] As shown in Figure 4, Marvell almost always achieves a better tradeoff than iso against both of our proposed attacks at both the cut layer and the first layer on both the ISIC and Criteo datasets. It is important to note that although the utility constraint is in terms of training loss optimization, Marvell’s better tradeoff still translates to the generalization performance when the utility is measured through test loss or test AUC. Additionally, despite achieving reasonable (though still worse than Marvell) privacy-utility tradeoff against the norm-based attack, iso performs much worse against the direction-based attack: on ISIC, even after applying a significant amount of isotropic noise (with $t>20$),  iso’s cosine leak AUC is still higher than $0.9$ at the cut layer (Figure 4(b,f)). In contrast, Marvell is effective against this direction-based attack with a much lower cosine leak AUC $\approx 0.6$.

• •

  [max_norm  heuristic] Beyond Marvell, we see that our heuristic approach max_norm can match and sometimes achieve even lower (Figure 4(a,f,i)) leak AUC value than Marvell at the same utility level. We believe this specifically results from our norm and direction consideration when designing this heuristic. However, without a tunable hyperparameter, max_norm cannot tradeoff between privacy and utility. Additionally, unlike Marvell which is designed to protect against the entire class of adversarial scoring functions, max_norm might still fail to protect against other future attack methods beyond those considered here.

In summary, our principled method Marvell significantly outperforms the isotropic Gaussian baseline, and our proposed max_norm heuristic can also work particularly well against the norm- and direction-based attacks which we identified in Section 2.