Debt Collector Series: §7 AttackGraph — Formal Exploit Chain Model

by

§7 AttackGraph — Formal Exploit Chain Model

Layer §6 of the Debt Collector Stack

Author: Shrikant Bhosale (@debtcollector21)

7.1 What It Is

AttackGraph is a formal mathematical model of exploit chains as a directed graph G = (V, E):

  • V = StateNode: A security-relevant program state (e.g., recon_info, heap_corruption, code_execution)
  • E = ExploitStep: A finding that transitions from one state to another (e.g., a buffer overflow transitions from recon_info to heap_corruption)

This is BloodHound for code — a graph model that enables pathfinding through vulnerability space.

7.2 Formal Definition

7.2.1 State Nodes

@dataclass
class StateNode:
    state: str        # e.g., "recon_info", "heap_corruption", "code_execution"
    category: str     # "recon", "corruption", "execution"
    severity: str     # "info", "low", "medium", "high", "critical"

Built-in states:

State Category Severity Description
no_access initial info No access to the target
recon_info recon info Information gathering (addresses, layout, data)
foothold access medium Initial code execution (sandboxed/user-level)
code_execution control critical Arbitrary code execution
data_exfil exfil high Data extraction
heap_corruption corruption critical Heap metadata/non-metadata corruption
stack_corruption corruption critical Stack buffer overflow
use_after_free corruption critical UAF condition established
type_confusion corruption high Type confusion achieved
info_leak recon high Sensitive data leaked
privilege_escalation access critical Privilege boundary crossed
dos impact medium Denial of service
crash impact low Program crash (no exploitation)

7.2.2 Exploit Step Edges

@dataclass
class ExploitStep:
    id: str                     # Finding ID (VMF-xxx or FUZZ-xxx)
    source: str                 # file:line
    vulnerability: str          # Type (heap_buffer_overflow, null_deref, etc.)
    cvss: float                 # CVSS v3.1 base score
    preconditions: set[str]     # Required postconditions from previous steps
    postconditions: set[str]    # Enabled states after this step
    metadata: dict              # Source, crash type, ASAN output, etc.

7.2.3 Node Identity

Critical design decision: Nodes are identified by STATE VALUE, not by file:line.

This means findings at different locations that produce the same state transition merge into a single abstract graph node. For example:

  • scanner.cc:342 memcpy OOB → heap_corruption
  • decoder.cc:88 section count overflow → heap_corruption

Both findings map to the SAME transition recon_info → heap_corruption because they have the same pre/post conditions. This merging is what enables multi-step pathfinding across disconnected files.

7.3 Pathfinding

AttackGraph implements 5 pathfinding strategies:

7.3.1 Shortest Path (Dijkstra, Unweighted)

def shortest_path(graph: AttackGraph, start: str, end: str) -> list[ExploitStep]:
    """
    Minimum number of steps from start to end state.

    Uses Dijkstra with unit weights (each edge = 1 step).
    Returns the shortest path in terms of step count.
    """
    return nx.shortest_path(graph.digraph, source=start, target=end)

Use case: “What’s the fastest way from no_access to code_execution?”

7.3.2 Fastest Path (Weighted by Complexity)

def fastest_path(graph: AttackGraph, start: str, end: str) -> list[ExploitStep]:
    """
    Minimum complexity path from start to end.

    Edge weight = 1 / (cvss * complexity_factor)
    Higher CVSS = lower weight = preferred path.
    Complexity factor penalizes steps that require:
    - Physical access (×2)
    - Admin privileges (×3)
    - Specific hardware (×4)
    """
    for edge in graph.digraph.edges(data=True):
        step = edge[2]['step']
        weight = 1.0 / (step.cvss * complexity_factor(step))
        graph.digraph[edge[0]][edge[1]]['weight'] = weight

    return nx.shortest_path(
        graph.digraph, source=start, target=end, weight='weight'
    )

Use case: “What’s the easiest path to exploitation?”

