  Attack trees (ATs) are a widely deployed modelling technique to categorize
potential attacks on a system. An attacker of such a system aims at doing as
much damage as possible, but might be limited by a cost budget. The maximum
possible damage for a given cost budget is an important security metric of a
system. In this paper, we find the maximum damage given a cost budget by
modelling this problem with ATs, both in deterministic and probabilistic
settings. We show that the general problem is NP-complete, and provide
heuristics to solve it. For general ATs these are based on integer linear
programming. However when the AT is tree-structured, then one can instead use a
faster bottom-up approach. We also extend these methods to other problems
related to the cost-damage tradeoff, such as the cost-damage Pareto front.
