# Towards Effective and Efficient Padding Machines for Tor

The good, the bad, and the ugly.

Tobias Pulls<EMAIL_ADDRESS>Computer Science, Karlstad University,
SwedenKarlstad

###### Abstract.

Tor recently integrated a circuit padding framework for creating padding
machines: defenses that work by defining state machines that inject dummy
traffic to protect against traffic analysis attacks like Website
Fingerprinting (WF) attacks. In this paper, we explore the design of effective
and efficient padding machines to defend against WF attacks. Through the use
of carefully crafted datasets, a circuit padding simulator, genetic
programming, and manual tuning of padding machines we explore different
aspects of what makes padding machines effective and efficient defenses. Our
final machine, named Interspace, is probabilistically-defined with a tweakable
trade-off between efficiency and effectiveness against the state-of-the-art
deep-learning WF attack Deep Fingerprinting by Sirinam et al. (df, ). We show
that Interspace can be both more effective and efficient than WTF-PAD by
Juarez et al. (JuarezIPDW16, ), the padding machine that inspired the design
of Tor’s circuit padding framework. We end this paper by showing how
Interspace can be made less effective, identifying the promising tactic of
probabilistically defined padding machines, and highlighting the need to
further explore this tactic in more complex defenses.

##  1\. Introduction

Tor (tor, ) recently integrated a circuit padding framework for circuit-level
defenses in the form of padding
machines111https://gitweb.torproject.org/torspec.git/tree/padding-spec.txt.
The framework is thoroughly documented
222https://gitweb.torproject.org/tor.git/tree/doc/HACKING/CircuitPaddingDevelopment.md
and a simulator for the framework has been
developed333https://github.com/pylls/circpad-sim. Moving forward, we expect
that researchers will use the circuit padding framework to build new padding
machines with the goal of defending against a range of traffic analysis
attacks. One such attack—that was one of the motivations behind the design of
the framework—is a Website Fingerprinting (WF) attack (cheng1998traffic, ;
DBLP:conf/sp/SunSWRPQ02, ; Hintz02, ; DBLP:conf/ccs/LiberatoreL06, ;
HerrmannWF09, ; PanchenkoNZE11, ). In a WF attack, a passive local
eavesdropper (e.g., a guard relay or an ISP) observes the encrypted traffic
between a Tor Browser client and the Tor network and attempts to infer the
destination based on patterns in the encrypted network traffic.

This paper is dedicated to the evaluation of WF attacks and defenses involving
padding machines in the circuit padding framework and accompanying simulator.
We present a dataset and evaluation method for the circuit padding simulator
structured for _webpage-to-website_ fingerprinting, building upon the work of
Cai et al. (touching, ) and Panchenko et al. (cumul, ) (Section 2). Using the
state-of-the-art Deep Fingerprinting (DF) attack by Sirinam et al. (df, ), we
show that DF is highly successful in webpage-to-website fingerprinting, that
the safest security level for TB is quite different from the others, and that
the start of traces is the most useful for DF (Section 3).

Using genetic programming together with the circuit padding simulator, we
evolved padding machines from February until June 2020, where the best machine
achieve 0.57 max recall444We focus on max recall because of the results of
Pulls and Dahlberg (wfwo, ), assuming that an attacker can use so-called
website oracles to reduce the false positive rate of its WF classifier. with
0.52 precision and 206% overhead (Section 4). Next, we refine the evolved
machines by manual pruning and tuning, resulting in two machines: Spring and
Interspace. Spring is a simplified machine from the best evolved machine.
Interspace in turn is based on Spring with the main change of being a
probabilistically defined machine, similar to how ScrambleSuit (and obfs4)
works (DBLP:conf/wpes/WinterPF13, ). The Interspace machine has a max recall
slightly above 0.3 with 230% overhead. In the same setting, the WTF-PAD
defense by Juarez et al. (JuarezIPDW16, )—that inspired the design of Tor’s
circuit padding framework—has a max recall of about 0.7 at 178% overhead.
Interspace is tweakable, allowing an effectiveness-efficiency trade-off. At
the same overhead as WTF-PAD, Interspace has a max recall of 0.5, and can
provide 0.7 max recall at 150% overhead (Section 5).

Section 6 discusses the good, the bad, and the ugly of our results. The good
was earlier mentioned: Interspace is an effective machine in our setting,
tweakable, and built for Tor’s circuit padding framework. In terms of the bad,
we are basically brute-forcing the design of the machines against a particular
deep learning attack through simulation. Also, we completely ignore time,
since DF does not use time and time in the simulator is unrealistically
accurate. For the ugly, we show that he effectiveness of Interspace could be
reduced by significantly increasing the training data available to DF through
repeated simulation of its defense on our collected traces (in a sense,
changing our experimental setting), reaching a max recall above 0.6.

We conclude this paper in Section 7. Interspace, being a probabilistically
defined machine, could be made less effective with more training data.
However, we show (again) that DF struggles once deprived of being able to
train on the exact defense used by a target. This tactic should be further
explored for more complex defenses.

##  2\. The Goodenough Dataset

We set out to create a dataset that better reflects the challenges of an
attacker than the typical datasets used in the evaluation of WF attacks. The
dataset consists of 10,000 monitored samples and 10,000 unmonitored samples
(balanced, so not taking into account client or network base rate). The
monitored samples represent 50 classes of popular websites taken from the
Alexa toplist (all within Alexa top-300 at the time of collection). For each
website/class, we selected ten webpages of that website to represent that
class, hence _webpage-to-website_ fingerprinting. For example, for the website
reddit.com, we selected ten URLs to popular subreddits such as
r/wholesomememes and r/Wellthatsucks/. Similarly, for wikipedia.org, we
selected articles such as https://en.wikipedia.org/wiki/Dinosaur and
https://en.wikipedia.org/wiki/Fossil. The full list of websites and webpages
are available as part of the dataset. We collected 20 samples per webpage,
resulting in $50x10x20=10,000$ monitored samples.

Now to the key idea of the dataset: to evaluate WF attacks based on
classifiers that need training, we split the dataset into training,
validation, and testing with a 8:1:1 ratio. This split is done _per webpage_ ,
such that the classifier never gets to train on the same webpage as is used
for validation or testing. This trains the classifier to identify the _common
structure_ that makes up different webpages belonging to the same
website/class.

Figure 1 visualizes the structure of our dataset, including the unmonitored
samples, which consists of 10,000 unmonitored webpages collected from
reddit.com/r/all (top last year). We made sure to exclude webpages of
monitored websites, which include self-hosted images at Reddit. We also
excluded direct image links, since they are too distinct to the monitored
webpages, and links to YouTube and Twitter that have a tendency of
sporadically blocking access from the Tor network.

Figure 1. A visualization of the structure of the Goodenough dataset.

###  2.1. Security Levels

The dataset exists in three versions with one for each security level in Tor
Browser: standard, safer, and safest. The security level determines if a
number of features in the browser are enabled or not, where one of if not the
most notable feature is JavaScript. JavaScript is completely disabled at the
safest security level. Three versions of the dataset allows us to better take
into account another important aspect often overlooked in the evaluation of WF
attacks and defenses.

###  2.2. Key Collection Details

