George Mason University
The authors optimally place Intrusion Detection System (IDS) sensors and prioritize IDS alerts using attack graph analysis. They begin by predicting all possible ways of penetrating a network to reach critical assets. The set of all such paths through the network constitutes an attack graph, which they aggregate according to underlying network regularities, reducing the complexity of analysis. They then place IDS sensors to cover the attack graph, using the fewest number of sensors. This minimizes the cost of sensors, including effort of deploying, configuring, and maintaining them, while maintaining complete coverage of potential attack paths. The sensor-placement problem they pose is an instance of the NP-hard minimal set cover problem.