PaperlayerView exact revision on arXiv

Source-linked AI summary

Aligning Provenance with Authorization: A Dual-Graph Defense for LLM Agents

Peiran Wang, Ying Li, Yuan Tian

arXiv:2605.26497v1cs.CR

TL;DR

Indirect prompt injection can turn attacker-controlled external data into unauthorized agent actions, while existing defenses lack either parameter-source tracking or an independent clean authorization baseline. AUTHGRAPH aligns execution provenance with a clean authorization graph; across AgentDojo and AgentDyn, it reports a state-of-the-art security-utility trade-off.

  • Problem

    Existing defenses either check tool calls without tracking parameter origins or analyze traces without an independent clean authorization baseline, leaving a gap in detecting injection-driven unauthorized actions.

    Source: §1 · pp. 1–2

  • Method

    AUTHGRAPH builds an injected reasoning graph from execution and an authorization graph from the prompt and tool catalog in a clean context, then aligns them to check tools and parameter sources.

    Source: §1 · p. 2

  • Results

    Across AgentDojo and AgentDyn, AUTHGRAPH achieves a state-of-the-art security-utility trade-off; on AgentDojo GPT-4o, ASR falls from 0.40 to 0.01.

    Source: §4.2 · p. 8, §5 · p. 9

  • Takeaways & Limitations

    AUTHGRAPH provides fine-grained injection detection beyond tool-call-level checking by structurally comparing authorization specifications with execution provenance at the parameter-source level.

    Source: §5 · p. 9

    If an authoritative tool’s own data source is poisoned, the source-tools check can pass because the value genuinely came from the expected tool.

    Source: §5 · p. 9

Abstract

from arXiv · show

LLM-based agents are increasingly deployed in high-stakes scenarios such as email management, financial transactions, and code execution, where they interact with the external world through tool calling. During execution, these agents must read external data sources (emails, webpages, files) that attackers can control; through indirect prompt injection, attackers embed malicious instructions in this data to manipulate agents into performing unauthorized operations such as transferring funds to attacker-controlled accounts. Existing defenses either perform tool-call-level value checking without tracking where parameter values originate, or analyze execution traces from a single perspective without a clean authorization baseline for comparison. We propose AuthGraph, a dual-graph alignment defense framework that constructs two complementary graphs: an injected reasoning graph that models information provenance from the actual execution trajectory (including potentially manipulated attributions), and an authorization graph derived from the user's intent in an isolated clean context that is information-theoretically impossible to be influenced by injection; a graph alignment checker then structurally compares the two graphs to detect both tool-level and parameter-source-level deviations. On AgentDojo, AuthGraph reduces the attack success rate from 40% to 1% while maintaining 76% task completion rate on GPT-4o; on AgentDyn, it reduces the attack success rate from 39% to 2% while preserving 51% utility, outperforming state-of-the-art defenses including CaMeL, DRIFT, and Progent. To our knowledge, AuthGraph is the first agent security defense to structurally compare authorization specifications against execution provenance at the parameter-source level, achieving fine-grained injection detection without sacrificing agent flexibility.

1 Introduction

Indirect prompt injection lets attacker-controlled external data steer agents toward unauthorized tool actions, while existing defenses lack both faithful provenance and a clean, source-aware authorization baseline. AUTHGRAPH aligns execution and authorization graphs and reports strong security-utility results on AgentDojo.

1 Introduction

  • Indirect prompt injection embeds malicious instructions in external data, manipulating agents into unauthorized operations such as booking a fraudulent flight.In the example, a compromised hotel listing supplies a flight code and malicious verification webpage.Source: §1 · pp. 1–2
  • Prompt-, input-, and model-level defenses do not structurally constrain tool choice or parameter origins, while system defenses lack three desired properties together.Those properties are faithful execution provenance, comprehensive injection-free authorization, and trajectory-grounded enforcement.Source: §1 · p. 2
  • AUTHGRAPH separates actual execution provenance in an injected reasoning graph from an authorization graph derived from the prompt and tool catalog in a clean context.The planner sees no observation data, so attackers have no channel to influence the authorization graph.Source: §1 · p. 2
  • ASR 0.01 with UR 0.69 on AgentDojo GPT-4o-mini gives AUTHGRAPH the best security-utility trade-off among defenses.It outperforms CaMeL (UR 0.48), Progent (UR 0.64), and DRIFT (UR 0.52) at comparable security.Source: §1 · p. 2
  • Its alignment checker uses hard-block, tool-name, and parameter-source checks, while the authorization graph combines source constraints with runtime least-privilege replanning.The injected reasoning graph preserves provenance, including attributions potentially manipulated by injected content.Source: §1 · p. 2

