Semantics of Attack-Defense Trees for Dynamic Countermeasures and a New Hierarchy of Star-Free Languages

We present a mathematical setting for attack-defense trees (adts), a classic graphical model to specify attacks and countermeasures. We equip adts with (trace) language semantics allowing to have an original dynamic interpretation of countermeasures. Interestingly, the expressiveness of adts coincides with star-free languages, and the nested countermeasures impact the expressiveness of adts. With an adequate notion of countermeasure-depth, we exhibit a strict hierarchy of the star-free languages that does not coincide with the classic one. Additionally, driven by the use of adts in practice, we address the decision problems of trace membership, non-emptiness, and equivalence, and study their computational complexities parameterized by the countermeasure-depth.