On Mon, Jan 28, 2013 at 6:22 PM, Matthew Toseland <t...@amphibian.dyndns.org > wrote:
> On Monday 28 Jan 2013 21:39:54 Michael Grube wrote: > > On Mon, Jan 28, 2013 at 4:14 PM, Matthew Toseland < > t...@amphibian.dyndns.org > > > wrote: > > > > > On Monday 28 Jan 2013 18:09:07 Michael Grube wrote: > > > > On Sun, Jan 27, 2013 at 12:30 PM, Matthew Toseland < > > > > t...@amphibian.dyndns.org> wrote: > > > > > > > > > On Sunday 27 Jan 2013 05:02:17 Michael Grube wrote: > > > > > > Hi everyone, > > > > > > > > > > > > Around this time last year I started on work to simulate the > pitch > > > black > > > > > > attack working against Oskar Sandberg's swapping algorithm that > is > > > > > > implemented for use with darknet. The work is essentially > incomplete, > > > > > but I > > > > > > did enough to get an idea of how well Oskar's proposed solution > to > > > the > > > > > > Black Attack works. Hopefully the information that follows can > > > provide > > > > > some > > > > > > insight for anybody working on this problem. > > > > > > > > > > It looks like we have a good chance of using Oskar's original plan. > > > Maybe > > > > > even getting it published, with some help (carl might help even if > you > > > > > don't have time?). > > > > > > > > > > > > The code is messy, so I'm going to do a walkthrough of how > exactly I > > > ran > > > > > > the simulation. > > > > > > > > > > > > To start off, my code is available at > http://github.com/mgrube/pbsim > > > . > > > > > > > > > > > > Let's start. The first thing I did was create the small world > network > > > > > that > > > > > > is assumed in the darknet. The graph size can obviously be of any > > > size, > > > > > but > > > > > > in our experiment we'll make the network size 1000 nodes. This is > > > pretty > > > > > > simple in python and can be accomplished with one line in the > > > networkx > > > > > > library: > > > > > > > > > > You did check that there isn't a scalability issue? :) > > > > > > > > I tested with 10,000 nodes as well and the results did not vary by > much. > > > > The most important difference I noticed was that 2 attackers became a > > > less > > > > significant number. Not that this really means anything to a would-be > > > > attacker. > > > > > > > > If you are convinced that scalability is a problem, I can add > support for > > > > threads to what I have and make it easy to simulate 100,000 or 1M or > > > > whatever number we want to try. > > > > > > I don't know. In my experience threads complicate matters quite a bit. > > > > > > > Certainly they can. In this case it would help, however. > > > > > > > > > > > > > > I wonder if it would be worth writing up the "natural pitch black > via > > > > > churn evolution" we saw in ~ 2008. Basically, when you have churn, > > > newbies > > > > > end up with the "worst" locations i.e. those furthest away from the > > > main > > > > > clusters. So even without an attack, the network locations become > more > > > and > > > > > more clustered. We fixed it by periodic randomisation, which > seemed to > > > have > > > > > relatively little cost - the nodes quickly got their old locations > > > back, > > > > > more or less. > > > > > > > > > > Another thing we want to look into is what the cost is of swapping > > > > > (especially on a growing network, or even two networks merging) in > > > terms of > > > > > losing datastores due to locations changing. That might need more > > > detailed > > > > > simulations... > > > > > > > > I will see what I can do about looking into these sometime later this > > > week. > > > > > > Good. > > > > > > > > > > We can see the aftermath by looking at a histogram of node > > > locations. The > > > > > > randomize function uses a random function to assign each node a > > > location, > > > > > > so first let's look at a histogram of locations before the > attack: > > > > > > > > > > > > > > > http://127.0.0.1:8888/CHK@ODZ1s5SDYrVvyNo0ONh4O9rtI~pcVmTSShh47UFPY5U,SKJfkX2eswHMrqidDWTUoZKGMaZ9yt0l6uLUZMmxOqk,AAMC--8/preattacklocations.PNG > > > > > > > > > > Suprisingly wide range of concentrations. > > > > > > > > > > > > The biasing locations for these attack nodes were: > > > > > > .6935 > > > > > > .1935 > > > > > > .9435 > > > > > > .4435 > > > > > > .4665 > > > > > > .9665 > > > > > > .7165 > > > > > > .2165 > > > > > > > > > > > > Our histogram of node locations now shows a disproportionate > number > > > of > > > > > > nodes with those locations: > > > > > > > > > > > > > > > > > > > > > http://127.0.0.1:8888/CHK@aI0BN0NXEjU--8dFtCYZwPwUWcM0rpamIf3lnv7FfHc,SCr2NPJYZVpFJKSf-qDYerQTQyDfdoV3-DeX-W1e91I,AAMC--8/postattack.PNG > > > > > > > > > > Scary! > > > > > > > > Quite. > > > > > > > > > > So, the attack with only two nodes is obviously very effective. > It's > > > > > > important to note that the attack simulation method assumed that > > > nodes > > > > > were > > > > > > attacking before the swapping algorithm had a chance to organize > the > > > > > > network. This is something of a worst case scenario. > > > > > > > > > > So this is attacking after we've done some swapping but not enough > to > > > > > reach the point of diminishing returns? > > > > > > > > > > > > Now, let's measure the effectiveness of Oskar Sandberg's proposed > > > > > solution, > > > > > > which is described on the bug tracker: > > > > > > https://bugs.freenetproject.org/view.php?id=3919 > > > > > > > > > > > > We can test sandberg's solution by using: > > > > > > > > > > > > sandbergsolution(sandberg_solution_network, attackers, .037) > > > > > > > > > > > > The last parameter, .037 is the distance threshold for > > > re-randomizing a > > > > > > node's location. To be completely honest I am not sure why, but > .037 > > > > > seemed > > > > > > to work out as a decent experimental distance. This could quite > > > easily > > > > > > change depending on the size of the network and should by no > means be > > > > > used > > > > > > as a default value. > > > > > > > > > > Isn't that rather large on a network of 1000 nodes? I guess it > depends > > > on > > > > > the average node degree? To be clear, you're randomising if the > (mean? > > > > > median?) distance is less than this value? > > > > > > > > No. If our probe does a DFS and cannot find a node further than the > > > > threshold distance, randomization happens. > > > > > > I don't understand. It does a depth first search for what exactly? > > > > > > > >From your notes in the bug tracker: > > > > "Pick a key randomly, route for it with a special query that returns the > > nearest node identifier to the key found. If the closest you can get is > much > > further than your distance to your neighbors, give up your current > position > > for the random one. The definition of "much further" needs to be > determined > > experimentally, but it shouldn't be an issue (since the attack in > question > > works by putting a neighbor thousands of times closer to you then it > should > > be)." > > > So how exactly do you use the 0.037 constant? > > If you don't have a peer with distance greater than 0.037 * (distance from > random location to nearest node to the random location), then you reset? > > (This will break for nodes with very small degree...) > I'm curious about why you think this is true. If the network is a small world graph, even nodes with a small degree should be OK using a probe given that they have more than 1 node that they trust. > > _______________________________________________ > Devl mailing list > Devl@freenetproject.org > https://emu.freenetproject.org/cgi-bin/mailman/listinfo/devl >
_______________________________________________ Devl mailing list Devl@freenetproject.org https://emu.freenetproject.org/cgi-bin/mailman/listinfo/devl