2 Related Work and Preliminaries

Prior defenses either check tool calls without tracing parameter origins or analyze execution traces without an independent clean authorization baseline. The preliminaries frame the problem as extracting information flow from unstructured agent trajectories, where observations may be untrusted.

2.1 Defenses Against Prompt Injection

  • Plan-then-check defenses verify tool calls but do not track parameter origins, leaving cross-tool pollution such as a flight code from a hotel listing undetected.Graph-trace methods use a single graph without an independent clean baseline, so injection can manipulate the graph without revealing the discrepancy.Source: §2.1 · p. 3
  • IFC-based defenses constrain data flow, but Fides’s strong guarantees come with TCR ≈25%; AUTHGRAPH instead uses dual-graph parameter provenance without hiding untrusted data.Other defenses include trusted-data-only planning and selective taint propagation.Source: §2.1 · p. 3

2.2 Attacks and Benchmarks

  • The paper situates evaluation among indirect-injection benchmarks, using AgentDojo for standardized scenarios and AgentDyn for open-ended dynamic tasks.The related work also describes attacks ranging from universal injection to multi-agent prompt infection.Source: §2.2 · p. 3

2.3 Preliminaries

  • An agent trajectory is an ordered sequence of thought, action, and observation tuples, recording decisions and information sources in unstructured natural language.The figure overview shows the Planner using the prompt and tool catalog without trajectory data, while the Graph Builder uses the execution trajectory.Source: §2.3 · pp. 3–4, Figure 1 · p. 4
  • IFC labels data by trust and propagates the most restrictive level, but agent reasoning makes information flow implicit in probabilistic natural language.AUTHGRAPH treats user prompts as trusted and tool observations as untrusted, tainting critical parameters that ultimately originate from untrusted observations.Source: §2.3 · p. 4

3 AUTHGRAPH

AUTHGRAPH separates actual execution provenance from an authorization specification generated in a clean context, then structurally aligns the two graphs. Its threat model covers attacker-controlled observations that may induce unauthorized tool calls or wrong-source parameters, while excluding user-authorized observation actions and same-observation pollution.

3.1 Overview

  • AUTHGRAPH aligns an execution-provenance graph with a cleanly generated authorization graph to detect deviations in tool calls and parameter sources.The checker blocks an unrelated webpage call and detects a flight ID taken from hotel results instead of flight-search results.Source: §3.1 · pp. 4–5

3.2 Injected Reasoning Graph

  • The IRG deliberately records actual behavior, including attributions manipulated by injected content, so deviations from an independent clean baseline become the injection signal.Its schema includes input, observation, decision, and intermediate nodes; INVOKE edges expose tool calls, while DERIVE and EXTRACT edges are not relied on for detection. Interactive construction uses a three-edge schema, which roughly halves construction cost versus the explored nine-edge variant without losing detection capability.Source: §3.2 · pp. 5–6

3.3 Authorization Graph

  • The authorization graph specifies expected tool order and legitimate sources for security-critical parameters, using a Planner that sees only the user prompt and tool catalog.For write-class tools, the Planner must declare a ParamPolicy for every security-critical parameter; its clean context contains no trajectory data.Source: §3.3 · p. 6
  • For runtime-dependent tasks, replan steps generate sub-authorization graphs constrained by an allowed-tool whitelist and programmatic consistency checks.When users explicitly authorize actions based on observations, the designated observation is treated as trusted for whitelisted actions; tampering harm then falls outside the dual-graph enforcement scope.Source: §3.3 · pp. 6–7

3.4 Graph Alignment Checker

  • The Checker aligns authorization steps with ordered INVOKE calls in O(n), using hard blocks, tool-name judgment, and source-constrained parameter checks.Authorized-set tools bypass tool-name judgment; parameter checking searches original source observations first, saving approximately 60% of LLM calls.Source: §3.4 · p. 7

