PaperlayerView exact revision on arXiv

Source-linked AI summary

k-fingerprinting: a Robust Scalable Website Fingerprinting Technique

Jamie Hayes, George Danezis

arXiv:1509.00789v3cs.CR

TL;DR

Website fingerprinting can reveal pages visited through encrypted or anonymized connections because Tor does not significantly alter traffic patterns. The paper introduces k-fingerprinting using packet-sequence features and multiple fingerprints for classification, reporting improved speed and accuracy with low false positives at large world sizes. It also finds that vulnerability varies across web resources and that changing website content can degrade attack accuracy.

  • Problem

    Encrypted or anonymized connections such as Tor still leak information through the order, timing, and volume of requested resources, enabling website fingerprinting attacks.

  • Method

    k-fingerprinting extracts packet-sequence features, evaluates TPR, FPR, and BDR, and varies feature selection and the number of fingerprints used for classification.

  • Results

    k-fingerprinting improves on state-of-the-art attacks in speed and accuracy; a fingerprint length of 20 achieves TPR 0.87 and FPR 0.013, with diminishing returns thereafter.

  • Takeaways & Limitations

    Classification errors are non-uniform across pages, allowing attackers to estimate per-page error rates and select targets with low misclassification rates.

  • Takeaways & Limitations

    Changing website content can degrade accuracy, with news and social media sites expected to degrade faster than stable landing pages.

Abstract

from arXiv · show

Website fingerprinting enables an attacker to infer which web page a client is browsing through encrypted or anonymized network connections. We present a new website fingerprinting technique based on random decision forests and evaluate performance over standard web pages as well as Tor hidden services, on a larger scale than previous works. Our technique, k-fingerprinting, performs better than current state-of-the-art attacks even against website fingerprinting defenses, and we show that it is possible to launch a website fingerprinting attack in the face of a large amount of noisy data. We can correctly determine which of 30 monitored hidden services a client is visiting with 85% true positive rate (TPR), a false positive rate (FPR) as low as 0.02%, from a world size of 100,000 unmonitored web pages. We further show that error rates vary widely between web resources, and thus some patterns of use will be predictably more vulnerable to attack than others.

1 Introduction

Website fingerprinting exploits traffic metadata that remains visible through encryption and Tor to classify which web page a client visits. The paper introduces k-fingerprinting, using random forests and fingerprint distances for open-world identification.

  • 1 Introduction: Traffic timing, ordering, volume, and resource-request patterns can reveal web pages despite encryption or Tor.Traditional encryption hides content but not metadata, while Tor does not significantly alter traffic shape.
  • 1 Introduction: Website fingerprinting trains a classifier on extracted traffic features to identify monitored pages from passively collected traces.The attack is formulated as classification over n web pages.
  • 1 Introduction: k-fingerprinting extracts traffic fingerprints with random forests and uses distances between fingerprints to support open-world identification.Each tree maps a feature vector to a leaf identifier, forming the fingerprint vector.
  • 1 Introduction: The attack classifies a test trace using the closest k training fingerprints and can trade true positive rate against false positive rate by varying k.The paper uses Hamming distance and requires agreement among the k closest labels in its described procedure.
  • 1 Introduction: The paper evaluates attack feasibility with TPR, FPR, and Bayesian Detection Rate, where BDR measures the probability that a recognized prediction is correct.BDR is presented as the practical measure of whether the classifier made a correct prediction.

4 Data gathering

The evaluation combines standard-browser and Tor traffic across monitored and unmonitored websites, including censored pages and Tor hidden services. These datasets support comparisons across realistic website populations and prior attacks.

  • 4 Data gathering: The study collects DSNorm through a standard browser and DSTor through Tor to evaluate website fingerprinting under both access conditions.DSNorm contains 30 instances from each of 55 monitored pages and 7,000 unmonitored pages.
  • 4 Data gathering: Traffic traces are collected for 20 seconds without caches, with two-second gaps between page loads and repeated monitored-page batches.The collection uses Amazon EC2 instances, Selenium, PhantomJS, and tcpdump.
  • 4 Data gathering: A prior Wang et al. dataset provides 90 instances from 100 monitored sites and 5,000 unmonitored sites for direct comparison with k-Nearest Neighbor.Its monitored pages include real-world censored websites from the UK, Saudi Arabia, and China.
  • 4 Data gathering: The experiments include Tor hidden services selected by popularity from the Ahmia .onion search engine.Hidden services preserve anonymity for both the accessing client and hosting server.

5 Feature selection