7.3.3 Stealthiest Path (Maximin Stealth)

def stealthiest_path(graph: AttackGraph, start: str, end: str) -> list[ExploitStep]:
    """
    Path that maximizes the minimum stealth factor.

    Stealth factor ∈ [0, 1] based on:
    - Crash/noise generation (noisy = 0.2, quiet = 0.9)
    - Logging presence (logged = 0.3, no log = 0.8)
    - Probability of detection (high = 0.1, low = 0.9)

    Uses maximin pathfinding: maximize the minimum stealth
    factor along the path.
    """
    paths = list(nx.all_simple_paths(graph.digraph, source=start, target=end))

    best_path = None
    best_stealth = 0

    for path in paths:
        min_stealth = min(
            graph.get_stealth(edge)
            for edge in zip(path[:-1], path[1:])
        )
        if min_stealth > best_stealth:
            best_stealth = min_stealth
            best_path = path

    return best_path

Use case: “How do I exploit this without getting caught?”

7.3.4 Most Reliable Path (Max Probability Product)

def most_reliable_path(graph: AttackGraph, start: str, end: str) -> list[ExploitStep]:
    """
    Path with highest overall success probability.

    Each edge has a success probability (0-1) derived from:
    - CVSS exploitability subscore
    - Fuzzer crash rate
    - PoC verification status
    - D_e of the target function

    Total = product of all edge probabilities along the path.
    """
    for edge in graph.digraph.edges(data=True):
        step = edge[2]['step']
        prob = step.success_probability()
        # Use negative log for shortest-path
        graph.digraph[edge[0]][edge[1]]['weight'] = -log(prob)

    return nx.shortest_path(
        graph.digraph, source=start, target=end, weight='weight'
    )

Use case: “Which chain am I most confident will work in practice?”

7.3.5 K-Shortest Paths (Top-K by Complexity)

def k_shortest_paths(graph: AttackGraph, start: str, end: str, k: int) -> list[list[ExploitStep]]:
    """
    Top-k paths ordered by complexity (ascending).

    Uses Yen's algorithm for k-shortest simple paths.
    Starts with shortest (Dijkstra), then finds alternatives.
    """
    return list(nx.shortest_simple_paths(
        graph.digraph, source=start, target=end, weight='complexity'
    )[:k])

Use case: “Show me the 5 most practical exploit chains.”

7.4 Bottleneck Analysis

AttackGraph uses betweenness centrality to identify critical nodes:

def bottleneck_analysis(graph: AttackGraph) -> dict[str, float]:
    """
    Compute betweenness centrality for each state node.

    Betweenness = fraction of all shortest paths that pass
    through this node. High betweenness = bottleneck.

    A single well-placed fix at a bottleneck node can
    collapse entire classes of attack paths.
    """
    return nx.betweenness_centrality(graph.digraph, normalized=True)

Empirical example ([Vendor] analysis):

State Node Betweenness Bottleneck?
heap_corruption 0.42 YES — 42% of all paths pass through it
recon_info 0.18 No
type_confusion 0.31 Moderate
code_execution 0.09 No (sink, not transit)

Interpretation: Fixing heap corruption (e.g., adding bounds checks to the Wasm decoder) would collapse 42% of all attack paths. This is the highest-leverage mitigation point.

7.5 Structure Classification

Every chain is classified by its graph structure:

Structure Pattern Example Mitigation Strategy
Linear A → B → C → D OOB → UAF → code exec Break any single link
Branching A → {B, C} → D Info leak enables 2 paths Collapse B and C
Looping A → B → A State corruption loop Fix invariant
Kill Chain Recon → Weaponize → Deliver → Exploit → Control → Exfil Full MITRE ATT&CK Detection at each phase
Singleton A (isolated) Info leak, No chain path Low priority

7.6 Chain Templates

AttackGraph supports 4 real-world chain templates:

Template Steps Example
Web-to-Full-Compromise SSRF → internal_recon → cred_access → priv_esc → data_exfil Server-side attack
Supply Chain dep_confusion → build_inject → signed_binary → widespread_install Dependency attack
Browser-to-Kernel [Vendor]_oob → sandbox_escape → kernel_exploit → persistence Browser pwn2own
Memory Corruption info_leak → heap_spray → uaf → code_exec Classic binary exploitation

7.7 Chain Validation

Each chain must satisfy the chain validity condition:

def chain_valid(chains: list[ExploitStep]) -> bool:
    """
    Every step's preconditions must be satisfied by the
    UNION of all preceding steps' postconditions.

    This uses abstract union (not sequential), because
    the attacker can choose which postconditions are active
    at each stage.
    """
    accumulated_postconditions = set()

    for step in chains:
        if not step.preconditions.issubset(accumulated_postconditions):
            return False  # Missing prerequisite
        accumulated_postconditions |= step.postconditions

    return True

7.8 CVSS Chain Multiplier

When findings are chained, the CVSS is adjusted:

def chain_cvss(chains: list[ExploitStep]) -> float:
    """
    Chain CVSS = max(base_cvss) × chain_multiplier

    Chain multiplier:
    - 1 chain crossing 2 trust boundaries: ×1.3
    - 1 chain with 3+ steps: ×1.15
    - Cross-language chain: ×1.1
    - Multiple chains converging: ×1.2
    """
    base = max(step.cvss for step in chains)
    multiplier = 1.0

    trust_boundaries = count_trust_boundaries(chains)
    if trust_boundaries >= 2:
        multiplier = max(multiplier, 1.3)

    if len(chains) >= 3:
        multiplier = max(multiplier, 1.15)

    languages = {step.metadata.get('language') for step in chains}
    if len(languages) > 1:
        multiplier = max(multiplier, 1.1)

    return round(min(10.0, base * multiplier), 1)

7.9 Integration with Feynman Gate

Every chain passes through the Feynman Gate before scoring:

def feynman_validate_chain(chains: list[ExploitStep]) -> ChainVerdict:
    """
    Feynman Gate for chains:
    - Q1: Does every step have a PoC? (must all pass)
    - Q2: Are all pre/post conditions verified? (chain_valid)
    - Q3: What would disprove this chain?
    - Q4: Is the chain realistic in practice (not just theoretical)?
    """
    # Q1: All steps need PoC
    all_poc = all(step.metadata.get("poc_exists", False) for step in chains)
    if not all_poc:
        return ChainVerdict.FAIL

    # Q2: Pre/post condition chain
    if not chain_valid(chains):
        return ChainVerdict.FAIL

    # Q3: Disproof test
    disproof = identify_mitigations(chains)
    if len(disproof) >= 2:  # Two independent mitigations block the chain
        return ChainVerdict.FAIL

    # Q4: Realism check
    realism = assess_chain_realism(chains)
    if realism < 0.5:
        return ChainVerdict.WARN

    return ChainVerdict.PASS

7.10 Empirical Results

Target Chains Top CVSS Bottleneck Structure
[Vendor] (Parcel) 4 8.8 heap_corruption (0.38) Linear + Branching
[Vendor] (4 subsystems) 3 8.0 heap_corruption (0.42) Cross-subsystem Linear
Chrome Mojo 2 8.3 type_confusion (0.31) Linear
Cash App (Java) 3 8.0 resource_leak (0.28) Linear
[Vendor] (14 apps) 1 7.5 oob_access (0.35) Linear
Wasm Fuzzer (KU-integrated) 1 8.65 heap_corruption (0.42) Linear

7.11 CLI Usage

# Show AttackGraph summary
vmf report --graph

# Find paths from start to end
vmf chain --from recon_info --to code_execution

# Find fastest path
vmf chain --from no_access --to data_exfil --strategy fastest

# K shortest paths
vmf chain --from no_access --to code_execution --strategy k_shortest --k 5

# Bottleneck analysis
vmf report --bottlenecks

# Chain validation
vmf chain --validate

Leave a Comment