Most vulnerability scanners treat each finding as an island. Finding A has CVSS 6.5. Finding B has CVSS 4.3. They’re filed, triaged, and forgotten as separate items.
This misses the most important question in exploit development: can you chain them?
A CVSS 4.3 info leak followed by a CVSS 6.5 use-after-free can produce a CVSS 9.3 sandbox escape. The chain is worth more than the sum of its parts. But no traditional scanner models this.
I built AttackGraph — a formal graph-theoretic model that transforms vulnerability analysis into a pathfinding problem.
The Formal Model
An AttackGraph is a directed graph G = (V, E) where:
- V = State nodes — security states like
no_access,recon,foothold,code_exec,data_exfil - E = Exploit steps — individual vulnerability findings that transition the system from one state to another
Each exploit step has:
- Preconditions: what must be true before this step works
- Postconditions: what becomes true after
- Layer complexity: how hard is this step, factoring precision, entropy, and chain depth
- Curvature κ: how confident are we this finding is real
A chain is valid only if each step’s preconditions are satisfied by the union of all previous steps’ postconditions.
Pathfinding Through Vulnerabilities
Once the graph is built, exploit chain discovery becomes a graph search problem. AttackGraph supports five strategies:
| Strategy | Algorithm | Use Case |
|---|---|---|
| Shortest path | Dijkstra (unweighted) | Minimum hop count to compromise |
| Fastest path | Weighted by complexity | Least effort to compromise |
| Stealthiest path | Maximin stealth factor | Hardest to detect chain |
| Most reliable | Highest probability product | Best chance of working chain |
| All paths | BFS enumeration | Complete attack surface map |
Real Example: The Android Binder Chain Lattice
From our Android AOSP research, three findings in Parcel.cpp form a chain lattice. Here’s how AttackGraph models them:
| Finding | Preconditions | Postconditions | κ |
|---|---|---|---|
| A01: Parcel capacity/size gap | Attacker controls IPC buffer | OOB write at controlled offset | 0.12 |
| A02: Raw pointer in objects[] | OOB write achieved | Heap metadata corruption | 0.15 |
| A03: Resize path FD confusion | Heap corrupted | Arbitrary close/use of FD | 0.10 |
The chain A01 → A02 → A03 has complexity score 0.083 (highly constrained — needs ASLR defeat + info leak). No single finding is exploitable alone. The chain exists only because the postconditions of each finding feed the preconditions of the next.
Bottleneck Analysis
AttackGraph computes betweenness centrality to identify the most critical findings. In a lattice of 118 chains found in Chrome’s Mojo IPC, one finding appeared in 89% of all chains: the nullptr validator in native_struct_serialization.cc. Fixing that single finding would break 89% of the exploit chains in the entire codebase.
This is the killer feature of AttackGraph. It doesn’t just tell you where the bugs are. It tells you which bugs matter most to an attacker — the ones that appear in the most paths to system compromise.
Chain Structure Classification
AttackGraph classifies each chain by its structure:
| Type | Description | Example |
|---|---|---|
| Linear | Single path, no branching | Classic stack overflow → ROP chain |
| Branching | Multiple paths to same goal | Info leak via timing OR via error message |
| Looping | Same findings reused in sequence | Spray → trigger → spray → trigger |
| Kill chain | Lockheed-Martin style multi-phase | Recon → weaponize → deliver → exploit |
| Singleton | Single finding, no chaining needed | Heartbleed — read more than requested |
Practical Implications
AttackGraph changes how you prioritize fixes. Instead of fixing bugs by CVSS score, you fix bugs by bottleneck centrality:
- Build the graph from your codebase’s VMF findings
- Rank findings by betweenness centrality (how many chains pass through each)
- Patch the top 10 bottlenecks
- Re-scan — the chain lattice should collapse
This is the first time exploit chain analysis has been automated as a graph search problem. It’s the difference between security as a list of CVEs and security as a topological map of your attack surface.
Up next: The Grand Unification: 5 Dimensions of Every Vulnerability →
Part of the Geometric Vulnerability Analysis series