Honeypot Allocation over Attack Graphs in Cyber Deception Games

In this paper, we propose a scalable algorithm to allocate honeypots over an attack graph. We formulate a two-person zero-sum strategic game between the network defender and an attacker. This formulation captures the importance of different nodes inside the network. The game mode accounts for the cost associated with different defense strategies as well as the cost paid by the attacker. Moreover, this game model considers a practical threat model with respect to the available information about the attacker to the network defender. Nash equilibrium defense strategies are analytically characterized and studied for a special game. The complexity of a general game is discussed and a scalable algorithm is proposed to obtain honeypots allocation strategy in large scale networks. Finally, samples of our numerical results are shown to verify our findings.