🤖 AI

SMSR: Certified Defence Against Runtime Memory Poisoning in Persistent LLM Agent Systems

This paper introduces SMSR, the first defense mechanism that provides certified robustness against Multi-Session Memory Poisoning (MSMP) in persistent LLM agent systems by combining HMAC-based provenance verification with randomized memory ablation and verdict-based majority voting to effectively neutralize both unsigned and authenticated memory injection attacks.

Original authors: Tarun Sharma

Published 2026-06-12

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Tarun Sharma

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

The Problem: The "Poisoned Diary"

Imagine a smart office assistant (an AI agent) that helps employees by remembering past conversations, company policies, and facts. It keeps a digital diary (memory) that it updates every time someone talks to it. This diary helps the AI answer future questions more accurately.

The Attack:
A bad actor (hacker) doesn't need to break into the AI's brain or rewrite its code. Instead, they just talk to the AI normally, but they slip in fake, carefully worded lies into the conversation. The AI, thinking this is a normal update, writes these lies into its diary.

Later, when a different employee asks a question, the AI reads its diary, finds the fake lie, and believes it is true. It then gives the wrong answer to the new employee. This is called "Memory Poisoning."

Existing defenses are like a security guard who only checks the content of what you say. But a smart liar can phrase their fake news so it sounds perfectly normal, fooling the guard. The paper argues that without a way to verify who wrote the entry, you can never be 100% sure the diary is safe.

The Solution: SMSR (Signed Memory with Smoothed Retrieval)

The authors propose a two-part defense system called SMSR. Think of it as a combination of a Secure Stamp and a Randomized Jury.

Part 1: The Secure Stamp (HMAC Provenance)

The Analogy: Imagine every page the AI writes in its diary must be stamped with a special, unforgeable wax seal (a cryptographic signature) by a trusted manager before it's saved.
How it works:
- If a hacker tries to inject a fake memory by directly hacking the database (without going through the normal chat), they can't forge the seal. The system sees the missing seal and throws that memory away immediately.
- Result: This stops 100% of "unsigned" attacks (hackers who try to sneak in data without permission).

Part 2: The Randomized Jury (Smoothed Retrieval)

The Problem: What if the hacker is a legitimate employee? They have a valid seal, so Part 1 lets their fake memory in.
The Analogy: Imagine the AI needs to answer a question. Instead of reading the entire diary (which might be full of lies), it plays a game of chance:
1. It pulls out a huge pile of relevant pages (say, 20 pages).
2. It randomly picks a small handful (say, 5 pages) to read.
3. It repeats this process 5 times, creating 5 different "mini-stories."
4. It asks a "Judge" (another AI) to check each story: "Is this story telling the truth or a lie?"
5. It takes a majority vote. If 3 out of 5 stories say "This is a lie," the system ignores the lie.
Why it works: Even if the hacker planted a lie, they can't guarantee that lie will be in every random handful of pages. If the lie only appears in 1 or 2 of the 5 random samples, the honest majority wins.
The "Certified" Part: The authors did the math to prove exactly how likely it is for the system to fail. They can say, "We are mathematically guaranteed that the chance of the AI giving a wrong answer is less than 10.4%." This is a "security certificate."

Key Concepts Made Simple

1. The "Consistent Minority" Trap

The Trap: If you ask a group of people a question, and 3 people give different, slightly varied "I don't know" answers, but 2 people give the exact same fake answer, a simple vote might pick the fake answer just because it's the most common string of words.
The Fix: SMSR doesn't vote on the words; it votes on the verdict. The Judge AI looks at the meaning. Even if the fake answers are worded differently, the Judge sees they are all "Malicious." The honest "I don't know" answers are all "Safe." The vote counts the safety verdict, not the specific words, so the fake answer loses.

2. The Cost

To get this high level of security, the system has to work harder. Instead of asking the AI one question and getting one answer, it asks the AI 5 times (with different random memories) and asks a Judge 5 times to check the answers.
The Trade-off: It takes about 10 times more computing power (and a tiny bit more money), but it prevents the AI from being tricked by lies. The paper says this is worth it for important business decisions.