All samples in the final dataset were gathered with Tor Browser 9.0.2 in
February, 2020, from Karlstad University, Sweden (connected to
SUNET555https://www.sunet.se) using freely available
tools666https://github.com/pylls/padding-machines-for-tor/tree/master/collect-
traces with ample compute and network resources. We also collected the full
dataset in December, 2019, and January, 2020. No differences in results
between the three different points in time were noticed, beyond having to
update a few webpages that disappeared (primarily news articles). We therefore
opt to only use the February dataset for the rest of this paper unless stated
otherwise.

Each sample consists of one log and two traces. The log is the modified tor
log from Tor Browser using the circpad-sim777https://github.com/mikeperry-
tor/tor/commits/circpad-sim-v4 modifications, generated by having 140
concurrent docker containers of headless Tor Browser visiting webpages for one
minute. In Tor Browser, we disabled guards (UseEntryGuards 0) and altered the
security level. Each visit used a dedicated copy of Tor Browser with a fresh
copy of the consensus (to reduce the load on the network). Therefore, each
sample was collected on its own circuit.

From each log, we generated the client trace from circpad-sim using
torlog2circpadtrace.py888https://github.com/pylls/circpad-
sim/blob/master/torlog2circpadtrace.py with default parameters (note the
10,000 maximum length per circuit to extract). We also include corresponding
_simulated_ relay traces, generated using
simrelaytrace.py999https://github.com/pylls/circpad-
sim/blob/master/simrelaytrace.py with default parameters. Please note that
accuracy of the timestamps in the traces are _unrealistically accurate_ for
_any_ possible network attacker. This is because the timestamps are generated
by tor with nanosecond precision _before_ the cells are ultimately packaged
into TCP/IP packets (inside a TLS record) and transmitted.

We made efforts to try to ensure that the monitored logs and traces actually
correspond to the intended webpages, discarding any traces where tor/Tor
Browser may have used two or more circuits to load content for the visit (for
unknown reasons). Less care was taken for unmonitored samples to better
represent realistic background traffic (that may use multiple circuits for
unknown yet sporadically observed reasons).

###  2.3. Related Work

Both the work of Panchenko et al. (cumul, ) and Cai et al. (touching, )
inspired how our dataset is structured and its implied method of use. Both
works use traditional machine learning techniques with manually engineered
features, significantly reducing the effectiveness of attacks in their
evaluations.

Cai et al. differentiate between websites and webpages, where an attacker’s
goal is to identify a visit to any webpage of a website. They note that
webpages of websites commonly share structure (“templates”), and that an
attacker can attempt to detect that structure regardless of exact webpage
visited by a victim. This is identical to our work. However, their dataset is
small, consisting of two monitored websites, with an unclear number of
unmonitored websites (open world is stated though). They also focus more on
modelling complete browsing sessions by victims, at a time when many of the
advances in WF attacks were still to see the light of day.

Panchenko et al. also differentiate between websites and webpages, but in
general, train on the same webpage as they later classify. They did note one
attempt of only training on a subset of the webpages later used for testing,
in the closed world, where the performance of their classifier degraded
significantly. This is our default setting, but in the open world. We used
reddit to gather our unmonitored dataset, while Panchenko et al. in part used
Twitter.

In gist, how our dataset is structured and its method of evaluation is based
upon the work of Panchenko et al. (cumul, ) and Cai et al. (touching, ), but
our results and extended experiment design benefit from the recent advances in
automatic feature engineering using deep learning.

##  3\. Results using Deep Fingerprinting

For all the following results, we extracted the first 5,000 cells101010Note
that cells make up a subset of the 10,000 maximum events extracted from logs,
as noted in Section 2.2. and their directions from the dataset for each
sample, _completely discarding time_ , because it is unrealistically precise.
We use the state-of-the-art Deep Fingerprinting (DF) attack by Sirinam et al.
(df, ), ported to the PyTorch library. Deep-learning based attacks (like DF)
free us from the burden of manual feature engineering and have been shown to
be superior to traditional machine-learning WF attacks in many settings
(DBLP:journals/popets/BhatLKD19, ; DBLP:journals/popets/OhSH19, ; df, ).

Because the dataset is of modest size—20,000 traces per security level—it is
feasible to perform ten-fold cross-validation when using DF and a modern GPU.
For each fold, we change the webpages used to train, validate, and test the
monitored websites as well as the unmonitored webpages deterministically,
never training on any webpage used for validation or testing.

###  3.1. Webpage-to-Website Fingerprinting

Figure 2 shows the results of performing webpage-to-website fingerprinting for
all three security levels of Tor Browser. Each dot represents a possible
precision-recall trade-off—based on the probability threshold for the
monitored classes from the final softmax in DF—for ten-fold cross-validation.
The DF attack is highly successful. We see slightly better protection offered
by the safest security level on average (note the axes), with no difference
between standard and safer.

Figure 2. 10-fold cross-validation with 16 thresholds for the three different
security levels in Tor Browser.

###  3.2. Classification Across Security Levels

Figure 3 shows the impact of cross-level classification, where a model trained
on a dataset generated by one security level of Tor Browser is used to
classify all three levels. We see a significant difference when it comes to
the safest security level: the impact on webpage-to-website fingerprinting is
huge. There is no significant difference between standard and safer, similar
to the results in Figure 2.

(a) Trained on standard

(b) Trained on safer

(c) Trained on safest

Figure 3. Precision-recall metrics on datasets collected using the three
security levels in Tor Browser, when the model is trained on data belonging to
a particular security level.

###  3.3. Estimating Defense Priorities

We can estimate the relative importance of different parts of a trace by
zeroing cells, removing a variable amount of information from the attacker. In
the following analysis we only consider the maximum recall by setting the
threshold in DF to 0 for each of the ten-folds per measurement.

Starting from an empty trace, Figure 4(a) includes increasingly more cells in
traces. Note the logarithmic x-axis. The figure shows a steep increase in
recall with a few hundreds of cells, needing only about 100 cells to hit 0.5
recall. No significant difference between security levels, with the exception
of a small dip for standard and safer around 1,500 cells.

Figure 4(b) starts with a full trace and excludes increasingly more cells.
Note the linear x-axis. Comparing the results to Figure 4(a), it is clear that
the start of a trace has the most utility for an attacker: the first 100 cells
are about as useful as the last 3,000 cells for standard and safer security
levels. This is in line with the results of Mathews et al. (featurediscovery,
). However, the most striking result is the impact on the safest security
level. By excluding the first 1,000 cells the maximum recall is cut to about
0.25, approximately a third of the recall for the other security levels.

(a) Increasingly including

(b) Increasingly excluding

Figure 4. The maximum recall when including or excluding increasingly more
cells of traces. Based on the dataset collected in January (took about a week
to produce with ten folds, cannot justify costs when no other scenario offers
any noticeable difference).

The degree to which the safest security level stands out in Figure 4(b) can be
explained in part with a closer look at the dataset. The safest dataset
consists of only 1,534 full traces (5,000 cells), with an average 1,478 and
mean 950 of cells per trace.

##  4\. Evolved Machines

During the first half of 2020 we used genetic programming together with the
circuit padding simulator to evolve machines. We evolved machines for several
months of wall-time using an AMD Ryzen 7 2700X and NVIDIA GeForce RTX 2070.

###  4.1. Method

We experimented early with a number of different fitness functions (including
information-theoretic ones based on trace collisions), but landed on
$1-\texttt{recall}$, where recall is computed using DF with threshold $0.0$.
That is, we aim to minimize the maximum recall of DF against the evolved
machines. Recall is used because it captures when the client visits a
monitored page, and it tells us how many out of all visits by the client the
classifier accurately detects. More importantly, as a metric, it ignores how
the classifier performs against unmonitored testing traces. DF does not use
time, so it is appropriate to use with the circuit padding simulator. It might
seem overkill to use deep learning, but our execution time was dominated by
simulating the evolved machines. In our implementation, to reach parity
between simulating traces and computing the fitness function (deep learning)
using a modest NVIDIA GeForce RTX 2070 we would need in the order of a 100 CPU
cores.

We used a small population size of ten machines, where the initial population
was randomly generated. This might seem small, but each machine has to be
simulated against 20,000 traces, taking significant time. We experimented
relatively briefly with different population sizes, but found no improvement
in larger sizes. We used the full dataset of 20,000 traces at the safest
security level (the smallest and easiest to protect, see Section 3.3) to make
maximum recall as good as possible of a fitness function.

Given a population of machines and their fitness determined based on their max
recall with DF, the next generation was evolved as follows. First, we selected
an _elitist fraction_ of the most fit machines and copied them over as-is. For
most of our runs, this was only the single best machine. We briefly
experimented with keeping a _diversity fraction_ of randomly selected
machines, but opted to disable this due to lack of initial results. For the
remaining slots in the population (typically nine), we evolved new machines
using crossover and mutation. For crossover, we performed single-point
crossover between _complete states_ of machines. For mutation, with some
probability, we mutated each part of each state (the inter-arrival
distribution, the length distribution, and the state transitions). Parents
were selected at random from the previous generation, weighted by fitness. The
client and relay parts of machines never interacted; each evolved
independently.

Each machine actually consists of a pair of machines: one machine running on
the client and one on the relay (we target the second hop, i.e., the middle
relay). In particular, we do not evolve _symmetric_ machines (as in, e.g.,
WTF-PAD), so the client and relay logic may be completely different. A single
machine consists of four states (compared to three in WTF-PAD), but only uses
distributions for length- and time-sampling (so no histograms) to limit the
search space. It is also known from WTF-PAD that tailoring histograms is a
significant challenge for deployment (or even evaluation across datasets). The
circuit padding framework enables us to put both absolute and relative
overhead limits for padding _circuit_ and machine. We used generous limits,
with the final machines allowing 1,000 cells in absolute terms, that are then
followed by a 50% overhead as a percentage of total traffic. Note that for
evaluating the fitness of machines we use the first 5,000 cells of each trace.
Finally, all machines start as soon as streams are attached to the circuit.
Due to how we collected our dataset, the first stream directly carries data to
connect to the destination website.

###  4.2. Results

During each month—from February until June 2020—we looked at the most fit
machines and made minor tweaks and/or fixes to our software for evolving
machines. Table 1 gives a summary of the most fit machines each month and
their bandwidth overheads in total and per direction (from the client’s
perspective). For reference, on unprotected traces DF gets 0.88 max recall and
0.93 precision. From the table, we note that the June machine is basically
useless, despite having the highest total bandwidth (242%). In comparison,
from the evolved machines, the best machine is April with a max recall of
0.57, 0.52 precision, and only 206% overhead.

Table 1. The five best evolved machines from February to June with their maximum recall and corresponding precision against the safest dataset. Average bandwidth (BW) is shown in total (where 100% means no overhead) as well as per direction (fraction of total in parenthesis). Machine | Max Recall | Precision | Total BW | Sent BW (total) | Recv BW (total)
---|---|---|---|---|---
February | 0.79 | 0.79 | 173% | 817% (48%) | 100% (52%)
March | 0.86 | 0.79 | 173% | 816% (48%) | 100% (52%)
April | 0.57 | 0.52 | 206% | 396% (19%) | 185% (81%)
May | 0.71 | 0.64 | 182% | 439% (24%) | 153% (76%)
June | 0.89 | 0.84 | 242% | 597% (25%) | 202% (75%)

From the results in Table 1 and details above one might wonder how come we see
such varying results between months. The answer is simple: bugs in our
evaluation code together with the importance of overhead limits and time spent
evolving. To help explain how the machines changed over time, Figure 5
visualizes the first 200 defended traces for each selected evolved machine,
using colors to differentiate between sent nonpadding (white), sent padding
(green), received nonpadding (black), and received padding (red) cells. The
completely white connected parts to the top-right of each figure is empty
traces (technically transparent but white due to medium).

(a) February

(b) March

(c) April

(d) May

(e) June

Figure 5. Color visualizations of a selection of the traces for selected
evolved machines. Black represents received nonpadding and white sent
nonpadding. Red shows received padding and green sent padding. Note the type
of padding and the importance of padding limits.

Starting with February, we see our first results. From Figure 5(a) the evolved
tactic of the machine is clear: send as much padding as possible up until the
overhead limits kick in. At this early stage, the allowed padding was set to
2,000 cells, which is slightly less than half the length of the trace (max
5,000 cells). Also, the fitness function was set to the recall at threshold
0.5, making the fitness calculation less stable. Notably, the defense
completely ignores any padding from the relay to the client (received padding,
red). This was due to a bug in our use of the circpad simulator (padding to
the guard instead of the middle relay, which is not supported).

The results from March builds upon February by changing the fitness to the
_minimal_ recall (threshold 1.0). While this resulted in worse fitness (higher
max recall), we note from Figure 5(b) that the padding is now better
distributed throughout the traces.

For April we see significant improvements in both Table 1 and Figure 5(c). We
fixed the bug that prevented any padding from the relay to the client
(received padding, red), set the fitness function to consider the _maximum_
recall (threshold to 0.0), and made the padding limits more strict (1,000
padding cells then at most 50% padding). Both sent and received padding are
distributed throughout the traces, achieving 0.57 max recall. We will return
to this machine in more detail later.

For the May machine we restarted evolving machines from a clean slate with the
hope of finding other tactics for padding. Table 1 shows weaker protection
than April, but still a notable improvement over no defense, and less
overhead. As we can see in Figure 5(d), the received overhead is significantly
reduced (note the total as well as received bandwidth reduction), in
particular towards the end of the traces.

The last evolved machine is from June, where we restarted from scratch and
fixed yet another bug. The generated c-code for machines did not correctly set
dist_added_shift_usec: a value added to the sampled delay distribution for
deriving the final padding delay. While this does not invalidate our prior
results, it makes our search space significantly bigger due to being such a
central parameter (up to eight states have this parameter and large, randomly
generated values significantly change the final padding delay). Figure 5(e) is
in a sense similar to Figure 5(a); we never get past the initial phase of
being dominated by our padding limits.

##  5\. Manually Tuned Machines

Using the evolved machines as a starting point, we set out to create manually
tuned machines. The source code of the evolved machines are available
online111111https://github.com/pylls/padding-machines-for-
tor/tree/master/machines/phase2, omitted here for sake of brevity.

We used April as a starting point for the _Spring_ machine, name from the fact
that April was the most effective evolved machine from spring. The following
changes were made:

  * •

upped padding limit to 1500

  * •

removed transitions and states that never could do anything

  * •

removed useless IAT dists (CIRCPAD_DIST_NONE)

  * •

removed each max_length, hardly ever hit

The main change in behavior of the machine was the upped padding limit,
reducing max recall from 0.57 to 0.47. The full source code of Spring is in
Appendix A.

The cleaned up Spring machine in turn was the basis for our final machine:
_Interspace_. The name comes from the song Interspace by Starcadian, that our
Spotify radio played at the time of creation. Thank you randomness (or rather,
deep learning based recommendation engine trained with over ten years of
personal listening history). For Interspace we introduce the concept of
_probabilistically defined_ machines. As part of little-t tor startup,
circpad_machines_init() initializes all padding machines. Here, we make the
actual definition of Interspace randomized. This is similar to how
ScrambleSuit (and later obfs4) picks a “polymorphic shape” per server
instance.

We spent a modest amount of time (about a week) exploring different
randomization tactics. The full source code of Interspace is in Appendix B,
and has the following main changes from Spring:

  * •

The client machine is changed to include—with 50% probability each—transitions
between the two main states that act on received padding or non-padding,
respectively.

  * •

With 50% probability, the relay machine consists of either the Spring relay
machine or another, completely hand-crafted, machine. The hand-crafted
machine, in turn, uniformly selects one of two tactics: either attempt to
extend real bursts of cells or inject completely fake bursts of modest size.
For iat and length distributions, we randomize the parameters to the used log-
logistic (waiting time before injecting a fake burst) and pareto (for length,
i.e., number of padding cells to send at most, and short iat between cells of
a burst) distributions.

Figure 6 shows the effectiveness of our our manually tuned machines for two
security levels. We also include a comparison with one configuration of WTF-
PAD using the most effective default configuration. To make the WTF-PAD
configuration to produce approximately the same amount of padding as reported
by Juarez et al. (177%), we scaled the timestamps of all cells in the dataset
until we reached nearly the same overhead on the standard dataset (178%), as
measured by their tool. In gist, WTF-PAD offers some protection, Spring is
notably more effective, and Interspace even more so. The differences between
the defenses are bigger than the differences between Tor Browser security
levels. Table 2 shows the overhead for the defenses and security levels. In a
sense, the results are a reverse of Figure 6: the more effective the defense,
the less efficient it is in comparison.

Figure 6. Precision-recall curve of our manually tuned machines, compared to the WTF-PAD defense (the norm-rcv config, the best config on our datasets), for two security levels from Goodenough February. Table 2. Overheads for the two tuned machines as well as WTF-PAD (as measured by their own tool) on the February Goodenough dataset for two security levels of Tor Browser. Machine | Level | Total BW | Sent BW (total) | Recv BW (total)
---|---|---|---|---
Spring | standard | 210% | 408% (19%) | 189% (81%)
Spring | safest | 285% | 731% (25%) | 236% (75%)
Interspace | standard | 230% | 604% (27%) | 188% (73%)
Interspace | safest | 305% | 909% (30%) | 238% (70%)
WTF-PAD | standard | 178% | — | —
WTF-PAD | safest | 248% | — | —

The overhead of each machine is capped by allowed_padding_count and
max_padding_percent, set for both the relay and client machines. Keeping
max_padding_percent fixed at 50%, Figure 7 shows the _max-recall_ and overhead
trade-off of Interspace when alternating allowed_padding_count from 1 to 1,500
(symmetrically, for both the client and relay) for the standard and safest
security levels. For reference, WTF-PAD had a max call at about 0.7 (average
over all folds) at 178% overhead for the standard level and a max recall
around 0.65 at 248% overhead for the safest level. Interspace can reach the
same defense effectiveness at 150% overhead, significantly more efficiently.

Figure 7. The maximum recall and overhead trade-off of Interspace when
alternating allowed_padding_count from 1 to 1,500 (inclusive) for two security
levels from Goodenough February.

##  6\. Discussion

We consider the good, the bad, and the ugly of our evolved and manually tuned
machines.

###  6.1. The Good

In April, we evolved a machine that is a more effective defense than WTF-PAD,
within the constraints of the circuit padding framework of Tor against the
state-of-the-art DF attack. We also showed that WTF-PAD may offer _some_
protection against DF in our more realistic setting—represented by our dataset
and evaluation method—assuming the way we manually tweaked the dataset to make
WTF-PAD’s default configuration work was not too drastic. This is an
indication that we need to further consider how we evaluate WF attacks and
defenses.

Our manually tuned machines offer further improvements. Interspace provides an
effective defense for both the standard and safest security levels in our
dataset. The overhead is larger than WTF-PAD, so Interspace is less efficient.
That said, the notion of overhead is worth to consider. With
allowed_padding_count set to 1500, this is a minimum of 1500 cells: about 750
KiB. This is not overwhelming. We know from Figure 4 that the early parts of
traces are the most important. Accepting, say, a 1 MiB overhead for web
circuits (with added logic on the client to only negotiate the machine when a
stream is attached using port 80 or 443) would likely go a long way in making
attacks harder, yet, not adding significant overheads over typical website
sessions that likely contain media such as images or even videos of relatively
large sizes.

Thanks to the circuit padding framework, Interspace is also tweakable,
offering efficiency–effectiveness trade-offs. We see a clear relationship
between overhead and maximum recall in Figure 7 for both security levels. In
part, by probabilistically defining the machine, its effectiveness was
improved. This appears to be a promising tactic to further explore.

###  6.2. The Bad

In gist, by using genetic programming to evolve machines, our results are
generated by trial-and-error. There is probably a significant room for
improvement. In a sense, we do not really understand why the machines work
other than more general observations such as the relative importance of
padding early rather than later.

While our dataset was captured on the live network from clients, the relay
portions were simulated. Further, we simulated all our defenses on those
traces and used DF that ignores time. Validating the machines on the live
network is a natural next step. An attenuating circumstance is that each trace
in our dataset was collected on its own unique circuit with no fixed relays.
Hopefully, this means that we have not overfitted our parameters to any
particular network circumstance. Future work will tell.

###  6.3. The Ugly

If the goal was a paper, we are pretty much done now. However, towards the
goal of effective and efficient padding machines for Tor, and not only for
publication, we look deeper. What has hopefully been clear so far is that our
machines _reduce_ the effectiveness of the DF attack. The question of what
exactly an “effective” defense against WF attacks looks like though has been
debated in the community. Issues such as dataset freshness, different attacker
goals (e.g., inline classification for censorship or ex-post for detection),
website vs website fingerprinting, and victim as well as website base rates
are all good examples. In part, these issues relate to the proper experiment
design as part of the method of evaluation of WF attacks and defenses. We
provided some improvements by taking into account webpage-to-website
fingerprinting and different security levels of Tor Browser.

In our experiments we simulate the machines by using circpad-sim. We, as well
as an attacker, can of course simulate each trace multiple times instead of
just once. This should be about the same as visiting webpages of target
websites more times for the sake of training, with the caveat that we also
give repeated samples of the unmonitored websites121212This is not strictly in
line with how unmonitored websites are represented in WF datasets, but because
of the large number of websites labeled as unmonitored (10,000), we believe
that this is negligible.. By multiplying the number of times we simulate our
machines per trace, we get increasingly more training data. Given that
Interspace is probabilistically defined, simulating the same trace several
times may also be particularly useful. Figure 8 shows the max recall of DF
(only one fold) as we simulate each trace by a factor from 1–20 (from 20,000
to 400,000 samples in the dataset, split 8:1:1). We see that this decreases
the effectiveness of Interspace, improving max recall up to a bit over 0.6
until the gain stalls around a factor 15 or so.

Figure 8. The maximum recall for Interspace as we grow the dataset by a
variable factor through repeated simulation, for two security levels from
Goodenough February.

##  7\. Conclusions

The WF setting is challenging. We improved the method of evaluation by
considering webpage-to-website fingerprinting and the security level of Tor
Browser, collecting extensive datasets, and identifying the general parts of
traces most useful for distinguishing between websites. For attacks we used
Deep Fingerprinting (DF), a state-of-the-art deep-learning model.

Using genetic programming and months of wall-time computing with a GPU, we
evolved defenses against DF. The defenses, in the form of padding machines in
Tor’s circuit padding framework, were evaluated against DF withing the circuit
padding simulator. Using the most promising evolved machines, we manually
tuned and built new machines, landing in our best candidate: Interspace.

We have created several padding machines for Tor that are more effective
defenses than WTF-PAD, the defense that inspired the design of Tor’s circuit
padding framework. Some of our machines are less efficient. Interspace
provides a tweakable trade-off between efficiency and effectiveness, using the
global machine parameters of Tor’s framework.

Finally, we showed that the effectiveness of Interspace could be reduced by
significantly increasing the training data available to DF through repeated
simulation of its defense on our collected traces. While it is promising that
this peaked around a factor 15 or so, a max recall of above 0.6 may or may not
be effective enough of a defense. It is also frustrating that central to our
approach is treating DF as a black box. We do not really understand why
defenses work to the extent they do or why, in this particular instance, DF
could be improved to such an extent by adding more training data. Clearly, it
is a challenge to perform genetic programming on such large datasets.

One particularly important lesson is that we observed significantly reduced
attack effectiveness when training on one type of dataset and classifying on
another. We saw this between the standard and safest security levels of TB.
Interspace is based on similar ideas by probabilistically defining its
machines. Table 3 shows cross-classification across different trained models,
security levels, and datasets. Here we see again that the DF attack suffers on
not being able to train on the correct dataset. This might appear obvious at
first, but it is a largely unexplored area for WF defenses.

Table 3. Max recall for cross-classification between different trained models and testing datasets. The trained models and tested datasets are from particular defenses and Tor Browser security levels. Red cells highlight where the model and testing dataset match, and orange the second-highest max-recall. |  |  | tested dataset
---|---|---|---
|  |  | Interspace | Spring | WTF-PAD
|  |  | standard | safest | standard | safest | standard | safest
trained model | Interspace | standard |  0.35 | 0.06 | 0.30 | 0.05 | 0.03 | 0.01
safest | 0.06 | 0.31 | 0.05 | 0.26 | 0.01 | 0.02
Spring | standard |  0.16 | 0.04 | 0.46 | 0.07 | 0.01 | 0.01
safest | 0.04 | 0.14 | 0.09 | 0.42 | 0.02 | 0.02
WTF-PAD | standard | 0.05 | 0.03 | 0.07 | 0.03 | 0.72 | 0.14
safest | 0.03 | 0.05 | 0.04 | 0.06 | 0.17 | 0.69

The above begs the question: what is the proper way of evaluating WF defenses?
This has been discussed for a long time in the research community, and while
we hope that Interspace and the lessons learned here move us forward towards
the ultimate goal of effective and efficient padding machines for Tor, we are
far from done.

Code and datasets available at https://github.com/pylls/padding-machines-for-
tor.

### Acknowledgements

This research was funded by generous grants from NGI Zero PET and the Swedish
Internet Foundation. Thank you Mahdi Akil for the review.

## References

  * [1] S. Bhat, D. Lu, A. Kwon, and S. Devadas.  Var-cnn: A data-efficient website fingerprinting attack based on deep learning.  Proc. Priv. Enhancing Technol., 2019(4):292–310, 2019.
  * [2] X. Cai, X. C. Zhang, B. Joshi, and R. Johnson.  Touching from a distance: website fingerprinting attacks and defenses.  In CCS, 2012.
  * [3] H. Cheng and R. Avnur.  Traffic analysis of SSL encrypted web browsing.  Project paper, University of Berkeley, 1998.
  * [4] R. Dingledine, N. Mathewson, and P. F. Syverson.  Tor: The second-generation onion router.  In USENIX Security, 2004.
  * [5] D. Herrmann, R. Wendolsky, and H. Federrath.  Website fingerprinting: attacking popular privacy enhancing technologies with the multinomial naïve-bayes classifier.  In CCSW, 2009.
  * [6] A. Hintz.  Fingerprinting websites using traffic analysis.  In PET, 2002.
  * [7] M. Juárez, M. Imani, M. Perry, C. Díaz, and M. Wright.  Toward an efficient website fingerprinting defense.  In I. G. Askoxylakis, S. Ioannidis, S. K. Katsikas, and C. A. Meadows, editors, Computer Security - ESORICS 2016 - 21st European Symposium on Research in Computer Security, Heraklion, Greece, September 26-30, 2016, Proceedings, Part I, volume 9878 of Lecture Notes in Computer Science, pages 27–46. Springer, 2016.
  * [8] M. Liberatore and B. N. Levine.  Inferring the source of encrypted HTTP connections.  In CCS, 2006.
  * [9] N. Mathews, P. Sirinam, and M. Wright.  Understanding feature discovery in website fingerprinting attacks.  In IEEE Western New York Image and Signal Processing Workshop (WNYISPW), 2018.
  * [10] S. E. Oh, S. Sunkam, and N. Hopper.  p1-fp: Extraction, classification, and prediction of website fingerprints with deep learning.  Proc. Priv. Enhancing Technol., 2019(3):191–209, 2019.
  * [11] A. Panchenko, F. Lanze, J. Pennekamp, T. Engel, A. Zinnen, M. Henze, and K. Wehrle.  Website fingerprinting at internet scale.  In NDSS, 2016.
  * [12] A. Panchenko, L. Niessen, A. Zinnen, and T. Engel.  Website fingerprinting in onion routing based anonymization networks.  In WPES, 2011.
  * [13] T. Pulls and R. Dahlberg.  Website fingerprinting with website oracles.  PETS, 2020.
  * [14] P. Sirinam, M. Imani, M. Juárez, and M. Wright.  Deep fingerprinting: Undermining website fingerprinting defenses with deep learning.  In CCS, 2018.
  * [15] Q. Sun, D. R. Simon, Y. Wang, W. Russell, V. N. Padmanabhan, and L. Qiu.  Statistical identification of encrypted web browsing traffic.  In IEEE S&P, 2002.
  * [16] P. Winter, T. Pulls, and J. Fuß.  Scramblesuit: a polymorphic network protocol to circumvent censorship.  In A. Sadeghi and S. Foresti, editors, Proceedings of the 12th annual ACM Workshop on Privacy in the Electronic Society, WPES 2013, Berlin, Germany, November 4, 2013, pages 213–224. ACM, 2013.

##  Appendix A Spring

###  A.1. Client

⬇

1circpad_machine_spec_t *client =
tor_malloc_zero(sizeof(circpad_machine_spec_t));

2client->conditions.state_mask = CIRCPAD_CIRC_STREAMS;

3client->conditions.purpose_mask = CIRCPAD_PURPOSE_ALL;

4client->conditions.reduced_padding_ok = 1;

5

6client->name = "spring_client";

7client->machine_index = 0;

8client->target_hopnum = 2;

9client->is_origin_side = 1;

10client->allowed_padding_count = 1500;

11client->max_padding_percent = 50;

12circpad_machine_states_init(client, 3);

13

14client->states[0].next_state[CIRCPAD_EVENT_PADDING_RECV] = 1;

15

16client->states[1].next_state[CIRCPAD_EVENT_NONPADDING_RECV] = 2;

17

18client->states[2].length_dist.type = CIRCPAD_DIST_PARETO;

19client->states[2].length_dist.param1 = 4.776842508009852;

20client->states[2].length_dist.param2 = 4.807709366988267;

21client->states[2].start_length = 1;

22client->states[2].iat_dist.type = CIRCPAD_DIST_PARETO;

23client->states[2].iat_dist.param1 = 3.3391870088596;

24client->states[2].iat_dist.param2 = 7.179045336148708;

25client->states[2].dist_max_sample_usec = 9445;

26client->states[2].next_state[CIRCPAD_EVENT_NONPADDING_SENT] = 1;

27client->states[2].next_state[CIRCPAD_EVENT_PADDING_SENT] = 2;

28

29client->machine_num = smartlist_len(origin_padding_machines);

30circpad_register_padding_machine(client, origin_padding_machines);

###  A.2. Relay

⬇

1circpad_machine_spec_t *relay =
tor_malloc_zero(sizeof(circpad_machine_spec_t));

2

3relay->name = "spring_relay";

4relay->machine_index = 0;

5relay->target_hopnum = 2;

6relay->is_origin_side = 0;

7relay->allowed_padding_count = 1500;

8relay->max_padding_percent = 50;

9circpad_machine_states_init(relay, 4);

10relay->states[0].iat_dist.type = CIRCPAD_DIST_PARETO;

11relay->states[0].iat_dist.param1 = 5.460653840184872;

12relay->states[0].iat_dist.param2 = 7.080387541173288;

13relay->states[0].dist_max_sample_usec = 94722;

14relay->states[0].next_state[CIRCPAD_EVENT_NONPADDING_RECV] = 1;

15relay->states[0].next_state[CIRCPAD_EVENT_PADDING_RECV] = 1;

16

17relay->states[1].iat_dist.type = CIRCPAD_DIST_LOGISTIC;

18relay->states[1].iat_dist.param1 = 1.2767765551835941;

19relay->states[1].iat_dist.param2 = 0.11492671368700358;

20relay->states[1].dist_max_sample_usec = 31443;

21relay->states[1].next_state[CIRCPAD_EVENT_NONPADDING_SENT] = 2;

22

23relay->states[2].length_dist.type = CIRCPAD_DIST_LOGISTIC;

24relay->states[2].length_dist.param1 = 4.11964473793041;

25relay->states[2].length_dist.param2 = 2.7250362139341764;

26relay->states[2].start_length = 5;

27relay->states[2].iat_dist.type = CIRCPAD_DIST_LOGISTIC;

28relay->states[2].iat_dist.param1 = 5.232180204916029;

29relay->states[2].iat_dist.param2 = 5.469677647300559;

30relay->states[2].dist_max_sample_usec = 94733;

31relay->states[2].next_state[CIRCPAD_EVENT_PADDING_SENT] = 2;

32relay->states[2].next_state[CIRCPAD_EVENT_PADDING_RECV] = 3;

33

34relay->states[3].length_dist.type = CIRCPAD_DIST_LOG_LOGISTIC;

35relay->states[3].length_dist.param1 = 1.6167675237934875;

36relay->states[3].length_dist.param2 = 6.128003159320049;

37relay->states[3].start_length = 5;

38relay->states[3].iat_dist.type = CIRCPAD_DIST_UNIFORM;

39relay->states[3].iat_dist.param1 = 4.270468437086448;

40relay->states[3].iat_dist.param2 = 7.926284402139126;

41relay->states[3].dist_max_sample_usec = 55878;

42relay->states[3].next_state[CIRCPAD_EVENT_NONPADDING_RECV] = 3;

43relay->states[3].next_state[CIRCPAD_EVENT_NONPADDING_SENT] = 0;

44relay->states[3].next_state[CIRCPAD_EVENT_PADDING_RECV] = 2;

45

46relay->machine_num = smartlist_len(relay_padding_machines);

47circpad_register_padding_machine(relay, relay_padding_machines);

##  Appendix B Interspace

###  B.1. Client

⬇

1const struct uniform_t my_uniform = {

2 .base = UNIFORM(my_uniform),

3 .a = 0.0,

4 .b = 1.0,

5};

6

7circpad_machine_spec_t *client =
tor_malloc_zero(sizeof(circpad_machine_spec_t));

8client->conditions.state_mask = CIRCPAD_CIRC_STREAMS;

9client->conditions.purpose_mask = CIRCPAD_PURPOSE_ALL;

10client->conditions.reduced_padding_ok = 1;

11

12client->name = "interspace_client";

13client->machine_index = 0;

14client->target_hopnum = 2;

15client->is_origin_side = 1;

16client->allowed_padding_count = 1500;

17client->max_padding_percent = 50;

18circpad_machine_states_init(client, 3);

19

20// wait until the relay is active

21client->states[0].next_state[CIRCPAD_EVENT_PADDING_RECV] = 1;

22

23// wait for something to either mask the length of or inject a fake request

24client->states[1].next_state[CIRCPAD_EVENT_NONPADDING_RECV] = 2;

25if (dist_sample(&my_uniform.base) < 0.5) {

26 client->states[1].next_state[CIRCPAD_EVENT_PADDING_RECV] = 2;

27}

28

29client->states[2].length_dist.type = CIRCPAD_DIST_PARETO;

30client->states[2].length_dist.param1 = 4.7;

31client->states[2].length_dist.param2 = 4.8;

32client->states[2].start_length = 1;

33client->states[2].iat_dist.type = CIRCPAD_DIST_PARETO; // tweak for log-
logistic?

34client->states[2].iat_dist.param1 = 3.3;

35client->states[2].iat_dist.param2 = 7.2;

36client->states[2].dist_max_sample_usec = 9445;

37client->states[2].next_state[CIRCPAD_EVENT_NONPADDING_SENT] = 1;

38client->states[2].next_state[CIRCPAD_EVENT_PADDING_SENT] = 2;

39if (dist_sample(&my_uniform.base) < 0.5) {

40 client->states[2].next_state[CIRCPAD_EVENT_NONPADDING_RECV] = 1;

41}

42

43client->machine_num = smartlist_len(origin_padding_machines);

44circpad_register_padding_machine(client, origin_padding_machines);

###  B.2. Relay

⬇

1circpad_machine_spec_t *relay =
tor_malloc_zero(sizeof(circpad_machine_spec_t));

2

3// short define for sampling uniformly random [0,1.0]

4const struct uniform_t my_uniform = {

5 .base = UNIFORM(my_uniform),

6 .a = 0.0,

7 .b = 1.0,

8};

9#define CIRCPAD_UNI_RAND (dist_sample(&my_uniform.base))

10

11// uniformly random select a distribution parameters between [0,10]

12#define CIRCPAD_RAND_DIST_PARAM1 (CIRCPAD_UNI_RAND*10)

13#define CIRCPAD_RAND_DIST_PARAM2 (CIRCPAD_UNI_RAND*10)

14

15relay->name = "interspace_relay";

16relay->machine_index = 0;

17relay->target_hopnum = 2;

18relay->is_origin_side = 0;

19relay->allowed_padding_count = 1500;

20relay->max_padding_percent = 50;

21circpad_machine_states_init(relay, 4);

22

23if (CIRCPAD_UNI_RAND < 0.5) {

24 /*

25 machine has following states:

26 0. init: don’t waste time early

27 1. wait: either extend or fake

28 2. extend: obfuscate length of existing bursts

29 3. fake: inject fake bursts

30 */

31

32 // wait for client to send something, no point in doing stuff too early

33 relay->states[0].next_state[CIRCPAD_EVENT_NONPADDING_RECV] = 1;

34

35 if (CIRCPAD_UNI_RAND < 0.5) {

36 // wait: extend real burst

37 relay->states[1].next_state[CIRCPAD_EVENT_NONPADDING_SENT] = 2;

38 } else {

39 // wait: inject a fake burst after a while (FIXME: too long below)

40 relay->states[1].iat_dist.type = CIRCPAD_DIST_LOG_LOGISTIC;

41 relay->states[1].iat_dist.param1 = CIRCPAD_UNI_RAND*1000; // alpha, scale
and mean

42 relay->states[1].iat_dist.param2 = CIRCPAD_UNI_RAND*10000; // shape, when >
1 larger reduces dispersion

43 relay->states[1].dist_max_sample_usec = 100000;

44 relay->states[1].next_state[CIRCPAD_EVENT_PADDING_SENT] = 3;

45 }

46

47 // extend: add fake padding for real bursts

48 relay->states[2].length_dist.type = CIRCPAD_DIST_PARETO;

49 relay->states[2].length_dist.param1 = CIRCPAD_RAND_DIST_PARAM1;

50 relay->states[2].length_dist.param2 = CIRCPAD_RAND_DIST_PARAM2;

51 relay->states[2].start_length = 1;

52 relay->states[2].iat_dist.type = CIRCPAD_DIST_PARETO;

53 relay->states[2].iat_dist.param1 = CIRCPAD_RAND_DIST_PARAM1;

54 relay->states[2].iat_dist.param2 = CIRCPAD_RAND_DIST_PARAM2;

55 relay->states[2].dist_max_sample_usec = 10000;

56 relay->states[2].next_state[CIRCPAD_EVENT_NONPADDING_SENT] = 1;

57 relay->states[2].next_state[CIRCPAD_EVENT_PADDING_SENT] = 2;

58

59 // fake: inject completely fake bursts

60 relay->states[3].length_dist.type = CIRCPAD_DIST_PARETO;

61 relay->states[3].length_dist.param1 = CIRCPAD_RAND_DIST_PARAM1;

62 relay->states[3].length_dist.param2 = CIRCPAD_RAND_DIST_PARAM2;

63 relay->states[3].start_length = 4;

64 relay->states[3].iat_dist.type = CIRCPAD_DIST_PARETO;

65 relay->states[3].iat_dist.param1 = CIRCPAD_RAND_DIST_PARAM1;

66 relay->states[3].iat_dist.param2 = CIRCPAD_RAND_DIST_PARAM2;

67 relay->states[3].dist_max_sample_usec = 10000;

68 relay->states[3].next_state[CIRCPAD_EVENT_NONPADDING_SENT] = 1;

69 relay->states[3].next_state[CIRCPAD_EVENT_PADDING_SENT] = 3;

70} else {

71 // spring-mr

72 relay->states[0].iat_dist.type = CIRCPAD_DIST_LOG_LOGISTIC;

73 relay->states[0].iat_dist.param1 = CIRCPAD_RAND_DIST_PARAM1;

74 relay->states[0].iat_dist.param2 = CIRCPAD_RAND_DIST_PARAM2;

75 relay->states[0].dist_max_sample_usec = 10000;

76 relay->states[0].next_state[CIRCPAD_EVENT_NONPADDING_RECV] = 1;

77 relay->states[0].next_state[CIRCPAD_EVENT_PADDING_RECV] = 1;

78

79 relay->states[1].iat_dist.type = CIRCPAD_DIST_LOG_LOGISTIC;

80 relay->states[1].iat_dist.param1 = CIRCPAD_RAND_DIST_PARAM1;

81 relay->states[1].iat_dist.param2 = CIRCPAD_RAND_DIST_PARAM2;

82 relay->states[1].dist_max_sample_usec = 31443;

83 relay->states[1].next_state[CIRCPAD_EVENT_NONPADDING_SENT] = 2;

84

85 relay->states[2].length_dist.type = CIRCPAD_DIST_LOG_LOGISTIC;

86 relay->states[2].length_dist.param1 = CIRCPAD_RAND_DIST_PARAM1;

87 relay->states[2].length_dist.param2 = CIRCPAD_RAND_DIST_PARAM2;

88 relay->states[2].start_length = 5;

89 relay->states[2].iat_dist.type = CIRCPAD_DIST_LOG_LOGISTIC;

90 relay->states[2].iat_dist.param1 = CIRCPAD_RAND_DIST_PARAM1;

91 relay->states[2].iat_dist.param2 = CIRCPAD_RAND_DIST_PARAM2;

92 relay->states[2].dist_max_sample_usec = 100000;

93 relay->states[2].next_state[CIRCPAD_EVENT_PADDING_SENT] = 2;

94 relay->states[2].next_state[CIRCPAD_EVENT_PADDING_RECV] = 3;

95

96 relay->states[3].length_dist.type = CIRCPAD_DIST_LOG_LOGISTIC;

97 relay->states[3].length_dist.param1 = CIRCPAD_RAND_DIST_PARAM1;

98 relay->states[3].length_dist.param2 = CIRCPAD_RAND_DIST_PARAM2;

99 relay->states[3].start_length = 5;

100 relay->states[3].iat_dist.type = CIRCPAD_DIST_LOG_LOGISTIC;

101 relay->states[3].iat_dist.param1 = CIRCPAD_RAND_DIST_PARAM1;

102 relay->states[3].iat_dist.param2 = CIRCPAD_RAND_DIST_PARAM2;

103 relay->states[3].dist_max_sample_usec = 55878;

104 relay->states[3].next_state[CIRCPAD_EVENT_NONPADDING_RECV] = 3;

105 relay->states[3].next_state[CIRCPAD_EVENT_NONPADDING_SENT] = 0;

106 relay->states[3].next_state[CIRCPAD_EVENT_PADDING_RECV] = 2;

107}

108

109relay->machine_num = smartlist_len(relay_padding_machines);

110circpad_register_padding_machine(relay, relay_padding_machines);


expressed, as in the main text, as a linear combination of the product
attributes; again, $\gamma_{n}$ denotes the marginal utility of social signals
for $n$. We assume again that the status-quo utility from not adopting is
fixed: $\bar{U}^{*}_{n}(t)=U^{(0)}_{n}$, where $U^{(0)}_{n}$ is a parameter
that could represent the price or risk associated with the adoption. In the
low-clarity regime Eq. (11), we obtain that $\Pi_{n}$ follows the Bass
equation with innovation parameter
$p_{n}=(1-c\,(U^{(0)}_{n}-U^{(A)}_{n}))/2=1/2-c\,R_{n}/4=1/2-R_{n}/T$ and
imitation parameter $q_{n}=c\,\gamma_{n}/4=\gamma_{n}/T$, where we defined the
temperature parameter Marsili [1999], Bouchaud [2013] as $T=4/c$, where factor
$4$ is introduced solely for cosmetic reasons. The role of temperature
parameter $T$ influences the Bass model’s parameter: In the infinite-
temperature limit, the choice is only determined by the stochastic component
of the utility. In this limit, the innovation parameter reflects a coin flip
($1/2$ probability) and the social signal plays no role (zero imitation
parameter). As the temperature is large (necessary to derive the linear
adoption probability) but finite, $p_{n}$ deviates from $1/2$ and $q_{n}>0$.
The finite-temperature result matches our intuition: the higher the resistance
of individual $n$ for the product, the lower the innovation coefficient; the
higher $n$’s marginal utility from the social signal, the higher the imitation
coefficient.

This simple argument shows that not only complex contagion models, but also
simple contagion ones can be reinterpreted in terms of the proposed micro-
level framework. Under standard assumption in discrete-choice theory, if the
utility from adopting grows as a power-law of the social signal, the two
considered complex and simple contagion models emerge naturally in the high-
and low-clarity regimes. Taken together, these findings suggest that
individual-level models might benefit policies to maximize or prevent social
spreading for a broader class of models than the complex contagion one studied
in the main text. We leave the derivation of alternative models of simple
contagions (e.g., rumor spreading models Borge-Holthoefer and Moreno [2012]
and empirical diffusion models Aral and Dhillon [2018]) for future research.

###  S6.4 Preferential attachment and fitness models

##### Pure preferential attachment.

When applied to social systems, preferential attachment models capture the
collective recognition received by cultural products such as scientific papers
Wang et al. [2013], patents Higham et al. [2017], books Yucesoy et al. [2018],
and online articles Capocci et al. [2006] as well as individuals in
collaboration networks Newman [2001], among others. We assume that individual
$n$ is faced with $I$ alternatives, and that her utility from adopting is
affected by the aggregate social signal, $s$, she receives about each of the
alternatives, which represents their total number of previous adopters. Assume
that individual $n$ exhibits decreasing marginal utility from the social
signal, which means that in response to an increase $ds$ in the social signal
received about a given product, her utility for that alternative increases by
$du=\gamma\,ds/s$. Under this assumption, the systematic component of $n$’s
utility from adopting $i$ is

$U^{*}_{ni}=\gamma_{n}\log{(s_{i})}.$ (18)

Under this assumption, whenever $n$ makes a new adoption decision among $I(t)$
available alternatives at time $t$,from Eq. (7), the probability she chooses
$i$ is

$P_{ni}=\frac{s_{i}^{\gamma_{n}}}{\sum_{j=1}^{I(t)}s_{j}^{\gamma_{n}}},$ (19)

where the sum in the denominator runs over the $I(t)$ available alternatives
at time $t$. Eq. (19) corresponds to a non-linear preferential attachment
model with heterogeneous exponent. If $\gamma_{n}=\gamma$ is homogeneous, we
recover a standard nonlinear preferential attachment model Barabási [2016];
with $\gamma=1$, we recover the standard preferential attachment model, as
noted by ref. Overgoor et al. [2019] in the context of network formation
models. It is interesting to note how a mild preference for more popular
alternatives can be amplified when moving from the individual-level utility
function to the collective adoption dynamics: The utility function scales only
logarithmically with $s$ (Eq. (18)), but the probability of adoption scales
linearly with $s$ (Eq. (19)); in the collective dynamics, this results in
extreme success inequalities (heavy-tailed distribution of $s$ Barabási
[2016]).

##### Generalized preferential attachment and fitness models.

Preferential attachment is not the only driving factor in state-of-the-art
models for characterizing and predicting the dynamics of scientific impact
Medo et al. [2011], Wang et al. [2013], book sales Yucesoy et al. [2018].
These studies consider more sophisticated models where alternatives are
characterized by their fitness level (which captures the intrinsic
attractiveness of an alternative’s qualities to the potential adopters) and an
aging function (which can capture the lower attractiveness of older
alternatives or more complex temporal patterns, e.g., for scientific paper
impact Medo et al. [2011], Wang et al. [2013]). To derive the relevance model
Medo et al. [2011], consider the following utility from adopting alternative
$i$:

$U^{*}_{ni}(t)=\gamma_{n}\log{(s_{i}(t))}+U^{A}_{ni}+\delta_{n}\,\phi(t-t_{i}),$
(20)

where:

  * •

The first preferential attachment term is analogous to Eq. (18).

  * •

The “fitness” component of the utility, $U^{A}_{ni}$, is analogous to the
attribute utility in main text. As in main text, in line with the consumer
behavior literature, it could be operationalized as
$U^{A}_{ni}=\sum_{a}\beta_{na}\,x_{ai}$, where $x_{ai}$ is the value taken by
attribute $a$ for alternative $i$ and $\beta_{na}$ captures $n$’s preference
for attribute $a$.

  * •

The age-dependent component of the utility depends on function $\phi(t-t_{i})$
depends on alternative $i$’s age (where $t_{i}$ denotes the time at which $i$
enters the system), while $\delta_{n}$ denotes $n$’s preference for old
products, which could very across individuals Medo et al. [2016], Catalini and
Tucker [2017].

With this utility function, the probability that $n$ adopts $\alpha$ at time
$t$ is

$\Pi_{ni}(t)=\frac{s_{i}(t)^{\gamma_{n}}\,\exp{(U^{A}_{ni})}\,\exp{(\delta_{n}\,\phi(t-t_{i}))}}{\sum_{j}s_{j}(t)^{\gamma_{n}}\,\exp{(U^{A}_{nj})}\,\exp{(\delta_{n}\,\phi(t-t_{j}))}}$
(21)

where $\exp{(U^{A}_{ni})}$ captures the intrinsic attractiveness of $i$’s
attributes for individual $n$ and $\Phi(t-t_{i})=\exp{(\phi(t-t_{i}))}$ plays
the role of an aging function (note that a linear preference for more recent
items in the utility function results in an exponential aging function). With
suitable simplifying assumptions, we can recover various preferential
attachment models from this expression.

  * •

Preferential attachment with fitness and aging. When $\gamma_{n}=1$
(homogeneous susceptibility to the social signal), $\delta_{n}=1$ (homogeneous
age preference), $\beta_{na}=\beta_{a}$ (homogeneous attribute preference), we
obtain the preferential attachment with fitness and aging Wang et al. [2013]:

$\Pi_{ni}(t)=\Pi_{i}(t)=\frac{s_{i}(t)\,\eta_{i}\,\Phi(t-t_{i})}{\sum_{j}s_{j}(t)\,\eta_{j}\,\Phi(t-t_{j})},$
(22)

where an alternative’s fitness is provided by
$\eta_{i}=\exp{(\sum_{a}\beta_{a}\,x_{ai})}$. A related model can be also
obtained without the homogeneous preference assumption, under the mean-field
assumption222See Medo et al. Medo et al. [2011] for a detailed discussion of
the plausibility and range of applicability this approximation. that the
denominator of $\Pi_{i}$ converges toward a constant value $\Omega^{*}$ Medo
et al. [2011]. Under this assumption, the rate at which alternative $i$
attracts more choices is $\propto s_{i}(t)\,\tilde{\eta}_{i}\,\Phi(t-t_{i})$,
where $\tilde{\eta}_{i}$ provides an alternative interpretation of an
alternative’s fitness as the average of the individuals’ preference factor,
$\exp{(U^{A}_{ni})}$, in line with the interpretation in Refs. Lynn et al.
[2009], Wang et al. [2013].

  * •

Preferential attachment with fitness. Under the homogeneous preference
assumption, by setting $\delta_{n}=0$, we obtain the Bianconi-Barabási model
Bianconi and Barabási [2001].

  * •

Fitness models without preferential attachment. By setting $\gamma_{n}=0$,
fitness models without preferential attachment like those considered by Refs.
Ghadge et al. [2010], Golosovsky [2018] can be obtained.

  * •

Preferential attachment with homophily. Models that take into account
homophily include the popularity-similarity model Papadopoulos et al. [2012]
and the more recent model in ref. Karimi et al. [2018]. For example, the
preferential attachment with homophily model by ref. Karimi et al. [2018] can
be simply obtained from Eq. (21) by setting $\gamma_{n}=1$ and $\delta_{n}=0$.

  * •

Heterogeneous models. Using Eq. (21), one can derive preferential attachment
models that include behavioral heterogeneity.