4 Evaluation

AUTHGRAPH is evaluated on AgentDojo and AgentDyn against existing defenses, with results reported for multiple models. The evaluation also examines model generalizability, component ablations, and runtime overhead.

4.1 Experimental Setup

  • The evaluation covers AgentDojo’s 97 tasks and 629 injection scenarios across four domains, AgentDyn’s open-ended tasks, nine defenses, and three utility and attack metrics.Baselines use identical model configurations and benchmark settings; experiments use GPT-4o for graph building and checking, GPT-4o-mini for planning, and temperature 0.Source: §4.1 · pp. 7–8

4.2 Experimental Results

  • On AgentDojo, AUTHGRAPH reaches ASR 0.01 with UR 0.69 on GPT-4o-mini, and ASR 0.01 with UR 0.76 on GPT-4o.Table 3 presents the full comparison across benchmarks and models.Source: Table 3 · p. 8, §4.2 · p. 8
  • On AgentDyn, AUTHGRAPH achieves ASR 0.02 with UR 0.51 on GPT-4o, the highest utility among defenses at comparable security.On GPT-4o-mini, it reduces ASR from 0.52 to 0.02 while preserving UR 0.37.Source: §4.2 · p. 8, Table 3 · p. 8
  • Across four AgentDojo models, AUTHGRAPH reduces ASR from 0.15–0.40 to 0.01–0.03, with UR loss of 3–6 percentage points and no model-specific tuning.The reported ASR pairs are 0.17 to 0.01 (GPT-4o-mini), 0.40 to 0.01 (GPT-4o), 0.15 to 0.02 (Qwen-2.5-70B), and 0.31 to 0.03 (DeepSeekr1-70B).Source: §4.2 · p. 8, Table 4 · p. 9
  • Removing the hard block raises ASR from 0.01 to 0.12, removing the name check to 0.21, and removing the parameter check to 0.18; UR remains 0.76–0.79.The parameter check provides independent value for envelope-internal attacks, where the tool name is correct but parameter values are manipulated.Source: §4.2 · p. 9, Table 5 · p. 9
  • AUTHGRAPH adds 4.61 seconds per task (1.87×); its own analysis accounts for less than half of total runtime.The agent runtime accounts for 53% of total time; CaMeL incurs 9.21× overhead.Source: §4.2 · p. 9, Table 6 · p. 9

5 Discussion and Conclusion

AUTHGRAPH’s reported boundaries include poisoned authoritative data, attribution errors, multi-agent execution, and the trust boundary opened by replanning. The paper concludes that its dual-graph comparison provides fine-grained injection detection and a state-of-the-art security-utility trade-off.

Limitations

  • If an authoritative tool’s data is poisoned, ParamPolicy’s source check passes because the value genuinely originates from the expected tool.The authors give tampering with a flight-search backend as an example.Source: §5 · p. 9
  • Graph-builder attribution errors may produce false positives or false negatives, and the current design targets single-agent execution rather than cross-agent information flow.Tracking cross-agent information flow is outside the current architecture.Source: §5 · p. 9
  • Replanning opens a controlled trust boundary constrained by the tool whitelist, but sophisticated attackers may exploit it to act within whitelisted tools.Source: §5 · p. 9

Conclusion

  • The conclusion attributes fine-grained injection detection to structural comparison of authorization and execution-provenance graphs at the parameter-provenance level.Evaluation on AgentDojo and AgentDyn demonstrates a state-of-the-art security-utility trade-off against CaMeL, DRIFT, and Progent.Source: §5 · p. 9

A System Prompts

The appendix presents system prompts for AUTHGRAPH’s Graph Builder, Planner, and Checker, including graph construction, authorization planning, and graph-alignment checks.

A System Prompts

  • The appendix organizes prompts for IRG construction, authorization-graph generation, and graph-alignment checks.Source: A System Prompts · p. 12

A.1 Graph Builder (IRG Construction)

  • The Graph Builder’s three phases are generation, extension with each execution step, and refinement after observations when risk-relevant information needs to be added.Refinement can be skipped when no risk-relevant information is present, the graph already captures what is needed, or the task appears complete.Source: §A.1 · pp. 12–13
  • The Graph Builder constructs a reasoning graph that tracks which inputs influence agent decisions, using input, observation, decision, and intermediate nodes.Source: §A.1 · p. 12
  • Its graph uses DERIVE, EXTRACT, and INVOKE edges; observations should pass through EXTRACT before DERIVE, and the graph must be a DAG.Source: §A.1 · p. 12