What the Paper Actually Found (The Results)

The authors tested this on 15 different business scenarios (like checking expense policies or security rules).

Stopping the Hackers: When hackers tried to inject fake data without a valid seal, the system stopped them 100% of the time.
Stopping the Sneaky Employees: When a legitimate user (who has a valid seal) tried to inject a lie, the system reduced the success rate of the attack from nearly 100% down to about 8% in a large, realistic test.
The Math Holds Up: The actual failure rate (8%) was lower than the mathematical "worst-case" prediction (10.4%), proving the security certificate works.
Real-World Test: Even when the hacker tricked the AI into writing the poison itself (by asking a tricky question that made the AI write the lie to its own diary), the defense still worked, dropping the success rate from 65% down to 5%.

Summary

The paper introduces a system that acts like a notarized diary combined with a randomized jury. It proves mathematically that you can't just filter bad words; you need to verify who wrote the memory and use randomness to dilute the bad memories. This ensures that even if a smart hacker gets inside, they can't easily trick the AI into giving dangerous advice.

Technical Summary: SMSR – Certified Defence Against Runtime Memory Poisoning in Persistent LLM Agent Systems

1. Problem Statement: Multi-Session Memory Poisoning (MSMP)

Retrieval-Augmented Generation (RAG) agents in enterprise environments increasingly rely on persistent memory stores that accumulate interactions across user sessions. This persistence creates a novel attack surface: an adversary (acting as an employee, customer, or compromised tool) can inject carefully crafted memories that persist indefinitely. Once retrieved, these poisoned entries redirect the agent's behavior on future queries without modifying model weights or application code.

The paper identifies the Multi-Session Memory Poisoning (MSMP) threat, where an adversary injects memories that semantically match future user queries, causing the agent to output malicious or incorrect responses. Existing defenses are insufficient:

Static-corpus defenses (e.g., RobustRAG, ReliabilityRAG) assume a fixed knowledge base indexed offline and fail when the adversary injects data at runtime via the agent's normal write path.
Heuristic filters (e.g., keyword blacklists, entropy checks, semantic anomaly detection) are bypassable by fluent, enterprise-style text that mimics legitimate policy updates.
Consensus-based heuristics (e.g., A-MemGuard) lack formal security guarantees and can be defeated by persistent adversaries who adapt their injection strategies.

Crucially, no existing defense provides a formal security certificate (a mathematical bound on attack success) against adaptive runtime memory poisoning.

2. Methodology: Signed Memory with Smoothed Retrieval (SMSR)

The authors propose SMSR, a two-component defense mechanism designed to provide a certified robustness bound against MSMP.

Component 1: HMAC Provenance Tagging (Write-Time Boundary)

To address unsigned adversaries (those with direct database access but no authentication credentials), SMSR implements a cryptographic boundary at the write time.

Mechanism: Every legitimate memory entry is tagged with an HMAC-SHA256 signature using a server-side secret key ( $K$ ).
Retrieval: At query time, the system verifies the HMAC tag of retrieved entries. Only entries with valid tags are admitted to the candidate pool.
Security: Under standard HMAC assumptions, an unsigned adversary cannot forge a valid tag, effectively reducing the attack success rate (ASR) for unsigned injections to 0%.

Component 2: Randomised Memory Ablation with Verdict-Based Aggregation (Authenticated Adversaries)

To address authenticated adversaries (legitimate users who can write signed memories), SMSR employs a randomized defense similar to smoothed classification.

Over-fetching: For a query, the system retrieves a large pool of $m$ verified candidates ( $m > k$ , where $k$ is the standard context size).
Randomised Ablation: The system performs $n_{runs}$ independent trials. In each trial, it samples $k$ entries uniformly at random (without replacement) from the $m$ candidates.
Verdict-Based Aggregation: An LLM judge evaluates the response generated in each trial, returning a verdict (e.g., correct, malicious, neither). The final output is determined by a majority vote of the verdicts, not the text strings themselves.
Theoretical Basis: This approach relies on a hypergeometric distribution to bound the probability that a majority of sampled contexts contain adversarial entries.

Theoretical Contributions

