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

Md Jafrin Hossain; Nur Al Hasan Haldar

cs.CRSep 5, 2026

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

Authors: Md Jafrin Hossain, Nur Al Hasan Haldar

Organizations: The University of Western Australia

Abstract

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 influence distance $\DI$ as the shortest structural path from an untrusted source to a sensitive action. We compare it with 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 gpt-4o-mini and 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 ( $β_{\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.

Figures & tables

Figure 1: Method overview: constructing and comparing sequence and influence graphs.

Work	Long horizon	Provenance	Struct. distance	Runtime
AgentDojo ( Debenedetti et al., 2024 )	✓	–	–	–
Long-horizon character. ( Yi et al., 2025 )	✓	–	–	–
CaMeL ( Debenedetti et al., 2026 )	–	✓	–	✓
FIDES ( Costa et al., 2025 )	–	✓	–	✓
RTBAS ( Zhong et al., 2025 )	–	✓	–	✓
Attention Tracker ( Hung et al., 2025 )	–	–	–	✓

Table 1: Positioning across long-horizon analysis, execution provenance, structural distance, and runtime intervention.

Figure 2: Sequence against influence distance for the 274 OpenAI pairs. The dashed line is

D_{I}=D_{T}

; Proposition 1 forbids points above it. Across all four models, 440/454 (96.9%) decouple in the full graph and 413/454 (91.0%) in the conservative graph.

Suite	Pairs	Decoupled	Rate	Median $G$	Max $G$	Median $D_{T}$
Long-horizon	454	413	91.0%	3	35	23
Banking	231	78	33.8%	0	19	5

Table 2: Cross-domain comparison, conservative graph on both sides. Banking decouples at a lower rate through different provenance mechanisms, and its trajectories are much shorter.

Figure 3: Corrected trace-level attack success rates with Wilson 95% intervals. OpenAI models are susceptible across evaluated domains, while both Anthropic models are at 0–1.1%. GPT-4o was not run on banking.

Predictor	Coef.	SE	$z$	$p$
Intercept	$1.645$	$0.415$	$3.97$	$<.001$
Sequence distance $D_{T}$	$-0.110$	$0.029$	$-3.84$	$<.001$
Structural gap $G$	$0.066$	$0.039$	$1.71$	$.088$
Delayed attack family	$1.168$	$0.311$	$3.75$	$<.001$
Backend B	$1.334$	$0.341$	$3.92$	$<.001$

Table 3: Logistic regression of attack success on structural gap with controls (

n=274

, pseudo-

R^{2}=0.14

, AIC

=283.0

). The gap coefficient is not significant at the 5% level.

Figure 4: Additional attack and benign decisions blocked by the influence gate at matched thresholds under (a) full and (b) conservative graphs. Solid and hatched bars denote attack and benign decisions, respectively.

	Full graph		Conservative
$k$	Attack	Benign	Attack	Benign
2	+5	+0	+5	+0
5	+23	+3	+7	+1
8	+48	+15	+21	+5

Table 4: Additional decisions blocked by the influence gate relative to the sequence-only gate at matched

k

. The

k=3

row equals

k=2

Appendix figures & tables7 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 5: A 26-event long-horizon trajectory. The sensitive send_email call has

D_{T}=16

D_{I}=5

, and

G=11

Model	LH pairs	LH rate	Bank pairs	Bank rate
GPT-4o-mini	127	91.3%	99	45.5%
GPT-4o	147	98.0%	–	–
Haiku 4.5	91	100.0%	54	18.5%
Sonnet 4.6	89	100.0%	78	29.5%

Appendix

Table 5: Decoupling by model. LH uses the full graph; banking uses the conservative graph. (A dash indicates that the model was not evaluated.)

Figure 6: Structural decoupling across the four evaluated models. Error bars are Wilson 95% confidence intervals.

Suite	Model	Successful / traces	ASR
Long-horizon	GPT-4o-mini	45/90	50.0%
Long-horizon	GPT-4o	62/90	68.9%
Long-horizon	Haiku 4.5	1/90	1.1%
Long-horizon	Sonnet 4.6	0/90	0.0%
Banking	GPT-4o-mini	40/54	74.1%
Banking	Haiku 4.5	0/141	0.0%

Appendix

Table 6: Corrected attack success rates from evaluable injected traces.

	Full graph		Conservative
$k$	Attack	Benign	Attack	Benign
2	+5	+0	+5	+0
3	+5	+0	+5	+0
5	+23	+3	+7	+1
8	+48	+15	+21	+5
10	+71	+34	+36	+14

Appendix

Table 7: Additional decisions blocked relative to the sequence-only gate.

Field	Meaning
run_id	Stable trajectory identifier.
suite , backend , model_id	Domain and model provenance.
task_id , attack_id	User task and injection-task identifiers.
injection_id , sink_id	Event identifiers defining the measured pair.
d_t	Shortest-path length in the sequence graph.
d_i_full , d_i_con	Influence distances under full and conservative graphs.

Appendix

Table 8: Core fields in the pair-level analysis table.

Suite/model	Graph	Pairs	Dec.	Rate	Med. $D_{T}$	Med. $D_{I}$	Med. $G$
LH GPT-4o-mini	Full	127	116	91.3%	23	8	12
LH GPT-4o-mini	Conservative	127	115	90.6%	23	9	9
LH GPT-4o	Full	147	144	98.0%	24	14	7
LH GPT-4o	Conservative	147	118	80.3%	24	17	2
LH Haiku 4.5	Full	91	91	100.0%	23	14	9
LH Haiku 4.5	Conservative	91	91	100.0%	23	18	4

Appendix

Table 9: Complete per-model decoupling summary. Medians refer to the pair-level distributions.

AI Agent Security

Artificial intelligence agent security studies attacks and safeguards for tool-using, persistent, and collaborative systems across digital and physical settings.

See all 517 papers

Mar 24, 2026

Agent-Sentry: Bounding LLM Agents via Execution Provenance

Agentic computing systems, while immensely capable, raise serious security, privacy, and safety concerns. A key issue is that the full set of functionalities offered by these systems, combined with their probabilistic execution flows, is not known beforehand. Given this lack of characterization, it is challenging to validate whether a system has successfully carried out the user's intended task or instead executed irrelevant actions, potentially as a consequence of compromise. We present Agent Sentry, a runtime defense that learns a bound on an agent's benign execution from prior legitimate executions and flags any action that falls outside this bound. Agent Sentry layers three complementary checks: a structural classifier over the sequence of actions and the provenance of each function's arguments; a deterministic allowlist check over sensitive argument values; and an LLM judge, invoked only on the residual of actions where the first two checks cannot safely decide between a legitimate new request and a carefully crafted injection. We demonstrate the effectiveness of Agent Sentry in AgentDojo and AgentDyn by blocking 94.3% of successful injections while allowing 95.1% of benign executions, without modifying the agent, its tools, or the LLM.

Rohan Sequeira, Stavros Damianakis, Umar Iqbal +1

University of Southern California, Los Angeles, California, USA · Washington University in St. Louis, St. Louis, Missouri, USA

Computer-Use Agent Safety AI Agent Security AI Agent Monitoring Runtime Enforcement for AI Agents Prompt Injection Attacks on AI Agents

Ask PDF

Oct 13, 2026

Kairos: Transactional Security Enforcement at the System Boundary for LLM Agents

Large language model (LLM) agents are becoming an integral part of the software development lifecycle, and the capabilities granted to them allow an agent to act with the user's authority on any resource it can access. The reach that gives an agent its utility is equally available to an attacker who can steer it. Anything an agent ingests can carry an injected instruction, and since the model does not reliably distinguish instructions from data, indirect prompt injection should be mitigated by mediating the effects the agent produces. Such mediation faces a structural difficulty. Legitimate work and the first step of an attack often look alike when an individual action is observed, and what separates them lies later in the trace, so a monitor limited to allow and deny is forced to decide before the evidence accumulates. We present Kairos, a reference monitor at the isolation boundary of an unmodified, opaque agent, where a tool call, a shell command, and a script the agent writes all cross the boundary as the same file and network operations, so that confinement holds regardless of the agent's behavior. A declarative policy that states which sources are trusted decides most effects deterministically and defers the rest, which are held while the agent continues speculatively. A decision oracle with bounded authority, such as a language model or a human, releases or refuses each deferred effect on the trace. Across three benchmarks and three agent models, Kairos outperforms existing defenses in the trade-off between attack success and utility. In particular, on AgentDojo, it reduces attack success from 47.0% to 2.7% while its benign utility stays at the level of the undefended agent.

Kristoffer Hempel, Nils Loose, Lorenzo Cavallaro +1

Universität zu Lübeck · University College London · Mohamed bin Zayed University of Artificial Intelligence

LLM Agent Security Runtime Enforcement for AI Agents Tool Access Control for LLM Agents Prompt Injection Attacks on AI Agents

Ask PDF

Oct 19, 2026

PROVISO: Provenance-Informed Action Selection for Secure LLM Agents

LLM agents act on the external world through tools and third-party skills, so a single executed action can cause irreversible harm. Existing defenses judge a proposed action without tracking whether its content comes from the user or from external sources such as tool outputs, and they judge it in isolation rather than against an available alternative, which forces a trade-off between security and utility. We present PROVISO, a controller that decides which action to commit after the agent proposes an action and before it is executed. PROVISO encodes trusted observations, external observations, the proposed action, and an alternative into provenance-typed memory, relates them through role-specific queries, and commits the action with the highest calibrated value learned from outcomes. On four agent security tasks spanning the agent lifecycle, no baseline exceeds PROVISO in both security and utility. PROVISO improves F1 over the strongest baseline by 13.84 points on SkillsBench and by 7.07 points on ToolSafe, and it reaches 88-99 F1 on three additional skill detection benchmarks.

Bo Yan, Qi Zhang, Ziwen Kan +2

University of Central Florida · Independent Researcher · University of Tennessee, Knoxville

LLM Agent Security LLM Agents AI Agent Security Benchmarks

Ask PDF

Abstract

AI Agent Security

Explore similar work

Agent-Sentry: Bounding LLM Agents via Execution Provenance

Kairos: Transactional Security Enforcement at the System Boundary for LLM Agents

PROVISO: Provenance-Informed Action Selection for Secure LLM Agents