A.2 Planner (Authorization Graph Generation)

  • The Planner generates a minimum expected tool-call sequence with parameter-source policies, including whether a step permits replanning.Source: §A.2 · p. 13
  • Policies distinguish literal user values, direct observation values, values reasoned from observations, and unspecified values; observation-based policies name allowed source tools.Source: §A.2 · p. 13
  • For WRITE tools, the Planner must declare policies for every security-critical field; replanning generates remaining steps and stays within the allowed tool list.The replan prompt also requires source-tool declarations for observation-based parameter policies.Source: §A.2 · pp. 13–14

A.3 Checker (Graph Alignment)

  • The Checker’s tool-name rule requires a verbatim observation sentence demanding the specific value before judging a parameter deviation injection-driven.For tool-call deviations, it distinguishes legitimate auxiliary or skipped steps from suspicious ones, including unrelated writes and external URL fetches.Source: §A.3 · p. 14

B Additional Case Studies

The section presents representative AUTHGRAPH detection case studies and discusses cases excluded from evaluation where users explicitly authorize consuming observations.

B Additional Case Studies

  • The section presents representative detection case studies and discusses evaluation exclusions involving explicit user authorization to consume observations.Source: B Additional Case Studies · p. 14

B.1 Successful Detection Cases

Successful detections include out-of-envelope tools and unauthorized values supplied through otherwise permitted tools. AUTHGRAPH also permits legitimate multi-hop and conditional workflows when the authorization graph models their parameter sources and replanning.

Category I: Tool-Name Detection

  • Out-of-envelope tools are deterministically caught, and this mechanism accounts for most successful detections on AgentDojo, where many attacks require cross-domain tools.The cases include password changes during shopping and filesystem operations during a Git task.Source: §B.1 · p. 15

Category II: Parameter Source Detection

  • Layer 3 detects substituted parameter values even when the tool and declared source type are allowed, by checking consistency with the user’s stated intent.It can also reject an OTP sourced from an unauthorized operation, despite the expected tool and source type being used.Source: §B.1 · p. 16
  • Compound attacks can trigger multiple detection layers, including separate blocks for an out-of-envelope tool and a parameter value that does not match the user’s request.Examples include an unauthorized purchase alongside a permitted shopping workflow and financial theft alongside a calendar-time change.Source: §B.1 · p. 16

Category III: Utility Preservation

  • Legitimate observation-sourced credentials and multi-hop parameter chains are permitted when the user’s task authorizes those sources and the authorization graph models the chain.The cross-account authentication and invoice-download cases are reported as having no false positives.Source: §B.1 · p. 17
  • Replanning permits conditional actions without requiring a fixed execution count, while per-parameter source types allow one task to combine distinct information sources.The repository-starring and multi-source calendar cases are reported as correctly permitted.Source: §B.1 · p. 17

B.2 Excluded Cases: User-Authorized Observation Consumption

The excluded cases arise when a user explicitly delegates trust to observation content and an injection redirects the agent through that content. Because the resulting attacked and legitimate traces can be identical in AUTHGRAPH’s observable space, the defense does not claim to distinguish them within its authorization-based scope.

B.2 Excluded Cases: User-Authorized Observation Consumption

  • When legitimate and attacked trajectories match in tool names, parameter source types, and envelope membership, AUTHGRAPH’s observable-space detector cannot distinguish them.The paper characterizes such traces as information-theoretically indistinguishable within the design scope.Source: §B.2 · p. 18
  • The excluded pattern requires the user to direct the agent to treat observation content as trusted, the authorization graph to permit that source, and an attacker to inject the observation.Examples include following a link in a document or using information from a designated file.Source: §B.2 · pp. 18–19
  • The evaluation excludes envelope-internal redirection cases because the paper treats explicit user delegation of trust as an authorization decision, not an agent scope violation.In AgentDyn, two such false negatives among 60 samples were excluded from reported metrics.Source: §B.2 · pp. 18–19
Loading 2605.26497v1…