PaperlayerView exact revision on arXiv

Source-linked AI summary

MemLineage: Lineage-Guided Enforcement for LLM Agent Memory

Ciyan Ouyang, Rui Hou

arXiv:2605.14421v1cs.CRcs.AI

TL;DR

Persistent agent memory can preserve untrusted content that later justifies sensitive actions, especially after LLM-mediated laundering into authentic agent-written entries. MemLineage adds cryptographic provenance and derivation lineage with a sensitive-action gate, and in the reported evaluations it reaches zero ASR across the deterministic workloads and vulnerable-profile AgentDojo pairs. Its scope depends on trusted inference and deterministic measurements do not cover all adaptive or real-LLM behavior.

  • Problem

    Persistent memory can let untrusted content re-enter later sessions as instructions, creating the systems question of preserving useful recall without allowing that state to justify sensitive actions.

  • Method

    MemLineage combines signed Merkle-anchored provenance, a weighted derivation DAG with thresholded propagation, and a sensitive-action gate for ancestry-based enforcement.

  • Results

    MemLineage is the only tested configuration driving all three deterministic-harness ASR columns to zero, while all rows reach 0/6 strict AgentDojo ASR under the vulnerable tool-output profile.

  • Takeaways & Limitations

    The design preserves benign memory use while refusing sensitive actions whose active justification descends from untrusted ancestry.

  • Takeaways & Limitations

    The defense assumes trusted LLM inference and cannot detect semantically illegitimate derived entries produced by compromised model weights or endpoints.

Abstract

from arXiv · show

We introduce MemLineage, a defense for LLM agent memory that attaches both cryptographic provenance and LLM-mediated derivation lineage to every entry. Recent and concurrent work shows that untrusted content can be written into persistent agent state and re-enter later sessions as an instruction; the remaining systems question is how to preserve useful memory recall while preventing such state from justifying sensitive actions. MemLineage treats this as a chain-of-custody problem rather than a filtering problem. It is a six-module design around an RFC-6962 Merkle log over per-principal Ed25519-signed entries: a weighted derivation DAG records which retrieved entries influenced each new memory, and a max-of-strong-edges propagation rule makes Untrusted-Path Persistence hold for any chain whose attribution edges remain above threshold. The sensitive-action gate then refuses dispatches whose active justification descends from an external ancestor, while still allowing benign recall. We evaluate three defense cells against three memory-poisoning workloads on a deterministic mechanism-isolation harness; MemLineage is the only configuration in that harness that drives all three columns to zero ASR, while sub-millisecond per-operation overhead keeps it well below the noise floor of any LLM call. A Codex-backed AgentDojo bridge further separates strong-model behavior from defense-layer behavior: under an intentionally vulnerable tool-output profile, no-defense and signature-only baselines fail on all six banking pairs, while all MemLineage rows reduce strict AgentDojo ASR to zero. The core deterministic artifacts are byte-equal CI-verified; hosted-model AgentDojo and live-model sweeps are recorded as auditable logs rather than byte-pinned artifacts.

1 Introduction

Persistent agent memory enables multistep workflows but also creates an attack surface when untrusted content survives across sessions or is laundered through agent-written entries. MemLineage addresses this chain-of-custody problem with cryptographic provenance, derivation lineage, and sensitive-action enforcement.

  • Motivation: Persistent memory accumulates chat logs, documents, tool returns, and derived observations that later sessions can retrieve.This capability supports multistep workflows while creating an attack surface for persistent memory poisoning.
  • Limitations of existing defenses: Signature-only layers verify writer identity but do not recover what an entry was derived from.This leaves laundered entries that appear authentic to the principal unresolved.
  • Limitations of existing defenses: Retrieval filters cannot distinguish benign summaries from laundered payloads arriving through an authentic principal.Coarse defenses may work by removing recall or attenuating capabilities, but they lose fine-grained distinctions between useful and untrusted derived memories.
  • Approach: MemLineage attaches Ed25519 provenance anchored in an RFC-6962 Merkle log and a weighted DAG recording LLM-mediated derivation.Its max-of-strong-edges rule propagates untrusted ancestry to the chain tip, which the sensitive-action gate refuses.
  • Evaluation: MemLineage drives all three mechanism-isolation ASR columns to zero, while per-operation overhead remains sub-millisecond.The AgentDojo bridge reports 0/6 strict ASR for all MemLineage rows under the explicitly vulnerable tool-output profile.
  • Evaluation: The evaluation includes a lineage-stress workload that transforms untrusted content through LLM-mediated derivation into an authentic agent-written entry.The workload separates signature-only, coarse-taint, and lineage-aware defenses rather than claiming cross-session persistence itself is novel.

2 Threat Model

