💻 computer science

MemLineage: Lineage-Guided Enforcement for LLM Agent Memory

MemLineage is a cryptographic defense system for LLM agents that prevents memory poisoning attacks by tracking the provenance and derivation lineage of memory entries, ensuring that sensitive actions are only authorized when their justification does not descend from untrusted sources.

Original authors: Ciyan Ouyang, Rui Hou

Published 2026-05-15

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Ciyan Ouyang, Rui Hou

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine an AI agent as a very helpful, but slightly gullible, personal assistant who keeps a notebook (memory) to remember your preferences, past conversations, and tasks. This notebook is powerful because it lets the assistant connect the dots over days or weeks. However, this notebook is also the assistant's biggest weakness.

MemLineage is a new security system designed to protect this notebook from being tricked by a clever hacker.

Here is how the paper explains the problem and the solution, using simple analogies:

The Problem: The "Fake Receipt" Scam

Currently, if a hacker can sneak a malicious instruction into the assistant's notebook, the assistant might obey it later, even if the instruction is dangerous (like "transfer money to a stranger").

The paper highlights a specific, sneaky trick called "Sleeper via Derivation."

The Old Way: A hacker writes a note saying "Steal money" and hides it in the notebook. A simple security guard (a "signature-only" defense) checks the note, sees it wasn't written by the user, and blocks it. Easy.
The New Trick: The hacker doesn't write the note directly. Instead, they plant a vague, harmless-sounding clue in a website the assistant visits (e.g., a story about a "secret bank account").
The assistant reads the story, summarizes it, and writes a new, clean-looking note in its own handwriting: "I found a reference to a secret bank account."
Because the note is now written in the assistant's own handwriting, a simple security guard thinks, "Oh, this is safe! It came from us!" and lets it stay in the notebook.
Later, the hacker asks a question that triggers this note, and the assistant, thinking it's a valid memory, executes the dangerous command.

The paper calls this "Memory Laundering": washing dirty, untrusted information until it looks clean and trustworthy.

The Solution: MemLineage (The "Chain of Custody" Tracker)

MemLineage treats the assistant's memory like a high-security evidence locker rather than just a notebook. It adds two main layers of protection:

1. The Digital Fingerprint (Cryptographic Provenance)

Every single note in the notebook gets a unique, unforgeable digital fingerprint (a cryptographic signature). This proves exactly who wrote it. If a note was written by an untrusted source (like a random website), it gets a "Red Flag" tag immediately.

2. The Family Tree (Lineage)

This is the paper's big innovation. MemLineage doesn't just look at who wrote the note; it looks at where the information came from.

Imagine every note has a "Family Tree" attached to it.
If a note is a summary of a previous note, the system draws a line connecting them.
The system asks: "Did this clean-looking note descend from a 'Red Flag' source?"
The Rule: If a note is a "child" of a "Red Flag" source, and the connection is strong enough, the child note inherits the Red Flag, even if it was written by the assistant.

How It Stops the Attack

When the assistant wants to perform a sensitive action (like sending money), a Gatekeeper checks the memory:

Check the Signature: Did the user or a trusted tool write this?
Check the Family Tree: Does this note have any ancestors that were untrusted?
The Verdict: If the note's "family tree" leads back to a hacker's website, the Gatekeeper says, "No." It blocks the action, even though the note looks perfectly normal on the surface.

The "Magic" Features

The paper claims MemLineage is special because:

It's Invisible: It adds almost no delay (less than a millisecond) to the assistant's thinking process. It's like adding a security check that happens so fast you don't even notice it.
It's Smart: It doesn't just block everything from untrusted sources. It allows the assistant to use that information for harmless things (like answering a trivia question) but blocks it from triggering dangerous actions (like transferring funds).
It Survives Time: Even if the hacker's original note is deleted or buried deep in the history, the "Red Flag" stays attached to the derived notes forever, preventing the "Sleeper" attack from waking up later.

The Results

The authors tested this system against three types of hacker attacks in a controlled, computer-simulated environment.

