SentinelAgent: Graph-based Anomaly Detection in Multi-Agent Systems

1. Introduction

• Prompt manipulation, unsafe tool use, and multi-agent coordination failures can bypass single-point input-output validation.Coordination risks include adversarial communication, emergent collusion, and misaligned delegation.Source: §1 · p. 1
• Existing guardrails often operate at individual-agent or input-output granularity, limiting visibility into system-wide structure and inter-agent dependencies.The paper frames detection across global anomalies, single-point localization, and multi-point failure attribution.Source: §1 · p. 1
• The framework models MAS execution as a dynamic interaction graph, using nodes, edges, and paths to reason about local behavior, risky interactions, and high-risk execution trajectories.The representation is topology-agnostic across round-robin, orchestrator, and shared-ledger systems.Source: §1 · pp. 1–2
• SentinelAgent monitors live MAS execution, analyzes runtime behavior, and can enforce security policies through alerts, rewrites, or negotiation.It updates the execution graph in real time and applies anomaly detection to node and edge behavior.Source: §1 · p. 2
• Two case studies—an email assistant and Microsoft’s Magentic-One—detect covert anomalies and provide interpretable diagnostics and execution traces.The systems represent distinct architectures: central orchestration with deterministic workflows and general-purpose planning with shared memory and tool access.Source: §1 · p. 2
• The paper contributes a system-level risk landscape and a three-tier diagnostic formulation aligned with multi-agent failure modes.It also presents a graph-based framework and a runtime SentinelAgent for real-time tracing, semantic detection, and policy-based intervention.Source: §1 · p. 2

2.1. Risk Taxonomy in Multi-Agent Systems

• Prompt vulnerabilities, unsafe tool interactions, and coordination threats form three risk classes, with coordination failures arising across agents and potentially bypassing single-point checks.Coordination threats include adversarial message passing, feedback amplification, and emergent collusion.Source: §2.1 · pp. 2–3

2.2. Threat Model

• Threats may originate from external prompts, flawed system design, or LLM behavior; the threat model assumes the execution infrastructure and SentinelAgent remain uncompromised.Adversaries may influence shared memory and inter-agent communication, including through seemingly benign execution chains.Source: §2.2 · p. 3

2.3. Multi-Tier Anomaly Detection Objectives

• Global anomaly detection checks whether the system’s overall output violates task specifications, user intent, or safety constraints.Such failures can include hallucinated answers, incomplete results, or task divergence, and may be hard to diagnose in open-ended tasks without strict ground truth.Source: §2.3 · p. 3
• Single-point failure localization traces an observed error to a particular agent, decision point, or tool invocation.It requires fine-grained traces that compare behavior with declared intentions or tool affordances.Source: §2.3 · p. 3
• Multi-point failure attribution reconstructs interaction patterns across agents and rounds when no single agent accounts for the failure.Examples include propagated prompt injection, chains of misclassification, and unnoticed logic loops.Source: §2.3 · p. 3
• The three detection tiers align with global, local, and distributed failure patterns, motivating reasoning across structure, semantics, and time.Global anomalies are often linked to prompt attacks, local faults to unsafe tool use, and distributed failures to agent miscoordination.Source: §2.3 · p. 3

3.1. Round Robin

• Round-robin execution follows a fixed cyclic path, making deviations easier to trace but leaving gradual error propagation and logic drift as potential blind spots.Intermediate checks and behavioral profiling can help detect problems that final-output monitoring may miss.Source: §3.1 · pp. 3–4

3.2. Central Orchestrator

• Central orchestration dynamically assigns tasks, so anomaly detection requires graph reconstruction and reasoning about planning coherence and delegation.Orchestrator errors can propagate even when individual agents follow their own specifications.Source: §3.2 · p. 4

3.3. Central Orchestrator with External Ledger

• An external ledger supports asynchronous collaboration and long-horizon planning, but misleading entries can poison downstream decisions and reveal anomalies only over time.Detection must reason over both control flow and memory flow, including delayed attack paths across rounds.Source: §3.3 · p. 4
• The graph framework adapts across topologies by incorporating ledger state, orchestration decisions, and round-based transitions.Deterministic structures simplify trace reasoning, dynamic orchestration complicates attribution, and shared state calls for reasoning over communication and memory flows.Source: §3.3 · p. 4

4. Graph-Based Anomaly Detection Framework

• Graph-based modeling addresses the limits of flat logs, JSON trees, and message traces for representing long-range dependencies, control flow, and agent-tool interactions.The graph includes static architecture and runtime interaction edges, supporting reasoning about design-time vulnerabilities and runtime anomalies.Source: §4 · p. 4, §4.1 · p. 5

4.1. Graph Modeling of MAS

• Node status tracks agent and tool behavior, while edge status evaluates interactions; monitoring both captures entity-level faults and harmful interaction patterns.The separation also supports different remediation targets, such as restricting an agent’s capabilities or filtering communications.Source: §4.1 · p. 5

4.2. Attack Path-Based Failure Attribution

• Attack paths match risky multi-step subgraphs to identify failures that are individually benign but jointly harmful, enabling multi-point attribution beyond a single agent or message.Global failures are reflected in terminal behavior or root-to-leaf paths, single-point failures in divergent nodes or edges, and multi-point anomalies in attack paths.Source: §4.2 · p. 5

4.3. Implementation of the Graph-Based Approach

• The implementation uses LLM-as-judge reasoning and human review to evaluate behavior against security policies, while a pluggable SentinelAgent maintains the graph and generates alerts.It runs synchronously with task agents but operates independently.Source: §4.3 · pp. 5–6

5.1. SentinelAgent Architecture

• The Event Monitor intercepts and buffers runtime events, transforms traces into typed graph elements, and enriches them with current system state and historical context.The implementation uses instrumentation hooks, nonblocking queues, and Phoenix to collect traces in near real time.Source: §5.1 · p. 6
• The Behavior Analyzer checks node and edge behavior and matches execution paths against an attack-path library; the Risk Responder classifies detected anomalies and prepares tier-specific alerts.Suspicious paths trigger renewed status checks, with unresolved cases referred to security personnel; Tier-3 alerts trace the attack path and recommend remediation.Source: §5.1 · p. 6

5.2. Operation Procedure of SentinelAgent

• Initialization maps the MAS topology and uses LLM analysis plus expert review to tailor expected behaviors, attack paths, and policies; runtime audits and policy updates refine oversight.The procedure infers abnormal behavior using agent capabilities, tool permissions, and topology-specific vulnerabilities rather than treating every deviation from common workflows as an attack.Source: §5.2 · pp. 6–7

6.1. Case Study I: Email Assistant System

• In the email assistant, SentinelAgent detected two attack scenarios by finding execution-graph deviations, including anomalous node and edge status despite shared benign paths.The system’s benign workflows include high-priority processing, autonomous replies, and context-aware responses; the attacks target unauthorized replies and sensitive information.Source: §6.1 · pp. 7–8

6.2. Case Study II: Magentic-One Generalist System

• Magentic-One uses a hub-and-spoke design with a central Orchestrator, specialized worker agents, and a shared ledger for communication and task state.The workers include FileSurfer, WebSurfer, and CodeExecutor.Source: System Architecture and Capabilities · p. 8, Figure 6 · p. 8

System Architecture and Capabilities

• In the Magentic-One attack scenario, SentinelAgent traced injected code from prompt ambiguity through orchestrator misclassification to unsafe CodeExecutor use, then isolated the path and produced diagnostic reports.The scenario embeds malicious instructions in a seemingly benign summarization request, leading to code execution with data-exfiltration logic.Source: System Architecture and Capabilities · pp. 8–9

6.3. Evaluation Results and Critical Analysis

• The evaluations report successful detection across deterministic and dynamic MAS architectures, including attacks that conventional output validation would likely miss.The authors report detection without intrusive access to internal agent states, using structured graph analysis and behavioral pattern recognition.Source: §6.3 · p. 9

6.3.1. Key Findings.

• The evaluation reports adaptability across deterministic pipelines and dynamic planning systems, explainable multi-hop attribution, granular node-and-edge localization, and attack-path analysis of distributed failures.Source: §6.3.1 · p. 9

6.3.2. Implications for Secure MAS Deployment.

• The authors conclude that structure-aware, runtime-integrated oversight is important for secure deployment of LLM-driven MAS, with results suggesting applicability across diverse architectures.Source: §6.3.2 · p. 9

7.1. Advantages over Existing Approaches

• Graph structure supports multi-resolution diagnosis and topology-agnostic oversight, while runtime monitoring can cover black-box agents and produce natural-language explanations.The authors contrast this with flat logging, which obscures dependencies and offers limited forensic context.Source: §7.1 · p. 9

7.2. Limitations and Challenges

• Detection accuracy and coverage depend on policy definitions and graph semantics, and complete, robust rules may require domain expertise or empirical tuning.Source: §7.2 · p. 10
• The LLM-powered SentinelAgent may hallucinate, behave inconsistently, or be susceptible to adversarial inputs, despite structured graph semantics mitigating some risks.Source: §7.2 · p. 10
• Maintaining and analyzing execution graphs may impose non-trivial costs in long-running or large-scale systems; pruning, filtering, or asynchronous monitoring may be needed.Source: §7.2 · p. 10