The threat model covers persistent memory poisoning in agents that retrieve stored entries and dispatch sensitive tools. It assumes attackers can control untrusted sources and legitimate write paths, but not host integrity, principal private keys, or the trusted inference path.

  • System model: The agent consists of a memory store, a retrieval surface, and a tool surface containing policy-sensitive functions.Sensitive tools include filesystem writes, financial transfers, outbound HTTP, and code execution.
  • Adversary capabilities: Attackers can control web pages, ingested documents, external-tool outputs, or upstream-agent messages that reach the agent.They may inject entries only through legitimate paths already permitted by the agent or host.
  • Attack patterns: Injected payloads may persist across sessions and re-enter memory through retrieval as sleeper patterns.The model also includes LLM-mediated laundering, where retrieved untrusted content becomes a fresh derived entry.
  • Trust boundaries: The adversary cannot modify the host, library, or out-of-memory state, forge protected principal signatures, or rewrite the inference path.The threat model nevertheless permits influence through memory contents and retrieved untrusted sources.
  • Security goals: MemLineage propagates Derived-Trusted or Derived-Untrusted labels from weighted parent edges above threshold τ.Its sensitive-action gate blocks dispatches whose justification violates the policy invariant.
  • Scope: Single-turn direct injection is treated as orthogonal and out of scope, while the defense addresses memory-backdoor, retrieval-poisoning, and sleeper-via-derivation families.The paper frames these families as the threat surface for persistent-memory enforcement.
  • Attack patterns: Sleeper-via-derivation produces an authentic agent-principal entry, which signature-only defenses cannot rule out.The adversary supplies ingredients through untrusted sources, and normal retrieval and summarization cause the agent to commit the payload.

3 Design

MemLineage combines signed provenance, append-only logging, derivation lineage, verifier-aware retrieval, and sensitive-action gating around one memory store. Its propagation rule preserves untrusted ancestry across strong derivation paths, while M6 blocks sensitive actions without preventing benign recall.

  • Architecture: MemLineage attaches provenance metadata, per-principal Ed25519 signatures, Merkle logging, lineage edges, trust labels, and policy checks to every memory entry.The architecture uses six modules around a single memory store.
  • Lineage propagation: The lineage DAG records LLM-mediated derivations, and max-of-strong-edges propagation preserves an untrusted label along any path whose edges exceed τ.Theorem 1 guarantees trust(c) ≥2 when an External or otherwise untrusted ancestor connects through strong edges.
  • Write and read paths: The write path runs through metadata, signing, and append-only Merkle logging, while retrieval verifies signatures and renders current trust labels.M5 drops entries whose signatures fail verification before consulting their trust labels.
  • Lineage propagation: The propagation fallback returns Trusted when no parent exceeds τ, leaving a residual risk if an attacker suppresses every attribution edge below threshold.The paper describes JSON-envelope hardening for this judge-injection case and acknowledges the remaining risk.
  • Sensitive-action gate: M6 checks active-context trust and per-parameter authority, refusing or repairing sensitive calls when untrusted context cannot authorize security-critical arguments.Repair-and-Retry substitutes attacker-controlled parameters only when trusted evidence supplies authorized replacement values.

4 Implementation

The implementation separates reusable provenance, lineage, retrieval, policy, and attack/evaluation components behind framework adapters. It also hardens attribution judging and pins deterministic evaluation behavior for reproducibility.

  • Package structure: The package separates core cryptography and storage from lineage, retrieval, policy, LangGraph adapters, attack adapters, and evaluation modules.The core layer does not import LangGraph, allowing framework-independent reuse.
  • Judge hardening: LmSelfEval is protected against prompt injection through JSON isolation, explicit data-only role instructions, bounded candidate content, and bounded candidate counts.The judge wrapper also treats only selected network/API failures as transient; programmer and shape errors fail closed at startup.
  • Reproducibility: The deterministic harness replaces the real judge with a prescribed wk = w0 · d^(k−1) schedule, making the τ × K ablation byte-equal CI-verifiable.This isolates ablation behavior from variability in live model judgments.
  • Agent integration: ProvMemMiddleware links retrieval results to subsequent writes, automatically selecting retrieved entries as candidate parents when auto_attribute=True.The write hook computes weights, applies propagation, and persists a freshly signed ProvEntry.
  • Agent integration: Explicit-parents-only semantics are available by setting auto_attribute=False, but that configuration is used only in the implicit-laundering ablation.The default configuration closes the laundering surface after retrieval.

5 Attacks Modelled

