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

What it is

ChainGraph is a pattern from an independent researcher (arXiv 2610.20902v1) for giving an unmodified coding agent (Claude Code or Codex) a persistent attack graph. The graph lives in Neo4j 5.26 with GDS 2.13 and is reached over MCP, with no custom harness. The paper's claim is that "AI can't chain exploitation" describes a flat context window, not the model.

How it works

State is split into two stores:

• Documentary memory: JSON findings and Markdown notes on disk. Raw tool output is saved as an evidence receipt and hashed with SHA-256.
• Reasoning memory: the Neo4j graph. It stores no raw evidence, only nodes carrying the receipt's hash and a path pointer back to the file. It can be dropped and rebuilt from the receipts.

Edge types are ENABLES, REQUIRES, YIELDS, ESCALATES_TO and PIVOTS_TO. Five operator questions become reusable Cypher/GDS queries:

1. Next-step inference.
2. Entry-to-crown-jewel pathing, using shortestPath against a declared Objective node.
3. Combined-severity promotion, via a "chain severity" score separate from per-finding severity.
4. Evidence provenance.
5. Chokepoint identification, using betweenness centrality.

flowchart LR
    T[Target output<br/>untrusted] --> A[Agent]
    A -->|MCP read/write tools| G[(Neo4j graph)]
    A -->|PostToolUse hook| R[Hashed receipts on disk]
    G -. SHA-256 + path pointer .-> R

Preconditions / Affected

• An authorized engagement. The threat model treats tool output and graph contents as untrusted data, because of indirect prompt injection from the target.
• Neo4j bound to loopback, treated as a reasoning store and not a target asset.
• The agent must populate the graph correctly from raw output. The paper puts the reliability of that step out of scope.

What to do

The paper says it gives a full recipe: Docker, schema, queries, MCP wiring for both Claude Code and Codex, permission settings, and a PostToolUse evidence-capture hook. It enforces read/write tool separation at the protocol boundary. That configuration is in later sections not included in the text I had, so I can't reproduce commands here. Read the paper before copying anything.

Results on the synthetic GOAD-style multi-forest AD lab:

• Three Medium findings are promoted to Critical once their path to the forest root is materialized.
• Betweenness centrality ranks the PKINIT authentication and DCSync steps as the top chain break-points. These are the candidates for remediation.
• One eight-hop path returned by a single shortestPath query cut the reasoning payload by about 98%, measured with a character-based token proxy.

Caveats

• The authors call every number an illustrative single-run measurement on a synthetic lab, not a controlled benchmark.
• The 98% figure is a character-count proxy, not measured model tokens or task success.
• The "deterministic chaining" claim applies once the graph is correctly populated. Whether the agent builds accurate nodes and edges is untested here.
• The commercial-product comparisons (Yaga, NodeZero) rely on vendor claims or third-party use, not the authors' own measurements.
• The paper discusses dual-use risk from giving an autonomous agent a persistent attack graph, but that section was beyond the fetched text.