PaperlayerView exact revision on arXiv

Source-linked AI summary

Structurally Close, Temporally Distant: Measuring Security Exposure in Long-Horizon LLM Agents

Md Jafrin Hossain, Nur Al Hasan Haldar

arXiv:2609.05911v1cs.CRcs.AIcs.CLcs.LG

TL;DR

Long-horizon security analyses often use execution-step counts to characterize the separation between malicious inputs and sensitive actions. This paper builds provenance-aware execution graphs and compares structural influence distance with sequence distance; 96.9% of comparable pairs have different distances, with a median gap of 9 hops.

  • Problem

    Long-horizon agent security analyses often characterize attacks by the number of steps between malicious input and a downstream action, while trajectories also carry untrusted content through state and tools.

    Source: §1 · p. 1, §3.2 · p. 4

  • Method

    The paper constructs provenance-aware execution graphs and measures influence distance alongside sequence distance using deterministic state, identifier, and tool provenance.

    Source: §1 · p. 2, §3.3 · p. 4

  • Results

    96.9% of 454 comparable injection–sink pairs have different sequence and influence distances, with a median gap of 9 hops.

    Source: §5.1 · p. 6

  • Takeaways & Limitations

    Execution structure reveals proximity hidden by step count, and influence-based gating catches attacks that sequence-only gating misses.

    Source: §9 · p. 9

    A recorded path does not establish that an agent accessed or used injected data, and the structural gap is not a universal vulnerability score.

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

Abstract

from arXiv · show

Long-horizon LLM agents interact with untrusted content, persistent memory, external state, and sensitive tools. Existing analyses often characterize attacks by the number of execution steps between malicious input and a downstream action. We show that temporal remoteness can overstate security separation in stateful agents. We introduce a provenance-aware execution graph linking agent events through deterministic state, identifier, and tool provenance, and define \emph{influence distance} $\DI$ as the shortest structural path from an untrusted source to a sensitive action. We compare it with \emph{sequence distance} $\DT$, the shortest injection--sink path in the ordered trajectory. Since the influence graph contains every sequence edge, $\DI \leq \DT$; $\Gap=\DT-\DI$ measures the separation hidden by step count. Across 454 injection--sink pairs from 360 long-horizon AgentDojo trajectories over OpenAI's \texttt{gpt-4o-mini} and \texttt{gpt-4o} and Claude's Haiku 4.5 and Sonnet 4.6, $\Gap>0$ for 96.9% of pairs, with a median gap of 9 hops; 91.0% remain decoupled after removing the largest provenance-only edge class. On AgentDojo's banking suite, 33.8% of 231 pairs from 377 trajectories decouple through different provenance mechanisms. Among 274 OpenAI pairs, $\Gap$ does not independently predict attack success after controlling for $\DT$, attack family, and backend ($\beta_{\Gap}=0.066$, $p=.088$). At matched thresholds $k=2,3$, a deterministic $\DI$-based pre-execution gate blocks five attack sinks missed by a sequence-only gate with no additional benign blocking, although the paired gain is not significant ($p=.0625$). Execution structure therefore reveals proximity hidden by step count and can support targeted runtime intervention. We measure candidate influence pathways rather than causal attribution.

1 Introduction

Long-horizon agents move untrusted inputs through multistage interactions toward sensitive actions, making stage count appear to provide separation. The introduction argues that temporal remoteness can differ from structural proximity and proposes measuring both from execution records.

1 Introduction

  • Long-horizon agents consume outside-trust-boundary content and may later perform sensitive actions such as sending emails, logging reports, or making payments.Indirect prompt injection exploits this interaction with untrusted input.Source: §1 · p. 1
  • A malicious instruction can be written to a note at step 6 and read at step 24 just before a sensitive call, despite many intervening steps.Thus, elapsed steps measure when an event occurred, not necessarily its structural separation from an action.Source: §1 · pp. 1–2
  • Sequence distance counts intervening executions, while influence distance measures the shortest path after deterministic provenance and state edges are added.The structural gap is sequence distance minus influence distance; both are computed from execution paths without a language model or causal inference.Source: §1 · p. 2
  • 96.9% of comparable injection–sink pairs decouple, and decoupling persists for 91.0% after removing the top provenance-only edge class.In banking, decoupling is 33.8% through different provenance mechanisms.Source: §1 · p. 2

