Alexandre Terefenko

Highlights Conference 2023 Conference Abstract

Semantics of Attack-Defense Trees for Dynamic Countermeasures: a New Hierarchy of Star-free Languages

• Alexandre Terefenko

The presentation aims at presenting a mathematical setting for attack-defense trees, a classic graphical model to specify attacks and nested countermeasures, that we equip with trace language semantics allowing to have an original dynamic interpretation of countermeasures. Interestingly, the expressiveness of attack-defense trees coincides with star-free languages, and the nested countermeasures impact the expressiveness of attack-defense trees. With an adequate notion of counter-depth, we exhibit a strict hierarchy of the star-free languages that does not coincides either with the dot-depth hierarchy, or with the first-order logic alternation quantifier hierarchy on the very first levels. Additionally, driven by the use of attack-defense trees in practice, we address the decision problems of trace membership and of non-emptiness, and study their computational complexities parameterized by the counter-depth. The presentation is based on a joint work with Sophie Pinchinat and Thomas Brihaye. Contributed talk given by Alexandre Terefenko

GandALF Workshop 2022 Workshop Paper

Adversarial Formal Semantics of Attack Trees and Related Problems

• Thomas Brihaye
• Sophie Pinchinat
• Alexandre Terefenko

Security is a subject of increasing attention in our actual society in order to protect critical resources from information disclosure, theft or damage. The informal model of attack trees introduced by Schneier, and widespread in the industry, is advocated in the 2008 NATO report to govern the evaluation of the threat in risk analysis. Attack-defense trees have since been the subject of many theoretical works addressing different formal approaches. In 2017, M. Audinot et al. introduced a path semantics over a transition system for attack trees. Inspired by the later, we propose a two-player interpretation of the attack-tree formalism. To do so, we replace transition systems by concurrent game arenas and our associated semantics consist of strategies. We then show that the emptiness problem, known to be NP-complete for the path semantics, is now PSPACE-complete. Additionally, we show that the membership problem is coNP-complete for our two-player interpretation while it collapses to P in the path semantics.

LAMAS&SR Workshop 2022 Workshop Paper

Formal trace semantics for attack-defence trees

• Alexandre Terefenko

Highlights Conference 2022 Conference Abstract

Multi-Player Attack Trees

• Alexandre Terefenko

Security is a subject of increasing attention in our actual society in order to protect critical resources from information disclosure, theft or damage. The informal model of attack trees introduced by Schneier [2], and widespread in the industry, is advocated in the 2008 NATO report to govern the evaluation of the threat in risk analysis. Attack-defense trees have since been the subject of many theoretical works addressing different formal approaches (see [3] for an exhaustive list). In [1], the authors introduced a path semantics over a transition system for attack trees. The presentation will be established over an ongoing work framed by Sophie Pinchinat from IRISA and Thomas Brihaye from UMONS in which we generalise the works of [1] by allowing a multi-agent interpretation of the attack-tree formalism. To do it, we replace transition systems by concurrent game arenas and our associated semantics consist of strategies. We then show that our proposed semantics can be recognised by tree automata and we finish by determining bounds to the complexity of the emptiness problem. This problem answers the following question: is there a winning strategy for the the player/coalition trying to achieve the objective described by the attack tree? References: [1] Maxime Audinot, Sophie Pinchinat, and Barbara Kordy, Is my attack tree correct? , European Symposium on Research in Computer Security, Springer, 2017, pp. 83–102. [2] Bruce Schneier, Attack trees, Dr. Dobbs journal 24 (1999), no. 12, 21–29. [3] Wojciech Wide l, Maxime Audinot, Barbara Fila, and Sophie Pinchinat, Beyond 2014: Formal methods for attack tree–based security modeling, ACM Computing Surveys (CSUR) 52 (2019), no. 4, 1–36.