Abstract
The representation of Internet traffic as connection graphs augments anomaly detection systems by providing insight on the structural connection properties, i.e., who-talks-to-whom. However, these graphs are extremely large and one has to decide in advance on which aspect to focus. In the context of malware detection, this is difficult as malware often mimics legitimate traffic. In this paper, we present a statistical approach for extracting the typical traffic destinations for a set of monitored hosts, and derive a reduced graph that contains only connections that are anomalous for that host. This graph can then be analyzed efficiently. Our system is designed to scale to thousands of monitored hosts. We evaluate our approach using a data set from a real network, and show that we can reliably detect injected malware activity.