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.
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: from pynetsim import * from networkx import * from pylab import * random_network = navigable_small_world_graph(1000, 4, 2, 1, 1).to_undirected() We've just made a Kleinberg small world graph of 1000 nodes with 4 nearest neighbors, 2 randomly chosen long distance connections, an exponent describing the probability of a connection(explicitly defined as 1/d for a Kleinberg graph) and specified one dimension. Now we'll randomize the locations assigned to all of the nodes with the randomize function in pynetsim: randomize(random_network) To compare graphs with the same initial conditions, we're going to copy the graph... clean_swap_network = random_network.copy() attacked_network = random_network.copy() sandberg_solution_network = random_network.copy() Before we go any further, we should verify that the darknet swapping algorithm is implemented properly. In order for the swapping algorithm to be the most effective, it should occur about 2000N times, where N is the number of nodes in the graph. Let's do that: while i < 2000: i += 1 swapiteration(clean_swap_network) Now it's time to stare at your computer while every node runs the swapping algorithm 2000 times. After you've done that, you can examine the link length distribution by using the hist function and the edges of the clean_swap_network: linklengths = list() for e in clean_swap_network.edges(): linklengths.append(abs(e[0][0] - e[1][0])) hist(linklengths, 100) I've taken a snapshot of the histogram that is generated from this: http://127.0.0.1:8888/CHK@YbRCKaxMhIxRgBpYIT2Ux4t-Pi01xxMu2XqWWvG2YY0,SWOn~fUZygCOzHNruIiw7eZEwqFDme9ZGTc4vdtgQFQ,AAMC--8/post_swapping.PNG Ok, so it looks like our swapping algorithm is properly implemented. Let's attack the network! attackers = list() pickmalnodes(attacked_network, attackers, 2) #We're picking 2 malicious nodes because that is the number chosen by the writers of the Pitch Black paper. attacksimulation(attacked_network, attackers) #We're using 2 nodes, each with 4 malicious locations. 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 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 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. 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. Let's look at the node location distribution again and see how well we did against the attack: http://127.0.0.1:8888/CHK@oM7nUV0u6qQwmGMTlqenvJlR0vNDed861BUBf~qSET8,quF5qCdrV-fKV77CKct0V~bi1GuxEjgjAPVTsmdRbPQ,AAMC--8/sandbergsolution.PNG Not bad! There is obviously still some influence but the location distribution has evened out noticeably. There is one down side to this solution, however, and that is that it appears to affect search performance. By how much, I am not sure, but our link length distribution is now looking less ideal: http://127.0.0.1:8888/CHK@TdODwHOdC9peiHYGtTxDa9yy9v0lXSHKWW4G7wM5-~A,OIy08YxNZdg4M3vpgm7wETOhUvU3RYFzrkJQ7No9poE,AAMC--8/deterioratinglinkdist.PNG My conclusion is that I have confidence in the solution Oskar proposed, but that it can be improved upon as well. I'm sure there are a lot of details I did not cover in this email, so if you have any questions, please ask me. Thank you The Snark
_______________________________________________ Devl mailing list Devl@freenetproject.org https://emu.freenetproject.org/cgi-bin/mailman/listinfo/devl
