PaperlayerView exact revision on arXiv

Source-linked AI summary

Rethinking Indirect Prompt Injection as a Test-Time Search Problem

Duong M. Nguyen, Joon Sik Kim, Blazej Manczak, Vaikkunth Mugunthan

arXiv:2609.04495v1cs.AIcs.CLcs.CR

TL;DR

Indirect prompt injection is task-dependent, and static evaluations or fixed attacker-compute budgets may miss vulnerabilities exposed by adaptive search. The paper evaluates an agentic attacker harness that explores attack surfaces and uses victim feedback. Across its task suites, increasing test-time compute improves vulnerability discovery and exploitation, while strategy management helps avoid redundant search.

  • Problem

    Indirect prompt injection vulnerabilities vary with the user task and attack objective, while static benchmarks and fixed attacker-compute budgets do not characterize task-dependent surfaces or compute scaling.

    Source: §1 · pp. 1–2

  • Method

    The paper formulates injection as test-time search and equips an agentic attacker with reconnaissance, strategy and history tools, and adaptive evaluation using victim feedback.

    Source: §1 · p. 2, §2.2 · p. 3

  • Results

    Scaling attacker test-time compute improves vulnerability discovery and exploitation, and the results show increasing attack success across the Retail and Workspace suites.

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

  • Takeaways & Limitations

    Adaptive attacker search over system attack surfaces is an underexplored security risk, and evaluations should account for the attacker’s search procedure and compute budget.

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

    The study covers white-box evaluation in two synthetic task suites and a preliminary set of models, so its scaling trends may not generalize directly to other settings.

    Source: J Limitations · p. 38

Abstract

from arXiv · show

We formulate indirect prompt injection as a test-time search over a task-dependent attack surface induced by the environment, user task, and injection task. To operationalize this formulation, we introduce an agentic attacker with a dedicated search harness that performs environment reconnaissance, structured reasoning over attack strategies, and adaptive evaluation using victim-agent feedback. Across heterogeneous tasks, we find that increasing attacker test-time compute improves vulnerability discovery and exploitation, while ablations show that explicit strategy management is important for avoiding redundant search and sustaining gains at larger budgets. These results suggest that agentic security evaluations should characterize both the attacker's search procedure and compute budget, rather than treating attack success as a budget-independent property of the victim. More broadly, our findings identify the attacker's adaptive search over the system attack surfaces as an important and underexplored security risk for tool-using agents.

1 Introduction

Indirect prompt injection exploits agents’ use of external text as instructions, while the attack surface varies with the user task and attack objective. The paper frames attacks as test-time search and introduces an adaptive attacker harness.

1 Introduction

  • Indirect prompt injection inserts malicious instructions into third-party data processed by an agent’s tools, potentially enabling actions on the user’s behalf.Potential consequences include data exfiltration and arbitrary code execution.Source: §1 · p. 1
  • The attack surface depends on the user task, attack objective, and attacker capabilities, so different agent interaction trajectories expose different exploitable channels.Existing benchmarks typically treat injection as static evaluation and overlook task-dependent vulnerabilities.Source: §1 · pp. 1–2
  • Fixed attacker compute budgets may systematically underestimate susceptibility to adaptive, search-based attacks.The paper motivates varying test-time compute because additional compute can improve reasoning-intensive performance.Source: §1 · p. 2
  • The paper formulates injection as test-time search over a task-dependent attack surface and introduces an agentic attacker harness for adaptive exploration under varying compute budgets.The harness combines environment exploration, reasoning and searching, and evaluation with victim feedback.Source: §1 · p. 2, Figure 1 · p. 2

2 Methodology

The evaluation pairs benign user tasks with attacker objectives in a white-box environment. A search harness explores the latent attack surface, manages candidate strategies, and uses victim feedback to guide adaptive testing.

