[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
[freehaven-cvs] Debugging; refactoring; make output-format python-fr...
Update of /home/freehaven/cvsroot/doc/e2e-traffic/src
In directory moria.mit.edu:/tmp/cvs-serv11564
Modified Files:
Makefile PLAN netparams.cpp netparams.h rng.cpp rng.h sim.cpp
simmain.cpp trials.cpp trials.h vec.h
Log Message:
Debugging; refactoring; make output-format python-friendly; write first 2 tests.
Index: Makefile
===================================================================
RCS file: /home/freehaven/cvsroot/doc/e2e-traffic/src/Makefile,v
retrieving revision 1.8
retrieving revision 1.9
diff -u -d -r1.8 -r1.9
--- Makefile 11 Dec 2003 11:07:51 -0000 1.8
+++ Makefile 22 Dec 2003 03:58:20 -0000 1.9
@@ -14,7 +14,7 @@
@if [ ! -d boost ]; then \
echo "========================="; \
echo "Download the latest version of Boost, unpack it, and"; \
- echo "symlink it to ./boost"; echo; \
+ echo "symlink it to ./boost"; \
echo "(Once I know what I use, I'll checkin those parts.)"; \
echo "========================="; \
exit 1; \
Index: PLAN
===================================================================
RCS file: /home/freehaven/cvsroot/doc/e2e-traffic/src/PLAN,v
retrieving revision 1.2
retrieving revision 1.3
diff -u -d -r1.2 -r1.3
--- PLAN 2 Dec 2003 20:15:46 -0000 1.2
+++ PLAN 22 Dec 2003 03:58:20 -0000 1.3
@@ -24,8 +24,8 @@
Additional variables: frequency of alice sending,
connectedness of Alice's recipients. (plus vars from (1))
- 3 Attack with a timed dynamic-pool mix or a mixnet.
- Mix=1mix/mixnet, Alice=SmallWorld, Background=Smallworld
+ 3 Attack a timed dynamic-pool mix
+ Mix=1mix, Alice=SmallWorld, Background=Smallworld
(class: DelayMixTrial)
Additional variables: mix algorithm, mix algorithm
@@ -33,13 +33,17 @@
Additional display: histogram of latency.
- 4 The impact of dummy traffic.
+ 4 Attack a mixnet
+ Mix=mixnet, Alice=SmallWorld, Background=Smallworld
+ (class: DelayMixTrial)
+
+ 5 The impact of dummy traffic.
Mix=mixnet, Alice=SmallWorld+dummies, Background=Smallworld+dummies
Additonal variables: Dummy approach and volume, probability that
Alice forgets to send. (plus vars from (3))
- 5 The impact of partial observation
+ 6 The impact of partial observation
Mix=po_mixnet, Alice=SmallWorld+dummies,
Background=Smallworld+dummies
(class: PO_DelayMixTrial)
@@ -50,7 +54,7 @@
======================================================================
- 6 Nymservice
- 7 Fragmented community
- 8 Suspicious user
+ 7 Nymservice
+ 8 Fragmented community
+ 9 Suspicious user
Index: netparams.cpp
===================================================================
RCS file: /home/freehaven/cvsroot/doc/e2e-traffic/src/netparams.cpp,v
retrieving revision 1.6
retrieving revision 1.7
diff -u -d -r1.6 -r1.7
--- netparams.cpp 11 Dec 2003 11:07:51 -0000 1.6
+++ netparams.cpp 22 Dec 2003 03:58:20 -0000 1.7
@@ -57,12 +57,13 @@
}
void
-getCommunicationLinks(Dist<int> *&aliceRecipDist,
- Dist<int> *&backgroundTraffic,
+getCommunicationLinks(InvDist<int> *&aliceRecipDist,
+ InvDist<int> *&backgroundTraffic,
std::vector<int> *&aliceRecipients,
int nAliceRecipients,
int nRecipients,
- bool weightAlice)
+ bool weightAlice,
+ bool smallworldAlice)
{
assert(nAliceRecipients < nRecipients);
assert(nRecipients >= 3);
@@ -80,7 +81,6 @@
while (conns[i] == 0) { // we want nRecipients connected recpients.
for (int j = 0; j < i; ++j) {
double pAdd = conns[j] / ((double)total);
- cout << "pAdd = "<<pAdd << endl;
if (rng() < pAdd) {
conns[i]++;
conns[j]++;
@@ -103,7 +103,10 @@
for (int i = 0; i < nAliceRecipients; ++i) {
int r;
do {
- r = backgroundTraffic->get();
+ if (smallworldAlice)
+ r = backgroundTraffic->get();
+ else
+ r = (int) (rng()*nRecipients);
} while (pAlice[r]);
if (weightAlice) {
pAlice[r] = conns[r];
Index: netparams.h
===================================================================
RCS file: /home/freehaven/cvsroot/doc/e2e-traffic/src/netparams.h,v
retrieving revision 1.2
retrieving revision 1.3
diff -u -d -r1.2 -r1.3
--- netparams.h 11 Dec 2003 11:07:51 -0000 1.2
+++ netparams.h 22 Dec 2003 03:58:20 -0000 1.3
@@ -45,12 +45,13 @@
// 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,
+void getCommunicationLinks(InvDist<int> *&aliceRecipDist,
+ InvDist<int> *&backgroundTraffic,
std::vector<int> *&aliceRecipients,
int nAliceRecipients,
int nRecipients,
- bool weightAlice=0);
+ bool weightAlice=0,
+ bool smallworldAlice=0);
Index: rng.cpp
===================================================================
RCS file: /home/freehaven/cvsroot/doc/e2e-traffic/src/rng.cpp,v
retrieving revision 1.6
retrieving revision 1.7
diff -u -d -r1.6 -r1.7
--- rng.cpp 11 Dec 2003 11:07:51 -0000 1.6
+++ rng.cpp 22 Dec 2003 03:58:20 -0000 1.7
@@ -1,18 +1,19 @@
// Copyright (c) 2003 Nick Mathewson. See LICENSE for licensing information.
// $Id$
-// rng.cpp -- Basic combinatorics
+// rng.cpp -- Basic prng functionality
#include <stdlib.h>
#include <math.h>
#include "rng.h"
-
#include <boost/random.hpp>
//
// If we're prototyping, use a lagged finonacci generator: it's fastest.
//
#ifdef FAST_RANDOM
+// #include <boost/random/lagged_fibonacci.hpp>
#define RNGCLASS boost::lagged_fibonacci19937
#else
+// #include <boost/random/mersenne_twister.hpp>
#define RNGCLASS boost::mt19937
#endif
@@ -62,6 +63,7 @@
return it - cumDist.begin();
}
+/*
OCumulativeDist::OCumulativeDist(const std::vector<double> &dist,
double granularity)
: prob(dist), lookupTable((int)round(1.0/granularity))
@@ -84,6 +86,7 @@
lookupTable[i] = it - cumDist.begin();
}
}
+*/
OCumulativeDist::OCumulativeDist(const std::vector<int> &dist)
: prob(dist.size())
@@ -98,8 +101,8 @@
int i = 0;
for (iter it = dist.begin(); it < dist.end(); ++it, ++i) {
prob[i] = ((double)(*it))/tot;
- for (int j = 0; j < *it; ++j) {
+ for (int j = 0; j < *it; ++j) {
lookupTable.push_back(i);
}
}
-}
+ }
Index: rng.h
===================================================================
RCS file: /home/freehaven/cvsroot/doc/e2e-traffic/src/rng.h,v
retrieving revision 1.6
retrieving revision 1.7
diff -u -d -r1.6 -r1.7
--- rng.h 11 Dec 2003 11:07:51 -0000 1.6
+++ rng.h 22 Dec 2003 03:58:20 -0000 1.7
@@ -123,7 +123,7 @@
std::vector<int> lookupTable;
public:
OCumulativeDist(const std::vector<int> &dist);
- OCumulativeDist(const std::vector<double> &dist, double granularity);
+ //OCumulativeDist(const std::vector<double> &dist, double granularity);
OCumulativeDist(const OCumulativeDist &d) :
prob(d.prob), lookupTable(d.lookupTable) {}
Dist<int> *copy() const { return new OCumulativeDist(*this); }
Index: sim.cpp
===================================================================
RCS file: /home/freehaven/cvsroot/doc/e2e-traffic/src/sim.cpp,v
retrieving revision 1.8
retrieving revision 1.9
diff -u -d -r1.8 -r1.9
--- sim.cpp 11 Dec 2003 11:07:51 -0000 1.8
+++ sim.cpp 22 Dec 2003 03:58:20 -0000 1.9
@@ -165,6 +165,7 @@
if (!nBg || !nAlice)
return false;
vec<double> u(uObservations);
+ assert(u.total(0.0) == nBg);
u *= (nOther / nBg);
r = vec<double>(vObservations);
r -= u;
@@ -316,8 +317,6 @@
if (!uTotal || !nObservedAlice)
return false;
vec<double> u(background);
- // XXX why does this work better?
- //u *= (oTotal / uTotal);
u *= (oTotal / exOtherInBackground);
res = observed - u;
res /= nObservedAlice;
Index: simmain.cpp
===================================================================
RCS file: /home/freehaven/cvsroot/doc/e2e-traffic/src/simmain.cpp,v
retrieving revision 1.9
retrieving revision 1.10
diff -u -d -r1.9 -r1.10
--- simmain.cpp 11 Dec 2003 11:07:51 -0000 1.9
+++ simmain.cpp 22 Dec 2003 03:58:20 -0000 1.10
@@ -3,6 +3,7 @@
#include <vector>
#include <algorithm>
#include <iostream>
+#include <string>
#include "sim.h"
#include "vec.h"
#include "trials.h"
@@ -11,68 +12,103 @@
using std::ostream;
using std::endl;
+void incBatchSize(int &batchSize)
+{
+ if (batchSize < 25)
+ batchSize += 5;
+ else if (batchSize < 100)
+ batchSize += 25;
+ else if (batchSize < 250)
+ batchSize += 150;
+ else if (batchSize < 1000)
+ batchSize += 250;
+ else
+ batchSize += 2000;
+}
-class XTrial : public Trial {
-public:
- TrialResult attempt()
- {
- UnkBGBatchTrialSpec s;
- s.setNRecipients(100).setNAliceRecipients(5).setBatchSize(30)
- .setAliceIsSmallworld(true).setExpMsgDist(true).setPMsgAlice(0.7)
- .setPDummyAlice(0).setPaddingLevel(0).setGranularity(10);
+void trial1() {
+ // Statistical disclosure attack.
- UnkBGBatchTrial trial(s);
- return trial.attempt();
+ for (int batchSize = 5; batchSize < 5000; incBatchSize(batchSize)) {
+ for (int nRecips = 32; nRecips <= 2000000; nRecips *= 2) {
+ for (int nAR = 1; (nAR <= 1024 && nAR < nRecips); nAR *= 2) {
+ SDTrialSpec s;
+ s.setNRecipients(nRecips);
+ s.setAliceRecipients(nAR);
+ s.setBatchSize(1000);
+ s.setCutoff(1000000);
+ if (nRecips > 2000)
+ s.setGranularity(100);
+ else
+ s.setGranularity(10);
+ for (int i = 1; i <= 100; ++i) {
+ s.write(std::cout);
+ std::cout << "\"" << i << "/" << 100 << "\"" << std::endl;
+ SDTrial trial(s);
+ TrialResult res = trial.attempt();
+ std::cout << res << std::endl << std::endl;
+ }
+ }
+ }
}
-};
-
-struct percentiles {
- int min, p25, p50, p75, p90, p95, max;
-};
-
+}
-void
-getPercentile(Trial &test, int nTrials, percentiles &p)
+void trial2()
{
- 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;
+ // attack with small-worlds network and unknown background.
+ for (int batchSize = 5; batchSize < 5000; incBatchSize(batchSize)) {
+ for (int nRecips = 32; nRecips <= 2000000; nRecips *= 2) {
+ for (int nAR = 1; (nAR <= 1024 && nAR < nRecips); nAR *= 2) {
+ for (int pMA = 6; pMA <= 9; pMA += 3) {
+ for (int AISW=0; AISW <= 1; ++AISW) {
+ UnkBGBatchTrialSpec s;
+ s.setNRecipients(nRecips).setNAliceRecipients(nAR)
+ .setBatchSize(batchSize).setPaddingLevel(0).setCutoff(1000000)
+ .setAliceIsSmallworld(AISW).setExpMsgDist(true)
+ .setPMsgAlice(pMA/10.0)
+ .setPDummyAlice(0.0);
+ if (nRecips > 2000)
+ s.setGranularity(100);
+ else
+ s.setGranularity(10);
+ for (int i = 1; i <= 100; ++i) {
+ s.write(std::cout);
+ std::cout << "\"" << i << "/" << 100 << "\"" << std::endl;
+ UnkBGBatchTrial trial(s);
+ TrialResult res = trial.attempt();
+ std::cout << res << std::endl << std::endl;
+ }
+ }
+ }
+ }
+ }
}
- std::sort(rounds.begin(), rounds.end());
+}
+
+void trial3()
+{
+ // attack against a dynamic-pool mix.
- 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);
- // 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);
- MixTrialSpec s;
- s.setNRecipients(10).setNAliceRecipients(3).setPathLen(3).setPDelay(0.7)
- .setExpAlice(0.5).setPMessage(0.6).setPDummy(0.2).setBGVolMean(50)
- .setBGVolDev(3).setPadding(0).setGranularity(100)
- .setPartial(false).setPObserve(1.0).setCutoff(1000000);
- MixTrial trial(s);
- //MixTrial trial(100, 5, 3, 0.5, true, 0.6, 0.2, 30, 3, 0, 20, true, 0.4);
- percentiles p;
- getPercentile(trial, 2, p);
- cout << "======"
- << p.min << " " << p.p50 << " "
- << p.p90 << " " << p.max << "=====" << endl;
+ if (c < 2) {
+ std::cout << "no args given";
+ return -1;
+ }
+
+ std::string trialname(v[1]);
+
+ if (trialname == "1") {
+ trial1();
+ } else if (trialname == "2") {
+ trial2();
+ } else {
+ std::cout << "unrecognized trial name: " << trialname << std::endl;
+ }
return 0;
}
Index: trials.cpp
===================================================================
RCS file: /home/freehaven/cvsroot/doc/e2e-traffic/src/trials.cpp,v
retrieving revision 1.7
retrieving revision 1.8
diff -u -d -r1.7 -r1.8
--- trials.cpp 11 Dec 2003 11:07:51 -0000 1.7
+++ trials.cpp 22 Dec 2003 03:58:20 -0000 1.8
@@ -6,24 +6,21 @@
#include "trials.h"
#include "netparams.h"
+using namespace std;
void
TrialResult::write(std::ostream &out) const
{
- if (failed) {
- out << "[-";
- } else {
- out << "[+";
- }
- out << "rounds: "<< nRounds<<" (alice in "<< nRoundsAlice
- << ") msgs: "<< nMsgs << " (alice sent "<< nMsgsAlice
- << ", "<< nMsgsAliceReal << " real)";
+ out << "Result(succeeded="<<!failed
+ << ",rounds="<< nRounds<<",roundsWithAlice="<< nRoundsAlice
+ << ",msgs="<< nMsgs << ",msgsFromAlice= "<< nMsgsAlice
+ << ",nMsgsMaybeReal="<< nMsgsAliceReal;
if (nRoundsMaybeAlice) {
- out << ". observed rounds: "<<nRoundsObserved<<" (alice maybe in "
- << nRoundsMaybeAlice << ")";
+ out << ",nObservedRounds="<<nRoundsObserved<<",nObsRoundsMaybeAlice="
+ << nRoundsMaybeAlice;
}
- out << "] ";
- pvec(out, roundsToGuessN);
+ out << "nRoundsToGuessNth=";
+ pvec(out, roundsToGuessN) << ")";
}
std::ostream &
@@ -148,7 +145,7 @@
else
o << "-uniform\"";
o << ",pMessage=" << pMsgAlice << ",pDummy=" << pDummyAlice
- << ")" << std::endl;
+ << ",paddingLevel="<< paddingLevel << ")" << std::endl;
// XXX paddingLevel is wrong, so include it when it's right.
}
@@ -172,27 +169,22 @@
BinaryDist<int> aMsgsB(pMsgA, 1, 0);
BinaryDist<int> aDummiesB(pDA, 1, 0);
- Dist<int> *aliceRecipDist = 0;
- Dist<int> *backgroundTrafficDist = 0;
+ InvDist<int> *aliceRecipDist = 0;
+ InvDist<int> *backgroundTrafficDist = 0;
std::vector<int> *aliceRecipients = 0;
getCommunicationLinks(aliceRecipDist, backgroundTrafficDist,
aliceRecipients,
- nAR, nR);
+ nAR, nR, 0, smallworldAlice);
- if (smallworldAlice) {
- truth = *aliceRecipients;
- if (expMsgDist)
- alice = new DistAlice(aliceRecipDist, &aMsgsE, &aDummiesE, padding, pOnline);
- else
- alice = new DistAlice(aliceRecipDist, &aMsgsB, &aDummiesB, padding, pOnline);
- } 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, pOnline);
- else
- alice = new UniformAlice(truth, &aMsgsB, &aDummiesB, padding, pOnline);
- }
+ truth = *aliceRecipients;
+ if (expMsgDist)
+ alice = new DistAlice(aliceRecipDist, &aMsgsE, &aDummiesE, padding, pOnline);
+ else
+ alice = new DistAlice(aliceRecipDist, &aMsgsB, &aDummiesB, padding, pOnline);
+ cout << "bgAlice={";
+ for (int i = 0; i < nAR; ++i)
+ cout << truth[i] << ":" << backgroundTrafficDist->getP(i) << ",";
+ cout << "}" << endl;
ConstDist<int> oneDist(1); // ignored.
background = new DistBackground(*backgroundTrafficDist, oneDist);
@@ -348,8 +340,8 @@
delete delayDist;
//// Set up small world.
- Dist<int> *aliceRecipDist = 0;
- Dist<int> *backgroundTrafficDist = 0;
+ InvDist<int> *aliceRecipDist = 0;
+ InvDist<int> *backgroundTrafficDist = 0;
std::vector<int> *aliceRecipients = 0;
getCommunicationLinks(aliceRecipDist, backgroundTrafficDist,
aliceRecipients,
@@ -366,6 +358,10 @@
alice = new DistAlice(aliceRecipDist, &aMsgsE, &aDummiesE, padding, pOnline);
else
alice = new DistAlice(aliceRecipDist, &aMsgsB, &aDummiesB, padding, pOnline);
+ cout << "bgAlice={";
+ for (int i = 0; i < nAR; ++i)
+ cout << truth[i] << ":" << backgroundTrafficDist->getP(i) << ",";
+ cout << "}" << endl;
//// set up background.
background = new DistBackground(*backgroundTrafficDist,
Index: trials.h
===================================================================
RCS file: /home/freehaven/cvsroot/doc/e2e-traffic/src/trials.h,v
retrieving revision 1.6
retrieving revision 1.7
diff -u -d -r1.6 -r1.7
--- trials.h 11 Dec 2003 11:07:51 -0000 1.6
+++ trials.h 22 Dec 2003 03:58:20 -0000 1.7
@@ -231,6 +231,7 @@
MixTrialSpec &setGranularity(int n) { granularity = n; return *this; }
MixTrialSpec &setCutoff(int n) { cutoff = n; return *this; }
+ // rename to geometric.
MixTrialSpec &setExpAlice(bool b) { expAlice = b; ea_set = true; return *this; }
MixTrialSpec &setPartial(bool b) { partial = b; p_set = true; return *this; }
@@ -282,6 +283,4 @@
~MixTrial() {}
};
-
-
#endif
Index: vec.h
===================================================================
RCS file: /home/freehaven/cvsroot/doc/e2e-traffic/src/vec.h,v
retrieving revision 1.5
retrieving revision 1.6
diff -u -d -r1.5 -r1.6
--- vec.h 11 Dec 2003 11:07:51 -0000 1.5
+++ vec.h 22 Dec 2003 03:58:20 -0000 1.6
@@ -261,13 +261,14 @@
}
template<class C>
-void pvec(std::ostream &o, const std::vector<C> &v)
+std::ostream& pvec(std::ostream &o, const std::vector<C> &v)
{
- o << "{";
+ o << "[";
for (typename std::vector<C>::const_iterator i = v.begin(); i != v.end(); ++i) {
- o << *i << " ";
+ o << *i << ",";
}
- o << "}" << std::endl;
+ o << "]";
+ return o;
}
#endif /* _VEC_H */
***********************************************************************
To unsubscribe, send an e-mail to majordomo@seul.org with
unsubscribe freehaven-cvs in the body. http://freehaven.net/