| Anomaly detection systems offer the potential to identify new attacks before signatures are identified. To do so, these systems build models of normal user activity from historical data and then use these models to identify deviations from normal behavior caused by attacks.; In this thesis, we develop a method of anomaly detection using protocol graphs, graph-based representations of network traffic. These protocol graphs model the social relationships between clients and servers, allowing us to identify clever attackers who have a hit list of targets, but don't understand the relationships these targets have to each other.; While this method can identify subtle attacks, anomaly detection systems and IDS in general are challenged by the rise of large-scale industrialized attacks conducted by botnets. The attackers who use botnets have an active interest in acquiring new hosts, leading to a general form of attack we refer to as harvesting. Harvesting attacks consist of a constant stream of low-success high-volume attempts to take over multiple hosts. Because attackers face relatively little risk of detection, harvesting attacks are conducted continuously. These attacks result in a constant stream of garbage traffic that can mistrain an anomaly detector, if the detector assumes that attacks are rare. Furthermore, since harvesting attacks have such a low success rate, they generally represent minimal risk to a network, treating all attacks as equivalent raises the alarm rate extensively even when the attacks represent little risk to the systems that the anomaly detector monitors.; To that end, we complement our anomaly detection system by developing a novel training method that can eliminate hostile activity even when it makes up the majority of logged traffic. Using this training method, we are able to increase the sensitivity of our detection method by two orders of magnitude, in order to detect subtle and successful compromises.; Finally, we examine the impact of our anomaly detection system on attacks by developing a novel payoff-based evaluation method. This approach treats alarms as a design specification to the attacker and demonstrates that by using alarms in combination, we can develop a system that caps the attacker's maximum effectiveness. However, we also show that all the systems we examine (ours and otherwise) have specific limits to their detection capabilities which reward a subtle attacker. |