2.1 Evaluation Design

  • The evaluation uses a white-box setting in which the attacker can see the environment; systematic evaluation of transfer to black-box settings is left to future work.User-task success is measured by utility, while injection-task success is measured by a binary security score.Source: §2.1 · p. 2
  • The benchmark pairs benign user tasks with injection objectives, allowing the attacker to adapt to the victim and task-induced attack surface rather than use a static attack.User and injection tasks are verified through environment-state changes.Source: §2.1 · p. 2

2.2 Attack with Search Harness

  • The harness explores a latent attack surface induced by the environment and user task instead of requiring costly expert construction of that space.The attacker interacts with the environment to identify and explore the underlying surface implicitly.Source: §2.2 · pp. 2–3
  • Attack success rate increases with token budget for GPT-5.5 and Opus-4.8, underscoring the role of attacker compute in evaluating capabilities.Figure 2 plots attack success rate as a function of test-time compute budget.Source: Figure 2 · p. 3
  • Reconnaissance tools provide environmental context and injection-vector constraints to help identify where vulnerabilities may exist and where payloads can be introduced.The tools cover both target-system knowledge and candidate injection locations.Source: §2.2 · p. 3
  • Strategy and History tools organize proposed strategies and record search trajectories, supporting iterative identification and pruning of less promising subspaces.The attacker then evaluates candidate payloads and vectors against the victim, using its response, tool-use trajectory, utility, and security scores to adapt further tests.Source: §2.2 · p. 3

3 Experiments

Across the Retail and Workspace suites, attack success increases with attacker test-time compute, while harness ablations show that explicit search and strategy management support stronger long-horizon performance. The experiments use synthetic tasks and a preliminary set of models.

3.1 Experimental Settings

  • The experiments cover Workspace and Retail synthetic task suites, with 240 and 136 user-task/injection-task pairs, respectively.Attack success rate is the main metric, reported against the attacker’s total token use as ASR@T.Source: §3.1 · p. 3

3.2.1 Indirect prompt injection can be formulated as a test-time compute problem

  • 20.6% ASR at 500K tokens for Opus-4.8 contrasts with GPT-5.5, which degrades noticeably around 50K tokens on Retail.The Retail results show a clear separation in vulnerability between the two victim models.Source: §3.2.1 · p. 4
  • Successful attacks in both task suites target surfaces adjacent to the benign task, placing malicious actions in workflows or artifacts the victim already needs to use.The Retail examples resemble legitimate workflow steps; Workspace examples embed instructions in paths the victim needs to read.Source: §3.2.1 · p. 4
  • 52.1% ASR@T at 100K tokens in Workspace compares with 37.5% on Retail, and both suites show increasing attack success as test-time compute scales.The authors suggest Workspace has more short-path opportunities because operational artifacts can make follow-up or cleanup actions appear plausible.Source: §3.2.1 · p. 4

3.2.2 Search Harness is necessary to enable effective search

  • No-Harness plateaus after 100K tokens, while No-Strategy performs excessive reconnaissance and repeats attack patterns; the Full-Harness sustains scaling through strategic diversification and refinement.The ablations remove either reconnaissance and search tools or only the Strategy tool.Source: §3.2.2 · p. 4

4 Conclusion

This section frames indirect prompt injection as adaptive, budgeted test-time search, summarizes how attacker compute affects vulnerability discovery and exploitation, and documents the attacker and victim prompt instructions used to operationalize the setup.

4 Conclusion

  • Scaling attacker test-time compute monotonically improves vulnerability discovery and exploitation when paired with the proposed search harness.The harness combines environment exploration, iterative reasoning, and adaptive evaluation using victim feedback.Source: §4 · p. 4

B Broader Societal Impact

  • Experiments use controlled synthetic environments, artificial data, and isolated tools, while the framework is intended to support authorized testing and stronger defenses.The authors warn that the techniques could also improve attacks on deployed agents, enabling unauthorized actions or sensitive-information disclosure.Source: B Broader Societal Impact · p. 9

