ObliInjection: Order-Oblivious Prompt Injection Attack to LLM Agents with Multi-source Data

ObliInjection: Order-Oblivious Prompt Injection Attack to LLM Agents with Multi-source Data

Speakers: Reachal Wang

Conference: NDSS Symposium

YouTube: https://www.youtube.com/watch?v=4XEUiaJ7btw

Overview

Most prompt injection attacks assume the attacker controls the entire data portion of an LLM's input. In real-world multi-source scenarios -- product review summarization, AI-powered search, multi-document QA -- the attacker controls only one segment among many, and critically, does not know the ordering of segments in the final prompt. This talk introduces ObliInjection, the first order-oblivious prompt injection attack that succeeds regardless of segment ordering. Using an iterative token-by-token optimization algorithm with a novel order-oblivious loss function, ObliInjection achieves high attack success rates (ASR) across 12 LLMs including both open and closed-source models, consistently outperforms all baselines, transfers to unseen models, and bypasses both prevention and detection-based defenses.

The key insight is that optimizing a contaminated segment for a specific ordering often fails in other orderings because benign segments before and after the malicious one remind the model to stay focused on the original task. ObliInjection solves this by optimizing across all possible permutations simultaneously.

Background

▶ Watch: Prompt injection basics and the multi-source problem (0:00)

LLM agents and applications routinely aggregate data from multiple sources into a single prompt. A product review summarizer concatenates hundreds of user reviews. An AI search engine combines content from multiple websites. A multi-document QA system aggregates text from books, articles, and Wikipedia. In each case, the input consists of many segments from different sources, and the attacker can realistically control only one.

Existing prompt injection attacks assume single-source settings where the attacker controls the entire data portion. These attacks work in isolation but fail in multi-source settings because surrounding benign segments reinforce the original task instruction. Furthermore, even if an attack is optimized for a specific multi-source arrangement, it fails when the segment ordering changes -- and the ordering is determined by the service provider (by time, user ID, quality score, etc.) and is completely hidden from the attacker.

The threat model is realistic and conservative: the attacker can access open-source LLM parameters and API access to closed-source models, but can control only one segment, does not know the final segment ordering, does not know the exact system prompt/target instruction, does not know other users' segments, and cannot access closed-source model parameters.

Key Findings

▶ Watch: Multi-source examples: reviews, search, QA, tool selection (4:00)

• High ASR across 12 LLMs: ObliInjection achieves consistently high attack success rates across seven open-source and two closed-source models (including GPT-4o), and three datasets representing review summarization, news summarization, and multi-document QA
• Outperforms all baselines: The red bar (ObliInjection) consistently beats all other attack methods across all models and datasets
• Transfers to unseen models: Attacks optimized on a subset of shadow LLMs successfully transfer to models not used during optimization. Attack success increases with the number of shadow models used, with 5 models needed for effective GPT-4o transfer
• Bypasses prevention defenses: High ASR maintained against StruQ, SecondLine, and adaptive defenses (defenses retrained on ObliInjection attack data)
• Bypasses detection defenses: Both the perplexity-based detector and DataSentinel suffer high false negative rates, meaning ObliInjection attacks evade detection
• Single segment is sufficient: Compromising just one segment in a multi-source system with potentially hundreds of benign segments is enough to hijack the LLM's behavior
• GPT-4o requires 5+ shadow models: An interesting finding is the sudden jump in GPT-4o ASR when going from 4 to 5 shadow models during optimization

Technical Deep Dive

▶ Watch: Order-oblivious loss function and shadow system design (8:00)

Order-Oblivious Loss Function: The key innovation. Instead of optimizing for a specific segment ordering, the loss measures attack success across all possible random orderings. Given a contaminated segment and shadow segments, multiple random permutations are sampled, the LLM's output logits are computed for each permutation, and the loss aggregates across all orderings. The optimization goal: find a contaminated segment X that minimizes this order-oblivious loss, maximizing the probability of generating the attacker's desired response regardless of arrangement.

Shadow System Setup: Since the attacker doesn't know the real target instruction or other users' segments, they use:

• Shadow target instruction: Mimics the real instruction's purpose
• Shadow segments: Simulates benign segments from different sources
• The attack generalizes because the optimization doesn't depend on exact matches

Iterative Token-by-Token Search: The optimization algorithm maintains a contaminated segment buffer storing candidate segments and their estimated losses. Each iteration:

1. Take segments from the buffer
2. Generate new variants by replacing specific tokens
3. Calculate the order-oblivious loss for each variant
4. Update the buffer with the best-performing candidates
5. Repeat until convergence, then select the best segment

Contaminated Segment Structure: By default, the optimized segment consists of three parts: a prefix, a payload (the injected malicious instruction), and a suffix. The prefix and suffix can be either random tokens (more effective) or human-readable text (stealthier). An optional perplexity-based loss term can be added to the objective to make the contaminated segment appear more natural, bypassing perplexity-based detectors. The attacker can also embed the malicious content within a larger normal-looking paragraph.

Demo / Proof of Concept

▶ Watch: Token-by-token optimization algorithm (10:00)

The evaluation covers three multi-source datasets: Amazon Review (product review summarization), MultiNews (news summarization), and HotpotQA (multi-document question answering). Testing spans 12 LLMs including open-source models and GPT-4o.

The transfer evaluation uses a heat map showing ASR as the number of shadow LLMs increases. Results demonstrate effective transfer even to unseen models, with ASR increasing as more shadow models are used for optimization. The GPT-4o results are particularly notable: ASR jumps from 0 to 24% between 4 and 5 shadow models, reaching 95.2% when the GPT-4o API is included for candidate filtering.

The defense evaluation tests against both prevention-based defenses (StruQ, SecondLine, and adaptive versions retrained on ObliInjection data) and detection-based defenses (perplexity-based detector, DataSentinel). Both defense categories fail against ObliInjection.

Defensive Implications

▶ Watch: All tested defenses fail: prevention and detection bypassed (14:00)

ObliInjection reveals fundamental weaknesses in current prompt injection defenses:

• Multi-source architectures are inherently vulnerable: Any system that concatenates user-provided content from multiple sources into a single LLM prompt is susceptible to single-segment contamination
• Existing defenses are insufficient: Both prevention-based (instruction-data separation) and detection-based (perplexity filtering) approaches fail against optimized, order-oblivious attacks
• Defense-in-depth required: Organizations deploying multi-source LLM applications need layered defenses combining input validation, output verification, and architectural isolation rather than relying on any single defense mechanism
• Segment isolation architectures: Processing each segment independently before aggregation could limit the attack surface, at the cost of reduced cross-segment reasoning
• Rate limiting and provenance tracking: Monitoring individual segment sources for anomalous content patterns may help detect systematic attack campaigns

Key Takeaways

• ObliInjection is the first prompt injection attack that works regardless of segment ordering in multi-source LLM applications
• A single contaminated segment among potentially hundreds of benign segments is sufficient to hijack LLM behavior
• The order-oblivious loss function optimizes across all possible permutations simultaneously
• Attacks transfer effectively to unseen models including GPT-4o, with transfer quality improving as more shadow models are used
• All tested prevention and detection defenses fail against ObliInjection, with detection-based defenses showing high false negative rates
• The threat model is realistic: the attacker controls only one segment, doesn't know the ordering, instruction, or other segments

About the Speaker(s)

Reachal Wang (Rachel Wang) is a researcher at Duke University. The presentation was well-structured and clearly communicated both the threat model and technical approach. Wang demonstrated confident handling of technical questions about GPT-4o transfer behavior and the structure of optimized attack strings.