# LTU Attacker for Membership Inference
## 4 Theoretical Analysis of Naive Attackers  
We present several theorems outlining weaknesses of the Defender that are particularly easy to exploit by a black-box LTU Attacker, not requiring training a sophisticated attack model \(\mathcal{M}_{A}\) (we refer to such attackers as \"naive\"). First, we prove, in the context of the LTU procedure, theorems related to an already known result connecting privacy and over-fitting: Defender trainers that overfit the Defender data lend themselves to easy attacks [8]. The attacker can simply exploit the loss function of the Defender (which should be larger on Reserved data than on Defender data). The last theorem concerns deterministic trainers \(\mathcal{T}_{D}\): We show that the LTU Attacker can defeat them with 100% accuracy, under mild assumptions. Thus, Defenders must introduce some randomness in their training algorithm to be robust against such attacks [23]. Throughout this analysis, we use the fact that our LTU methodology simplifies the work for the LTU Attacker since it is always presented with pairs of samples for which exactly one is in the Defender data. This can give it very simple attack strategies. For example, for any real valued function \(f(x)\), with \(x\in\mathcal{D}_{S}\), let \(r\) be drawn uniformly from \(\mathcal{D}_{R}\) and \(d\) be drawn uniformly from \(\mathcal{D}_{D}\), and define:  
\[p_{R} =\Pr_{ \begin{subarray}{c}u_{1}\sim\mathcal{D}_{R}\\ u_{2}\sim\mathcal{D}_{D}\end{subarray} }[f(u_{1})>f(u_{2})] \tag{3}\] \[p_{D} =\Pr_{ \begin{subarray}{c}u_{1}\sim\mathcal{D}_{R}\\ u_{2}\sim\mathcal{D}_{D}\end{subarray} }[f(u_{1})<f(u_{2})] \tag{4}\]  
Thus, \(p_{R}\) is the probability that discriminant function \(f\) \"favors\" Reserved data while \(p_{D}\) is the probability with which it favors the Defender data. \(p_{R}>p_{D}\) occurs if for a larger number of random pairs \(f(x)\) is larger for Reserved data than for Defender data. If the probability of a tie is zero, then \(p_{R}+p_{D}=1\). **Theorem 1**. : _If there is any function \(f\) for which \(p_{R}>p_{D}\), an LTU Attacker exploiting that function can achieve an accuracy \(A_{ltu}\geq\frac{1}{2}+\frac{1}{2}(p_{R}-p_{D})\)._  
Proof. : A simple attack strategy would be predict that the unlabeled sample with the smaller value of \(f(x)\) belongs to the _Defender_ data, with ties (i.e., when \(f(u_{1})=f(u_{2})\)) decided by tossing a fair coin. This strategy would give a correct prediction when \(f(r)>f(d)\), which occurs with probability \(p_{R}\), and would be correct half of the time when \(f(r)=f(d)\), which occurs with probability \((1-(p_{r}+p_{d}))\). This gives a classification accuracy:  
\[A_{ltu}=p_{R}+\frac{1}{2}(1-p_{R}-p_{D})=\frac{1}{2}+\frac{1}{2}(p_{R}-p_{D})\;. \tag{5}\]  
Figure 2: Taxonomy of LTU Attacker. **Top:** Any LTU Attacker has available the Defender trainer \(\mathcal{T}_{D}\), the trained Defender model \(\mathcal{M}_{D}\), and attack data \(\mathcal{D}_{A}\) including (almost) all the Defender data \(\mathcal{D}_{D}\) and Reserved data \(\mathcal{D}_{R}\)\(\mathcal{D}_{A}=\mathcal{D}_{D}-\{\texttt{membship}(d)\}\cup\mathcal{D}_{R}-\{ \texttt{membship}(r)\}\). However, it may use only part of this available knowledge to conduct attacks. \(r\) and \(d\) are two labeled examples belonging \(\mathcal{D}_{R}\) and \(\mathcal{D}_{D}\), respectively, and \(u_{1}\) and \(u_{2}\) are two unlabeled examples, one from \(\mathcal{D}_{R}\) and one from \(\mathcal{D}_{D}\) (ordered randomly). **Bottom Left:** Attacker \(\mathcal{M}_{A}\) targets only the trained Defender model \(\mathcal{M}_{D}\). **Bottom Right:**\(\mathcal{M}_{A}\) targets both \(\mathcal{M}_{D}\) and its trainer \(\mathcal{T}_{D}\). This is similar to the threshold adversary of [8], except that the LTU Attacker does not need to know the exact conditional distributions, since it can discriminate pairwise.