The paper systematically ranks feature importance for random-forest classification and finds that a small set of features captures most of the useful signal. Later experiments therefore use 150 features despite diminishing returns from adding more.

  • 5 Feature selection: The study addresses a stated lack of systematic feature analysis in website fingerprinting, where prior features were selected heuristically.Feature-importance experiments use the Wang et al. dataset for direct comparison with prior results.
  • 5 Feature selection: Feature importance is estimated from random-forest splits using the Gini coefficient as the branch-purity criterion.The classifier is trained in a closed-world setting with literature-derived features and monitored-site labels.
  • 5 Feature selection: Accuracy increases monotonically with more features but shows diminishing returns, reaching nearly the same accuracy with the 30 most important features.The paper uses batches of five features and selects 150 for subsequent experiments because the training-time difference was negligible.
  • 5 Feature selection: The top 13 features are substantially more important than the remaining top 20, followed by a drop between ranks 13 and 14.Ranks vary somewhat across 100 repeated experiments and are assigned using average feature rank.

Feature Importance

Packet counts and ordering are the most informative features, while timing and padded concentration features contribute less consistently.

  • Inter-arrival-time statistics rank between 40 and 70, whereas zero-padded outgoing concentration features are least important.
  • Incoming packet count is the most informative feature because resource sizes remain poorly hidden by encryption or anonymization.
  • Incoming and outgoing packet fractions are informative, reflecting differences in web-page resource sizes.
  • Packet ordering features rank 4, 7, 12, and 13, indicating that browser request and server transmission order aids classification.
  • Early packet counts rank 19 and 20, outperforming corresponding late counts ranked 50 and 55.

6 Attack on hardened defenses

The evaluation compares k-fingerprinting with prior attacks under multiple defenses, finding comparable or better performance than k-NN and substantially better performance than CUMUL.

  • BuFLO sends constant-size packets at fixed intervals, potentially extending transmission length.The passage identifies this as one of the evaluated defenses.
  • AP uses one master histogram for all clients in this implementation, although histogram distributions depend on client bandwidth capacity.Optimizing histograms across many clients remains open according to the cited discussion.
  • Under every tested defense, k-fingerprinting is comparable to or better than k-NN and significantly better than CUMUL.The comparison uses a closed-world setting and the Wang et al. data set.
  • Traffic morphing produces similar k-fingerprinting accuracy to having no defense.The authors relate this to morphing targeting only the features used by an attacker.

7 k-fingerprinting the Wang et al. data set

On the Wang et al. Tor data set, k-fingerprinting uses timing and volume information to classify monitored pages amid unmonitored pages, with k controlling the TPR–FPR trade-off.

  • The data set pads packets to fixed-size cells and randomizes request order, leaving timing and volume as available information.Training uses 60 of 90 instances for each of 100 monitored pages.
  • TPR 0.88 ± 0.01 and FPR 0.005 ± 0.001 are achieved with 3500 unmonitored training pages and k=3.The corresponding k-NN result is TPR 0.85 ± 0.04 and FPR 0.006 ± 0.004.
  • Increasing unmonitored training pages lowers FPR with almost no TPR reduction, with no further FPR benefit after 3500 pages.
  • Increasing k reduces misclassifications and FPR but also reduces TPR, allowing the attacker to tune the classifier.At low k, FPR is around 1%.
  • Changing k affects TPR and FPR more than changing the number of unmonitored training pages, while 1500 pages can reduce start-up requirements.
  • A fingerprint length of 20 yields TPR 0.87 and FPR 0.013, after which increasing length has diminishing returns.Length one has high FPR because the leaf-symbol universe is small.

8 Attack evaluation on DSTor

On DSTor, k-fingerprinting maintains high TPR while additional unmonitored training sharply reduces FPR, including at large world sizes and for Tor hidden services.

  • DSTor Alexa pages: For top Alexa pages, increasing training from 2% to 16% lowers FPR from 3.2% to 0.3% while TPR decreases from 93% to 91%.
  • DSTor Alexa pages: With k=5, the FPR is 2.5% across 98,000 unmonitored pages in the Alexa evaluation.
  • DSTor hidden services: For hidden services, increasing training from 2% to 16% lowers FPR from 0.2% to 0.02% while TPR decreases from 82% to 81%.
  • DSTor hidden services: With k=5, the hidden-service FPR is 0.2%, corresponding to 196 falsely classified pages out of 98,000.
  • Detection confidence: With k=10, a monitored hidden-service classification has over 80% probability of being correct despite 98,000 unmonitored versus 600 monitored pages.
  • Interpretation: Tor hidden services are more distinguishable than standard web pages, which the authors associate with their lower FPR.

9 Attack evaluation on DSNorm

On DSNorm, k-fingerprinting was evaluated with and without packet-size features to compare encrypted browsing and Tor-like settings. Packet-size information improved closed-world accuracy, while open-world performance remained strong across training-set sizes.

  • 0.87 TPR and 0.004 FPR were achieved despite the larger world size, with best results when training on 4000 unmonitored web pages.
  • Varying the number of unmonitored training pages decreased FPR while only slightly decreasing TPR, mirroring findings on other data sets.
  • 0.81 TPR and 0.005 FPR were achieved without packet-size features when training on 5000 unmonitored web pages.
  • The DSNorm comparison removed packet-size information to match Tor-collected data and establish the effect of additional size features.
  • 0.91 closed-world accuracy without packet-size features increased to 0.96 when those features were available.

