  We present a mathematical setting for attack-defense trees, a classic
graphical model to specify attacks and countermeasures. We equip attack-defense
trees 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 countermeasure-depth, we exhibit a strict hierarchy of the
star-free languages that does not coincides with the classic one. 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 countermeasure-depth.