The evaluation models three memory-poisoning families: direct trigger planting, trusted-principal retrieval poisoning, and sleeper-via-derivation. Together they distinguish signature integrity from lineage persistence and policy enforcement across agent-authored derivations.

  • Attack families: The harness evaluates AgentPoison-style, MemoryGraft-style, and sleeper-via-derivation attacks using deterministic adapters for reproducible ASR measurements.The first two reproduce published threat models, while the third stresses lineage under LLM-mediated laundering.
  • AgentPoison-style: AgentPoison-style attacks plant trigger-bound entries under an unregistered External principal and surface them when a matching query retrieves the payload.A working signature layer drops these entries before they reach the gate, so this workload is a sanity check rather than a discriminating test.
  • MemoryGraft-style: MemoryGraft-style attacks plant entries under a trusted writer and require lineage analysis because valid signatures alone admit the poisoned memory.The sig_only_baseline fails this column, whereas MemLineage blocks chains reaching an External ancestor.
  • Sleeper-via-derivation: Sleeper-via-derivation launders an adversarial primer through normal retrieval and summarization into an agent-signed entry that appears benign to signature-only defenses.The attack plants only ingredients externally, then relies on derived entries to bias a later sensitive tool call.
  • Sleeper-via-derivation: The sleeper workload varies chain length K, primer type, sink action, and derivation prompt to test how semantic survival and attribution strength change across derivations.K ∈{1, 2, 3, 5}; longer chains create more opportunities for primer loss or edge weights falling below τ.
  • What the workloads separate: These workloads jointly test whether signature, lineage, and policy layers preserve useful memory while blocking sensitive dispatch.The paper identifies sleeper-via-derivation as the case requiring all three capability dimensions together.

6 Evaluation

The evaluation isolates how provenance, lineage propagation, and sensitive-action gating behave across deterministic memory-poisoning workloads and a bounded AgentDojo bridge. MemLineage blocks attacks while preserving more utility than coarse denial or retry-based recovery, with low per-operation overhead.

  • Experimental setup: The mechanism-isolation harness holds all plumbing constant while varying only propagation and gating policy across three documented attack cells.This design makes column-to-column differences attributable to the defense.
  • Deterministic harness: MemLineage is the only configuration that drives all three deterministic-harness attack columns to zero ASR.Signature-only protection closes AgentPoison-style attacks but fails on MemoryGraft-style and sleeper-via-derivation attacks.
  • Deterministic harness: Lineage propagation blocks signed laundering because derived entries retain an External ancestor and the sensitive-action gate refuses the resulting chain.This preserves the upstream edge across the memory write/read boundary, unlike signature-only verification.
  • AgentDojo bridge: Authority repair blocks attacks on 6/6 pairs, recovers utility on 5/6 pairs, and averages 0.33 denied and 0.33 repaired calls per row.Generic strip-and-retry also preserves security but averages 5.17 denied calls per row and recovers utility on 4/6 pairs.
  • AgentDojo bridge: The vulnerable-agent AgentDojo stress test makes both no-defense baselines fail on all six banking pairs, while every MemLineage row reduces strict AgentDojo ASR to zero.The stress profile intentionally exposes tool-output vulnerabilities to separate model behavior from defense-layer behavior.
  • Threshold calibration: The attribution ablation shows that safe threshold selection depends on expected chain depth because degrading edge weights can move individually safe derivations into the unsafe region.Under w0 = 0.9 and d = 0.7, the deepest edge determines the tightest constraint, with w3 = 0.441 and w5 ≈0.216.
  • Performance: The write hot path costs 214 µs median, with Ed25519 signing, codec work, and Merkle append among the reported contributors.The reported overhead remains sub-millisecond per operation.

7 Related Work

Prior work spans persistent-memory attacks and defenses organized by their mechanisms, while MemLineage is positioned against these attack and defense families. The cited attacks establish cross-session compromise as a relevant setting for comparison.

  • Persistent-memory attacks include trigger-bound vector-store poisoning, query-only poisoning, self-derived experience poisoning, and two-phase infection followed by unauthorized action.
  • AgentPoison, MINJA, and MemoryGraft represent distinct ways attacker-controlled content can enter or later activate persistent agent memory.
  • Zombie Agents most closely precedes the paper’s memory-laundering workload by modeling infection through long-term memory followed by later action.
  • Indirect prompt injection at the active-context boundary is treated as foundational background but remains outside this paper’s scope.

7.2 Coarse Memory Gating and Temporal Re-Entry

Coarse defenses protect agents by restricting recall or attenuating capabilities after exposed reads, but they sacrifice fine-grained utility distinctions. MemLineage instead preserves recall while making dispatch decisions from retrieved entries’ provenance and trust labels.

  • Input and retrieval filters largely fail on delayed-trigger attacks, whereas a Memory Sandbox blocks most evaluated models.
  • RTW-A combines temporal write-before-read control, sealed configuration, typed promotion, persistent taint, and capability attenuation.
  • Memory Sandbox blocks attacks by removing the recall capability they require, while RTW-A attenuates high-risk capabilities after tainted reads.
  • MemLineage takes an entry-level route that signs memory entries, records derivation parents, preserves recall, and gates each sensitive dispatch.

