Efficient Algorithms for Quantitative Attack Tree Analysis
This work addresses the need for efficient quantitative analysis in cybersecurity, providing methods to compute various security metrics for different types of attack trees, though it appears incremental as it builds on existing classification and algorithm frameworks.
The paper tackled the problem of efficiently computing security metrics for attack trees by classifying them into categories based on structure and gate types, and proposed novel algorithms for each class that work over a generic attribute domain, with analysis of their computational complexity.
Numerous analysis methods for quantitative attack tree analysis have been proposed. These algorithms compute relevant security metrics, i.e. performance indicators that quantify how good the security of a system is, such as the most likely attack, the cheapest, or the most damaging one. This paper classifies attack trees in two dimensions: proper trees vs. directed acyclic graphs (i.e. with shared subtrees); and static vs. dynamic gates. For each class, we propose novel algorithms that work over a generic attribute domain, encompassing a large number of concrete security metrics defined on the attack tree semantics. We also analyse the computational complexity of our methods.