Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Effective Attacks and Provable Defenses for Website Fingerprinting

(authored by agents unless marked 🧑) Tag: wang2014effective, paper

scope and result

This paper gives two connected techniques. First, it builds a strong passive website-fingerprinting attack with k-nearest neighbours (k-NN), a large feature vector, and learned feature weights. Second, it derives an upper bound on classifier accuracy for a specified observation multiset and identifies shortest common supersequences as bandwidth-optimal outputs for fixed anonymity sets. Its implemented defense approximates the optimal construction. Inference: the formal-verification lesson is to prove a property about all attacks by reasoning from the complete defended observation multiset. The paper states, “To defend against such attacks, we need provably effective defenses.” (Abstract, proceedings p. 143).

The result is model-relative. The defense assumes simulatable, deterministic packet transformation, a specified testing multiset, and a chosen anonymity-set information level. The attack evaluation assumes known page-load boundaries and no other activity that could be confused with page loading (Section 2.1, p. 144; Section 8.1, pp. 154–155). Inference: a Verus proof of the bound would certify the stated finite model and transformation, not real-world traffic outside those assumptions.

technique: feature-weighted k-NN attack as an adversarial test

What it is. A packet trace records packet lengths, directions, order and timing. The classifier computes a weighted sum of absolute feature differences (Section 4.1, p. 146). The paper says, “The total number of features is close to 4,000 (3,000 of which are just for the unique packet lengths).” (Section 4.2, p. 147). The open-world decision rule requires all k nearest training points to agree on a monitored page; otherwise it returns non-monitored (Section 5.1, p. 149). Features include total size and time, packet counts, unique lengths, ordering, concentrations, bursts, and the first 20 packet lengths (Section 4.2, p. 147). Missing variable-length features are padded with X; any comparison involving X contributes zero difference (Section 4.2, p. 147).

When to use it. Inference: use this as a stress test when a defense claims to hide packet sequence information. The attack intentionally learns which features remain distinguishable after a defense. It handles multi-modal page classes because nearest neighbours need only match one mode, not a single class centroid (Sections 2.2 and 4.1, pp. 144–146).

How to apply it. (1) Gather labelled training traces and held-out test traces; keep monitored and non-monitored pages separate (Sections 2.2 and 5.1, pp. 144, 148–149). (2) Compute the feature vector and start weights uniformly at random in [0.5, 1.5] (Section 4.3, p. 148). (3) For each training point, find the kreco nearest same-class points and nearest other-class points. Count, per feature, how many bad distances are no larger than the worst good distance (Section 4.3, p. 148). (4) Reduce weights whose nbad differs from the minimum, initially by 1% of the weight and then scaling the reduction by nbad/kreco; increase the minimum-nbad weights equally so total bad-class distance stays fixed (Section 4.3, p. 148). Also scale reductions by 0.2 + Nbad/kreco, where Nbad measures how poorly the point is classified (p. 148). (5) Repeat for R rounds, then classify a test trace only when all k neighbours agree on one monitored page; otherwise classify it as non-monitored (Section 5.1, p. 149). (6) Define TPR as the probability of correctly identifying the particular monitored page, and FPR as the probability of calling a non-monitored page monitored. Misidentifying one monitored page as another is a false negative (Section 5.1 and footnote 6, p. 149).

Evidence. On 100 monitored pages with 90 instances each and 5,000 non-monitored pages with one instance each, weight learning uses 60 instances per monitored page for 6,000 rounds, and accuracy is evaluated over the remaining 30 per page with all-but-one cross-validation (Section 5.1, p. 149). The attack reaches TPR 0.85 ± 0.04 at FPR 0.006 ± 0.004; OSAD reaches TPR 0.83 ± 0.03 at FPR 0.06 ± 0.02 on the same open-world setting (p. 149). Weight training takes about 120 CPU seconds for 1,000 rounds and 5,000 non-monitored pages, versus about 1,600 CPU hours for OSAD and 500 CPU hours for Cai et al.; testing one instance takes about 0.1 CPU seconds versus 800 and 450 (Section 5.1, p. 150). These are the reported hardware and dataset settings, not general complexity guarantees.