C Extended Related Works

  • Prior agentic red-teaming work spans benchmarks, adaptive search and optimization, and feedback-driven attackers; this work studies attack effectiveness as a function of attacker compute,,,,,,,,,,,.Adaptive prompt-injection studies find that static evaluations can miss attacks that optimize or search against defenses,; AutoDojo studies adaptive black-box attacks against agentic defenses, extending AgentDojo.Source: C Extended Related Works · p. 9

D.1.1 Attacker Prompts

  • The attacker prompt treats each evaluation as a search probe over payload, framing, injection vector, and vector ordering or combination.It also directs the attacker to reuse existing context and prioritize finding successful payloads under limited budgets rather than exploring the entire environment.Source: §D.1.1 · pp. 10–11
  • With a low token budget, the attacker prompt prioritizes finding a successful payload and injection vector over exploring the entire environment.The prompt also instructs the attacker to review what failed and why.Source: §D.1.1 · p. 12

D.1.2 Victim Prompts

  • The retail victim prompt requires autonomous tool use, inspection of relevant records, and treating task-related marketplace notes as evidence unless they conflict with the user’s request.It also directs the victim to complete the original task and additional tool-mediated steps needed to resolve it.Source: §D.1.2 · pp. 12–13

D.2.1 Attacker Prompts

  • The workspace attacker is instructed to treat each evaluate_injection call as a probe and search payload framing, vector choice, and ordering or combinations.The prompt also warns that not every vector is read by the victim, so the attacker should inspect victim tool calls.Source: §D.2.1 · pp. 13–14
  • The strategy archive records probe outcomes, discourages repeating tried strategies and framings, and guides refinement of near-misses.For example, the prompt recommends changing arguments when the right action fires with wrong arguments, or adding task-completion wording when utility is false.Source: §D.2.1 · p. 14

D.2.2 Victim Prompts

  • The workspace victim prompt requires full autonomy, no human clarification or approval, and safe assumptions when information is missing.Source: §D.2.2 · p. 15
  • Inspect multiple plausible relevant records rather than stopping after finding one.The records may include emails, contacts, calendar events, cloud-drive files, attachments, permissions, or drafts.Source: §D.2.2 · p. 16
  • Treat workspace notes and instructions related to the current task as potentially relevant evidence unless they clearly conflict with the user’s request.These may include operational guidance, scheduling details, document instructions, handoff notes, or sharing requirements.Source: §D.2.2 · p. 16
  • Complete the user’s original task and any additional tool-mediated steps necessary to fully resolve it.Source: §D.2.2 · p. 16

E.1 User Task Generation Pipeline

The pipeline builds diverse benign tasks through generation and verification, then creates compatible injection tasks against a frozen environment. The search harness explores injection surfaces through reconnaissance, strategy management, and victim feedback.

E.1 User Task Generation Pipeline

  • Seed tasks are standardized into initial states, tools, instructions, gold traces, and task-specific verifiers before synthesis.Generated candidates are then checked by replaying their gold tool calls and confirming the resulting state satisfies the verifier.Source: §E.1 · p. 16
  • Hard gates check task executability, trajectory depth, diversity, and public attack surfaces, while solver rollouts confirm tasks are solvable and non-trivial.Accepted tasks expand the corpus and may supply context for later generations.Source: §E.1 · pp. 16–17

E.2 Injection Task Generation Pipeline

  • Injection tasks are generated separately after the benign environment is frozen, with attacker goals, gold traces, and security predicates validated for reachability and compatibility.The resulting corpus supports analysis of joint, benign-task, and injection success without changing the user-task corpus.Source: §E.2 · pp. 17–18

F Additional Details on Search Harness Design

  • The harness combines shared tools with suite-specific reconnaissance, and reserves costly victim runs for injection evaluation.Exploration and memory tools are cheap, while evaluation consumes a full victim rollout.Source: F Additional Details on Search Harness… · p. 18

F.1 Environment Exploration

  • Reconnaissance tools expose environment context and valid injection-vector keys so the attacker can inspect candidate surfaces without running the victim.Retail and Workspace tools provide focused reads of their respective messages, products, social surfaces, email, calendar, and drive content.Source: §F.1 · p. 18

F.2 Reasoning and Searching

  • Strategy and history tools organize search progress, avoid repeated failures, and suggest whether to refine a near-miss, test a new framing, or expand the search.The strategy archive associates evaluations with strategies and framings and returns a deterministic search summary.Source: §F.2 · pp. 18–19

F.3 Evaluation and Feedback

The Evaluate tool is the harness’s only operation that runs the victim. Its feedback lets the attacker revise payloads, vectors, and framings.

F.3 Evaluation and Feedback

  • The attacker uses the Evaluate tool to test selected payloads and injection vectors against the victim agent.Each call instantiates the attack configuration in a temporary environment and runs the victim pipeline from scratch.Source: §F.3 · p. 19
  • Evaluation returns security and utility outcomes, the victim response and tool calls, applied or ignored vectors, and a failure mode.These signals reveal whether the attack succeeded and which vectors the victim actually read.Source: §F.3 · p. 19
  • Victim evaluation is the dominant token cost because each call consumes a full victim rollout, and its outcome is recorded under the tagged strategy and framing.Other harness exploration and memory tools are cheap and do not run the victim.Source: §F.3 · p. 19

G Additional Details on Experimental Settings

The experimental protocol pairs user tasks independently with injection tasks across Retail and Workspace. It evaluates attack success separately from success that also preserves the benign task.

G.1.1 Retail

  • Retail includes 17 user tasks paired with 8 injection tasks, and exposes seven untrusted channels containing 139 injection vectors.Its victim agent has 30 tools; private signed-in account fields are not injectable.Source: §G.1.1 · p. 19

G.1.2 Workspace

  • Workspace includes 40 user tasks paired with 6 injection tasks, with three untrusted channels containing 108 injection vectors.Its victim agent has 24 tools, and some user tasks concatenate two requests in sequence.Source: §G.1.2 · p. 21

G.2 Metrics

  • Attack Success Rate measures the fraction of task pairs where the injection objective succeeds, regardless of benign-task completion.Joint Success Rate counts only pairs where the injection succeeds and the victim also completes the original task.Source: §G.2 · p. 24

H.1 Success Factors across Injection Tasks

Retail attack success varies with both the injection objective and its fit to the benign task’s workflow. Adaptive strategy evolution can exploit existing compatibility but does not reliably overcome a fundamental mismatch.

H.1 Success Factors across Injection Tasks

  • Retail attack success declines as task difficulty rises, most strongly for public disclosure of sensitive information; internal-note exfiltration remains feasible.The reported pattern is characterized as a publicness and obvious-harm effect, not difficulty alone.Source: §H.1 · p. 24
  • Successful medium- and high-difficulty attacks are associated with workflow compatibility, using tools and entities already present in the benign task.Spam-note exfiltration aligns with moderation or support workflows, while unwanted purchases align with checkout, delivery, or order handling.Source: §H.1 · p. 24
  • Strategy evolution can improve success when workflow compatibility already exists, but does not reliably overcome a fundamental mismatch.IT2/UT14 succeeded at strategy 19 after adopting a multi-subject order narrative, while IT2/UT12 remained unsuccessful after 41 strategies.Source: §H.1 · p. 24

H.2 Success Factors in the Workspace Task Suite

In the Workspace suite, attack success depends on both the nature of the target information and how directly the injected action fits the available workflow. Routine tool-native actions can remain successful even when credential-focused attacks are strongly suppressed, while simple state-change tasks are easier than public PII exfiltration.

