The Power of the Defender

We consider a security problem on a distributed network. We assume a network whose nodes are vulnerable to infection by threats (e.g. viruses), the attackers. A system security software, the defender, is available in the system. However, due to the network’s size, economic and performance reasons, it is capable to provide safety, i.e. clean nodes from the possible presence of attackers, only to a limited part of it. The objective of the defender is to place itself in such a way as to maximize the number of attackers caught, while each attacker aims not to be caught. In [7], a basic case of this problem was modeled as a non-cooperative game, called the Edge model. There, the defender could protect a single link of the network. Here, we consider a more general case of the problem where the defender is able to scan and protect a set of k links of the network, which we call the Tuple model. It is natural to expect that this increased power of the defender should result in a better quality of protection for the network. Ideally, this would be achieved at little expense on the existence and complexity of Nash equilibria (profiles where no entity can improve its local objective unilaterally by switching placements on the network). In this paper we study pure and mixed Nash equilibria in the model. In particular, we propose algorithms for computing such equilibria in polynomial time and we provide a polynomial-time transformation of a special class of Nash equilibria, called matching equilibria, between the Edge model and the Tuple model, and vice versa. Finally, we establish that the increased power of the defender results in higher-quality protection of the network.