10 Fine grained open-world false positives on Alexa monitored set of DSTor

The evaluation examines whether an attacker can estimate false-positive behavior for individual monitored pages using limited unmonitored training data. Estimates were close to actual FPRs, enabling selective removal of problematic monitored classes without requiring extensive additional training.

  • Classification errors are uneven across web pages: some are repeatedly confused with many others, while others are never misclassified.
  • An attacker estimates each monitored class’s TPR and FPR by splitting the training data into smaller training and validation sets with known labels.
  • With 2000 unmonitored training pages split evenly, FPR estimates remained accurate when monitored classes were removed.
  • The true FPR for the best 20 monitored classes was 0.010, closely matching the estimate from the split data.
  • There was only a small gap between estimated and actual FPRs in both 2000-page and 16000-page training settings, with little benefit from more unmonitored data.
  • Removing monitored pages can reduce the monitored set’s utility loss while the overwhelmingly large unmonitored world size limits BDR growth from such removals.

11 Attack Summary & Discussion

The paper summarizes k-fingerprinting as accurate, scalable, and adaptable across monitored sets and collection conditions, while exposing uneven page-level vulnerability. It also identifies website content changes as an important boundary on attack accuracy.

  • Attack Summary: Training on about two thirds of unmonitored pages produced the best results, but training on 2% still achieved a very small FPR with only marginally lower accuracy.
  • Attack Summary: Changing k influenced accuracy more than changing the number of training samples across the evaluated data sets.
  • Discussion: k-fingerprinting achieved the same accuracy across monitored-set types and collection methods, including Tor and standard web browsing.
  • Discussion: Misclassified monitored pages were usually misclassified repeatedly, allowing attackers to estimate per-page error rates and select targets with lower misclassification rates.
  • Computational Efficiency: Training took 30.738 CPU seconds for 6000 monitored and 2500 unmonitored pages, versus about 500 CPU hours for the compared Cai et al. attack.
  • Discussion: Increasing the monitored training set size improved accuracy only incrementally compared with using a small number of monitored instances.
  • Discussion: Website content changes can reduce accuracy, with faster degradation expected for news and social-media sites than for stable landing pages.

12 Conclusion

The paper concludes that k-fingerprinting is a scalable, accurate threat to privacy across Tor and standard browsing, while vulnerability and error rates vary substantially by web page. Attackers can improve confidence by filtering high-error monitored pages, although estimates depend on training-data size.

  • Conclusion: k-fingerprinting improves website-fingerprinting speed and accuracy across four datasets, including large-scale browsing environments.The authors report robustness against overfitting and applicability to real-world browsing at scale.
  • Scalability: Training on a small fraction of unmonitored pages can support accurate attacks, while increasing world size does not necessarily reduce accuracy.Figure 16 varies k and the number of trained unmonitored pages; the conclusion also reports that small-fraction training can enable later filtering.
  • Closed-world error rates: 49 of 550 instances were misclassified in the closed-world Tor attack, yielding an average error rate of 0.09.The confusion matrix reports F1 score = 0.913 and Accuracy = 0.915.
  • Closed-world error rates: Classification error is uneven across web pages, with some pages frequently confused and others never misclassified.Per-page misclassification estimates can replace the global average when assessing vulnerability.
  • Page selection: Considering only the 50% of pages with lower per-page misclassification rates reduces the true and estimated global error by over 70% on Wang et al. and over 80% on DSNorm.Figures 14 and 15 order monitored pages from smallest to largest misclassification rate.
  • Limitations: The attacker’s per-page error estimates may diverge from test-set error because training-data size differs between datasets.Wang et al. has 60 instances per monitored page versus 20 for DSNorm, and closer alignment is expected with more training instances.

15 Attack on larger world size of DSNorm

The DSNorm experiment tests k-fingerprinting with 17,000 unmonitored pages and finds no accuracy degradation relative to a smaller world. Training on roughly 30% of the data still produces low false-positive rates, while larger k reduces false classifications among unmonitored pages.

  • Experimental setup: The experiment increases DSNorm’s unmonitored-world size to 17,000 pages while evaluating both time and size features.The attack uses the same number of monitored sites as in the preceding experiment.
  • Accuracy at larger world size: Attack accuracy remains comparable to the 7,000-page experiment after adding 10,000 unmonitored pages.Figure 16 varies k from 1 to 10 and compares different numbers of trained unmonitored pages.
  • Training cost: Training on approximately 30% of 17,000 unmonitored pages gives TPR = 0.90 and FPR = 0.006 for k=1.For approximately 30% of 7,000 pages, the corresponding values are TPR over 0.90 and FPR = 0.01.
  • False positives: Only 72 of 12,000 unmonitored pages were classified as monitored, falling to 24 when k=10.The decline in false classifications supports scaling to a broader real-world browsing world without decreased attack accuracy.
Loading 1509.00789v3…