A honeynet is a portion of routed but otherwise unused address space that is instrumented for network traffic monitoring. Over the past several years, honeynets have proven to be an invaluable tool for monitoring and detecting unwanted Internet traffic and malicious attacks. However malicious parties are also aware of these honeynets and will attempt to identify these from normal host addresses by probes.

We address the problem of defending honeynets against systematic mapping.  Honeynet can be periodically reshuffled. But reshuffling is a relatively costly operation. In between reshuffles honeynet can engage in limited conversations with probing hosts.  This serves to obfuscate malicious probes while collecting data.  We model this problem as a two-person game between an Attacker and a Defender. A segment of the address space is marked as an honeynet, hidden from the Attacker.  The objective of the Attacker is to identify the embedded honeynet by probes. The Defender wants to obfuscate so as to minimize the shuffling frequency.

After defining the precise formulation of the game, we give provable optimal strategies for both the Attacker and Defender.  The main technical ingredient is a combinatorial lemma concerning a packing problem.

My colleagues have also implemented a network shuffling middlebox. Experimental results show that the system is capable of effectively defending large networks, with limited impact on normal traffic, and responds well in the face of network attacks and anomalies.

Joint work with Vinod Yegneswaran, Chris Alfeld and Paul Barford.