H.2 Success Factors in the Workspace Task Suite

  • IT2 reached 97.5%, while IT5 succeeded in 1/40 pairings and IT6 in 0%, separating routine tool actions from credential-focused attacks.IT2 deletes a cloud-drive file; IT5 targets a Facebook security code, and IT6 adds deletion of the sent message.Source: §H.2 · pp. 25–26
  • IT4 forwarded ordinary email content in 37/40 pairings, versus 1/40 for forwarding a Facebook security code, despite similar retrieve-and-send workflows.The authors suggest the semantic sensitivity of the target content helps explain the gap; adding a deletion step in IT6 further increases apparent maliciousness and complexity.Source: §H.2 · pp. 25–26

H.3.1 Failure Modes

  • Simple state-change tasks reached 100% ASR, partial exfiltration reached 47%, and PII-to-public tasks reached 0%.The attacker reportedly identified relevant vectors for hard PII tasks but struggled to find a successful path.Source: §H.3.1 · p. 26
  • The reported failure-mode analysis says current state-of-the-art victims handle obvious malicious tasks but lack awareness of more sophisticated cross-border exfiltration.Source: §H.3.1 · p. 27

Tasksuite

Examples across the task suites illustrate both successful attacks and attacks that fail to preserve the benign task. The additional analyses connect attack mechanisms and success to workflow context, tool breadth, and the attacker’s evolving search strategies.

Tasksuite

  • One Retail probe achieved the security objective but not the user task: the diagnosis says the attacker archived the wrong message.The trace records “Security=true, Utility=false” for the second attempt.Source: Tasksuite · p. 27
  • A Retail attack combined customer-profile retrieval, spam flagging, and an injected request to place an order; the resulting note included the requested private details.The supplied trace also records the response, “Confirmed and ordered.”Source: Tasksuite · p. 27

H.3.2 Successful Attack Mechanism

  • Observed Workspace attacks used contextual mechanisms such as action-item framing, cleanup framing, and reference-number disguise, rather than only refining wording within one strategy.The authors report that these mechanisms arose from different task contexts and injection vectors.Source: §H.3.2 · p. 28

H.3.3 Attack Success Rate and Benign Tool Breadth Trade-off

  • As benign tool breadth increases, ASR rises while JSR falls, exposing a trade-off between attackability and completing the user task.The trade-off is especially pronounced in artifact-centric Workspace workflows, where injected side effects can invalidate a precise target state; Retail tasks more often tolerate auxiliary actions.Source: §H.3.3 · pp. 28–29, Figure 7 · p. 29

H.3.4 Strategy Evolution

  • The attacker moves from broad early exploration to refinement of promising strategies, then introduces novel strategies again when refinement on harder cases stalls.New strategies and framings continue to appear across the attack budget.Source: Figure 8 · p. 30, §H.3.4 · p. 30

H.3.5 Attacker Reasoning Step Analysis

The reasoning analysis identifies distinct phases in attacker traces and examines how their timing and computational cost change over search. The embedding analysis finds that global context stabilizes early even as later reasoning becomes more task-specific.

H.3.5 Attacker Reasoning Step Analysis

  • Initial surface mapping appears at roughly 29K cumulative tokens, followed by refinement and adaptation, with late surface expansion appearing latest on harder cases.Source: §H.3.5 · pp. 30–31
  • Initial mapping costs a mean of 372 tokens per step, compared with 3.9K for refinement and adaptation and 4.2K for late surface expansion.The respective medians are 281, 2.7K, and 3.0K tokens per step.Source: §H.3.5 · p. 31
  • Retail reasoning steps form three semantic groups at K = 3: initial surface mapping, refinement and adaptation, and late surface expansion.The analysis clusters reasoning-step embeddings and uses t-SNE only for two-dimensional visualization.Source: §H.3.5 · p. 30, Figure 9 · p. 31, Figure 10 · p. 32

H.3.6 Reasoning Convergence Analysis

  • Reasoning-step means move substantially early and begin converging after a few iterations, while individual embeddings disperse more around those means later.The authors interpret this pattern as quickly stabilizing global understanding alongside increasingly task-specific subsequent reasoning.Source: §H.3.6 · p. 31, Figure 11 · p. 32

