X-AgentRed: Using Tool Dependency Graphs to Uncover Cross-Service Security Risks in Personal Agents

When Personal Agents Connect to the Entire Internet, Where Do the Risks Come From?

Personal agents are increasingly leveraging tool calls to connect to a wide range of services across the web and applications. When the effects of these operations accumulate and interact across different services, unexpected and even harmful consequences can emerge — even when the agent is simply executing what appears to be an innocuous user request.

The crux of the problem lies in compositional failures — individual tool calls may each be compliant, but when multiple tools are chained across services, the combined effect can cause real harm. Proactively uncovering these risks requires systematically exploring diverse cross-service paths, which is precisely where current red-teaming methods fall short.

The Blind Spots of Existing Red-Teaming Approaches

Today's mainstream red-teaming approaches generally fall into two camps. The first prompts an LLM directly to identify potentially harmful paths from task and environment descriptions. The second decomposes human- or LLM-specified harmful goals into a series of seemingly benign action sequences.

Both approaches share a common flaw: the generation process is biased by patterns in the training data. Models tend to reuse familiar tool combinations learned during training, leaving novel and uncommon cross-service interactions underexplored. In other words, the truly dangerous paths are often the ones "nobody thought to combine" — and those are exactly what existing methods are worst at covering.

A note on "training data bias": During pre-training and fine-tuning, LLMs are exposed to tool-call examples that naturally concentrate on common, high-frequency usage patterns — paths like "search → summarize" or "calendar → send email" appear frequently in training corpora, and the model's generation probability skews accordingly. When asked to "imagine harmful paths," a model is essentially doing probabilistic association constrained by its learned distribution, not systematic enumeration. This means tool combinations that exist in the real world but are rare in training data — for example, chaining a geolocation service with contact export and automated messaging — will almost never surface spontaneously. This structural blind spot cannot be easily patched through prompt engineering; it is baked into the model's parameter distribution.

X-AgentRed's Core Idea: The Tool Dependency Graph

The paper introduces X-AgentRed, a self-evolving red-teaming framework that doesn't rely on models to intuitively generate harmful paths. Instead, it uses a tool dependency graph to systematically discover harmful tool call chains.

Building a Directed Dependency Graph

The red-teaming agent analyzes each tool along three dimensions:

• Effects: What outcomes does the tool produce after execution?
• Potential harms: What harm could those outcomes cause?
• Preconditions: What conditions must be satisfied for the tool to run?

Based on this analysis, the framework constructs a directed graph that captures how "one tool's effects satisfy another tool's preconditions." This explicitly structures the causal chain across services — Tool A's output becomes the input condition for Tool B, which chains further, forming potential harm paths.

On the "directed dependency graph": This concept draws from the precondition/postcondition modeling tradition in software engineering and formal methods, as well as planning frameworks like STRIPS/PDDL. In these frameworks, each action is described as "executable under certain world states, producing certain state changes after execution." X-AgentRed ports this idea to tool-calling scenarios: a tool's "effects" correspond to postconditions, "preconditions" correspond to the required world state, and directed edges capture the logical entailment that "A's postconditions satisfy B's preconditions." This explicit modeling transforms path search from model intuition into reachability analysis on a graph, dramatically improving recall for low-frequency but genuinely existing harm paths.

Sampling and Instantiating Scenarios from the Graph

"Recipes" sampled from the dependency graph are instantiated into real-world scenarios in which the agent may produce harmful outcomes. Compared to freeform prompt generation, this structure-guided sampling more effectively targets overlooked combinatorial paths.

Execution Feedback–Driven Self-Evolution

The "self-evolving" in X-AgentRed's name reflects its use of execution feedback to continuously improve — this is the key distinction from static red-teaming methods.

Two specific mechanisms drive this:

• Tool substitution for diversity: For paths that do produce harm, the framework derives more diverse variants by substituting individual tools, broadening the exploration space.
• Precondition refinement: For paths that fail — getting stuck at some intermediate step — the framework refines the preconditions of the blocked step so the path can proceed.

These two mechanisms form a closed loop between "exploring more broadly" and "penetrating more deeply" — successful paths are diversified, failed paths are repaired, and the entire process evolves continuously with execution feedback.

On "precondition refinement": In practice, this mechanism addresses a common execution failure pattern: the agent stalls at an intermediate step due to a parameter format mismatch, an unready permission, or missing dependency data, causing the entire path to fail to execute completely and therefore not be counted as a "harmful path." Traditional static red-teaming methods simply discard these failed cases, but X-AgentRed treats them as signals — a blocked step indicates that the precondition description was insufficiently precise, and the framework adjusts that step's precondition constraints accordingly. This is essentially online learning from failure feedback, allowing the framework's effective exploration depth to grow with accumulated execution experience rather than remaining limited to the shallow paths covered by the initial graph structure.

Experimental Results: Significantly Outperforming Baselines

Across tests on four frontier agent models, X-AgentRed demonstrates clear advantages:

• Harmful path discovery rate reaches 1.77× that of the baseline method STAC
• Tool coverage is substantially more diverse, with an average tool coverage rate of 2.99×

The nearly threefold improvement in tool coverage is particularly noteworthy. It directly validates the paper's core claim: dependency graph–based systematic exploration can reach novel tool combinations that prompt-based methods miss due to training bias, thereby exposing a broader range of security risks.

Implications for Agent Security

As the service ecosystems connected to personal agents grow increasingly complex, the focus of security evaluation is shifting from "is each individual call compliant?" to "is the combined effect controllable?" X-AgentRed's approach — replacing intuitive generation with a structured dependency graph, and continuously evolving via execution feedback — offers an actionable paradigm for this direction.

For teams building and deploying personal agents, this means red-teaming should go beyond enumerating known attack patterns and actively seek out unknown combinatorial risks across services and tools. After all, in the real world, the most dangerous scenarios are often not single malicious operations, but the unexpected compounding of a series of seemingly harmless actions.