The Mathematical Structure of Attack Trees

Abstract

In the kitchen, every cook can start with the same ingredients and end with a different result based on the recipe used. However, without cooking a hundred dishes, how can you tell which recipe is best? This problem of how to compare 'recipes' can be used to imagine the need for testing vulnerabilities in cybersecurity. In the field of cybersecurity, professionals use graphical models called attack trees to determine all the possible attacks on a particular system. These trees are basically recipes, or series of steps to gain a desired result. But they cannot be tested and compared by trial, so instead we need to use more abstract reasoning to weed outduplicates, compare prevention strategies and cost, and many other useful tasks. We are trying to translate the graphical models of attack trees into a mathematical model called POMSETs (partially-ordered multisets), in which each step in the recipe becomes a member of the POMSET. We then use several POMSET operators to build recipes with the proper ordering of steps. In doing this, we hope to be able to use these POMSET tools to better understand and compare the complex recipes that are attack trees.