[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
[freehaven-cvs] Add license comments; find another bug
Update of /home/freehaven/cvsroot/doc/e2e-traffic/src
In directory moria.mit.edu:/tmp/cvs-serv5638
Modified Files:
Makefile comb.h netparams.cpp netparams.h rng.cpp rng.h
sim.cpp sim.h simmain.cpp trials.cpp trials.h vec.cpp vec.h
Log Message:
Add license comments; find another bug
Index: Makefile
===================================================================
RCS file: /home/freehaven/cvsroot/doc/e2e-traffic/src/Makefile,v
retrieving revision 1.7
retrieving revision 1.8
diff -u -d -r1.7 -r1.8
--- Makefile 2 Dec 2003 20:15:46 -0000 1.7
+++ Makefile 11 Dec 2003 11:07:51 -0000 1.8
@@ -5,8 +5,7 @@
./test
CXX=g++
-CFLAGS=-Wall -O2 -g -DFAST_RANDOM
-#-DQUIET
+CFLAGS=-Wall -O2 -g -DFAST_RANDOM -DQUIET
clean:
rm -f *.o *~ sim test
Index: comb.h
===================================================================
RCS file: /home/freehaven/cvsroot/doc/e2e-traffic/src/comb.h,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -d -r1.1 -r1.2
--- comb.h 9 Aug 2003 02:35:13 -0000 1.1
+++ comb.h 11 Dec 2003 11:07:51 -0000 1.2
@@ -1,18 +1,22 @@
-
+// Copyright (c) 2003 Nick Mathewson. See LICENSE for licensing information.
+// $Id$
+// comb.h -- Basic combinatorics
#ifndef _COMB_H
#define _COMB_H
#include <assert.h>
+// return n factorial.
inline long fact(int n) {
assert(n>=0);
int r = 1;
for (int i = 2; i <= n; ++i) {
r *= i;
}
- return r;
+ return r;
}
+// return the number of combinations of n items taken k at a time.
inline long comb(int n, int k) {
/* COMB(n,k) = n!/(k!(n-k)!) */
assert(n>=0 && k>=0 && k<=n);
@@ -28,8 +32,9 @@
return r;
}
+// return the number of ways to place n identical items into k distinct bins.
inline long bins(int n, int k) {
- return comb(n+k, k);
+ return comb(n+k-1, k-1);
}
#endif
Index: netparams.cpp
===================================================================
RCS file: /home/freehaven/cvsroot/doc/e2e-traffic/src/netparams.cpp,v
retrieving revision 1.5
retrieving revision 1.6
diff -u -d -r1.5 -r1.6
--- netparams.cpp 11 Dec 2003 05:03:57 -0000 1.5
+++ netparams.cpp 11 Dec 2003 11:07:51 -0000 1.6
@@ -1,3 +1,6 @@
+// Copyright (c) 2003 Nick Mathewson. See LICENSE for licensing information.
+// $Id$
+// netparams.cpp -- Generate network parameters
#include <iostream.h>
#include <vector>
Index: netparams.h
===================================================================
RCS file: /home/freehaven/cvsroot/doc/e2e-traffic/src/netparams.h,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -d -r1.1 -r1.2
--- netparams.h 23 Aug 2003 19:04:29 -0000 1.1
+++ netparams.h 11 Dec 2003 11:07:51 -0000 1.2
@@ -1,10 +1,21 @@
+// Copyright (c) 2003 Nick Mathewson. See LICENSE for licensing information.
+// $Id$
+// netparams.h -- Calculate network parameters.
#ifndef _NETPARAMS_H
#define _NETPARAMS_H
#include "rng.h"
+// Return a distribution for rounds that a message will stay in a single
+// mix. In each round, the mix has a probability of 'pDelay' of holding
+// any given message in the pool for an another rounds.
InvDist<int> *getSingleMixDelays(double pDelay);
+// Return a distribution for rounds that a message will stay in a mixnet.
+// We assume that path lengths are chosen according to pathLenDist, and are
+// no longer than maxPathLen. We also assume that every message will arrive
+// within maxDelay rounds, and that a message is delayed at each mix with
+// probability pSingleDelay.
InvDist<int> *getMixNetDelays(const InvDist<int> &pathLenDist,
int maxPathLen,
double pSingleDelay,
@@ -14,7 +25,7 @@
# Albert-L\'aszl\'o Barab\'osi, R\'eka Albert, and Hawoong Jeong
Mean-field theory for scale-free random networks
Physica A 272, 173-187 (1999).
-[ PDF ] [ cond-mat/9907068 ]
+[ PDF ] [ cond-mat/9907068 ]
http://www.nd.edu/~networks/papers.htm#paper3
*/
@@ -23,11 +34,17 @@
equal to K^-gamma. (gamma ~= 2.4 ish)
Grow networks as:
- -> Every timestem add a new vertex.
+ -> Every timestep add a new vertex.
-> Prob of connecting to vertex I with connectivity K_i is
PI(k_i) = k_i / sum_j k_j.
*/
-
+
+// Generate traffic patterns for a small-worlds network according to
+// the above references. We generate a network of 'nRecipients' connected
+// recipients, of which Alice sends messages to 'nAliceRecipients'.
+// Background traffic is distributed according to recipients' connectedness.
+// If 'weightAlice' is true, then Alice also sends messages according to
+// the recipients' connectedness.
void getCommunicationLinks(Dist<int> *&aliceRecipDist,
Dist<int> *&backgroundTraffic,
std::vector<int> *&aliceRecipients,
Index: rng.cpp
===================================================================
RCS file: /home/freehaven/cvsroot/doc/e2e-traffic/src/rng.cpp,v
retrieving revision 1.5
retrieving revision 1.6
diff -u -d -r1.5 -r1.6
--- rng.cpp 11 Dec 2003 05:03:57 -0000 1.5
+++ rng.cpp 11 Dec 2003 11:07:51 -0000 1.6
@@ -1,4 +1,6 @@
-
+// Copyright (c) 2003 Nick Mathewson. See LICENSE for licensing information.
+// $Id$
+// rng.cpp -- Basic combinatorics
#include <stdlib.h>
#include <math.h>
#include "rng.h"
Index: rng.h
===================================================================
RCS file: /home/freehaven/cvsroot/doc/e2e-traffic/src/rng.h,v
retrieving revision 1.5
retrieving revision 1.6
diff -u -d -r1.5 -r1.6
--- rng.h 24 Nov 2003 00:33:27 -0000 1.5
+++ rng.h 11 Dec 2003 11:07:51 -0000 1.6
@@ -1,4 +1,6 @@
-
+// Copyright (c) 2003 Nick Mathewson. See LICENSE for licensing information.
+// $Id$
+// rng.h -- random number code
#ifndef _RNG_H
#define _RNG_H
@@ -6,27 +8,38 @@
#include <cmath>
#include "comb.h"
+// Return a pseudorandom number between 0.0 and 1.0.
double rng();
+// Return a pseudorandom number according to a normal distribution with
+// mean 0.0 and std deviation 1.0
double normal_rng();
-inline int rng(int m) { return static_cast<int>(rng()*m); }
+// Return a pseudorandom number x such that 0 <= x < m
+inline int rng(int m) { return (int) (rng()*m); }
+
+// Abstract base class: random distribution of elements of type C.
template <class C>
class Dist
{
public:
+ // return a random element from this distribution
virtual C get() const = 0;
+ // return a new copy of this distribution
virtual Dist<C> *copy() const = 0;
virtual ~Dist() {}
};
-// 'invertible' discrete distribution.
+// Abstract base class: an 'invertible' discrete distribution of elements of
+// type C.
template <class C>
class InvDist : public Dist<C>
{
public:
+ // Return the probability of v in this distribution.
virtual double getP(const C &v) const = 0;
};
+// Distrubution with only a single element of probability 1.0.
template <class C>
class ConstDist : public InvDist<C>
{
@@ -40,6 +53,7 @@
~ConstDist() {}
};
+// Geometric distribution.
class GeometricDist : public InvDist<int>
{
private:
@@ -48,12 +62,13 @@
GeometricDist(double param) : p(param) {}
Dist<int> *copy() const { return new GeometricDist(p); }
int get() const { int v = 0; while (rng() > p) ++v; return v; }
- double getP(const int &val) const {
+ double getP(const int &val) const {
return p * std::pow(1-p, (int)val);
}
~GeometricDist() {}
};
+// Binomial distribution.
class BinomialDist : public InvDist<int>
{
private:
@@ -62,8 +77,8 @@
public:
BinomialDist(double prob, int maximum) : p(prob), n(maximum) {}
Dist<int> *copy() const { return new BinomialDist(p, n); }
- int get() const {
- int v = 0;
+ int get() const {
+ int v = 0;
for (int i = 0; i < n; ++i) {
if (rng() < p) ++v;
}
@@ -75,10 +90,15 @@
~BinomialDist() {}
};
+// Distribution assigning an arbitrary fixed probability to values 0..M-1, for
+// some M.
class CumulativeDist : public InvDist<int>
{
private:
+ // M-element vector, containing the probability of each item in range 0..M-1
std::vector<double> prob;
+ // M-element vector containing, for each element i, the probability
+ // of that element or any lesser one.
std::vector<double> cumDist;
public:
CumulativeDist(const std::vector<double> &dist);
@@ -92,15 +112,19 @@
~CumulativeDist() {}
};
+// Optimized version of OCumulativeDist
class OCumulativeDist : public InvDist<int>
{
private:
+ // M-element vector, containing the probability of each item in range 0..M-1
std::vector<double> prob;
+ // N-element vector of items in the range 0..M-1, such that the number of
+ // elements with value x is proportional to the probability of x.
std::vector<int> lookupTable;
public:
OCumulativeDist(const std::vector<int> &dist);
OCumulativeDist(const std::vector<double> &dist, double granularity);
- OCumulativeDist(const OCumulativeDist &d) :
+ OCumulativeDist(const OCumulativeDist &d) :
prob(d.prob), lookupTable(d.lookupTable) {}
Dist<int> *copy() const { return new OCumulativeDist(*this); }
OCumulativeDist & operator=(const OCumulativeDist &d)
@@ -111,6 +135,7 @@
~OCumulativeDist() {}
};
+// Distribution choosing uniformly between a number of choices.
template<class C>
class UniformChoiceDist : public InvDist<C>
{
@@ -123,9 +148,10 @@
int n = choices.size();
for (int i = 0; i < n; ++i) { if (choices[i] == v) return 1.0/n; }
return 0.0; }
- ~UniformChoiceDist() {}
+ ~UniformChoiceDist() {}
};
+// Distribution choosing between two elements
template<class C>
class BinaryDist : public InvDist<C>
{
@@ -139,19 +165,20 @@
Dist<C> *copy() const { return new BinaryDist<C>(p,c1,c2); }
C get() const { if (rng()<p) return c1; else return c2; }
double getP(const C& v) const {
- if (v == c1) return p;
+ if (v == c1) return p;
else if (v == c2) return 1-p;
else return 0;
}
~BinaryDist() {}
};
+// Normal distribution, rounded to the nearest integer.
class IntNormalDist : public Dist<int>
{
double m, s;
bool clamp;
public:
- IntNormalDist(double mean, double stddev, bool clampToZero)
+ IntNormalDist(double mean, double stddev, bool clampToZero)
: m(mean), s(stddev), clamp(clampToZero) {}
Dist<int> *copy() const { return new IntNormalDist(m,s,clamp); }
int get() const {
@@ -160,12 +187,15 @@
}
};
+// Return a random element of the vector v.
template<class C>
const C &rng_pick(const std::vector<C> &v) { return v[rng(v.size())]; }
template<class C>
C &rng_pick(std::vector<C> &v) { return v[rng(v.size())]; }
-template<class C> void
+// Re-order the elements of a vector v at random. If 'n' is provided,
+// then shuffle 'n' random elements to the front.
+template<class C> void
rng_shuffle(std::vector<C> &v, int n=-1) {
int sz = v.size();
if (n == -1) { n = v.size()-1; }
Index: sim.cpp
===================================================================
RCS file: /home/freehaven/cvsroot/doc/e2e-traffic/src/sim.cpp,v
retrieving revision 1.7
retrieving revision 1.8
diff -u -d -r1.7 -r1.8
--- sim.cpp 11 Dec 2003 05:03:57 -0000 1.7
+++ sim.cpp 11 Dec 2003 11:07:51 -0000 1.8
@@ -1,4 +1,5 @@
-
+// Copyright (c) 2003 Nick Mathewson. See LICENSE for licensing information.
+// $Id$
#include <iostream>
#include "sim.h"
#include "rng.h"
Index: sim.h
===================================================================
RCS file: /home/freehaven/cvsroot/doc/e2e-traffic/src/sim.h,v
retrieving revision 1.6
retrieving revision 1.7
diff -u -d -r1.6 -r1.7
--- sim.h 2 Dec 2003 20:15:46 -0000 1.6
+++ sim.h 11 Dec 2003 11:07:51 -0000 1.7
@@ -1,32 +1,57 @@
-
+// Copyright (c) 2003 Nick Mathewson. See LICENSE for licensing information.
+// $Id$
+// sim.h -- Simulation classes
#ifndef _SIM_H
#define _SIM_H
#include "vec.h"
#include "rng.h"
+// Message flow:
+//
+// Background -->
+// --> Mixnet ---> FwdAttacker
+// Alice -->
+
+
+// A target sender whose recipients the attacker is trying to identify.
class Alice {
public:
Alice() {}
+ // Add messages for a single round to the vector v_add. Set nAdd
+ // to the number of messages sent in this round.
virtual void addTraffic(vec<int> &v_add, int &nAdd) = 0;
virtual ~Alice();
};
+// Source of background traffic masking the target sender.
class Background {
public:
Background() {}
+ // Add nMessages to the traffic vector v_out.
virtual void addNTraffic(vec<int> &v_out, int nMessages) = 0;
+ // Add messages for a single round to the vector v_out according to
+ // the default background-size distribution. Set nOut to the number
+ // of messages added.
virtual void addTraffic(vec<int> &v_out, int &nOut) = 0;
virtual ~Background();
};
+// An attack algorithm: attempts learn Alice's recipients.
class FwdAttacker {
public:
FwdAttacker() {}
+ // Clear the attacker's memory.
virtual void reset() = 0;
+ // Add a round to the attacker's observations. The attacker sees that
+ // Alice has sent nSentAlice messages, that other users have send nSentOther
+ // messages, and that each recipient i has received nReceived[i] messages.
virtual void addRound(int nSentAlice, int nSentOther,
const vec<int> &nReceived) = 0;
+ // Guess Alice's recipients, based on past observations. Set recipients[i]
+ // to our estimate of the probability that a message from Alice is to
+ // recipient i.
virtual bool guessAlice(vec<double> &recipients) = 0;
void getRoundCounts(int &nObs, int &nAlice) {
nObs = nAlice = 0;
@@ -35,10 +60,15 @@
virtual ~FwdAttacker() {}
};
+// A mixnet: distributes messages to their recipients (and to the attacker)
class Mixnet {
public:
Mixnet() {}
+ // clear the mixnet's memory.
virtual void reset() = 0;
+ // Send a round through the mixnet. The round countains nAlice messages
+ // from alice, and nBackground messages from other users. It contains
+ // input[i] messages to each recipient i.
virtual void addRound(const vec<int> &input,
int nAlice, int nBackground,
FwdAttacker *r) = 0;
@@ -49,6 +79,10 @@
// ======================================================================
// Original statistical disclosure attack
+// Sender that chooses recipients, messages, and dummies through random
+// distributions. Alternatively, if padding is sent, then we always
+// send at least padding messages and ignore the dummies dist. The
+// sender considers whether to participate in a round with probability pSend.
class DistAlice : public Alice {
protected:
Dist<int> *nMessageDist;
@@ -68,6 +102,7 @@
};
+// Sender that chooses recipients uniformly from a list
class UniformAlice : public DistAlice {
public:
UniformAlice(const std::vector<int> &r,
@@ -76,6 +111,7 @@
~UniformAlice() { }
};
+// Background that sends messages to recipients with uniform probability
class UniformBackground : public Background {
private:
int nRecipients;
@@ -87,6 +123,7 @@
void addTraffic(vec<int> &v_out, int &nOut);
};
+// Mix that accumulates B messages and then relays them all.
class BatchMix : public Mixnet {
private:
int batchSize;
@@ -99,6 +136,7 @@
~BatchMix() {}
};
+// Implements the original statistical disclosure attack
class SDAttacker : public FwdAttacker {
private:
int nRounds;
@@ -160,7 +198,7 @@
Dist<int> *delayDist;
protected:
- int getDelay() { int d = delayDist->get();
+ int getDelay() { int d = delayDist->get();
return d >= maxDelay ? maxDelay-1 : d; }
public:
Index: simmain.cpp
===================================================================
RCS file: /home/freehaven/cvsroot/doc/e2e-traffic/src/simmain.cpp,v
retrieving revision 1.8
retrieving revision 1.9
diff -u -d -r1.8 -r1.9
--- simmain.cpp 11 Dec 2003 05:03:57 -0000 1.8
+++ simmain.cpp 11 Dec 2003 11:07:51 -0000 1.9
@@ -1,4 +1,5 @@
-
+// Copyright (c) 2003 Nick Mathewson. See LICENSE for licensing information.
+// $Id$
#include <vector>
#include <algorithm>
#include <iostream>
Index: trials.cpp
===================================================================
RCS file: /home/freehaven/cvsroot/doc/e2e-traffic/src/trials.cpp,v
retrieving revision 1.6
retrieving revision 1.7
diff -u -d -r1.6 -r1.7
--- trials.cpp 11 Dec 2003 05:03:57 -0000 1.6
+++ trials.cpp 11 Dec 2003 11:07:51 -0000 1.7
@@ -1,4 +1,5 @@
-
+// Copyright (c) 2003 Nick Mathewson. See LICENSE for licensing information.
+// $Id$
#include <iostream>
#include <vector>
#include <cmath>
Index: trials.h
===================================================================
RCS file: /home/freehaven/cvsroot/doc/e2e-traffic/src/trials.h,v
retrieving revision 1.5
retrieving revision 1.6
diff -u -d -r1.5 -r1.6
--- trials.h 2 Dec 2003 20:15:46 -0000 1.5
+++ trials.h 11 Dec 2003 11:07:51 -0000 1.6
@@ -1,4 +1,5 @@
-
+// Copyright (c) 2003 Nick Mathewson. See LICENSE for licensing information.
+// $Id$
#ifndef _TRIALS_H
#define _TRIALS_H
Index: vec.cpp
===================================================================
RCS file: /home/freehaven/cvsroot/doc/e2e-traffic/src/vec.cpp,v
retrieving revision 1.2
retrieving revision 1.3
diff -u -d -r1.2 -r1.3
--- vec.cpp 11 Dec 2003 05:03:57 -0000 1.2
+++ vec.cpp 11 Dec 2003 11:07:51 -0000 1.3
@@ -1,4 +1,5 @@
-
+// Copyright (c) 2003 Nick Mathewson. See LICENSE for licensing information.
+// $Id$
#include "vec.h"
#include <functional>
Index: vec.h
===================================================================
RCS file: /home/freehaven/cvsroot/doc/e2e-traffic/src/vec.h,v
retrieving revision 1.4
retrieving revision 1.5
diff -u -d -r1.4 -r1.5
--- vec.h 11 Dec 2003 05:03:57 -0000 1.4
+++ vec.h 11 Dec 2003 11:07:51 -0000 1.5
@@ -1,4 +1,5 @@
-
+// Copyright (c) 2003 Nick Mathewson. See LICENSE for licensing information.
+// $Id$
#ifndef _VEC_H
#define _VEC_H
***********************************************************************
To unsubscribe, send an e-mail to majordomo@seul.org with
unsubscribe freehaven-cvs in the body. http://freehaven.net/