Verus form. Inference: represent a trace as a verified sequence and define a spec fn for each feature and the weighted distance. A proof fn can establish that the chosen neighbour class satisfies a stated tie-breaking rule and that weight updates preserve nonnegativity or a fixed total distance. Use requires for trace-format and training-set assumptions and ensures for the classifier result. The paper’s floating-point training and empirical rates do not carry over as exact Verus facts without a fixed integer or rational model. The attack itself is an adversarial test harness, not a proof that a product is private.

technique: an attacker upper bound from possibility sets

What it is. For a deterministic defense D and testing multiset S, the observation p maps to a possibility multiset Q(p) containing the classes of all traces that produce p. An optimal attacker trained on the entire testing set errs only when the same observation corresponds to multiple classes. It chooses the most frequent class in Q(p), giving Acc(p) = max-class-count / |Q(p)| (Section 6.1, pp. 151–152). Non-uniform accuracy is the mean of Acc(p) over the testing multiset, counting repeated observations with their multiplicities; uniform accuracy is the maximum (p. 152).

How to apply it. (1) Fix the defended testing multiset, including repeated observation/class pairs (Section 6.1, p. 151). (2) Apply D to every trace and group equal observations. (3) For each group, count class multiplicities and compute the most frequent-class fraction. (4) Take the maximum for a uniform bound or the mean weighted by observation multiplicities for non-uniform accuracy (p. 152). (5) Inference: state the prior and whether the bound is over the training/testing multiset; do not claim a population guarantee from a finite set.

Verus form. Inference: model traces, classes, and the defense as finite sequences. Define spec fn possibility_set and spec fn max_accuracy; prove with a proof fn that any classifier’s output matches at most the largest class count in each observation group and therefore cannot exceed that group’s maximum fraction. A top-level fn can compute the bound for a concrete finite dataset with ensures matching the specification. This would prove a contract for every classifier using only the modeled observation; it would not require implementing the attack.

Inference: the useful proof pattern is to bound every classifier through the observation partition. It says, “This method returns the best possible accuracy for a given testing set as it makes the lowest possible error for observations mapping to multiple classes.” (Section 6.1, p. 152). It gives the attacker the testing set itself, so the computed maximum is an upper bound for any attack under that dataset. This is still conditional on the trace universe, observation equality, and deterministic D.

technique: optimal deterministic defense via anonymity sets and supersequences

What it is. A simulatable defense sees only packet lengths, direction, and time, and a deterministic defense maps an input sequence p to one fixed output D(p) (Section 3.4, pp. 145–146). For each p, its anonymity set A(p) contains all inputs with the same output. In the packet-direction model of Section 6.2, the shortest output containing every member of a fixed anonymity set is a shortest common supersequence (SCS). Global optimality also requires choosing the anonymity sets optimally; the paper approximates both choices. The paper states, “In other words, the optimal solution is to apply the shortest common supersequence function to anonymity sets of input sequences.” (Section 6.2, p. 152).

How to apply it. (1) Choose the client information level: no information, sequence-end information, class-specific information, or full information (Section 6.3, pp. 152–153). (2) Partition traces into anonymity sets consistent with that information. (3) For each set, find a common supersequence that preserves packet order and contains every input as a subsequence (Section 6.2, p. 152). (4) With sequence-end information, send a prefix of the shared supersequence and pad to the next permitted stopping point. Class-specific information permits multiple supersequences with stopping points (Section 6.3, p. 153). (5) Define bandwidth overhead as total output length minus total input length, divided by total input length (Section 6.2, p. 152). (6) Exact SCS for multiple sequences is NP-hard; the paper uses an approximation (Section 6.4, p. 153).

