[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
[freehaven-cvs] All the simple cases work.
Update of /home/freehaven/cvsroot/doc/e2e-traffic/src
In directory moria.mit.edu:/tmp/cvs-serv28591
Modified Files:
.cvsignore Makefile rng.cpp rng.h sim.cpp sim.h simmain.cpp
Added Files:
PLAN netparams.cpp netparams.h trials.cpp trials.h
Log Message:
All the simple cases work.
--- NEW FILE: PLAN ---
Simulations:
1 Original attack.
Mix=Batch, Alice=SD, Background=SD.
(class: SDTrial)
2 Attack with unknown background.
Mix=Batch, Alice=SD+pNoSend, Background=SmallWorld.
(class: UnkBGBatchTrial)
3 Attack with realistic sender/recipient model.
Mix=Batch, Alice=SmallWorld, Background=SmallWorld.
(class: UnkBGBatchTrial)
4 Attack with a timed dynamic-pool mix.
Mix=1mix, Alice=SmallWorld, Background=Smallworld
(class: DelayMixTrial)
5 Attack with a mix-net.
Mix=mixnet, Alice=SmallWorld, Background=Smallworld
(class: DelayMixTrial)
6 Attack with a mix-net and dummies
Mix=mixnet, Alice=SmallWorld+dummies, Background=Smallworld+dummies
(class: DelayMixTrial)
======================================================================
7 Partial observation: fraction of mixes
Mix=po_mixnet, Alice=SmallWorld+dummies,
Background=Smallworld+dummies
(class: PO_DelayMixTrial)
======================================================================
8 Nymservice
9 Fragmented community
10 Suspicious user
--- NEW FILE: netparams.cpp ---
#include <vector>
#include "assert.h"
#include "rng.h"
#include "netparams.h"
InvDist<int> *
getSingleMixDelays(double pDelay) {
assert(0.0 < pDelay && pDelay < 1.0);
return new ExponentialDist(pDelay);
}
InvDist<int> *
getMixNetDelays(const InvDist<int> &pathLenDist,
int maxPathLen,
double pSingleDelay,
int maxDelay)
{
std::vector<double> p(maxPathLen+maxDelay, 0.0);
for (int pathLen = 1; pathLen < maxPathLen; ++pathLen) {
double pathProb = pathLenDist.getP(pathLen);
if (!pathProb)
continue;
for (int d = 0; d < maxDelay; ++d) {
p[pathLen+d] += pathProb * bins(d, pathLen) *
std::pow(pSingleDelay, d) * std::pow(1.0-pSingleDelay, pathLen);
}
}
return new CumulativeDist(p, false);
}
void
getCommunicationLinks(Dist<int> *&aliceRecipDist,
Dist<int> *&backgroundTraffic,
std::vector<int> *&aliceRecipients,
int nAliceRecipients,
int nRecipients,
bool weightAlice)
{
assert(nAliceRecipients < nRecipients);
assert(nRecipients >= 3);
backgroundTraffic = aliceRecipDist = NULL;
// Generate the network connectivity.
std::vector<int> conns(nRecipients, 0);
int total = 0;
conns[0] = 2;
conns[1] = 2;
conns[2] = 2;
total = 6;
for (int i = 3; i < nRecipients; ++i) {
for (int j = 0; j < i; ++j) {
double pAdd = conns[j] / ((double)total);
if (rng() < pAdd) {
conns[i]++;
conns[j]++;
total += 2;
}
}
}
std::vector<double> pBackground(nRecipients, 0.0);
for (int i = 0; i < nRecipients; ++i) {
pBackground[i] = conns[i] / ((double)total);
}
backgroundTraffic = new CumulativeDist(pBackground);
std::vector<double> pAlice(nRecipients, 0.0);
double pTotalAlice = 0.0;
for (int i = 0; i < nAliceRecipients; ++i) {
int r;
do {
r = backgroundTraffic->get();
} while (pAlice[r]);
if (weightAlice) {
pAlice[r] = pBackground[r];
pTotalAlice += pBackground[r];
} else {
pAlice[r] = 1.0;
pTotalAlice += 1.0;
}
}
for (int i = 0; i < nAliceRecipients; ++i) {
pAlice[i] /= pTotalAlice;
}
aliceRecipients = new std::vector<int>(nAliceRecipients);
int j = 0;
for (int i = 0; i < nRecipients; ++i) {
if (pAlice[i]) {
(*aliceRecipients)[j++] = i;
}
}
aliceRecipDist = new CumulativeDist(pAlice, false);
}
--- NEW FILE: netparams.h ---
#ifndef _NETPARAMS_H
#define _NETPARAMS_H
#include "rng.h"
InvDist<int> *getSingleMixDelays(double pDelay);
InvDist<int> *getMixNetDelays(const InvDist<int> &pathLenDist,
int maxPathLen,
double pSingleDelay,
int maxDelay);
/*
# 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 ]
http://www.nd.edu/~networks/papers.htm#paper3
*/
/*
Need power-law distribution: probability that node has K vertices is
equal to K^-gamma. (gamma ~= 2.4 ish)
Grow networks as:
-> Every timestem add a new vertex.
-> Prob of connecting to vertex I with connectivity K_i is
PI(k_i) = k_i / sum_j k_j.
*/
void getCommunicationLinks(Dist<int> *&aliceRecipDist,
Dist<int> *&backgroundTraffic,
std::vector<int> *&aliceRecipients,
int nAliceRecipients,
int nRecipients,
bool weightAlice=0);
#endif // _NETPARAMS_H
--- NEW FILE: trials.cpp ---
#include <iostream>
#include <vector>
#include <cmath>
#include "trials.h"
#include "netparams.h"
template<class C>
void pvec(std::ostream &o, const std::vector<C> &v)
{
o << "{";
for (typename std::vector<C>::const_iterator i = v.begin(); i != v.end(); ++i) {
o << *i << " ";
}
o << "}" << std::endl;
}
void
TrialResult::write(std::ostream &out) const
{
out << "[rounds: "<< nRounds<<" (alice in "<< nRoundsAlice
<< ") messages: "<< nMsgs << " (alice sent "<< nMsgsAlice
<< ", "<< nMsgsAliceReal << " real)";
if (nRoundsMaybeAlice) {
out << ". observed rounds: "<<nRoundsObserved<<" (alice maybe in "
<< nRoundsMaybeAlice << ")";
}
out << "]";
}
std::ostream &
operator<<(std::ostream &out, const TrialResult &r)
{
r.write(out); return out;
}
TrialResult
BatchTrial::attempt()
{
TrialResult res;
mixnet->reset();
attacker->reset();
vec<int> aTraffic(nRecips, 0);
vec<int> bTraffic(nRecips, 0);
vec<double> recips(nRecips, 0.0);
int n = 0;
while (1) {
aTraffic.reset(0);
bTraffic.reset(0);
int nAlice;
alice->getTraffic(aTraffic, nAlice);
if (nAlice) {
res.nMsgsAlice += nAlice;
res.nMsgsAliceReal += aTraffic.total(0);
res.nRoundsAlice += 1;
}
background->getNTraffic(bTraffic, nBatch-nAlice);
res.nMsgs += nBatch;
//std::cout << n << " "<< aTraffic << std::endl;
mixnet->addRound(aTraffic, nAlice, bTraffic, attacker);
++n;
if (!(n % granularity)) {
if (!attacker->guessAlice(recips)) continue;
//std::cout << n << " " << recips << std::endl;
//std::cout << n << " ------ " << std::endl;
//pvec(std::cout, truth);
//pvec(std::cout, recips.topN(truth.size()));
//std::cout << n << " ------ " << std::endl;
if (truth == recips.topN(truth.size())) {
res.nRounds = n;
return res;
}
}
}
}
BatchTrial::~BatchTrial()
{
delete mixnet;
delete attacker;
delete background;
delete alice;
}
SDTrial::SDTrial(int nR, int nAR, int b, int g)
{
ConstDist<int> aMsgs(1);
ConstDist<int> aDummies(0);
truth = std::vector<int>(nAR, 0);
for (int i=0; i<nAR; ++i) { truth[i] = i; }
alice = new UniformAlice(truth, &aMsgs, &aDummies);
background = new UniformBackground(nR);
vec<double> uniform(nR, 1.0/b);
attacker = new SDAttacker(uniform);
mixnet = new BatchMix(b);
nRecips = nR;
nBatch = b; granularity = g;
}
SDTrial::~SDTrial()
{
}
UnkBGBatchTrial::UnkBGBatchTrial(int nR, int nAR, int b,
bool smallworldAlice,
bool expMsgDist,
double pMsgA, double pDA,
int padding,
int g)
{
ExponentialDist aMsgsE(1.0-pMsgA);
ExponentialDist aDummiesE(1.0-pDA);
BinaryDist<int> aMsgsB(pMsgA, 1, 0);
BinaryDist<int> aDummiesB(pDA, 1, 0);
Dist<int> *aliceRecipDist = 0;
Dist<int> *backgroundTrafficDist = 0;
std::vector<int> *aliceRecipients = 0;
getCommunicationLinks(aliceRecipDist, backgroundTrafficDist,
aliceRecipients,
nAR, nR);
if (smallworldAlice) {
truth = *aliceRecipients;
if (expMsgDist)
alice = new DistAlice(aliceRecipDist, &aMsgsE, &aDummiesE, padding);
else
alice = new DistAlice(aliceRecipDist, &aMsgsB, &aDummiesB, padding);
} else {
truth = std::vector<int>(nAR, 0);
for (int i=0; i<nAR; ++i) { truth[i] = i; }
if (expMsgDist)
alice = new UniformAlice(truth, &aMsgsE, &aDummiesE, padding);
else
alice = new UniformAlice(truth, &aMsgsB, &aDummiesB, padding);
}
ConstDist<int> oneDist(1); // ignored.
background = new DistBackground(*backgroundTrafficDist, oneDist);
delete aliceRecipDist;
delete backgroundTrafficDist;
delete aliceRecipients;
attacker = new UnkBGBatchAttacker(nR);
mixnet = new BatchMix(b);
nRecips = nR;
nBatch = b; granularity = g;
}
UnkBGBatchTrial::~UnkBGBatchTrial()
{
}
// ======================================================================
TrialResult
NonbatchTrial::attempt()
{
TrialResult res;
attacker->reset();
mixnet->reset();
vec<int> aTraffic(nRecips, 0);
vec<int> bTraffic(nRecips, 0);
vec<double> recips(nRecips, 0.0);
int n = 0;
while (1) {
aTraffic.reset(0);
bTraffic.reset(0);
int nAlice;
alice->getTraffic(aTraffic, nAlice);
if (nAlice) {
res.nMsgsAlice += nAlice;
res.nMsgsAliceReal += aTraffic.total(0);
res.nRoundsAlice += 1;
}
int nBackground;
background->getTraffic(bTraffic, nBackground);
res.nMsgs += nAlice + nBackground;
mixnet->addRound(aTraffic, nAlice, bTraffic, attacker);
++n;
if (!(n % granularity)) {
if (!attacker->guessAlice(recips)) continue;
std::cout << n << " ------ " << std::endl;
pvec(std::cout, truth);
pvec(std::cout, recips.topN(truth.size()));
std::cout << n << " ------ " << std::endl;
if (truth == recips.topN(truth.size())) {
res.nRounds = n;
return res;
}
}
}
}
NonbatchTrial::~NonbatchTrial()
{
delete alice;
delete background;
delete mixnet;
delete attacker;
}
MixTrial::MixTrial(int nR, int nAR, int pathLen, double pDelay,
bool expAlice, double pMessage, double pDummy,
double bgVolMean, double bgVolDev, int padding,
int g)
: NonbatchTrial(nR, g)
{
assert(pathLen > 0);
////
// Set up mixnet and attacker.
InvDist<int> *delayDist;
int maxDelay = static_cast<int>(std::log(0.01)/std::log(pDelay))+1;
if (pathLen == 1) {
delayDist = getSingleMixDelays(pDelay);
} else {
delayDist = getMixNetDelays(ConstDist<int>(pathLen), pathLen+1,
pDelay, maxDelay);
}
mixnet = new DelayMix(nR, maxDelay, delayDist);
attacker = new DelayMixAttacker(nR, maxDelay, delayDist);
delete delayDist;
//// Set up small world.
Dist<int> *aliceRecipDist = 0;
Dist<int> *backgroundTrafficDist = 0;
std::vector<int> *aliceRecipients = 0;
getCommunicationLinks(aliceRecipDist, backgroundTrafficDist,
aliceRecipients,
nAR, nR);
//// set up alice.
ExponentialDist aMsgsE(1.0-pMessage);
ExponentialDist aDummiesE(1.0-pDummy);
BinaryDist<int> aMsgsB(pMessage, 1, 0);
BinaryDist<int> aDummiesB(pDummy, 1, 0);
truth = *aliceRecipients;
if (expAlice)
alice = new DistAlice(aliceRecipDist, &aMsgsE, &aDummiesE, padding);
else
alice = new DistAlice(aliceRecipDist, &aMsgsB, &aDummiesB, padding);
//// set up background.
background = new DistBackground(*backgroundTrafficDist,
IntNormalDist(bgVolMean, bgVolDev, true));
delete aliceRecipDist;
delete backgroundTrafficDist;
delete aliceRecipients;
}
TrialResult
MixTrial::attempt()
{
TrialResult res = NonbatchTrial::attempt();
dynamic_cast<DelayMixAttacker*>(attacker)->getRoundCounts(
res.nRoundsObserved, res.nRoundsMaybeAlice);
return res;
}
--- NEW FILE: trials.h ---
#ifndef _TRIALS_H
#define _TRIALS_H
#include <iostream>
#include "sim.h"
#include "rng.h"
class TrialResult
{
public:
TrialResult() {
nRounds = nRoundsAlice = nRoundsObserved = nRoundsMaybeAlice = 0;
nMsgs = nMsgsAlice = nMsgsAliceReal = 0L;
}
int nRounds;
int nRoundsAlice;
long nMsgs;
long nMsgsAlice;
long nMsgsAliceReal;
// only interesting for DelayMix attacks
int nRoundsObserved;
int nRoundsMaybeAlice;
virtual void write(std::ostream &o) const;
virtual ~TrialResult() {}
};
std::ostream &operator<<(std::ostream &out,
const TrialResult &r);
class Trial {
public:
Trial() {}
virtual TrialResult attempt() = 0;
virtual ~Trial() {}
};
// Trial with a batch mix. use calss.
class BatchTrial : public Trial {
protected:
Alice *alice; // What does alice do?
Background *background; // What do the other senders do?
BatchMix *mixnet; // How does the mix behave?
FwdAttacker *attacker; // How does the attacker analyze the network?
std::vector<int> truth; // What does the attacker guess to win?
int nRecips; // How many recipients are there in total?
int nBatch; // How large is the batch?
int granularity; // How often to we check whether the attacker has won?
BatchTrial() : alice(0), background(0), mixnet(0), attacker(0) {}
public:
TrialResult attempt();
virtual ~BatchTrial();
};
// ========================================
// Simple statistical disclosure attack
// Batch mix, alice sends 1 message per batch
// Background distribution is known
// Alice has fixed list of recipients, chooses with equal probability.
class SDTrial : public BatchTrial {
public:
SDTrial(int nRecipients, int nAliceRecipients, int batchSize,
int granularity=5);
~SDTrial();
};
// ========================================
// Generalized statistical diclosure attack against a batch mix.
// Batch mix, alice either:
// - sends 1 or 0 messages per batch.
// - follows smallworld distribution.
// Background distribution is unknown smallworld instance.
class UnkBGBatchTrial : public BatchTrial {
public:
UnkBGBatchTrial(int nRecipients, int nAliceRecipients,
int batchSize, bool aliceIsSmallworld,
bool expMsgDist, // if true, alice sends N msgs on exp. dist
double pMsgAlice, double pDummyAlice,
int paddingLevel=0, // if true, and if alice sends dummies in a round, she sends fillDummies messages total.
int granularity=5);
~UnkBGBatchTrial();
};
// Shared code for case when background decides how many messages to send
// per round.
class NonbatchTrial : public Trial {
private:
NonbatchTrial();
protected:
Alice *alice;
Background *background;
Mixnet *mixnet;
FwdAttacker *attacker;
std::vector<int> truth;
int nRecips;
int granularity;
NonbatchTrial(int nR, int g) : alice(0), background(0), mixnet(0),
attacker(0), truth(nR), nRecips(nR), granularity(g) {}
public:
TrialResult attempt();
~NonbatchTrial();
};
// Trial with a single mix or a whole mixnet.
class MixTrial : public NonbatchTrial {
public:
MixTrial(int nRecipients, int nAliceRecipients,
int pathLen, // 1 if using a single mix.
double pDelay, // probability of being delayed in a randomly chosen round.
bool expAlice, // alice uses exponential distribution.
double pMessage, // probability of Alice sending a single message.
double pDummy, // probability of Alice sending a dummy message
double bgVolMean, // \ Taken together, these two decide how many
double bgVolDev, // / messages the background sends in a round.
int padding=0,
int granularity=5
);
TrialResult attempt();
~MixTrial() {}
};
#endif
Index: .cvsignore
===================================================================
RCS file: /home/freehaven/cvsroot/doc/e2e-traffic/src/.cvsignore,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -d -r1.1 -r1.2
--- .cvsignore 9 Aug 2003 02:35:12 -0000 1.1
+++ .cvsignore 23 Aug 2003 19:04:29 -0000 1.2
@@ -1,5 +1,5 @@
sim
+.gdb_history
test
gmon.out
boost*
-
Index: Makefile
===================================================================
RCS file: /home/freehaven/cvsroot/doc/e2e-traffic/src/Makefile,v
retrieving revision 1.2
retrieving revision 1.3
diff -u -d -r1.2 -r1.3
--- Makefile 21 Aug 2003 21:05:57 -0000 1.2
+++ Makefile 23 Aug 2003 19:04:29 -0000 1.3
@@ -5,7 +5,7 @@
./test
CXX=g++
-CFLAGS=-Wall -O2 -DFAST_RANDOM
+CFLAGS=-Wall -g -O2 -DFAST_RANDOM
clean:
rm -f *.o *~ sim test
@@ -20,26 +20,20 @@
exit 1; \
fi
-rng.o: rng.cpp BOOST
- $(CXX) $(CFLAGS) -I boost -c rng.cpp
-
-sim.o: sim.cpp vec.h comb.h sim.h
- $(CXX) $(CFLAGS) -c sim.cpp
-
-vec.o: vec.cpp vec.h
- $(CXX) $(CFLAGS) -c vec.cpp
-
-test.o: test.cpp vec.h comb.h
- $(CXX) $(CFLAGS) -c test.cpp
-
-simmain.o: simmain.cpp vec.h comb.h
- $(CXX) $(CFLAGS) -c simmain.cpp
-
-netparams.o: netparams.cpp rng.h netparams.h
- $(CXX) $(CFLAGS) -c netparams.cpp
+.cpp.o:
+ $(CXX) $(CFLAGS) -I boost -c $<
-sim: sim.o vec.o rng.o simmain.o netparams.o
- $(CXX) $(CFLAGS) -o sim sim.o vec.o rng.o simmain.o netparams.o
+sim: sim.o vec.o rng.o simmain.o netparams.o trials.o
+ $(CXX) $(CFLAGS) -o sim sim.o vec.o rng.o simmain.o netparams.o trials.o
test: test.o vec.o sim.o rng.o
$(CXX) $(CFLAGS) -o test test.o vec.o sim.o rng.o
+
+# Generated by g++ -MM, with boost stuff removed.
+netparams.o: netparams.cpp rng.h comb.h netparams.h
+rng.o: rng.cpp rng.h comb.h
+sim.o: sim.cpp sim.h vec.h rng.h comb.h
+simmain.o: simmain.cpp sim.h vec.h rng.h comb.h trials.h
+test.o: test.cpp vec.h comb.h rng.h netparams.h
+trials.o: trials.cpp trials.h sim.h vec.h rng.h comb.h netparams.h
+vec.o: vec.cpp vec.h
Index: rng.cpp
===================================================================
RCS file: /home/freehaven/cvsroot/doc/e2e-traffic/src/rng.cpp,v
retrieving revision 1.2
retrieving revision 1.3
diff -u -d -r1.2 -r1.3
--- rng.cpp 21 Aug 2003 21:05:57 -0000 1.2
+++ rng.cpp 23 Aug 2003 19:04:29 -0000 1.3
@@ -2,7 +2,7 @@
#include <stdlib.h>
#include "rng.h"
-#include "boost/random.hpp"
+#include <boost/random.hpp>
//
// If we're prototyping, use a lagged finonacci generator: it's fastest.
@@ -10,7 +10,7 @@
#ifdef FAST_RANDOM
#define RNGCLASS boost::lagged_fibonacci19937
#else
-#define RNGCLASS boost:mt19937
+#define RNGCLASS boost::mt19937
#endif
class RNGState {
@@ -37,7 +37,7 @@
}
CumulativeDist
-CumulativeDist::fromDist(Dist<int> &d, int max)
+CumulativeDist::fromDist(InvDist<int> &d, int max)
{
std::vector<double> probabilities(max);
double total = 0.0;
@@ -82,4 +82,3 @@
std::lower_bound(cumDist.begin(), cumDist.end(), rng());
return it - cumDist.begin();
}
-
Index: rng.h
===================================================================
RCS file: /home/freehaven/cvsroot/doc/e2e-traffic/src/rng.h,v
retrieving revision 1.2
retrieving revision 1.3
diff -u -d -r1.2 -r1.3
--- rng.h 21 Aug 2003 21:05:57 -0000 1.2
+++ rng.h 23 Aug 2003 19:04:29 -0000 1.3
@@ -8,34 +8,45 @@
double rng();
double normal_rng();
+inline int rng(int m) { return static_cast<int>(rng()*m); }
template <class C>
class Dist
{
public:
virtual C get() const = 0;
- virtual double getP(const C &v) const = 0;
+ virtual Dist<C> *copy() const = 0;
virtual ~Dist() {}
};
+// 'invertible' discrete distribution.
template <class C>
-class ConstDist : public Dist<C>
+class InvDist : public Dist<C>
+{
+ public:
+ virtual double getP(const C &v) const = 0;
+};
+
+template <class C>
+class ConstDist : public InvDist<C>
{
private:
C val;
public:
ConstDist(const C &vv) : val(vv) {}
+ Dist<C> *copy() const { return new ConstDist<C>(val); }
C get() const { return val; }
double getP(const C &v) const { return v == val ? 1.0 : 0.0; }
~ConstDist() {}
};
-class ExponentialDist : public Dist<int>
+class ExponentialDist : public InvDist<int>
{
private:
double p;
public:
ExponentialDist(double param) : p(param) {}
+ Dist<int> *copy() const { return new ExponentialDist(p); }
int get() const { int v = 0; while (rng() > p) ++v; return v; }
double getP(const int &val) const {
return p * std::pow(1-p, (int)val);
@@ -43,13 +54,14 @@
~ExponentialDist() {}
};
-class GeometricDist : public Dist<int>
+class GeometricDist : public InvDist<int>
{
private:
double p;
int n;
public:
GeometricDist(double prob, int maximum) : p(prob), n(maximum) {}
+ Dist<int> *copy() const { return new GeometricDist(p, n); }
int get() const {
int v = 0;
for (int i = 0; i < n; ++i) {
@@ -57,21 +69,22 @@
}
return v;
}
- double getP(int &v) const {
+ double getP(const int &v) const {
return comb(n, v)*std::pow(p,v)*std::pow(1-p,n-v);
}
~GeometricDist() {}
};
-class CumulativeDist : public Dist<int>
+class CumulativeDist : public InvDist<int>
{
private:
std::vector<double> prob;
std::vector<double> cumDist;
public:
- static CumulativeDist fromDist(Dist<int> &d, int max);
+ static CumulativeDist fromDist(InvDist<int> &d, int max);
CumulativeDist(const std::vector<double> &dist, bool isCumulative=0);
- CumulativeDist(const CumulativeDist &d) : cumDist(d.cumDist) {}
+ CumulativeDist(const CumulativeDist &d) : prob(d.prob), cumDist(d.cumDist) {}
+ Dist<int> *copy() const { return new CumulativeDist(*this); }
CumulativeDist & operator=(const CumulativeDist &d)
{ prob=d.prob; cumDist = d.cumDist; return *this; }
int get() const;
@@ -80,8 +93,54 @@
~CumulativeDist() {}
};
+template<class C>
+class UniformChoiceDist : public InvDist<C>
+{
+ std::vector<C> choices;
+ public:
+ UniformChoiceDist(const std::vector<C> &c) : choices(c) {}
+ Dist<C> *copy() const { return new UniformChoiceDist<C>(choices); }
+ C get() const { return choices[rng(choices.size())]; }
+ double getP(const C &v) const {
+ int n = choices.size();
+ for (int i = 0; i < n; ++i) { if (choices[i] == v) return 1.0/n; }
+ return 0.0; }
+ ~UniformChoiceDist() {}
+};
-inline int rng(int m) { return static_cast<int>(rng()*m); }
+template<class C>
+class BinaryDist : public InvDist<C>
+{
+ C c1, c2;
+ double p;
+ public:
+ BinaryDist(double prob, const C &choice1, const C &choice2)
+ : c1(choice1), c2(choice2), p(prob) {
+ assert(0.0 <= p && p <= 1.0);
+ }
+ 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;
+ else if (v == c2) return 1-p;
+ else return 0;
+ }
+ ~BinaryDist() {}
+};
+
+class IntNormalDist : public Dist<int>
+{
+ double m, s;
+ bool clamp;
+ public:
+ 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 {
+ int i = static_cast<int>(m+normal_rng()*s+0.5);
+ return (!clamp || i>0)?i:0;
+ }
+};
template<class C>
const C &rng_pick(const std::vector<C> &v) { return v[rng(v.size())]; }
Index: sim.cpp
===================================================================
RCS file: /home/freehaven/cvsroot/doc/e2e-traffic/src/sim.cpp,v
retrieving revision 1.2
retrieving revision 1.3
diff -u -d -r1.2 -r1.3
--- sim.cpp 21 Aug 2003 21:05:57 -0000 1.2
+++ sim.cpp 23 Aug 2003 19:04:29 -0000 1.3
@@ -1,4 +1,5 @@
+#include <iostream>
#include "sim.h"
#include "rng.h"
@@ -7,21 +8,28 @@
// ======================================================================
-UniformAlice::UniformAlice(const std::vector<int> &r,
- Dist<int> *mD, Dist<int> *dD)
- : recipients(r), msgDist(mD), dummyDist(dD)
+void
+DistAlice::getTraffic(vec<int> &v_out, int &n_out)
{
+ int nM;
+ n_out = nM = nMessageDist->get();
+ for (int i = 0; i < n_out; ++i) {
+ ++ v_out[recipientDist->get()];
+ }
+ if (nDummyDist) {
+ int nD = nDummyDist->get();
+ if ((nD||nM) && padding) {
+ if (padding>nM)
+ n_out = padding;
+ } else
+ n_out += nD;
+ }
}
-void
-UniformAlice::getTraffic(vec<int> &v_out, int &nOut)
+UniformAlice::UniformAlice(const std::vector<int> &r,
+ Dist<int> *mD, Dist<int> *dD, int p)
+ : DistAlice(new UniformChoiceDist<int>(r), mD, dD, p)
{
- nOut = msgDist->get();
- for (int i = 0; i < nOut; ++i) {
- ++ v_out[rng_pick(recipients)];
- }
- if (dummyDist)
- nOut += dummyDist->get();
}
UniformBackground::UniformBackground(int nR, int nPR)
@@ -39,10 +47,11 @@
}
void
-UniformBackground::getTraffic(vec<int> &v_out)
+UniformBackground::getTraffic(vec<int> &v_out, int &nOut)
{
assert(nPerRound >= 0);
getNTraffic(v_out, nPerRound);
+ nOut = nPerRound;
}
BatchMix::BatchMix(int b)
@@ -62,9 +71,7 @@
{
assert(alice.size() == background.size());
int nOther = background.total(0);
- vec<int> total(alice);
- total += background;
- a->addRound(nAlice, nOther, total);
+ a->addRound(nAlice, nOther, alice+background);
}
SDAttacker::SDAttacker(vec<double> &bg)
@@ -92,9 +99,11 @@
}
}
-void
+bool
SDAttacker::guessAlice(vec<double> &r)
{
+ if (!nAlice) return false;
+
r = vec<double>(observed);
//cerr << "1." << r << endl;
//cerr << "1b." << background << endl;
@@ -103,67 +112,7 @@
//cerr << "2." << r << endl;
r /= nAlice;
//cerr << "3." << r << endl;
-}
-
-SDTrial::SDTrial(int nR, int nAR, int b, int g)
-{
- aMsgs = new ConstDist<int>(1);
- aDummies = new ConstDist<int>(0);
-
- truth = std::vector<int>(nAR, 0);
- for (int i=0; i<nAR; ++i) { truth[i] = i; }
-
- alice = new UniformAlice(truth, aMsgs, aDummies);
- background = new UniformBackground(nR);
- vec<double> uniform(nR, 1.0/b);
- attacker = new SDAttacker(uniform);
- mixnet = new BatchMix(b);
- nRecips = nR;
- nBatch = b;
- granularity = g;
-}
-
-SDTrial::~SDTrial()
-{
- delete mixnet;
- delete attacker;
- delete background;
- delete alice;
- delete aMsgs;
- delete aDummies;
-}
-
-int
-SDTrial::attempt()
-{
- mixnet->reset();
- attacker->reset();
-
- vec<int> aTraffic(nRecips, 0);
- vec<int> bTraffic(nRecips, 0);
- vec<double> recips(nRecips, 0.0);
-
- int n = 0;
- while (1) {
- aTraffic.reset(0);
- bTraffic.reset(0);
- int nAlice;
- alice->getTraffic(aTraffic, nAlice);
- background->getNTraffic(bTraffic, nBatch - aTraffic.total(0));
- //cout << n << " "<<bTraffic << endl;
- mixnet->addRound(aTraffic, nAlice, bTraffic, attacker);
- if (!(n % granularity)) {
- attacker->guessAlice(recips);
- // cout << n << " " << recips << endl;
- //cout << n << " ------ " << endl;
- //pvec(cout, truth);
- //pvec(cout, recips.topN(truth.size()));
- //cout << n << " ------ " << endl;
- if (truth == recips.topN(truth.size()))
- return n;
- }
- ++n;
- }
+ return true;
}
// ======================================================================
@@ -173,14 +122,15 @@
DistBackground::getNTraffic(vec<int> &v_out, int nMessages)
{
while (nMessages-- > 0) {
- ++ v_out[ dist.get() ];
+ ++ v_out[ recipientDist->get() ];
}
}
void
-DistBackground::getTraffic(vec<int> &v_out)
+DistBackground::getTraffic(vec<int> &v_out, int &nOut)
{
- getNTraffic(v_out, nMessages->get());
+ nOut = nMessages->get();
+ getNTraffic(v_out, nOut);
}
UnkBGBatchAttacker::UnkBGBatchAttacker(int nR)
@@ -210,21 +160,24 @@
}
}
-void
+bool
UnkBGBatchAttacker::guessAlice(vec<double> &r)
{
+ if (!nBg || !nAlice)
+ return false;
vec<double> u(uObservations);
u *= (nOther / nBg);
r = vec<double>(vObservations);
r -= u;
r /= nAlice;
+ return true;
}
// ======================================================================
DelayMix::DelayMix(int nR, int mD,
Dist<int> *d)
- : maxDelay(mD), poolIdx(0), pools(mD), delayDist(d)
+ : maxDelay(mD), poolIdx(0), pools(mD), delayDist(d->copy())
{
for (int i = 0; i < mD; ++i) {
pools[i] = new vec<int>(nR, 0);
@@ -245,6 +198,7 @@
for (int i = 0; i < maxDelay; ++i) {
delete pools[i];
}
+ delete delayDist;
}
void
@@ -254,12 +208,11 @@
FwdAttacker *a)
{
int nOther = background.total(0);
- vec<int> total(alice);
- total += background;
int sz = alice.size();
for (int i = 0; i < sz; ++i) {
- for (int j = 0; j < total[i]; ++j) {
- ++ pools[(poolIdx+getDelay())%maxDelay];
+ int totalForRecip = alice[i]+background[i];
+ for (int j = 0; j < totalForRecip; ++j) {
+ ++( (*pools[(poolIdx+getDelay())%maxDelay]) [i]);
}
}
a->addRound(nAlice, nOther, *pools[poolIdx]);
@@ -269,13 +222,14 @@
poolIdx = 0;
}
-DelayMixAttacker::DelayMixAttacker(int nR, int mD, Dist<int> *dDist)
+DelayMixAttacker::DelayMixAttacker(int nR, int mD, InvDist<int> *dDist)
: nRecips(nR), maxDelay(mD), nAliceIdx(0), nAliceHist(mD, 0),
nOtherHist(mD, 0),
background(nR, 0.0),
observed(nR, 0.0),
nObservedOther(0.0), nObservedAlice(0.0),
- delayDist(dDist)
+ delayDist(dynamic_cast<InvDist<int>*>(dDist->copy())),
+ nRoundsObserved(0), nRoundsMaybeAlice(0)
{
}
@@ -308,9 +262,11 @@
background.reset(0.0);
observed.reset(0.0);
nObservedOther = nObservedAlice = 0.0;
+ nRoundsObserved = nRoundsMaybeAlice = 0;
}
-#define BG_THRESHOLD 0.05
+//XXXX make this configurable. Low values really seem to hurt.
+#define BG_THRESHOLD 0.8
void
DelayMixAttacker::addRound(int nAlice, int nOther,
const vec<int> &r)
@@ -320,10 +276,12 @@
double exAlice = expectedAliceMsgs();
double exOther = expectedOtherMsgs();
+ ++nRoundsObserved;
if (exAlice < BG_THRESHOLD) {
for (int i = 0; i < nRecips; ++i)
background[i] += r[i]*exOther;
} else {
+ ++nRoundsMaybeAlice;
for (int i = 0; i < nRecips; ++i)
observed[i] += r[i]*exAlice;
nObservedOther += exOther;
@@ -335,12 +293,16 @@
nAliceIdx = 0;
}
-void
+bool
DelayMixAttacker::guessAlice(vec<double> &res)
{
+ double uTotal = background.total(0.0);
+ if (!uTotal || !nObservedAlice)
+ return false;
vec<double> u(background);
- u *= (nObservedOther / u.total(0.0));
+ u *= (nObservedOther / uTotal);
res = observed - u;
res -= u;
res /= nObservedAlice;
+ return true;
}
Index: sim.h
===================================================================
RCS file: /home/freehaven/cvsroot/doc/e2e-traffic/src/sim.h,v
retrieving revision 1.2
retrieving revision 1.3
diff -u -d -r1.2 -r1.3
--- sim.h 21 Aug 2003 21:05:57 -0000 1.2
+++ sim.h 23 Aug 2003 19:04:29 -0000 1.3
@@ -16,7 +16,7 @@
public:
Background() {}
virtual void getNTraffic(vec<int> &v_out, int nMessages) = 0;
- virtual void getTraffic(vec<int> &v_out) = 0;
+ virtual void getTraffic(vec<int> &v_out, int &nOut) = 0;
virtual ~Background();
};
@@ -27,7 +27,7 @@
virtual void reset() = 0;
virtual void addRound(int nSentAlice, int nSentOther,
const vec<int> &nReceived) = 0;
- virtual void guessAlice(vec<double> &recipients) = 0;
+ virtual bool guessAlice(vec<double> &recipients) = 0;
virtual ~FwdAttacker() {}
};
@@ -43,26 +43,34 @@
virtual ~Mixnet() {}
};
-class Trial {
-public:
- Trial() {}
- virtual int attempt() = 0;
- virtual ~Trial() {}
-};
// ======================================================================
// Original statistical disclosure attack
-class UniformAlice : public Alice {
-private:
- std::vector<int> recipients;
- Dist<int> *msgDist;
- Dist<int> *dummyDist;
+class DistAlice : public Alice {
+ protected:
+ Dist<int> *nMessageDist;
+ Dist<int> *nDummyDist;
+ Dist<int> *recipientDist;
+ // if padding is >0, and we send any dummies, we instead send >=padding
+ // messages total including dummies.
+ int padding;
+ DistAlice() : nMessageDist(0), nDummyDist(0), recipientDist(0), padding(0) {}
+ public:
+ DistAlice(Dist<int> *recips, Dist<int> *msgs, Dist<int> *dummies,
+ int p=0)
+ : nMessageDist(msgs->copy()), nDummyDist(dummies->copy()),
+ recipientDist(recips->copy()), padding(p) {}
+ void getTraffic(vec<int> &v_out, int &nOut);
+ ~DistAlice() { delete nMessageDist; delete nDummyDist; delete recipientDist;}
+};
+
+
+class UniformAlice : public DistAlice {
public:
UniformAlice(const std::vector<int> &r,
- Dist<int> *msgDist, Dist<int> *dummyDist);
- void getTraffic(vec<int> &v_out, int &nOut);
- ~UniformAlice() {}
+ Dist<int> *msgDist, Dist<int> *dummyDist, int padding=0);
+ ~UniformAlice() { }
};
class UniformBackground : public Background {
@@ -72,7 +80,7 @@
public:
UniformBackground(int nR, int nPR=-1);
void getNTraffic(vec<int> &v_out, int nMessages);
- void getTraffic(vec<int> &v_out);
+ void getTraffic(vec<int> &v_out, int &nOut);
~UniformBackground() {}
};
@@ -101,44 +109,23 @@
void reset();
void addRound(int nSentAlice, int nSentOther,
const vec<int> &nReceived);
- void guessAlice(vec<double> &recipients);
+ bool guessAlice(vec<double> &recipients);
~SDAttacker() {}
};
-
-// Simple statistical disclosure attack.
-class SDTrial : public Trial {
-protected:
- Dist<int> *aMsgs;
- Dist<int> *aDummies;
- Alice *alice;
- Background *background;
- BatchMix *mixnet;
- FwdAttacker *attacker;
- std::vector<int> truth;
- int nRecips;
- int nBatch;
- int granularity;
-public:
- SDTrial(int nRecipients, int nAliceRecipients, int batchSize,
- int granularity=5);
- int attempt();
- ~SDTrial();
-};
-
// ======================================================================
-// Attack with unknown background
+// Attack with unknown background, unknown sender behavior.
class DistBackground : public Background {
private:
- CumulativeDist dist;
+ Dist<int> *recipientDist;
Dist<int> *nMessages;
public:
- DistBackground(const CumulativeDist &d, Dist<int> *nMsgs)
- : dist(d), nMessages(nMsgs) {}
+ DistBackground(const Dist<int>&d, const Dist<int> &nMsgs)
+ : recipientDist(d.copy()), nMessages(nMsgs.copy()) {}
void getNTraffic(vec<int> &v_out, int nMessages);
- void getTraffic(vec<int> &v_out);
- ~DistBackground() {}
+ void getTraffic(vec<int> &v_out, int &nOut);
+ ~DistBackground() { delete recipientDist; delete nMessages; }
};
class UnkBGBatchAttacker : public FwdAttacker {
@@ -152,7 +139,7 @@
UnkBGBatchAttacker(int nRecips);
void reset();
void addRound(int nSentAlice, int nSentOther, const vec<int> &nReceived);
- void guessAlice(vec<double> &nRecipients);
+ bool guessAlice(vec<double> &nRecipients);
~UnkBGBatchAttacker() {}
};
@@ -195,7 +182,11 @@
double nObservedOther;
double nObservedAlice;
- Dist<int> *delayDist;
+ InvDist<int> *delayDist;
+
+ // for TrialResult
+ int nRoundsObserved;
+ int nRoundsMaybeAlice;
int aHist(int rds) { return rds>maxDelay ? 0 :
nAliceHist[(maxDelay+nAliceIdx-rds)%maxDelay]; }
@@ -206,11 +197,16 @@
double expectedOtherMsgs();
public:
- DelayMixAttacker(int nRecips, int maxDelay, Dist<int> *delayDist);
+ DelayMixAttacker(int nRecips, int maxDelay, InvDist<int> *delayDist);
void reset();
void addRound(int nSentAlice, int nSentOther, const vec<int> &nReceived);
- void guessAlice(vec<double> &nRecipients);
- ~DelayMixAttacker() {}
+ bool guessAlice(vec<double> &nRecipients);
+ void getRoundCounts(int &nObs, int &nAlice) {
+ nObs = nRoundsObserved; nAlice = nRoundsMaybeAlice; }
+ ~DelayMixAttacker() { delete delayDist; }
};
+
+
+
#endif /* _SIM_H */
Index: simmain.cpp
===================================================================
RCS file: /home/freehaven/cvsroot/doc/e2e-traffic/src/simmain.cpp,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -d -r1.1 -r1.2
--- simmain.cpp 9 Aug 2003 02:35:13 -0000 1.1
+++ simmain.cpp 23 Aug 2003 19:04:29 -0000 1.2
@@ -1,30 +1,22 @@
-#include "sim.h"
-#include "vec.h"
#include <vector>
#include <algorithm>
#include <iostream>
+#include "sim.h"
+#include "vec.h"
+#include "trials.h"
using std::cout;
using std::ostream;
using std::endl;
-template<class C>
-void pvec(ostream &o, const std::vector<C> &v)
-{
- o << "{";
- for (typename std::vector<C>::const_iterator i = v.begin(); i != v.end(); ++i) {
- o << *i << " ";
- }
- o << "}" << endl;
-}
class XTrial : public Trial {
public:
- int attempt()
+ TrialResult attempt()
{
- SDTrial x(100, 10, 1000);
- return x.attempt();
+ UnkBGBatchTrial trial(100, 5, 30, true, true, 0.7, 0, 0, 10);
+ return trial.attempt();
}
};
@@ -36,29 +28,33 @@
void
getPercentile(Trial &test, int nTrials, percentiles &p)
{
- std::vector<int> results(nTrials);
+ std::vector<TrialResult> results(nTrials);
+ std::vector<int> rounds(nTrials);
for (int i = 0; i < nTrials; ++i) {
results[i] = test.attempt();
+ rounds[i] = results[i].nRounds;
cout << results[i] << endl;
}
- std::sort(results.begin(), results.end());
+ std::sort(rounds.begin(), rounds.end());
- p.min = results[0];
- p.p25 = results[(int)(nTrials *.25)];
- p.p50 = results[(int)(nTrials *.50)];
- p.p75 = results[(int)(nTrials *.75)];
- p.p90 = results[(int)(nTrials *.90)];
- p.p95 = results[(int)(nTrials *.95)];
- p.max = results[nTrials-1];
+ p.min = rounds[0];
+ p.p25 = rounds[(int)(nTrials *.25)];
+ p.p50 = rounds[(int)(nTrials *.50)];
+ p.p75 = rounds[(int)(nTrials *.75)];
+ p.p90 = rounds[(int)(nTrials *.90)];
+ p.p95 = rounds[(int)(nTrials *.95)];
+ p.max = rounds[nTrials-1];
}
int
main(int c, char **v)
{
- SDTrial trial(10000, 10, 3000);
+ // SDTrial trial(10000, 10, 3000);
// XTrial trial;
+ // UnkBGBatchTrial trial(100, 5, 30, false, 0.5, 0.0, 10);
+ MixTrial trial(100, 5, 3, 0.5, true, 0.6, 0.2, 30, 3, 0, 5);
percentiles p;
getPercentile(trial, 5, p);
cout << "======"
***********************************************************************
To unsubscribe, send an e-mail to majordomo@seul.org with
unsubscribe freehaven-cvs in the body. http://freehaven.net/