[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
[freehaven-cvs] Figure out why stuff was so balky. Make the attack ...
Update of /home/freehaven/cvsroot/doc/e2e-traffic/src
In directory moria.mit.edu:/tmp/cvs-serv26484
Modified Files:
netparams.cpp rng.cpp sim.cpp simmain.cpp trials.cpp vec.cpp
vec.h
Log Message:
Figure out why stuff was so balky. Make the attack even scarier, by having
it work.
The changes are:
- Generating small-world networks of the requested sizes, not counting
non-connected nodes against the network size.
- Do single-mix delays correctly.
- Calculate maximum round delays more thoroughly.
- Scale rounds correctly when calculating likely recipients.
Also, kill some needless whitespace and move some functions around.
Index: netparams.cpp
===================================================================
RCS file: /home/freehaven/cvsroot/doc/e2e-traffic/src/netparams.cpp,v
retrieving revision 1.4
retrieving revision 1.5
diff -u -d -r1.4 -r1.5
--- netparams.cpp 2 Dec 2003 20:15:46 -0000 1.4
+++ netparams.cpp 11 Dec 2003 05:03:57 -0000 1.5
@@ -1,13 +1,26 @@
+#include <iostream.h>
#include <vector>
#include "assert.h"
#include "rng.h"
#include "netparams.h"
+#include "vec.h"
InvDist<int> *
getSingleMixDelays(double pDelay) {
assert(0.0 < pDelay && pDelay < 1.0);
- return new GeometricDist(pDelay);
+ InvDist<int> *r = new GeometricDist(1.0-pDelay);
+#ifndef QUIET
+ cout << "Single MIX ";
+ for (int i = 0; i < 1000; ++i) {
+ cout << r->get() << " ";
+ }
+ cout << endl;
+ for (int i = 0; i < 25; ++i) {
+ cout << "P(" << i << ")=" << r->getP(i) << endl;
+ }
+#endif
+ return r;
}
InvDist<int> *
@@ -22,19 +35,30 @@
if (!pathProb)
continue;
for (int d = 0; d < maxDelay; ++d) {
- p[pathLen+d] += pathProb * bins(d, pathLen) *
+ p[pathLen+d] += pathProb * bins(d, pathLen) *
std::pow(pSingleDelay, d) * std::pow(1.0-pSingleDelay, pathLen);
}
}
- return new CumulativeDist(p);
+ InvDist<int> *r = new CumulativeDist(p);
+#ifndef QUIET
+ cout << "MIXNET ";
+ for (int i = 0; i < 1000; ++i) {
+ cout << r->get() << " ";
+ }
+ cout << endl;
+ for (int i = 0; i < 25; ++i) {
+ cout << "P(" << i << ")=" << r->getP(i) << endl;
+ }
+#endif
+ return r;
}
-void
+void
getCommunicationLinks(Dist<int> *&aliceRecipDist,
Dist<int> *&backgroundTraffic,
std::vector<int> *&aliceRecipients,
int nAliceRecipients,
- int nRecipients,
+ int nRecipients,
bool weightAlice)
{
assert(nAliceRecipients < nRecipients);
@@ -50,16 +74,24 @@
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;
+ 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]++;
+ }
}
}
+ total += conns[i];
}
-
+
+#ifndef QUIET
+ cout << " CONNECTIONS " << endl;
+ pvec(cout, conns);
+#endif
+
// XXX Make a constructor decide to use CumulativeDist if granularity
// XXX is too small.
backgroundTraffic = new OCumulativeDist(conns);
Index: rng.cpp
===================================================================
RCS file: /home/freehaven/cvsroot/doc/e2e-traffic/src/rng.cpp,v
retrieving revision 1.4
retrieving revision 1.5
diff -u -d -r1.4 -r1.5
--- rng.cpp 24 Nov 2003 00:33:27 -0000 1.4
+++ rng.cpp 11 Dec 2003 05:03:57 -0000 1.5
@@ -75,7 +75,7 @@
for (int i = 0; i < sz; ++i) {
cumDist[i] /= tot;
}
-
+
for (unsigned int i = 0; i < lookupTable.size(); ++i) {
std::vector<double>::const_iterator it =
std::lower_bound(cumDist.begin(), cumDist.end(), i*granularity);
Index: sim.cpp
===================================================================
RCS file: /home/freehaven/cvsroot/doc/e2e-traffic/src/sim.cpp,v
retrieving revision 1.6
retrieving revision 1.7
diff -u -d -r1.6 -r1.7
--- sim.cpp 2 Dec 2003 20:15:46 -0000 1.6
+++ sim.cpp 11 Dec 2003 05:03:57 -0000 1.7
@@ -6,7 +6,6 @@
Alice::~Alice() {}
Background::~Background() {}
-
// ======================================================================
void
@@ -228,6 +227,7 @@
delayDist(dynamic_cast<InvDist<int>*>(dDist->copy())),
nRoundsObserved(0), nRoundsMaybeAlice(0)
{
+ std::cout << "DMA : maxDelay = " << maxDelay << std::endl;
}
double
@@ -235,6 +235,8 @@
{
double tot = 0.0;
for (int i = 0; i < maxDelay; ++i) {
+ //std::cout << i << "/" << maxDelay << ":" << delayDist->getP(i) << ","
+ // << aHist(i) << std::endl;
tot += delayDist->getP(i)*aHist(i);
}
return tot;
@@ -264,7 +266,7 @@
}
//XXXX make this configurable. Low values really seem to hurt.
-#define BG_THRESHOLD 0.5
+#define BG_THRESHOLD 1.0
void
DelayMixAttacker::addRound(int nAlice, int nOther,
const vec<int> &r)
@@ -284,7 +286,7 @@
} else {
++nRoundsMaybeAlice;
for (int i = 0; i < nRecips; ++i)
- observed[i] += r[i]*exAlice;
+ observed[i] += r[i]*(exAlice/(exOther+exAlice));
nObservedOther += exOther;
nObservedAlice += exAlice;
}
@@ -298,20 +300,29 @@
DelayMixAttacker::guessAlice(vec<double> &res)
{
double uTotal = background.total(0.0);
+ double oTotal = observed.total(0.0);
+#ifndef QUIET
+ std::cout << exOtherInBackground << "++++" << exAliceInBackground
+ << " " << ((double)exAliceInBackground)/exOtherInBackground
+ << "(" << uTotal << ")" <<std::endl;
+ std::cout << nObservedOther << "++++" << nObservedAlice
+ << " " << ((double)nObservedAlice)/nObservedOther
+ << "(" << observed.total(0.0) << ")" << std::endl;
+ std::cout << observed << std::endl;
+ std::cout << background << std::endl;
+ std::cout << res << std::endl;
+#endif
if (!uTotal || !nObservedAlice)
return false;
vec<double> u(background);
// XXX why does this work better?
- u *= 1.8*(nObservedOther / exOtherInBackground);
+ //u *= (oTotal / uTotal);
+ u *= (oTotal / exOtherInBackground);
res = observed - u;
+ res /= nObservedAlice;
#ifndef QUIET
- std::cout << exOtherInBackground << "++++" << exAliceInBackground << std::endl;
- std::cout << nObservedOther << "++++" << nObservedAlice << std::endl;
- //std::cout << observed << std::endl;
- //std::cout << u << std::endl;
- //std::cout << res << std::endl;
+ std::cout << res << std::endl;
#endif
- res /= nObservedAlice;
return true;
}
Index: simmain.cpp
===================================================================
RCS file: /home/freehaven/cvsroot/doc/e2e-traffic/src/simmain.cpp,v
retrieving revision 1.7
retrieving revision 1.8
diff -u -d -r1.7 -r1.8
--- simmain.cpp 2 Dec 2003 20:15:46 -0000 1.7
+++ simmain.cpp 11 Dec 2003 05:03:57 -0000 1.8
@@ -61,8 +61,8 @@
// 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(100).setNAliceRecipients(5).setPathLen(3).setPDelay(0.5)
- .setExpAlice(0.5).setPMessage(0.6).setPDummy(0.2).setBGVolMean(30)
+ 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);
Index: trials.cpp
===================================================================
RCS file: /home/freehaven/cvsroot/doc/e2e-traffic/src/trials.cpp,v
retrieving revision 1.5
retrieving revision 1.6
diff -u -d -r1.5 -r1.6
--- trials.cpp 2 Dec 2003 20:15:46 -0000 1.5
+++ trials.cpp 11 Dec 2003 05:03:57 -0000 1.6
@@ -6,16 +6,6 @@
#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
{
@@ -307,10 +297,12 @@
return new MixTrial(*this);
}
+#define DELAY_SLOP 0.0001
+
void
MixTrial::init(int nR, int nAR, int pathLen, double pDelay,
bool expAlice, double pMessage, double pDummy,
- double bgVolMean, double bgVolDev,
+ double bgVolMean, double bgVolDev,
double pOnline, int padding,
int g, bool partial, double pObserve, int c)
{
@@ -319,14 +311,31 @@
////
// Set up mixnet and attacker.
InvDist<int> *delayDist;
- int maxDelay = static_cast<int>(std::log(0.001)/std::log(pDelay))*2+1;
- std::cout << "MAXDELAY="<<maxDelay<<std::endl;
+#if 0
+ int maxDelay;
+ if (pDelay < 0.00001)
+ maxDelay = pathLen+1;
+ else
+ maxDelay = static_cast<int>(std::log(0.001)/std::log(pDelay))*2+pathLen;
+#endif
+
if (pathLen == 1) {
delayDist = getSingleMixDelays(pDelay);
- } else {
+ } else {
+ int md;
+ if (pDelay < 0.00001)
+ md = pathLen + 1;
+ else
+ md = (int)( (std::log(DELAY_SLOP) / std::log(pDelay))+1)*pathLen;
delayDist = getMixNetDelays(ConstDist<int>(pathLen), pathLen+1,
- pDelay, maxDelay);
+ pDelay, md);
}
+ double totalPDelay = 0.0;
+ int maxDelay = 0;
+ while (totalPDelay < 1.0-DELAY_SLOP) {
+ totalPDelay += delayDist->getP(maxDelay++);
+ }
+ std::cout << "MAXDELAY="<<maxDelay<<std::endl;
std::cout << "Prob of delay (max-1) is = " << delayDist->getP(maxDelay-1)
<< std::endl;
Index: vec.cpp
===================================================================
RCS file: /home/freehaven/cvsroot/doc/e2e-traffic/src/vec.cpp,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -d -r1.1 -r1.2
--- vec.cpp 9 Aug 2003 02:35:13 -0000 1.1
+++ vec.cpp 11 Dec 2003 05:03:57 -0000 1.2
@@ -8,3 +8,5 @@
template class vec<int>;
template class vec<double>;
+
+
Index: vec.h
===================================================================
RCS file: /home/freehaven/cvsroot/doc/e2e-traffic/src/vec.h,v
retrieving revision 1.3
retrieving revision 1.4
diff -u -d -r1.3 -r1.4
--- vec.h 23 Nov 2003 06:26:23 -0000 1.3
+++ vec.h 11 Dec 2003 05:03:57 -0000 1.4
@@ -1,5 +1,5 @@
-#ifndef _VEC_H
+#ifndef _VEC_H
#define _VEC_H
#include <assert.h>
@@ -20,21 +20,21 @@
Item() {}
Item(const vec<C> &vec, int i) : index(i), v(&vec) {}
const C& getValue() const { return (*v)[index]; }
- bool operator<(const vec<C>::Item &o) const {
- return getValue() < o.getValue();
+ bool operator<(const vec<C>::Item &o) const {
+ return getValue() < o.getValue();
}
- bool operator>(const vec<C>::Item &o) const {
- return getValue() > o.getValue();
+ bool operator>(const vec<C>::Item &o) const {
+ return getValue() > o.getValue();
}
- bool operator==(const vec<C>::Item &o) const {
- return getValue() == o.getValue();
+ bool operator==(const vec<C>::Item &o) const {
+ return getValue() == o.getValue();
}
~Item() {}
};
protected:
std::vector<C> rep;
-
+
public:
explicit vec(int len);
vec(int len, C val) : rep(len, val) {}
@@ -43,7 +43,7 @@
int sz = rep.size();
for (int i = 0; i < sz; ++i) {
rep[i] = static_cast<C>(other[i]);
- }
+ }
}
void reset(const C& v) {
@@ -56,12 +56,12 @@
int size() const {
return rep.size();
}
-
+
vec<C> &operator=(const vec<C>& other) {
rep = other.rep;
return *this;
}
-
+
vec<C> operator+(const vec<C>& other) const {
return (vec<C>(*this) += other);
}
@@ -181,7 +181,7 @@
}
return minidx;
}
-
+
// Returns indices with higest values, in order of indices.
std::vector<int> topN(int n) const
{
@@ -190,16 +190,16 @@
for (int i = 0; i<sz; ++i) {
items[i] = vec<C>::Item(*this, i);
}
-
+
std::partial_sort(items.begin(), items.begin()+n, items.end(),
std::greater<vec<C>::Item>() );
-
+
std::vector<int> r(n);
for (int i = 0; i < n; ++i) {
r[i] = items[i].index;
}
std::sort(r.begin(), r.end());
-
+
return r;
}
@@ -218,14 +218,14 @@
return o;
}
-inline int
+inline int
nVecMatch(const std::vector<int> &a, const std::vector<int> &b)
{
int n = 0;
for (std::vector<int>::const_iterator it = a.begin(); it != a.end(); ++it) {
for (std::vector<int>::const_iterator it2 = b.begin(); it2 != b.end(); ++it2) {
-
+
if (*it2 == *it) {
++n;
break;
@@ -242,12 +242,12 @@
typedef std::vector<int>::const_iterator iter;
iter i1 = a.begin();
iter i2 = b.begin();
- if (i1 == a.end() || i2 == b.end())
+ if (i1 == a.end() || i2 == b.end())
return 0;
while (1) {
if (*i1 == *i2) {
- ++n; ++i1; ++i2;
- if (i1 == a.end() || i2 == b.end())
+ ++n; ++i1; ++i2;
+ if (i1 == a.end() || i2 == b.end())
return n;
} else if (*i1 < *i2) {
++i1;
@@ -257,6 +257,16 @@
if (i2 == b.end()) return n;
}
}
+}
+
+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;
}
#endif /* _VEC_H */
***********************************************************************
To unsubscribe, send an e-mail to majordomo@seul.org with
unsubscribe freehaven-cvs in the body. http://freehaven.net/