Transcript Photo Album
The Topology of Covert Conflict Shishir Nagaraja, Ross Anderson Cambridge University Topology and Resilience • Many real-world networks can be modeled as scale-free – social contacts, disease spread, spread of computer viruses • Power-law distribution of vertex order, often arising from preferential attachment • Highly-connected nodes greatly enhance connectivity • This gives resilience against random failure Topology and Vulnerability • Although power-law vertex order distribution gives resilience to random failure, it makes the network vulnerable to targeted attack • If you attack high-order nodes, the network is rapidly disconnected (Albert, Jeong and Barabási, 2000) • Example: Sierra Leone HIV/AIDS program treated prostitutes first – only 2% of population infected (vs 40% in Botswana) Topology and Vulnerability (2) • Music companies target high-order nodes in peer-to-peer networks (prolific uploaders) • More traditional example: if you conquer a country, subvert or kill the bourgeoisie first • What about the dynamic case, e.g. insurgency? Police keep arresting, insurgents keep recruiting • We set out to study this dynamic case, using evolutionary game theory Simulation Methodology • After Axelrod’s work on iterated prisoners’ dilemma • Scale-free network of 400 nodes • At each round, attacker kills 10 nodes – their selection is his strategy • Defender recruits 10 more, then reconfigures network – how he does this is his strategy • Iterate search for defense, attack strategy Naïve Defenses Don’t Work! • Basic vertexorder attack – network dead after 2 rounds • Random replenishment – 3 rounds • Scale-free replenishment – 4 rounds Evolving Defense Strategies • Black – scalefree replenishment • Green – replace high-order nodes with rings • Cyan - replace high-order nodes with cliques • Cliques work very well against the vertex-order attack Evolving Attack Strategies • Centrality attacks are the best counter we found to clique-based defenses • Rings: G, B cliques: C, M • Vertex-order attack: B, G, C • Attack using centrality: R, B, M Next Evolution … • Combine two defensive strategies – yellow graph is delegation plus cliques • Modern terror network? • 3rd-generation music-sharing network? What this teaches • People set out to make peer-to-peer systems robust by arranging the nodes in rings. This didn’t work. Clubs do work • We have some insight into why insurgents organise themselves in cells • We can model strategies for wiretapping, surveillance, counterinsurgency … • What about biology? Biological Robustness • Redundancy via homologous genes makes an organism better able to evolve (phenotypic changes less often lethal) • This evolvability is an important element of robustness (Hiroaki Kitano, Nature, Nov 2004, pp 826–837) • What we call ‘cells’ biologists think of as conserved clusters, the bows in bow-tie networks, or evolutionary capacitors • Our work may give an insight into the evolution of hierarchical modularity Conclusion • We’ve built a bridge between network analysis and evolutionary game theory • Using our simulation methodology, we get insights into why revolutionaries use cells, the effects of modern policing, and more • Simulations let us explore many new attack and defense strategies • Implications for all sorts of networks – computer, social, political … biological?