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

Agent-Sentry: Bounding LLM Agents via Execution Provenance
Mar 24, 2026Rohan Sequeira, Stavros Damianakis, Umar Iqbal +1Computer-Use Agent Safety AI Agent Security
University of Southern California, Los Angeles, California, USA · Washington University in St. Louis, St. Louis, Missouri, USA
Kairos: Transactional Security Enforcement at the System Boundary for LLM Agents
Oct 13, 2026Kristoffer Hempel, Nils Loose, Lorenzo Cavallaro +1LLM Agent Security Runtime Enforcement for AI Agents
Universität zu Lübeck · University College London · Mohamed bin Zayed University of Artificial Intelligence
PROVISO: Provenance-Informed Action Selection for Secure LLM Agents
Oct 19, 2026Bo Yan, Qi Zhang, Ziwen Kan +2LLM Agent Security LLM Agents
University of Central Florida · Independent Researcher · University of Tennessee, Knoxville

Mar 24, 2026J/K move · Enter open · S save

Agent-Sentry: Bounding LLM Agents via Execution Provenance

Rohan Sequeira, Stavros Damianakis, Umar Iqbal, Konstantinos Psounis

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

Open paper AskPDF arXiv

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.

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