When will I ever use this ? #2 Graph Theory in the Trenches: Memory Topology, Garbage Collection, and Use-After-Free Exploits
1 feb 2026
⚠️ Warning: This post is written purely for proactive cybersecurity education and awareness. Our goal is to make our systems safer by understanding how algorithms work and how vulnerabilities occur. Please do not use the concepts explained here for malicious purposes.
In school, graph theory and topology are often presented as abstract, almost childish exercises. You draw circles on a chalkboard, connect them with lines, and try to find a path that crosses every bridge exactly once without lifting your chalk. It feels like a connect-the-dots puzzle.
Here is the boring academic definition they force you to memorize:
Let G = (V, E) be a directed graph where V is a set of vertices (nodes) and E is a set of ordered pairs of vertices, called directed edges. Topology is the mathematical study of the properties that are preserved through continuous deformations, twistings, and stretchings of these objects.
What they don't tell you is that this exact mathematical model is the only thing keeping your computer from collapsing into a chaotic void of corrupted memory.
In the real world of operating systems, Garbage Collection (GC), and cybersecurity, G = (V, E) is the map of your application's RAM.
Memory as a Directed Graph
When a program runs, it requests memory from the heap. Every time an object is instantiated, the memory allocator creates a vertex (v \in V). Every time an object holds a pointer or reference to another object, the compiler creates a directed edge (e \in E)
When you look at memory this way, fundamental computer science concepts become pure graph theory:
Garbage Collection (Mark-and-Sweep): This is literally just a Breadth-First Search (BFS) or Depth-First Search (DFS) graph traversal algorithm. The GC starts at the "root" nodes (global variables, active stack frames) and traverses every edge. Any vertex that cannot be reached is considered mathematically isolated from the topology. It is "garbage" and its memory is reclaimed.
Memory Leaks: A memory leak is a disconnected subgraph. A cluster of vertices that reference each other, but have no incoming edges from the root topology.
Race Conditions: Imagine Thread A and Thread B operating on the same graph simultaneously. Thread A is traversing an edge from Vertex 1 to Vertex 2. At that exact microsecond, Thread B deletes Vertex 2. The topology shatters.
This leads us to one of the most devastating cybersecurity vulnerabilities in existence: Use-After-Free (UAF).
The Topology of an Exploit: Use-After-Free
A Use-After-Free vulnerability occurs when a vertex is destroyed (freed), but another vertex in the graph still retains a directed edge (pointer) pointing to that now-empty memory address. This is called a dangling pointer.
To a hacker, a broken topology is an invitation. If they can force the memory allocator to create a new malicious vertex at the exact memory address where the old vertex used to be, the dangling edge will now point to their payload. When the program traverses that edge, it expects a trusted object, but executes the attacker's data instead.
Let's look at how this abstract graph manipulation happens in raw C++.
C++ Code Example: Weaponizing a Broken Edge
In this example, we have a system that uses an AdminSession. We will artificially create a broken edge, simulate an attacker reallocating that memory space (Heap Grooming), and trigger a Use-After-Free.
**************************************************************************************************************************
#include <iostream>
#include <cstring>
// Vertex Type A: A legitimate object in our graph
class AdminSession {
public:
// Virtual functions rely on a vtable (an array of function pointers).
// Traversing to this object and calling authenticate() means the CPU
// will look up the function address in the vtable.
virtual void authenticate() {
std::cout << "[SYSTEM] Admin access granted. Proceeding to dashboard...\n";
}
};
// Vertex Type B: The Attacker's Payload
class MaliciousData {
public:
uint64_t fake_vtable_pointer; // Used to hijack the execution flow
MaliciousData() {
// In a real exploit, the attacker overwrites the vtable pointer
// to point to their own shellcode. Here, we just corrupt the memory.
fake_vtable_pointer = 0xDEADBEEFCAFEBABE;
std::cout << "[ATTACKER] Malicious payload injected into the heap.\n";
}
};
int main() {
std::cout << "--- Graph Topology Initialized ---\n";
// 1. Create a vertex and a directed edge (pointer) to it
AdminSession* session_edge = new AdminSession();
std::cout << "1. AdminSession allocated at: " << session_edge << "\n";
// 2. BREAKING THE GRAPH (The Vulnerability)
// The vertex is destroyed, returning the memory to the OS.
// HOWEVER, the pointer 'session_edge' is NOT set to nullptr.
// It is now a dangling edge pointing into the void.
delete session_edge;
std::cout << "2. AdminSession freed. 'session_edge' is now a dangling pointer.\n";
// 3. HEAP GROOMING (The Exploit)
// The attacker forces the program to allocate an object of the exact same size.
// Low-level allocators (like glibc's ptmalloc) will optimize by reusing
// the most recently freed block. The attacker seamlessly replaces the vertex.
MaliciousData* attacker_vertex = new MaliciousData();
std::cout << "3. MaliciousData allocated at: " << attacker_vertex << "\n";
// 4. USE-AFTER-FREE (The Execution)
// The system blindly traverses the broken edge. It believes it is talking
// to an AdminSession, so it tries to resolve the virtual function.
// Instead, it hits the 0xDEADBEEFCAFEBABE payload.
std::cout << "4. System traverses dangling edge: session_edge->authenticate()\n";
// WARNING: This line causes Undefined Behavior.
// In a compiled environment, this attempts to jump the Instruction Pointer (RIP)
// to 0xDEADBEEFCAFEBABE, resulting in a Segmentation Fault, or if properly
// crafted, Remote Code Execution (RCE).
session_edge->authenticate();
return 0;
}
**************************************************************************************************************************
The Breakdown
When delete session_edge is called, the memory block is marked as free, but the variable session_edge still holds the literal hexadecimal memory address (the edge still exists).
Because MaliciousData is likely the exact same byte size as AdminSession (just a single pointer size for the vtable), the OS allocator efficiently places attacker_vertex exactly where the old object used to be.
When the program executes session_edge->authenticate(), it traverses the graph following the dangling pointer. The CPU looks at the memory, grabs the first 8 bytes expecting a valid virtual method table, but instead grabs 0xDEADBEEFCAFEBABE. The program attempts to execute memory at that address. The topology has been successfully weaponized.
Graph theory isn't just about connecting dots; it is about guaranteeing that the bridges your software crosses don't lead into a minefield.