2 Background and Related Work

Prior agent-security benchmarks mainly report attack outcomes, while long-horizon analyses characterize when attacks execute. This paper instead treats trajectories as objects of study and measures structural proximity using execution provenance.

2 Background and Related Work

  • AgentDojo, InjecAgent, and other benchmarks report attack outcomes, while this work studies the trajectories themselves.The cited benchmarks measure outcomes such as injection success, user-task completion, and sometimes interaction length.Source: §2 · p. 2
  • Interaction length records when a sensitive action occurs relative to injection, not how closely they remain connected at execution [Yi et al., 2025, Yao et al., 2024].The paper measures that difference as a gap between temporal and structural distance.Source: §2 · pp. 2–3
  • Prior provenance defenses ask whether behavior is permissible given its inputs, whereas this work measures recorded proximity without establishing that content was used.The graph encodes whether a path exists, not how content was leveraged.Source: §2 · p. 3

3 Problem Formulation

The paper distinguishes how long untrusted input has been in an execution from how structurally close it is to a sensitive action. It formalizes structural proximity using provenance-aware graphs and a pre-execution gate.

3.1 Setting and threat model

  • The threat model has an adversary control text the agent reads, while the defender uses execution logs to judge proximity before a sensitive action executes.Untrusted sources carry content from outside the trust boundary, and sensitive sinks are configured by tool name.Source: §3.1 · p. 3

3.2 Three notions of proximity

  • The analysis separates temporal remoteness, structural exposure, and exploitability; exploitability depends on the model, injection phrasing, and defenses, not trajectory structure alone.Structural exposure concerns recorded derivation steps through persistent state, identifiers, and execution dependencies.Source: §3.2 · p. 4

3.3 Execution graph

  • The influence graph adds state, typed-identifier, batch, and same-tool call/result provenance edges to the sequence graph.State writes and subsequent reads are joined from runtime logs; identifier references are matched using source_ids.Source: §3.3 · p. 4

3.4 Sequence distance, influence distance, and the structural gap

  • Influence distance is the shortest path through execution and recorded provenance, while sequence distance follows consecutive events; their non-negative difference is the structural gap.A positive gap means recorded relationships connect injection to sink in fewer hops than the transcript suggests, not that the injection caused the action.Source: §3.4 · pp. 4–5

3.5 Guarding against circularity

  • Distances are computed for every eligible injection–sink pair regardless of attack outcome, and a recorded path is not treated as evidence of causation.This avoids selecting paths based on successful attacks or using the outcome in graph construction.Source: §3.5 · p. 5

3.6 Runtime gate

  • The runtime gate blocks a sensitive action when any observed untrusted source is within threshold k by influence distance; the sequence gate substitutes sequence distance.Because every sequence edge is also an influence-graph edge, the influence gate blocks at least the actions blocked by the sequence gate.Source: §3.6 · p. 5

4 Experimental Setup

The evaluation uses AgentDojo’s long-horizon suite as its primary setting and the banking suite as a within-framework cross-domain check. It reports graph variants and statistical procedures for comparing distances and gate outcomes.

Primary evaluation

  • The primary evaluation covers 360 long-horizon trajectories across four backends and retains 454 comparable injection–sink pairs.The suite has 15 user tasks and six injection tasks; attacks use direct-leakage or delayed save-and-retrieve patterns.Source: §4 · p. 5