7.3 IFC at Planning Time

Planning-time IFC defenses enforce labels during a single execution, while cross-session defenses add persistent semantic taint or memory validation. MemLineage complements these approaches by durably binding trust labels to memory entries.

  • Fides tracks confidentiality and integrity labels through tool-call sequences and refuses dispatches that violate policy, but its label state is erased at execution boundaries.
  • MemLineage persists an External ancestor’s label across LLM-mediated derivations and session boundaries by attaching it to the memory entry.
  • Fides and MemLineage are described as complementary: deployments can combine planning-time IFC labels with durable provenance.
  • NeuroTaint propagates semantic taint across agent sessions but does not provide cryptographic integrity for the taint label.
  • A-MemGuard uses consensus validation and dual-memory distillation to address malicious records and self-reinforcing error cycles, making its mechanism orthogonal to MemLineage.

7.6 Retrieval-Stage Filtering

Retrieval-stage defenses treat the recall surface as the filtering chokepoint, but laundering makes benign and poisoned summaries indistinguishable from content alone. MemLineage adds provenance-aware rendering and downstream sensitive-action gating.

  • RAGPart and RAGMask filter or mask candidate entries at retrieval time under the assumption that content reveals whether an entry is benign or poisoned.
  • Laundered entries are authentic LLM summaries, so retrieval content alone cannot distinguish them from benign summaries of the same context.
  • MemLineage’s verifier-aware retrieval surfaces trust labels and lets the sensitive-action gate refuse downstream dispatches without removing recall.
  • Signature-only integrity attests who authored an entry but not what it was derived from, leaving a capability gap for laundering.
  • Section 6.2 reports the empirical consequence of this signature-only gap on sleeper-via-derivation.

7.8 Sensitive-Action Policy

MemLineage’s sensitive-action policy uses trust-aware dispatch decisions over persistent labels, combining provenance and lineage to cover capabilities that prior systems split across mechanisms.

  • M6 adopts Progent’s JSON-schema predicate model while making dispatch depend on M5’s rendered trust labels rather than the LLM’s account of consulted entries.
  • MemLineage jointly covers cryptographic label integrity, LLM-mediated lineage attribution, cross-session label persistence, and agent-derived entries.
  • Prior systems typically provide only subsets: planner enforcement lacks durable labels, semantic taint lacks cryptographic integrity, and signature-only layers lack lineage attribution.
  • Figure 8 marks MemLineage as the only compared system with full coverage across all four capability dimensions.

7.10 Adjacent and Non-Competing Threads

MemLineage complements rather than replaces adjacent defenses, which address detection, confidentiality, or memory-content protection rather than trust-label persistence and lineage-aware enforcement.

  • Detection-only defenses can operate above retrieval, while encryption-at-rest and TEE-bound custody protect memory contents rather than their trust semantics.

8 Discussion

The discussion identifies scope boundaries around trusted inference, attribution availability, residual prompt-injection risk, adaptive evaluation, and model-dependent AgentDojo behavior.

  • MemLineage assumes trusted LLM weights and inference, so compromised models or endpoints require separate weight-level attestation.
  • White-box attention requires open weights, while an adversary suppressing attribution edges below τ can locally defeat lineage propagation and permit a laundered dispatch.
  • Strict-mode mitigations include defaulting no-strong-parent cases to Derived-Untrusted or requiring attribution quorum, but JSON-envelope hardening does not eliminate residual risk.
  • The headline deterministic ASR matrix uses fixed non-adaptive payloads; a full adaptive sweep remains future work because of noise and API-budget constraints.
  • The all-zero live-model table reflects a benign query, whereas task-relevant AgentDojo injections expose the interaction between model safety behavior and provenance gating.
  • Under vulnerable tool-output injections, no-defense baselines reach 6/6 strict AgentDojo ASR while all MemLineage rows remain at 0/6.

9 Conclusion

MemLineage addresses sensitive-action enforcement for persistent agent memory through cryptographic provenance and derivation lineage, while preserving useful recall. In the reported evaluations, it uniquely achieved zero ASR across modeled workloads and maintained sub-millisecond overhead.

  • MemLineage combines cryptographic provenance with LLM-mediated derivation lineage to prevent sensitive actions justified by untrusted persistent state.
  • MemLineage was the only tested configuration reaching zero Attack Success Rate on all three modeled workloads.
  • Sub-millisecond per-operation overhead remained on the agent’s critical path.
  • Its distinguishing capability is joint coverage of cryptographic label integrity, lineage attribution, cross-session persistence, and agent-derived entries.
Loading 2605.14421v1…