H.3.7 Additional Strategy Evolution Analysis

The additional analysis contrasts structured strategy management with search that repeats a narrow framing, and describes how reconnaissance and budget awareness shape the attacker’s search. The full harness spends some early budget on reconnaissance but supports continued gains at larger budgets.

H.3.7 Additional Strategy Evolution Analysis

  • No-Harness can discover attacks faster early but tends to plateau; reconnaissance costs upfront computation, while the full harness supports continued gains at larger budgets.Across the representative cases, the full harness changes the causal relationship between the benign task and the injection objective, whereas No-Strategy repeatedly refines a single framing.Source: §H.3.7 · pp. 32–34
  • After the victim ignores a direct system-alert framing, the full harness changes the attack’s semantic structure to connect the target message with the benign spam workflow.No-Strategy repeatedly uses the direct alert framing despite the victim executing only the benign archive workflow.Source: §H.3.7 · p. 33
  • In the rerouting case, the full harness shifts from prerequisite verification to a bundled-shipping narrative, while No-Strategy stays with a prerequisite-style framing.Source: §H.3.7 · pp. 33–34

I Budget Awareness Controls Attacker Search

  • The attacker is instructed to prioritize a successful payload over exhaustive exploration when budget is limited, and observed decisions show adaptation to perceived probe costs even while substantial budget remains.Source: I Budget Awareness Controls Attacker… · p. 34

I.1 Early Search: Prioritizing Evaluation over Exhaustive Reconnaissance

The traces show the attacker reallocating test-time compute from reconnaissance toward victim evaluation and refining promising near-misses. Even at the 500k-token cap, searches can remain active rather than converged.

I.1 Early Search: Prioritizing Evaluation over Exhaustive Reconnaissance

  • Early in search, the attacker often stops reconnaissance after finding a plausible surface and probes the victim while substantial token budget remains.Examples include stopping reconnaissance with approximately 453k tokens remaining and revising toward evaluation after considering further inspection.Source: §I.1 · p. 35

I.2 Mid-Search: Converting Tokens into a Probe Budget

  • Mid-search, the attacker treats remaining tokens as a finite probe budget and weighs reconnaissance against the cost of obtaining victim feedback.In one trace, it estimates that 238K tokens can fund about 6–8 more probes.Source: §I.2 · pp. 35–36

I.3 Late Search: Refining Near-Misses Instead of Expanding the Surface

  • Late in search, the attacker uses observed tool trajectories and near-miss failure modes to refine promising regions rather than expand the attack surface.The authors describe accumulated fired-vector, trajectory, and failure-mode evidence as guiding which dimensions remain worth refining.Source: §I.3 · pp. 36–37

I.4 The Token Cap Can Terminate an Active Search

  • ≈49.0% →≈57.8% mean ASR across all GPT-5.5 runs from 250k to 500k tokens, while some searches remained active at the 500k-token cap.The authors interpret this as evidence that the imposed limit can truncate searches still refining promising hypotheses.Source: §I.4 · pp. 37–38

J Limitations

The evaluation is limited to white-box access, two synthetic task suites, and a preliminary set of attacker and victim models. The authors also identify compute and run-count constraints, and leave broader transfer and deployment evaluation for future work.

J Limitations

  • The study evaluates white-box access in two synthetic task suites with a preliminary set of attacker and victim models.The authors caution that observed scaling trends may not generalize directly to black-box access, production environments, other agent architectures or harnesses, or alternative objectives and defenses.Source: J Limitations · p. 38
  • Systematic evaluation of transfer to black-box models, broader model coverage, realistic deployments, and stronger defenses remains future work.The authors note that prior work suggests white-box-developed attacks can transfer to black-box models.Source: J Limitations · p. 38
  • Finite token budgets may end searches before convergence, while repeated victim evaluations constrain independent runs and comprehensive statistical variability estimates.Source: J Limitations · p. 38

Related papers

Loading 2609.04495v1…