Unit 8 exercises

At \(\tau_1\), \(\mathrm{TPR} = 300/1{,}000 = 0.30\) and \(\mathrm{FPR} = 100/1{,}000 = 0.10\), so the advantage is 0.20, the balanced accuracy is \((1 + 0.20)/2 = 0.60\), and \(300/400 = 75\%\) of the member guesses are right. At \(\tau_2\), \(\mathrm{TPR} = 0.02\), \(\mathrm{FPR} = 0.002\), the advantage is 0.018, the balanced accuracy is 0.509, and \(20/22 \approx 91\%\) of the member guesses are right.

Advantage and balanced accuracy favor \(\tau_1\). The stricter threshold is the greater violation for the 20 people it identifies, because the attacker is right about them nine times in ten, whereas at \(\tau_1\) one guess in four is wrong and the attacker cannot tell which. This is why Carlini et al. (2022) evaluate attacks by the true positive rate at a low false positive rate, here 2% at 0.2%.

(a) \(e^2 = 7.389\). At a false positive rate of 0.001 the ceiling is \(7.389 \times 0.001 + 10^{-6}\), about 0.0074, and at 0.01 it is about 0.0739. An attacker may identify at most about 7.4 times as many members as a random guesser at either operating point.

(b) The advantage bound is \((e^2 - 1)/(e^2 + 1)\), which equals \(6.389/8.389 \approx 0.762\), so the balanced accuracy is at most \((1 + 0.762)/2 \approx 0.881\). The bound of Yeom et al. (2018) gives \(e^2 - 1 \approx 6.39\), larger than 1 and therefore uninformative. At \(\epsilon = 2\) the guarantee is meaningful at low false positive rates and weak as an average, since the bound still allows an attack whose balanced accuracy is 88%, far from the 50% of guessing. Measured attacks are usually far weaker than these ceilings, but only the ceilings are guaranteed.

(a) \(h_j = \sum_i W_{ij} a_i + b_j\), so by the chain rule

which is the \((i, j)\) entry of \(a\,u^\top\). Then

whose square root is \(\lVert a \rVert_2 \lVert u \rVert_2\).

(b) \(\partial \ell / \partial b = u\), so the squared norm over \(W\) and \(b\) is \(\lVert a \rVert_2^2 \lVert u \rVert_2^2 + \lVert u \rVert_2^2\), which equals \(\lVert u \rVert_2^2 (\lVert a \rVert_2^2 + 1)\). Summing this over layers gives the squared norm of the full gradient.

(c) DP-SGD must clip each example's full gradient to norm \(C\) before summing, so it needs every per-example norm. Ordinary backpropagation returns only the batch sum. The identity gives all per-example norms from quantities the forward and backward passes already compute, the inputs \(a\) and the output gradients \(u\) of each example, without forming a gradient matrix per example. Write \(a^{(k)}\) and \(u^{(k)}\) for the input and the output gradient of example \(k\) in the batch, \(g_k\) for its full gradient, and \(c_k = \min(1, C/\lVert g_k \rVert_2)\) for its clipping factor, and let \(c\) be the vector of these factors. If the rows of the matrices \(A\) and \(U\) are \(a^{(k)\top}\) and \(u^{(k)\top}\), the clipped sum for the layer equals a single matrix product,

In the form of Lesson 8.3, the noise standard deviation is \(\sigma\Delta_2\) with \(\sigma > \sqrt{2 \ln(1.25/\delta)}/\epsilon\). Here \(2 \ln(1.25 \times 10^6)\) equals \(2 \times 14.04 = 28.08\), whose square root is 5.30, so \(\sigma > 5.30/0.5 \approx 10.6\), and with \(\Delta_2 = 1\) the standard deviation must be about 10.6. The published count is 40 plus Gaussian noise with standard deviation about 10.6, so it lies within about \(\pm 10.6\) of 40 two times in three and within about \(\pm 21\) in 95% of releases. For a single small count this is a large error, which is the privacy-utility trade-off in its simplest form; for a model trained on many examples, the noise in DP-SGD is spread over many steps and averaged over large batches.

(a) \(\Phi^{-1}(0.75) = 0.6745\) and \(\Phi^{-1}(0.25) = -0.6745\), so

(b) The first perturbation has L2 norm \(\sqrt{16 \times 0.1^2} = 0.4 > 0.337\), so it is not covered; the prediction may or may not change. The second has norm \(\sqrt{4 \times 0.15^2} = 0.3 < 0.337\), so the smoothed classifier's prediction provably does not change (with the confidence level of the Monte Carlo bound).

(c) Its L2 norm is \(0.03 \sqrt{3{,}072} \approx 1.66\), far outside the radius, so the certificate says nothing about it. An L2 certificate covers small changes to a few pixel values or very small changes to many, and every other threat model needs its own analysis.

(a) A reasonable prediction is that recall falls much less than halfway. The forest still sees about half the brute-force records labeled as attacks, and the relabeled records lie among records that keep the attack label, so the trees disagree. Each tree grows until its leaves are pure, and a test brute-force record falls in an attack leaf in some trees and in a normal leaf in others. The forest's score, the average over its trees, drops but stays above most normal traffic.

(b) Replace y_poison[bf_train] = 0 by these three lines, indented inside the same if block,

rng = np.random.default_rng(7)
half = rng.choice(bf_train, len(bf_train) // 2, replace=False)
y_poison[half] = 0

Run the cell, then repeat with seeds 8 and 9. The forest's recall on test brute-force attacks stays within a few points of its clean value for all three seeds, far above the fully flipped value. The scores of brute-force traffic drop, but they stay above the alert-budget threshold, because each region of feature space that holds brute-force records still contains many records labeled as attacks. The attacker needed to relabel nearly the whole family, and relabeling half of it achieved little. The logistic regression loses more recall than the forest, but it also keeps far more than in the fully flipped case.

(c) The out-of-fold label check. A brute-force record labeled normal is scored by a model trained on the other folds, which still contain many correctly labeled brute-force records, so its out-of-fold attack score is high and it is flagged. The check works because the attack leaves contradictory labels for similar records; it would work much less well if the attacker relabeled the whole family, as in the lab's original cell, since then no correctly labeled examples remain to contradict the flipped ones.

Goals. An availability attack degrades the classifier so it blocks many legitimate URLs, which users then learn to ignore. A targeted attack makes the attacker's own future phishing domains pass. A backdoor makes any URL with a chosen pattern (for example a path component) pass.

Capabilities. Training data control and label control through user reports, since anyone can create accounts and report or un-report URLs; clean-label poisoning is also possible, because the attacker can host genuinely benign pages on domains it will later use for phishing so that they are labeled benign. The attacker has no model or source code control. As for knowledge, the attacker can probe the deployed classifier by sending test emails, and the feature set of URL classifiers is often public.

Controls. (1) Limit and weight each reporter's influence. Cap the number of labels any account contributes per week, weight new or low-reputation accounts low, and record the provenance of every label so that a source found to be malicious can be removed as a group. (2) Hold labels that move a URL from blocked to allowed for review or require agreement among several independent reporters before they enter training, since "not phishing" labels are the ones a phisher benefits from. (3) Compare each retrained model with the previous one on a trusted, curated evaluation set that does not come from user reports, including recent confirmed phishing campaigns, and refuse to deploy a model that regresses on it. A statistical filter such as the out-of-fold label check can be added as a fourth control, but it cannot be the only one, because clean-label poison carries correct labels.