Without MemLineage: The hackers succeeded 100% of the time.
With a Basic Security Guard (Signatures only): The hackers succeeded 100% of the time on the "Sleeper" attack because the notes looked clean.
With MemLineage: The hackers succeeded 0% of the time. The system caught every attempt, including the sneaky "laundered" ones, without slowing the assistant down or blocking harmless tasks.

In short, MemLineage ensures that an AI assistant can remember things safely, knowing that even if a piece of information looks clean, it won't let that information cause harm if it has a "dirty" history.

Technical Summary: MemLineage

Problem Statement

Modern LLM agents rely on persistent memory stores to accumulate chat logs, tool returns, and derived observations across user sessions. While this memory enables multi-step workflows, it has become a critical attack surface. Recent research (e.g., AgentPoison, MINJA, MemoryGraft, Zombie Agents) demonstrates that adversaries can inject malicious content into an agent's memory, which may lie dormant across sessions and later re-emerge as an instruction to trigger sensitive actions.

The core enforcement gap identified is that existing defenses fail to handle memory laundering. A sophisticated adversary can plant "ingredients" in untrusted sources, allowing the agent's normal retrieval and summarization loop to generate a fresh, derived entry. Because this derived entry is authored by the agent itself, it carries a valid cryptographic signature, making it indistinguishable from benign content to signature-only defenses. Consequently, the agent may later retrieve this "laundered" entry and execute sensitive actions (e.g., financial transfers) based on untrusted ancestry, breaking the chain of custody.

Current solutions suffer from specific limitations:

Signature-only layers verify the writer but cannot trace derivation history.
IFC-based planners (e.g., Fides) enforce labels during planning but lose them across LLM derivation steps.
Retrieval filters (e.g., RAGPart) cannot distinguish a benign summary from a laundered payload if both arrive via an authenticated principal.
Coarse defenses (e.g., Memory Sandbox) often block all recall after exposure, sacrificing utility.

Methodology: MemLineage Design

MemLineage addresses this by treating memory security as a chain-of-custody problem rather than a filtering problem. It attaches cryptographic provenance and a weighted derivation lineage to every memory entry. The system is built around six modules:

Provenance Metadata (M1): Every entry is a ProvEntry record containing the writer principal, source hash, context hash, and a list of parent entries with attribution weights.
Cryptographic Binding (M2): Entries are signed using Ed25519 keys per principal. The signature covers a canonical CBOR encoding of all fields except the signature itself.
Append-Only Log (M3): An RFC 6962-style Merkle log records entry hashes. Deletion is handled via signed "tombstone" markers to prevent history rewriting.
Lineage DAG (M4): A directed acyclic graph where edges represent LLM-mediated derivation. Each edge $(p, c)$ $(p, c)$ has a weight $w(p, c) \in [0, 1]$ $w (p, c) \in [0, 1]$ determined by an attribution algorithm.
- Propagation Rule: Trust is propagated via a max-of-strong-edges rule. An entry $c$ inherits the trust level of its parent $p$ if $w(p, c) > \tau$ (a declassification threshold).
- Untrusted-Path Persistence (Theorem 1): If a path exists from an "External" ancestor to a current entry where every edge weight exceeds $\tau$ , the current entry is labeled "Derived-Untrusted."
Verifier-Aware Retrieval (M5): Before an entry is spliced into the LLM prompt, M5 verifies signatures, inclusion proofs, and renders the entry with a structural trust label (e.g., [trust=DERIVED_UNTRUSTED]).
Sensitive-Action Gate (M6): Before dispatching a tool call (especially to sensitive sinks like file writes or payments), M6 inspects the active prompt. If the justification for a parameter descends from a "Derived-Untrusted" or "External" ancestor, the call is denied. M6 also supports Authority Repair, where it can surgically replace attacker-sourced parameters with values from trusted provenance.

The system supports three attribution algorithms:

