An important way cyber adversaries find vulnerabilities in modern networks is through reconnaissance, in which they attempt to
identify configuration specifics of network hosts. To increase uncertainty of adversarial reconnaissance, the network administrator
(henceforth, defender) can introduce deception into responses to
network scans, such as obscuring certain system characteristics.
We introduce a novel game-theoretic model of deceptive interactions of this kind between a defender and a cyber attacker, which
we call the Cyber Deception Game. We consider both a powerful
(rational) attacker, who is aware of the defender’s exact deception
strategy, and a naive attacker who is not. We show that computing
the optimal deception strategy is NP-hard for both types of attackers.
For the case with a powerful attacker, we provide a mixed-integer
linear program solution as well as a fast and effective greedy algorithm. Similarly, we provide complexity results and propose exact
and heuristic approaches when the attacker is naive. Our extensive experimental analysis demonstrates the effectiveness of our