# Calibrating the Attack to Sensitivity in Differentially Private Mechanisms
## 2 System Model and Its Components
### Problem Definition
#### 2.1.1 First-Order Statistics of \(X_{a}\)  
Our first approach is inspired by [8] where the authors determine statistical thresholds for the adversary's hypothesis problem which is set to decide a given dataset entry is included in a dataset \(D\) or its neighbor \(\tilde{D}\). This approach is adapted to the problem of detecting a strong adversary who does not only want to discover all the entries of a dataset but also wants to harm it. Accordingly, we set the following hypotheses where the null and alternative hypotheses are respectively translated into DP noise distribution with and without the bias induced by the attacker.  
\[\begin{split} H_{0}:&\text{defender fails to detect the attack}\\ H_{1}:&\text{defender detects the attack}\end{split} \tag{7}\]  
The hypothesis testing problem defined above in (7) can be translated into deciding on the DP noise distribution with its parameters. Here \(H_{0}\) and \(H_{1}\) correspond to DP noise following the probability distributions \(p_{0}\) with mean \(\mu_{0}\) and \(p_{1}\) with mean \(\mu_{1}\), respectively. Therefore, the decision boils down to choosing between \(Y_{0}-\sum_{i=1}^{n}X_{i}=Z\) and \(Y_{0}-\left[\sum_{i=1}^{n}X_{i}+X_{a}\right]\). Hence the shift in the location due to the addition of \(X_{a}\) to the dataset is \(\Delta\mu=\mu_{1}-\mu_{0}\). The corresponding likelihood ratio for this problem yields  
\[\Lambda=\frac{\mathcal{L}(p_{1})}{\mathcal{L}(p_{0})}\lessneq_{H_{1}}^{H_{0}}\kappa \tag{8}\]  
where \(\mathcal{L}(.)\) denotes the likelihood function for the corresponding hypothesis and \(\kappa\) is some positive number to be determined. Such a threshold defines the critical region in statistical hypothesis tests where the null hypothesis is rejected. This approach results in a precise trade-off between the attacker's advantage (or the bias induced by the adversary) \(\Delta\mu\), the sensitivity \(s\) and the privacy parameter \(\epsilon\) of the differentially private mechanism to characterize the threshold for rejecting the null hypothesis, i.e., detecting the attack, as a function of the error probabilities.  
\(\alpha\) and \(\beta\) respectively denote type I and type II error probabilities which are defined for the hypothesis testing problem in (7) as follows:  
\[P_{FA}=\alpha =\Pr[H_{0}\text{ reject}|H_{0}\text{ is true}] \tag{9}\] \[P_{MD}=\beta =\Pr[H_{1}\text{ reject}|H_{1}\text{is true}]. \tag{10}\]  
Based on the definition of \(\alpha\), also called the _probability of false-alarm_, we denote its complement by \(\bar{\alpha}=1-\alpha\). Similarly, due to (10), the complement of type II error probability (or the _probability of mis-detection_) is denoted by \(\bar{\beta}=1-\beta\). The probability of detection \(\bar{\beta}\) (i.e., correctly deciding \(H_{1}\)) is also called the _power of the test_ in the statistics or the recall in machine learning terminology.  
According to the Neyman-Pearson Theorem [18], the likelihood ratio compared against some positive integer defines the best critical region of size \(\alpha\) for testing a simple hypothesis against an alternative simple hypothesis with the largest (or equally largest) power of the test. An extension of this result to testing against a composite alternative hypothesis is also possible. Such an extension is called _uniformly most powerful test_ since such a test with the best critical region of size \(\alpha\) is conducted for each possible value of the alternative hypothesis. Once we define the critical region for deciding between \(H_{0}\) and \(H_{1}\) in (7) as a function of \(\Delta\mu\), the privacy parameter \(\epsilon\) and the sensitivity \(s\), we will derive the error probabilities and the power of the test analytically as well as compute and depict them numerically.