[FoRK] How To Attack Scale-Free Networks

Contempt for Meatheads jbone at place.org
Thu May 6 12:29:13 PDT 2004


Great new bits up on Global Guerillas:

	http://globalguerrillas.typepad.com/globalguerrillas/2004/05/
scalefree_terro.html

HOW TO ATTACK SCALE-FREE NETWORKS

Scale-free networks are everywhere. The can be seen in airline traffic
routes, connections between actors in Hollywood, weblog links, sexual
relationships, and terrorist networks. So what exactly is a scale-free
network? A scale-free network is one that obeys a power law
distribution in the number of connections between nodes on the network.
Some few nodes exhibit extremely high connectivity (essentially
scale-free) while the vast majority are relatively poorly connected.
The reason that scale-free networks emerge, as opposed to evenly
distributed random networks, is due to these factors:

    * Rapid growth confers preference to early entrants. The longer a
node has been in place the greater the number of links to it. First
mover advantage is very important.
    * In an environment of too much information people link to nodes
that are easier to find. This preferential linking reinforces itself by
making the easier to find nodes even more easy to find.
* The greater the capacity of the hub (bandwidth, work ethic, etc.) the
faster its growth.


The Strength and Weaknesses of Scale-Free Networks
The proliferation of scale-free networks and our increasing dependence
on them (particularly given their prevalence in energy, transportation,
and communications systems) begs the question: how reliable are these
networks? Here's some insight into this:

    * Scale-free networks are extremely tolerant of random failures. In
a random network, a small number of random failures can collapse the
network. A scale-free network can absorb random failures up to 80% of
its nodes before it collapses. The reason for this is the inhomogeneity
of the nodes on the network -- failures are much more likely to occur
on relatively small nodes.
    * Scale-free networks are extremely vulnerable to intentional
attacks on their hubs. Attacks that simultaneously eliminate as few as
5-15% of a scale-free network's hubs can collapse the network.
Simultaneity of an attack on hubs is important. Scale-free networks can
heal themselves rapidly if an insufficient number of hubs necessary for
a systemic collapse are removed.
* Scale-free networks are extremely vulnerable to epidemics. In random
networks, epidemics need to surpass a critical threshold (a number of
nodes infected) before it propogates system-wide. Below the threshold,
the epidemic dies out. Above the threshold, the epidemic spreads
exponentially. Recent evidence indicates that the threshold for
epidemics on scale-free networks is zero.


What this means for Counter-terrorists
Given the vulnerability of scale-free networks to intentional
disruption, what does this mean for counter-terrorist planners (which I
hope, but doubt, they are thinking about)? This theory has strong
implications for defense as well as offense. Here's what it means:

    * Eliminating terrorist scale-free network hubs will likely not be
effective. Non-state terrorist networks are not only scale-free they
also exhibit small world properties (see "TERRORIST CELLS" for more).
This means that while large hubs still dominate the network, the
presence of tight clusters (cells), continues to provide local
connectivity when the hubs are removed. This implies that the attack on
al Qaeda's Afghanistan training camps (the location of multiple hubs)
did not collapse its network in any meaningful way. Rather, it atomized
the network into anonymous clusters of connectivity until the hubs
could reassert their priority again. Additionally, many of these
clusters, even without the global connectivity provided by the hubs,
will still be able to conduct attacks if they are of sufficient size
and complexity (a variety of skill sets). A better approach may be to
observe the hubs covertly to assertain the location of local clusters
that need to be shut down.
    * Critical terrorist social network hubs cannot be identified based
on the number of links alone. Hubs vary in value depending on multiple
vectors such as depth of connections (strong face-to-face social
history is extremely important for trust development in covert networks
-- see MAPPING TERRORIST NETWORKS for more), frequency of contact
(which may indicate the individual is a conduit for information flow
rather than an resource), and duration of links (which is tied to the
importance of that individuals skill set to ongoing operations of cells
they connect to). Analysis of the network along each of vectors can
make for better decision making.
* Defense against attacks on hubs can be achieved in ways other than
physical defense. These methods include: increasing the capacity of all
hubs to absorb the taffic of failed hubs (a kind of surge protection),
limiting or decreasing the maximum number of connections to any one hub
(reduction in criticality), and increasing the cross connectivity of
the network (local pooling of resources).

Posted by John Robb on 07.05.2004 at 09:50 AM | Permalink

_______________________________________________
FoRK mailing list
http://xent.com/mailman/listinfo/fork

----- End forwarded message -----
--
Eugen* Leitl <a href="http://leitl.org">leitl</a>
______________________________________________________________
ICBM: 48.07078, 11.61144            http://www.leitl.org
8B29F6BE: 099D 78BA 2FD3 B014 B08A  7779 75B0 2443 8B29 F6BE
http://moleculardevices.org         http://nanomachines.net

[demime 1.01d removed an attachment of type application/pgp-signature]





More information about the cypherpunks-legacy mailing list