On the Relative Security of Prompt Injection: Mechanised Definitions, Defences and Verdicts for LLM Agents

Brijesh DongolarXiv 2026 · arXiv

TL;DR

LLM agents are inherently vulnerable to prompt injection because they must process untrusted data to be useful, making traditional "all-or-nothing" security models like noninterference impractical. This paper introduces PlanTERS, a formal framework that defines security relatively: an agent is secure if it leaks no more information than a "reference agent" that follows the same plan but ignores untrusted instructions. Using the Isabelle/HOL proof assistant, the authors prove a "Fence Theorem" that guarantees security by revoking sensitive tool access at the exact moment untrusted content is first encountered.

What Problem Does This Paper Address?

Large Language Model (LLM) agents combine a program (the "planner") with a model that interprets user tasks and external content (like emails or web pages). This creates a massive security hole: prompt injection. An attacker can hide instructions in an email that trick the agent into exfiltrating private user data or performing unauthorized actions.

Existing security properties struggle here:

  • Noninterference is too strict; it forbids any secret data from influencing public output. A useful calendar agent must disclose your availability to a requester, so it would be rejected by this model.
  • Declassification requires developers to manually write complex "release policies" for every single task, which is unscalable.
  • Heuristic defenses (like "spotlighting" or marking untrusted text) are often bypassed by adaptive attackers.

The authors seek a mechanised, formal security criterion that can prove whether a defense actually works against a worst-case attacker, without breaking the agent's intended functionality.

Methods

The authors propose a "plan-then-execute" architecture where a trusted planner fixes a sequence of tool calls before any untrusted content is read.

Figure 1: Our plan-then-execute agent ar- chitecture. Trusted components are blue, untrusted ones red and the monitor amber. All calls and untrusted content pass through the monitor, and M observes the allowed calls on sinks.

Key components of their approach include:

  1. Relative Security: Instead of absolute secrecy, they compare the real agent to a "reference agent." If the attacker can't distinguish between two secret values in the real agent any better than they could in the reference agent, the system is relatively secure.
  2. PlanTERS Framework: A formal language and semantics for agents, monitors, and attackers, allowing for rigorous mathematical proofs.
  3. Runtime Monitors (Fences): A stateful monitor that can allow or deny tool calls. A "fence" specifically revokes certain capabilities (like SendEmail) when the agent enters a "tainted" state (e.g., after reading untrusted content).
  4. Mechanisation: The entire theory—including definitions, theorems, and 25 case studies—is implemented in Isabelle/HOL, totaling over 31,000 lines of formal proof code.

Datasets

As a formal verification paper, it does not use traditional machine learning datasets. Instead, it evaluates its framework against 25 "litmus tests"—small, targeted agent programs designed to isolate specific security behaviors. These include:

  • Leaky Summariser: A baseline agent that leaks an account number via an injected URL fetch.
  • Meeting Reply: An agent that legitimately discloses calendar data, used to show that relative security accepts "intended" leaks.
  • Budget/Approval Agents: Tests for defenses that limit the number of calls or require human-in-the-loop confirmation.
  • Dual-LLM Patterns: Models of architectures like CaMeL that isolate untrusted content in a quarantined model.

Key Insights and Ideas

  • The "Fence Theorem": The authors prove that revoking all "injectable" tools at the first untrusted read (and never granting them back) makes any plan relatively secure. This provides a clear, provable design rule for agent developers.
  • Timing is a Channel: The paper distinguishes between event-level security (what messages are sent) and step-level security (when they are sent). Some defenses, like "Call Approval," are secure at the event level but still leak information through timing.
  • Relative Security as a Policy: By using the agent's own intended plan as the reference, the security policy is implicitly defined by the task itself. This elegantly handles the "intended disclosure" problem that plagues traditional models.
  • Fence Placement is Critical: A "Late Fence" (locking after reading a secret) is useless if the injection happens immediately after reading the untrusted content. Security requires an "Early Fence" placed before the first untrusted read.
Figure 4: Where the fence goes. Only a lock before the first untrusted read leaves no window (shaded) for an injected Send call.

Key Results

  • Formal Proofs: The authors successfully proved (or refuted) relative security for all 25 litmus tests.
  • Defense Verdicts: They showed that spotlighting is insecure against a worst-case model because an attacker can simply "un-mark" the content. Conversely, they proved that sandboxing injected programs is effective if the fence covers both reads and calls.
  • Meeting Reply vs. Reset Code: Figure 3 illustrates the core logic: an injection that sends a calendar is "secure" if a genuine request would have done the same. However, an injection that adds a "reset code" to that same reply is an insecure leak because the reference agent would never send that code.
Figure 3: Meeting Reply (top) and Reset Code (bottom). The two injections reveal the calendar 𝑐 and the reset code 𝑟. A genuine request makes the reference reveal 𝑐too, but no email makes it reveal 𝑟.

Limitations and Future Work

  • Hijacking: The paper focuses on information leaks. It does not address "hijacking," where an injection makes an agent perform a harmful action (like deleting a file) that doesn't necessarily leak data.
  • Dynamic Planning: The current model assumes a fixed plan. Agents that use "ReAct" style loops (planning one step at a time based on tool outputs) are currently out of scope.
  • Complex Tools: Tools whose replies depend on the specific call (like a search engine) are not modeled, as they could potentially be controlled by the attacker to create a feedback loop.
  • Multi-Agent Systems: The framework currently considers a single agent interacting with a user and an attacker. Extending this to swarms of agents is a suggested future direction.

Summary updated

Abstract

An LLM agent that reads untrusted content, such as an email or a web page, may follow instructions hidden in it. Noninterference is too strong for such agents, since a useful agent lets untrusted content influence what it does and may disclose the user's data by design, and declassification needs a release policy written for each task. We instead state security relative to a reference agent, which runs the same plan under the same runtime monitor with a model that never obeys untrusted content. An agent is relatively secure if every leak it has is a leak the reference already has. Our framework, PlanTERS, instantiates relative security, a notion from speculative execution, with a small agent language in which the attacker chooses how the model follows instructions, a composition with runtime monitors, and attacker models that differ in what they observe. A fence theorem shows that revoking injectable tools at the first untrusted read, and never granting them back, makes every plan relatively secure at the event level on finite runs, for every model behaviour in which each injection is a single call and the model obeys on a schedule fixed in advance; with a fairness condition, this extends to possibly infinite runs. We prove or refute relative security for agents with fences, budgets, approvals, loops and dual LLMs, in Isabelle/HOL.
BibTeX
@misc{dongol2026relative,
  author = {Brijesh Dongol},
  title = {{On the Relative Security of Prompt Injection: Mechanised Definitions, Defences and Verdicts for LLM Agents}},
  year = {2026},
  eprint = {2611.11506},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.11506},
}
Figure