Dynamic topologies for robust scale-free networks

Shishir Nagaraja, Ross Anderson

Research output: Chapter in Book/Report/Conference proceedingConference contribution book

4 Citations (Scopus)

Abstract

In recent years, the field of anonymity and traffic analysis have attracted much research interest. However, the analysis of subsequent dynamics of attack and defense, between an adversary using such topology information gleaned from traffic analysis to mount an attack, and defenders in a network, has recieved very little attention. Often an attacker tries to disconnect a network by destroying nodes or edges, while the defender counters using various resilience mechanisms. Examples include a music industry body attempting to close down a peer-to-peer file-sharing network; medics attempting to halt the spread of an infectious disease by selective vaccination; and a police agency trying to decapitate a terrorist organisation. Albert, Jeong and Barabási famously analysed the static case, and showed that vertex-order attacks are effective against scale-free networks. We extend this work to the dynamic case by developing a framework to explore the interaction of attack and defence strategies. We show, first, that naive defences don't work against vertex-order attack; second, that defences based on simple redundancy don't work much better, but that defences based on cliques work well; third, that attacks based on centrality work better against clique defences than vertex-order attacks do; and fourth, that defences based on complex strategies such as delegation plus clique resist centrality attacks better than simple clique defences. Our models thus build a bridge between network analysis and traffic analysis, and provide a framework for analysing defence and attack in networks where topology matters. They suggest definitions of efficiency of attack and defence, and may even explain the evolution of insurgent organisations from networks of cells to a more virtual leadership that facilitates operations rather than directing them. Finally, we draw some conclusions and present possible directions for future research.

Original languageEnglish
Title of host publicationBio-Inspired Computing and Communication - First Workshop on Bio-Inspired Design of Networks, BIOWIRE 2007, Revised Selected Papers
EditorsP. Liò, E. Yoneki , J. Crowcroft, D. C. Verma
Place of PublicationBerlin
PublisherSpringer
Pages411-426
Number of pages16
Volume5151
ISBN (Print)3540921907, 9783540921905
DOIs
Publication statusPublished - 1 Dec 2008
Event1st Workshop on Bio-Inspired Design of Networks, BIOWIRE 2007 - Cambridge, United Kingdom
Duration: 2 Apr 20075 Apr 2007

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5151 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference1st Workshop on Bio-Inspired Design of Networks, BIOWIRE 2007
CountryUnited Kingdom
CityCambridge
Period2/04/075/04/07

Fingerprint

Scale-free Networks
Complex networks
Attack
Topology
Law enforcement
Electric network analysis
Redundancy
Clique
Traffic Analysis
Centrality
Industry
Vertex of a graph
Delegation
Leadership
Vaccination
Infectious Diseases
Resilience
Anonymity
Network Analysis
Network Traffic

Keywords

  • covert groups
  • robustness
  • scale-free networks
  • security
  • topology
  • traffic analysis

Cite this

Nagaraja, S., & Anderson, R. (2008). Dynamic topologies for robust scale-free networks. In P. Liò, E. Yoneki , J. Crowcroft, & D. C. Verma (Eds.), Bio-Inspired Computing and Communication - First Workshop on Bio-Inspired Design of Networks, BIOWIRE 2007, Revised Selected Papers (Vol. 5151 , pp. 411-426). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5151 LNCS). Berlin: Springer. https://doi.org/10.1007/978-3-540-92191-2_36
Nagaraja, Shishir ; Anderson, Ross. / Dynamic topologies for robust scale-free networks. Bio-Inspired Computing and Communication - First Workshop on Bio-Inspired Design of Networks, BIOWIRE 2007, Revised Selected Papers. editor / P. Liò ; E. Yoneki ; J. Crowcroft ; D. C. Verma . Vol. 5151 Berlin : Springer, 2008. pp. 411-426 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{9713c3c2fa7143f09735315c1b5153af,
title = "Dynamic topologies for robust scale-free networks",
abstract = "In recent years, the field of anonymity and traffic analysis have attracted much research interest. However, the analysis of subsequent dynamics of attack and defense, between an adversary using such topology information gleaned from traffic analysis to mount an attack, and defenders in a network, has recieved very little attention. Often an attacker tries to disconnect a network by destroying nodes or edges, while the defender counters using various resilience mechanisms. Examples include a music industry body attempting to close down a peer-to-peer file-sharing network; medics attempting to halt the spread of an infectious disease by selective vaccination; and a police agency trying to decapitate a terrorist organisation. Albert, Jeong and Barab{\'a}si famously analysed the static case, and showed that vertex-order attacks are effective against scale-free networks. We extend this work to the dynamic case by developing a framework to explore the interaction of attack and defence strategies. We show, first, that naive defences don't work against vertex-order attack; second, that defences based on simple redundancy don't work much better, but that defences based on cliques work well; third, that attacks based on centrality work better against clique defences than vertex-order attacks do; and fourth, that defences based on complex strategies such as delegation plus clique resist centrality attacks better than simple clique defences. Our models thus build a bridge between network analysis and traffic analysis, and provide a framework for analysing defence and attack in networks where topology matters. They suggest definitions of efficiency of attack and defence, and may even explain the evolution of insurgent organisations from networks of cells to a more virtual leadership that facilitates operations rather than directing them. Finally, we draw some conclusions and present possible directions for future research.",
keywords = "covert groups, robustness, scale-free networks, security, topology, traffic analysis",
author = "Shishir Nagaraja and Ross Anderson",
year = "2008",
month = "12",
day = "1",
doi = "10.1007/978-3-540-92191-2_36",
language = "English",
isbn = "3540921907",
volume = "5151",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer",
pages = "411--426",
editor = "P. Li{\`o} and {Yoneki }, E. and J. Crowcroft and {Verma }, {D. C.}",
booktitle = "Bio-Inspired Computing and Communication - First Workshop on Bio-Inspired Design of Networks, BIOWIRE 2007, Revised Selected Papers",

}

