Graph Based Analysis of Multi Step Attack Paths

80 concepts53 papers1 proposal

Traditional security assessments treat vulnerabilities like items on a checklist. A scanner crawls an environment, generates a list of flaws, and assigns each a severity score based on isolated technical metrics.

However, real-world attackers rarely rely on a single catastrophic exploit. Instead, they navigate systems like a map, combining minor, low-severity flaws into complex, multi-stage intrusion sequences. A low-risk vulnerability on an internet-facing server might grant low-level access, which is then used to exploit an internal configuration error, ultimately leading to full administrative control.

To capture this reality, a prominent research direction models security risks not as isolated bugs, but as interconnected attack paths within a graph. By representing software architectures, network topologies, and system permissions as graphs, researchers can analyze how vulnerabilities chain together to threaten critical assets.

The Fallacy of the Isolated Bug

Evaluating vulnerabilities in isolation creates a dangerous blind spot. As Ankur Chowdhary et al. observe in their work on Adaptive MTD Security using Markov Game Modeling, naive security strategies that prioritize flaws purely by individual severity scores often leave critical paths wide open. They fail to recognize how multiple minor vulnerabilities can be chained together to reach a high-value target.

This distinction is formalized by Thaier Hamid et al. in Methodologies to Develop Quantitative Risk Evaluation Metrics, where they separate vulnerabilities into two categories:

  1. Direct vulnerabilities: Flaws that are immediately reachable from an external network.
  2. Indirect vulnerabilities: Flaws accessible only via lateral movement after an initial foothold has been established.

Without modeling these multi-step intrusion paths, organizations cannot accurately assess the true risk of an attacker pivoting through their network. For instance, Ujas Dhami in Effectuating Blockchain Network Compromise by Orchestrating a Daisy - Chain Architecture demonstrates how an initial operating system breach can move laterally to compromise a blockchain protocol, illustrating how disparate exploits across different layers are linked in practice.

Representing Systems as Attack Graphs

To uncover these hidden pathways, researchers translate complex environments into structural graph representations. In these graphs, nodes can represent vulnerabilities, system components, or access permissions, while edges represent the relationships, data flows, or dependencies between them.

[ Internet ] 
     │
     ▼
[ Web Server ] ──(Data Flow / Trust Boundary)──► [ Internal Database ]
  (Bug A: Low)                                      (Bug B: Medium)
     │                                                     │
     └───────────────────► [ Exploit Chain ] ──────────────┘
                        (Result: Critical Breach)

This graph-based framing is highly versatile and applies across several domains:

The Mechanics of Vulnerability Chaining

Why do these chains work? At a technical level, vulnerability chaining is a dependency-resolution problem. The execution of an exploit changes the state of the system, granting the attacker new privileges or capabilities. If these new capabilities match the prerequisites required to execute a subsequent exploit, a link is formed.

The authors of RangeFactory: Scalable Construction of Multi-Hop Cyber Ranges utilize this exact mechanism to automatically build complex cyber ranges. By matching the output capabilities of one vulnerability module to the input requirements of subsequent stages within a network topology, they programmatically generate valid, multi-hop attack paths.

This lineage can also be traced through the relationships between software weaknesses themselves. In A Proposed Approach to Integrate Application Security Vulnerability Data with Incidence Response Systems, Santanam Kasturi et al. map the hierarchical connections (such as parent-child or peer relationships) between Common Weakness Enumerations (CWEs). This lineage-based approach reveals how low-level code flaws serve as necessary prerequisites for high-level, critical exploits.

To model how these conditions combine, researchers often use logical frameworks. For example, Xiaorong Lyu et al. in Bayesian Network Based C2P Risk Assessment for Cyber-Physical Systems connect vulnerabilities using logic gates (AND/OR). This defines whether an attacker needs to exploit a specific combination of multiple security failures, or just a single vulnerability, to advance to the next stage of the architecture.

Algorithmic Pathfinding and Threat Reasoning

Once a system is mapped as a graph, discovering exploit chains becomes a matter of graph traversal and reasoning.

A straightforward approach applies shortest-path algorithms to find the most probable intrusion trajectories. As Zhengwei Qu et al. demonstrate in Electric power cyber-physical systems vulnerability assessment under cyber attack, if edge weights are configured to represent the ease of exploitation and system-wide impact, pathfinding algorithms can pinpoint the exact sequence of node compromises an attacker is most likely to follow to reach critical targets.

For highly complex or unstructured security data, researchers turn to machine learning and knowledge graphs:

Shifting Left and Strategic Defense

Understanding security through the lens of graph reachability fundamentally changes how systems are defended. Instead of attempting the impossible task of patching every single vulnerability, defenders can focus on breaking the chains.

In large organizational networks, this means identifying and blocking critical bottlenecks. The algorithms developed by Mingyu Guo et al. in Scalable Edge Blocking Algorithms for Defending Active Directory Style Attack Graphs calculate the optimal, minimal set of user permissions to revoke in order to completely sever lateral movement pathways to high-value targets.

Furthermore, this graph-based perspective allows security to "shift left" into the earliest stages of system design. By representing system architectures as graphs of interconnected assets before any code is written, engineers can run algorithmic pathfinding to uncover hidden risks.

As Georgios Bakirtzis et al. demonstrate with their tool CYBOK in Data Driven Vulnerability Exploration for Design Phase System Analysis, modeling component interdependencies and communication flows early on allows designers to visualize how an attacker might pivot from a non-critical entry point to a high-value target. This enables teams to alter the system's topology and eliminate dangerous exploit chains before they are ever baked into production software.

Key Foundational Work

Computational Vulnerability Analysis for Information Survivability (2002) — contributed 3 concept elements to this direction.
Developing and Managing Software Components in an Ontology-based Application Server (2004) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_isolated_vulnerability_assessment_b8bd0a7b,
  title = {isolated vulnerability assessment},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/isolated-vulnerability-assessment/rdr_b8bd0a7bdb24490dacb039ecdc4fb54c},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_isolated_vulnerability_assessment_b8bd0a7b_v1,
  title = {isolated vulnerability assessment},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/isolated-vulnerability-assessment/rdr_b8bd0a7bdb24490dacb039ecdc4fb54c/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake