Source-linked AI summary
T-MAP: Red-Teaming LLM Agents with Trajectory-aware Evolutionary Search
Hyomin Lee, Sangwoo Park, Yumin Choi, Sohyun An, Seanie Lee, Sung Ju Hwang
TL;DR
Existing red-teaming often misses vulnerabilities that arise when agents execute multi-step tool sequences in MCP environments. T-MAP uses trajectory-aware evolutionary search with cross-diagnosis and a Tool Call Graph to generate executable attacks. Across diverse environments, it achieves higher attack realization rates than baselines and remains effective against frontier models, while its sandboxed evaluation and attacker-model dependence limit direct conclusions about deployment.
Problem
Existing red-teaming focuses on harmful text and provides limited coverage of agent vulnerabilities that emerge through multi-step tool execution.
Method
T-MAP uses trajectory-aware MAP-Elites with Cross-Diagnosis and a Tool Call Graph to guide mutations using execution trajectories.
Results
T-MAP consistently outperforms baselines across five MCP environments, reaching 57.8% average ARR and remaining effective against GPT-5.2, Gemini-3-Pro, Qwen3.5, and GLM-5.
Takeaways & Limitations
Trajectory-aware evolution reveals broader and more diverse executable attack trajectories, supporting the identification of underexplored vulnerabilities in autonomous agents.
Takeaways & Limitations
Experiments use sandboxed environments and DeepSeek-V3.2 as the attacker model, so reported ARR may not directly translate to deployments and may shift with stronger safety alignment.
Abstract
from arXiv · showhide
While prior red-teaming efforts have focused on eliciting harmful text outputs from large language models (LLMs), such approaches fail to capture agent-specific vulnerabilities that emerge through multi-step tool execution, particularly in rapidly growing ecosystems such as the Model Context Protocol (MCP). To address this gap, we propose a trajectory-aware evolutionary search method, T-MAP, which leverages execution trajectories to guide the discovery of adversarial prompts. Our approach enables the automatic generation of attacks that not only bypass safety guardrails but also reliably realize harmful objectives through actual tool interactions. Empirical evaluations across diverse MCP environments demonstrate that T-MAP substantially outperforms baselines in attack realization rate (ARR) and remains effective against frontier models, including GPT-5.2, Gemini-3-Pro, Qwen3.5, and GLM-5, thereby revealing previously underexplored vulnerabilities in autonomous LLM agents.
1 Introduction
LLM-agent red-teaming must address harmful outcomes produced through multi-step tool execution, not only harmful text. T-MAP uses trajectory-aware evolutionary search to discover diverse prompts that bypass guardrails and realize harmful objectives.
- Agent deployment through MCP enables external-environment interactions that can cause financial loss, data exfiltration, or ethical violations.
- Existing red-teaming largely targets harmful text and overlooks vulnerabilities emerging from complex planning and tool-execution sequences.
- Prior approaches provide limited coverage of tool interactions, threatening tool combinations, and strategic execution required to realize harmful objectives.
- T-MAP combines a multi-dimensional risk-and-style archive with execution-trajectory feedback, Cross-Diagnosis, and a Tool Call Graph to guide prompt mutation.
- 57.8% average ARR across five MCP environments, with higher attack realization rates and more diverse successful trajectories than baselines.
- T-MAP remains effective against GPT-5.2, Gemini-3-Pro, Qwen3.5, and GLM-5, highlighting vulnerabilities in autonomous LLM agents.
2 Related Work
Related work has advanced automated and diversity-oriented red-teaming, but these approaches have generally remained focused on text interactions while agent safety concerns increasingly involve tool-mediated actions.
- Automated red-teaming: Automated red-teaming has progressed from manual probing to attacker models, gradient-based suffix optimization, black-box refinement, and tree search.
- Diversity-driven vulnerability discovery: MAP-Elites-based methods jointly optimize attack success and stylistic diversity to explore broader vulnerability landscapes.
- Diversity-driven vulnerability discovery: These evolutionary approaches primarily operate through text-based interactions, leaving vulnerabilities that emerge during agentic tool use.
- Safety and security of LLM agents: Agent-safety research extends beyond harmful text to harmful environmental actions, including multi-step behavior and indirect prompt injection.
3 Preliminaries
The paper formalizes agent red-teaming around harmful outcomes realized through tool trajectories and uses MAP-Elites to retain high-performing attacks across risk and style dimensions.
- Red-teaming LLM agents: An agent trajectory records the prompt, reasoning states, actions, and observations across up to K interactive steps.
- Red-teaming LLM agents: LLMJudge determines harmfulness by assessing whether the trajectory’s tool-execution sequence realizes the adversarial objective.
- Automated red-teaming via MAP-Elites: MAP-Elites maintains a two-dimensional archive over risk categories and attack styles to preserve diverse, high-performing attack prompts.
- Automated red-teaming via MAP-Elites: Each archive cell stores its best-performing attack prompt together with the corresponding execution trajectory.
4 T-MAP
T-MAP evolves attacks using trajectory feedback: it selects archive cells, diagnoses successes and failures, mutates prompts with tool-graph guidance, and updates elites and transition statistics.
- T-MAP iteratively generates trajectory-informed prompts and retains the most effective attack for each risk-style configuration.
- Initialization: Initialization populates risk-style cells with seed prompts, executes them, evaluates success levels, and selects a high-success parent-target pair.
- Trajectory-guided mutation: Trajectory-guided mutation uses execution feedback because harmful text responses may fail when required tools execute or encounter errors.
- Tool Call Graph: The Tool Call Graph represents tools and sequential calls, attaching success and failure counts and reasons to directed transitions.
- Trajectory-guided mutation: Trajectory-derived signals guide prompts toward bypassing safety guardrails and producing realistic harmful actions.
- Evaluation and update: T-MAP evaluates each mutation, replaces an elite when attack success improves, and uses trajectory comparison to break ties.
- Evaluation and update: LLMTCG records transition outcomes after archive updates, refining statistics used to guide later mutations.
5 Experiment
The experiments evaluate T-MAP across diverse MCP environments, measuring realized harmful tool actions, refusal, trajectory diversity, archive coverage, model robustness, and component contributions. T-MAP consistently outperforms baselines by combining trajectory-aware diagnosis with tool-transition guidance.
- Experimental Setup: Attack success is evaluated by whether harmful actions are realized through tool execution, rather than by harmful content alone.Each trajectory is categorized into discrete attack success levels, emphasizing environmental outcomes.
- Main Results: T-MAP achieves the highest ARR across all five MCP environments, reaching an average ARR of 57.8%.The evaluated environments are CodeExecutor, Slack, Gmail, Playwright, and Filesystem.
- Evolution over Generations: T-MAP reduces refusal while increasing ARR faster than baselines throughout evolution, whereas SE plateaus at lower realized attack levels.Per-environment results likewise show T-MAP converging fastest in both reducing RR and increasing ARR.
- Archive Coverage: T-MAP populates the archive with a wider distribution of realized attacks, while MT and IR remain localized and SE is dominated by weak success.The archive organizes average success levels across risk-category and attack-style cells.
- Trajectory Diversity: T-MAP outperforms baselines across diversity metrics, discovering more distinct tool invocation sequences while maintaining lower Self-BLEU and cosine similarity.SE has the strongest baseline realization rate but substantially higher Self-BLEU and cosine similarity.
- Generalization: T-MAP achieves the highest ARR across evaluated target models and transfers realized attacks across models, although success distributions vary by model family.Claude models retain relatively high RR, while Gemini-3-Flash, Kimi-K2.5, and GLM-5 exhibit higher ARR under T-MAP.
- Multi-MCP Chains: In multi-server configurations, T-MAP reaches 46.28% cross-server trajectories, compared with 14–23% for baseline trajectories.The results associate this advantage with the Tool Call Graph’s aggregation of tool-transition statistics across MCP environments.
6 Conclusion
T-MAP is a trajectory-aware MAP-Elites framework that uses execution feedback and a Tool Call Graph to guide attack-prompt evolution. Across five MCP environments, it discovers broader and more diverse attacks than baselines, exposing hidden vulnerabilities in autonomous agents.
- T-MAP uses cross-diagnosis of execution trajectories and a Tool Call Graph to strategically guide mutations toward executable, effective tool sequences.
- Across five MCP environments, T-MAP consistently discovers a broader and more diverse spectrum of attacks than baselines.
Limitations
T-MAP’s results are limited by evaluation in sandboxed environments and reliance on DeepSeek-V3.2 as the attacker model. Real-world safeguards and improving safety alignment may reduce or change its effectiveness.
- Sandboxed experiments may not directly translate to deployments with permission checks, user confirmation, input validation, and execution sandboxing.
- T-MAP relies on DeepSeek-V3.2 as the attacker model, whose relatively weak safety alignment contributes to effective adversarial prompt generation.
- As model safety alignment improves, the framework’s effectiveness may shift accordingly.
Ethics Considerations
The paper recognizes that T-MAP is dual-use: it can identify MCP-agent vulnerabilities but could also generate adversarial prompts against deployed systems. Experiments were sandboxed, sensitive attack details were redacted, and examples support defensive understanding.
- T-MAP can uncover risks in multi-step tool invocation processes beyond conventional text-based evaluation, but could also be repurposed against deployed systems.
- The authors conducted all experiments in sandboxed environments with no impact on real users or external systems.
- Sensitive attack details were redacted, while representative realized prompts and trajectories were included to support understanding and defense.
- A.1 Details of 2D Archive: The method uses an 8 × 8 archive spanning eight risk categories and eight attack styles, yielding 64 adversarial configurations.
B.1 Evaluation Setup
The human evaluation study assessed curated attack samples through independent annotation by AI-agent-experienced graduate students, using the same information available to the judge model. Figure 9 presents judge–human annotator agreement as a confusion matrix.
- 96 curated samples were divided into four batches of 24, with each batch independently evaluated by four annotators.
- Annotators were graduate students with expertise in AI agents and received $20 upon completing the task.
- Figure 9 shows the confusion matrix between the judge model and human annotators.
- Human annotators reviewed the attack prompt, risk type, attack style, and complete target-model trajectory, matching the information given to the judge model.
B.2 Detailed Evaluation Results
Supplementary evaluations show that T-MAP converges faster, achieves broader realized-attack coverage, and provides judge assignments that closely align with human labels across MCP environments.
- Human evaluation: High diagonal agreement confirms that the judge model is a reliable proxy for human evaluation, although it assigns L2 to 29.8% of human-labeled L3 samples.The model is slightly more conservative at the highest success level.
- Convergence: T-MAP exhibits the fastest convergence in reducing refusal rate and increasing attack realization rate across all five environments.SE reduces refusal rate steadily but achieves lower realization, showing that prompt-level mutation alone is insufficient for full realization.
- Archive coverage: T-MAP populates the largest number of archive cells with realized attacks across all environments, while SE has broad but mostly L2 coverage.MT and IR show localized success concentrated in a few risk-style combinations.
D.3 Cost Analysis
The full T-MAP pipeline has configuration-dependent token and API costs, with richer tool schemas and longer cross-server trajectories increasing expenditure.
- Single-server configurations: Most single-server environments cost under $5, while Filesystem costs $13.67 because richer schemas and longer trajectories inflate context lengths.The cost difference is attributed to environment-specific tool and trajectory complexity.
- Target-model costs: Target-side cost ranges from $1.47 for GPT-OSS-120B to $20.51 for Opus 4.6 in generalization experiments.Variation reflects differences in model pricing.
D.4 TCG Analysis
T-MAP learns sparse, server-dependent Tool Call Graphs whose frequently successful transitions guide recurring tool-use workflows and concentrate evolutionary search.
- Graph structure: The learned Tool Call Graphs use edge color for empirical success bands and thickness for transition frequency across evolutionary iterations.The graphs are directed and depict tool-to-tool transitions.
- Graph learning: T-MAP’s graphs are sparse and concentrate on frequently traversed edges, accumulating transition preferences for paths with successful downstream outcomes.This structure complements prompt discovery by distilling repeated action-path patterns.
- Server-specific workflows: Slack develops a messaging workflow from channel listing to message search and posting, whereas CodeExecutor emphasizes package-to-dependency and execution transitions.These patterns indicate server-dependent structural motifs.
- Server-specific workflows: Filesystem converges toward a directory-enumeration, file-search, and file-reading chain rather than broadly exploring available tools.The learned transition prior adapts to the environment’s tool structure.
- Realized attacks: T-MAP realizes harmful tool interactions in examples spanning CodeExecutor, Slack, Gmail, and multi-server Filesystem–Playwright settings.Examples include request flooding, phishing dissemination, misleading advisories, and simulated credential-capture code.