Fast and optimal countermeasure selection for attack defence trees

Risk treatment is an important part of risk management, and deals with the question which security controls shall be implemented in order to mitigate risk. Indeed, most notably when the mitigated risk is low, the costs engendered by the implementation of a security control may exceed its benefits. The question becomes particularly interesting if there are several countermeasures to choose from. A promising candidate for modeling the effect of defensive mechanisms on a risk scenario are attack–defence trees. Such trees allow one to compute the risk of a scenario before and after the implementation of a security control, and thus to weigh its benefits against its costs. A naive approach for finding an optimal set of security controls is to try out all possible combinations. However, such a procedure quickly reaches its limits already for a small number of defences. This paper presents a novel branch-and-bound algorithm, which skips a large part of the combinations that cannot lead to an optimal solution. The performance is thereby increased by several orders of magnitude compared to the pure brute–force version. © 2017, Springer International Publishing AG.