  Honeypot is an important cyber defense technique that can expose attackers
new attacks. However, the effectiveness of honeypots has not been
systematically investigated, beyond the rule of thumb that their effectiveness
depends on how they are deployed. In this paper, we initiate a systematic study
on characterizing the cybersecurity effectiveness of a new paradigm of
deploying honeypots: blending honeypot computers (or IP addresses) into
production computers. This leads to the following Honeypot Deployment (HD)
problem, How should the defender blend honeypot computers into production
computers to maximize the utility in forcing attackers to expose their new
attacks while minimizing the loss to the defender in terms of the digital
assets stored in the compromised production computers? We formalize HD as a
combinatorial optimization problem, prove its NP hardness, provide a near
optimal algorithm (i.e., polynomial time approximation scheme). We also conduct
simulations to show the impact of attacker capabilities.
