Abstract

We study the architecture of networks which are robust to attacks by an intelligent adversary.

We start with a model in which designer chooses a network with a view to maximizing communication between nodes, and the adversary can choose to attack nodes. Our analysis focuses on a simple trade-off: better connected agents are more likely to succeed in completing the task. Monitoring on the part of the adversary however induces a cost to connecting agents since detection of a single node in the network may lead to the detection of other connected nodes. We first characterize optimal networks faced with a uniform attack probability of all nodes. We show that optimal networks are constituted of cells which increase in number (and decrease in size) as the intensity of monitoring grows. We then examine the optimality of uniform attack strategy: symmetric attacks are optimal if adversary has very large budgets, but asymmetric attacks are optimal otherwise. Interestingly, optimal networks are constituted of equal size cells, irrespective of adversary budget size!

We then allow for designer to choose a network as well as to defend individual nodes. The robustness of networks now depends on the efficacy of defense and attack technologies. If nodes can be made attack-proof and designer has small budgets then star network and its variants are optimal.