Thinking in Graphs: Neo4j-Backed Exploit-Chain Reasoning for LLM Penetration-Testing Agents

What it claims

ChainGraph argues that "LLMs can't chain exploits" describes the flat context window, not the model. Store the engagement as a Neo4j attack graph and chaining becomes a deterministic query. In the paper's running example, the chain is LLMNR capture → cracked domain-user hash → AD CS template allowing certificates for arbitrary principals → forged domain-admin certificate → PKINIT authentication → DCSync. A list-shaped report would show this as one Medium (LLMNR), one Medium (weak password), one High (the template) and two operational notes. In the graph it is one eight-hop path, returned by a single shortestPath query.

How it works

The design uses two kinds of memory:

• Documentary memory: each finding is a JSON document and narrative is Markdown. Every supporting observation is saved as an evidence receipt: raw tool output written to disk, hashed with SHA-256 and referenced by hash. This store is append-mostly and version-controlled, and it is the auditor's record.
• Reasoning memory: Neo4j holds the same entities as typed nodes. Edges carry pre/post-conditions: ENABLES, REQUIRES, YIELDS, ESCALATES_TO, PIVOTS_TO.
• Link between them: the graph never stores raw evidence, only the receipt hash and a path pointer. Editing a receipt breaks both its hash and its graph link. The graph is treated as disposable and can be dropped and rebuilt from the receipts.

flowchart LR
  T[Target tool output<br/>untrusted] --> H[PostToolUse hook]
  H --> R[Receipts on disk<br/>SHA-256]
  R -->|hash + pointer only| G[Neo4j graph]
  R -.rebuild.-> G
  A[Claude Code / Codex] -->|MCP read tools| G
  A -->|MCP write tools, gated| G
  O[Operator approval] --> A

The integration uses an unmodified Claude Code or Codex connected over MCP. Read and write tools are separated at the protocol boundary, and a PostToolUse hook captures evidence. Neo4j runs as a loopback-only store, and graph contents are treated as untrusted data because of the indirect-prompt-injection risk.

The authors position the work as BloodHound-style graph reasoning connected to a live agent, and as a commodity version of Incalmo's "state service."

Evidence

All results come from one synthetic multi-forest AD lab modeled on GOAD, running Neo4j 5.26 with GDS 2.13, single run:

• Severity promotion: three findings rated Medium in isolation become Critical once their path to the forest root exists in the graph.
• Chokepoints: GDS betweenness centrality ranks the PKINIT authentication and DCSync steps as the highest-value points to break the chain. This is the result most useful for remediation.
• Token savings: the ~98% payload reduction compares returning the one eight-hop path against re-feeding the raw engagement corpus. It is measured with a character-based token proxy, not a real tokenizer, and no task-accuracy comparison is given.

How to use it

The paper says it provides a complete reproducible configuration: Docker setup, schema, Cypher/GDS queries, MCP wiring for both agents, and the evidence hook. None of that material appears in the fetched text, so there are no commands or queries to reproduce here. Read the full paper's Section VIII for them.

Limits

• The authors state that the numbers are illustrative single-run measurements on a synthetic lab, not a benchmark.
• Graph population is untested. Whether a given model correctly turns raw tool output into nodes and edges is explicitly out of scope. The deterministic-chaining claim holds only after the graph is correctly populated.
• Also out of scope: unsupervised exploitation, exploit development and defense evasion. The design assumes an authorized operator approving gated actions.
• No comparison is made against flat-context agents (PentestGPT, Incalmo) on success rate. The commercial comparisons (Yaga, NodeZero) rest on vendor accounts.
• The fetched text ends partway through Section IV. The schema details, the chain-severity formula and the threats-to-validity section were not visible.