[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
[freehaven-cvs] Write simulation section. Results and discussion of ...
Update of /home/freehaven/cvsroot/doc/e2e-traffic
In directory moria.mit.edu:/tmp/cvs-serv11149
Modified Files:
e2e-traffic.tex e2e-traffic.bib
Log Message:
Write simulation section. Results and discussion of results are still missing,
and will come next.
Also, bump font size to 11 points as required by submission
guidelines. We are now at 15 pages, excluding bibliography.
Index: e2e-traffic.tex
===================================================================
RCS file: /home/freehaven/cvsroot/doc/e2e-traffic/e2e-traffic.tex,v
retrieving revision 1.16
retrieving revision 1.17
diff -u -d -r1.16 -r1.17
--- e2e-traffic.tex 21 Jan 2004 05:02:11 -0000 1.16
+++ e2e-traffic.tex 22 Jan 2004 03:50:14 -0000 1.17
@@ -1,6 +1,7 @@
% $Id$
-\documentclass{llncs}
+% The CFP requests '11 point font and reasonable margins'.
+\documentclass[11pt]{llncs}
%\documentclass{article}
%\usepackage{times}
@@ -13,6 +14,8 @@
\newcommand\XXXX[1]{{\small\bf [XXXX #1]}}
\newcommand\PMIX{P_{\mbox{\scriptsize MIX}}}
+\newcommand\Pobserve{P_{\mbox{\scriptsize observe}}}
+\newcommand\Ponline{P_{\mbox{\scriptsize online}}}
\newcommand\V[1]{\overrightarrow{#1}}
\newcommand\B[1]{\overline{#1}}
@@ -33,7 +36,7 @@
\email{\{nickm,arma\}@freehaven.net}}
\maketitle
-\centerline{\LARGE\bf *DRAFT* --- not for publication}
+\centerline{\LARGE\bf *DRAFT*---not for publication}
%======================================================================
\begin{abstract}
We extend earlier research on mounting and resisting passive
@@ -718,34 +721,172 @@
%======================================================================
\section{Simulation results}
\label{sec:simulation}
+Above, we've repeatedly said that each complication of the sender or the
+network forces the attacker to gather more information. But how much?
+To find out, we ran a series of simulations of our attacks, first against the
+model of the original statistical disclosure attack, then against more
+sophisticated models. We describe our simulations and present results below.
-\subsection{The original statistical disclosure attack}
-\label{subsec:sim-statistical-disclosure}
+\subsubsection{The original statistical disclosure attack}
+%trial1
+First, we simulated Danezis's original statistical disclosure attack,
+choosing different values for $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$ addition 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
+from getting stuck on hopeless cases.)
-\subsection{Complex sender behavior and unknown background traffic}
-\label{subsec:sim-complex-senders}
+(Describe results)
-\subsection{Attacking pool mixes and mix-nets}
+\subsubsection{Complex sender behavior and unknown background traffic}
+% trial2
+The next simulation examines the consequences of a more complex model for
+background traffic, and of several related models for Alice's behavior.
+
+We model the background as a graph $N$ communicating parties, each of whom
+communicates with some of the others. We build this graph according to the
+``scale-free'' model proposed in \cite{scale-emergence} and analyzed in
+\cite{scale-analysis}, which shares desirable properties with ``small-world''
+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
+the WWW.
+
+%Should I include this?
+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
+popularity (connectedness). This simulates a case where users send messages
+with equal frequency and choose recipients uniformly from among the people
+they know.
+
+Again, we simulated trial attacks for different values of $N$ (the number of
+recipients), $m$ (the number of Alice's recipients), and $b$ (the batch
+size). Instead of contributing one message per batch, however, Alice now
+contributes messages according to a geometric distribution with parameter
+$P_{M}$ (such that Alice sends $n$ messages with probability $P_m(n) =
+(1-P_M)P_M^n$). We also tried three methods for assigning Alice's
+recipients: In the `uniform/uniform' (UU) model, Alice's $m$ recipients are
+chosen uniformly from among the $N$ recipients in the graph, and Alice sends
+to each of them with uniform probability. In the `background/uniform' (BU)
+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. Finally,
+in the `background/background' (BB) 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 three
+models to examine the attack's effectiveness against users whose behavior was
+unrelated to other users' behavior (UU), users whose behavior was generated
+with the same model ather users' (BU), and users who mimiced the background
+distribution (BB).
+
+(Describe results)
+
+\subsubsection{Attacking pool mixes and mix-nets}
\label{subsec:sim-complex-mixes}
+%trials 3,4
+Pooling slows an attacker by increasing the number of possible output
+messages corresponding to each input message. To simulate an attack against
+pool mixes and mix-nets, we abstract away the actual pooling rule used by the
+network, and instead assume that the network has reached a steady state, so
+that each mix sends the same fraction of the messages in its pool every
+round. We also assume that all senders choose paths of exactly the same
+length.
-\subsection{The impact of dummy traffic}
+Unlike in the simulations above, `rounds' are now determined---not by a batch
+mix receiving a fixed number $b$ of messages---but by the passage of a fixed
+interval of time. Thus, the number of messages sent by the background is no
+longer a fixed $b-n_a$ (where $n_a$ is the number of messages Alice sends),
+but now follows a normal distribution with mean $B$ (and standard deviation
+set arbitrarily to $B/10$).\footnote{It's hard to determine the actual
+ standard deviation of message volumes on the currently deployed remailer
+ network: automatic reliability checkers that send messages to themselves
+ (``pingers'') contribute to a false sense of uniformity, while other users
+ generate volume spikes by sending enormous fragmented files, or maliciously
+ flooding discussion groups. Neither of these groups blends with the bulk
+ of the senders on the network.}
+
+(Results go here.)
+
+\subsubsection{The impact of dummy traffic}
\label{subsec:sim-dummies}
+%trials 5a,5b
+Several proposals exist for using dummy messages to frustrate traffic
+analysis. Although several of them have been examined in the context of
+low-latency systems \cite{defensive-dropping}, little work has been done to
+examine their effectiveness against long term intersection attacks.
-\subsection{The impact of partial observation}
-\label{subsec:sim-partial}
+First, we chose to restrict our examination (due to time limitations) to the
+effects of dummy messages in several cases of the pool-mix/mix-net simulation
+above. Because we are interested in learning how well dummies thwart
+analysis, we chose cases where, in the absence of dummies, the attacker had
+little trouble in learning Alice's recipients.
-\subsection{Attacking a nym service (full linkability)}
-\label{subsec:sim-full-linkability}
+% Are there better citations for these strategies? Are there better names?
+We evaluated the effectiveness of two padding strategies. The first
+strategy (`geometric padding') is based on the link padding strategy from
+the Mixminion design \cite{minion-design}: Alice generates a random number
+of dummy messages in each round according to a geometric distribution,
+independent of her number of real messages. With second strategy
+(`imperfect threshold-padding'), we assume that Alice attempts to implement
+the unbreakable threshold-padding strategy (always send $M$ messages total
+in every round, adding dummies up to $M$ as necessary), but that her
+implementation is imperfect: when she needs to send more than $M$ real
+messages, she does so anyway rather than wait for a later round; and she is
+only sometimes online (with probability $\Ponline$ each round), and cannot
+send real messages or padding when she is not. (This last deviation in
+particular will be typical for any real-world user attempting to implement
+threshold padding in a world of unreliable hardware and network
+connections.)
-\subsection{Attacking a fragmented community (partial linkability)}
-\label{subsec:sim-partial-linkability}
+(Results)
-\subsection{Attacking a suspicious user}
-\label{subsec:sim-suspicion}
+\subsubsection{The impact of partial observation}
+\label{subsec:sim-partial}
+%trial 6
+Finally, we examine the degree to which a non-global passive adversary can
+mount the statistical disclosure attack. Again, we base our simulation on
+the mix-net simulation where the attacker can only observe a few mixes, and
+try to see whether a non-global observer can do so also.
-% Not simulated: time-variant traffic, attacks against multiple
-% senders and recipients, partitioning attack
+% (have we defined 'entry'?)
+Clearly, if Alice chooses only from a fixed set of entry and exit mixes as
+suggested by (XXXX cite here XXXX), and the attacker is watching none of
+her chosen mixes, the attack will fail---and conversely, if the attacker is
+watching all of her chosen mixes, the attack proceeds as before. For our
+simulation, therefore, we assume that all senders (including Alice) choose
+all mixes as entry and exit points with equal probability for each message,
+and that the attacker is watching some fraction $f$ of the mixes. We
+simulate this by revealing each message entering or leaving the network to
+the attacker with probability $\Pobserve=f$.
+
+(Results.)
+
+%\subsection{Attacking a nym service (full linkability)}
+%\label{subsec:sim-full-linkability}
+%%nope
+%
+%\subsection{Attacking a fragmented community (partial linkability)}
+%\label{subsec:sim-partial-linkability}
+%%nope
+%
+%\subsection{Attacking a suspicious user}
+%\label{subsec:sim-suspicion}
+%%nope
+%
+%% Not simulated: time-variant traffic, attacks against multiple
+%% senders and recipients, partitioning attack
%======================================================================
\section{Conclusions}
@@ -753,20 +894,14 @@
\subsection{Implications for mix-net design}
\label{subsec:implications}
-\XXXX{I think I'll hold off drawing any conclusions until we have
- simulated/analytic results. If we're lucky, the results will
- suggest some method that resists intersection attacks without
- sending every single round or $N^2$ padding, and we can tell people
- to do that. If not, we'll need to suggest that users and networks
- be designed to maximize the number of observations an attacker
- needs; that users need to send dummy messages often enough to smooth
- out their $P_R$ from round to round; and ...?}
\subsection{Future work}
\label{subsec:future-work}
-\XXXX{One big question I want answered is: will any of the
- information-theoretic measurements turn out to be useful in
- analyzing this attack? If not, why not?}
+
+\section*{Acknowledgments}
+%Thanks also to Gerald Britton, Geoffrey Goodell, Pete St. Onge, Peter
+%Palfrader, Al Riddoch Mike Taylor, and Dave Turner for letting us run our
+%simulations on their computers.
%======================================================================
\bibliographystyle{plain} \bibliography{e2e-traffic}
Index: e2e-traffic.bib
===================================================================
RCS file: /home/freehaven/cvsroot/doc/e2e-traffic/e2e-traffic.bib,v
retrieving revision 1.4
retrieving revision 1.5
diff -u -d -r1.4 -r1.5
--- e2e-traffic.bib 21 Jan 2004 04:08:25 -0000 1.4
+++ e2e-traffic.bib 22 Jan 2004 03:50:14 -0000 1.5
@@ -78,7 +78,7 @@
year = {2003},
month = {March},
editor = {Roger Dingledine},
- publisher = {Springer-Verlag, LNCS 2760},
+ publisher = {SprRinger-Verlag, LNCS 2760},
www_ps_gz_url = {http://www.esat.kuleuven.ac.be/~cdiaz/papers/DS03.ps.gz},
}
@@ -376,3 +376,38 @@
www_pdf_url = {http://www.cl.cam.ac.uk/users/gd216/p125_danezis.pdf},
}
+
+@article{scale-emergence,
+ title = {Emergence of Scaling in Random Networkds},
+ author = {Albert-L\'azl\'o Barab\'asi and R\'eka Albert},
+ journal = {Science},
+ volume = {286},
+ year = {1999},
+ month = {October},
+ day = {15},
+ pages = {509--512},
+ www_pdf_url = {http://www.nd.edu/~networks/Papers/science.pdf}
+}
+
+@article{scale-analysis,
+ title = {Mean-field theory for scale-free random networks},
+ author = {Albert-L\'azl\'o Barab\'asi and R\'eka Albert and Hawoong Jeong},
+ journal = {Physica A},
+ volume = {272},
+ year = {2000},
+ pages = {173-187},
+ www_pdf_url={http://www.nd.edu/~networks/Papers/physica.pdf}
+}
+
+@article{small-worlds,
+ title = {Collective dynamics of `small-world' networks},
+ author = {Duncan J. Watts and Steven H. Strogatz},
+ journal = {Nature},
+ volume = {393},
+ pages = {440--442},
+ year = {1998},
+ month = {June},
+ day = {4},
+ www_pdf_url = {http://tam.cornell.edu/SS_nature_smallworld.pdf}
+}
+
***********************************************************************
To unsubscribe, send an e-mail to majordomo@seul.org with
unsubscribe freehaven-cvs in the body. http://freehaven.net/