[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
[freehaven-cvs] clean trials 1 and 2, merge figs 1 and 2
Update of /home/freehaven/cvsroot/doc/e2e-traffic
In directory moria.mit.edu:/home2/arma/work/freehaven/doc/e2e-traffic
Modified Files:
e2e-traffic.tex
Log Message:
clean trials 1 and 2, merge figs 1 and 2
Index: e2e-traffic.tex
===================================================================
RCS file: /home/freehaven/cvsroot/doc/e2e-traffic/e2e-traffic.tex,v
retrieving revision 1.27
retrieving revision 1.28
diff -u -d -r1.27 -r1.28
--- e2e-traffic.tex 25 Jan 2004 09:47:30 -0000 1.27
+++ e2e-traffic.tex 25 Jan 2004 10:49:24 -0000 1.28
@@ -621,7 +621,7 @@
\subsubsection{Exploiting message partitioning:}
%\label{subsubsec:full-linkability}
The attacker's work can be greatly simplified if some output messages are
-{\it linkable}. Two messages are said to be linkable if they are
+{\it linkable}. Two messages are linkable if they are
likelier to originate from the same sender than are two randomly chosen
messages. We consider a special case of linkability, in which we discover
linkage by {\it partitioning} messages into separate classes such that
@@ -694,7 +694,7 @@
%======================================================================
\section{Simulation results}
\label{sec:simulation}
-In Section \ref{subsec:broadening}, we repeatedly claimed that each
+In Section \ref{subsec:broadening}, we repeatedly claim that each
complication of the sender or the
network forces the attacker to gather more information. But how much?
@@ -704,36 +704,54 @@
\subsubsection{The original statistical disclosure attack:}
%trial1
-First, we simulated Danezis's original statistical disclosure attack,
-varying the parameters $N$ (the number of recipients), $m$ (the number
+%We simulated Danezis's original statistical disclosure attack,
+Our simulation
+varied the parameters $N$ (the number of recipients), $m$ (the number
of Alice's recipients), and $b$ (the batch size). The simulated ``Alice''
sends a single message every round to one of her recipients, chosen uniformly
at random. The simulated background sends to $b-1$ additional recipients per
round, also chosen uniformly at random. We ran 100 trial attacks for each
-chosen $\left<N,m,b>\right>$ tuple. Each attack was set to halt when the
-attacker had correctly identified Alice's recipients, or until 1,000,000
-rounds had passed. (We imposed this cap on run time to keep our simulator
+chosen $\left<N,m,b\right>$ tuple. Each attack was set to halt when the
+attacker has correctly identified Alice's recipients, or when 1,000,000
+rounds have passed. (We imposed this cap on run time to keep our simulator
from getting stuck on hopeless cases.)
-\begin{figure}[ht]
-\centering
-\mbox{\epsfig{angle=0,figure=graphs/fig1,width=4in}}
-\caption{Statistical disclosure model: Median rounds to guess all recipients}
-\label{fig1}
-\end{figure}
+%\begin{figure}[ht]
+%\centering
+%\mbox{\epsfig{angle=0,figure=graphs/fig1,width=4in}}
+%\caption{Statistical disclosure model: Median rounds to guess all recipients}
+%\label{fig1}
+%\end{figure}
-We present the results of our simulations in Figure~\ref{fig1}.
-%% We don't do this next silly thing anymore. -NM
-%(We found
-%that the time required for the attacker to learn Alice's last few recipients
-%was highly variable, especially in later simulations, so we present instead
-%the $90^{th}$ percentile of number of rounds required to $m-1$ of Alice's
-%recipients, across 100 trials per data point.)
+%\begin{figure}[ht]
+%\centering
+%\mbox{\epsfig{angle=0,figure=graphs/fig2a,width=4in}}
+%\caption{Unknown background: Median rounds to guess all recipients}
+%\label{fig2a}
+%\end{figure}
+
+We present the results of our simulations in Figure~\ref{fig1} (the low-$m$ curves
+are at the bottom).
As expected, the attack
-becomes more effective when Alice sends messages to a broader group of
-recipients (large $m$); when there are fewer recipients for Alice to hide
+becomes more effective when Alice sends messages to only a few
+recipients (small $m$); when there are fewer recipients for Alice to hide
hers among (small $N$); or when batch sizes are small (small $b$).
+\begin{figure}
+\begin{minipage}[t]{5.75cm}
+\mbox{\epsfig{angle=0,figure=graphs/fig1,width=6cm}}
+\caption{Statistical disclosure model: Median rounds to guess all recipients}
+\label{fig1}
+\end{minipage}
+\hfill
+\begin{minipage}[t]{5.75cm}
+\mbox{\epsfig{angle=0,figure=graphs/fig2a,width=6cm}}
+\caption{Unknown background: Median rounds to guess all recipients}
+\label{fig2a}
+\end{minipage}
+\hfill
+\end{figure}
+
\subsubsection{Complex sender behavior and unknown background traffic:}
% trial2
The next simulation examines the consequences of a more complex model for
@@ -746,20 +764,20 @@
networks \cite{small-world}. Scale-free networks share the ``six degrees of
separation property'' (for arbitrary values of six) with small-world
networks, but also mimic the clustering and `organic' growth of real social
-networks, including citations in journals, co-actors in IMDB, and links in
+networks, including citations in journals, co-stars in IMDB, and links in
the WWW.
-
-%Should I include this? -NM
-%If we run low on space, I would take out the first half of it, and
-% merge the second half with the above paragraph. -RD
-The scale-free model works as follows: we begin with a small number of
-interconnected vertices (in our case, 2). Then, we iteratively add vertices
-to our graph, connecting each new vertex to every older vertex $i$ with
-probability $c_i/|E|$, where $c_i$ is the number of existing connections to
-vertex $i$, and $|E|$ is the total number of edges in the graph. Our
-simulation continues until it has generated $N$ connected vertices. For
-these trial attacks, the background messages were generated by choosing
-random nodes from the graph, with probability proportional to their
+%
+%%Should I include this? -NM
+%%If we run low on space, I would take out the first half of it, and
+%% merge the second half with the above paragraph. -RD
+%The scale-free model works as follows: we begin with a small number of
+%interconnected vertices (in our case, 2). Then, we iteratively add vertices
+%to our graph, connecting each new vertex to every older vertex $i$ with
+%probability $c_i/|E|$, where $c_i$ is the number of existing connections to
+%vertex $i$, and $|E|$ is the total number of edges in the graph. Our
+%simulation continues until it has generated $N$ connected vertices.
+For these trial attacks, the background messages were generated by
+choosing nodes from the graph with probability proportional to their
popularity (connectedness). This simulates a case where users send messages
with equal frequency and choose recipients uniformly from among the people
they know.
@@ -773,29 +791,22 @@
recipients: In the `uniform'
model, Alice's recipients are chosen according to their connectedness (so
that Alice, like everyone else, is likelier to know people who are already
-well-known), but Alice still sends to each with equal probability. In the
-`weighted' model, not only are Alice's recipients
-chosen according to their connectedness, but Alice also sends to them with
-probability proportional to their connectedness. We selected these
+well-known), but Alice still sends to each chosen recipient with equal
+probability. In the `weighted' model, not only are Alice's recipients
+chosen according to their connectedness, but Alice also sends to them
+proportional to their connectedness. We selected these
models to examine the attack's effectiveness against users whose behavior is
generated with the same model as other users' (U), and against users who mimic
the background distribution (W).
-\begin{figure}[ht]
-\centering
-\mbox{\epsfig{angle=0,figure=graphs/fig2a,width=4in}}
-\caption{Unknown background: Median rounds to guess all recipients}
-\label{fig2a}
-\end{figure}
-
The results are in Figure~\ref{fig2a}, along with the results for the
original statistical disclosure attack as reference. As expected, the attack
-succeeded easily, and finished faster against uniform senders for equivalent
-values of $\left<N,m,b>\right>$ than it did against weighted senders.
-Interestingly, the attack against 'uniform' senders was {\it faster} than the
+succeeds easily, and finishes faster against uniform senders than weighted
+senders for equivalent values of $\left<N,m,b\right>$.
+Interestingly, the attack against uniform senders was {\it faster} than the
original statistical disclosure attack---because the background traffic is
-now more clustered about popular recipients, Alice's recipients stand out
-more than they did before.
+now clustered about popular recipients, Alice's recipients stand out
+more. %than they did before.
%XXX say more? -NM
\subsubsection{Attacking pool mixes and mix-nets:}
***********************************************************************
To unsubscribe, send an e-mail to majordomo@seul.org with
unsubscribe freehaven-cvs in the body. http://freehaven.net/