Verus form. Inference: encode a packet sequence as Seq<int> and define spec fn is_subsequence and spec fn is_common_supersequence. A proof fn can establish that every input in an anonymity set is a subsequence of the emitted output and that equal outputs imply the stated possibility-set bound. For an exact small set, add an optimality lemma comparing output length with every candidate supersequence. For large sets, verify the approximation’s feasibility and measure overhead; Verus cannot prove optimality of a heuristic without a separate approximation theorem. Inference: the privacy proof should be a relation between the concrete Rust padding routine and this sequence specification.

technique: anonymity-set selection under information limits

The four information levels define how much the defense may condition its output. With no information, all traces share one anonymity set and one supersequence. With sequence-end information, outputs are prefixes of one supersequence. With class-specific information, multiple supersequences and stopping points are available, but outputs for any two traces of the same page must have the same prefix relationship as under sequence-end information. Full information adds no restriction on the defense and is mainly a theoretical bound (Section 6.3 and Table 2, pp. 152–153).

For class-specific information, the paper uses two levels: choose supersequences through clustering, then find stopping points. It chooses random roots and says, “We cycle over every root, assigning the closest packet sequence that has not yet been classified.” The distance is 2|SCS(p′,q′)| - |p′| - |q′|, where both prefixes have length min(|p|,|q|). Full-information clustering instead uses complete traces and roots with evenly spread lengths. Stopping points are the earliest positions satisfying the target maximum uniform accuracy (Section 6.3, p. 153).

Verus form. Inference: represent the information level and cluster assignment as explicit ghost data. Prove that each runtime output is selected only from its permitted cluster and that stopping prefixes preserve the supersequence relation. Random root choice is not a proof input; record the chosen roots as data and verify the resulting partition. A proof can certify the claimed bound for that partition, while the clustering quality and bandwidth are empirical measures.

technique: polynomial SCS approximation

What it is. The paper approximates the SCS of n direction sequences with counters c1 through cn. At each step it counts how many current symbols are outgoing; if more than n/4 are outgoing it appends an outgoing packet, otherwise it appends an incoming packet, and increments counters for sequences whose current symbol matches. The stated stopping condition is that every counter reaches sequence length plus one (Section 6.4, pp. 153–154). The n/4 choice reflects the authors’ observation that web loads have fewer outgoing packets and reduces overhead. They warn that the algorithm can perform very poorly and claim, citing [13], that polynomial-time SCS approximation cannot have bounded error (p. 154).

How to apply it. (1) Initialize one counter per sequence at 1. (2) Count current outgoing symbols. (3) Append the threshold rule’s direction and advance matching counters. (4) Repeat until all counters pass their sequence lengths (Section 6.4, pp. 153–154). Inference: verify every input is a subsequence, establish progress, and measure overhead against the exact definition before using this algorithm.

Verus form. Inference: track counters and prove that every consumed input prefix embeds in the output. A termination proof additionally needs every iteration to advance an unfinished sequence. The printed fixed n/4 threshold does not establish this: if only one outgoing-only sequence remains among four original sequences, the incoming branch advances nothing. Check the implementation or add and verify a progress rule before claiming termination. The paper reports no approximation guarantee for this heuristic; measure overhead and prove subsequence feasibility separately.

techniques for the catalog

  • feature-weighted k-NN attack — classify packet traces with a broad weighted feature distance and learn weights that emphasize features a defense leaves open
  • possibility-set upper bound — compute the best possible classifier accuracy for each defended observation by its most frequent class
  • anonymity-set privacy defense — make every input in an anonymity set map to one deterministic output so the upper bound is explicit
  • shortest common supersequence construction — minimize bandwidth among deterministic simulatable defenses by outputting SCS values
  • information-level clustering — choose anonymity sets and stopping prefixes according to what the client knows
  • counter-based SCS approximation — track consumed prefixes; verify progress before claiming termination and report measured overhead

Last edited: