PaperlayerView exact revision on arXiv

Source-linked AI summary

DAG-Based Attack and Defense Modeling: Don't Miss the Forest for the Attack Trees

Barbara Kordy, Ludovic Piètre-Cambacédès, Patrick Schweitzer

arXiv:1303.7397v1cs.CR

TL;DR

DAG-based attack and defense modeling has grown into a field with more than 30 methodologies whose differing features and goals complicate comparison and selection. The paper surveys these formalisms, systematizes them using a common classification, and identifies unification and domain-specific specification as two broad trends. It concludes that the field remains rapidly growing, with further development needed to connect theoretical models to practical security assessment and automate model construction.

  • Problem

    More than 30 DAG-based attack and defense modeling methodologies have different features and goals, creating a need for a complete overview, comparison, and selection framework.

  • Method

    The survey describes existing DAG-based formalisms and classifies them using 13 aspects covering graphical, formal, and usability characteristics.

  • Results

    The survey identifies two broad trends: unification approaches for broad security scenarios and specification approaches for domain-specific problems.

  • Takeaways & Limitations

    The classification and tabular comparisons support selecting a formalism according to user requirements.

  • Takeaways & Limitations

    Further development is needed before security assessment can fully benefit from graphical models, including automated construction from reusable attack patterns.

Abstract

from arXiv · show

This paper presents the current state of the art on attack and defense modeling approaches that are based on directed acyclic graphs (DAGs). DAGs allow for a hierarchical decomposition of complex scenarios into simple, easily understandable and quantifiable actions. Methods based on threat trees and Bayesian networks are two well-known approaches to security modeling. However there exist more than 30 DAG-based methodologies, each having different features and goals. The objective of this survey is to present a complete overview of graphical attack and defense modeling techniques based on DAGs. This consists of summarizing the existing methodologies, comparing their features and proposing a taxonomy of the described formalisms. This article also supports the selection of an adequate modeling technique depending on user requirements.

1 Introduction

The survey addresses the rapidly expanding field of graphical attack and defense modeling by focusing on DAG-based formalisms and organizing their diverse features for comparison and selection.

  • Graphical security models combine intuitive visual representations with formal semantics and algorithms for qualitative and quantitative security analysis.
  • More than 30 attack and defense modeling approaches exist, extending threat-tree ideas with defenses, timing, ordering, dynamics, and quantification.
  • DAG-based approaches decompose feared events into refining nodes and support modularization, parallel expertise, and scalability for complex models.
  • The survey presents the state of the art in DAG-based graphical attack and defense modeling as of 2012.
  • It identifies comparison criteria, proposes a taxonomy, and explains how to select an appropriate formalism according to application requirements.

2 Preliminaries

The preliminaries establish shared terminology and a 13-aspect framework for comparing graphical security formalisms by modeling capabilities, structural characteristics, and maturity or usability.

  • 2.1 Keywords and Terminology: The survey defines attack and defense modeling as representing malicious behavior and reasoning about possible defensive strategies.
  • 2.1 Keywords and Terminology: A rooted DAG uses a single root node to represent the overall modeled concept, while leaf nodes represent atomic components no longer refined.
  • 2.1 Keywords and Terminology: Edges express relations between concepts, and connectors specify parent-child relationships through constructs such as AND, OR, XOR, and priority AND.
  • 2.2 Examined Aspects: The 13 aspects cover modeling capabilities, formalism characteristics, and maturity or usability factors including tools, case studies, and external use.
  • 2.2 Examined Aspects: The comparison framework distinguishes static from sequential approaches according to whether they model temporal or action-order dependencies.
  • 2.2 Examined Aspects: The classification helps users make a primary selection by asking what they want to model and how they want to model it.

3 Description of the Formalisms

The survey’s main descriptive section presents numerous DAG-based attack and defense approaches using a common template and orders them chronologically within each subsection.

  • 3 Description of the Formalisms: Section 3 describes numerous DAG-based approaches for graphical attack and defense modeling.
  • 3 Description of the Formalisms: Each subsection gathers models according to the description template outlined in Section 2.3.
  • 3 Description of the Formalisms: Models within each subsection are ordered chronologically by the year in which they were introduced.

3.1 Static Modeling of Attacks

Static attack modeling centers on AND-OR trees that hierarchically refine attacker goals into basic actions, with extensions adding quantitative measures, uncertainty handling, vulnerability-focused roots, and broader modeling features.

  • Attack Trees: Attack trees refine an attacker’s main goal recursively into conjunctive or disjunctive subgoals until reaching quantifiable basic actions.Disjunctive refinements represent alternatives, whereas conjunctive refinements require combined actions.
  • Attack Trees: Bottom-up attack-tree quantification can compute costs, attack time, and skill level, while more complex attributes require additional assumptions or alternative methods.Probability, risk, and similarity measures may require assumptions such as mutual independence among leaf nodes.
  • Attack Trees: Attack trees are widely supported by commercial and academic tools and numerous case studies, but their static attacker-only scope motivates extensions for defenses, dynamics, and ordered actions.The survey notes that terminology and the exact modeling scope vary across related tree formalisms.
  • Augmented Vulnerability Trees: Vulnerability trees use a vulnerability event as the root and branches for alternative exploitation paths, distinguishing them from attack trees’ attacker-goal roots.Their leaves represent attacker steps, and augmented versions combine concepts from vulnerability trees, fault trees, attack trees, and cause-consequence diagrams.
  • Augmented Attack Trees: Augmented attack trees add quantitative labels, descriptive edges, attack signatures, or generalized weights to support probability, forensic analysis, intrusion filtering, and detectability assessment.Different definitions target different operations, including measuring compromised subgoals, least effort, state transitions, and attack signatures.
  • OWA Trees: OWA trees replace AND and OR with ordered weighted averaging nodes that model quantifiers such as most, some, or half of the required actions.They support qualitative and quantitative attack modeling under uncertainty about how many actions must be satisfied.

3.2 Sequential Modeling of Attacks

Sequential attack models represent ordered stages and dependencies rather than only static logical relations, while extended fault trees incorporate security events into fault-tree analysis.

  • Cryptographic DAGs: Cryptographic DAGs represent attack stages as colored nodes, with arrows encoding dependencies and repeated enabling relationships.The color code indicates stage difficulty, and the formalism targets high-level descriptions of attack processes.
  • Cryptographic DAGs: Cryptographic DAGs provide visual descriptions of attack sequences but support no quantification and depend heavily on textual descriptions inside model boxes.They have been used to demonstrate attacks on SSL and Needham-Schroeder protocols.
  • Cryptographic DAGs: Unlike attack trees, cryptographic DAGs cannot capture static AND and OR relations, limiting them to sequence and dependency representations.The formalism’s text inside boxes is not standardized, which affects model clarity and usability.
  • Extended Fault Trees: Extended fault trees allow basic events to represent accidental failures, attack steps, or security events within a fault-tree structure.They add security modeling to classical fault-tree concepts while retaining explicit AND and OR gates.
  • Fault Trees for Security: Brooke and Paige question probabilistic quantitative analysis because useful probabilities are difficult to assign to computer-security events, recommending risk analysis instead.Their recommended risk analysis examines how systems fail based on primary events represented by leaf nodes.

3.2.3 Bayesian Networks for Security

Bayesian networks apply probabilistic DAG inference to security under uncertainty, representing events and causal dependencies while enabling efficient queries and model updates.

  • Bayesian Networks: Bayesian networks represent events or objects as probabilistic variables and directed edges as causal dependencies.They were adopted as a security modeling technique beginning in 2004 by several researchers.
  • Bayesian Networks: Bayesian-network methods can convert attack-tree relationships into probabilistic network structures for evaluating attack-goal likelihoods and predicting upcoming attacks.The surveyed conversion preserves attack-tree nodes while encoding logical relationships with directed edges.
  • Analysis Under Uncertainty: Efficient Bayesian-network inference algorithms support single or multiple queries on DAG structures, avoiding the general NP-hardness of querying arbitrary graphs.The DAG structure keeps the computational exponent small and reduces inference to polynomial algorithms when the DAG is a tree.
  • Analysis Under Uncertainty: Bayesian networks can update posterior distributions when new information becomes available, supporting security analysis under uncertainty.This updating capability is identified as a major strength alongside efficient inference.
  • Tool Support: The survey found no dedicated security-specific Bayesian-network analysis tools, although standard Bayesian-network tools and attack-graph software have been used.Examples include GeNIe/SMILE and MulVal.

3.2.4 Bayesian Attack Graphs

Bayesian attack graphs combine attack-graph structures with Bayesian-network inference after eliminating cycles, enabling probabilistic security analysis. The surveyed approaches differ in cycle-removal procedures, probability representations, and treatment of defenses.

  • Bayesian attack graphs combine general attack graphs with Bayesian-network computational procedures, requiring cycle elimination because Bayesian inference operates on cycle-free structures.After cycles are removed, the graphs model causal relationships between vulnerabilities.
  • All three surveyed approaches eliminate cycles from potentially cyclic underlying attack graphs, but their procedures differ in specificity and complexity.Liu and Man give no specific procedure, Frigault’s group refers to an intricate attack-graph procedure, and Poolsappasit et al. use a monotonicity constraint.
  • Liu and Man provide edge probabilities, Frigault et al. use CVSS-estimated conditional probability tables, and Poolsappasit et al. use local conditional probability distributions.
  • Poolsappasit et al. augment Bayesian attack graphs with defense nodes and values representing hardening measures, then propose a genetic algorithm on the augmented structure.
  • The Wang group uses the Topological Vulnerability Analysis tool to create attack graphs that form the basis for Bayesian attack graphs.
  • Wang et al. also base their work on acyclic Bayesian networks for modeling privacy-violation risks in databases.

3.2.5 Compromise Graphs

Compromise graphs assess technical security measures by modeling attack phases and their time-to-compromise costs. Related formalisms extend this time-based approach to architectural decomposition, while enhanced attack trees model ordered attack behavior and intrusion detection.

  • Compromise Graphs: Compromise-graph nodes represent attack phases, while weighted edges estimate the time required to complete each phase for a target compromise.
  • Compromise Graphs: The time-to-compromise metric models each edge as a random process combining exponential, gamma, and beta-like distributions.Parameters depend on known component vulnerabilities and the estimated attacker skill.
  • Compromise Graphs: Security-measure efficiency is evaluated by comparing shortest paths measured in TTC with and without hardening, firewalls, or enhanced authentication.
  • Compromise Graphs: The SCADA example applies compromise graphs to attacks, while STEA combines modified TTC calculations with decomposition by the targeted system’s architectural areas.
  • Enhanced Attack Trees: Enhanced attack trees add an ordered-AND gate to classical OR and AND gates, representing sequential behavior and attack-step ordering constraints.Their associated technique uses automata theory to verify model completeness for intrusion detection.
  • Enhanced Attack Trees: Enhanced attack-tree quantification defines subgoal confidence as the percentage-based chance of reaching the attacker’s final goal after that subgoal is accomplished.The confidence value is intended to support early warning of attacks.

3.2.7 Vulnerability Cause Graphs

Vulnerability cause graphs support root-cause analysis of security-related software failures by relating causes to a vulnerability exit node. They also represent mitigation and preserve mitigation status through graph transformations, but abstraction depth creates a design challenge.

  • Vulnerability cause graphs were developed to support security activities across the software development lifecycle.
  • Each vulnerability cause graph has one exit node representing the vulnerability, while other nodes represent conditions that can cause it.Directed predecessor-successor relationships express how conditions may cause other conditions.
  • Nodes can be marked blocked when their underlying causes are mitigated, allowing computation of whether the exit-node vulnerability is also mitigated.
  • Graph transformations can preserve whether the modeled vulnerability is mitigated, including conjunction conversion, sequence reordering, node combination, and compound-node conversion.
  • VCGs have been applied to multiple CVE vulnerabilities and software-vulnerability case studies, with the GOAT tool developed for use alongside them.
  • Compound nodes enable multiple abstraction layers, but introduce the design problem of deciding how many abstraction layers are appropriate.

3.2.8 Dynamic Fault Trees

Dynamic fault-tree gates extend attack trees with temporal and dependency behavior, including ordered execution. The surveyed dynamic attack-tree adaptation lacks its own quantification procedure, while serial multi-parameter models provide richer attacker-behavior analysis and several outcome-computation frameworks.

  • Dynamic Fault Trees: Khand adapted dynamic fault-tree gates to attack trees to add a dynamic dimension to classical attack trees.
  • Dynamic Fault Trees: The adapted formalism reuses PAND, SEQ, and FDEP gates, renaming FDEP as CSUB and omitting cold-spare gates.
  • Dynamic Fault Trees: The PAND gate succeeds when all inputs are realized in a prescribed left-to-right order.
  • Dynamic Fault Trees: The dynamic attack-tree paper develops no quantification aspects and does not specify a model-processing tool.
  • Dynamic Fault Trees: Markovian analysis techniques used for quantifying dynamic fault trees might also apply, although the surveyed attack-tree work does not describe computation details.
  • Serial Model for Multi-Parameter Attack Trees: Serial multi-parameter attack trees model either a prescribed attack order or fully adaptive ordering based on previous trial results.The serial approach is described as more accurate for attacker behavior than the parallel approach.
  • Serial Model for Multi-Parameter Attack Trees: An efficient algorithm computes expected attacker outcomes for a given order, while decision-theoretical and game-theoretical frameworks address maximal outcomes or upper utility bounds.Finding the best attack permutation may otherwise become superexponential.

3.2.10 Improved Attack Trees

Improved attack trees extend attack trees for space-based information systems by adding sequential AND nodes and a system-risk computation, but remain informally defined.

  • Improved attack trees target security risks in space-based information systems, including information links, acquisition systems, and ground-based systems.
  • The formalism explicitly incorporates a sequential AND operator while relying heavily on Schneier’s description.Its formal definition is not provided.
  • Leaf-node risk values are combined into risk rate, risk possibility, and overall system risk.The formulas distinguish OR, AND, and sequential AND nodes.

3.3 Static Modeling of Attacks and Defenses

Static attack and defense formalisms model decomposed security goals, protections, activities, or opposing actions without emphasizing temporal ordering, using varied qualitative and quantitative analyses.

  • Anti-models: Anti-models extend AND-OR goal-refinement structures with malicious and intentional obstacles to security goals called anti-goals.They can generate subtle attacks, discard non-realizable or unlikely ones, and derive more effective custom attacks.
  • Anti-models: Anti-model construction begins by negating security requirements, identifying attacker classes and goals, and refining anti-goals through an AND-OR process.
  • Anti-models: Anti-models do not provide quantitative analysis of security goals or anti-goals.
  • Defense trees: Defense trees decorate attack-tree leaves with countermeasures and support qualitative and quantitative security modeling.Their analyses use economic indexes and game-theoretical solution concepts, although the model itself is introduced verbally without a formal definition.
  • Protection trees: Protection trees allocate limited resources across defenses derived from attack-tree leaves, using probability, financial cost, performance cost, and sometimes impact.They have been applied to network, banking, RFID, and mobile ad hoc network protection cases.
  • Attack countermeasure trees: Attack countermeasure trees place defensive measures at any tree node and extend defense-tree analysis with probabilistic analysis.
  • Attack–defense trees: Attack–defense trees merge attack and protection trees to represent interleaved attacker and defender actions qualitatively and quantitatively.Hierarchical cumulative voting identifies effective countermeasures, favoring those preventing several attacks.

3.4 Sequential Modeling of Attacks and Defenses

Sequential and dynamic formalisms represent attack progression, intrusion response, probabilistic security dependencies, inspection indicators, and Markovian attack processes.

  • Insecurity flows: Insecurity flows combine graph theory and discrete probability to identify vulnerable paths and security measures in serial or parallel architectures.The probability of passing through modeled measures can be computed and defensive architectures compared.
  • Intrusion DAGs: Intrusion DAGs represent attack goals in ADEPTS, allowing multiple roots and AND-OR refinements linked to intrusion-detection alerts.
  • Intrusion DAGs: Three algorithms classify response candidates, assign response indices, and dynamically select subsequent responses using effectiveness indices.Effectiveness decreases after failed responses and increases after successful deployments.
  • Intrusion DAGs: ADEPTS was tested on a distributed e-commerce system with 6 servers and a corresponding 26-node intrusion DAG.
  • Bayesian defense graphs: Bayesian defense graphs use chance, decision, utility, and causal nodes with conditional probability tables to analyze security mechanisms and enterprise-wide security.Iterative refinement trades model complexity against the amount and accuracy of collected data.
  • Security goal indicator trees: Security goal indicator trees combine positive and negative inspection features through conditional dependencies, Boolean gates, and specialization relations.
  • Attack-response trees: The RRE performed better than static lookup-table response mechanisms, recovering systems at lower cost and helping with many distributed IDS alerts.The approach was implemented over Snort 2.7 and validated on SCADA and web-retail cases.
  • Boolean Logic Driven Markov Process: BDMPs combine attack-tree readability with Markov-chain modeling through triggers, logical gates, and dynamically selected Markov processes.This supports sequential modeling while enabling efficient quantification.

4 Summary of the surveyed formalisms

The survey consolidates DAG-based formalisms into comparable tables that organize modeling capabilities, characteristics, maturity, and usability to support technique selection.

  • Tables 2–4 characterize the surveyed methodologies using 13 aspects grouped into features and capabilities, characteristics, and maturity and usability factors.
  • The tables make similarities and differences easier to compare and support selection against specific modeling needs and requirements.Two exemplary situations illustrate this support.
  • Final methodology choices require complementary investigation of computational procedures and algorithms described in the referenced papers.

5 Alternative Methodologies

The survey situates DAG-based attack and defense models alongside alternative graphical security methodologies, including Petri nets, attack graphs, UML-derived approaches, and isolated extensions.

  • Petri nets: Petri-net approaches model security scenarios using colored, disjunctive, reference, generalized stochastic, deterministic-time, or aspect-oriented variants.Several works also combine Petri nets with security patterns or attack trees.
  • Privilege graphs: Privilege graphs represent an attacker’s progress through privilege states, with edges denoting vulnerability exploitation and memory preventing revisiting acquired states.
  • Other extensions: Other extensions address real-time cyber conflicts, context-sensitive incident analysis, prediction, concurrent actions, incomplete information, and stochastic non-controlled events.Some of these models contain cycles and therefore fall outside the survey’s main DAG scope.
  • Attack graphs: Attack graphs represent system states and attacker-induced transitions, supporting automated generation, model checking, combinatorial-explosion reduction, and quantitative security assessment.Quantitative extensions address vulnerability-removal cost, attack resistance, network-security measures, and probabilistic multi-step attack likelihood.
  • Attack chains: Attack chains combine deductive tree structures with inductive goal-inducing reasoning and can generate attack trees for conventional quantification.
  • UML-derived approaches: UML-derived misuse, abuse, and mal-activity diagrams capture threats, abusive behavior, security requirements, design, testing, or numerous system interactions.These approaches can also be combined with attack trees, while misuse and abuse cases may focus on architectural mechanisms rather than security requirements.

6 Conclusion

The survey organizes DAG-based attack and defense formalisms into a systematic overview and identifies unification and specification as two broad field trends. It also highlights unresolved practical challenges, especially automated model construction and stronger theory–practice interaction.

  • Survey contribution: The survey provides a complete overview, structured descriptions, related resources, and a classification based on 13 graphical, formal, and usability aspects.The classification supports comparison and selection of formalisms for attack and defense modeling.
  • Unification trend: Unification methodologies seek broad solutions for diverse security scenarios and typically provide formal foundations, semantics, and mathematical frameworks for quantitative analysis.Examples include attack–defense trees, parameterizable attack trees, OWA trees, Bayesian attack graphs, and Bayesian defense graphs.
  • Specification trend: Specification methodologies target domain-specific problems such as intrusion detection, secure software development, and security requirements engineering.They often use domain-specific metrics and remain isolated from other approaches.
  • Open research directions: Automatic construction from existing attack templates and patterns remains underdeveloped, leaving large-scale model creation manual, tedious, and error-prone.The survey identifies this as a research question requiring further attention.
  • Open research directions: Security-pattern reuse can improve threat-analysis efficiency and accuracy because attackers often reuse known attack vectors and vulnerabilities.Existing libraries such as the SVRS provide a basis for generating general models before refinement and analysis.
  • Theory–practice gap: A gap remains between theoretical research and practical employment, while stronger interaction could support integrating graphical models into standardized auditing and risk-assessment tools.The authors associate this integration with improved quality and usability of currently table-based methodologies.
Loading 1303.7397v1…