Coarse: Binary weight (1.0) if a parent was in the retrieval context.
LmSelfEval: A secondary LLM judge scores semantic influence (hardened against prompt injection via JSON envelopes).
AttnAttr: White-box attention analysis (requires open-weight models).

Key Contributions

Lineage-Stress Workload: The paper introduces a "sleeper-via-derivation" attack model. Unlike direct injection, this workload plants ingredients in untrusted sources, forcing the LLM to derive a malicious payload as a fresh, signed entry. This separates signature-only defenses from lineage-aware ones.
Formal Propagation Rule: The design formalizes the Untrusted-Path Persistence theorem, proving that if every edge in a derivation chain is "strong" (above threshold $\tau$ ), the untrusted label propagates to the chain tip.
Attribution Algorithms & Trade-offs: The paper evaluates three attribution strategies and quantifies the interaction between the lineage threshold ( $\tau$ ) and chain length ( $K$ ). It demonstrates that a single-shot $\tau$ measurement is insufficient; deeper chains require lower thresholds to maintain safety under decaying attribution confidence.
End-to-End Evaluation Harness: A deterministic, reproducible harness is provided that pins attacker behavior and avoids real LLM API calls for core metrics. It produces byte-equal CI-verified artifacts for Attack Success Rate (ASR), utility baselines, and lineage ablations.

Results

The evaluation compares three configurations: no_defense, sig_only_baseline (signatures + Merkle log, no lineage), and MemLineage (full stack).

Attack Success Rate (ASR):
- AgentPoison (Trigger-bound): sig_only_baseline and MemLineage both achieve 0.00 ASR (signatures block untrusted writers).
- MemoryGraft (Retrieval poisoning): sig_only_baseline fails (1.00 ASR) because entries are signed by the agent. MemLineage achieves 0.00 ASR by tracing the lineage to an external ancestor.
- Sleeper-via-Derivation: sig_only_baseline fails (1.00 ASR) as the derived entry is validly signed. MemLineage achieves 0.00 ASR by propagating the untrusted label through the derivation chain.
- Conclusion: MemLineage is the only configuration to drive ASR to zero across all three attack families.
Performance:
- The per-operation overhead is sub-millisecond. The write hot path (including signing and Merkle logging) averages ~214 µs, and verification is ~82 µs. This is well below the noise floor of typical LLM API calls.
Utility (False Positives):
- On benign workflows, MemLineage achieves 1.00 legitimate dispatch rate (zero false positives). It successfully allows derived-trusted chains and non-sensitive recall of external content.
- Authority Repair: In AgentDojo banking scenarios, MemLineage with authority repair blocks 100% of attacks while recovering utility on 5/6 pairs, outperforming simple denial or retry strategies.
Threshold Sensitivity:
- The $\tau \times K$ ablation shows that for decaying attribution weights (e.g., $w_0=0.9, d=0.7$ ), a deployment allowing $K=5$ hops requires $\tau \le 0.10$ , whereas a $K=1$ measurement might suggest $\tau \le 0.30$ .

Significance and Claims

The paper claims that MemLineage provides a fine-grained enforcement primitive that preserves useful long-term memory while preventing untrusted ancestry from authorizing sensitive actions.

Differentiation: Unlike coarse defenses that remove recall entirely, MemLineage maintains the utility of derived memories while strictly gating sensitive actions based on provenance.
Completeness: It is the only system evaluated that jointly covers four dimensions: cryptographic integrity of the trust label, lineage attribution across LLM derivation, cross-session persistence of the label, and coverage of agent-derived entries.
Modesty: The authors acknowledge that the system relies on the trustworthiness of the LLM inference weights (it cannot detect backdoors in the model itself) and that the strongest attribution algorithm (AttnAttr) requires open-weight models. The "no-strong-parent" fallback defaults to "Trusted," which could be exploited if an adversary suppresses all attribution edges below $\tau$ , though JSON-envelope hardening mitigates prompt injection risks.

The paper concludes that MemLineage shifts the defense paradigm from "filtering content" to "enforcing chain of custody," offering a viable path for secure, persistent LLM agents.