• attack graph
• complex attacks
• monotonic assumption
• network security
• safeguard selection

When intelligent threats attack a system, they rarely achieve their goals by exploiting a single vulnerability. Rather, they achieve their goals by composing attacks and by exploiting structural security flaws of the target system. Attack graphs have been the de facto tool for discovering possible complex attacks. This thesis proposes a cost-effective safeguard selection strategy, which first identifies a complex attack set that covers all the complex attacks through the use of attack graphs and later selects a minimal set of countermeasures through the formulation and resolution of an integer linear programming problem. Multiple goals in conjunction or disjunction relation can be analyzed. We have built a working prototype system that implements this strategy and that helps maximizing the return-on-investment by identifying critical stepping-stone hosts and by suggesting the most cost-effective set of countermeasures. The mechanism of this approach is independent of the modeling abstraction level. We have considered both an example model that goes into the details of elementary attacks and an example model that targets worst-case analysis.