Impossibility Result (Theorem 1): The authors prove that no deterministic, provenance-free filter operating solely at retrieval time can achieve a non-trivial security certificate against an adaptive adversary. This necessitates the write-time provenance mechanism of Component 1.
Certified Robustness Bound (Theorem 2): A formal hypergeometric certificate is derived for Component 2, defining the maximum probability ( $\delta$ ) of a malicious output given $t$ adversarial entries in a pool of size $m$ .
Consistent Minority Effect (CME): The paper formalizes a pitfall where string-based majority voting fails because adversarial responses are textually consistent while benign responses vary (paraphrase variation). SMSR mitigates this by using verdict-based aggregation, which counts semantic correctness rather than string equality.

3. Key Contributions

Formal Definitions: Introduction of the MSMP threat model and the first $(t, \delta)$ -security definition for runtime agent memory systems.
Impossibility Proof: Demonstration that provenance-free defenses cannot be certified against adaptive injection.
SMSR Construction: A practical defense combining HMAC provenance and randomized ablation with a formal certificate.
CME Characterization: Formalization and quantification of the Consistent Minority Effect, showing that verdict-based aggregation is required to neutralize it.
Empirical Validation: Extensive evaluation across 15 enterprise scenarios and 3,150 repeated trials.

4. Experimental Results

The evaluation was conducted on 15 enterprise knowledge-base scenarios (finance, compliance, IT, HR) using a 20-seed memory store for production-scale testing and a 10+seed store for small-scale evaluation.

Unsigned Attacks (Component 1): SMSR reduced the Attack Success Rate (ASR) from 93–100% (in undefended baselines) to 0% for all unsigned injection variants, including "bypass" attacks crafted to evade heuristic filters.
Authenticated Attacks (Component 2):
- Production-Scale ( $m=20, t=1$ ): SMSR reduced ASR from 93–100% to 8.0% (95% CI [5.8%, 10.9%]). This result is safely below the theoretical worst-case bound of $\delta = 10.4\%$ (at $n_{runs}=5$ ).
- Small-Scale ( $m'=11, t=1$ ): ASR was 37.8% (95% CI [33.4%, 42.3%]), which is below the certificate bound of $\delta = 41.5\%$ .
- Flooding Variants: In flooding scenarios (multiple paraphrased injections), ASR approached the theoretical bound, confirming the tightness of the certificate.
Comparison with Heuristics: While an A-MemGuard-style consensus baseline achieved a comparable empirical ASR (3.8% vs. 8.0% in a specific 20-seed test), it offered no formal certificate. SMSR's distinction is the provision of a mathematical guarantee.
End-to-End Validation: In a query-only attack where the agent itself wrote the poison (mimicking the MINJA attack vector), SMSR reduced ASR from 65.3% to 5.3%.
Utility: Component 1 preserved 90% utility on clean queries. The combined defense (Components 1 & 2) maintained 85% utility, representing a 5% cost for the security guarantee.
Judge Reliability: Inter-judge agreement between Haiku and Sonnet models was high ( $\kappa = 0.955$ ), confirming the reliability of the verdict aggregation.

5. Significance and Claims

The paper claims to present the first formally certified defense against runtime memory poisoning in persistent LLM agent systems. Its significance lies in:

Moving beyond heuristics: Unlike prior work that relies on empirical observation or static assumptions, SMSR provides a mathematical guarantee ( $\delta$ ) on the probability of a successful attack.
Addressing the dynamic nature of memory: It specifically targets the "live append-only" nature of agent memory, a setting where static corpus defenses fail.
Proving necessity of provenance: The impossibility result establishes that without write-time cryptographic attestation, no retrieval-time filter can be certified.
Practical Deployability: The system is designed as a drop-in wrapper for existing RAG architectures, requiring no changes to the underlying LLM or embedding models, with manageable computational overhead (approx. 10 API calls per query for $n_{runs}=5$ ).

The authors conclude that SMSR effectively mitigates the MSMP threat for bounded adversaries, providing a foundational step toward a comprehensive security stack for LLM applications (specifically addressing OWASP LLM08 poisoning sub-problems).