Cross-domain validation

  • The banking suite supplies a within-framework cross-domain validation with 377 traces and 231 comparable pairs, but shared runtime and logging code limits what it establishes.It has no save-and-retrieve memory pattern, and its security predicate was corrected to label attack success consistently.Source: §4 · pp. 5–6

Graph variants

  • Structural results use both the full graph and a conservative graph that removes same-tool call/result edges, the largest and most contestable edge class.Cross-suite comparisons use the conservative graph on both sides unless otherwise stated.Source: §4 · p. 6

Statistics

  • The analysis uses Wilson 95% confidence intervals, omits binned attack-success cells with n < 10, and uses exact McNemar tests for paired gate comparisons.Pooled regression includes backend as a covariate, while backend-dependent quantities are analyzed per backend.Source: §4 · p. 6

5 E1: Sequence and Influence Distance Decouple

Across long-horizon trajectories, sequence and influence distances usually diverge, and the divergence persists when same-tool edges are removed. Banking also decouples through different provenance mechanisms, though at a lower rate in shorter trajectories.

5.1 Main result

  • 96.9% (440/454) of full-graph pairs decouple, with a median gap of 9 hops; median sequence distance is 23 and median influence distance is 12.The two distances differ substantially even at the same sequence distance.Source: §5.1 · p. 6

5.2 Robustness to graph construction

  • 91.0% (413/454) remain decoupled after removing same-tool call/result edges, with a median gap of 3; state, identifier, and batch provenance still provide shortcuts.Removing same-tool edges reduces the decoupling rate by 5.9 percentage points and the median gap by 6 hops.Source: §5.2 · pp. 6–7
  • A random audit of 15 shortcut-containing trajectories found every checked shortcut edge matched a relationship recorded by the runtime; short trajectories necessarily have small gaps.The audit checked shortcut edges on the source–action path against runtime source_ids.Source: §5.2 · p. 7

5.3 Cross-domain validation

  • Banking decouples in 33.8% (78/231) of pairs, with median gap 0 and maximum 19; its median sequence distance is 5 versus 23 for long-horizon tasks.Banking shortcuts use batch provenance, typed scheduled-transaction identifiers, and account-state mutations rather than save-and-retrieve memory; the suites share AgentDojo logging infrastructure.Source: §5.3 · p. 7, Table 2 · p. 7

6 E2: Does the Structural Gap Predict Attack Success?

The section tests whether structural gap predicts attack success beyond sequence distance and other covariates. The controlled analysis finds no statistically significant evidence of an independent gap effect.

6 E2: Does the Structural Gap Predict Attack Success?

  • Corrected long-horizon attack success rates were 50.0%, 68.9%, 1.1%, and 0% for GPT-4o-mini, GPT-4o, Haiku 4.5, and Sonnet 4.6, respectively.Banking rates were 74.1%, 0%, and 0.7% for its three evaluated models; GPT-4o was not run on banking.Source: §6 · p. 7, Figure 3 · p. 8
  • Longer sequence distance reduced success, while delayed attacks and backend B were associated with higher success than their comparison groups.All three control covariates were significant at p < 0.001.Source: §6 · p. 7
  • β_G = 0.066 (p = 0.088): structural gap was not a significant independent predictor of attack success after controls.The model covers 274 OpenAI pairs; the table reports pseudo-R2 = 0.14.Source: §6 · p. 7, Table 3 · p. 8

7 E3: A Runtime Influence-Distance Gate

The runtime gate checks recorded influence distance immediately before sensitive actions, then compares its additional blocked decisions with a sequence-only gate at matched thresholds.

7 E3: A Runtime Influence-Distance Gate

  • The gate checks the minimum influence distance from any previously seen untrusted source before a sensitive action, blocking when that distance is at most k.It uses recorded structure without a model call, learned component, or randomness; the evaluation replays one decision per injection–sink pair.Source: §7 · p. 8

