The impact of graph properties on the complexity of attack tree analysis

Attack Trees are tree-like diagrams that represent the logical steps by which a target may be attacked. They may be analysed to extract meaningful information about attacks on the given system. As the target systems become ever more complex, so does its Attack Tree, as more information is incorporated into them. This paper studies which graph metrics—such as the number of nodes, or the depth of the tree—affect the complexity of Attack Tree analyses and how they are affected. It appears that the most effective metric that was explored is the number of so-called foster nodes in an Attack Tree.