Nagaraja, S & Anderson, R 2008, Dynamic topologies for robust scale-free networks. in P Liò, E Yoneki , J Crowcroft & DC Verma (eds), Bio-Inspired Computing and Communication - First Workshop on Bio-Inspired Design of Networks, BIOWIRE 2007, Revised Selected Papers. vol. 5151 , Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5151 LNCS, Springer, Berlin, pp. 411-426, 1st Workshop on Bio-Inspired Design of Networks, BIOWIRE 2007, Cambridge, United Kingdom, 2/04/07. https://doi.org/10.1007/978-3-540-92191-2_36

Dynamic topologies for robust scale-free networks. / Nagaraja, Shishir; Anderson, Ross.

Bio-Inspired Computing and Communication - First Workshop on Bio-Inspired Design of Networks, BIOWIRE 2007, Revised Selected Papers. ed. / P. Liò; E. Yoneki ; J. Crowcroft; D. C. Verma . Vol. 5151 Berlin : Springer, 2008. p. 411-426 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5151 LNCS).

Research output: Chapter in Book/Report/Conference proceedingConference contribution book

TY - GEN

T1 - Dynamic topologies for robust scale-free networks

AU - Nagaraja, Shishir

AU - Anderson, Ross

PY - 2008/12/1

Y1 - 2008/12/1

N2 - In recent years, the field of anonymity and traffic analysis have attracted much research interest. However, the analysis of subsequent dynamics of attack and defense, between an adversary using such topology information gleaned from traffic analysis to mount an attack, and defenders in a network, has recieved very little attention. Often an attacker tries to disconnect a network by destroying nodes or edges, while the defender counters using various resilience mechanisms. Examples include a music industry body attempting to close down a peer-to-peer file-sharing network; medics attempting to halt the spread of an infectious disease by selective vaccination; and a police agency trying to decapitate a terrorist organisation. Albert, Jeong and Barabási famously analysed the static case, and showed that vertex-order attacks are effective against scale-free networks. We extend this work to the dynamic case by developing a framework to explore the interaction of attack and defence strategies. We show, first, that naive defences don't work against vertex-order attack; second, that defences based on simple redundancy don't work much better, but that defences based on cliques work well; third, that attacks based on centrality work better against clique defences than vertex-order attacks do; and fourth, that defences based on complex strategies such as delegation plus clique resist centrality attacks better than simple clique defences. Our models thus build a bridge between network analysis and traffic analysis, and provide a framework for analysing defence and attack in networks where topology matters. They suggest definitions of efficiency of attack and defence, and may even explain the evolution of insurgent organisations from networks of cells to a more virtual leadership that facilitates operations rather than directing them. Finally, we draw some conclusions and present possible directions for future research.

AB - In recent years, the field of anonymity and traffic analysis have attracted much research interest. However, the analysis of subsequent dynamics of attack and defense, between an adversary using such topology information gleaned from traffic analysis to mount an attack, and defenders in a network, has recieved very little attention. Often an attacker tries to disconnect a network by destroying nodes or edges, while the defender counters using various resilience mechanisms. Examples include a music industry body attempting to close down a peer-to-peer file-sharing network; medics attempting to halt the spread of an infectious disease by selective vaccination; and a police agency trying to decapitate a terrorist organisation. Albert, Jeong and Barabási famously analysed the static case, and showed that vertex-order attacks are effective against scale-free networks. We extend this work to the dynamic case by developing a framework to explore the interaction of attack and defence strategies. We show, first, that naive defences don't work against vertex-order attack; second, that defences based on simple redundancy don't work much better, but that defences based on cliques work well; third, that attacks based on centrality work better against clique defences than vertex-order attacks do; and fourth, that defences based on complex strategies such as delegation plus clique resist centrality attacks better than simple clique defences. Our models thus build a bridge between network analysis and traffic analysis, and provide a framework for analysing defence and attack in networks where topology matters. They suggest definitions of efficiency of attack and defence, and may even explain the evolution of insurgent organisations from networks of cells to a more virtual leadership that facilitates operations rather than directing them. Finally, we draw some conclusions and present possible directions for future research.

KW - covert groups

KW - robustness

KW - scale-free networks

KW - security

KW - topology

KW - traffic analysis

UR - http://www.scopus.com/inward/record.url?scp=58449096466&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-92191-2_36

DO - 10.1007/978-3-540-92191-2_36

M3 - Conference contribution book

SN - 3540921907

SN - 9783540921905

VL - 5151

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 411

EP - 426

BT - Bio-Inspired Computing and Communication - First Workshop on Bio-Inspired Design of Networks, BIOWIRE 2007, Revised Selected Papers

A2 - Liò, P.

A2 - Yoneki , E.

A2 - Crowcroft, J.

A2 - Verma , D. C.

PB - Springer

CY - Berlin

ER -

Nagaraja S, Anderson R. Dynamic topologies for robust scale-free networks. In Liò P, Yoneki E, Crowcroft J, Verma DC, editors, Bio-Inspired Computing and Communication - First Workshop on Bio-Inspired Design of Networks, BIOWIRE 2007, Revised Selected Papers. Vol. 5151 . Berlin: Springer. 2008. p. 411-426. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-540-92191-2_36