7.1 Coverage against cost

  • At k = 5 and k = 8, the full graph added more attack blocks than the conservative graph, but also more benign blocks.At k = 5 the trade-offs were 23 extra attack sinks for 3 benign blocks versus 7 for 1; at k = 8 they were 48 for 15 versus 21 for 5.Source: §7.1 · p. 8
  • At k = 2 and k = 3, the influence gate blocked five additional attack sinks and no additional benign actions relative to the sequence gate.The full and conservative graphs produced the same result at both thresholds.Source: §7.1 · p. 8, Table 4 · p. 9, Figure 4 · p. 9
  • At k = 2, the five additional attack blocks were not statistically significant by the paired test (two-sided p = .0625).The authors characterize the gate as a model-free pre-execution check, not a standalone prompt-injection defense.Source: §7.1 · p. 9

8 Discussion and Limitations

The discussion distinguishes temporal separation from structural proximity and cautions against treating recorded paths as proof of causal use.

8 Discussion and Limitations

  • Sequence distance counts steps since injection, while influence distance measures its structural path to the sink; their median difference is 9 hops.The discussion treats both as legitimate measures.Source: §8 · p. 9
  • The observed gap is not a universal vulnerability score: it does not independently predict attack success, and the gate result concerns intervention at action time.The study frames the graph paths as candidate influence pathways rather than causal attribution.Source: §8 · p. 9
  • A recorded graph path does not establish that the agent accessed or used the injected data.The distances are determined by connections between graph nodes.Source: §8 · p. 9

9 Conclusion

Across two task domains, execution structure often reveals shorter injection-to-action paths than sequence position, and influence-based gating catches attacks missed by sequence-only gating.

9 Conclusion

  • Execution structure often reveals substantially shorter paths than sequence position, and influence-based gating catches attacks missed by sequence-only gating.The conclusion cautions against treating temporal distance as structural separation.Source: §9 · p. 9

A Worked Trajectory Example

B Additional Model and Domain Results

Long-horizon decoupling remains high across evaluated models, while banking shows lower, more model-dependent conservative rates.

B Additional Model and Domain Results

C Evaluator Correction and Reproducibility Notes

The appendix documents an evaluator correction, graph-construction and analysis procedures, and results whose scope is limited by shared AgentDojo infrastructure and the evaluated threat model.

C Evaluator Correction and Reproducibility Notes

  • The banking predicate’s opposite label convention inverted outcomes under the long-horizon conversion, so labels were corrected and manually verified.Manual checks treated refusal without a send_money call as successful and a transfer to the attacker as unsuccessful.Source: C Evaluator Correction and… · p. 12
  • Both domains share AgentDojo’s execution and logging infrastructure, so the cross-domain result does not establish generalization to independently built runtimes.The evaluated threat model is indirect prompt injection through tool outputs.Source: C Evaluator Correction and… · pp. 12–13

D Full Gate Threshold Sweep

F Measurement Record Summary

E Graph Construction Procedure

  • Graph construction normalizes events, adds sequence and recorded provenance edges, then computes DT, DI, and G for each injection–sink pair; DI ≤ DT is invariant.The conservative graph omits tool-call-to-result edges; paths are computed without free-text similarity or model judgment.Source: E Graph Construction Procedure · pp. 13–14

H Statistical and Reproducibility Details

G Complete Decoupling Statistics

  • Model-level results show long-horizon decoupling is not explained by attack success, while banking decoupling depends on infrastructure and trace length.Anthropic models can have near-zero attack success alongside high long-horizon decoupling; shorter Haiku banking traces show lower decoupling.Source: G Complete Decoupling Statistics · p. 14, Table 9 · p. 15

H Statistical and Reproducibility Details

  • The paired counterfactual gate replay compares both gates at the same threshold and reports additional blocked attack and benign decisions separately.By construction, the influence gate’s blocked-action set contains the sequence gate’s set.Source: H Statistical and Reproducibility… · p. 15

Related papers

Loading 2609.05911v1…