Modelling Attack-defense Trees Using Timed Automata

Olga Gadyatskaya, René Rydhof Hansen, Kim Guldstrand Larsen, Axel Legay, Mads Chr. Olesen, Danny Bøgsted PoulsenFORMATS 2016 · DOI

TL;DR

This paper introduces a novel framework for modeling complex interactions between attackers and defenders in security scenarios. By translating attack-defense trees into timed automata, the authors enable automated analysis of security risks, allowing for the quantification of attack probabilities and costs under various defense strategies.

What Problem Does This Paper Address?

In today's interconnected world, organizations face increasingly sophisticated security threats. Performing thorough security risk assessments is crucial but challenging, especially with the rise of outsourced services and complex internal IT infrastructures. Traditional attack trees, while useful for modeling attacker actions, often fall short in capturing the dynamic interplay with defensive measures. This paper addresses the need for a more comprehensive approach that models both attacker and defender behaviors, incorporating temporal aspects, stochasticity, and costs to enable robust security analysis.

Methods

The core contribution of this paper is a framework that models attack-defense trees using timed automata. This involves:

  • Attack-Defense Trees (ADTs): An extension of traditional attack trees that explicitly models both attacker and defender actions.
  • Timed Semantics: Introducing temporal aspects to ADTs, allowing for the modeling of execution times for actions.
  • Stochastic Semantics: Incorporating probabilities for action success and execution time distributions, enabling probabilistic analysis.
  • Cost Modeling: Assigning costs to attacker actions to analyze the economic impact of attacks.
  • Timed Automata Encoding: Translating the ADT semantics into a network of timed automata. This encoding allows leveraging existing model-checking tools like UPPAAL for automated analysis. The authors describe how to model the attacker, defender, and the environment that resolves non-determinism.

Datasets

Not discussed in the paper. The paper uses a running example of an attack-defense tree (Figure 1) for illustration and evaluation.

Key Insights and Ideas

  • Separation of Concerns: The framework effectively separates the modeling of attacker and defender behaviors from the attack-defense tree itself. This allows for intuitive modeling of complex temporal interactions without overcomplicating the attack-defense tree structure.
  • Automated Analysis: By encoding ADTs into timed automata, the paper unlocks the power of state-of-the-art model-checking tools for quantitative and qualitative security analysis. This moves beyond manual analysis and enables more thorough risk assessments.
  • Comprehensive Modeling: The inclusion of time, stochasticity, and costs provides a more realistic and nuanced view of security scenarios, allowing for analysis of questions like "how quickly can an attack succeed?" or "what is the expected cost of an attack?".
  • Synthesized Attackers: The framework can be used to find optimal attacker strategies that minimize costs, demonstrating its potential for understanding attacker motivations and predicting their behavior.

Key Results

The paper demonstrates the application of its framework through several questions and experimental results:

  • Question 1 (Boolean Analysis): Whether a set of defenses can prevent an attack, answerable by reachability checks on attack graphs.
  • Question 2 (Timed Defense): Whether a set of defenses can ensure an attack takes longer than a specified time limit, answerable by timed reachability checks.
  • Question 3 (Timed Attack): Whether an attacker can achieve a successful attack within a given time limit, also answerable by timed reachability checks.
  • Question 4 (Cost Minimization): Finding a defense strategy that minimizes the expected cost of an attack.
  • Question 5 (Expected Cost): Estimating the expected cost of a uniform attacker within a time limit. Table 1 shows that selecting specific defense measures (t2, t1, tf) can significantly reduce expected costs, sometimes equivalent to selecting all defense measures.
  • Question 6 (Cost Minimizing Attacker): Finding a stochastic attacker profile that minimizes its cost. The UPPAAL-STRATEGO tool was used to synthesize such attackers, which generally achieved reduced expected costs by avoiding blocked attacks and expensive actions.

Limitations and Future Work

  • Limitations:
    • The current framework assumes a uniform distribution for attacker action execution times and a fixed probability of success.
  • The modeling of the defender's strategy is simplified, assuming they select a fixed set of defense measures.
  • The paper mentions that the stochastic semantics is given for arbitrary time distributions, but for the remainder, they restrict attention to stochastic attackers using only uniform distributions.
  • Future Work:
    • The authors plan to extend the framework by describing the attacker's actual behavior in a more thorough way, potentially incorporating parts of other works that add temporal behaviors.
  • They aim to maintain these more complex behaviors in a separate modeling language to keep the core ADT description simple.

Summary updated

BibTeX
@inproceedings{gadyatskaya2016modelling,
  author = {Olga Gadyatskaya and René Rydhof Hansen and Kim Guldstrand Larsen and Axel Legay and Mads Chr. Olesen and Danny Bøgsted Poulsen},
  title = {{Modelling Attack-defense Trees Using Timed Automata}},
  booktitle = {FORMATS},
  year = {2016},
  doi = {10.1007/978-3-319-44878-7\_3},
}
Figure