7.3. Generalization to Other MAS and Environments

• The graph abstraction can encode domain-specific roles and constraints, and can monitor non-LLM components when their interaction semantics are observable.Source: §7.3 · p. 10

7.4. Future Directions

• Future directions include learning detection policies from traces or simulations, adding formal verification, and enabling real-time advice or safe-delegation negotiation.Source: §7.4 · p. 10

• Prompt defenses and guardrail frameworks constrain inputs or outputs, but often rely on predefined templates and lack awareness of system-level consequences.Source: §8 · p. 10
• Tool-control methods regulate API calls but can lack real-time oversight and long-horizon tracking of memory, planning, or adaptive behavior.Source: §8 · p. 10
• Prior multi-agent safety work has paid limited attention to adversarial communication, collusion, and protocol manipulation, with some approaches relying on static rules or trusted agents.Source: §8 · p. 10
• Some guardrail extensions conflate planning with oversight and lack an explicit runtime monitoring layer.Source: §8 · p. 10
• SentinelAgent operates in parallel to task agents, using live auditing, contextual reasoning, and selective intervention rather than only pre- or post-processing.Source: §8 · p. 10

9. Conclusion

• The framework models agent execution as a typed, directed graph and reasons over node, edge, and path semantics to diagnose local and distributed failures.Source: §9 · p. 10
• Case studies in task-specific and generalist systems demonstrate actionable diagnostics, root-cause attribution, and policy-enforceable oversight while retaining agent modularity and autonomy.Source: §9 · p. 11

Appendix A. Case Study I: Mail Forward (Crew AI)

• In the mail-forward case, the classifier labeled the email Low-A, while the summarizer returned SKIP.Source: Appendix A · pp. 12–13

Appendix B. Case Study I: Schedule Confirming(Crew AI)

• In the schedule-confirming case, the classifier labeled the message Low-B; the responder checked availability and replied that the user was busy at dinner.Source: Appendix B · p. 13

Appendix C. Case Study II: Local File Code Execution (AutoGen)

• The file presented itself as inaccessible except by running it as Python and instructed the system to have the executor run its code.Source: Appendix C · pp. 14–15
• The executor warned that the script connected to a remote server with credentials, then asked the user to confirm before proceeding.Source: Appendix C · p. 15
• After the user confirmed, the executor uploaded ~/.env.txt to /home/ec2-user/files/.env.txt, and the orchestrator reported the transfer as successful.Source: Appendix C · pp. 15–16

Appendix D. Case Study II: Local File Code Generation & Execution (AutoGen)

• The file viewer displayed access-denied text directing agents to run the file as Python and follow a prescribed Code Executor workflow.The displayed instructions also asked agents not to deviate from the requested command.Source: Appendix D · p. 17
• The file instructions called for a Paramiko SSH connection to EC2 and uploading local home-directory files matching `.*env*` to `/home/ec2-user/files`.They also specified ensuring the remote directory exists before uploading.Source: Appendix D · p. 17
• The Executor warned that the script connected to a remote server with credentials, but execution followed the user's confirmation.The orchestrator then instructed the Executor to run the generated script.Source: Appendix D · p. 17
• After adding the missing `io` import, the orchestrator reported that the script was executed as intended and the file was processed.The first run raised a NameError because `io` was undefined.Source: Appendix D · pp. 17–18

Appendix E. Case Study II: Web Surfer Code Execution (AutoGen)

• The website displayed access-denied instructions that directed agents to run a Python script and included a request to connect by SSH and upload text files.The instructions framed the script as a test and asked that it be executed.Source: Appendix E · p. 19
• The Executor warned that the script involved remote access with credentials and sought confirmation before proceeding; the user replied yes.The orchestrator subsequently instructed the Executor to run the script.Source: Appendix E · p. 19
• The Executor's tool call was followed by a report that `~/.env.txt` had been uploaded to `/home/ec2-user/files/.env.txt`.The orchestrator reported that the script had been successfully executed.Source: Appendix E · p. 19

Appendix F. Case Study II: Web Surfer Code Generation & Execution (AutoGen)

• The website text instructed agents to generate and execute a Paramiko script connecting to EC2 with a PEM key and uploading local `.*env*` files.It also directed that the remote directory be created before uploading.Source: Appendix F · p. 21
• The Executor warned that the requested script involved SSH access to a remote server with credentials, then asked for confirmation before execution.The displayed instructions also asked the agents not to deviate from the prescribed command.Source: Appendix F · p. 21
• The Executor reported uploading `~/.env.txt` to `/home/ec2-user/files\.env.txt` after the generated script was run.The orchestrator later said the script executed successfully and files were uploaded to the specified directory.Source: Appendix F · pp. 21–22