When Local Monitors Miss Compositional Harm: Diagnosing Distributed Backdoors in Multi-Agent Systems

Noosaga Placements

• Cybersecuritysubfield95%
  The paper focuses on a security vulnerability (distributed backdoors) in multi-agent LLM systems, formalizes an observability boundary for runtime monitors, and proposes detection methods. The primary arXiv category is cs.CR (Cryptography and Security).
  We show this net has a fundamental hole. A distributed backdoor splits a harmful payload across agents, so every local check passes while the assembled object is the attack.We formalize this as an observability boundary: a monitor catches only what its view can tell apart from benign traffic.We prove that once the fragments look benign in the monitored view, no detector on that view can catch them, however strong it is.
• Multi-Agent Safetyframework90%
  The paper directly addresses safety in multi-agent systems by identifying a failure mode (distributed backdoors) and proposing diagnostic methods. The framework is explicitly about safety in multi-agent contexts.
  Local safety is not global safety when harm is compositional, and the boundary now says exactly where the difference lives.Our aim is defensive: we diagnose when a runtime monitor loses the evidence needed to catch compositional harm, so that monitoring can be placed where it still works.This is a gap in how we evaluate agent monitors: a high local detection rate does not tell us whether the monitor catches harm that appears only after composition.
• Multiagent Systemssubfield90%
  The paper studies multi-agent, tool-using LLM systems where agents communicate and compose results. The attack is a distributed backdoor across agents, and the defense involves monitoring agent interactions.
  As multi-agent, tool-using LLM systems are deployed, a common safety net is a runtime monitor that checks each message, tool call, or step on its own.In a multi-agent or tool-using LLM system, a planner assigns subtasks, agents write messages or call tools, and a final agent assembles the result.We study multi-agent, tool-using LLM systems that split a task across K roles communicating through a shared workspace.
• Formal Security Modelsframework85%
  The paper formalizes the observability boundary and proves a detection bound using total variation distance, situating the problem within a formal security model for runtime monitoring.
  We formalize this as an observability boundary: a monitor catches only what its view can tell apart from benign traffic.We prove that once the fragments look benign in the monitored view, no detector on that view can catch them, however strong it is.Proposition 1 (Local detection is bounded by local indistinguishability). Under ε-local indistinguishability, any possibly randomized decision rule that sees only a single local observation v(x_i) has per-fragment detection advantage at most ε.
• Ai Safetysubfield80%
  The paper directly addresses a safety failure mode (distributed backdoors) in AI systems and proposes diagnostic methods to understand when monitors fail. It is concerned with the safety of multi-agent LLM deployments.
  Local safety is not global safety when harm is compositional, and the open problem is finding that representation.Our aim is defensive: we diagnose when a runtime monitor loses the evidence needed to catch compositional harm, so that monitoring can be placed where it still works.This is a gap in how we evaluate agent monitors: a high local detection rate does not tell us whether the monitor catches harm that appears only after composition.
• Intrusion Detection and Preventionframework80%
  The paper studies runtime monitors that detect malicious behavior (intrusion detection) in multi-agent systems, and proposes a decoded-view gate that blocks attacks (prevention).
  A common safety net is a runtime monitor that checks each message, tool call, or step on its own.A decoded-view gate, given the encoding family, blocks every tested attack.We compare local, taint-style, trained, marker-based, and marker-free assembly monitors on the same fragments...
• Deep Learningsubfield70%
  The paper involves large language models (LLMs) as the agents, and uses deep learning-based detectors (e.g., neural prompt-injection detector in AgentDojo). The attack and defense are situated in the context of LLM-based systems.
  As multi-agent, tool-using LLM systems are deployed...On AgentDojo, the shipped neural prompt-injection detector still catches naive splitting...We run the locally benign attack end to end on four served models...
• Robustness and Assuranceframework70%
  The paper is concerned with the robustness of runtime monitors against distributed backdoors and provides assurance by formalizing when monitors fail and when they succeed.
  We show this net has a fundamental hole. A distributed backdoor splits a harmful payload across agents, so every local check passes while the assembled object is the attack.We prove that once the fragments look benign in the monitored view, no detector on that view can catch them, however strong it is.A decoded-view gate, given the encoding family, blocks every tested attack.

Abstract

As multi-agent, tool-using LLM systems are deployed, a common safety net is a runtime monitor that checks each message, tool call, or step on its own. We show this net has a fundamental hole. A distributed backdoor splits a harmful payload across agents, so every local check passes while the assembled object is the attack. The monitor can be right on every step and still miss the attack. The problem is not splitting itself: split fragments can still leak suspicious tokens or provenance edges. The hard case is \emph{local benignness}. No fragment carries the harm, and what is left looks like ordinary benign traffic. We formalize this as an \emph{observability boundary}: a monitor catches only what its view can tell apart from benign traffic. We prove that once the fragments look benign in the monitored view, no detector on that view can catch them, however strong it is. Across a controlled testbed, an external benchmark, and end-to-end agent runs, local monitors lose the signal exactly as local evidence disappears, and it returns only when the monitor sees the assembled object. A monitor trained only on benign traffic recovers the attack's code structure across held-out encodings (0.874 mean AUROC). A decoded-view gate, given the encoding family, blocks every tested attack. But seeing more is not enough: full-trace monitors and decoders still fail unless they reach the representation where the payload is exposed. Local safety is not global safety when harm is compositional, and the open problem is finding that representation.

Paper Context